Transcript The Learnability of Quantum States

The Power of Unentanglement
|
Scott Aaronson (MIT)
Salman Beigi (MIT)
Andrew Drucker (MIT)
|
|
Bill Fefferman (Caltech)
Peter Shor (MIT)
“It is not yet entirely clear what advances in
our understanding of quantum computation
and quantum information can be expected
as a result of the study of quantitative
measures of entanglement.”
—Nielsen & Chuang (2000)
In this work, we connect quantum complexity theory to
entanglement theory—ironically, by studying the power
of lack of entanglement!
Previous 3 talks, 3 talks at upcoming FOCS:
Quantum multi-prover interactive proof systems where
provers share entanglement
Not what I’ll be talking about today
Main Results
Proving 3SAT With Õ(n) Qubits
Let  be a 3SAT instance of size n. Someone can prove to
you that  is satisfiable by giving you only O(n polylog n)
qubits—provided you know certain subsets of the qubits are
unentangled with the rest
Proof is nonrelativizing, and requires a tight PCP theorem
Additivity  Amplification and Collapse
Multi-prover quantum MA can be amplified to exponentially
small error, and three or more Merlins can be simulated with
two, assuming the famous Additivity Conjecture from
quantum information theory
QMA: Quantum Merlin-Arthur
[Kitaev and Watrous, 2000]
Class of languages L such that for all inputs x:
• xL  exists a witness | with poly(n) qubits, causing
polytime quantum verifier Arthur to accept w.p.  2/3
• xL  for all witnesses |, Arthur accepts w.p.  1/3
We know a reasonable amount about QMA: it’s
contained in PP, allows amplification, has natural
complete promise problems…
QMA(k)
[Kobayashi, Matsumoto, Yamakami 2003]
Class of languages L such that for all inputs x:
• xL  there exist witnesses |1,…,|k causing
Arthur to accept w.p. 2/3
• xL  for all |1,…,|k, Arthur accepts w.p. 1/3
Classically, this is completely
uninteresting: MA(k)=MA
But quantumly, a single Merlin could cheat by
entangling the k proofs!
Do Multiple Quantum Proofs
Ever Actually Help?
Liu, Christandl, Verstraete: Natural
problem from quantum chemistry,
pure state N-representability, which
is in QMA(2) but not known to be in
QMA
Blier and Tapp (independent of us): 3-COLORING admits
a 2-prover QMA protocol with witnesses of size log(n),
and a (1/n6) probability of catching cheating provers
This work: A protocol for 3SAT with Õ(n) quantum
witnesses of size log(n), and constant soundness
Our Protocol for 3SAT
We’ll work not with 3SAT but with “2-out-of-4-SAT”:
xi + xj + xk + xl = 2 (mod 4)
We need our 2-out-of-4-SAT instance to be balanced
(each variable occurs in O(1) clauses), as well as a
PCP (either satisfiable or -far from satisfiable)
Theorem: We can get all of this using
known classical reductions from 3SAT
(including Dinur’s gap amplification
procedure), incurring a polylog(n)
blowup in the number of variables and
clauses.
So suppose Arthur has done all this, to obtain a 2-outof-4-SAT instance . And suppose Merlin sends him a
log(n)-qubit state of the form
n
1
xi
 1 i
 

n i 1
where x1,…,xn is a claimed satisfying assignment for .
(I.e., a proper state.)
Then Arthur can measure | in a basis corresponding
to the clauses of , obtaining the outcome
1
xi
i   1
xj
j   1 k   1 l
xk
xl
for some clause C=(xi,xj,xk,xl). A further measurement
reveals whether C is satisfied with (1) probability.
Problem: How can Arthur force Merlin to send him a
proper state? (E.g., what if Merlin cheats by putting all
amplitude on a few computational basis states?)
n
Solution: More Merlins!
|
log(n)
1 n
xi
 1 i
 

