Fetching the paper…

Reading the bibliography…

Optimizing the Number of Gates in Quantum Search · Around

2015

Optimizing the Number of Gates in Quantum Search

Arunachalam, Srinivasan, de Wolf, Ronald

Original
PDF
Post on X

Understand

$ $In its usual form, Grover's quantum search algorithm uses $O(\sqrt{N})$ queries and $O(\sqrt{N} \log N)$ other elementary gates to find a solution in an $N$-bit database.

Grover in 2002 showed how to reduce the number of other gates to $O(\sqrt{N}\log\log N)$ for the special case where the database has a unique solution, without significantly increasing the number of queries.
We show how to reduce this further to $O(\sqrt{N}\log^{(r)} N)$ gates for any constant $r$, and sufficiently large $N$.
This means that, on average, the gates between two queries barely touch more than a constant number of the $\log N$ qubits on which the algorithm acts.

Built on

A quantum algorithm for finding the minimum
C. Dürr and P. Høyer · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
Earlier work this paper cites.
Quantum algorithm for the collision problem
G. Brassard, P. Høyer, and A. Tapp · 1997
Earlier work this paper cites.
Quantum vs. classical communication and computation
H. Buhrman, R. Cleve, and A. Wigderson · 1998
Earlier work this paper cites.

Similar

Grover’s quantum searching algorithm is optimal
Ch. Zalka · 1999
Cited alongside, same era.
Quantum amplitude amplification and estimation
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002
Cited alongside, same era.
Trade-offs in the quantum search algorithm
L. K. Grover · 2002
Cited alongside, same era.
Quantum query complexity of some graph problems
C. Dürr, M. Heiligman, P. Høyer, and M. Mhalla · 2004
Cited alongside, same era.

Then

Quantum search of spatial regions
S. Aaronson and A. Ambainis · 2005
Later among the works it cites.
Quantum algorithms for element distinctness
H. Buhrman, Ch. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha, and R. de Wolf · 2005
Later among the works it cites.
Quantum Complexity of Graph and Algebraic Problems
S. Dörn · 2007
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…