Research projects in quantum complexity theory
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(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?
Follow
Comment #1 October 27th, 2010 at 3:17 pm
Howdy Scott. Hate to tell you this but a helicopter tour of the grand canyon does not count as having visited that seminal american landmark. You need to drive there, ala Thelma and Louise, if you want that honor. But on the bright side, you probably won enough playing black jack to afford to take a road trip out West over winter break, right?
Comment #2 October 27th, 2010 at 3:43 pm
Scott, would you like to post them as an answer to: http://cstheory.stackexchange.com/questions/710/quantum-computing-project-ideas
Comment #3 October 27th, 2010 at 4:44 pm
Shardik: Well, I didn’t claim to have “visited” the Grand Canyon! I’ll go there for real when I have a spare week (maybe after I retire?).
Comment #4 October 27th, 2010 at 4:44 pm
anon: Thanks for the suggestion! I posted a link to this blog post on stackexchange.
Comment #5 October 28th, 2010 at 2:20 pm
Hi Scott,
I’m a computer engineering student currently working on a thesis that will get me my master’s degree. I came across your blog by chance. You seem to be just the right person to ask for an opinion on my thesis subject.
My thesis is about quantum algorithms. The original plan was to include either two or three parts, a bibliographical part (overview of a few important algorithms, like Shor’s factoring algorithm and Grover’s searching algorithm), a part concerning simulations of these algorithms on a classical computer (I haven’t started this one yet) and possibly a part where I tackle on a theoretical problem. However, the title is purposely left vague (“Quantum Algorithms”), so that if things go south, I can just leave in the bibliographical part (though I don’t want to do that; I’m aiming for a high grade).
My supervisor would be content even with a purely bibliographical project, but the other two examiners would strongly prefer an original aspect. I’ve asked my supervisor for advice, but I’d like a second opinion. Keeping in mind that I’m almost done with the bibliographical part and that I have to turn it in in February, is it possible for me to pull off the third part in this time? And if so, which problem might be the right difficulty for me (not too easy, not too hard)?
(On a relevant note, I’m ashamed to admit that I’m having trouble understanding the recursive Fourier sampling problem. I’ve read the paper by Bernstein and Vazirani, and I’ve started reading your paper “Quantum Lower Bound for Recursive Fourier Sampling”, but I’m afraid I’m going to need a dumbed-down version >.> Google hasn’t been much help. Any suggestions? If it’s not too much trouble, that is.)
Any input, however small, will be greatly appreciated. Thanks 🙂
Comment #6 October 28th, 2010 at 6:23 pm
TentacledBeast,
Perhaps good questions to start with are
1) what are you interested in (in quantum computation, in computer engineering, in life in general)?
2) what are you good at?
3) what/where do you want to be? (you’re about to graduate with an MS, what you do now will influence where you go next and a relevant master thesis can really help you)
Comment #7 October 29th, 2010 at 8:15 am
To tell you the truth, I think I’ve made a mistake going for computer engineering. Instead of choosing what I liked most (that would be Physics), I went for what I was better at, and the one that had more chances of getting me a good job.
I took one course of quantum mechanics, which I aced, and wanted more. But the only relevant thing I could do in my department would have to do with quantum computers. The hardware aspect is out of my reach (I’ll probably never even see the kind of equipment needed), so I went for the algorithmic aspect.
So far, I really like the subject. The algorithms I’ve seen are creative and elegant and make me wish I could invent something similar. But that’s unlikely. Writing a simulator is certainly feasible, but not all that interesting.
As for where I want to be, I don’t know. I guess I’m not mature enough yet to decide. I know that quantum mechanics caught my interest, and that I like the aspect of quantum computing that I’ve seen, but I don’t know where I want to go from this point.
Comment #8 October 29th, 2010 at 3:03 pm
Dear TentacledBeast,
“The hardware aspect is out of my reach”. Well, not entirely. While experimental quantum computation does require oodles of equipment, you can still do plenty of pen/paper/personal computer projects related to it. For example, you could run simulations about some physical system/device upon which quantum computers could be built.
“As for where I want to be, I don’t know. I guess I’m not mature enough yet to decide.” Not to sound like a tool, but you probably should think about this a little more. Fair warning (from personal experience): it’s hard to find a “regular” job in quantum computation. It’s a good idea to pursue your interest in quantum computation, but it’s also important to have a back up plan (especially if you’re not in a PhD program; the few places that do have full time quantum computation jobs are usually looking for professors or research scientists).
Comment #9 October 29th, 2010 at 6:18 pm
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?
I’m actually pretty surprised to learn that this is open — I thought it was proven a while back (by Kitaev, maybe?) Isn’t there some universality result somewhat like this? Or what is it that I’m thinking of?
That said, now that I know it’s (apparently) open, I’m surprised you consider it easy enough for a grad student to make progress on in 1-2 months (and, presumably, have at least a small chance of solving — and maybe a larger chance given a couple of years.) It just sounds like such a basic problem that, if it really were approachable, someone would have solved it already. Is there any particularly promising approach that you think will lead to someone cracking this within the next few years? Or is it just one of those simply-stated-but-overlooked problems that crops up from time to time?
Comment #10 October 29th, 2010 at 6:23 pm
TentacledBeast:
Here are a couple of relevant facts:
1. Most people in STEM wind up changing the field that they work in several times. Often none of your jobs are in exactly what you studied.
2. Professor jobs are rare, getting rarer, and getting less fun as management increasingly encrusts universities.
3. Many of the interesting/cool/well paying jobs in ten years haven’t been imagined yet.
General advice:
1. If you get a wide background in math, physics, and CS, you will be prepared to surf whatever the next wave turns out to be, not be a casualty. If you can’t decide what to do, get a MS in a related field at another university.
2. A lot of people in TCS don’t appear to stoop to any actual programming. Bad idea. Take a course in software development. You are much more likely to get paid for this. Learn a couple languages and play around with several others.
Comment #11 October 30th, 2010 at 2:41 pm
Scott asks: 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?
Scott’s question naturally generalizes from discrete dynamics to continuum dynamics: (unitary maps ⊕ projections) → (Hamiltonian ⊕ Lindbladian flows). In particular, Carlton Caves has an on-line memo titled “Completely positive maps, positive maps, and the Lindblad form” that describes this map.
In Caves’ language, we can express Scott’s question in an explicitly geometric form: Is it true that if a Hamiltonian/ Lindbladian flow is simulable in classical polynomial time, that quantum trajectories are dynamically compressed onto a Kählerian manifold of polynomially dimensions?
This approach can be understood as the analog in QIT of Ketan Mulmuley’s “GCT Flip” in the following broad sense: where the GCT Flip requires the construction of a concrete geometric obstruction that separates P from NP ; the QIT Flip requires the construction of a concrete geometric compression that separates dynamical flows in P from dynamical flows in BQP.
Here as with Mulmuley’s GCT program, it’s often a good idea for students to study alternative mathematical approaches to long-standing problems in complexity theory. As Lance Fortnow memorably said on his weblog last week: “Complexity theorists need to give up ownership of the P v NP problem.”
Hmmm .. perhaps this is similarly true of P v BQP?
Comment #12 October 31st, 2010 at 3:54 pm
Amusing video: “So you want to get a PhD in theoretical computer science?” http://www.xtranormal.com/watch/7520547/
Comment #13 October 31st, 2010 at 11:55 pm
Tom,
Excellent pointer. I hope wannabe TCS students get to see it. Note my comment above about taking some software dev and engineering classes. Then when you don’t get a university job, you can have a consolation prize of making more money than the TSC people do. Making things that work is actually pretty rewarding.
Comment #14 November 1st, 2010 at 8:03 am
Thanks for the advice, everyone 🙂
Comment #15 November 1st, 2010 at 8:22 am
Tom, that same “amusing video” was posted on the Fortnow/GASARCH Shtetl Optimized weblog.
The video’s sentiments have become widespread among STEM students in every discipline … for the obvious reason that these sentiments are amply justified by modern STEM realities.
And yet, that video should not be allowed to stand as the last word on these tough STEM issues … it is preferable to view the video as an invitation to start thinking, not stop thinking.
Last week’s reading list of our TCS/QSE Litotica seminar challenged students to go beyond that video’s (shallow) reading of the challenges that the STEM community is facing … that reading list included the essays (by Thomas Benton) from which that video was derived.
Comment #16 November 1st, 2010 at 9:17 pm
John, in comment #11, I don’t understand how the “compression that separates” would work. In GCT, an obstruction is an object whose existence proves that the inclusion of one complexity class in another is impossible, because it exists for the first class, should be preserved by an inclusion mapping, but provably can’t exist for the second class. Do you envisage the “QIT Flip” working in a similar way, or through some other method?
Comment #17 November 3rd, 2010 at 5:57 am
Mitchell asks: Do you envisage the “QIT flip” working in a similar way [to Ketan Mulmuley’s GCT flip], or through some other method?
Michael, we’ll be discussing the QIT flip at this morning’s UW/QSE Litotica seminar. For this seminar, I prepared some brief notes, provisionally titled “Comment 17” (my name above is a link to these notes) that perhaps will appear eventually as a Shtetl Optimized comment.
Very often, our Litotica seminars include links to the fine weblogs of Scott, Dick, Ken, Lance, Dave, Terry, Gil, Tim … the “first-name mafia” of TCS/STEM weblogging. It’s worth stating explicitly what everyone acknowledges: these weblogs are an outstanding asset to our community.
Comment #18 November 3rd, 2010 at 10:04 am
John, at your link you write
“without Lindbladian dynamics, we have BQP computation, which few believe is feasibly simulable (with classical resources)” [my emphasis]
But the whole point of separating P and BQP is to prove, not just to believe, that this is so. It sounds like what you want to do is to show that something which ought to be in P (einselected quantum dynamics) actually is in P, by exhibiting concrete polynomial-time algorithms that simulate it. Great, but to separate P from BQP, you need to prove that no such algorithms exist, for some other sort of quantum dynamics. The GCT flip is all about proving the nonexistence of something, by proving the existence of something else – the obstruction.
For example, maybe you could show that “BQP-complete quantum dynamics” can’t arise from a polynomially complex perturbation or deformation of einselected quantum dynamics. That would still be just a statement of the desired nonexistence result – we still haven’t “flipped” it into an existence problem. If we were really employing Mulmuley’s method here, we’d pick a special instance of “P-complete dynamics” and a special instance of “BQP-complete dynamics”, and then we’d show that some special property exists that differentiates the two, and which polynomially complex perturbation can’t transmute in the required way. That property would be the obstruction.
Comment #19 November 3rd, 2010 at 10:51 am
Michael, posts: But the whole point of separating P and BQP is to prove, not just to believe, that [a separation exists]
Michael, I greatly enjoyed your post, and everything *after* the initial statement is very well-expressed indeed (IMHO). In particular, the challenge of writing concrete simulation codes in P turns out to be a pretty good way to highlight the obstructions you discuss, since in writing each code, we are led to ask the natural question: “What fundamentally obstructs this particular algorithm from simulating systems in BQP ? Is the obstruction most naturally described as informatic, algebraic, or geometric, or as a blend of all three? Can we prove that this obstruction exists for all problems in BQP ?”
And yet, with respect to your initial statement itself, surely there is room for multiple perspectives regarding the “the whole point” of these investigations. Because by the very nature of complexity-theoretic problems relating to separations from P, as we come to understand the various separations better, the set of problems known to be in P and/or empirically found to be in P expands irreversibly and inexorably.
From a mathematician’s point of view, the steady expansion of the set of problems known to be in P serves to highlight the problem of proving separation theorems more-and-more clearly … which is a good outcome.
Yet from a “flipped” engineering point of view—especially in quantum systems engineering—the expansion of P is itself the chief utilitarian good, such that “the whole point” of studying separation problems is to accelerate that expansion … which also is a good outcome.
Now, is TCS more closely allied with mathematics, or with engineering? It seems to me that a good outcome for TCS is that opinions on this question remain diverse.
As Lance Fortnow posted last week “Complexity theorists need to give up ownership of the P v NP problem.” But it would have been even better (IMHO) had Lance posted instead “Complexity theorists need to share ownership of the P v NP problem.”
Comment #20 November 3rd, 2010 at 12:23 pm
LOL … Michael, as a follow-one to the above post, I just finished mining my BibTeX file for quotes relating to proofs and doubts … the selected quotes characterize an attitude toward proofs that is widespread among engineers and scientists, yet is very different from the typical attitudes of mathematicians; these considerations apply especially (IMHO) to problems in quantum complexity theory.
I’ll use these quotes to start-off today’s Litotica seminar, whose broad theme is the role that quantum systems engineering plays in providing the requisite confidence to initiate large-scale enterprises. Here they are:
——————————
“The virtue of a logical proof is not that it compels belief but that it suggests doubts. The proof tells us where to concentrate our doubts.” (Henry George Forder)
——————————
“One thing is to prove it by equations; the other is to check it by calculations. I have mathematically proven to myself so many things that aren’t true. I’m lousy at proving things—I always make a mistake. […] So I always have to check with calculations; and I’m very poor at calculations—I always get the wrong answer. So it’s a lot of work […] If you do a real physical problem with real physical things in them, then I’m sure we have the right method.” (Richard Feynman)
——————————
“It is one of the chief merits of proofs that they instill a certain skepticism about the result proved.” (Bertrand Russell)
——————————
Comment #21 November 4th, 2010 at 2:59 am
though I guess you have already seen it:
http://www.telegraph.co.uk/science/7904712/Quantum-time-machine-allows-paradox-free-time-travel.html
Comment #22 November 7th, 2010 at 5:19 pm
Scott,
On a quite different topic (although it is also an interesting research project), there was a question raised today on MathOverflow concerning a possible generalization of the PCP theorem to the quantum case:
http://mathoverflow.net/questions/45106/quantum-pcp-theorem
In his answer, Peter Shor argues that he would be very surprised if such a generalization was possible.
At the same time, four years ago, you (Scott) said here:
“I’m 99% sure that this theorem (alright, conjecture) or something close to it is true. I’m 95% sure that the proof will require a difficult adaptation of classical PCP machinery (whether Iritean or pre-Iritean), in much the same way that the Quantum Fault-Tolerance Theorem required a difficult adaptation of classical fault-tolerance machinery. I’m 85% sure that the proof is achievable in a year or so, should enough people make it a priority.”
https://scottaaronson-production.mystagingwebsite.com/?p=139
My question, prompted by Peter’s comment, is this: do you still believe that a quantum PCP theorem exists?
Thanks!
Comment #23 November 8th, 2010 at 11:16 am
Anthony: Yes, I still think a quantum PCP theorem should be true. Proving it has turned out to be an extremely hard problem; a significant number of quantum complexity theorists (not including I) have been working hard on it the past few years.
Comment #24 November 8th, 2010 at 11:31 am
OK, thanks!