mlin2

Multilinear Formulas and Skepticism of Quantum Computing: 

Multilinear Formulas and Skepticism of Quantum Computing Scott Aaronson, UC Berkeley http://www.cs.berkeley.edu/~aaronson

Outline: 

Outline Four objections to quantum computing Sure/Shor separators Tree states Result: QECC states require n(log n) additions and tensor products Experimental (!) proposal Conclusions and open problems

Four Objections: 

Four Objections

(A): QC’s can’t be built for fundamental reason—Levin’s arguments : 

(A): QC’s can’t be built for fundamental reason—Levin’s arguments (1) Analogy to unit-cost arithmetic model (2) Error-correction and fault-tolerance address only relative error in amplitudes, not absolute (3) “We have never seen a physical law valid to over a dozen decimals” (4) If a quantum computer failed, we couldn’t measure its state to prove a breakdown of QM—so no Nobel prize “The present attitude is analogous to, say, Maxwell selling the Daemon of his famous thought experiment as a path to cheaper electricity from heat”

Responses : 

Responses Continuity in amplitudes more benign than in measurable quantities—should we dismiss classical probabilities of order 10-1000? How do we know QM’s successor won’t lift us to PSPACE, rather than knock us down to BPP? To falsify QM, would suffice to show QC is in some state far from eiHt|. E.g. Fitch & Cronin won 1980 Physics Nobel “merely” for showing CP symmetry is violated Real Question: How far should we extrapolate from today’s experiments to where QM hasn’t been tested?

How Good Is The Evidence for QM?: 

How Good Is The Evidence for QM? Interference: Stability of e- orbits, double-slit, etc. Entanglement: Bell inequality, GHZ experiments Schrödinger cats: C60 double-slit experiment, superconductivity, quantum Hall effect, etc. C60 Arndt et al., Nature 401:680-682 (1999)

Alternatives to QM: 

Alternatives to QM Roger Penrose Gerard ‘t Hooft (+ King of Sweden) Stephen Wolfram

Slide9: 

My View: Any good argument for why quantum computing is impossible must answer this question—but I haven’t seen any that do What I’ll Do: Initiate a complexity theory of (pure) quantum states, that studies possible Sure/Shor separators Prove a superpolynomial lower bound on “tree size” of states arising in quantum error correction Propose an NMR experiment to create states with large tree size

Classes of Pure States : 

Classes of Pure States

Slide11: 

Tree size TS(|) = minimum number of unbounded-fanin + and  gates, |0’s, and |1’s needed in a tree representing |. Constants are free. Permutation order of qubits is irrelevant. Example:

Slide12: 

Motivation: If we accept | and |, we almost have to accept || and |+|. But can only polynomially many “tensorings” and “summings” take place in the multiverse, because of decoherence? Tree States: Families such that TS(|n)p(n) for some polynomial p Will abuse and refer to individual states

Example Tree State: 

Example Tree State = equal superposition over n-bit strings of parity i

Multilinear Formulas: 

Trees involving +,, x1,…,xn, and complex constants, such that every vertex computes a multilinear polynomial (no xi multiplied by itself) Given let MFS(f) be minimum number of vertices in multilinear formula for f Multilinear Formulas

Depth Reduction: 

Theorem: Any tree state has a tree of polynomial size and logarithmic depth Proof Idea: Follows Brent’s Theorem (1974), that any function with a poly-size arithmetic formula has a formula of polynomial size and logarithmic depth Depth Reduction

Slide16: 

is an orthogonal tree state if it has a polynomial-size tree that only adds orthogonal states Theorem: Any orthogonal tree state can be prepared by a poly-size quantum circuit Proof Idea: If we can prepare | and |, clearly can prepare ||. To prepare |+| where |=0: let U|0n=|, V|0n=|. Then Add OR of 2nd register to 1st register

Slide17: 

Why It’s Not Obvious: Theorem: If is chosen uniformly under the Haar measure, then with 1-o(1) probability, no state | with TS(|)=2o(n) satisfies |||215/16 Proof Idea: Use Warren’s Theorem from real algebraic geometry

