A breakthrough on QMA(2)?
Last night, Martin Schwarz posted a preprint to the arXiv that claims to show the new complexity class containment QMA(2) ⊆ EXP. (See also his brief blog post about this result.) Here QMA(2) means Quantum Merlin-Arthur with two Merlins—i.e., the set of languages for which a “yes” answer can be witnessed by two unentangled quantum states, |ψ〉⊗|φ〉, on polynomially many qubits each, which are checked by a polynomial-time quantum algorithm—while EXP means deterministic exponential time. Previously, the best upper bound we had was the trivial QMA(2) ⊆ NEXP (Nondeterministic Exponential Time), which comes from guessing exponential-size classical descriptions of the two quantum proofs.
Whether QMA(2) is contained in EXP is a problem that had fascinated me for a decade. With Salman Beigi, Andy Drucker, Bill Fefferman, and Peter Shor, we discussed this problem in our 2008 paper The Power of Unentanglement. That paper (with an additional ingredient supplied by Harrow and Montanaro) shows how to prove that a 3SAT instance of size n is satisfiable, using two unentangled quantum proofs with only Õ(√n) qubits each. This implies that searching over all n-qubit unentangled proofs must take at least exp(n2) time, unless 3SAT is solvable in 2o(n) time (i.e., unless the Exponential Time Hypothesis is false). However, since EXP is defined as the set of problems solvable in 2p(n) time, for any polynomial p, this is no barrier to QMA(2) ⊆ EXP being true—it merely constrains the possible techniques that could prove such a containment.
In trying to prove QMA(2) ⊆ EXP, the fundamental difficulty is that you need to optimize over unentangled quantum states only. That might sound easier than optimizing over all states (including the entangled ones), but ironically, it’s harder! The reason why it’s harder is that optimizing over all quantum states (say, to find the one that’s accepted by some measurement with the maximum probability) is a convex optimization problem: in fact, it boils down to finding the principal eigenvector of a Hermitian matrix. By contrast, optimizing over only the separable states is a non-convex optimization problem, which is NP-hard to solve exactly (treating the dimension of the Hilbert space as the input size n)—meaning that the question shifts to what sorts of approximations are possible.
Last week, I had the pleasure of speaking with Martin in person, when I visited Vienna, Austria to give a public lecture at the wonderful new research institute IST. Martin was then ironing out some final wrinkles in his proof, and I got to watch him in action—in particular, to see the care and detachment with which he examined the possibility that his proof might imply too much (e.g., that NP-complete problems are solvable in quasipolynomial time). Fortunately, his proof turned out not to imply anything of the kind.
The reason why it didn’t is directly related to the most striking feature of Martin’s proof—namely, that it’s non-relativizing, leaving completely open the question of whether QMA(2)A ⊆ EXPA relative to all oracles A. To explain how this is possible requires saying a bit about how the proof works. The obvious way to prove QMA(2) ⊆ EXP—what I had assumed from the beginning was the only realistic way—would be to give a quasipolynomial-time approximation algorithm for the so-called Best Separable State or BSS problem. The BSS problem, as defined in this paper by Russell Impagliazzo, Dana Moshkovitz, and myself (see also this one by Barak et al.), is as follows: you’re given as input an n2×n2 Hermitian matrix A, with all its eigenvalues in [0,1]. Your goal is to find length-n unit vectors, u and w, that maximize
(uT⊗wT)A(u⊗w),
to within an additive error of ±ε, for some constant ε.
Of course, if we just asked for a length-n2 unit vector v that maximized vTAv, we’d be asking for the principal eigenvector of A, which is easy to find in polynomial time. By contrast, from the ABDFS and Harrow-Montanaro results, it follows that the BSS problem, for constant ε, cannot be solved in poly(n) time, unless 3SAT is solvable in 2o(n) time. But this still leaves the possibility that BSS is solvable in nlog(n) time—and that possibility would immediately imply QMA(2) ⊆ EXP. So, as I and others saw it, the real challenge here was to find a quasipolynomial-time approximation algorithm for BSS—something that remained elusive, although Brandao-Christandl-Yard made partial progress towards it.
But now Martin comes along, and proves QMA(2) ⊆ EXP in a way that sidesteps the BSS problem. The way he does it is by using the fact that, if a problem is in QMA(2), then we don’t merely know a Hermitian operator A corresponding to the measurement of |ψ〉⊗|φ〉: rather, we know an actual polynomial-size sequence of quantum gates that get multiplied together to produce A. Using that fact, Chailloux and Sattath showed that a natural variant of the QMA-complete Local Hamiltonians problem, which they call Separable Sparse Hamiltonians, is complete for QMA(2). Thus, it suffices for Martin to show how to solve the Separable Sparse Hamiltonians problem in singly-exponential time. This he does by using perturbation theory gadgets to reduce Separable Sparse Hamiltonians to Separable Local Hamiltonians with an exponentially-small promise gap, and then using a result of Shi and Wu to solve the latter problem in singly-exponential time. All in all, given the significance of the advance, Martin’s paper is remarkably short; a surprising amount of it boils down to deeply understanding some not-especially-well-known results that were already in the literature.
One obvious problem left open is whether the full BSS problem—rather than just the special case of it corresponding to QMA(2)—is solvable in quasipolynomial time after all. A second obvious problem is whether the containment QMA(2) ⊆ EXP can be improved to QMA(2) ⊆ PSPACE, or even (say) QMA(2) ⊆ PP. (By comparison, note that QMA ⊆ PP, by a result of Kitaev and Watrous.)
Update (Nov. 10): I thought I should let people know that a serious concern has been raised by an expert about the correctness of the proof—and in particular, about the use of perturbation theory gadgets. Martin tells me that he’s working on a fix, and I very much hope he’ll succeed, but not much to do for now except let the scientific process trundle along (which doesn’t happen at blog-speed).
Follow
Comment #1 October 30th, 2015 at 6:41 pm
Do you know if the result algebrizes (if this question makes sense)?
Comment #2 October 30th, 2015 at 7:24 pm
g #1: I don’t even know whether the result relativizes. All I know is that Schwarz’s proof techniques are non-relativizing, so that a new proof would be needed to show that QMA(2)A⊆EXPA for all oracles A, if that’s indeed the case. (Showing that the statement relativizes would be more-or-less equivalent to giving a quasipolynomial-time approximation algorithm for the BSS problem.)
Now, just as the proof techniques are non-relativizing, it’s equally true that the techniques are non-algebrizing, so that a new proof would be needed to show that QMA(2)A⊆EXP~A for all oracles A, if that’s indeed the case. (Indeed, the reason why the techniques don’t relativize has nothing to do with low-degree polynomial extensions, as used for IP=PSPACE and other similar results, so there’s no reason why they would algebrize.) But again, this doesn’t imply that the containment itself doesn’t algebrize (indeed, if it relativizes, then it certainly algebrizes as well).
Comment #3 October 31st, 2015 at 12:59 pm
This sounds very interesting! Two questions that come to mind: First, there is still a huge gap between $2^o(n)$ and $n^{log (n)}$, what is the weakest results about BSS that will lead to the consequence on QMA(2) (perhaps relative to arbitrary oracles as well)? Second what is QMA(2) then, how small can it be?
Comment #4 October 31st, 2015 at 2:22 pm
Gil #3: Good questions.
If BSS is solvable in f(n) time, then you can simulate n-qubit QMA(2) protocols in f(2n) time. So, anything subexponential gives you a nontrivial simulation.
At present, we don’t have very good evidence even for QMA(2)≠QMA—not even a quantum oracle separation. There are one or two candidate problems in QMA(2), like pure state N-representability, that are not known to be in QMA, but that’s about it. Martin’s result at least tells us that QMA(2) doesn’t go to the other extreme of equaling NEXP, which before last week we didn’t have good evidence against either! Right now, I see it as extremely likely that QMA(2)⊆PSPACE, and as plausible even that QMA(2)⊆PP, but would still bet against QMA(2) equaling QMA (not at huge odds though).
Comment #5 October 31st, 2015 at 2:35 pm
After the last post, there is for me something truly refreshing about not understanding a single word of this one and therefore not forming an opinion and not having feelings about other people’s opinions, etc. !
Comment #6 October 31st, 2015 at 3:58 pm
luca #5: Welcome to my world! I can either talk about things most people won’t understand, or about things they will understand and will hate me for…
Comment #7 October 31st, 2015 at 8:10 pm
Scott #6:
Don’t worry Scott, there will be many who love you even when they don’t understand you, just by virtue of the fact that they admire someone who works hard and has mastered their craft.
Comment #8 October 31st, 2015 at 9:20 pm
william #7: Thanks so much. As happens once every couple of weeks, I had a pretty miserable day, its tone set by finding yet another person online who attacked me without bothering to learn the most basic facts. (Given my personality, sealing myself off from this stuff is just not an option—if someone says something vicious about me on the public Internet, I will read it and it will depress me for a while, until I make a conscious decision that continuing to do what I love is the only and best response.) Anyway, your comment just cheered me up.
Happy Halloween, everyone!
Comment #9 October 31st, 2015 at 10:16 pm
Between this work and the work by Ryan Williams it seems like were moving into an era where people are seriously starting to get around (possibly) the big barriers, but maybe we’ll just find more barriers.
One would naively have guessed that there might be a hierarchy here but since QMA(k)=QMA(2) for k >2, that doesn’t happen. Is there anything else that collapses if QMA(2)=QMA? For that matter, do we get any unexpected collapses if one takes the sort of ridiculous assumption that NP=QMA=QMA(2)?
(Also someone should update the Zoo entry with Schwarz’s result.)
Comment #10 October 31st, 2015 at 10:29 pm
Joshua #9: No, from the mere assumption that QMA=QMA(2), nothing is known to collapse. (If, however, the simulation of QMA(2) by QMA failed to blow up the number of qubits at least quadratically, that would mean 3SAT would be solvable in subexponential time!)
NP=QMA would be extremely surprising, more so than QMA=QMA(2)—among many other things it would obviously mean BQP⊆NP! But no, it by itself wouldn’t collapse any hierarchies as far as anyone knows.
Comment #11 November 1st, 2015 at 10:58 am
Hi Scott, sorry for going back to the old dwave post but I have a question.
Maybe somebody else proposed this already but, along the lines of dwave: what about making a dedicated CLASSICAL chip which is really a controllable ising lattice? Basically this would be a classical version of the quantum (??) one of dwave. Such a system could even be built on a board which you can then be inserted into a normal PC.
So basically you realize the annealing on a real system instead of into a program and it should be much faster. It’s kind of doing your pegs-and-soapy water experiment in reality instead of running a variational calculation program..
Does it make sense, or the complexity of translating the problem into an ising minimization kills also this idea?
Thanks for the latest complexity news.
Best, K.
Comment #12 November 1st, 2015 at 12:11 pm
anon #11: Sure, one could try that. Indeed, it would be quite interesting to see how the performance of an Ising-spin minimizer that’s “not even trying to be quantum” compared to the D-Wave machines’.
My rough guess is that, as with the D-Wave machines themselves, you could be competitive with or even superior to a single-core silicon chip for the exact problem for which you designed for your device (i.e., Ising spin minimization with this one particular coupling graph). But if you embed other NP-hard problems onto that one, then it’s quite likely that the blowup will kill you and silicon will again be superior.
In general, the rule in classical computing since the 1960s has been “silicon beats everything”—by now there’s a long history of nifty ideas people have tried for alternative computing architectures (analog, optical, superconducting…), and many of them could have found a market, had general-purpose silicon chips not been so damn good and clobbered all of them. The interesting question, to my mind, is whether this is because of something inherent about the silicon / integrated circuit architecture, or merely because once the whole world converges around some architecture and invests trillions of dollars in it, it becomes so good that nothing else can catch up.
Comment #13 November 1st, 2015 at 12:42 pm
Hi Scott,
Wonderfull post 🙂
Two side questions:
1) suppose that, instead of vectors composed of imaginary numbers (e.g. quantum state), QMA were defined as exchanging vectors of quaternions (or octonion, sednion, etc). Is QMA known to be, as a complexity class, robust to this kind of change, or would this modification deeply impact the properties of this complexity class?
2) a large part of your focus is on describing Schwarz’s proof. You describe some parts as “using gadgets”, and you describe some other parts as “boils down to deeply understanding [something]”.
Using exactly the same language (e.g., puting completly aside whether using this language boils down to describing some particular subjective feeling or to something much deeper), would you describe deep learning, random forests, and Watson as more of the “using gadgets” side, or as more of the “deeply understanding something” side?
Comment #14 November 1st, 2015 at 2:45 pm
Scott #12: thank you very much for the answer: you gave me many things to think about. Hope Lily had a nice halloween 😉 .
Comment #15 November 1st, 2015 at 5:15 pm
anon #14: She did! It was her first time trick-or-treating. At her request, we dressed her as a fairy (I was worried she would pick Peppa Pig, which is more complicated to pull off).
She didn’t fully grasp the protocol, needing constant reminders to say “trick-or-treat.” On the other hand, the basic concept of running from house to house, grabbing a candy from each one, and putting it in her bag was something she immediately understood and loved, as if she’d been doing it her whole life.
What struck me was that the basic components of the holiday—scaring 3-year-olds with skeletons and fake blood; encouraging them to take candy from strangers, indeed formally to extort candy under the threat of vandalism, and then gorge themselves eating high-fructose corn syrup; heavy interaction with neighbors just because they’re neighbors—none of it could ever have been invented in the fear- and lawsuit-driven modern world. It’s all a holdover from an earlier era. May our social norms never change so much that trick-or-treating becomes impossible.
Comment #16 November 1st, 2015 at 5:33 pm
Jay #13:
(1) QMA, like BQP and most other quantum complexity classes, is robust to replacing the complex amplitudes by reals or quaternions. (The octonions aren’t even associative, so in that case it’s harder even to define what we’re talking about.)
Interestingly, the situation is less obvious for classes like QMA(2), which involve stipulating that states are separable! There’s a paper by Matthew McKague that proves that QMA(2) is robust under replacing complex amplitudes by reals, but I don’t know about quaternions.
(2) Sorry, that question is a bit too broad for me. I think there was deep understanding of something that went into the invention several decades ago by Geoff Hinton and others of the backpropagation algorithm, and all the other neural net stuff that’s now been rebranded as “deep learning.” You might call it a deep understanding of a basic issue in statistics: how to approximate a huge class of nonlinear functions by a low-dimensional manifold that you kind-of, sort-of know how to optimize over. On the other hand, the whole point of all this is to avoid the need for the human programmers to have deep understanding of the particular application domain. (Famously, an IBM group in the 1990s used statistical ML to blow the previous results for English/French translation out of the water, despite the programmers themselves not speaking French.)
Comment #17 November 1st, 2015 at 6:40 pm
Scott #14: I’m an european living in north america and this was my third trick-or-treat experience with my children: indeed is an interesting sociological experiment..They enjoyed it so much this year that I agree on what you said. Sorry again for having dragged your blog post twice off-topic! But the idea of a physical controllable realization of an NP-complete problem keeps bugging me since some time. Soon or later I’ll try it.
Comment #18 November 1st, 2015 at 7:59 pm
Anon #11, Scott #12: I’m sure this has been tried before, but there’s a very recent rendition of this — this year Hitachi presented an N=20,000 Ising machine implemented using a custom-designed chip at the most prestigious circuits conference (ISSCC). Their graph was two layers of 2D nearest-neighbor Ising graphs. The title of their submission was: “20k-spin Ising Chip for Combinational Optimization Problem with CMOS Annealing”. Their paper/extended-abstract is available at http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7063111 . The main sales pitch in the paper is that they claim their chip can perform optimizations with much better power efficiency than regular processors.
Interestingly Hitachi apparently believe that this technology is sufficiently good at some image processing tasks (not described in the paper) that they’re considering adding a similar annealing chip as a coprocessor in cameras and cellphones. I will be very curious to see how this goes; if it works out, I think it’ll be the first mainstream use of a non-Von-Neumann-type coprocessor in at least 60 years!
Comment #19 November 1st, 2015 at 9:55 pm
> QMA, like BQP and most other quantum complexity classes, is robust to replacing the complex amplitudes by reals or quaternions. (The octonions aren’t even associative, so in that case it’s harder even to define what we’re talking about.)
Tangent, while people often think that the octonions being non-associative makes them terrible, they are almost associative in the following important sense: they are alternative (that is (xx)y=x(xy) and y(xx)=(yx)x) https://en.wikipedia.org/wiki/Alternative_algebra It turns out that for many purposes one wants associativity for, this property is enough. I would therefore guess that one can make BQP make sense for the octonions, but someone who knows more about these things would probably have to actually go and figure out what the correct interpretation is.
Comment #20 November 2nd, 2015 at 12:52 am
Joshua, QC is about vectors. Vectors of octonians are terrible. In particular, QC is about projective space. Projective octonionic space doesn’t exist. (Yeah, yeah, OP¹ exists. BFD. Credit it to alternation, if you must.) QC is about groups. Groups are associative. There are three families of groups: O(n), U(n), Sp(n), corresponding to R, C, H.
Lesson: your heuristic is completely wrong. The octonians are terrible.
Comment #21 November 2nd, 2015 at 1:06 am
Question: Is there any intuitive way of explaining why it is that QMA(2) could potentially be larger than QMA? Like, from the definition it’s easy to see why — a “no” answer only requires there to exist no unentangled pair of witnesses — but I don’t really have any good sense of what this means.
Seeing as (if I’ve understood correctly) the classical analogue of QMA(2) ends up just being MA, I’m guessing the answer may just be “sorry, there’s no simple explanation”, but I figured I’d ask.
Comment #22 November 2nd, 2015 at 1:14 am
Josh: I don’t think alternativity is going to be enough here. We want matrices and vectors to all work, right? (Well, vectors in O^n; I’m not even going to try to think about more general “vector spaces” over O.) But we have two big problems here:
The smaller problem is that matrix multiplication won’t work right — not even for 1×1 matrices. Matrix multiplication is supposed to represent composition, but without associativity, right-multiplication by x followed by right-multiplication by y won’t be right-multiplication by xy. So…?
Meanwhile the larger problem is that without associativity, right-multiplication isn’t even (left-)linear! The proof that a (left-)linear transformation of O^n must be (right-)multiplication by some matrix still goes through, I’m pretty sure, but not every matrix ends up being linear! In fact, I think the only way to get a matrix that actually acts as a linear transformation is for it to have all real entries. Which is, uh, pretty constrained. And honestly at that point, why are you using octonions? You may as well be using real numbers, seems to me; the octonion part isn’t really doing anything.
[Now let me go on a long tangent where I nitpick Josh’s comment about alternativity and point out that what really makes alternativity useful is not the bare relations he mentioned, but rather the fact that more generally, any subalgebra of O generated by two elements is associative — the octonions are “di-associative”, though for the reasons below one usually doesn’t bother to distinguish this from alternativity. (And note that x^-1 is in the subalgebra generated by x, since it’s equal to (2Re(x)-x)/||x||^2.)
Diassociativity does follow from those two relations, but requires the use of the fact that it’s an algebra, with addition and distributivity and all; for more general monoids, these relations are not enough to imply di-associativity. (Actually I think it requires moreover that O is a division algebra.) However any Moufang loop is di-associative; the proof that an alternative division algebra is di-associative works by proving (using addition and subtraction and such) that an alternative algebra satisfies the Moufang identities, and therefore the set of invertible (in this case, nonzero) elements is a Moufang loop.
(More generally it’s true in a Moufang loop that the subloop generated by any three associating elements is associative, a fact known as Moufang’s theorem.)]
Comment #23 November 2nd, 2015 at 7:04 am
Sniffnoy #21: Yes, I think it can be made reasonably intuitive. Suppose you’re a verifier, expecting two quantum witnesses that you’re going to cross-check against each other by measuring them in different, randomly-chosen bases. If the prover can entangle the witnesses, that might open up lots of ways for the prover to cheat—just like how entanglement lets you “cheat” in the CHSH game, winning it with greater than the “maximum possible” probability. So the assumption that the witnesses are unentangled gives more power to the verifier. And of course, the other way to think about it is that, if the verifier had wanted to eliminate the prover entirely, in the case of one witness it would just need to solve a convex optimization problem, but in the case of two or more witnesses (that are promised to be unentangled) it needs to solve a non-convex one.
If you want to understand how the promise of unentanglement actually gets used in real protocols, I think the first step would be to check out the Blier-Tapp protocol, which verifies that a graph is 3-colorable with two unentangled quantum proofs of log(n) qubits each, albeit with only a 1/poly(n) probability of catching cheating provers (which is why it doesn’t imply QMA(2)=NEXP—that 1/poly(n) becomes 1/exp(n) when you scale up by an exponential). Next you could look at our paper, where we verify that a 3SAT instance is satisfiable using O(√n polylog(n)) unentangled quantum proofs of log(n) qubits each. We tried hard to give an intuitive explanation of the protocol before delving into the soundness analysis.
Comment #24 November 2nd, 2015 at 8:22 am
Scott #16,
(1) thanks!
(2) ok then I’ll need to refine it
Joshua Zelinsky #19
Interesting! Could you provide a specific exemple (of a purposes for which one would want associativity, but for which alternativity may be enough)?
Douglas Knight #20
Is it possible your post was cut? What are OP, BFD, O(n), U(n), Sp(n), R, C, H?
Comment #25 November 2nd, 2015 at 9:07 am
I looked briefly at the paper, and that level of math is obviously way over my head.
The proof doesn’t seem that long, but how “difficult” is it for a professional in the field?
How likely is it that some mathematical error is lurking in there?
Is there a way to test this with an actual program/simulation?
Comment #26 November 2nd, 2015 at 9:35 am
fred #25: This is a brand-new preprint that hasn’t been peer-reviewed, and I haven’t verified all the details. So, yes, it’s always possible in such a case that an error will surface—either in this paper or in one of the several other recent papers that it relies on—and if it does of course I’ll update the post.
I decided to blog this because, as I mentioned in the post, I’m very satisfied that Martin did everything reasonable to try to test and refute his own result (e.g., making sure it didn’t imply anything absurdly strong).
Hopefully it will only take a year or so for this to be fully reviewed and appear in a journal. In practice, though, “review” will happen faster: various experts (especially grad students 🙂 ) will work through the arXiv preprint, and will let Martin know if there’s anything they don’t understand. And if this blog post causes that to happen a bit faster than it otherwise would have, so much the better.
The question about testing with an actual program or simulation is actually a very interesting one in this case. A curious feature of Martin’s proof is that, at the end of the day, it gives an algorithm to simulate QMA(2) protocols, but it does so in an extremely non-explicit way—basically by chaining together a sequence of reductions, rather than by directly telling you how you’d program your computer to do the simulation. If there were a bug, then possibly a good way to find it would be to unravel the reduction sequence into an actual algorithm. Actually implementing the algorithm might be overkill, though, particularly since the polynomial blowups would be quite large, and might make it almost impossible to notice the difference between exponential time and doubly-exponential time in any simulations that we could feasibly do.
Comment #27 November 2nd, 2015 at 11:25 am
Douglas #20 and Sniffnoy #22,
Ok. Yeah, I’m convinced that’s a bad heuristic which I shouldn’t use, and certainly not in this case.
Jay #24,
Douglas’s example of OP^1 is a good example https://en.wikipedia.org/wiki/Cayley_plane . I was actually thinking of the connnection between the octonions and Spin(8), but thinking about that more, I’m not actually sure that being alternative is at all important there.
Comment #28 November 2nd, 2015 at 1:01 pm
Joshua #27,
Thanks. Would you say this mathematical operation looks like measuring some octonionic state by an apparatus itself an octonionic state, or it’s too far-fetched?
Comment #29 November 2nd, 2015 at 2:33 pm
joe #18: thank you very much: this is really what I was looking for!
Comment #30 November 2nd, 2015 at 6:05 pm
Jay #28,
I’m no sure what you mean. What mathematical operation are you referring to?
Comment #31 November 2nd, 2015 at 7:43 pm
Scott #23: OK, I guess I’ll have to take a look at those to get a better sense of it!
Comment #32 November 2nd, 2015 at 7:48 pm
More octonion nitpicking: The Cayley plane is OP^2, not just OP^1, that would really be terrible if you could only get OP^1.
(Its existence can kind of be attributed to alternativity — it exists because of being able to divide, i.e. the loop property, and getting that from inverses uses alternativity. Whereas if you go on to sedenions then you have useless “inverses” that don’t actually let you divide.)
Comment #33 November 2nd, 2015 at 11:52 pm
Scott #8:
I totally admire your gumption in engaging and debating all comers, on topics technical and otherwise, on top of a very demanding job. The physical and emotional energy required is enormous. There can’t be many people in the world taking on a task like this.
So hang in there and keep up the good work!
Comment #34 November 3rd, 2015 at 11:11 am
I’m fairly sure the Sedonions were the bad guys in a 1970’s era Dr Who story (though it could have been their friends, the Sedonians).
Comment #35 November 3rd, 2015 at 12:29 pm
I was really confused when I wrote that parenthetical. But OP¹ is not a triviality. If you think of it as just the one-point compactification of O, that is a triviality. But if you think of it as lines in O², so it has a bundle of lines, that’s a significant structure.
Comment #36 November 3rd, 2015 at 12:57 pm
My answer: Essentially every topic in both quantum physics and quantum computation/information has the property that anything that you could with real or quaternionic amplitudes can be co-opted in one way or another by formalism with complex amplitudes. The essential point is that the norm squared of an amplitude is a probability. After that, everything works better with complex amplitudes simply because the complex numbers are both commutative and algebraically closed.
This point is woven into linear algebra itself. Do you ever wonder why linear algebra is largely taught over the complex numbers? There is a notion of quaternionic linear algebra, so why isn’t it usually taught? The answer is that quaternionic linear algebra reduces to a special case of complex linear algebra. Real and complex linear algebra also reduce to special cases of each other, but in the end the version with complex numbers is just nicer because they are algebraically closed. (Since they are simpler for many purposes, I think that they should have been called the “complete” numbers rather than the complex numbers.)
There are some questions in mathematics and even in quantum physics that are more nicely stated in terms of quaternions than complex numbers. But it’s not that many, and even then, notational standardization based on complex numbers has its advantages.
Comment #37 November 3rd, 2015 at 1:08 pm
I’ve heard about this question from time to time from Rena. Apparently the answer is that gallium arsenide is historically the one major, credible alternative to silicon. Doped semiconductor transistors clobber everything else for intrinsic reasons; in a nutshell, that you get an overwhelming combination advantage of speed, reliability, miniaturization, and scalability. (Some of the hyped alternatives that show up in the press from time to time don’t even have voltage gain and thus aren’t yet viable; and have other practical disadvantages.) In fact, the genesis of Moore’s Law is that people saw coming that once you have semiconductor transistors, you don’t have to invent anything fundamentally new for a long time.
So, if it’s going to be a semiconductor, which one? It would be coincidental for there to be more than a few “best” choices. If there is more than one, then yes, trillions of dollars of prior investment could make a difference. It is possible, albeit far from certain, that if humanity had standardized around gallium arsenide, then we would all have been better off for it.
Around the corner you have graphene, which in some key respects would be superior to both silicon and gallium arsenide. However, as a VLSI technology, it hasn’t really fully been invented yet.
Comment #38 November 3rd, 2015 at 1:16 pm
It is potentially like the difference between IP, interactive proof, and MIP, multiple interactive provers. It is believable, and known in the case of IP vs MIP, that you might learn more by interrogating two witnesses separately, even if both of them want to convince you of the same thing, than by interrogating just one witness. It’s also intuitive that two witnesses interrogated together are equivalent to just one witness.
So, QMA vs QMA(2) is somewhat similar, except with interactive proof replaced by quantum state and non-communication between provers replaced by non-entanglement of quantum proofs.
Comment #39 November 3rd, 2015 at 2:05 pm
Greg #38: Yes, that’s a very good analogy (one that’s made particularly explicit in the paper by Russell Impagliazzo, Dana Moshkovitz, and myself).
The other thing you can do is just look at the protocols we designed, and see how they involve learning one thing by measuring one state and then cross-checking it by measuring a second copy of the state.
The one point that’s subtle to explain, is where exactly those protocols break down if the two states can be entangled. The easiest two things to say are that, at any rate,
(1) it’s a-priori plausible that such protocols would break down if the two states were entangled, and
(2) we know that they somehow have to break down in that case, because if they didn’t, then 3SAT would be solvable in subexponential time!
Comment #40 November 5th, 2015 at 10:49 am
Joshua #30
I’m not sure 🙂
Let’s put it differently: it seems clear that when you, Greg, sniffoy and Douglas talk about the use of these numbers, most of the focus is on mathematics. On this topics Greg #36 is crystal clear on why complex numbers outperforms quaternions, octonions, and friends. (Thanks for the cues!)
Now, my question was more about physics:
1) in some situation quantum mechanics is odd. Let’s assume no noise, two observers A and B, and some superposed quantum state S. A measures S at time 1, then B measure A at time 2. According to A, S was measured at time 1. According to B, no he was still superposed until time 2.
2) octonions are non associative, e.g. (SA)B is not the same as S(AB).
1+2 => maybe what looks like a bug for a mathematician, could be considsered a feature in order to describe some physical situation?
Comment #41 November 5th, 2015 at 3:36 pm
Jay #40,
I’m not where you are going. That disagreement doesn’t seem at all akin to operations being non-associative. Possibly someone who knows more about the physics end can comment.
Comment #42 November 5th, 2015 at 4:15 pm
Re: Greg #36, Scott #16, Jay #13,
Scott’s point that “the situation is less obvious for classes like QMA(2), which involve stipulating that states are separable!” has some force here because it’s not all that clear how to define composite quaternionic systems. One can embed quaternionic systems in complex ones, though, and if one does things that way then one can come up with a good notion of a composite of two quaternionic systems—but it’s a real system, not another quaternionic ones. Matthew Graydon, Alex Wilce, and I did this from the point of view of mixed-state spaces using Jordan algebras (which allows one to make composites of any combination of real, quaternionic, and complex quantum systems); I think that the simplest category we construct in this way is probably equivalent to an approach by John Baez to the real and quaternionic pure state quantum theories, which considers the systems as complex group representations, but equipped with a real or quaternionic structure, and defines composites of such systems, also ending up with quaternionic times quaternionic being real. Either of these settings would allow one to formally investigate the power of computation in the real,
real and quaternionic combined, or (at least with the Jordan-algebraic approach) real complex and quaternionic combined. I suspect it would be much as Greg says, since everything can be embedded in a higher-dimensional complex space, but it’s not completely obvious. The nature of the failure of local tomography might be relevant. The failure when quaternions are included is worse than in the real case: since in our Jordan-algebraic approach, the mixed-state space of an m quaternionic-dimensional system (i.e. the m by m quaternionic-self-adjoint density matrices), combined with an n quaternionic-dimensional system, is 4mn by 4mn dimensional, this is a more severe failure of local tomography than in the real case. In particular, a pure quaternionic tensor pure quaternionic becomes a mixed rank-4 real state, so that (depending on which operations one defines to be local) one may be able to encode information globally that can be manipulated, but not read out, locally. (I am not sure if bringing in local ancillas might allow readout, though; it’s possible it doesn’t.) E.g. this might affect some of the more cryptographic issues that arise in multiple-prover situations.
Comment #43 November 5th, 2015 at 5:29 pm
Oh yeah, I didn’t even consider that point. Over a noncommutative ring, tensor product just doesn’t work that way.
Comment #44 November 6th, 2015 at 8:52 am
Howard Barnum #42,
Thanks for your comments. Do you know a good online introduction to Jordan algebra?
Comment #45 November 7th, 2015 at 8:02 am
Jay #44 The main Wikipedia article “Jordan algebra” is OK for some of the basics, and has a section on the “formally real” ones which are the relevant ones here, but make sure you check out the article Symmetric Cones (alternatively titled “Euclidean Jordan Algebras”) which has the details relevant for real, complex, and quaternionic quantum theory.
My paper with Alex and Matthew summarizes some of the relevant ones. The early chapters of Faraut and Koranyi’s book Analysis on Symmetric Cones are a good reference; the Wikipedia article on Symmetric Cones seems to be based on it.
For general mathematical interest, Kevin McCrimmon has a nice general intro article on Jordan algebras, but has less of the relevant detail, and goes relatively quickly into Jordan algebras over arbitrary fields.
I suspect quaternionic vs. complex may not make much difference to QMA(2)-type classes, since the peculiarities of quaternionic composites seem more relevant to cryptographic issues of the sort that might arise with multiple provers, than to the complexity of determining separability vs entanglement, which seems most relevant to QMA(2).
Comment #46 November 7th, 2015 at 1:31 pm
Thanks Howard, I’ll try to have “at least some respect for the terms Lie algebra, Lie group, Riemannian, symmetric space, and bounded symmetric domain”. 🙂
Comment #47 December 1st, 2015 at 1:40 pm
As Scott pointed out, one of the exciting implications of QMA(2)⊆EXP would be that the pure state N-representability problem and some of its variants are in EXP. Along these lines is perhaps worth mentioning that we recently proved using rather different methods that the pure state *one-body* quantum marginal problem for a fixed number of parties is in NP∩coNP and that the pure state *one-body* N-representability problem and variants are in NEXP∩coNEXP (these are special cases of arXiv:1511.03675).
Comment #48 December 8th, 2015 at 6:54 am
Any news about the current status of Martin’s proof?
Comment #49 December 8th, 2015 at 8:20 am
Aula #48: I am still working on an updated version of the proof. I think the issue raised can be fixed, but it does require a significant rework of the proof.
Comment #50 January 7th, 2016 at 6:51 pm
[…] paper by Martin Schwarz improves the previous upper bound of . (Update: Per this the result is in doubt.) We can also mention a new paper by Le Gall with Shojo Nakajima that […]
Comment #51 February 12th, 2016 at 11:26 pm
[…] paper by Martin Schwarz improves the previous upper bound of . (Update: Per this the result is in doubt.) We can also mention a new paper by Le Gall with Shojo Nakajima that […]
Comment #52 November 29th, 2016 at 2:25 am
Since all approaches to resolve the problem so far didn’t work, I have withdrawn the paper (which I probably should have done earlier). For a summary of the issue, see the slides from my talk at the recent Workshop on QMA(2) and the Complexity of Entanglement at QuICS/UMD.
Comment #53 November 29th, 2016 at 3:54 pm
(A year ago) I said that QC is about groups. I should have said that all computation is about groups (well, monoids). Computation is about composing subroutines and composition is associative. Composition is the very reason we consider associativity.