Research projects in quantum complexity theory
Wednesday, October 27th, 2010Today 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(x1,…,xn) 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 x1,…,xn.)
Can every quantum algorithm that makes k queries to an n-bit string, be simulated by a randomized algorithm that makes n1-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 |ψ>2] 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 uij≠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 n3/4?