TreeBQP: 

Theorem: Proof Idea: Guess and verify trees; use Goldwasser-Sipser approximate counting Evidence that TreeBQP  BQP? Class of problems solvable by a quantum computer whose state at every time is a tree state. (1-qubit intermediate measurements are allowed.) BPP  TreeBQP  BQP TreeBQP

QECC States: 

QECC States Let C be a coset in then Codewords of stabilizer codes (Gottesman, CSS) Later we’ll add phases to reduce codeword size Take the following distribution over cosets: choose u.a.r. (where k=n1/3), then let

Raz’s Breakthrough: 

Raz’s Breakthrough Given coset C, let Need to lower-bound multilinear formula size MFS(f) LOOKS HARD Until June, superpolynomial lower bounds on MFS didn’t exist Raz: n(log n) MFS lower bounds for Permanent and Determinant of nn matrix (Exponential bounds conjectured, but n(log n) is the best Raz’s method can show)

Idea of Raz’s Method: 

Idea of Raz’s Method Given choose 2k input bits u.a.r. Label them y1,…,yk, z1,…,zk Randomly restrict remaining bits to 0 or 1 u.a.r. Yields a new function Let Show MR has large rank with high probability over choice of fR fR(y,z) MR = y{0,1}k z{0,1}k

Slide22: 

Intuition: Multilinear formulas can compute functions with huge rank, i.e. But once we restrict everything except y1,…,yk, z1,…,zk, with high probability rank becomes small Theorem (Raz):

Lower Bound for Coset States: 

Lower Bound for Coset States b x A If these two kk matrices are invertible (which they are with probability > 0.2882), then MR is a permutation of the identity matrix, so rank(MR)=2k

Corollary: 

Corollary First superpolynomial gap between multilinear and general formula size of functions f(x) is trivially NC1—just check whether Ax=b Determinant not known to be NC1—best formulas known are nO(log n) Still open: Is there a polynomial with a poly-size formula but no poly-size multilinear formula?

Inapproximability of Coset States: 

Inapproximability of Coset States Fact: For an NN complex matrix M=(mij), (Follows from Hoffman-Wielandt inequality) Corollary: With (1) probability over coset C, no state | with TS(|)=no(log n) has ||C|20.98

Shor States: 

Shor States Superpositions over binary integers in arithmetic progression: letting w = (2n-a-1)/p, (= 1st register of Shor’s alg after 2nd register is measured) Conjecture: Let S be a set of integers with |S|=32t and |x|exp((log t)c) for all xS and some c>0. Let Sp={x mod p : xS}. For sufficiently large t, if we choose a prime p uniformly at random from [t,5t/4], then |Sp|3t/4 with probability at least 3/4 Theorem: Assuming the conjecture, there exist p,a for which TS(|pZ+a)=n(log n)

Challenge for NMR Experimenters: 

Challenge for NMR Experimenters Create a uniform superposition over a “generic” coset of (n9) or even better, Clifford group state Worthwhile even if you don’t demonstrate error correction We’ll overlook that it’s really (1-10-5)I/512 + 10-5|CC| New test of QM: are all states tree states?

Tree Size Upper Bounds for Coset States: 

Tree Size Upper Bounds for Coset States log2(# of nonzero amplitudes) n # of qubi ts “Hardest” cases (to left, use naïve strategy; to right, Fourier strategy)

For Clifford Group States: 

For Clifford Group States log2(# of nonzero amplitudes) n # of qubi ts

Open Problems: 

Open Problems Exponential tree-size lower bounds Lower bound for Shor states Explicit codes (i.e. Reed-Solomon) Concrete lower bounds for (say) n=9 Extension to mixed states Separate tree states and orthogonal tree states PAC-learn multilinear formulas? TreeBQP=BPP? Non-tree states already created in solid state? Important for experiments

Conclusions: 

Conclusions Complexity theory is relevant for experimental QIP Complexity of quantum states deserves further attention QC skeptics can strengthen their case (and help us) by proposing Sure/Shor separators QC experiments will test quantum mechanics itself in a fundamentally new way