n i 1
|
log(n)
|
log(n)
The Protocol
With 1/3 prob.
With 1/3 prob.
With 1/3 prob.
Pick a random
|k and do the
Satisfiability Test
described earlier
Pick two random
|k’s and do a
Swap-Test
Do a Uniformity
Test to make
sure the |k’s are
close to proper
states
(Ensures most
|k’s are pretty
much identical)
The Uniformity Test
Pick a random matching M on [n]
Measure each witness | in a basis containing
i  j
2
,
i  j
2
|3-|4
for each (i,j)M.
|8+|10
|2+|9
|8-|10
Since there are n witnesses, by the Birthday Paradox,
with constant probability we’ll see a collision: two
outcomes involving the same edge (i,j).
If both outcomes are |i+|j or both |i-|j, accept.
If one outcome is |i+|j and the other is |i-|j, reject.

Accepts with certainty if the witnesses are
identical and proper
Theorem: Rejects with (1) probability if witnesses are
close to each other but far from proper
Proof: So intuitively obvious, it takes 14 pages to prove
Why doesn’t our protocol work with entangled
witnesses?
Because the Merlins could send a state that passes all
Swap-Tests, yet doesn’t produce collisions
Amplification
For QMA, it’s easy to amplify success probability, even if
Merlin cheats by entangling the witnesses
Witness1
Witness2
Witness3
So then what’s the problem with amplifying QMA(2)?
Merlin1
:
Witness1
Merlin2
:
Witness1
Witness2
Witness3
Uh-oh!
Accept
Witness2
Witness3
“Entanglement Swapping”
Yet it seems possible to defend against this bizarre
behavior…
W1
W2
W3
W4
W5
W6
W7
W1
W2
W3
W4
W5
W6
W7
n100 pairs of witnesses, of which we only measure a
random n
Does any tiny amount of entanglement that’s created
during this protocol “spread itself thinly” across the
registers in a reasonable way?
To answer this question, we need a way to measure
entanglement…
Entanglement of Formation EF(AB)
Intuitively, minimum # of EPR pairs needed to prepare AB
Fun Facts:
• EF can only increase by  2K when we act on a K-qubit
register
Good for us
• If EF(AB)0, then AB is close to a separable state in
trace distance
Good for us




k

A1Ak , B1Bk
Ai , Bi 
Is EF superadditive?  EF 
  EF 

i 1


Shor 2003: Equivalent to proving the “additivity of
quantum channel capacity,” a famous open problem
Assuming the Additivity
Conjecture, we show that…
QMA(2) protocols can be amplified to exponentially
small error
QMA(2)=QMA(k) for all 2kpoly(n) (building on [KMY])
SymQMA(k)=QMA(k)
(SymQMA(k): All k Merlins send the same state)
For every fixed polynomial p, p(n) entanglement
gives the Merlins no extra power to cheat
Upper Bounds for QMA(2)
NEXP
?
EXP
PSPACE
PP
It’s obvious that QMA(2)NEXP.
Embarrassingly, we still don’t have a
better upper bound!
Our Result: QMA(2)PSPACE,
assuming “Strong Amplification” of
QMA(2) protocols
(Amplification that reuses one of the Merlin’s
witnesses over and over)
On the other hand: If amplification
that reuses both witnesses is
possible, then PSPACE=NEXP!
Does QMA(2)=QMA?
Right now, even proving an oracle separation between
them seems way beyond reach!
Conjecture (Watrous): There’s no way to simulate
QMA(2) in QMA by taking an arbitrary polynomial-size
witness, and “disentangling” it to produce an arbitrary
roughly-separable witness
All states
All separable
states
We show: If you want a perfect disentangler, then the
input Hilbert space needs to be infinite-dimensional.
More Open Problems
In our 3SAT protocol, can the assumption of
unentanglement be removed? If so, then we get a
2Õ(n) quantum algorithm for 3SAT!
Conjecture: Our protocol can be modified to
require only two provers sending Õ(n) qubits each
Can we improve on Õ(n), or get evidence against this?
In defining QMA(2), does it matter whether amplitudes are
real or complex?
Are there natural group-theoretic problems in QMA(2)? Does
QMA(2) have natural complete promise problems?
Remove additivity/amplification assumptions!