Shtetl-Optimized

In a post a year and a half ago, I offered a prize of $200 for proving something called the Generalized Linial-Nisan Conjecture, which basically said that almost k-wise independent distributions fool AC⁰ circuits.  (Go over to that post if you want to know what that means and why I cared about it.)

Well, I’m pleased to report that that’s a particular $200 I’ll never have to pay.  I just uploaded a new preprint to ECCC, entitled A Counterexample to the Generalized Linial-Nisan Conjecture.  (That’s the great thing about research: no matter what happens, you get a paper out of it.)

A couple friends commented that it was wise to name the ill-fated conjecture after other people rather than myself.  (Then again, who the hell names a conjecture after themselves?)

If you don’t feel like downloading the ECCC preprint, but do feel like scrolling down, here’s the abstract (with a few links inserted):

In earlier work, we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an oracle separating the decision versions would follow from what we called the Generalized Linial-Nisan (GLN) Conjecture: that “almost k-wise independent” distributions are indistinguishable from the uniform distribution by constant-depth circuits. The original Linial-Nisan Conjecture was recently proved by Braverman; we offered a $200 prize for the generalized version. In this paper, we save ourselves $200 by showing that the GLN Conjecture is false, at least for circuits of depth 3 and higher.
As a byproduct, our counterexample also implies that Π₂^p⊄P^NP relative to a random oracle with probability 1. It has been conjectured since the 1980s that PH is infinite relative to a random oracle, but the best previous result was NP≠coNP relative to a random oracle.
Finally, our counterexample implies that the famous results of Linial, Mansour, and Nisan, on the structure of AC⁰ functions, cannot be improved in several interesting respects.

To dispel any confusion, the $200 prize still stands for the original problem that the GLN Conjecture was meant to solve: namely, giving an oracle relative to which BQP is not in PH.  As I say in the paper, I remain optimistic about the prospects for solving that problem by a different approach, such as an elegant one recently proposed by Bill Fefferman and Chris Umans.  Also, it’s still possible that the GLN Conjecture is true for depth-two AC⁰ circuits (i.e., DNF formulas).  If so, that would imply the existence of an oracle relative to which BQP is not in AM—already a 17-year-old open problem—and net a respectable $100.

I promised myself I’d stop blogging about controversial issues whose mere mention could instigate a flamewar and permanently get me in trouble.  Well, today I’m going to violate that rule, by blogging about the difference relativized and unrelativized complexity classes.

Recently a colleague of mine, who works in the foundations of quantum mechanics, sent me a long list of questions about the seminal 1993 paper of Bernstein and Vazirani that introduced the complexity class BQP (Bounded-Error Quantum Polynomial-Time).  It was clear to me that all of his questions boiled down to a single point: the distinction between the relativized and unrelativized worlds.  This is an absolutely crucial distinction that trips up just about everyone when they’re first learning quantum computing.

So I fired off a response, which my colleague said he found extremely helpful.  It then occurred to me that what one person found helpful, another might as well—and that which makes 30% of my readers’ eyes glaze over with its thoroughgoing duh-obviousness, might be very thing that another 30% of my readers most want to see.  So without further ado, the two worlds of quantum complexity theory…

In the relativized world, we let our algorithms access potentially-powerful oracles, whose internal structure we don’t examine (think of Simon’s algorithm for concreteness).  In that world, we can indeed prove unconditionally that BPP≠BQP—that is, quantum computers can solve certain problems exponentially faster than classical computers, when both computers are given access to the same oracle.

In general, almost every “natural” complexity class has a relativized version associated with it, and the relativized versions tend to be much easier to separate than the unrelativized versions (it’s basically the difference between a masters or PhD thesis and a Fields Medal!)  So for example, within the relativized world, we can separate not only BPP from BQP, but also P from NP, NP from PSPACE, NP from BQP, etc.

By contrast, in the unrelativized world (where there are no oracles), we can’t separate any complexity classes between P and PSPACE.  Doing so is universally recognized as one of the biggest open problems in mathematics (in my opinion, it’s far-and-away the biggest problem).

