This is a personal, idiosyncratic list, written at the suggestion of Boaz Barak in connection with the Theory Matters wiki. I tried to satisfy two almost-contradictory objectives: (1) that some progress should almost certainly be possible in 5-6 years, but (2) that progress seems likely to require new ideas, not just the tweaking of old ones. Most of the problems are just tips of various icebergs, but it's harder to explain the icebergs themselves in plain English.

Three notes: first, to keep things informal, I didn't give references. Use Google. Second, while many of the challenges are vague and open-ended, I didn't include any that are completely inexhaustible, like "How can quantum computing contribute to classical computer science?" In my view, a scientific challenge ought to include some goals that might, in principle, be reached -- otherwise it's less of a challenge than just an area of research. Third, you might object that some of the challenges are not "grand" enough to deserve the title of grand (or even semi-grand) challenges. If so, pick the one you think is least grand, and solve it!

1. What is the threshold for universal quantum computing? I mean this in both a narrow and a broad sense. The narrow sense: what is the maximum probability of decoherence per qubit per time step under which universal quantum computing is still possible? This is arguably the central question facing quantum computer builders, and it's entirely theoretical in nature. The best lower bounds we had until recently were 10^-6 to 10^-4, depending on what decoherence model is assumed (new heuristic arguments suggest 1%-5% is achievable). The best upper bound is 50%.
   The broad sense: which physical systems (quantum cellular automata, anyons, etc.) exhibit quantum universality? Also, is it true that every class of quantum gates is either universal for BQP, or else simulable in classical polynomial time? If so, what criterion separates the two? If not, do we get an interesting hierarchy of complexity classes between BPP and BQP?
   
   
2. The flip side: what quantum systems can be simulated in classical polynomial time? Though we don't always appreciate it, this is a question of direct and immediate interest to condensed-matter physicists (or so they tell me!). We know basically three examples with nontrivial classical simulations: stabilizer circuits, fermionic systems with noninteracting modes, and quantum computers with bounded Schmidt rank (a measure of entanglement). Are there common generalizations of these three examples? Also, can we efficiently simulate a quantum computer that's (say) always in a separable mixed state, or always in a state representable by a small number of linear combinations and tensor products?
   
   
3. BQP versus classical complexity classes. After twelve years of effort, not only do we still not know whether BQP sits in the classical polynomial hierarchy, there's really no evidence either way. There's an oracle relative to which BQP is not in MA, but we still have no oracle relative to which BQP is not in AM. At least in the unrelativized world, I consider it entirely possible that BQP is contained in AM intersect coAM (and thus in NP intersect coNP under a derandomization assumption). This would mean that whenever a quantum computer yields a particular outcome, there's a short classical proof that it does so.
   
   
4. The power of quantum messages, quantum proofs, and quantum advice. For almost a century, physicists and philosophers have debated whether the components of a quantum state are "really there" (some would say inhabiting parallel universes), or are "mere potentialities" until the act of measurement makes one of them real. Today we're starting to make this vague question precise, by asking in what sense a quantum state is "more useful" than a corresponding sample from a classical probability distribution. We can address this question by studying two complexity classes: QMA (Quantum Merlin-Arthur), which is like NP except that the verification algorithm is quantum and the yes-witnesses are quantum states; and BQP/qpoly, or BQP with a polynomial-size quantum advice state that depends only on the input length. Then the obvious question is: can we always replace the quantum yes-witnesses by classical yes-witnesses, and the quantum advice by classical advice? Again, we don't even have oracle evidence either way.
   Closely related are the central open questions of quantum communication complexity: is there a total Boolean function whose quantum communication complexity is superpolynomially smaller than its randomized communication complexity? In the case of one-way communication complexity of Boolean functions, it's not even known if there's any asymptotic gap between quantum and classical (though if a gap existed, it could be as large as exponential).
   
   
5. Beyond Shor and Grover. For many people, this phrase will suggest something specific: trying to find quantum algorithms for graph isomorphism, approximate shortest vector, and the nonabelian hidden subgroup problem. But there are other ways to approach the question of whether "fundamentally new" quantum algorithms remain to be discovered. For example, is there a quantum query algorithm that evaluates a total Boolean function, and that gets more than the quadratic speedup of Grover's algorithm as compared to the best classical algorithm? Also, is there a quantum query algorithm for a partial function invariant under permutation symmetry (as are the collision and element distinctness functions), which is superpolynomially faster than the best randomized algorithm? One last example: is there a polynomial-time quantum query algorithm which is not only hard to simulate classically (as Shor's and Simon's algorithms are), but which doesn't even have a polynomial-time classical simulation that works for most oracle strings in {0,1}^{2^n}? This is closely related to the longstanding open question of whether BPP=BQP relative to a random oracle with probability 1.
   
   
6. Beyond BQP. Are there plausible physical theories that yield more power than standard quantum computation? For example, what about (3+1)-dimensional quantum field theories? (What's known is that (2+1)-dimensional "topological quantum field theories" yield no more power than ordinary quantum computers.) Also, what about various formulations of (say) string theory or loop quantum gravity?
   
   
7. Quantum obfuscation. Can I give you a quantum state, such that with the help of that state you can evaluate some Boolean function f, but such that you can't learn anything more about f than you could if I gave you a "black box" for f? (I.e. if you try to "peek inside the box" by measuring the state, you'll just collapse it and not get any useful information.) Classically, it's known that such "program obfuscation" is impossible in general, but the proof breaks down in the quantum case because of the impossibility of cloning an unknown quantum state. A related question is whether one can use quantum states to create tamper-proof software copy-protection. Even if these tasks are impossible in general, they might be possible for large and nontrivial classes of functions.
   
   
8. PKC secure against quantum. Currently, there's really only one class of public-key cryptosystems that's not known to be breakable with a quantum computer: the class where you encode the plaintext using a lattice or a linear code, and then add some random noise (this class includes the McEliece, Ajtai-Dwork, and Regev cryptosystems). Can we find other such systems, ideally practical ones? (Also, it's worth mentioning that, if we could solve the general nonabelian hidden subgroup problem, then we could break many of the public-key cryptosystems based on lattices and linear codes.)
   
   
9. The power of small-depth quantum circuits. Is BQP = BPP^BQNC? In other words, can the "quantum" part of any quantum algorithm be compressed to polylog(n) depth, provided we're willing to do polynomial-time classical postprocessing? (This is known to be true for Shor's algorithm.) If so, building a general-purpose quantum computer would be much easier than is generally believed! Incidentally, it's not hard to give an oracle separation between BQP and BPP^BQNC, but the question is whether there's any concrete function "instantiating" such an oracle.
   
   
10. Quantum learning. Can the concept class of AC⁰ circuits be PAC-learned in quantum polynomial time? (The best known classical algorithm takes n^{log n} time.) More audaciously, can the concept class of TC⁰ circuits be PAC-learned in quantum polynomial time? If so, then quantum computers would have an enormous advantage over classical computers in learning close-to-optimal weights for neural networks. In my view, there are two facts that make this a serious possibility: first, that the best classical learning algorithms so often work by learning the Fourier spectrum of the function of interest. And second, that the only evidence that learning TC⁰ circuits is hard classically comes from the presumed intractability of the factoring and discrete log problems.

[Return to Writings page]