Shtetl-Optimized

Disclaimer: The White House Office of Science and Technology Policy has asked me to clarify that, although this post will contain a photograph of me standing near the President of the United States, nothing in the post, or in Shtetl-Optimized more generally, is endorsed in any way by the White House or the President.  You know, just in case you were wondering.

It’s a good thing that I chose a career in science rather than in public relations.

Within one century, government-sponsored scientific research radically changed the ways that human beings exist on this planet.  Electronics are possible because of the quantum revolution of the 1920s, a revolution that many of us are still trying to understand the full implications of.  While it benefited from a government monopoly, Bell Labs was able to invent and/or commercialize the transistor, the laser, the fiber-optic cable, and the communications satellite.  (As soon as Congress opened the telecom market to competitors, Bell Labs’ capacity to innovate was permanently crippled.)  Computers, the Internet, cell phones, nuclear energy, DNA testing, and widespread vaccination are a reality today largely because of a partnership between academic scientists and their governments, in the US and elsewhere, that started in earnest during World War II and has continued to the present.

I sort of imagined that, if you were reading this blog, then you knew all of that, and also knew that I knew it.  But I was mistaken.  In writing about what seemed to me like a slam-dunk issue for any thinking person—namely, protecting the 0.18% of the United States federal budget that goes to the National Science Foundation—I somehow managed to make enemies not only of the NSF’s opponents, who skewered me as an ivory-tower elitist, but also of many of its supporters, who either didn’t understand or didn’t appreciate my attempts at gallows humor.

Fortunately, today I have a happy story involving the NSF.  As Lance Fortnow kindly mentioned a month ago, I had the honor of being included in this year’s PECASE (Presidential Early Career Award for Scientists and Engineers) class.  Here I followed in the footsteps of Adam Smith and Sean Hallgren, two theoretical computer scientists from Penn State (and very nice people) who won last year.  The PECASE is given for a combination of research and outreach, so there’s little doubt this blog played a role, in addition (I hope!) to the research and teaching that I sometimes do in my spare time.  There’s no money in the PECASE, just a fun trip to DC for ceremonies and a photo-op with the President.

The day (last Monday) started with a ceremony in the Department of Agriculture building. There was a Color Guard, then a beautiful live performance of the national anthem, then short speeches, then a presentation of awards that resembled a high-school graduation, then a reception where they served these really nice smoked-salmon wraps, as well as chocolate truffles that were on sticks like lollipops.  The awardees’ families were all there with us, but unfortunately, only the awardees themselves were cleared to enter the White House complex for the presidential photo-op.  There was no Air Force One pickup to get to the White House: we took the Metro.  We arrived at the Eisenhower Executive Office Building, which is to the left of the White House, adjacent to the West Wing.  There were Christmas decorations all around.

After going through a security check, we were ushered into a room that seemed specially designed for presidential photo-ops.  It had staggered platforms for standing on, with curtains in the background.

I was allowed to bring my cellphone, but it didn’t work inside the White House.  There was a strict no-photography rule.

We were called to pose for the photo in order of height: people over 6ft in the back row, then people over 5ft 10in in the next two rows, etc.  I was lucky to be short enough to land a spot in the second-to-front row.  We stood there for about fifteen minutes while waiting for the President to arrive.

The organizer from the Office of Science and Technology Policy warned the women in the front row that last year, the President put his arm around them for the photo—so they should be prepared!

At 1:55pm, we received word that the President would arrive at 2:05pm, and at 2pm, we received word that he was on his way over.  Finally, at 2:05 on the dot, he bounded into the room and the PECASE awardees erupted into applause.  My MIT colleague Manolis Kellis bellowed “Mr. President!”, which made the President laugh.

The President looked and sounded pretty much the same as on TV.  I was happy to see that his lip looked fine.  He shook hands with everyone in the front row, assuring everyone else that they’d get a chance to shake his hand later as well.

(I’m the one wearing a tie with a little drawing of the MIT Stata Center on the bottom.)

The President spoke for about five minutes, while Secret Service agents stood unobtrusively in the corners of the room.  Here were his main points, as I remember them:

• He couldn’t be more proud of us.
• Science and technology are extremely important for the nation’s future.
• He’s been fighting for more science funding.  (At this, the PECASE awardees burst into applause again.)
• Science will be a highlight of his next State of the Union address.  (Hey, you read it here first.)
• He understands that the PECASE award is not just for research but also for outreach and education, which is great.
• As someone with two daughters, he’s especially happy to see so many female PECASE winners.
• He feels so honored to be able to pose for a photo with us.  (At this, everyone laughed.)
• He made a reference to “young people, which most of you still qualify as” (causing more laughter), and said he’s expecting us to “produce” and win some Nobel prizes.

