@inproceedings{4952e1832a524f53ad6f8bb07db07ea8,
title = "Quantum search of spatial regions",
abstract = "Can Grover's quantum search algorithm speed up search of a physical region - for example a 2D grid of size √n x √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 0(√n) for d ≥ 3, or 0(√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 an 0(√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.",
keywords = "Databases, Holography, Hypercubes, Laboratories, Orbital robotics, Physics, Protocols, Robots, Thermodynamics, Upper bound",
author = "S. Aaronson and A. Ambainis",
note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 ; Conference date: 11-10-2003 Through 14-10-2003",
year = "2003",
doi = "10.1109/SFCS.2003.1238194",
language = "English",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "200--209",
booktitle = "Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003",
address = "United States",
}