Now, Bernstein and Vazirani proved that BQP is “sandwiched” between P and PSPACE.  For that reason, as they write in their paper, one can’t hope to prove P≠BQP in the unrelativized world without also proving P≠PSPACE.

Let’s move on to another major result from Bernstein and Vazirani’s paper, namely their oracle separation between BPP and BQP.  You might wonder: what’s the point of proving such a thing?  Well, the Bernstein-Vazirani oracle separation gave the first formal evidence that BQP “might” be larger than BPP.  For if BPP equaled BQP relative to every oracle, then in particular, they’d have to be equal relative to the empty oracle—that is, in the unrelativized world!

(The converse need not hold: it could be the case that BPP=BQP, despite the existence of an oracle that separates them.  So, again, separating complexity classes relative to an oracle can be thought of as a “baby step” toward separating them in the real world.)

But an even more important motivation for Bernstein and Vazirani’s oracle separation is that it led shortly afterward to a better oracle separation by Simon, and that, in turn, led to Shor’s factoring algorithm.

In a sense, what Shor did was to “remove the oracle” from Simon’s problem.  In other words, Shor found a concrete problem in the unrelativized world (namely factoring integers), which has a natural function associated with it (namely the modular exponentiation function, f(r) = x^r mod N) that one can usefully treat as an oracle.  Treating f as an oracle, one can then use a quantum algorithm related to Simon’s algorithm to find the period of f, and that in turn lets you factor integers in polynomial time.

Of course, Shor’s algorithm became much more famous than Simon’s algorithm, since the implications for computer science, cryptography, etc. were so much more concrete and dramatic than with an abstract oracle separation.  However, the downside is that the speedup of Shor’s algorithm is no longer unconditional: for all anyone knows today, there might also a fast classical algorithm to factor integers.  By contrast, the speedup of Simon’s algorithm (and of Bernstein-Vazirani before it) is an unconditional one.

I’ve been depressed all month about the oil spill.  So what better to cheer me up than a flurry of comments and emails asking me to comment on an Ars Technica story by Chris Lee, reporting that it’s now been proven once and for all that quantum computers don’t help with NP-complete problems?

Now, just to really put the screws on any optimists out there, a new paper has shown that adiabatic computers are actually quite bad at hard math problems …

What [the researchers] have shown is that, when adiabatic quantum computers are used to solve NP-complete problems, the energy gap between the lowest energy state and the next state up is not well behaved. Instead, it narrows faster than exponentially, meaning the adiabatic quantum computing cannot, even in principle, solve NP-complete problems faster than a classical computer …

In the end, they conclude that NP-complete problems are just as hard on an adiabatic quantum computer as on a classical computer. And, since earlier work showed the equivalence between different variants of quantum computers, that pretty much shuts down the possibility of any quantum computer helping with NP-complete problems.

I don’t think anyone in the field will be particularly surprised by this. The failure of earlier work to show that quantum computers offered a speed-up on any NP-complete problem indicated that it was likely that it simply was not possible.

I’m heartened by the progress we’ve made these last ten years: from overhyped and misleading claims that quantum computers can solve NP-complete problems in polynomial time, to overhyped and misleading claims that they can’t.

The link to the paper from the article is broken, and the article doesn’t give the names of the researchers involved, but from the context, I’m pretty sure the article’s attempting to talk about this paper by Boris Altshuler, Hari Krovi, and Jeremie Roland, amusingly entitled “Anderson localization casts clouds over adiabatic quantum optimization.”  This paper really is an interesting and important one—but alas, the Ars Technica story grossly misstates and exaggerates what it does.

For what I hope will be the last time, but I’m sure won’t: yes, almost everyone in the field believes it’s true that quantum computers can’t solve NP-complete problems in polynomial time.  But we have no idea at present how to prove anything of the kind.  In fact, we don’t even know how to prove classical computers can’t solve NP-complete problems in polynomial time (that’s called the P vs. NP question; maybe you’ve heard of it!).  Nor do we even know how to prove a conditional statement, like “quantum computers can’t solve NP-complete problems in polynomial time unless classical computers can also.”  Any such result would be the biggest advance in theoretical computer science at least since I was born.

