Exponential algorithmic speedup by a quantum walk

2002/09/30 by Andrew M. Childs, Richard Cleve, E. Deotto +4 · 99 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum-Dot Cellular Automata #quant-ph

paper · pdf · doi:10.1145/780542.780552

published as Proc. 35th ACM Symposium on Theory of Computing (STOC 2003), pp. 59-68 · 24 pages, 7 figures; minor corrections and clarifications

arxiv created 2002/10/25 · openalex publication_date 2003/06/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time.

Citations

• Quantum Computation and Decision Trees
• Quantum Complexity Theory
• On the Power of Quantum Computation
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Cited by

• Krylov Polynomials and Quantum Query Complexity
• Exponential Quantum Advantage for Message Complexity in Distributed Algorithms
• A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems
• Quantum walks through generalized graph composition
• QSearchNet: A Quantum Walk Search Framework for Link Prediction
• Iterative quantum algorithms for the minimum vertex cover problem based on continuous-time quantum walks
• Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization
• On the Complexity of Decoded Quantum Interferometry
• Simulating and Learning Quantum Evolution: A CTQW-ML Framework
• A hybrid quantum walk model unifying discrete and continuous quantum walks
• Fast simulation of fermions with reconfigurable qubits
• Weakly-Driven Quantum Walks for Memory-Constrained Pauli Channel Learning
• Quantum Walks for Chemical Reaction Networks
• Quipper: A Scalable Quantum Programming Language
• Graphs of unitary matrices
• A Brief Introduction to Quantum Query Complexity
• Matrix Inversion by Quantum Walk
• Continuous-time quantum walks on the symmetric group
• Forrelation is Extremally Hard
• Probing graph topology from local quantum measurements
• Fourier space readout method for efficiently recovering functions encoded in quantum states
• A note on the classical lower bound for a quantum walk algorithm
• High-dimensional graphs convolution for quantum walks photonic applications
• Entanglement Certification by Measuring Nonlocality
• Two-Dimensional Quantum Walk of Correlated Photons
• Investigation of Continuous-Time Quantum Walk Via Spectral Distribution Associated with Adjacency Matrix
• Quantum Computation Beyond the Circuit Model
• A Novel Clustering Algorithm Based on Quantum Random Walk
• Search by quantum walks on two-dimensional grid without amplitude amplification
• Quipper: Concrete Resource Estimation in Quantum Algorithms
• Quantum Fractional Revival on Graphs
• Quantum Fast-Forwarding: Markov Chains and Graph Property Testing
• Partition of graphs and quantum walk based search algorithms
• Estimating mixing properties of local Hamiltonian dynamics and continuous quantum random walks is PSPACE-hard
• Quantum Search of Spatial Regions
• Lecture Notes on Quantum Algorithms
• Quantum Stochastic Walks for Portfolio Optimization: Theory and Implementation on Financial Networks
• Quantum Imaginary-Time Evolution with Polynomial Resources in Time
• Quantum Search with a Generalized Laplacian
• Deterministic quantum search on all Laplacian integral graphs
• Quantum Walks: First Hitting Times with Weak Measurements
• Search of clustered marked states with lackadaisical quantum walks
• Future of Quantum Computing
• Can graph properties have exponential quantum speedup?
• Quantum Speedups for Testing Similar Means
• Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
• Grover Speedup from Many Forms of the Zeno Effect
• Quantum computation and the evaluation of tensor networks
• Where to quantum walk
• Quantum Algorithms for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems
• Entanglement Theory and the Quantum Simulation of Many-Body Physics
• Time Independence Does Not Limit Information Flow. I. The Free-Particle Case
• A Critical and Moving-Forward View on Quantum Image Processing
• A Lattice Problem in Quantum NP
• Applications of the Adversary Method in Quantum Query Algorithms
• Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
• Symmetry in quantum walks
• How symmetric is too symmetric for large quantum speedups?
• Graph identification by quantum walks
• An HHL-based algorithm for computing hitting probabilities of quantum walks
• Quantum Walks, Feynman Propagators and Graph Topology on an IBM Quantum Computer
• Quantum algorithms: an overview
• A random walk approach to quantum algorithms
• Decoherence in quantum walks – a review
• Optimal computation with non-unitary quantum walks
• Decoherent quantum walks driven by a generic coin operation
• Quantum quincunx for walk on circles in phase space with indirect coin flip
• Quantum Walks: A Markovian Perspective
• Quantum walks with history dependence
• Simulating Sparse Hamiltonians with Star Decompositions
• Efficient Quantum Algorithms for Simulating Sparse Hamiltonians
• Almost uniform sampling via quantum walks
• Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
• The Nature of Computation
• Universal Computation by Quantum Walk
• Path-sum solution of the Weyl quantum walk in 3 + 1 dimensions
• Limits on Efficient Computation in the Physical World
• Experimental pairwise entanglement estimation for an N-qubit system
• Quantum algorithms for path and cycle containment problems
• Tree search and quantum computation
• Isolated vertices in continuous-time quantum walks on dynamic graphs
• Reversion of Quantum Walks via interventions on coin space
• Complete classification of trapping coins for quantum walks on the two-dimensional square lattice
• Perfect State Transfer in Weighted Cubelike Graphs
• Quantum phase discrimination with applications to quantum search on graphs
• Perfect edge state transfer on cubelike graphs
• QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
• Refinement orders for quantum programs
• Comparative Benchmarking of Utility-Scale Quantum Emulators
• Prospects of Quantum Computing for Molecular Sciences
• Sensitivity of quantum speedup by quantum annealing to a noisy oracle
• Probability distributions for Markov chain based quantum walks
• Propagating quantum walks: The origin of interference structures
• Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters
• Limits of quantum speedup in photosynthetic light harvesting
• History dependent quantum random walks as quantum lattice gas automata
• Percolation induced effects in two-dimensional coined quantum walks: analytic asymptotic solutions
• Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems
• Efficient quantum circuits for continuous-time quantum walks on composite graphs
• Richard Cleve [wikipedia]

Related

• A note on the classical lower bound for a quantum walk algorithm
• A Panoply of Quantum Algorithms
• Efficient quantum circuit implementation of quantum walks
• Introduction to Quantum Algorithms
• Quadratic speedup for finding marked vertices by quantum walks