Quantum Search Form

Neil B. Lovett, Viv M. Kendon

We show numerically how the quantum walk search algorithm depends on both the spatial dimension and connectivity of the structure being searched. We investigate this using a simple form of tunnelling to interpolate between lattices.

Sergei Kurgalin, Sergei Borzunov

Andris Ambainis, Martins Kokainis, Jevgēnijs Vihrovs

We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity $O(\sqrt{T}\log n)$ where $T=\sum_{i=1}^n t_i^2$ with $t_i$ denoting the time to check the $i$-th item. Our second result is a quantum lower bound of $Ω(\sqrt{T\log T})$. Both the algorithm and the lower bound improve over previously known results by a factor of $\sqrt{\log T}$ but the algorithm is also substantially simpler than the previously known quantum algorithms.

Prateek Tandon, Stanley Lam, Ben Shih +3 more

Lov K. Grover

The quantum search algorithm is a technique for searching N possibilities in only O(N) steps. Although the algorithm itself is widely known, not so well known is the series of steps that first led to it; these are quite different from any of the generally known forms of the algorithm. This paper describes these steps, which start by discretizing Schrödinger’s equation. This paper also provides a self-contained introduction to quantum computing algorithms from a new perspective.

Ashley Montanaro