The NEW Ten Most Annoying Questions in Quantum Computing
Eight years ago, I put up a post entitled The Ten Most Annoying Questions in Quantum Computing. One of the ten wasn’t a real question—it was simply a request for readers to submit questions—so let’s call it nine. I’m delighted to say that, of the nine questions, six have by now been completely settled—most recently, my question about the parallel-repeated value of the CHSH game, which Andris Ambainis pointed out to me last week can be answered using a 2008 result of Barak et al. combined with a 2013 result of Dinur and Steurer.
To be clear, the demise of so many problems is exactly the outcome I wanted. In picking problems, my goal wasn’t to shock and awe with difficulty—as if to say “this is how smart I am, that whatever stumps me will also stump everyone else for decades.” Nor was it to showcase my bottomless profundity, by proffering questions so vague, multipartite, and open-ended that no matter what progress was made, I could always reply “ah, but you still haven’t addressed the real question!” Nor, finally, was my goal to list the biggest research directions for the entire field, the stuff everyone already knows about (“is there a polynomial-time quantum algorithm for graph isomorphism?”). My interest was exclusively in “little” questions, in weird puzzles that looked (at least at the time) like there was no deep obstruction to just killing them one by one, whichever way their answers turned out. What made them annoying was that they hadn’t succumbed already.
So, now that two-thirds of my problems have met the fate they deserved, at Andris’s suggestion I’m presenting a new list of Ten Most Annoying Questions in Quantum Computing—a list that starts with the three still-unanswered questions from the old list, and then adds seven more.
But we’ll get to that shortly. First, let’s review the six questions that have been answered.
CLOSED, NO-LONGER ANNOYING QUESTIONS IN QUANTUM COMPUTING
1. 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? Positive answer by Ashley Montanaro and Dan Shepherd, posted to this blog in 2006.
3. Can any QMA(2) (QMA with two unentangled yes-provers) protocol be amplified to exponentially small error probability? Positive answer by Aram Harrow and Ashley Montanaro, from a FOCS’2010 paper.
4. If a unitary operation U can be applied in polynomial time, then can some square root of U also be applied in polynomial time? Positive answer by Lana Sheridan, Dmitri Maslov, and Michele Mosca, from a 2008 paper.
5. 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?
OK, let me relay what Andris Ambainis told me about this question, with Andris’s kind permission. First of all, we’ve known for a while that the optimal success probability is not the (3/4)n that Alice and Bob could trivially achieve by just playing all n games separately. I observed in 2006 that, by correlating their strategies between pairs of games in a clever way, Alice and Bob can win with probability (√10 / 4)n ~ 0.79n. And Barak et al. showed in 2008 that they can win with probability ((1+√5)/4)n ~ 0.81n. (Unfortunately, I don’t know the actual strategy that achieves the latter bound! Barak et al. say they’ll describe it in the full version of their paper, but the full version hasn’t yet appeared.)
Anyway, Dinur-Steurer 2013 gave a general recipe to prove that the value of a repeated projection game is at most αn, where α is some constant that depends on the game in question. When Andris followed their recipe for the CHSH game, he obtained the result α=(1+√5)/4—thereby showing that Barak et al.’s strategy, whatever it is, is precisely optimal! Andris also observes that, for any two-prover game G, the Dinur-Steurer bound α(G) is always strictly less than the entangled value ω*(G), unless the classical and entangled values are the same for one copy of the game (i.e., unless ω(G)=ω*(G)). This implies that parallel repetition can never completely eliminate a quantum advantage.
6. Forget about an oracle relative to which BQP is not in PH (the Polynomial Hierarchy). Forget about an oracle relative to which BQP is not in AM (Arthur-Merlin). Is there an oracle relative to which BQP is not in SZK (Statistical Zero-Knowledge)? Positive answer by me, posted to this blog in 2006. See also my BQP vs. PH paper for a different proof.
9. 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? A positive answer follows from this 2009 paper by Richard Low—thanks very much to Fernando Brandao for bringing that to my attention a few months ago.
OK, now on to:
THE NEW TEN MOST ANNOYING QUESTIONS IN QUANTUM COMPUTING
1. Can we get any upper bound whatsoever on the complexity class QMIP—i.e., quantum multi-prover interactive proofs with unlimited prior entanglement? (Since I asked this question in 2006, Ito and Vidick achieved the breakthrough lower bound NEXP⊆QMIP, but there’s been basically no progress on the upper bound side.)
2. Given any n-qubit unitary operation U, does there exist an oracle relative to which U can be (approximately) applied in polynomial time? (Since 2006, my interest in this question has only increased. See this paper by me and Greg Kuperberg for background and related results.)
3. How many mutually unbiased bases are there in non-prime-power dimensions?
4. Since Chris Fuchs was so thrilled by my including one of his favorite questions on my earlier list (question #3 above), let me add another of his favorites: do SIC-POVMs exist in arbitrary finite dimensions?
5. Is there a Boolean function f:{0,1}n→{0,1} whose bounded-error quantum query complexity is strictly greater than n/2? (Thanks to Shelby Kimmel for this question! Note that this paper by van Dam shows that the bounded-error quantum query complexity never exceeds n/2+O(√n), while this paper by Ambainis et al. shows that it’s at least n/2-O(√n) for almost all Boolean functions f.)
6. Is there a “universal disentangler”: that is, a superoperator S that takes nO(1) qubits as input; that produces a 2n-qubit bipartite state (with n qubits on each side) as output; whose output S(ρ) is always close in variation distance to a separable state; and that given an appropriate input state, can produce as output an approximation to any desired separable state? (See here for background about this problem, originally posed by John Watrous. Note that if such an S existed and were computationally efficient, it would imply QMA=QMA(2).)
7. Suppose we have explicit descriptions of n two-outcome POVM measurements—say, as d×d Hermitian matrices E1,…,En—and are also given k=(log(nd))O(1) copies of an unknown quantum state ρ in d dimensions. Is there a way to measure the copies so as to estimate the n expectation values Tr(E1ρ),…,Tr(Enρ), each to constant additive error? (A forthcoming paper of mine on private-key quantum money will contain some background and related results.)
8. Is there a collection of 1- and 2-qubit gates that generates a group of unitary matrices that is (a) not universal for quantum computation, (b) not just conjugate to permuted diagonal matrices or one-qubit gates plus swaps, and (c) not conjugate to a subgroup of the Clifford group?
9. Given a partial Boolean function f:S→{0,1} with S⊆{0,1}n, is the bounded-error quantum query complexity of f always polynomially related to the smallest degree of any polynomial p:{0,1}n→R such that (a) p(x)∈[0,1] for all x∈{0,1}n, and (b) |p(x)-f(x)|≤1/3 for all x∈S?
10. Is there a quantum finite automaton that reads in an infinite sequence of i.i.d. coin flips, and whose limiting probability of being found in an “accept” state is at least 2/3 if the coin is fair and at most 1/3 if the coin is unfair? (See this paper by me and Andy Drucker for background and related results.)
Follow
Comment #1 May 13th, 2014 at 2:11 pm
When some of these get resolved, I would suggest the following additions:
11. Does communication complexity become trivial when we have nonlocal boxes with success rates higher than quantum’s 0.85…? In quant-ph/0508042 Brassard et al. showed that the answer is “yes” if the success rate is at least 0.908.. What happens between these two values has annoyed me for far too many years.
12. Are there total functions for which the bounded error quantum query complexity is more than quadratically better than the classical complexity? [I’ve been told that Scott considers this question ‘beyond annoying’, which disqualifies it from being on the above list.]
Comment #2 May 13th, 2014 at 4:59 pm
Hi Scott,
Thanks for these! In the spirit of number 5, I would also add one of my own favourites:
13. Are there total boolean functions on n bits whose exact quantum query complexity is equal to n, and which are not equivalent to AND on n bits?
It was conjectured that the answer is “no” in a recent paper by Ambainis, Gruska and Zheng.
Comment #3 May 14th, 2014 at 3:46 am
So, 8 doesn’t seem all that hard, but rather simply requires a lot of work. If you take the 1 and 2 qubit gates applied to a two qubit system, they necessarily generate some subgroup of SU(4). You can enumerate the semi-simple lie groups using Dynkin diagrams, and the finite subgroups have been characterised (see http://openaccess.city.ac.uk/818/1/9905212v2.pdf for example). It seems likely that once you have this you can then work out what group they can generate when applied across n qubits (for examples of this see Daniel Burgarth’s papers on quantum control).
Comment #4 May 14th, 2014 at 5:35 am
8. There is collection of 1- and 2-qubit gates densely approximating group of matchgates and because such gates need to generate group with infinite amount of elements to approximate the continuous group they may not belong to Clifford group.
Comment #5 May 14th, 2014 at 5:45 am
PS. Yet, the collection of gates may be converted into universal set by addition of swap gates acting on some pair of qubits.
Comment #6 May 14th, 2014 at 6:42 am
Alexander #4, #5: Yeah, I’m aware of the matchgates, thanks! However, they don’t provide an example of what I’m asking for, because they only give you a non-universal set when there’s a nearest-neighbor restriction on which pairs of qubits you can apply them to. In this problem, the assumption is that you can apply any gate in your set to any list of qubits that you want, as often as you want.
Comment #7 May 14th, 2014 at 6:54 am
Joe #3: Yes, that basically is the approach that my student Adam Bouland and I (or Adam, really 🙂 ) recently took to classify the 2-mode beamsplitters! (Which was intended as a warmup to the classification of 1- and 2-qubit gates.) For that, we used the classification of irreps of subgroups of SU(3). Alas, not only was it complicated, involving pages of case analysis, but Adam found out after writing it that a guy named Patrick Otto Ludl recently discovered that the published classifications were missing a family of irreps! (Yes, it’s mindblowing that something this basic could’ve been overlooked, but there you have it.) So then he had to add a couple more pages of reasoning to deal with Ludl’s family (it didn’t change the conclusion).
Because of this experience, we’re not sure that we should trust a published classification of the representations of subgroups of SU(4), if it hasn’t been “Ludl-ized” yet. And of course, even if it has, carrying this out would be considerably more complicated than in the SU(3) case.
So, it would be extremely interesting if there were a way to get to the answer we want without going through all of this!
Comment #8 May 14th, 2014 at 10:38 am
Another exception you should include in 8 is SU(2) plus permutations of the qubits.
The best candidate I know of for the “no” answer to 8 is the Clifford group conjugated by some non-Clifford single-qubit gate. (This candidate is due to Carlos Mochon.) If your initial states and measurements are in the standard basis, it’s not clear how to simulate them classically, so it makes sense to count it as a separate case from the Clifford group. But it is not universal because it is still a finite group.
Note, Joe #3, that you also need to rule out infinite groups, and it’s not clear that looking at characterizations of the subgroups of SU(4) is sufficient, because there are isomorphic subgroups of SU(4) that will lead to different groups when you extend to more qubits. (Consider the various U(1) subgroups generated by any single gate.)
Let me also add another semi-question:
3.5 Why does everyone seem to think 3 and 4 are related? And are they?
Comment #9 May 14th, 2014 at 1:19 pm
Daniel #8: Thanks so much for the corrections to question 8—I’ve implemented them both! Omitting 1-qubit gates with swaps was just a silly oversight, but omitting the Clifford group conjugated by a non-Clifford 1-qubit gate was a genuine, non-silly oversight—i.e., I’m embarrassed that Carlos’s candidate didn’t occur to me. Still, of course what I’d really like to know is whether there’s any interesting non-universal subgroup that’s not equivalent to a subgroup of the Clifford group (even under conjugation), so I edited the question to make that clear.
And yes, the issue you raise—that it’s not enough to have a characterization of the subgroups of SU(k); you also need a characterization of all the inequivalent representations of the subgroups—is exactly what led to the complexity of my and Adam Bouland’s paper on beamsplitter universality. This is also where the error crept in that Patrick Otto Ludl identified: the classification of the subgroups of SU(3) was fine; it was the published classification of the irreps of those subgroups that was missing something.
As for the relation (if any) between MUBs and SIC-POVMs: the Wikipedia article on SIC-POVMs has an interesting section about the analogies between them and MUBs, which don’t however seem to rise right now to the level of any formal implications in either direction (someone correct me if I’m wrong).
Comment #10 May 14th, 2014 at 1:44 pm
I always imagined Pure Math to be the field where lists of unsolved questions are hardest to understand.
But now I’m convinced that it’s Comp. Sci. Or rather QC. 🙂
Boy those questions were hard to understand.
Comment #11 May 14th, 2014 at 3:22 pm
Very nice new list, and very successful old list! (Greg nicely said there that it may in the end be more helpful to come up with “annoying” problems than with “Everests.”) I looked at the old thread and there were a couple of suggestions for #10. One by Simone Severini was if it is NP hard to compute the “quantum chromatic number” of a graph. Another by “Tez” was a speculative way to distinguish non isomorphic graphs based on a certain k-symmetric powers. Are there news about them? (Interestingly many of the links in this thread are by now broken.)
Comment #12 May 14th, 2014 at 6:52 pm
Question #1 tantalizes me. Sure there must be some god-awful way to show that QMIP \(\subseteq\) ELEMENTARY? I believe the problem is that there is no way to upper bound the amount entangled qubits the provers will use. Even without such a bound I believe it would be possible to prove that every language in QMIP is recursively enumerable, seeing as it is possible to search through all protocols with any amount of entanglement until one works. I suppose that counts as “any bound whatsoever”, if only in the loosest sense possible.
Comment #13 May 14th, 2014 at 7:41 pm
Here is an annoying weakening of the SIC-POVM question:
The SIC-POVM question is to find a d^2 vectors in d space such that v_i* v_i = 1 and (v_i* v_j) (v_j* v_i) = 1/(d+1) for i not equal to j. (Here * means conjugate transpose.)
We can ask instead if there are two lists of d^2 complex vectors, v_i and w_i, such that
v_i^T w_i = 1
(v_i^T w_j) (v_j^T w_i) = 1/(d+1).
Now we have removed complex conjugation from the situation and just have d^2 (d^2+1)/2 polynomial relations between d^3 variables. Can anyone explain why they should be solvable, even before we impose the constraint that v_i = \bar{w}_i?
Comment #14 May 14th, 2014 at 7:49 pm
Sorry, that should say 2d^3 variables. I should probably say that the point of thinking this way is to get algebraic geometry into play, as it likes polynomial equations better than complex conjugation.
Comment #15 May 14th, 2014 at 8:48 pm
Gil #11: Yes, those were good questions too! I just googled “quantum chromatic number NP-hard” to see whether that problem had been solved yet, but none of the papers that I found about the quantum chromatic number (including several after 2006) mentioned any proof of its NP-hardness. So I’m going to guess that that one’s still open (someone please correct me if I’m wrong!). As for quantum algorithms for graph isomorphism, I know that there were a bunch of ideas similar to Tez’s that failed to pan out, but not being an expert, I can’t speak to any specific proposal.
Comment #16 May 14th, 2014 at 8:55 pm
Itai #12: Amazingly annoyingly, your argument for
QMIP ⊆ RECURSIVELY-ENUMERABLE
only works if you define QMIP so that the amount of entanglement used by the provers has to be finite! There are also sensible notions of QMIP with infinite-dimensional Hilbert spaces, and no one has proved that the maximum value attainable with those can always be achieved as a lim sup of finite-dimensional strategies. If it weren’t, then QMIP wouldn’t even need to be r.e. (And even if you define this problem away, I believe we still don’t have an upper bound better than r.e. There was a paper discussing this, but I can’t find it right now.)
Anyway, the QMIP upper bound problem was, in retrospect, arguably the most important example of a problem that shouldn’t have been on my list. For it’s now known to be closely related to very deep open problems in operator algebras; this explains its difficulty and shows that it was anything but a “little annoyance” to be knocked off with a week or two of effort. (This paper might be relevant — I’m not sure. Maybe someone else can fill us in on the details.)
Comment #17 May 14th, 2014 at 11:03 pm
How is question 2 formalized? Do we need to talk about a family of unitary matrices, one for each n, and then a language L, such that BQP with access to L can implement {U_n} approximately? Can I think about it without using a family of uinitary matrices? Do we have to worry about uniformity in the BQP circuit?
Comment #18 May 15th, 2014 at 3:20 am
Scott/Gil: I believe (though would be very happy to be corrected!) that it’s not only still open whether the quantum chromatic number is NP-hard, it’s even still open whether it is computable at all.
Comment #19 May 15th, 2014 at 6:54 am
Another Anon #17: No, you don’t need to worry about Turing machines and uniformity for this problem. A simple argument is that you could always hard-code a description of a polynomial-size circuit into an initial part the oracle A, and have a universal Turing machine that read the description and then simulated the circuit. Thus, if this problem is solvable using nonuniform machines, then it’s also solvable using uniform ones. And conversely, if you’re trying to prove impossibility by any BQP algorithm (which is what I conjecture), then you might as well phrase the problem as proving that, for many n-qubit unitaries U, there’s no polynomial-size quantum circuit C and oracle A such that CA applies U.
Comment #20 May 15th, 2014 at 7:58 am
@Itai 12: In ‘tantalizes’, I think I meant to say ‘taunts’. Both words work, though.
@Scott 16: Thanks for the explanation. I see why the problem is difficult. Moving on, hopefully it may be possible to prove the Hilbert space has a countable dimension (and that may even be part of the definition). In that case it should be possible to prove that \(\mathrm{QMIP} \subseteq \Sigma^1_1\). (By now I’m clearly cheating. I might as well say that the fact that QMIP is definable in ZFC is in itself an upper bound.)
Comment #21 May 15th, 2014 at 10:31 am
I’m not sure whether you would consider this an answer to question 8 or just another example illustrating the need to slightly modify the phrasing of the question, but I believe the following is a class of quantum gates that can be efficiently simulated classically and which are not already included in your list of exceptions. Basically, the gates are a restricted class of conjugated permuted diagonal unitaries. One might be tempted to think that all conjugated permuted diagonal unitaries can be efficiently simulated classically, but this appears not to be the case. (For example, consider Simon’s algorithm, which is a permutation conjugated by Hadamards.)
\( \phantom{x} \)
This following is a lemma from joint work with Gorjan Alagic and Aniruddha Bapat to appear in TQC2014.
\( \phantom{x} \)
Let \(\mathcal{R}=\{R_1,R_2,\ldots,R_k\}\) be a set of unitary 2-qudit gates, each one a composition
$$R_i = (Q \otimes Q) D_i P_i (C_i \otimes C_i) (Q \otimes Q)^{-1}$$
of invertible operators. Suppose that for each \(i\), \(D_i\) is a diagonal unitary, \(C_i\) is a \(d \times d\) permutation matrix, and \(P_i\) is either the identity or the swap gate. Under a certain condition on \(Q\), described below, there exists a classical probabilistic algorithm which, given an \(n\)-qudit \(\mathcal{R}\)-circuit \(U\) of \(m\) gates, strings \(x,z \in \{0,1,\ldots,d\}^n\), and \(\epsilon > 0\), outputs a number \(r\) in time \( \mathrm{poly}(n,m,1/\epsilon)\) such that \( |r-\langle x | U | z \rangle | \lt \epsilon\) except with probability exponentially small in \(n\) and \(1/\epsilon\).
$$ $$
Condition on \(Q\): Let \(G\) be the subgroup of \(S_d\) generated by \(\{C_1,\ldots,C_k\}\). Let \(A_{ij} = |Q_{ij}|\) and \(B_{ij} = | ( Q^{-1} )_{ij}| \). For every \( \pi \in G \) we demand \( \sum_j A_{k\pi j} B_{jl} \leq 1\). Note that \(Q \) need not be unitary.
Comment #22 May 15th, 2014 at 10:41 am
Also, although you have disqualified conjugates of the Clifford group from being answers to question 8, I think it is interesting to note that they are not so trivial. By starting with \(|00\ldots 0\rangle\), applying a conjugated Clifford circuit, and measuring in the computational basis, one can sample from probability distributions that cannot be efficiently sampled from classically without collapsing the PH. This follows from results of Jozsa and Van den Nest in arXiv:1305.6190.
Comment #23 May 15th, 2014 at 11:42 am
Stephen #21 and #22: Thanks! Yeah, I noticed yesterday that you could also take classical gates and conjugate them by a 1-qubit unitary to get a plausibly-intermediate class, and I kept meaning to edit question 8 further to reflect that observation, but something else kept coming up, and now you’ve beat me to it. 🙂 And yes, it’s clear that you can get hardness of exact sampling results for these sorts of models (assuming PH is infinite) — I learned yesterday that Adam Bouland and Joe Fitzsimons had independently made the same observation.
So yes, this does significantly change my understanding of the problem of classifying quantum gate sets. But that was yesterday! 😉 Today I’ve already assimilated this, and want to know whether there’s any way BESIDES conjugation to get an “exotic” set of 1- and 2- qubit gates (i.e., something besides classical, 1-qubit, Clifford, and universal).
Incidentally, I can see why you get a hard problem by taking classical 3-qubit gates (including the Toffoli gate) and conjugating them by Hadamards. But can you show that we also get a hard problem by conjugating classical 2-qubit gates by Hadamards?
Comment #24 May 15th, 2014 at 11:45 am
It appears I misread your question 8, and didn’t notice that it said “not just conjugate to permuted diagonal matrices.” So, my example in comment 21 actually is amongst the already listed exceptions.
Comment #25 May 15th, 2014 at 12:11 pm
Stephen: No, I edited the question (which, as I said, I was meaning to do, but your comment prodded me)!
Comment #26 May 15th, 2014 at 12:22 pm
Oh, I see. Someone should write a worpress plugin that provides arxiv-style timestamped versioning.
Comment #27 May 15th, 2014 at 1:04 pm
Scott 23: As I recall, all two-bit reversible gates are linear over \(\mathbb{Z}_2\), which I think implies that they can all be constructed from NOT and CNOT. So, unless I am mistaken, the answer to your question “But can you show that we also get a hard problem by conjugating classical 2-qubit gates by Hadamards?” is: No, the resulting circuits are all contained in the Clifford group.
Comment #28 May 15th, 2014 at 1:09 pm
Stephen #27: Ah, but what if we allow 2-qubit Controlled-Phase gates, where the phase we rotate by could be an irrational multiple of π?
Comment #29 May 16th, 2014 at 3:08 am
Scott (#28), that model contains IQP. But this raises an interesting point. You phrase 8 in terms of the group generated by the gates, but much of the argument in the comments is related not to the group generated, but rather the combination of that and the set of input states and measurements allowed. If you define any of these groups without reference to a particular state or structure, then some of the groups discussed above are identical (i.e. Cliffords vs rotated Cliffords etc.).
Comment #30 May 16th, 2014 at 8:22 am
Joe #29: OK, so we could summarize by saying that the groups are the same (under isomorphism), and even their representations are the same (under conjugation), but the representations do differ by conjugation, and the latter can matter for computational complexity purposes.
Comment #31 May 16th, 2014 at 11:04 am
Well, none of a particular set of isomorphic circuit groups is more powerful than any other until you start putting restrictions on input and output. The conjugated Clifford group gates only appear more powerful because we are making measurements and doing state preparation in a way which has not been transformed in the same way. You can get exactly the same model from the usual Clifford group by allowing preparation in non-stabiliser states and measurement of non-Pauli operators. The actual gates don’t tell you the full story about complexity without a reference specified by allowable input and measurement.
Comment #32 May 16th, 2014 at 11:56 am
Joe: Yes, sure, if we care about complexity rather than just classification, then assume all initial states and all measurements are in the computational basis.
Comment #33 May 16th, 2014 at 12:54 pm
Does http://arxiv.org/pdf/quant-ph/0510187.pdf imply that you can do no better than the naive algorithm for (7)? (where the naive algorithm is just repeated measurement of Tr(E_n \rho))
Or is the intent to make use of structure among the set of E_n? I feel like I’m missing something. (I should probably just wait for you paper…)
Comment #34 May 16th, 2014 at 1:32 pm
Ashley #18: I haven’t checked this thoroughly, but I think http://arxiv.org/abs/1310.3794 shows that checking whether a graph is quantum 3-colorable is NP-hard?
Comment #35 May 16th, 2014 at 1:44 pm
Scott: Sure, you could specify the problem that way, but maybe it makes the problem have too many special cases. It seems to me that there are several questions here:
1) What groups are generated by sets of 1 and 2 qubit gates?
2) What complexity classes does the fundamental representation of each such group give rise to for different restrictions on input and measurement?
3) What additional structure is gained for different representations?
It seems like these are questions may be more approachable individually.
Comment #36 May 16th, 2014 at 1:51 pm
Daniel #33: Thanks for the link to that paper, which I hadn’t seen! Unfortunately, unless I’m missing something it doesn’t solve the problem, since it deals with estimating the expectation value of just a single observable, whereas I care about N observables. And yes, you could glom together N observables into a single mega-observable, but if you do that then there’s no good reason why the success requirement (that each Tr(Ei ρ) is approximated to within ε) will be preserved.
To build intuition for question 7, you might enjoy proving that, IF you’re promised that either Tr(Ei ρ)≤1/3 or Tr(Ei ρ)≥2/3 for all i, then it’s easy to achieve the sort of measurement I’m asking for, indeed with k=O(log N) completely independent of d.
Comment #37 May 16th, 2014 at 4:12 pm
Cedric #34: Thanks! You’re right.
Comment #38 May 19th, 2014 at 11:23 am
I’m afraid I’m late to the party, but I’d like to suggest my favourite annoying question: is the entangled value of a nonlocal game \(\omega^*(G)\) computable?
Comment #39 May 19th, 2014 at 12:09 pm
Mateus #38: Isn’t that basically equivalent to the problem of upper-bounding QMIP (i.e., problem 1 on my list)?
Comment #40 May 19th, 2014 at 6:24 pm
Scott #39: I was not aware of this connection. Can you enlighten me?
My impression is that upper bounds on \(\omega^*(G)\) lead to lower bounds on MIP\(^*\), whereas upper bounds on the amount of entanglement that you need to perform the optimal strategy in a nonlocal game lead to upper bounds on MIP\(^*\). But I don’t know how to relate \(\omega^*(G)\) to upper bounds on MIP\(^*\).
Comment #41 May 19th, 2014 at 10:14 pm
Annoying problem #8′:
Figure out a good way to express what it means for a set of gates to be not universal.
Comment #42 May 20th, 2014 at 10:27 am
Mateus #40: I was simply thinking that, if you had an algorithm to compute ω*(G), then you could express an MIP* protocol as a 2-prover game and thereby get a computable upper bound on MIP*. And aonversely, if you had a computable upper bound on MIP*, then given a 2-prover game G, then you could define a language L such that, for some input x, whether x∈L depended on whether ω*(G) was ≥2/3 or ≤1/3. Then deciding whether x∈L would at least give you a nontrivial approximation to ω*(G). It’s entirely possible that I’m missing something, but if so, could you tell me what?
Comment #43 May 20th, 2014 at 11:30 am
Scott #42: Yet again you baffle me. Perhaps I should clarify that my background is in physics and I know these results about MIP* only from hearsay. But I care a lot about this problem, as the computability of ω*(G) is hot topic in the nonlocality community now (or, more specifically, the quality of a particular upper bound on ω*(G)).
So why the computability of ω*(G) implies that one can reduce the number of provers to 2? And are good upper bounds known for MIP*(2,1)?
I’d be glad if you could explain or point me to a reference.
In addition, do you wish to risk a guess on the computability of ω*(G)? At least from my side (and I believe most physicists agree with me) it’s clear that it’s not computable.
Comment #44 May 20th, 2014 at 11:53 am
Mateus: Sorry, I wasn’t even thinking about more than 2 provers or more than 1 round. Let’s just define MIP* to mean MIP*(2,1)—in any case, we still don’t have a computable upper bound even in that case. Do you still see any difference between the problem of upper-bounding MIP*(2,1) and the problem of giving an algorithm to approximate ω*(G), for a 2-prover game G?
FWIW, my guess is that it might well be undecidable whether ω*(G)=1—I’m not sure—but that, in any case, there ought to be an algorithm to approximate ω*(G), since you ought to be able to get within ε of the optimal value ω*(G) using an amount of entanglement that scales reasonably with the size of G.
Comment #45 May 20th, 2014 at 4:28 pm
Ah! That’s good to know. I never understood why computer scientists cared about having more than one round.
So, the converse seems clear to me, but I still don’t see how being able to approximate ω*(G) (how well? up to a costant?) would give a computable upper bound on MIP*. Does computable upper bound in this context mean including it in a computable complexity class?
About the conjecture, I don’t expect to get within ε for a reasonable amount of entanglement. After all, there is strong numerical evidence that even for a particular instance of a game you need infinite-dimensional states: arXiv:1006.3032.
Comment #46 May 20th, 2014 at 10:07 pm
Mateus: Yes, if you could approximate ω*(G) up to an additive constant less than 1/2, that would let you simulate MIP*(2,1) in some computable complexity class. The reason is just that a 2-prover, 1-round interactive protocol is exactly a 2-prover game! The verifier submits questions to the provers and receives answers from them, the goal of the provers is to cause the verifier to accept with the maximum probability, and the verifier’s algorithm defines the function that the provers are trying to maximize. And the provers can use entanglement to coordinate their answers. Is there anything else that needs to be said?
Also, the paper you linked to is interesting and not something I’d seen, so thanks! However, from a quick scan, I couldn’t tell whether the paper actually provides any evidence against the conjecture that I made. Remember, I’m not saying there aren’t games (even purely-classical games) where you can win with higher and higher probability the more entanglement you have—in fact, I think it’s quite likely that such games exist (and the Pal-Vertesi paper strengthens that belief). My conjecture says only that:
(1) As you increase the amount of entanglement, the success probability converges to a limit, which equals the success probability that you can attain using a countably-infinite amount of entanglement.
(2) A computable upper bound can be given on the rate of convergence.
So, again, do Pal and Vertesi give any evidence against that?
(1) and (2) above would clearly suffice for placing a computable upper bound on the QMIP*(2,1) class.
Comment #47 May 21st, 2014 at 8:17 am
Scott: Ah! I see! The point is that a 2-prover game where you know the probabilities of succes is strictly more powerfull than one where you don’t. I’m sorry, I should have realized that sooner.
As for the conjecture, you’re right, the paper does not provide evidence against that. It’s just a general feeling that the easiest way for the conjecture to be right would be if you could always get the optimal strategy with an amount of entanglement that would be a function of the size of the input, and this is not true. Certainly you might be able to get within ε for some nice function, but nobody knows any bound on how ε goes with the dimension of the state and the size of the input.
Comment #48 May 22nd, 2014 at 1:49 pm
Regarding the quantum chromatic number. It is indeed not known to be computable (again, essentially due to the fact that we don’t know how much entanglement the players might require). However, recently Zhengfeng Ji has shown that it is NP-hard [1310.3794]. So now we have “narrowed down” the possible complexity range to somewhere between NP and uncomputable.
Comment #49 May 24th, 2014 at 4:23 am
Scott,
Is there such a thing as quantum reduction ( like there is a special reduction for every type of Turing machine: polynomial reduction, probabilistic polynomial reduction etc )
I guess best candidates for example to have reduction between them is factoring and DLOG ( there is no polynomial reduction between them as far as i know )
Comment #50 March 10th, 2015 at 3:28 pm
[…] the apparent wide-spread interest in the problem (for example, see these statements of interest by Scott Aaronson and Peter […]