As the rows cleared out, the President shook hands with everyone in turn.  A few people said Merry Christmas.  I just said “thank you,” and he said “thank you” back.  Then I quickly moved away, since I had a cold and was worried about giving it to him.  (Also, my hand was sweating for some reason—maybe because I was wearing a suit, which was definitely one of the more unusual aspects of the day for me!)

Immediately after the photo, we were escorted out of the Eisenhower Building.  (Apparently the PECASE awardees in some previous years got a tour of the White House, but we didn’t.)

Later in the afternoon, there was a reception at NSF headquarters for the 19 PECASE winners whose research was sponsored by NSF (the remaining 66 were sponsored by the National Institutes of Health, the Department of Energy, the Defense Department, NASA, or other agencies). After opening remarks by Subra Suresh, the new NSF director and previously Dean of Engineering at MIT, each of the awardees gave a 3-minute speech about his or her work. I really enjoyed listening to the other 18 talks (as for my own, I spoke too fast and probably lost people).

At the risk of annoying earnestness, I’d like to thank:

• My NSF program officer (and all-around favorite government official), Dmitri Maslov.
• Every reader of this blog who ever said anything positive (or at least non-negative) about it.
• The Office of Science and Technology Policy, for putting together an awesome day (and inducing me to wear a tie even though no one was being married, buried, or bar-mitzvahed).
• President Obama, for supporting science and education even in the face of determined opposition.
• My fellow American taxpayers, for bankrolling the NSF. May all who receive grants strive to be worthy of them.
• My family.

Follow

Years ago, Sasha Razborov taught me one of my all-time favorite jokes.

In the 1960s, a man starts handing out leaflets in Moscow’s Red Square. Needless to say, he’s immediately apprehended by the KGB. On examining the leaflets, however, the KGB agents discover that they’re just blank pieces of paper. “What is the meaning of this?” the agents demand.

“What could I write?” exclaims the man. “It’s so obvious!”

The lesson I’ve learned this week is that the man was wrong. In politics, nothing is ever too obvious.

Follow

Five years ago, not long after the founding of Shtetl-Optimized, I blogged about Alex Halderman: my best friend since seventh grade at Newtown Junior High School, now a famous security researcher and a computer science professor at the University of Michigan, and someone whose exploits seem to be worrying at least one government as much as Julian Assange’s.

In the past, Alex has demonstrated the futility of copy-protection schemes for music CDs, helped force the state of California to change its standards for electronic voting machines, and led a spectacular attack against an Internet voting pilot in Washington DC.  But Alex’s latest project is probably his most important and politically-riskiest yet.  Alex, Hari Prasad of India, and Rop Gonggrijp of the Netherlands demonstrated massive security problems with electronic voting machines in India (which are used by about 400 million people in each election, making them the most widely-used voting system on earth).  As a result of this work, Hari was arrested in his home and jailed by the Indian authorities, who threatened not to release him until he revealed the source of the voting machine that he, Alex, and Rop had analyzed.  After finally being released by a sympathetic judge, Hari flew to the United States, where he received the Electronic Frontier Foundation’s 2010 Pioneer Award.  I had the honor of meeting Hari at MIT during his and Alex’s subsequent US lecture tour.

But the story continues.  Earlier this week, after flying into India to give a talk at the International Conference on Information Systems Security (ICISS’2010) in Gandhinagar, Alex and Rop were detained at the New Delhi airport and threatened with deportation from India.  No explanation was given, even though the story became front-page news in India.  Finally, after refusing to board planes out of New Delhi without being given a reason in writing for their deportation, Alex and Rop were allowed to enter India, but only on the condition that they did so as “tourists.”  In particular, they were banned from presenting their research on electronic voting machines, and the relevant conference session was cancelled.

To those in the Indian government responsible for the harassment of Alex Halderman and Rop Gonggrijp and (more seriously) the imprisonment of Hari Prasad: shame on you!  And to Alex, Hari, and Rop: let the well-wishes of this blog be like a small, nerdy wind beneath your wings.

Follow

WARNING: This post makes (what turned out in retrospect to be) advanced use of sarcasm, irony, and absurdism.  Indeed, even after I added a disclaimer explaining the sarcasm, many commenters still responded as if I actually favored gutting the National Science Foundation.  (Unless, of course, those commenters were also being sarcastic—in which case, touche!)

