- Given an n-qubit pure state, is there always a way to apply Hadamard gates to some subset of the qubits, so as to make all 2n computational basis states have nonzero amplitudes?
- Can we get any upper bound on QMIP (quantum multi-prover interactive proofs with unlimited prior entanglement)? It would suffice to show (for example) that the provers never need more than Ackermann(n) ebits of entanglement.
- Can any QMA(2) (QMA with two unentangled yes-provers) protocol be amplified to exponentially small error probability? If you think the answer is trivially yes, think about it some more!
- If a unitary operation U can be applied in polynomial time, then can some square root of U also be applied in polynomial time?
- Suppose Alice and Bob are playing n parallel CHSH games, with no communication or entanglement. Is the probability that they’ll win all n games at most pn, for some p bounded below 0.853?
- Forget about an oracle relative to which BQP is not in PH. Forget about an oracle relative to which BQP is not in AM. Is there an oracle relative to which BQP is not in SZK?
- Given any n-qubit unitary operation U, does there exist an oracle relative to which U can be (approximately) applied in polynomial time?
- How many mutually unbiased bases are there in non-prime-power dimensions? (Alright, I don’t care about this one, but so many people do that I figured I’d put it in.)
- Is there an n-qubit pure state that can be prepared by a circuit of size n3, and that can’t be distinguished from the maximally mixed state by any circuit of size n2?
- Fill this space with your own annoying question! Here are the rules: the question must involve quantum. It must be annoying. It must be clearly-stated — no open-ended pontificating allowed. It can’t be an Everest of the field, like graph isomorphism or increasing the fault-tolerance threshold. Instead it should be a dinky little molehill, that’s nevertheless caused all would-be climbers to fall flat on their asses.
This entry was posted
on Tuesday, August 15th, 2006 at 7:38 pm and is filed under Complexity, Quantum.
You can follow any responses to this entry through the RSS 2.0 feed.
Both comments and pings are currently closed.
Follow
Comment #1 August 15th, 2006 at 7:51 pm
Greg: Happy?
Comment #2 August 15th, 2006 at 8:21 pm
Do SIC-POVMs exist in every dimension?
Comment #3 August 15th, 2006 at 8:42 pm
That’s a good one — thanks!
Comment #4 August 15th, 2006 at 9:04 pm
Suppose Alice and Bob are playing n parallel CHSH games, with no communication or entanglement. Is the probability that they’ll win all n games at most pn, for some p bounded below 0.853?
Let me know if I’m missing something, but…
I assume that Alice and Bob are allowed shared random data, that a referee supplies inputs, and that a strategy is evaluated by the probability of success on the worst case input pair. Success means winning all n games. I’m also assuming it should be p^n.
First, let’s make things easier for Alice and Bob. Let’s use an average over all inputs instead of the worst case. Any bound obtained will also apply to the worst case problem. Now note that any probabilistic strategy corresponds to using deterministic strategy D1 with probability p1, D2 with probability p2 and so on. At least one of the Di has probability of success at least as great as the probabilistic strategy. So restrict attention to deterministic strategies. But now it’s fairly trivial as there is no longer an issue of correlating strategies over the different games. The best deterministic strategy will have probability of success (3/4)^n.
Still, I should think that Bell inequalities, nonlocality and communication complexity in general are pretty fertile grounds for annoying questions. How about this: can any bipartite PPT state violate a Bell inequality?
JB
Comment #5 August 15th, 2006 at 9:14 pm
I’m also assuming it should be p^n.
I used an HTML superscript tag; I guess it didn’t display on your browser.
But now it’s fairly trivial as there is no longer an issue of correlating strategies over the different games. The best deterministic strategy will have probability of success (3/4)^n.
Nope! Not only is this not as obvious as you think (and as I thought), it’s actually false! Even with a deterministic strategy, Alice and Bob can correlate across different games. To see this, consider the case n=2.
If Alice receives the bit sequence 00, 01, or 10, she’ll output 00. If she receives 11, she’ll output 10.
If Bob receives the bit sequence 00, 01, or 10, he’ll output 00. If he receives 11, he’ll output 01.
You can check that this strategy causes Alice and Bob to win both games with probability 10/16 > (3/4)^2.
Comment #6 August 15th, 2006 at 9:58 pm
No pontificating? What’s the point 🙂
Comment #7 August 15th, 2006 at 10:03 pm
WARNING: This is an explicit advertisement!
Question: Is it NP-hard to compute the quantum chromatic number of a graph?
http://xxx.soton.ac.uk/abs/quant-ph/0608016
Yes, this cannot really be classified as an annoying question. In particular, most of you will say “what the heck is this thing?”. I try to justify my post with two points:
1) This blog is about computational complexity and my question is about computational complexity. Good.
2) If you want to sell something then you need to show it around.
Simone
Comment #8 August 15th, 2006 at 10:29 pm
Simone: No need to apologize — that’s a fine question.
Dave: Weren’t you a literature major? Show, don’t tell.
Comment #9 August 15th, 2006 at 11:04 pm
Can we get any respectable upper bound on QIP(2)? Like at least PSPACE for godsakes?!
Gus
Comment #10 August 15th, 2006 at 11:35 pm
“But now it’s fairly trivial as there is no longer an issue of correlating strategies over the different games. The best deterministic strategy will have probability of success (3/4)^n.
Nope!”
Ooops, thanks. Guess that counts as falling flat on my ass.
Comment #11 August 15th, 2006 at 11:36 pm
If somebody comes with the CHSH problem do post on the blog.
Comment #12 August 16th, 2006 at 12:10 am
Greg: Happy?
Yes, for many reasons! For one, your questions 9 and 5 seem zoology-inspired.
Here is one that irritates me: Is QMIP_le contained in QMIP_ne? If QMIP_le were restricted to EPR pairs, it would trivially be so, because Arthur could provide the entanglement to the Merlins. But it is instead defined as arbitrary polynomial entanglement.
Another one (which may not qualify because it could be hard): Suppose that you encode an irreducible representation of SU(2) so that the weight vectors are computational states. (In other words, SU(2) acts on polynomials in x and y of degree N, and we encode so that the monomials are proportional to basis states for the qubits.) Then is there a good quantum algorithm or circuit to implement the action of non-diagonal elements of SU(2)?
Comment #13 August 16th, 2006 at 4:35 am
Great list Scott!
Comment #14 August 16th, 2006 at 6:49 am
Today I’ve learnt that I spend a lot of time thinking about “annoying” questions.
In question 6, do you want p to be bounded below 1 instead of 0.853?
Comment #15 August 16th, 2006 at 10:18 am
Ben: Nope! It’s easy if you just want it bounded below 1. (Indeed, a result of David Peleg gets you down to 0.86, while the Feige-Lovasz approximation gets you down to 0.853 itself.)
PS. “Annoying” questions are the only ones I ever work on.
Comment #16 August 16th, 2006 at 11:23 am
Thanks Scott, I missed the “no entanglement” part of the question.
Comment #17 August 16th, 2006 at 12:41 pm
“What is the quantum complexity of ordered searching?”
I find this one particularly embarassing for the field.
Comment #18 August 16th, 2006 at 12:46 pm
It would be very useful to simply have an on-line problem list in quantum algorithms.
Comment #19 August 16th, 2006 at 10:31 pm
The infrastructure for a quantum computation online problem list is out there – just colonise the quantum information theory problem list at
http://www.imaph.tu-bs.de/qi/problems/
I’m sure the custodians won’t mind sharing space with their computer science cousins.
PH
Comment #20 August 17th, 2006 at 12:21 am
Another one (which may not qualify because it could be hard): Suppose that you encode an irreducible representation of SU(2) so that the weight vectors are computational states.
[snip]
Then is there a good quantum algorithm or circuit to implement the action of non-diagonal elements of SU(2)?
this depends on what you mean: if approximations are allowed, the problem is solved by Zalka’s (admittedly sketchy) quant-ph/0407140, “Implementing high dimensional unitary representations of SU(2) on a Quantum Computer”.
Exact implementations indeed seem more difficult.
Comment #21 August 17th, 2006 at 1:31 am
Approximations are fine; QC without approximations is artificial. However, Zalka’s interesting paper does not completely solve the problem as far as I know.
(I ranted about EQP in a previous post, because it is a classic example of an artificial complexity class. However I later decided that EQP should be placed among other complexity classes which are interesting even though they are artificial. Two other examples are LWPP and HalfP, which bound EQP from above and below.)
Comment #22 August 17th, 2006 at 10:40 am
Scott sez: “The question must involve quantum. It must be annoying. It must be clearly-stated.”
Oh boy … clearly-stated, annoying questions!
Q1: In what years (if ever) will posts to the arxiv server surpass: (a) 10^3 articles/day, (b) 10^4 articles/day, (c) 10^5 articles/day?
Q2: In what year will global employment for quantum engineers first surpass employment for quantum physicists? What will be the employment figures in that year?
It might be objected, that these questions are annoying in the “wrong” way: they concern a system of exponential complexity, such that no algorithmically efficient (“simple”) answer can be reasonably expected.
Which (of course) leads to a final annoying yet well-posed question: are the previous questions on this thread any different?
Comment #23 August 17th, 2006 at 1:45 pm
This is an interesting seed for a problem list in quantum algorithms — it may in the end be more helpful to come up with “annoying” problems than with “Everests”.
If I may borrow this space for a different but related purpose: It would be extremely helpful for the complexity zoology project to come up with extreme statements of the form “we can’t even find an oracle such that A is not in B”. A and B would ideally be so extreme that it is preposterous that A is in B for all oracles; yet no one can find a counterexample. Scott has already mentioned one example on this list, A = BQP and B = SZK. It can indeed be upped a bit to A = DQP and B = PZK, although that may be an artificial variation of the more interesting question.
Lame, artificial, tacky variations are just fine with me. In fact, I would prefer them, provided that the problem really is open and the classes are listed in the Zoo. If you can identify examples anywhere in the zoology diagram that are not already marked as open, I would really like to hear about it. Indeed I would like to ask Scott to announce this as another “contest” in this useful blog.
The fruit of it would be that the robozoologist would automatically mark many other harder oracle separation problems (or easier relativizing inclusion problems) as also open.
(Granted, it’s your blog, Scott, and you can post whatever you want, but if you agree with me that it is a useful contest…)
Comment #24 August 17th, 2006 at 2:22 pm
Alright Greg. I hereby announce such a contest, to take place in this comments section alongside the annoying quantum questions.
Comment #25 August 17th, 2006 at 4:16 pm
How come you guys have not talked about the Time’s article on Stringy yet?
Comment #26 August 17th, 2006 at 5:51 pm
Because I trust Peter and Lubos to duke this one out.
Comment #27 August 17th, 2006 at 5:56 pm
Patrick: Hey, that’s a fantastic page — thanks for the link!
Only one problem: I don’t have time to write up long “dossiers” and reference lists for each of my problems (and for some of them, there’s really nothing to write…).
Comment #28 August 17th, 2006 at 10:22 pm
Ok this one is annoying me:
Consider (hard core) bosons hopping around the vertices of a graph G (via a standard exchange hamiltonian). The Hamiltonian when restricted to a single particle hopping is exactly the adjacency matrix of the graph. The annoying question is this: When you have two particles hopping on either a graph G or a graph G’ and the energy spectra are the same for both graphs, are the single particle spectra also the same? (i.e. are the graphs cospectral, in a graph theorists language?) Numerics and physical intuition strongly suggest so.
More difficult: Despite searching millions of likely candidate pairs of graphs, no pair of (non-isomorphic) graphs with the same spectra for 3 particles have been found. However if none such existed there would be a cubic time (classical) algorithm for graph isomorphism! I’d really like to find such a pair so I could see what is special about them.
These Hubbard model spectra are “quantum computable” graph invariants to one extent or another, so it would be nice to know something about them. What little we do know is here:
http://www.arxiv.org/abs/math.CO/0507251
Comment #29 August 17th, 2006 at 11:35 pm
Tez: I don’t know what you mean by the “energy spectrum” as distinct from the “single particle spectrum” of a graph.
Your question about 3 particles brings to mind an impressive result of Cai, Fürer, and Immerman (see here). It says that the graph identification strategy of coloring tuples of vertices based on their valence may require linear-sized tuples of vertices to get started. I am not sure, but this could imply in your case that you need a linear number of particles, not just 3. (At least, that was my intuition when I thought about these matters last year.)
Comment #30 August 18th, 2006 at 1:21 am
Greg,
Tez means the spectrum of the Hamiltonian he described, which is the random walk on a different graph, the symmetric power of the original graph (where you only allow one particle/coordinate to change at a time).
Comment #31 August 18th, 2006 at 3:05 am
I see. Then my question remains whether the Cai-Fürer-Immerman graphs are a counterexample to this speculation in math.CO/0507251: “If it were true for some fixed k that any two graphs X and Y are isomorphic if and only if their k-th symmetric powers are cospectral, then we would have a polynomial-time algorithm for solving the graph isomorphism problem.”
Comment #32 August 18th, 2006 at 7:03 pm
Please Greg, would you advice me a good reference for Cai-Fürer-Immerman graphs? These may well be counterexamples to my speculations (somehow similar to Terry’s method). Thanks a lot!
Comment #33 August 18th, 2006 at 7:05 pm
Sorry, I did forget to include a link
http://arxiv.org/abs/quant-ph/0505026
Comment #34 August 18th, 2006 at 11:34 pm
Simone: I hyperlinked the word “here” above to the paper in question. Here is the URL spelled out: http://www.cse.psu.edu/~furer/Papers/cfi.ps
Comment #35 August 19th, 2006 at 10:57 am
Concerning Time Magazine’s article about Peter Woit’s and Lee Smolin’s books:
The emphasize on confirmation in science is a completely understandable reaction to pseudo-science, and even more so to religious intrusions on science. But in my view, it has come to be a shallow point and it is sometimes oversold. Even creationists have learned to use it against evolutionary biology. (Of course at the level of flim-flam rather than real science.) It is easy to forget that there is more to theory than educated stabs at the experimental truth.
To take an extreme example, very little was known about the hidden side of the moon before the space age. Undoubtedly there were discussions in lunar astronomy where people said, “Let us suppose that the hidden side of the moon is much like the side that we can see.” If you wanted to be obnoxious, you could say, “Stop right there! No testable hypotheses.”
Likewise, string theory and quantum computation are both attempts at reasonable extrapolations of known physics. They are equally vulnerable to inappropriate foot-tapping from skeptics demanding confirmation. What they miss is that really good testable hypotheses may take a lot of work. Some efforts at it deserve great patience. I would think that everyone here accepts QC as a good example. My outside impression is that string theory is an equally meritorious example.
Of course, the example about the hidden side of the moon can also be defended by Occam’s razor. Which is the whole point. Some of the implications of Occam’s razor are far from obvious. For example, to me it suggests that BQP is a realistic complexity class. String theorists would emphasize that Occam’s razor excludes inconsistent models above all.
Comment #36 August 19th, 2006 at 11:09 am
Thanks Greg. I did not see the correct post before.
Comment #37 August 21st, 2006 at 7:59 pm
What about “Can NP-complete problems be solved efficiently in the physical universe?”
I bring this up because I thought your paper, “NP-complete Problems and Physical Reality,” was pretty much saying “no,” (at least with respect to adiabatic QC), but on Geordie Rose’s blog, he links to that very paper while building a case that he’ll solve Max Clique with an adiabatic quantum processor. What’s up with that?
Comment #38 August 22nd, 2006 at 3:48 am
This is not that hard. Either he means that he’ll get a polynomial speedup (as the adiabatic algorithm can), or he means that he’ll get a constant-factor speedup, or he means something false. 🙂
(Of course, if he can put NP in BQP then I’ll stand corrected…)
Comment #39 August 26th, 2006 at 12:48 pm
Re: NP-complete problems, superconducting AQCs etc: If what we were aiming for were exact solutions, then a quadratic speed-up together with a big prefactor speed-up is probably the best we could hope for (although note that a naive application of the quadratic speed up (2^N->2^0.5N) still doesn’t beat the best exact classical clique algorithms ~2^0.2N).
The problem is actually much more interesting than this. The capabilities of the AQC need to be integrated together with classical algorithms in a non-trivial way to get “good approximations”, not just exact solutions. Analyzing the performance of AQCs+conventional clique algorithms where success is defined to be obtaining an answer within $epsilon$ of the exact solution is more on point for us. Time will tell how this hybrid system actually performs on clique problems.
Comment #40 September 20th, 2006 at 5:10 pm
Partial answer to #10
http://www-users.york.ac.uk/
~ss54/scottquestion.pdf
Comment #41 December 21st, 2006 at 6:41 pm
[…] A month ago, I posed the following as the 10th most annoying question in quantum computing: Given an n-qubit pure state, is there always a way to apply Hadamard gates to some subset of the qubits, so as to make all 2n computational basis states have nonzero amplitudes? […]
Comment #42 December 21st, 2006 at 6:57 pm
[…] Alright, I can give an oracle relative to which BQP is not in SZK, thereby knocking off one of the Ten Most Annoying Questions in Quantum Computing. […]