So then what do Altshuler, Krovi, and Roland do?  They consider a specific quantum algorithm—namely, the quantum adiabatic algorithm with linear interpolation—applied to random instances of an NP-complete problem, namely Exact Cover.  They then argue, based on a combination of numerical simulations and perturbation theory approximation, that the spectral gap decreases exponentially (actually, like 1/n!), which would imply that the adiabatic algorithm generally requires exponential time to reach the ground state.

If that sounds pretty interesting, you’re right!  But what’s the fine print?  Well, let’s accept, for the sake of argument, Altshuler et al.’s claim that their conclusions about Exact Cover would likely generalize to 3SAT and other standard NP-complete problems.  Even then, there are three crucial caveats, all of which the Ars Technica story ignores:

1. Most importantly, the limitation (if it is one) applies only to one specific algorithm: namely the adiabatic optimization algorithm (with a specific interpolation schedule, but let’s ignore that for now).  Now, some people seem to think a limitation on the adiabatic algorithm implies a limitation of quantum computers in general, since “adiabatic is universal”—a buzzphrase that’s caused a lot of confusion.  In reality, what Aharonov et al. proved, in a beautiful paper six years ago, is that the adiabatic model of computation is universal.  But they were talking about something much more general than the adiabatic optimization algorithm. For example, the ground state of Aharonov et al.’s adiabatic process is not the solution to a combinatorial optimization problem, but rather a “history state” that encodes an entire computation itself.
2. The Altshuler et al. paper talks about random instances of the Exact Cover problem—but the uniform distribution over instances is just one particular distribution.  Even if the adiabatic algorithm doesn’t help there, it’s possible that there are other natural distributions over instances for which it exponentially outperforms (say) classical simulated annealing.
3. Finally, even given the above two caveats, Altshuler et al. only show that the adiabatic algorithm fails on random Exact Cover instances at a “physics level of rigor.”  In other words, their argument relies on a “perturbative approximation” that seems plausible but isn’t proved.  A cynic might retort that, at a “physics level of rigor,” we also know that P≠NP!  But such a cynic would be unfair.  I don’t want to knock Altshuler et al.’s contribution.  For almost two decades, there’s been a spectacularly fruitful interaction between the physicists and the math/CS folks in the study of random constraint satisfaction problems.  Indeed, many of the conjectures (or, in physics lingo, “results”) in this area that the physicists derived using their hocus-pocus methods, were later rigorously confirmed by the mathematicians, and I don’t know of any that were disconfirmed.  Even so, the distinction between a proof and a “physics proof” is one that seems worth insisting on—especially in theoretical computer science, an area that’s often far removed from conventional “physical intuition.”

In summary, while it feels like swimming through a burning oil slick to say so, I have to side with D-Wave about the Ars Technica piece (though my reasons are mostly different).

So congratulations, Ars Technica!  Like The Economist before you, you’ve successfully cast clouds over yourself when reporting about stuff I don’t understand.

PS. I’m at STOC’2010 right now, in exotic Cambridge, MA.  If you’re interested, here’s the talk I gave this morning, on “BQP and the Polynomial Hierarchy,” and here’s the talk my PhD student Andy Drucker gave, on “A Full Characterization of Quantum Advice.”  And Lance, please stop looking over my shoulder!

Recently a journalist asked me why we don’t yet have quantum computers.  Since I get that question, in some form, at least 300 times per day, I thought it might be worthwhile to collect my thoughts about it in one place.  The essay below doesn’t say anything that I and others in the field haven’t said many times before, so hardcore Shtetl-Optimized fans should probably skip it.  (Don’t worry, I’ll let y’all know when I have something new to say and am reckless enough to say it.)

---