The confusion is completely my fault.  When I write a post, I have in my mind a reader who’s read this blog for a while, and knows that obviously I don’t favor gutting the fraction of a percentage of the Federal budget devoted to the progress of human understanding and American leadership thereof; obviously the NSF wastes plenty of money, but if it didn’t, then it would be doing a terrible job, because research is all about trying stuff that has a good chance of failure; obviously if you were seriously looking for waste, you could find orders of magnitude more of it in the military and elsewhere.  So then the only remaining question is: how can we best have fun with a disgusting and contemptible situation?  I forgot how many people come to this blog not having any idea who I am or why I’m writing—and for that, I sincerely apologize.

Now, if you’d like a sarcasm-detection challenge, I did leave lots of hints in the following post that I didn’t actually agree with Congressman Smith.  See how many of them you can find!

As some of you may have heard, the incoming Republican majority in Congress has a new initiative called YouCut, which lets ordinary Americans like me propose government programs for termination.  So imagine how excited I was to learn that YouCut’s first target—yes, its first target—was that notoriously bloated white elephant, the National Science Foundation.  Admittedly, I’ve already tried to save NSF from some wasteful expenditures, in my occasional role as an NSF panel member.  But this is my first chance to join in as a plain US citizen.

In a video explaining the new initiative, Congressman Adrian Smith concedes that the NSF supports “worthy research in the hard sciences,” but then gives two examples of NSF grants that strike him as wasteful: one involving collaboration among soccer players, the other involving modeling the sound of breaking objects.  This article gives some more detail about the projects in question.

While I can’t wait to participate, I have a few questions before I start:

1. Exactly which sciences count as “hard”?  Once the pitchforks are raised, how far do we go?  Is math fair game?  What about economics, cosmology, evolutionary biology?
2. Has there ever been a research project that couldn’t be described in such a way as to sound absurd?  (“Even in the middle of a war, university academics in Chicago are spending taxpayer dollars in a quixotic attempt to smash teeny-tiny uranium atoms underneath a football field…”)
3. Years ago, several commenters on my and Lance’s blogs eloquently argued that science funding isn’t a traditional left vs. right issue, that Republicans are at least as friendly to science as Democrats, and that viewing the modern GOP as the “party of ignorance” is inaccurate, simplistic, and offensive.  Would any of those commenters kindly help us understand what’s going on?

Let me end this post with a request: I want all of my readers to visit the YouCut page, and propose that quantum computing and theoretical computer science research be completely eliminated.  Here’s my own CAREER Award; go ahead and cite it by number as a particularly egregious example of government waste.

See, I’m hungry for the honor (not to mention the free publicity) of seeing my own favorite research topics attacked on the floor of the House.  As we all know, it’s child’s play to make fun of theoretical computer science: its abstruseness, its obvious irrelevance to national goals—however infinitesimal the cost is compared to (say) corn subsidies or defense contracts for stuff the military doesn’t want, however gargantuan the payoffs of such research have been in the past.  So what are Reps. Eric Cantor and Adrian Smith waiting for?  I dare them to do it!

Obviously, though, before the House Republicans end American participation in theoretical computer science, they’ll want to familiarize themselves with what our tiny little field actually is.  To that end, let me humbly offer the links on the sidebar to the right as one place to get started.

Update (12/18):  When a friend read this post, his first reaction was that the sarcasm would be lost on most readers.  I didn’t believe him.  See, I exist in a frame of reference wherein, when the mob shows up at your house with torches, you don’t argue with them.  Instead you say: “Oh, so you’re the ones here to burn me?  Then please, let’s get started!  There’s plenty of flammable fat around my torso area.  Do you prefer rare, medium, or well done?”  That way, at least history will record you as having gone down with your middle finger proudly aloft, rather than cowering in a corner.  However, it’s now obvious that my friend was right.  So, for the literal-minded: I think reacting to our country’s debt crisis by looking for NSF grants to ridicule is a really terrible idea, for reasons that are so self-evident I’ll simply provide some blank space for you to fill them in yourself: _______________________________.   And, having devoted my whole career to quantum computing and theoretical computer science research, I don’t wish to see them eliminated.  On the other hand, if science in United States were going to be dismantled (which, despite the efforts of some politicians, I don’t think it will be), then I’d consider it an honor for theoretical computer science to be the first in the crosshairs.

Follow

