Transcript Quantum Search of Spatial Regions

Quantum Search of Spatial Regions
Scott Aaronson (UC Berkeley)
Joint work with Andris Ambainis (U. Latvia)
Grover’s Search Algorithm
Unsorted database
of n items
Goal: Find one
“marked” item
• Classically, (n) queries to database needed
• Grover 1996: O(n) queries quantumly
• BBBV 1996: Grover’s algorithm is optimal
Great for combinatorial search—but
can it help with a physical database?
What even a dumb computer scientist knows:
THE SPEED OF LIGHT IS FINITE
Consider a quantum robot searching a 2D grid:
Robot
n
n
Marked item
We need n Grover iterations, each of which
takes n time, so we’re screwed!
What’s the Model?
• Undirected connected graph G=(V,E)
• Bit xi at each vertex vi
• Goal: Compute some Boolean f(x1…xn){0,1}
• State can have arbitrary workspace z:
| =  i,z |vi,z
• Alternate query transforms |vi,z  (-1)x(i) |vi,z
with ‘local’ unitaries U
What does ‘local’ mean? Depends on your religion
Defining Locality: 3 Choices
(1) Decomposability
(2) Zero pattern of U
respects graph
0
0
0
1
U is a product of commuting
edgewise operations
(3) Zero pattern of
Hamiltonian H
respects graph
U = eiH
H has bounded eigenvalues
1
0
0
0
0
1
0
0
0
0
1
0
(1)  (2),(3)
Upper bounds work for (1)
Lower bounds for (2),(3)
Whether they’re
equivalent is open
We saw Grover search of a 2D grid presented a problem…
So why not pack data in 3 dimensions?
Then the complexity would be n  n1/3 = n5/6
Trouble: Suppose our “hard disk” has mass density 
Once radius exceeds Schwarzschild bound of
(1/), database collapses to form a black hole
Makes things harder to retrieve…
Holographic Principle: Best one can do
asymptotically is store data on a 2D surface,
1.41069 bits/meter2
So Quantum Mechanics and General Relativity
both yield a n lower bound on search
But can we search a 2D region in less than n steps?
Benioff (2001): Guess we can’t…
REVENGE OF COMPUTER SCIENCE
• We can.
• Example: Take a classical subroutine that searches
a square of size n in n steps
Run n copies in superposition and use Grover  O(n3/4)
(n time to move across grid is
needed for subroutine anyway)
By adding more levels of
recursion, can make running
time O(n1/2+)
Can we do better?
Say n?
Amplitude Amplification
Brassard, Høyer, Mosca, Tapp 2002
Theorem: If a quantum algorithm has success
probability p and returns a certificate, then by
invoking it m times, m=O(1/p), we can amplify
success probability to (1-m2p/3)m2p
Diminishing
returns
Success
Probability
Better to keep prob
low & amplify later
# of Iterations
Algorithm for d3 Dimensions
• Assume there’s a unique marked item
• Divide into n1/5 subcubes, each of size n4/5
• Algorithm A:
If n=1, check whether you’re at a marked item
Else pick a random subcube and run A on it
Amplify n1/11 times
Running Time: T(n)  n1/11(T(n4/5)+O(n1/d)) = O(n5/11)
Success Prob: P(n)  (1-)n2/11n-1/5P(n4/5) = (n-1/11)
(we show  is negligible)
Amplify whole algorithm n1/22 times to get
T(n) = O(n1/22n5/11) = O(n),
P(n) = (1)
Summary of Bounds
d3
d=2
Unique marked item
k marked items
(n)
(n / k1/2-1/d)
O(n log2n)
O(n log3n)
Arbitrary graph
O(n logcn)
n 2O(log n)
Arbitrary graph, h
O(h (n/h)1/d logch) n 2O(log n)
possible marked items (h (n/h)1/d)
When d=2, time for Grover search matches radius of grid
An arbitrary graph is d-dimensional if for any vertex v,
number of vertices at distance r from v is (min{rd,n})
When there are h possible marked items with known
locations, the worst case is that they’re evenly scattered
Application: Disjointness
• Problem: Alice has x1…xn{0,1}n, Bob has y1…yn
They want to know if xiyi=1 for some i
• How many qubits must they communicate?
• Buhrman, Cleve, Wigderson 1998: O(n log n)
• Høyer, de Wolf 2002: O(n clog*n)
• Razborov 2002: (n)
Disjointness in O(n) Communication
A
B
State at any time:
 i,z(A),z(B) |vi,zA  |vi,zB
Communicating one of 6 directions takes only 3
qubits
Recent Progress
Childs-Goldstone: Spatial search by quantum walk
O(n5/6) for d=3, O(n log n) for d=4, O(n) for d>4
Running time not competitive with ours in low
dimensions, but less memory needed
Ambainis-Kempe: Discrete walk with 2-bit coin
O(n log n) for d=2, O(n) for d3
Connection to Dirac equation?