Theory of Computing
-------------------
Title : Quantum Search of Spatial Regions
Authors : Scott Aaronson and Andris Ambainis
Volume : 1
Number : 4
Pages : 47-79
URL : https://theoryofcomputing.org/articles/v001a004
Abstract
--------
Can Grover's algorithm speed up search of a physical region---for
example a 2-D grid of size \sqrt{n}\times\sqrt{n}? The problem is
that \sqrt{n} time seems to be needed for each query, just to move
amplitude across the grid. Here we show that this problem can be
surmounted, refuting a claim to the contrary by Benioff. In particular,
we show how to search a d-dimensional hypercube in time O(\sqrt{n})
for d\ge 3, or O(\sqrt{n}\log^{5/2}n) for d=2. More generally, we
introduce a model of quantum query complexity on graphs, motivated
by fundamental physical limits on information storage, particularly
the holographic principle from black hole thermodynamics. Our results
in this model include almost-tight upper and lower bounds for many
search tasks; a generalized algorithm that works for any graph with
good expansion properties, not just hypercubes; and relationships
among several notions of `locality' for unitary matrices acting
on graphs. As an application of our results, we give an
O(\sqrt{n})-qubit communication protocol for the disjointness problem,
which improves an upper bound of Hoyer and de Wolf and matches a lower
bound of Razborov.