It’s time someone said it.  There exists, among a small but vocal subset of the nerd community, a strange animus against computational complexity theory, which is often rooted in factual misunderstandings, and seems wholly out of proportion to any real shortcomings that complexity theory has.  Granted, every field of science has its backseat-drivers, those extralusionary intellects who feel sure they could best the experts, but haven’t expended any actual effort in solving the problems on which the experts are stuck.  But, perhaps because of the unusual accessibility of its open problems, complexity theory seems (I might be wrong) to attract more such naysayers than other mathematical fields.

It goes without saying that no intellectual pursuit is automatically entitled to respect: it has to earn it by actual accomplishments.  But even after complexity theory delivers spectacular accomplishments—from NP-completeness to PCPs to public-key cryptography to zero-knowledge proofs to quantum computing—the carping continues unabated.  It’s this phenomenon that I’d like to understand better.

Here are the main manifestations of anti-complexitism that I’ve witnessed:

“Monday-morning quarterbacking” of complexity breakthroughs.  For an example, see this thread on Lance and Bill’s blog, which is full of knowing comments seeking to minimize Ryan Williams’s recent NEXP vs. ACC breakthrough.  Some of these comments are strangely off the mark: for example, the new result is taken to task for being “nonconstructive,” relying on the ability to perform diagonalization within the huge set NEXP.  But we’ve known since Natural Proofs that, if you want to make progress on the P vs. NP question, then you’ll need “nonconstructive” techniques that seize on a special property of the function f being lower-bounded—and diagonalization remains one of the few examples of such a technique that we have.  On the other hand, we’ve also known that, if you do use diagonalization, then you’ll need to combine it with some new ingredient to get around both the relativization and algebrization barriers.  Ryan’s proof actually does all of that, which is why many of us are so excited about it.

Refusal to accept the incremental nature of complexity theory (which is shared by every other scientific field known to humankind).  To me, one of the more humorous criticisms of Ryan’s breakthrough is that it “merely” shows NEXP is not in ACC, and not (for example) that the MAJORITY function is not in ACC.  Granted, the statement NEXP⊄ACC is pathetically weak compared to what we believe is true.  But then again, what have you done that’s advanced circuit complexity by 1% as much as this “pathetic” lower bound?

Fervent desire to see complexity theorists get their comeuppance from an “outsider.”  The anonymous blog-commentariat’s pooh-poohing of the ACC breakthrough stands in contrast to the praise that same commentariat heaped on Vinay Deolalikar’s unsuccessful attempt at proving P≠NP a few months ago.  Even though Vinay and Ryan are both academic researchers working at industry labs (HP and IBM respectively), from reading the comments, it appears part of the reason for the differing reactions is that Deolalikar was seen as more of an “outsider.”  Now, I like to root for the underdog as much as the next American, but it’s worth remembering that every scientist starts as an outsider.  It was only a decade ago that Ryan and I were both nerdy kids at Cornell, trying to get our respective crazy ideas taken seriously by professors.  To paraphrase Niels Bohr, is a “scientific insider” anything more than an outsider who’s already made most of the egregious mistakes in some subfield?

Presenting obvious, universally-known limitations of asymptotic analysis as if they were new insights.  Yes, I’m aware that a polynomial-time algorithm can be impractical because of huge constant factors or a whopping exponent.  I’m aware that an NP-complete problem can be easy on those instances that arise in practice.  Even if I have a debilitating brain injury, so that I no longer remember my own name or how to count to 10, I like to think that I’ll still be aware of these facts.  To me, dismissing complexity theory because of its love affair with worst-case, asymptotic analysis is like dismissing physics because of its love affair with frictionless surfaces, point particles, elastic collisions, and ideal springs and resistors.  In both cases, people make the simplifying assumptions not because they’re under any illusions that the world really is that way, but rather because their goal is understanding.  And in both cases, the theory itself gives you the tools to complicate your model—to put legs and hooves on your spherical cow—until you get reasonably-accurate predictions for the practical problems that interest you.  (See: D. E. Knuth, The Art of Computer Programming.)

Dismissal of complexity theory as “not real mathematics.”  There’s no denying that complexity theory is young compared to (say) complex analysis, differential equations, or Lie groups.  But if you were choosing an area to work on, why would that be a point against complexity?  It means all the more to do and discover: instead of having the elegant, unifying theory presented to you in yellow books, you get to create it!  Furthermore, we’ve seen that the connections between complexity theory and “traditional” areas of mathematics are as deep as people want to make them (and often deeper): in recent years, metric embeddings, elliptic curves, algebraic geometry, and arithmetic combinatorics have all played starring roles in complexity results.  On the other hand, yes, sometimes you can achieve a complexity breakthrough the way Ryan did, not by using “deep” mathematics, but just by thinking incredibly hard about simple facts like fast matrix multiplication and the Time Hierarchy Theorem.  Again, that’s a negative?

