Quantum Walks Search Spatial

Short answer: Spatial search asks a quantum walk to find a marked node in a graph, a task a classical random walk does slowly. Three papers from 2016 to 2022 show how general the speedup is: the 2016 result shows continuous-time quantum walk search is optimal for almost all graphs, a 2021 paper gives deterministic search on a class of networks, and a 2021 arXiv paper gives an algorithm that finds a marked node in any graph, quadratically faster than classical random walks. These are theoretical algorithm results.

The problem

A 2016 Physical Review Letters paper describes the task as finding a marked node in a graph, solvable by spatial search based on continuous-time quantum walks. A 2021 arXiv paper says the open question had been whether spatial search by continuous-time quantum walk gives a quadratic advantage over classical random walks, and that until then the advantage had been shown only for specific graphs or when a single node was marked.

Optimal for almost all graphs

The 2016 authors note that the algorithm was known to run in optimal time only for a handful of graphs. They prove that for Erdos-Renyi random graphs, with n vertices and each edge present with probability p, search by continuous-time quantum walk is almost surely optimal provided p is at least log^(3/2)(n)/n. They conclude that quantum spatial search is optimal for almost all graphs, meaning the fraction of n-vertex graphs where this holds tends to one asymptotically. The proof shows search is optimal on graphs where the ratio of the second largest to the largest eigenvalue is bounded by a constant below 1. They also extend the result to high-fidelity quantum state transfer and entanglement generation between two arbitrary nodes of a random network of interacting qubits, concluding that tasks designed for structured systems keep their performance in very disordered ones.

Deterministic search with alternating walks

A 2021 Physical Review A paper studies spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. The authors prove that, for a set of optimal walk times and marked-vertex phase shifts, a deterministic algorithm finds the marked vertex with probability 1, improving on the Childs and Goldstone algorithm on the same graphs, which they show can only amplify to 50 percent. The method uses a number of phase shifts of order the square root of N for an N-vertex graph, comparable to Grover search for unstructured search, and they expect it to extend to other graph families.

Any graph, any number of marked nodes

The 2021 arXiv paper provides a new continuous-time quantum walk search algorithm that its authors say resolves the question: it can find a marked node in any graph with any number of marked nodes, in time quadratically faster than classical random walks. The algorithm needs only time evolution under the quantum walk Hamiltonian followed by a projective measurement. A key step is a purely analog procedure that applies an operator of the form e^(-tH^2) to a state by evolving H for time scaling as the square root of t, which quadratically fast-forwards classical random walk dynamics. The authors say the idea may lead to analog algorithms for preparing ground states of Hamiltonians or solving optimisation problems.

What this does not tell you

These are analytical results about idealised quantum walks, with running time counted in the walk model. They say nothing about the cost of building the walk on real hardware.

FAQ

What is spatial search?

Finding a marked node in a graph using a quantum walk.

Is the quantum walk always optimal?

It was known for few graphs, and a 2016 paper proves it for almost all graphs.

Can search be deterministic?

A 2021 paper gives a deterministic version for a class of interdependent networks.

Is there a quadratic speedup in general?

A 2021 arXiv paper reports an algorithm giving it for any graph and any number of marked nodes.

Has this been built?

These papers are theoretical.