Transcript The Learnability of Quantum States

Quantum Double Feature

The Learnability of
Quantum States

Quantum Software
Copy-Protection
Scott Aaronson (MIT)
Starting Point For This Work: A Practical
Problem In Experimental Physics (!)
(well, actually the starting point was whether BQP/qpoly  QMA/poly
… but let’s say it was experimental physics)
We have an unknown quantum state  (possibly
involving many entangled particles)
We can reliably produce as many copies of  as we
want, and measure each copy in a different basis
Our goal is to learn an (approximate) classical
description of 
The physicists call this quantum state tomography.
There are whole books, conferences, etc. about it
But there’s a problem…
The number of measurements needed grows
exponentially with the number of particles
(Indeed, even just writing down the state takes exponentially many bits)
Even the physicists know this is a problem
Current record: Tomography of an 8-qubit state
[Häffner et al., Nature, 2005]
Required 656,000 measurements, each repeated
100 times
So, can a generic state of 10,000 particles never be
“learned” within the lifetime of the universe?
(One can hear the QC skeptics crowing: “It’s just like how we said!”)
A completely irrelevant detour into
quantum coding lower bounds
Berkeley. 1999. Ambainis, Nayak, Ta-Shma, and
Vazirani want to encode a classical string x1…xn into a
quantum state | with o(n) qubits, such that by
measuring | in an appropriate basis, you can recover
any bit xi of your choice
They prove this is impossible: “quantum random
access codes” do no better than classical codes
Upshot: An n-qubit state has ~2n degrees of freedom,
but only ~n “independent and reliably-measurable”
degrees of freedom
All I did: turned Ambainis et al.’s
qulemon into qulemonade
Suppose we have a probability distribution D over twooutcome measurements, and we only care about
(approximately) predicting the outcomes of most
measurements drawn from D
We can do that, with high probability, using a number
of sample measurements from D that increases only
linearly with the number of qubits
The Quantum Occam’s
Razor Theorem
Let  be an n-qubit mixed state. Let D be a distribution
over two-outcome measurements. Suppose we draw
Result says nothing about the
m measurements E1,…,Em independently from D, and
computational complexity of preparing
then output a “hypothesis state”  such that
a hypothesis state that agrees with
|Tr(Ei)-Tr(Ei)|≤ for all i. Then provided /10 and
measurement results
 1  n
1
1 
m   2 2  2 2 log  log  ,
I can make
 
 and  and
 
  the dependence
we’ll have more reasonable, at the cost of
replacing n by n log2n
Pr  TrE   TrE      1  
ED
with probability at least 1- over E1,…,Em
Proof Idea
Interpret Ambainis et al.’s result as proving an O(n)
upper bound on the fat-shattering dimension of
n-qubit quantum states, considered as a concept
class
Use results from computational learning theory
(e.g. [Bartlett-Long 95]), which say that every
concept class has sample complexity linear in its
fat-shattering dimension
Simple Application to Communication Complexity
x
y
Alice
Bob
f(x,y)
f: Boolean function mapping Alice’s N-bit string x and
Bob’s M-bit string y to a binary output
D1(f), R1(f), Q1(f): Deterministic, randomized, and
quantum one-way communication complexities of f
How much can quantum communication save?
In 2004 I showed that for all f (partial or total),
D1(f)=O(M Q1(f)logQ1(f))
Theorem: R1(f)=O(M Q1(f))
for all f, partial or total
Proof: Fix Alice’s input x
By Yao’s minimax principle, Alice can consider a worstcase distribution D over Bob’s input y
Alice’s classical message will consist of y1,…,yT drawn
from D, together with f(x,y1),…,f(x,yT), where T=(Q1(f))
Bob searches for a quantum message  that yields the
right answers on y1,…,yT
By the learning theorem, with high probability such a 
yields the right answers on most y drawn from D
Another cute application
You buy a state | at the quantum software store
The vendor says, “just feed | to your quantum
computer as advice, and it’ll be deciding f in no
time!”
But you don’t trust | to work as expected
Theorem: For any distribution D over inputs, there’s
a small (poly-size) set of “test inputs” x1,…,xt, such
that if you try | on the test inputs and it works, then
whp it will also work on most inputs drawn from D
Quantum Double Feature