Attacks on complexity theory for over-reliance on conjectures, even though almost every field outside mathematics (and quite a few within mathematics) rely on conjectures as well.  This one really gets me—and is the reason why I often point out that, if we complexity theorists were physicists, we would have declared P≠NP a law of nature decades ago, then looked back with pride on our far-reaching discovery about the workings of the universe.  The problem of rigorously proving the No-SuperSearch Law would have been relegated to the mathematical physicists, much like the problem of proving the consistency of (3+1)-dimensional quantum field theory.  Instead, because we complexity theorists have the custom of trumpeting what we can’t prove from the rooftops, we give our extralusionary friends the ammunition they need to regard us as dismal failures, should they so choose.  “So you landed on the moon?  How adorable.  But tell me, why does that represent even the slightest progress toward the real goal of visiting other galaxies?”  The response, which should be obvious, is that taunting mountain-climbers for being out-of-shape laggards works best when you’re at the peak of the mountain looking down at them, not at the base looking up.  But then again, if you were climbing the mountain too, you’d be less likely to want to taunt other climbers, even those behind you: for then the competitive instincts common to all humans would have to contend with the feeling of being part of a great and difficult shared enterprise.

Follow

I usually avoid blogging about my own papers—since, as a tenure-track faculty member, I prefer to be known as a media-whoring clown who trashes D-Wave Sudoku claims, bets $200,000 against alleged P≠NP proofs, and complains about his lecture notes being appropriated by Australian actresses to sell printers.  Any research that I happen to do is best kept secret, lest it interfere with that carefully-constructed persona.

Today, though, I’m making an exception.  On Thursday, my PhD student Alex Arkhipov and I finally finished our mammoth 94 95-page preprint on The Computational Complexity of Linear Optics, which we were writing for the past year.  (Remarkably, this is Alex’s first paper.  Congratulations, Alex!)  Never before was I involved in a project that forced me to learn so many unfamiliar things, from experimental quantum optics to random matrix theory to exotic complexity classes like BPP^NP and PostBQP.  (Alright, that last one wasn’t particularly unfamiliar, but the others were.)

In one sentence, the goal of our paper is to help bridge the yawning gap between what complexity theorists believe is true about quantum mechanics—namely, that it’s exponentially-hard to simulate on a classical computer—and what experimentalists can currently demonstrate.  To do so, we try to “meet the experimentalists halfway,” by proposing a linear-optical setup that seems significantly closer to practicality than (say) a universal quantum computer, but still solves a computational problem that we can show is intractable for classical computers, under plausible and clearly-stated hardness assumptions (which don’t just amount to “our system is hard to simulate”!).

Without further ado, here’s the abstract:

We give new evidence that quantum computers — moreover, rudimentary quantum computers built entirely out of linear-optical elements — cannot be efficiently simulated by classical computers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum computation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions.

Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then P^#P=BPP^NP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation.

Our main result suggests that even an approximate or noisy classical simulation would already imply a collapse of the polynomial hierarchy. For this, we need two unproven conjectures: the Permanent-of-Gaussians Conjecture, which says that it is #P-hard to approximate the permanent of a matrix A of independent N(0,1) Gaussian entries, with high probability over A; and the Permanent Anti-Concentration Conjecture, which says that |Per(A)|≥√(n!)/poly(n) with high probability over A. We present evidence for these conjectures, both of which seem interesting even apart from our application.

This paper does not assume knowledge of quantum optics. Indeed, part of its goal is to develop the beautiful theory of noninteracting bosons underlying our model, and its connection to the permanent function, in a self-contained way accessible to theoretical computer scientists.

As you can see from the abstract, there’s a huge amount still to be done—of which the most obvious is (1) proving our #P-hardness conjecture and (2) doing our experiment!  I’m also hopeful that people will take up the challenge of proving similar hardness results for other “rudimentary” quantum systems, besides linear optics.  In that vein, one immediate question is whether we can give evidence that the beautiful “commuting quantum computations” model of Bremner, Jozsa, and Shepherd is hard to simulate even approximately by a classical computer.

Here are a few options for anyone who’s slightly curious about our work, but not curious enough to, y’know, download the paper:

