Report

Are Quantum States Exponentially Long Vectors? Distributions over n-bit strings 2n-bit strings Scott Aaronson (who did and will have an affiliation) (did: IAS will: Waterloo) The Computer Science Picture of Reality + details Quantum computing challenges this picture That’s why everyone should care about it, whether or not quantum factoring machines are ever built As far as I am concern[ed], the QC model consists of exponentially-long vectors (possible configurations) and some “uniform” (or “simple”) operations (computation steps) on such vectors … The key point is that the associated complexity measure postulates that each such operation can be effected at unit cost (or unit time). My main concern is with this postulate. My own intuition is that the cost of such an operation or of maintaining such vectors should be linearly related to the amount of “non-degeneracy” of these vectors, where the “non-degeneracy” may vary from a constant to linear in the length of the vector (depending on the vector). Needless to say, I am not suggesting a concrete definition of “non-degeneracy,” I am merely conjecturing that such exists and that it capture[s] the inherent cost of the computation. —Oded Goldreich My Two-Pronged Response (1) It’s not easy to explain current experiments (let alone future ones!), if you don’t think that quantum states are exponentially long vectors [A. 2004, “Multilinear Formulas and Skepticism of Quantum Computing”] (2) But it’s not that bad [A. 2004, “Limitations of Quantum Advice and One-Way Communication”] Prong (1) Quantum states are exponentially long vectors How Good Is The Evidence for QM? (1) Interference: Stability of e- orbits, double-slit, etc. (2) Entanglement: Bell inequality, GHZ experiments (3) Schrödinger cats: C60 double-slit experiment, superconductivity, quantum Hall effect, etc. C60 Arndt et al., Nature 401:680-682 (1999) Exactly what property separates the Sure States we know we can create, from the Shor States that suffice for factoring? DIVIDING LINE Not precision in amplitudes: 0 1 2 n Not entanglement across hundreds of particles: 0 n 1 n 2 Not a combination of the two: 1 0 1 2 2 n 0 1 2 n Intuition: Once we accept | and | into our set of possible states, we’re almost forced to accept || and |+| as well But we might restrict ourselves to tree states: n-qubit states obtainable from |0 and |1 by a polynomial number of linear combinations and tensor products + 2 7 3 7 1 2 |01 + 1 2 |11 1 2 |02 + 1 2 |12 |01 |12 Definition: The tree size of a pure state | is the minimum number of linear combinations and tensor products in any tree representing | Question: Can we show that quantum states arising in real (or at least doable) experiments have superpolynomial tree size? Observation: If f x x , x0,1n then the tree size of | equals the multilinear formula size of f up to a constant factor If C 1 C Main Result x is a uniform superposition xC over the codewords of a binary linear code, then |C has tree size n(log n), with high probability if the generator matrix is chosen 1/ 3 n uniformly at random from F n 2 • Even to approximate |C takes tree size n(log n) • Can derandomize using Reed-Solomon codes • Yields the first function f:{0,1}n with a superpolynomial gap between formula size and multilinear formula size Conjectures • n(log n) tree size lower bounds can be improved to exponential Can show this under the restriction that linear combinations are “manifestly orthogonal” • States arising in Shor’s algorithm also have superpolynomial tree size Can show this assuming a number-theoretic conjecture: Conjectures (con’t) • 2D and 3D “cluster states” (lattices of spins with pairwise interactions) have large (2(n)?) tree size Would mean that states with enormous tree sizes have already been seen in the lab, if we believe the condensedmatter physicists (e.g. Ghosh et al., “Entangled quantum state of magnetic dipoles,” Nature 425:48-51, 2003) Can show that a 1D cluster state of n spins has tree size O(n4) • If a quantum computer is in a tree state at every time step, then that computer has a nontrivial classical simulation Can show it’s simulable in the third level of PH Prong (2) It’s not that bad Quantum Advice Nielsen & Chuang: “We know that many systems in Nature ‘prefer’ to sit in highly entangled states of many systems; might it be possible to exploit this preference to obtain extra computational power?” BQP/qpoly: Class of languages decidable by polynomial-size, bounded-error quantum circuits, given a polynomial-size quantum advice state |n that depends only on the input length n Obvious Challenge: Prove an oracle separation between BQP/poly and BQP/qpoly Harry Buhrman: Hey Scott—why not try for an unrelativized separation? After all, if quantum states are like 2n-bit classical strings, then maybe BQP/qpoly NEEEEE/poly! Maybe BQP/qpoly even contains NP! Result: Like BPP but with no gap BQP/qpoly PP/poly Corollary: Can’t show BQP/poly BQP/qpoly without also showing PP P/poly Proof based on new communication result: Given f:{0,1}n{0,1}m{0,1} (partial or total), D1(f) = O(m Q1(f) logQ1(f)) D1(f) = deterministic 1-way communication complexity of f Q1(f) = bounded-error quantum 1-way complexity Alice’s Classical Message y1 y2 Bob, if you use the maximally mixed state in place of my quantum message, then y1 is the lexicographically first input for which you’ll output the wrong answer with probability at least 1/3. But if you condition on succeeding on y1, then y2 is the next input for which you’ll output the wrong answer with probability at least 1/3. But if you condition on succeeding on y1 and y2, then y3 is the … Technicality: We assume Alice’s quantum message was boosted, so that the error probability is negligible Claim: Alice only needs to send T=O(Q) inputs y1,…,yT, where Q = size of her quantum message Proof Sketch: Bob succeeds on y1,…,yT simultaneously with probability at most (2/3)T. But we can decompose the Q-qubit maximally mixed state as 1 2 where |1 is i i Q Q 2 i 1 Alice’s “true” quantum message. Therefore Bob also succeeds with probability (1/2Q). BQP/qpoly PP/poly Alice is the “advisor” Bob is the PP algorithm But why can Bob’s procedure be implemented in PP? A. 2005: PostBQP = PP, where PostBQP = BQP with postselected measurement outcomes (The PostBQP PP direction is an easy modification of Adleman et al.’s proof that BQP PP) Remarks • Contrast with PQP/qpoly = Everything, and Raz’s recent result that QIP/qpoly = Everything • Using similar techniques, I get that for every k, there exists a language in PP that does not have quantum circuits of nk, not even with quantum advice • A second limitation of quantum advice (A. 2004): there exists an oracle relative to which NP BQP/qpoly Conjectures • The question of whether classical advice can always replace quantum advice (i.e. BQP/poly = BQP/qpoly) is not independent of ZF set theory • Similarly for whether classical proofs can replace quantum proofs (i.e. QCMA = QMA) • QMA/qpoly PP/poly • Randomized and quantum one-way communication complexities are asymptotically equal for all total Boolean functions f Summary • The state of n particles is an exponentially long vector. Welcome to Quantum World! • But for most purposes, it’s no worse than a probability distribution being an exponentially long vector • If you’re still not happy, suggest a Sure/Shor separator