When people ask me why we don’t yet have quantum computers, my first response is to imagine someone asking Charles Babbage in the 1820s: “so, when are we going to get these scalable classical computers?  by 1830? or maybe 1840?”  In that case, we know that it took more than a century for the technology to catch up with the theory (and in particular, for the transistor to be invented).  More generally, we have lots of precedents for a technology being imaginable decades or even centuries before it became technologically feasible—heavier-than-air flight is another example.  So there’s nothing weird or anomalous about our current situation.The central technological obstacle to building a scalable quantum computer is well-known, and is decoherence, or unwanted interaction between the computer and its external environment.  When information about a quantum state leaks into the outside world—by any means whatsoever, intended or not—the state loses its “quantumness” and reverts to being classical.  So to do a quantum computation, it’s necessary to keep the qubits (atomic nuclei, photons, or whatever else they are) almost fanatically isolated from their environment.  But at the same time, you also need to manipulate the qubits, move them around, etc., in such a way as to carry out the computation.  Those twin requirements are the reasons why the most famous ’success’ of practical quantum computing to date was factoring 15 into 3×5.

Indeed, the problem of decoherence is so severe that you might even conjecture that building a quantum computer is impossible in principle.  However, by now people have thought pretty hard about that possibility, and have failed to find any fundamental obstacle to quantum computing.  Indeed, the starting assumption that quantum computing “must be impossible” hasn’t led to a research program with any real successes.

On the positive side, by contrast, in the 1990s computer scientists and physicists developed the beautiful theory of quantum fault-tolerance, which shows that, as long as you can get the decoherence rate below a certain finite threshold (which current estimates put at somewhere around a 10^-3 probability of failure per qubit per gate time), you can fix the errors caused by decoherence faster than you introduce new ones, and thereby perform an arbitrarily long quantum computation.  (I like to think of this fault-tolerance threshold as analogous to the critical mass for an atomic bomb!)  So, today there are large research efforts in two directions: on the experimental side, to push down the decoherence rate, and on the theoretical side, to find error-correction schemes that can cope with higher decoherence rates.  Hopefully those efforts will “meet in the middle” someday, and then we’ll have quantum computers!

However, long before we see general-purpose quantum computers, I predict that we’ll see a proliferation of special-purpose quantum simulators—basically, quantum computers that are tailored to some specific physics, chemistry, or optimization problem.  Indeed, arguably we already have that today, in that we have plenty of many-particle entangled quantum systems (such as high temperature superconductors and quark-gluon plasmas) that we don’t know how to simulate efficiently on a classical computer.  You could think of all these systems as “quantum computers” that compute their own time evolution!  From this perspective, the challenge is “merely” to get a programmable quantum computer, one that can solve a problem of our choosing (like factoring a huge composite number).  But I can easily imagine gradual steps in that direction from what we already have over the next couple of decades.

Finally, maybe it’s worth mentioning that there have already been some significant spinoffs of quantum computing in classical computer science (see here for a beautiful survey of them).  Also, as “ordinary” transistors get closer and closer to the atomic scale, I predict that ideas from quantum information science will be increasingly relevant, if only to suppress the quantum effects that the chip designers don’t want!

There’s an article in this week’s New Scientist by Justin Mullins about unforgeable quantum money.  By the standards of “quantum mechanics journalism,” the article is actually really good; I’d encourage you to read it if you want to know what’s going on in this area.  In particular, Mullins correctly emphasizes that the point of studying quantum money is to understand quantum mechanics better, not to mint practical QCash anytime soon (to do the latter, you’d first have to solve the minor problem of the money decohering within microseconds…).

My main quibble is just that I think the article overstates my own role!  In my Complexity’09 paper, the main thing I showed is that secure quantum money that anyone can verify is possible, assuming the counterfeiters only have black-box access to the device for verifying the money.  I also showed that, to get quantum money that anyone can verify, you have to make computational assumptions.  (By contrast, Stephen Wiesner’s scheme from the 1960s, in which only the bank could verify the money, was information-theoretically secure.)  But in terms of coming up with actual candidate quantum money schemes (as well as breaking those schemes!), the other members of the “quantum money club”—Andy Lutomirski, Avinatan Hassidim, David Gosset, Ed Farhi, Peter Shor—have been more active than me.

Two other quibbles:

(1) Mullins writes: “Then last year, Aaronson proposed a new approach that does away with the banknote and concentrates instead on the stream of information that represents quantum cash.”  In Wiesner’s scheme, too, I think it was pretty clear that the “banknote with qubits stuck to it” was just a fun way to tell the story…