The Learnability of
Quantum States

Quantum Software
Copy-Protection
Scott Aaronson (MIT)
Classically: Giving someone a program that they can
use but not copy is fundamentally impossible
(tell that to Sony/BMG…)
Quantumly: Well, it’s called the “No-Cloning Theorem”
for a reason…
Question: Given a Boolean function f:{0,1}n{0,1},
can you give your customers a state |f that lets them
evaluate f, but doesn’t let them prepare more states
from which f can be evaluated?
“Can they use the state more than once?”
Answer: Sure, without loss of generality
Note: We’re going to have to make computational
assumptions
Example where quantum copy-protection
seems possible
Consider the class of point functions: fs(x)=1 if x=s,
fs(x)=0
otherwiseThis scheme is provably secure
Theorem:
under
assumption such
that itthat
can’t
be Choose
broken.
Encode
s bythe
a permutation
2=e.
1,…,k uniformly at random. Then give your customers
(Assumption
is related to, but stronger than, the
the following
state:
hardness of the Hidden Subgroup Problem over Sn)
 
 1   1
2

 k   k
2
Given any permutation ’, I claim one can use | to test
whether ’= with error probability 2-k
On the other hand, | doesn’t seem useful for preparing
additional states with the same property
Example where quantum copyprotection is not possible
Let G be a finite group, for which we can efficiently
prepare |G (a uniform superposition over the elements)
Let H be a subgroup with |H|  |G|/polylog|G|
Given |H, Watrous showed we can efficiently decide
membership in H
Check whether |H and |Hx are equal or orthogonal
Furthermore: given a program to decide membership in H,
we can efficiently prepare |H
First prepare |G, then postselect on membership in H
Conclusion: Any program to decide membership in H can
be pirated
But apparently, only by a “fully quantum pirate”
Speculation: Every class of functions can be
quantumly copy-protected, except the ones that
can’t for trivial reasons
(i.e., the ones that are “quantumly learnable from inputs and outputs”)
Main Result [A. 2034]: There exists a “quantum
oracle” relative to which this speculation is correct
Thus, even if it isn’t, we won’t be able to prove that
by any “quantumly relativizing technique”
Second application of my proof techniques
[Mosca-Stebila]: Provably unforgeable quantum
money
(Provided there’s a quantum oracle at the cash register)
Handwaving Proof Idea
For each circuit C, choose a “meaningless quantum
label” |C uniformly at random
Our quantum oracle will map |C|x|0 to |C|x|C(x)
(and also |C|0 to |C|C)
Intuitively, then, having |C is “just the same as” having
a black box for C
Goal: Show that if C is not learnable, then |C can’t be
pirated
To prove this, we need to construct a simulator, which
takes any quantum algorithm that pirates |C, and
converts it into an algorithm that learns C
Ingredient #1 in the simulator
construction: a “Complexity-Theoretic
No-Cloning Theorem”
Theorem: Suppose a quantum algorithm is given an nqubit state |, and can also access a quantum oracle U
that “recognizes” | (i.e., maps | to -| and every |
with |=0 to itself). Then the algorithm still needs
(2n/2) queries to U to prepare the state || or
anything close to it
Note: Contains both the No-Cloning Theorem and the
optimality of Grover search as special cases
Proof Idea: Generalization of Ambainis’s adversary
method
Ingredient #2: Pseudorandom States
p 
1
2
n
 1
 
p0  x 
x
xGF 2 n
where p is a degree-d univariate polynomial over GF(2n)
for some d=poly(n), and p0(x) is the “leading bit” of p(x)
Clearly the |p’s can be prepared in polynomial time
Lemma: If p is chosen uniformly at random, then |p
“looks like” a completely random n-qubit state
- Even if we get polynomially many copies of |p
- Even if we query the quantum oracle, which depends on |p
So the simulator can use |p’s in place of |C’s

Future Directions

Computationally-efficient learning algorithms
Efficient algorithm to reconstruct an unknown “stabilizer
state” after O(n) n-qubit measurements: [A., Gottesman],
in pre-preparation
Experimental implementation!
Simulation of “pretty-good tomography” in MATLAB: [A.,
Dechter], in progress
Quantum copy-protection: get rid of the oracle!