• My PowerPoint slides.
• Alex’s PowerPoint slides, which I like better than mine.
• A MathOverflow question that I posted yesterday about the Permanent Anti-Concentration Conjecture, and which was quickly answered by Terry Tao.
• A CS Theory StackExchange question about our paper posted by András Salamon, which I answered this morning.
• New: An interesting blog post about our work by Gil Kalai.

Anyway, the main purpose of this post was simply to provide a place for people with questions about our paper to ask them.  So, shoot!

Follow

When people want to emphasize how pathetically far we are from proving P≠NP, they often use the following argument: for godsakes, we can’t even prove that NEXP-complete problems aren’t solvable by depth-3, polynomial-size circuits consisting entirely of mod 6 gates!

But no more.

As some of you may have heard, recently Ryan Williams achieved a breakthrough in circuit lower bounds.  And as a result, now we can prove that NEXP-complete problems aren’t solvable by depth-3, polynomial-size circuits consisting entirely of mod 6 gates.

More generally, Williams proves that NEXP does not have ACC circuits of third-exponential size: that is, size f(n) where f(f(f(n))) is exponential.  Here NEXP means nondeterministic exponential time (the exponential-time analogue of NP), and was long a “barrier class” for circuit lower bounds.  (Note that, if we go even slightly above NEXP, to MA_EXP, then Buhrman, Fortnow, and Thierauf proved in 1998 that MA_EXP doesn’t have polynomial-size circuits of any depth, and here the polynomial can be improved to half-exponential.)  Meanwhile, by “ACC circuits” we mean a nonuniform family of constant-depth circuits consisting of AND, OR, NOT, and MOD m gates for arbitrary positive integers m.  ACC is another “barrier class” for circuit lower bounds: if we go even slightly below it, to AC0[p] (the same as ACC, except that now we only allow MOD p gates for some fixed prime p), then we’ve known how to prove exponential circuit-size lower bounds since the work of Razborov and Smolensky in the 1980s.

To achieve the combination of NEXP and ACC, Williams implements a program proposed in his previous STOC’2010 paper, for the specific case of ACC.  At the core of his lower bound is an algorithm for deciding satisfiability of ACC circuits, which does slightly (not much) better than brute-force search.  (The algorithm relies on, of all things, fast multiplication of rectangular matrices.)  While Williams’s techniques have nothing to do with Mulmuley’s GCT program, they do fit in well with the Mulmuleyist “flip” philosophy of “proving lower bounds by proving upper bounds.”

I haven’t verified Williams’s proof, but the high-level ideas are compelling—and while the result is one of the most spectacular of the decade, it’s not so far beyond the current frontier as to strain credulity.  Suffice it to say that I won’t be betting $200,000 against this one.

Congratulations, Ryan!

Update: Amusingly, if you google Ryan Williams ACC, you get a football player of the same name who was apparently Rookie of the Year in the Atlantic Coast Conference.  Let’s all link to Ryan’s paper from our homepages, and see if we can make our “ACC Rookie of the Year” win out!

Follow

Today I’m in College Park, Maryland, for a fun quantum information workshop.  I just came from Las Vegas, where I was at FOCS 2010, appropriately held at the Monte Carlo.  (Don’t tell anyone, but I also skipped out on part of the conference for a helicopter tour of the Grand Canyon.)

However, while I’ll be happy to answer questions about either of those conferences (or about the Grand Canyon, I guess), the rest of this post won’t be about them.  Instead, it will be about some relatively approachable-looking open problems in quantum complexity theory: basically, the problems that I’d be tackling today if I were a bright-eyed grad student instead of a senile, over-the-hill 29-year-old.

The inspiration for this open problems list came from the graduate course I’m currently teaching on Quantum Complexity Theory.  Just like when I taught this class two years ago, I’m asking every student to complete a term project, either individually or in groups of two.  Here’s the thing: assigning student projects in theoretical computer science turns out to be damn hard.  Even if you make it clear that a literature survey is fine, many of the students admirably want to do something original.  But how do you come up with a theory problem that

(a) hasn’t been solved, and

(b) can be solved by someone who’s just learning the material, with a high probability of success, in 1-2 months?

And thus it is that I present my sort-of updated version of my Ten Semi-Grand Challenges for Quantum Computing Theory.  Despite the original motivation, most of these problems are probably too hard for a student term project—but all of them, I think, have term-project-sized chunks that could be ripped off.  The new challenges list makes no claim whatsoever of comprehensiveness, and is heavily skewed toward problems that I, personally, have worked on.

Without further ado, and organized into seven topics, starting with the one closest to my heart:

Quantum Query Complexity

