Exponential algorithmic speedup by quantum walk

Exponential algorithmic speedup by quantum walk

(25 October 2002) | Andrew M. Childs,1,* Richard Cleve,2,† Enrico Deotto,1,‡ Edward Farhi,1,§ Sam Gutmann,3,¶ and Daniel A. Spielman4,**
The paper presents a quantum algorithm that solves an oracular problem exponentially faster than any classical algorithm. The quantum algorithm is based on a continuous-time quantum walk, which is implemented in a conventional quantum computing paradigm using an oracular setting. The authors construct a family of graphs, specifically modified versions of balanced binary trees, where the quantum walk can efficiently traverse from the entrance to the exit vertex. They prove that no classical algorithm can solve this problem with high probability in subexponential time. The quantum walk is implemented by simulating the Hamiltonian evolution on a quantum computer, using a sequence of unitary operators that act on a few qubits at a time. The paper also includes a detailed analysis of the quantum walk's propagation on a line, providing evidence that it traverses the graph in linear time. Finally, the authors prove an upper bound on the hitting time, showing that the probability of finding the exit vertex is greater than \(\frac{1}{2n}(1 - \epsilon)\) after running the quantum walk for a time polynomial in \(n\).The paper presents a quantum algorithm that solves an oracular problem exponentially faster than any classical algorithm. The quantum algorithm is based on a continuous-time quantum walk, which is implemented in a conventional quantum computing paradigm using an oracular setting. The authors construct a family of graphs, specifically modified versions of balanced binary trees, where the quantum walk can efficiently traverse from the entrance to the exit vertex. They prove that no classical algorithm can solve this problem with high probability in subexponential time. The quantum walk is implemented by simulating the Hamiltonian evolution on a quantum computer, using a sequence of unitary operators that act on a few qubits at a time. The paper also includes a detailed analysis of the quantum walk's propagation on a line, providing evidence that it traverses the graph in linear time. Finally, the authors prove an upper bound on the hitting time, showing that the probability of finding the exit vertex is greater than \(\frac{1}{2n}(1 - \epsilon)\) after running the quantum walk for a time polynomial in \(n\).
Reach us at info@study.space