Transcript Multilinear Formulas and Skepticism of Quantum Computing


Multilinear Formulas and
Skepticism of Quantum
Computing

/
2
Scott Aaronson, UC Berkeley
http://www.cs.berkeley.edu/~aaronson
Outline
(1)
(2)
(3)
(4)
Four objections to quantum computing
Sure/Shor separators
Tree states
Result: QECC states require n(log n)
additions and tensor products
(5) Experimental (!) proposal
(6) Conclusions and open problems
Four Objections
Theoretical
Practical
Physical
(A): QC’s can’t
be built for
fundamental
reason
(B): QC’s can’t
be built for
engineering
reasons
Algorithmic
(C): Speedup
is of limited
theoretical
interest
(D): Speedup
is of limited
practical value
(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
(1) Continuity in amplitudes more benign than in
measurable quantities—should we dismiss
classical probabilities of order 10-1000?
(2) How do we know QM’s successor won’t lift us to
PSPACE, rather than knock us down to BPP?
(3) 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?
(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)
Alternatives to QM
Roger Penrose
Gerard ‘t Hooft
(+ King of Sweden)
Stephen Wolfram
Exactly what property separates
the Sure States we know we can
create, from the Shor States that
suffice for factoring?
DIVIDING LINE
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
AmpP
Classes
of Pure
States
 H
n
2
Circuit
Tree
P
TSH
OTree
Vidal
MOTree
2
2
1
1
Classical
Tree size TS(|) = minimum number of unboundedfanin + and  gates, |0’s, and |1’s needed in a tree
representing |. Constants are free. Permutation
order of qubits is irrelevant.


Example:   00  2 01  10  11 / 7 
+
2
7

3
7

1
2
|01
+
1
2
|11

1
2
|02
+
1
2
|12
|01
|12
 TS  
  11
n


H
2 n 1 such that
Tree States: Families  n
TS(|n)p(n) for some polynomial p
Will abuse and refer to individual states
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?
Example Tree State
Pn
Pn
0
Pn1
Pn i
i
= equal superposition over n-bit strings of parity i




1

Pn / 2 0  Pn / 2 0  Pn / 21  Pn / 21
2
1

Pn / 2 0  Pn / 21  Pn / 21  Pn / 2 0
2

 TS Pn i

n
n


1  0 1 
i 0  1 
i





1

TS
P




 
n

2 
2 
2  


 O  n2 
  O n
Multilinear Formulas
Trees involving +,, x1,…,xn, and complex
constants, such that every vertex computes a
multilinear polynomial (no xi multiplied by itself)
Given f : 0,1  , let MFS(f) be minimum
number of vertices in multilinear formula for f
n
+
Theorem: If

 

then
x1
x2
-3i
x1
TS  

x0,1
f  x  x ,
n
    MFS  f  
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
  H2n 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
 0 0
n
 1 U V 0
1
 0      

n
 0 0
n
 0 U V 0
1
n
Add OR of 2nd register to 1st register
Theorem: If   H2n is chosen uniformly under
the Haar measure, then with 1-o(1) probability, no
state | with TS(|)=2o(n) satisfies |||215/16
Why It’s Not Obvious:

: TS  
2
o n 

Proof Idea: Use Warren’s Theorem from real
algebraic geometry
H
n
2
TreeBQP
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
Theorem:
TreeBQP    
P
3
P
3
Proof Idea: Guess and verify trees; use GoldwasserSipser approximate counting
Evidence that TreeBQP  BQP?
QECC States
Let C be a coset in
n
2
; then C  1
C
x
xC
Codewords of stabilizer codes (Gottesman, CSS)
Later we’ll add phases to reduce codeword size
Take the following distribution over cosets: choose
1/3), then let
k n
k
u.a.r.
(where
k=n
A Z , b  Z
2
2
C  x  Z : Ax  b
n
2
Result:
Pr TS  C
C
n
 log n
   1
Raz’s Breakthrough
Given coset C, let
 1 if x  C
f  x  
0 otherwise
Need to lower-bound multilinear formula size
MFS(f)
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
Given f : 0,1  , choose 2k input bits u.a.r.
Label them y1,…,yk, z1,…,zk
n
Randomly restrict remaining bits to 0 or 1 u.a.r.
Yields a new function f R  y, z  : 0,1  0,1 
k
k
Let
MR =
fR(y,z)
z{0,1}k
y{0,1}k
Show MR has large rank with high probability over
choice of fR
Intuition: Multilinear formulas can compute
functions with huge rank, i.e.
IP  x, w  x1w1 
 xn wn  mod 2
But once we restrict everything except y1,…,yk,
z1,…,zk, with high probability rank becomes small
 x1 x2
w w
2
 1
x3
x4
x5
x6
x7
w3
w4
w5
w6
w7
x8   y2


w8   0
1
z1
1 1 1
z3
y3 0 1 y1
0 z2 
0 1 
Theorem (Raz):
Pr  rank  M R   c2 k    1  MFS  f   n log n 
Lower Bound for Coset States
0

x
0
1
1
0
0
0
1
0


A
1 0 1 1 0 1 1 1   y1 

 
0 0 0 1 0 1 0 0   y2  1
   b
 y3   1 
1  
   0 
If these two kk matrices are
 z1 
invertible (which they are with
z 
2
2


probability > 0.288 ), then MR is
 z3 
a permutation of the identity
matrix, so rank(MR)=2k
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
Fact: For an NN complex matrix M=(mij),
rank  M   N   mij   ij
2
ij
(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
Superpositions over binary integers in arithmetic
progression: letting w = (2n-a-1)/p,
a p
1 w

a  pi

w i 0
(= 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
• Create a uniform superposition over a
n
“generic” coset of 2 (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?
What’s been done: 5-qubit codeword in liquid NMR
(Knill, Laflamme, Martinez, Negrevergne, quant-ph/0101034)
1  00000  10010  01001  10100  01010  11011  00110  11000
  
4   11101  00011  11110  01111  10001  01100  10111  00101
TS(|)  69



Tree Size Upper Bounds for Coset States
log2(# of nonzero amplitudes)
0
1
n 1
1
3
2
3
7
7
3
4
9
17
10
4
5
11
21
27
13
5
6
13
25
49
33
16
6
7
15
29
57
77
39
19
7
8
17
33
65
121 89
45
8
9
19
37
73
145 185 101 51
9
10
21
41
81
161 305 225 113 57
10
11
23
45
89
177 353 433 249 125 63
11
12
25
49
97
193 385 705 545 273 137 69
12
13
27
53
105 209 417 833 993 593 297 149 75
#
o
f
q
u
b
i
t
s
2
3
4
5
6
7
8
9
10
11
12
“Hardest” cases
(to left, use naïve
strategy; to right,
Fourier strategy)
22
25
28
31
34
37
For Clifford Group States
log2(# of nonzero amplitudes)
0
1
n 1
1
3
2
3
7
11
3
4
9
17
25
4
5
11
21
41
53
5
6
13
25
49
89
6
7
15
29
57
113 153 133
7
8
17
33
65
129 225 233 189
8
9
19
37
73
145 289 369 345 301
9
10
21
41
81
161 321 545 561 537 413
10
11
23
45
89
177 353 705 865 817 793 541
11
12
25
49
97
193 385 769
1281
1313
1265
1177
733
12
13
27
53
105 209 417 833
1665
1985
1889
1841
1689
#
o
f
q
u
b
i
t
s
2
3
4
5
6
7
8
9
10
11
12
85
957
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
Important for
experiments
• 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?
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