I’ve been enjoying Athens and the coast of Greece for the past four days. I was going to take a day trip to Delphi, for the sole purpose of blogging about having “queried the Oracle” there, but I ultimately decided to confine this trip to the unrelativized regions of Greece.
However, I do have something else related to oracles that I’d like to blog about today. Last week I put out a preprint on the ECCC (that’s the Electronic Colloquium on Computational Complexity for newbs), entitled “The Equivalence of Sampling and Searching.” There, I use Kolmogorov complexity to prove the surprising (to me) fact that
FBPP=FBQP if and only if SampP=SampBQP.
In other words: classical computers can efficiently solve every search (i.e., “functional” or “relational”) problem that quantum computers can solve, if and only if they can efficiently approximately sample the output distribution of every quantum circuit. (Note that, although this result involves the names of quantum complexity classes, it has almost nothing to do with quantum computing.) Anyway, when I gave a talk about this result at Hebrew University, Noam Nisan raised two excellent questions, neither of which I’d thought to ask and neither of which I knew the answers to:
Is there an oracle relative to which BPP=BQP but PromiseBPP≠PromiseBQP? (In other words: an oracle that makes classical and quantum computers equivalent for language decision problems, but different for promise problems?)
Is there an oracle relative to which PromiseBPP=PromiseBQP but FBPP≠FBQP? (In other words: an oracle that makes classical and quantum computers equivalent for promise problems, but different for search problems? Here FBPP and FBQP are the classes of search problems solvable in polynomial time by classical and quantum computers respectively—see my preprint for formal definitions of them.)
Affirmative answers to these questions would imply that any extension of my equivalence theorem to decision and promise problems would have to be non-relativizing. I’d be incredibly grateful for any thoughts about these questions, and will even offer a $5 reward for each one.
However, since I have a feeling that these oracle challenges won’t generate quite enough comments, let me now pour some gasoline on the fire. You may have noticed that what I did above, among other things, was to call attention to my own ECCC preprint. Up till today, I’ve had an informal policy of almost never using Shtetl-Optimized to blog about my own research, except indirectly (e.g., when I talk about open problems that arose out of my papers). I had three reasons for this policy: first, blogging about one’s own research always runs the severe risk of boring everyone. Second, after I’ve finished a paper, I’m usually bored with it; writing a blog entry that rehashes what’s already in the paper is usually the last thing I want to do. Third, and most importantly, I didn’t want to create the impression that I was using this blog to give my papers an “unfair advantage” over everyone else’s.
However, recently a consensus seems to have formed, among the community of disgruntled anonymous commenters on computational complexity blogs, that I’m some sort of clown who bets $200,000 against alleged P≠NP proofs for the sole reason that he’s unable to do any actual research of his own. While I ought to have the Obamalike composure to remain unaffected by such gutter-sniping, I have to admit that it pissed me off. To be sure, I am a clown who bets $200,000 against alleged P≠NP proofs instead of doing actual research. However, this is not because I can’t do actual research; rather, it’s because I don’t feel like it. To help prove this, I’ve decided to abandon my previous no-tooting-my-own-research-horn policy. So, anonymous commenters: you wanna know about my actual research? Well then, blog entries about actual research are what you’re gonna get—so much that you’ll wish you never brought it up.
Bloggingheads has just posted an hour-long diavlog between the cosmologist Anthony Aguirre and your humble blogger. Topics discussed include: the anthropic principle; how to do quantum mechanics if the universe is so large that there could be multiple copies of you; Nick Bostrom’s “God’s Coin Toss” thought experiment; the cosmological constant; the total amount of computation in the observable universe; whether it’s reasonable to restrict cosmology to our observable region and ignore everything beyond that; whether the universe “is” a computer; whether, when we ask the preceding question, we’re no better than those Renaissance folks who asked whether the universe “is” a clockwork mechanism; and other questions that neither Anthony, myself, nor anyone else is really qualified to address.
There was one point that sort of implicit in the discussion, but I noticed afterward that I never said explicitly, so let me do it now. The question of whether the universe “is” a computer, I see as almost too meaningless to deserve discussion. The reason is that the notion of “computation” is so broad that pretty much any system, following any sort of rules whatsoever (yes, even non-Turing-computable rules) could be regarded as some sort of computation. So the right question to ask is not whether the universe is a computer, but rather what kind of computer it is. How many bits can it store? How many operations can it perform? What’s the class of problems that it can solve in polynomial time?
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) = xr 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:
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.
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.
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.)
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:
the relationship I noticed last year between the BQP versus the polynomial hierarchy problem and the Generalized Linial-Nisan Conjecture.
the QIP=PSPACE breakthrough of Jain et al. (based on the recent multiplicative-weights update method from classical computer science).
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.
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.
Several people asked me to comment on an entry by Hartmut Neven in the Google Research Blog, about using D-Wave’s “quantum” computers for image recognition.
I said nothing: what is there to say? Didn’t I already spend enough time on this subject for 10400 lifetimes? I want to create, explore, discover things that no one expected—not be some talking-head playing his assigned role in a script, a blogger-pundit who journalists know they can rely on to say “f(X)” whenever X happens. Even if f(X) is true. Why can’t I just tell the world what f is and be done with it?
Then more people asked me to comment.
I set the matter aside. I worked on the complexity problem that’s currently obsessing me. I met with students, sent recommendation letters, answered emails, went ice-skating with my girlfriend.
Then more people asked me to comment.
And I thought: yes, I believe it’s vital for scientists to communicate with the broader public, not just a few colleagues. And yes, it’s important for scientists to offer a skeptical perspective on the news—since otherwise, they implicitly cede the field to those making dubious and unsubstantiated claims. And yes, blogging is a wonderful tool for scientists to connect directly with anyone in the world who’s curious about their work. But isn’t there some statute of limitations on a given story? When does it end? And why me?
Then more people asked me to comment—so I wrote the following only-slightly-fictionalized exchange.
Skeptic: Let me see if I understand correctly. After three years, you still haven’t demonstrated two-qubit entanglement in a superconducting device (as the group at Yale appears to have done recently)? You still haven’t explained how your “quantum computer” demos actually exploit any quantum effects? While some of your employees are authoring or coauthoring perfectly-reasonable papers on various QC topics, those papers still bear essentially zero relation to your marketing hype? The academic physicists working on superconducting QC—who have no interest in being scooped—still pay almost no attention to you? So, what exactly has changed since the last ten iterations? Why are we still talking?
D-Wave: Then you must not have read our latest press release! Your questions are all obsolete, because now we’re recruiting thousands of volunteers over the Internet to study the power of adiabatic quantum computing!
Onlooker: Hmm, an interesting counterargument! D-Wave might not be using quantum mechanics, but they are using the Internet! And their new project even has a cool code-name: “AQUA@home”! So, skeptic, how do you respond to that?
Skeptic (distractedly): You know, when I was eight years old, and dreamed of building starships and artificial intelligences in my basement, my first order of business was always to invent code-names—not just for the projects themselves, but for every little subcomponent of them. The second order of business was to think through the marketing aspects. What should the robot look like? What recreational facilities should be available on the starship, and what color should it be painted? It really, genuinely felt like I was making concrete progress toward realizing my plans. Sure, the engine and control system still needed to be built, but at least I had code-names and “design specs”! How many others had even gotten that far?
D-Wave: Who cares? This isn’t some children’s game. Keep in mind that we’re delivering a product—serving our customers, by solving the 4-by-4 Sudoku puzzles they rely on to keep their businesses running.
Skeptic: We’ve been through this how many times? A pigeon can probably be trained to solve 4-by-4 Sudokus. So the only relevant questions concern the details of how you solve them. For example, how do you encode a problem instance? How much of the work is done in the encoding procedure itself? What evidence do you have for quantum coherence at intermediate points of the computation? Can you measure an entanglement witness, to give people confidence that you’re doing something other than classical simulated annealing?
Onlooker: Hmm, those do seem like important questions…
D-Wave: But they’re based on outdated premises! Today, we’re pleased to announce that, using what might be a quantum computer, and might also be a noisy, probabilistic classical computer, we can solve 5-by-5 Sudoku puzzles!
Onlooker: Whoa, awesome! So we’re back to square one then. As long as D-Wave’s demos only involved 4-by-4 Sudokus, the skeptic’s arguments almost had me persuaded. But 5-by-5? I don’t know what to think anymore. Skeptic, where are you? What’s your reaction to this latest development?
Skeptic: …
D-Wave: That silence you hear is the sound of the skeptic’s worldview crashing all around him! But we haven’t even played our top card yet. Today, we’re positively ecstatic to announce that we’ve entered into an official-sounding partnership with GOOGLE, Inc. (or anyway, with someone who works at Google Research). Together, we’re harnessing the power of quantum adiabatic optimization to create the next generation of car-recognition systems!
Onlooker:WOW! This debate is over, then. I confess: D-Wave on its own did seem a bit flaky to me. But Google is the company born without sin. Everything they do, have done, and will ever do is perfect by definition—from building the search engine that changed the world, to running mail servers that only fail for an insignificant 0.001% of users, to keeping the Chinese people safe from lies. And, as Google is infallible, so too its 20,000 diverse employees—who are encouraged to spend 20% of their time on high-risk, exploratory projects—have nevertheless failed to come up with a single idea that didn’t pan out. Skeptic, show your face! Will you admit that, through grit, moxie, old-fashioned Canadian inventiveness, and the transformative power of the Internet, D-Wave has finally achieved what the naysayers said was impossible—namely, getting someone from Google Research to coauthor a paper with them?
Skeptic: Yes. I concede! D-Wave wins, and I hereby retire as skeptic. In particular, the next time D-Wave announces something, there’s no need to ask me for my reaction. I’ll be busy tending to my own project, codenamed ARGHH@home, which consists of banging my head against a brick wall.
I tried to be cynical—really I did. But despite my best efforts, somehow I went home more excited about quantum than I’ve been in a long time.
The highlight of the workshop was of course the closed, invitation-only, late-night meeting in the basement of NSF headquarters, at which a group of us hidebound quantum computing reactionaries plotted to keep the field focused on irrelevant mathematical abstractions, and to ostracize the paradigm-smashing entrepreneurial innovators who threaten our status. I don’t think I’ve ever heard so much cackling in the space of a single evening, or so much clinking of bone goblets. Stuff like that is why I entered the field in the first place.
1. In his talk on quantum algorithms with polynomial speedups, Andris Ambainis called attention to a spectacular recent paper by Ben Reichardt, which characterizes the quantum query complexity of any partial or total Boolean function f (up to a logarithmic factor) as the optimal witness size of a span program for f, and also as the negative-weight quantum adversary lower bound for f. Assuming this result is correct, it seems possible that the remaining open problems in quantum query complexity will be pulverized, one after another, by solving the associated SDPs for the optimal span programs. (Incidentally, using Reichardt’s result, it must be possible to prove, e.g., a Ω(n1/3/log(n)) lower bound for the quantum query complexity of the collision problem using the adversary method. This was a longstanding open problem. Can one say, explicitly, what the adversary matrices are in this case?) Alas, it also seems possible that span programs will turn out to be almost as hard to analyze as quantum algorithms were…
(1+√5)/2. Despite the obvious danger to the future funding of the entire field, by some clerical error I was released from my padded cell to speak about “Quantum Complexity and Fundamental Physics”. My “talk,” if it can be called that, was in my opinion neither rational nor integral to the workshop.
2. In her talk on blind quantum computation, Anne Broadbent (who’s also visiting MIT this week) described some beautiful new results that partly answer my Aaronson $25.00 Challenge from a year and a half ago. The Challenge, if you recall, was whether a quantum computer can always “prove its work” to a classical skeptic who doesn’t believe quantum mechanics—or more formally, whether every problem in BQP admits an interactive protocol where the prover in BQP and the verifier is in BPP. Anne, Joe Fitzsimons, and Elham Kashefi haven’t quite answered this question, but in a recent paper they’ve come close: they’ve shown that a quantum computer can prove its work to someone who’s almost completely classical, her only “quantum” power being to prepare individual polarized photons and send them over to the quantum computer. Furthermore, their protocol has the amazing property that the quantum computer learns nothing whatsoever about which particular quantum computation it’s performing! (Aharonov, Ben-Or, and Eban independently gave a protocol with the same amazing properties, except theirs requires the “classical” verifier to have a constant-sized quantum computer.) Anne et al. also show that two quantum computers, who share entanglement but can’t communicate with each other, can prove their work to a completely classical verifier (while, again, remaining completely oblivious to what they computed).
On top of everything else, these results appear to be the first complexity-theoretic application of the measurement-based quantum computing paradigm, as well as the first “inherently quantum” non-relativizing results. (Admittedly, we don’t yet have an oracle relative to which the blind quantum computing protocols don’t work—but the protocols rely essentially on the gate structure of the quantum circuits, and I conjecture that such an oracle exists.)
Rereading my Challenge, I noticed that “the [one-member] Committee may also choose to award smaller prizes for partial results.” And thus, yesterday I had the pleasure of awarding Anne a crumpled $10 bill, with an additional $5 contributed by Seth Lloyd, for a grand total of $15.00 to be shared equally among Anne, Joe, and Elham. (Update: Since I wrote that, Anne has elected to trade in for three signed and doodled-upon $5 bills.) (Another Update: A $12, or $15-$O(1), prize shall be awarded to Dorit Aharonov, Michael Ben-Or, and Elad Eban the next time I see them.) This is, I believe, the first time a monetary reward offered on Shtetl-Optimized has actually been paid out.
3. In a talk that was so good, you almost forgot it involved chemistry, Alán Aspuru-Guzik discussed applications of quantum complexity theory to understanding photosynthesis and the design of efficient solar cells (!). To give you a sense of how mindblowing that is, it briefly made me wonder whether I should reread some of John Sidles’ cheerful ramblings about the coming merger of quantum systems engineering with biology in the 21st century (of which, I predict, this very sentence will inspire dozens more).
So what then is the connection between quantum complexity theory and photosynthesis? Well, a few of you might remember my post “Low-Hanging Fruit from Two Conjoined Trees” from years ago, which discussed the lovely result of Childs et al. that a quantum walk on two conjoined binary trees can reach a designated end vertex exponentially faster than a classical walk on the same graph. That result interested me, among other things, because it can be shown to lead to an oracle relative to which BQP ⊄ SZK, which at the time I didn’t know how to find otherwise. But especially given the bizarre nature of the graph needed to produce the oracle separation, I thought of this result as pretty much the prototype of an irrelevant complexity-theoretic curiosity (which, naturally, made me like it all the more).
You can probably guess where this is going.
Shown above is a light-harvesting molecule (image snagged from Alán’s slides), which apparently is efficient at concentrating light at its center for essentially the same reason the Childs et al. quantum walk reaches the target vertex exponentially faster than a classical walk: namely, because of destructive interference between the paths that point backward, toward the leaves. According to Alán, what plants do to harvest sunlight is not entirely unrelated either (it also involves quantum coherence), and fully understanding these mechanisms in quantum information terms might conceivably be useful in designing better solar cells. To be fair, a part of me always did suspect that quantum oracle separations would turn out to be the key to solving the world energy crisis. I’ll point you here or here if you want to know more.
Incidentally, Alán’s talk had another, also extremely interesting part, which was about coming up with precise numerical estimates of the number of qubits you’d need to simulate the wavefunctions of (say) benzene, caffeine, and cholesterol. (Many of us have long thought that simulating physics and chemistry will be the real application for scalable quantum computers if we ever build them, practical long before breaking RSA and ultimately more useful too. But it’s not something we often talk about—ostensibly for lack of meaty things to say, really because we don’t know chemistry.)
4. In her talk, Dorit Aharonov posed an open problem that I now have no choice but to inflict on others, if I don’t want to feel forced to think about it myself. So here’s her problem: how hard is it to find the ground state of a local Hamiltonian H=H1+…+Hm (that is, a sum of k-qubit interactions, for some constant k), if we impose the constraint that the Hi’s all commute with each other? Clearly it’s somewhere between NP and QMA. It might seem obvious that this problem should be in NP—to which I can only respond, prove it!
There were also lots of great talks by the experimentalists. Having attended them, I can report with confidence that (1) they’re still trying to build a quantum computer but (2) decoherence is still a big problem. If you want to know even more detail than I’ve just provided—or you want to know about the theory talks I didn’t mention, or more about the ones I did mention—ask away in the comments. I can’t promise that no one will know the answer.