Can we use Reichardt’s breakthrough characterization of quantum query complexity by span programs and the negative-weight adversary method to obtain new results on quantum query complexity for concrete problems?

In the quantum black-box model, if we relax the assumption that the linear transformations are unitary, and merely require that, for every Boolean input x, the sum of the squares of the “amplitudes” of the accept states is a probability (i.e., belongs to [0,1]), do we ever get an asymptotically smaller query complexity?  What about an exponentially smaller query complexity?

Given a quantum algorithm that makes T queries, can we approximate its acceptance probability on most Boolean inputs using a classical algorithm that makes poly(T) queries?  (See here for more.)

Are randomized and quantum query complexities polynomially related for all functions f(x₁,…,x_n) that are invariant under permuting the indices 1,…,n (for example, the Collision and Element Distinctness functions)?  (In previous work with Ambainis, we showed randomized and quantum query complexities are polynomially related for all functions that are invariant under permuting both the indices and the values of x₁,…,x_n.)

Can every quantum algorithm that makes k queries to an n-bit string, be simulated by a randomized algorithm that makes n^1-1/2k queries?  Does the k-fold generalization of the Fourier Checking problem provide an example for which this conjectured bound is tight?

Let f be a black-box function, which is promised to be either 1-to-1 or 2-to-1.  Is there a polylog(n)-qubit quantum proof that f is 1-to-1, which can be verified using polylog(n) quantum queries to f?  (If not, then we get an oracle relative to which SZK is not in QMA.)

Let f be a black-box function, which is promised either to satisfy the Simon promise or to be one-to-one.  Can a prover with the power of BQP convince a BPP verifier that f is one-to-one?

Cryptography

Are there interesting functionalities, besides point functions, that can be quantumly copy-protected?

Can we give classical oracles relative to which publicly-verifiable quantum money and copy-protected quantum software are possible?

Is the GGM construction of pseudorandom functions from pseudorandom generators secure even against quantum adversaries?  If not, can we give an analogous construction that’s secure?

Intermediate Possibilities Between BPP And BQP

Is it true that every set of unitary quantum gates (acting on qubits) is either universal for quantum computation, or else simulable in classical polynomial time?

If a quantum computer is in a tree state at every time step, does it follow that the computer can be simulated in classical polynomial time (i.e., in BPP)?

If a quantum computer is in a separable mixed state at every time step, does it follow that the computer can be simulated in classical polynomial time?

Postselection

Can we take any quantum computational model that allows adaptive measurements, and simulate it by a model that allows postselected measurements instead?

What are the “weakest” models of quantum computation that yield all of PostBQP when combined with postselection on measurement outcomes?

Communication Complexity

In the Group Membership Problem, there is a finite group G known to both Alice and Bob.  Alice is given a subgroup H of G,  Bob is given an element x of G, and the problem is for Bob to decide whether x is in H.  What is the randomized one-way communication complexity of GM?  Can we prove a lower-bound better than the trivial log|G|, thereby separating randomized and quantum one-way communication complexities for a total Boolean function?

Are the randomized and quantum one-way communication complexities polynomially related for every total Boolean function f?  What about the randomized and quantum two-way communication complexities?

QMA(2)

Is QMA(2) contained in EXP?  To put it differently: let V be a two-outcome measurement, which acts on the tensor product of two n-dimensional Hilbert spaces. Is there a quasipolynomial-time classical algorithm that approximates max_|ψ>[V accepts |ψ>²] to constant additive error?

Is QMA(2) with real amplitudes the same thing as QMA(2) with complex amplitudes?

Quantum Computing With Locality Constraints

Let G be a graph with n vertices, and let U be an nxn unitary matrix with the property that u_ij≠0 only if (i,j) is an edge of G.  Then how efficiently can we represent (or approximate) U as a product of unitaries that are “local” with respect to G?  This is a vague question, but see my paper with Ambainis for ways of making it precise.

Given n bits arranged in a √nx√n square grid, suppose we want to know whether every row contains at least one ‘1’ bit.  Can we do this using an ~O(√n) quantum algorithm that is “local” in the sense defined by myself and Ambainis?  Can we beat the trivial upper bound of n^3/4?

Follow

So, I’ve decided to simultaneously do something positive for theoretical computer science, stimulate BQPology research at MIT, and solve the “problem” of having too much grant money by hiring a postdoc.  The main area of interest for this postdoc is quantum complexity theory, but I’ll also consider outstanding applicants of a more classical bent—in fact, the ideal applicant is someone equally excited to tackle meaty open problems in quantum complexity, classical complexity, or any combination of the two.  As a postdoc here, you’ll collaborate (I hope) with me and my PhD students, but you’ll also have plenty of opportunities for interaction with the other quantum computing theory folks at MIT (Peter Shor, Ed Farhi, Seth Lloyd…), as well as the other computational complexity folks (too many to list).  This postdoc is for one year, with the expectation of a renewal for a second year.

