Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
arXiv:1603.05423 · doi:10.1103/PhysRevA.93.062313
Abstract
Continuous-time quantum walks and adiabatic quantum evolution are two general techniques for quantum computing, both of which are described by Hamiltonians that govern their evolutions by Schrödinger's equation. In the former, the Hamiltonian is fixed, while in the latter, the Hamiltonian varies with time. As a result, their formulations of Grover's algorithm evolve differently through Hilbert space. We show that this difference is fundamental; they cannot be made to evolve along each other's path without introducing structure more powerful than the standard oracle for unstructured search. For an adiabatic quantum evolution to evolve like the quantum walk search algorithm, it must interpolate between three fixed Hamiltonians, one of which is complex and introduces structure that is stronger than the oracle for unstructured search. Conversely, for a quantum walk to evolve along the path of the adiabatic search algorithm, it must be a chiral quantum walk on a weighted, directed star graph with structure that is also stronger than the oracle for unstructured search. Thus the two techniques, although similar in being described by Hamiltonians that govern their evolution, compute by fundamentally irreconcilable means.
arXiv comment8 pages, 4 figures
References in corpus (26)
- Strengths and Weaknesses of Quantum Computing
- A Quantum Random Walk Search Algorithm
- Spatial search by quantum walk
- Quantum Search by Local Adiabatic Evolution
- Quantum Computation by Adiabatic Evolution
- Universal computation by multi-particle quantum walk
- Quantum Computation
- Connectivity is a Poor Indicator of Fast Quantum Search
- Quantum Adiabatic Evolution Algorithms with Different Paths
- Accuracy vs run time in adiabatic quantum search
- Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
- Quantum Transport Enhancement by Time-Reversal Symmetry Breaking
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Chiral Quantum Walks
- Hamiltonian Oracles
- Quantum circuit implementation of the Hamiltonian versions of Grover's algorithm
- Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
- Quantum Search with General Nonlinearities
- Nonlinear Quantum Search Using the Gross-Pitaevskii Equation
- On the adiabatic condition and the quantum hitting time of Markov chains
- Faster Quantum Walk Search on a Weighted Graph
- Quantum Walk Search with Time-Reversal Symmetry Breaking
- An intuitive Hamiltonian for quantum search
- Probing nonlinear adiabatic paths with a universal integrator
- Nonlinear Quantum Search
- Completeness is Unnecessary for Fast Nonlinear Quantum Search
Cited by in corpus (7)
- Complex Networks from Classical to Quantum
- Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
- An energetic perspective on rapid quenches in quantum annealing
- Non-Markovian channel from the reduced dynamics of coin in quantum walk
- Continuous-time quantum walks in the presence of a quadratic perturbation
- Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
- Robust Diabatic Quantum Search by Landau-Zener-Stückelberg Oscillations