(2) The article does a good job of explaining the distinction between information-theoretic and computational security.  But it doesn’t stress that, with the latter, we can’t actually prove that any of the “hard problems” are hard, without also proving P≠NP!  (I’ll admit that the importance of this point is slightly hard to convey in a popular article, possibly because many people, or so I’m told, go about their lives without proving anything.)  The best we can do is show that, if you could solve this problem, then you could also solve this other problem that people have studied for a long time.  But in the case of quantum money, we don’t even know how to do that—which is what we meant when we wrote in our ICS paper that “it seems possible that public key quantum money intrinsically requires a new mathematical leap of faith.”

Considered as research topics in complexity theory, uncloneable quantum money, copy-protected quantum software, and so on are almost as wide-open today as public-key encryption was in the 1970s.  That is, we don’t have a compelling intuition as to whether these tasks are possible at all: all quantum mechanics does is open up the possibility of them, which wasn’t there in the classical world.  Unfortunately, in the case of quantum money, most of the ideas we’ve had for realizing the possibility have turned out to be insecure—often for non-obvious reasons.  Assuming quantum money is possible, we don’t know what the right protocols are, what types of math to base them on, or how to argue for their security.  So if you’re not impressed by the results we have, why don’t you try your hand at this quantum money business?  Maybe you’ll have better luck than we did.

(Addendum: I also have a PowerPoint presentation on quantum money, which ironically goes into more detail than my Complexity paper.)

Does this post finally herald my return to regular blogging after a months-long absence?

I don’t know.  For me, writing a Shtetl-Optimized entry always followed the same process: I’d get an idea and start typing, furiously rocking back and forth in my chair.  Then the voices in my head would pipe up: no, I can’t say that—what will everyone think?—judging from past experience, they’ll probably take offense—I can already see the commenters boiling me alive—maybe if I rephrased it, or, y’know, provided some context—but to explain the real context, I’d need a whole book—and who has the time for that?—better wait till after tenure—meantime, maybe I could blog about something light and uncontroversial instead—but then what’s the point?—we already have one GASARCH—well, I could always put off a decision till later—

Back in the blog’s heyday, I’d win these fights about 40% the time and the voices would win about 60%.  (In other words: if you’ve ever taken offense at an entry of mine, rest assured that you haven’t even seen the half of my drafts folder.)  But now that I have an actual stake in this shabby world—students to advise and look after, a tenure case to build, conceivably even a family to start—the voices win more like 98% of the time.  And that’s why my blogging fell off.

Occasionally, though, something comes along so uncomplicatedly joyous that I feel no reservations about sharing it with the world.  Such was the case this weekend, when I was somehow called upon to represent MIT’s EECS Department in the annual “Professor Talent Show” at Campus Preview Weekend.  This is an event where six faculty members square off, taking eight minutes each to

(1) explain why their department is the coolest,
(2) crack jokes, and
(3) possibly demonstrate a musical or athletic talent.

Then, using electronic clickers, the several hundred prefrosh in attendence vote for which major carried the day.  Though I had no absolutely no talent of any kind to demonstrate, and was up against a banjo-player, violinist, and basketball-spinner among other tough competitors, for some reason EECS won!  You can see my PowerPoint slides here:

The Future of Computer Science, and Why Every Other Major Sucks By Comparison
http://www.scottaaronson.com/talks/futurecs.ppt
(You can read the jokes that go along with each slide in the slide notes at the bottom.)

Update (4/15): I hadn’t realized at all that there’s actually a video of me giving the talk!  (Click on “Part 2.”)

I thought the eight people who still read this blog might be interested to know that the FOCS’2010 Call for Papers is now out.

Firstly, if you haven’t contributed to relief efforts in Haiti, you can do so (the charity linked to was recommended by a Haitian-American working at MIT CSAIL).  I wish I had something more useful to say about this tragedy, but I don’t.

For the past couple days, I’ve been at QIP’2010 in Zurich, Switzerland.  I’d had premonitions, even before arriving, that this was going to be an unusually awesome QIP.  Having been on the PC, I knew the strength of the technical program, and I’d learned that the turnout—320 participants—would be a record high.  My positive feelings only intensified when I saw the following in the hallway of my hotel:

My buzz reached a fever pitch when I entered the lecture hall and found giant, gourmet Swiss chocolate bars on every seat.

But I only knew for sure that this QIP would rock when my erstwhile adviser, Umesh Vazirani, gave his opening plenary talk on “New bridges between computer science and quantum computation.”  Umesh highlighted several developments, including:

1. the relationship I noticed last year between the BQP versus the polynomial hierarchy problem and the Generalized Linial-Nisan Conjecture.
2. the QIP=PSPACE breakthrough of Jain et al. (based on the recent multiplicative-weights update method from classical computer science).
3. recent breakthroughs in lattice-based cryptography (most famously, Gentry’s fully homomorphic encryption system), which took inspiration from the quantum computing work of Oded Regev five years ago.
4. the work of Broadbent, Fitzsimons, and Kashefi and independently Aharonov, Ben-Or, and Eban (for which I paid out pieces of the Aaronson $25.00 Prize), which lets a “classical” verifier (equipped with the ability to send single, unentangled qubits through a channel) verify an arbitrary quantum computation; and which Umesh illustrated by a story about a verifier investigating the claims of a shady, fly-by-night company called “Q-Wave.”

Umesh argued that the deepening connections between quantum computing and classical complexity theory—open problems in classical complexity being solved using quantum-inspired techniques, tools that weren’t available in the classical world until a year or two ago already being used for quantum purposes, etc.—represent one of the most exciting new developments in the field.

The combination of the chocolate bar (which I was already eating), and Umesh preaching so much truth from the pulpit, was heavenly.

Amazingly, subsequent talks managed to keep up the momentum.  Daniel Gottesman spoke about his work with Sandy Irani on the quantum complexity of translationally-invariant tiling and Hamiltonian problems.  By giving tools to say something useful about computational complexity even in cases where the only free parameter is the system size, Gottesman and Irani open up some exciting avenues for further work.  Jordan Kerenidis spoke about the effort to prove an analogue of the Valiant-Vazirani witness isolation theorem for QMA (Quantum Merlin-Arthur).  Stefano Pironio talked about how you can exploit the Bell inequality violations to generate a long random string starting from a short random seed, assuming only the locality of the laws of physics, and not assuming anything about the reliability of your randomness-generating devices.  This observation, which I find to be of great conceptual (and conceivably even practical) interest, is related to the so-called “Free Will Theorem” of Conway and Kochen, as well as to a result I proved eight years ago in my review of Stephen Wolfram’s book.  For Conway and Kochen, though, the motivation was to prove that “subatomic particles have free will” (a strange interpretation that I don’t by any means endorse!), while for me, the motivation was to prove that Wolfram was wrong.  Neither I nor (as far as I know) Conway and Kochen thought about the obvious-in-retrospect application to generating random numbers.  (Incidentally, if anyone’s interested, my talk slides from yesterday morning are here.)

There’s also been a great deal of excitement at this year’s QIP about the efficient simulation of quantum systems occurring in nature, using recent techniques for model-order reduction (including MERA, matrix product states, quantum metropolis sampling, area laws…).  I hope I haven’t just made John Sidles faint from excitement.

The full schedule is here; feel free to ask in the comments about any talks I didn’t mention.  If there’s enough interest, I might also write a followup post about the rest of the conference.

I’m at CWI in Amsterdam, after spending two weeks in Israel.  Next week I head to QIP’2010 in Zurich, and the week after that, to the Perimeter Institute in Waterloo.

The following meta-question emerged from a conversation with Dorit Aharonov two weeks ago:

What’s your favorite example of a result in theoretical computer science that works over finite fields, but doesn’t work (or isn’t known to work) over the reals or complex numbers?

Conversely, what’s your favorite example of a result in TCS that works over the reals or complex numbers, but doesn’t work (or isn’t known to work) over finite fields?

In either case, what’s the crucial property of the underlying field, that causes the result to work in one case but not the other?

By “crucial property”, I mean something like this:

1. There’s a natural metric (i.e., a distance measure) on the reals or complex numbers, but not on a finite field.
2. There’s a uniform distribution over a finite field, but not over the reals or complex numbers.

I’d especially be interested in properties that don’t reduce to one of the two above.