TY - GEN
T1 - Quantum search of spatial regions
AU - Aaronson, Scott
AU - Ambainis, Andris
PY - 2003
Y1 - 2003
N2 - Can Grover's quantum search algorithm speed up search of a physical region-for example a 2-D grid of size √n × √n? The problem is that √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(√n) for d > 3, or O(√n log3 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 on O(√n)-qubit communication protocol for the disjointness problem, which improves an upper bound of Høyer and de Wolf and matches a lower bound of Razborov.
AB - Can Grover's quantum search algorithm speed up search of a physical region-for example a 2-D grid of size √n × √n? The problem is that √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(√n) for d > 3, or O(√n log3 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 on O(√n)-qubit communication protocol for the disjointness problem, which improves an upper bound of Høyer and de Wolf and matches a lower bound of Razborov.
UR - https://www.scopus.com/pages/publications/0344009617
M3 - Conference paper
AN - SCOPUS:0344009617
SN - 0769520405
T3 - Annual Symposium on Foundations of Computer Science - Proceedings
SP - 200
EP - 209
BT - Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003
PB - IEEE Computer Society
T2 - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003
Y2 - 11 October 2003 through 14 October 2003
ER -