If you’re interested, email your CV, a link to your homepage, and what you consider your top 3 or 4 publications to aaronson@csail.mit.edu, and also arrange to have 3 rec letters emailed to me.  Feel free to apply even if you previously applied for other postdocs at MIT: this is a new opportunity that’s somewhat different from previous ones.  The application deadline is, shall we say, December 1^st?  Let me know if you have any questions.

Finally, while I was tempted to make “reading Shtetl-Optimized” an effective prerequisite for the postdoc, feel free to distribute this call for applications more widely.

Follow

A year ago, Timothy Gowers posted the following beautiful question to MathOverflow:

Are there any interesting examples of random NP-complete problems?
Here’s an example of the kind of thing I mean. Let’s consider a random instance of 3-SAT, where you choose enough clauses for the formula to be almost certainly unsatisfiable, but not too many more than that. So now you have a smallish random formula that is unsatisfiable.

Given that formula, you can then ask, for any subset of its clauses, whether that subset gives you a satisfiable formula. That is a random (because it depends on the original random collection of clauses) problem in NP. It also looks as though it ought to be pretty hard. But proving that it is usually NP-complete also seems to be hard, because you don’t have the usual freedom to simulate.

So my question is whether there are any results known that say that some randomized problem is NP-complete. (One can invent silly artificial examples like having a randomized part that has no effect on the problem — hence the word “interesting” in the question.)

On skimming this question, my first thought was: “aha, he’s obviously groping toward the well-studied notion of average-case complexity!  Let me generously enlighten him.”  But no, it turns out he wasn’t asking about average-case complexity, but about something different and novel.  Namely, the random generation of computational problems consisting of exponentially many instances, for which we’re then interested in the worst-case instance.  When I explained to Gil Kalai what Gowers wanted, Gil amusingly described it as the “converse of smoothed analysis.”  In smoothed analysis—one of many contributions for which Dan Spielman recently won the Nevanlinna Prize—we start with a worst-case instance of a problem (such as linear programming), then perturb the instance by adding some random noise.  Gowers wants to do the opposite: start from a random instance and then perform a “worst-case perturbation” of it.  (The closest existing notions I could think of were trapdoor one-way functions and other primitives in cryptography, which involve the random generation of a computational problem that’s then supposed to be hard on average.)

Anyway, I tossed the question onto my stack of “questions that could develop into whole new branches of theoretical computer science, if someone felt like developing them,” and pretty much forgot about it.  Then, at  dinner last night, I posed the question to Allan Sly, who’s visiting MIT to talk about his exciting new FOCS paper Computational transition at the uniqueness threshold.  Within an hour, Allan had emailed me a sketch of an NP-hardness proof for the “random 3SAT” problem that Gowers asked about.  I repost Allan’s solution here with his kind permission.

Group the n variables into N=n^ε groups of size n^1-ε, M₁,…M_N arbitrarily.  For each group M_i take all the clauses with all 3 variables in M_i such that it satisfies both the all 1 and the all 0 assignments i.e. clauses that have either 1 or 2 variables negated.  I think that just a first moment estimate should show that with high probability the only assignments on M_i that satisfies all of these clauses should be the all 1 assignment or the all 0 assignment – other assignments are just too unlikely.  So in taking these clauses we reduce to the case where we have constant values on each of the groups.

Once you have these clauses you can then treat each group as a new variable and can construct any SAT assignment on these new variables.  Because now you only need to find a clause with 1 variable in each M_i, M_j, M_k for each (i,j,k) ∈ [N]³ that has the right negations. With high probability all of them should exist so you should be able to make whatever SAT assignment on the N variables you want.

My back of the envelope calculation then suggests that as long as you have n^1+ε random clauses to begin with then this should be enough.

It’s not hard to see that Allan’s solution generalizes to 3-COLORING and other constraint satisfaction problems (maybe even all NP-complete CSPs?).  In retrospect, of course, the solution is embarrassingly simple, but one could easily generate other problems in the same vein for which proving NP-hardness was as nontrivial as you wanted it to be.  Further development of this new branch of theoretical computer science, as well as coming up with a catchy name for it, are left as exercises for the reader.

Follow