Exponential algorithmic speedup by quantum walk

Abstract

We construct an oracular (i.e., black box) 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 oracular setting. We then show how this quantum walk can be used to solve our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve this problem with high probability in subexponential time.

24 pages, 7 figures; minor corrections and clarifications

References in corpus (8)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Computation and Decision Trees
• From quantum cellular automata to quantum lattice gases
• An example of the difference between quantum and classical random walks
• Quantum Random Walks Hit Exponentially Faster
• Efficient Quantum Algorithms for Estimating Gauss Sums
• Efficient Quantum Algorithms for Shifted Quadratic Character Problems
• Sharp Quantum vs. Classical Query Complexity Separations

Cited by in corpus (343)

• Quantum algorithms: an overview
• Universal computation by quantum walk
• Quantum walks: a comprehensive review
• Programmable Quantum Simulations of Spin Systems with Trapped Ions
• Hamiltonian Simulation by Qubitization
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Photonic quantum information processing: a review
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Universal quantum computation using the discrete time quantum walk
• A Theory of Trotter Error
• Universal computation by multi-particle quantum walk
• On the relationship between continuous- and discrete-time quantum walk
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Quantum algorithms for algebraic problems
• Random Walks: A Review of Algorithms and Applications
• Hybrid quantum-classical approach to correlated materials
• Decoherence in quantum walks - a review
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum Walks driven by many coins
• Adiabatic Quantum Simulation of Quantum Chemistry
• Faster quantum simulation by randomization
• Verification of quantum computation: An overview of existing approaches
• Limits of quantum speedup in photosynthetic light harvesting
• Quantum random walks with decoherent coins
• ScaffCC: Scalable Compilation and Analysis of Quantum Programs
• Quantum Algorithm for Linear Regression
• Hitting time for quantum walks on the hypercube
• Quipper: A Scalable Quantum Programming Language
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Limit Theorem for Continuous-Time Quantum Walk on the Line
• On the robustness of bucket brigade quantum RAM
• A random walk approach to quantum algorithms
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Automated distribution of quantum circuits via hypergraph partitioning
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Quantum Machine Learning: from physics to software engineering
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
• Simulating sparse Hamiltonians with star decompositions
• Quantum speedup of classical mixing processes
• Hamiltonian Simulation with Optimal Sample Complexity
• An Introduction to Quantum Programming in Quipper
• Prospects of Quantum Computing for Molecular Sciences
• Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target
• Perfect state transfer on distance-regular graphs and association schemes
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Quantum Transport Enhancement by Time-Reversal Symmetry Breaking
• Two-component Dirac-like Hamiltonian for generating quantum walk on one-, two- and three-dimensional lattices
• Quantum Computation and Quantum Information
• Quantum random walks with history dependence
• Bayesian Deep Learning on a Quantum Computer
• Hitting time for the continuous quantum walk
• Demonstration of algorithmic quantum speedup
• Nearly tight Trotterization of interacting electrons
• Quantum linear systems algorithms: a primer
• Laplacian versus Adjacency Matrix in Quantum Walk Search
• Almost uniform sampling via quantum walks
• Quantum interference as a resource for quantum speedup
• Quantum key distribution with quantum walks
• Coined quantum walks on percolation graphs
• Analysis of Absorbing Times of Quantum Walks
• Observation of quasiperiodic dynamics in a one-dimensional quantum walk of single photons in space
• Review on Quantum Walk Computing: Theory, Implementation, and Application
• Centrality measure based on continuous-time quantum walks and experimental realization
• Quantum Walks
• Hybridized Methods for Quantum Simulation in the Interaction Picture
• A quantum walk assisted approximate algorithm for bounded NP optimisation problems
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Quantum walks and Dirac cellular automata on a programmable trapped-ion quantum computer
• Asymptotic entanglement in a two-dimensional quantum walk
• Finding spin-glass ground states using quantum walks
• Variational quantum eigensolvers for sparse Hamiltonians
• Projective simulation with generalization
• Machine learning \& artificial intelligence in the quantum domain
• Complex Quantum Networks: a Topical Review
• Black-box Hamiltonian simulation and unitary implementation
• Formal Verification of Quantum Programs: Theory, Tools and Challenges
• Large scale quantum walks by means of optical fiber cavities
• Quantum Lattice Boltzmann is a quantum walk
• Meta-learning within Projective Simulation
• Propagating Quantum Walks: the origin of interference structures
• Topological bound states of a quantum walk with cold atoms
• Investigation of continuous-time quantum walk by using Krylov subspace-Lanczos algorithm
• Quantum Computation Beyond the Circuit Model
• Experimental simulation of quantum tunneling in small systems
• Trapping photons on the line: controllable dynamics of a quantum walk
• Perfect wave-packet splitting and reconstruction in a one-dimensional lattice
• A quantum-walk-inspired adiabatic algorithm for graph isomorphism
• Continuous-time quantum walks on star graphs
• Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation
• Efficient discrete-time simulations of continuous-time quantum query algorithms
• The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
• Experimental realization of a momentum-space quantum walk
• Decoherence in Discrete Quantum Walks
• Quantum walk speedup of backtracking algorithms
• A brief introduction to quantum algorithms
• Exact gate decompositions for photonic quantum computing
• Spin-1/2 particles moving on a 2D lattice with nearest-neighbor interactions can realize an autonomous quantum computer
• Many-body quantum interference on hypercubes
• Quantum walks and quantum search on graphene lattices
• Universal measurement-based quantum computation in two-dimensional SPT phases
• Enhanced non-Markovian behavior in quantum walks with Markovian disorder
• How fast do quantum walks mix?
• Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
• Variationally Scheduled Quantum Simulation
• Quantum spatial search in two-dimensional waveguide arrays
• A Comparison of Quantum Walk Implementations on NISQ Computers
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Quantum walk algorithm for element distinctness
• Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
• QSWalk: a Mathematica package for quantum stochastic walks on arbitrary graphs
• Quantum walk on circles in phase space
• Quantum walks: decoherence and coin-flipping games
• Limits on Efficient Computation in the Physical World
• Certainty and Uncertainty in Quantum Information Processing
• Supergoop Dynamics
• Disorder-assisted quantum transport in suboptimal decoherence regimes
• Verifiable Quantum Advantage without Structure
• Entanglement Theory and the Quantum Simulation of Many-Body Physics
• Driving quantum systems with repeated conditional measurements
• Quantum walks with a one-dimensional coin
• Complexity Classes of Equivalence Problems Revisited
• Decoherent quantum walks driven by a generic coin operation
• Efficient quantum circuits for continuous-time quantum walks on composite graphs
• From quantum graphs to quantum random walks
• Fast Quantum Methods for Optimization
• Investigation of continuous-time quantum walk on root lattice $A_n$ and honeycomb lattice
• Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk
• Product Formulas for Exponentials of Commutators
• Levinson's theorem for graphs II
• The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processors
• Simulating nonnative cubic interactions on noisy quantum machines
• Weyl, Dirac and Maxwell Quantum Cellular Automata: analitical solutions and phenomenological predictions of the Quantum Cellular Automata Theory of Free Fields
• Discrete-Time Quantum-Walk & Floquet Topological Insulators via Distance-Selective Rydberg-Interaction
• Synthesizing efficient circuits for Hamiltonian simulation
• The Road to Quantum Artificial Intelligence
• Quantum centrality testing on directed graphs via PT-symmetric quantum walks
• Quantum walk transport properties on graphene structures
• Optimal computation with non-unitary quantum walks
• Quantum walks on embedded hypercubes
• Path-integral solution of the one-dimensional Dirac quantum cellular automaton
• Quantum Simulation of Second-Quantized Hamiltonians in Compact Encoding
• A tutorial introduction to quantum circuit programming in dependently typed Proto-Quipper
• Simulation of Quantum Walks and Fast Mixing with Classical Processes
• Singular continuous Cantor spectrum for magnetic quantum walks
• Quantum algorithms for scientific computing
• Properties of Open Quantum Walks on $\mathbb{Z}$
• Percolation induced effects in 2D coined quantum walks: analytic asymptotic solutions
• A note on graphs resistant to quantum uniform mixing
• Quantum walk on distinguishable non-interacting many-particles and indistinguishable two-particle
• Assessment of various Hamiltonian partitionings for the electronic structure problem on a quantum computer using the Trotter approximation
• Discrete Feynman propagator for the Weyl quantum walk in 2+1 dimensions
• Universal quantum walks and adiabatic algorithms by 1D Hamiltonians
• Analysis of quantum Krylov algorithms with errors
• An Effective Hamiltonian Approach to Quantum Random Walk
• Symmetries, graph properties, and quantum speedups
• Quantum walks on a circle with optomechanical systems
• Strategies to simulate dephasing-assisted quantum transport on digital quantum computers
• Vertices cannot be hidden from quantum spatial search for almost all random graphs
• One-Dimensional Lazy Quantum walk in Ternary System
• An efficient quantum algorithm for spectral estimation
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Engineering the Success of Quantum Walk Search Using Weighted Graphs
• Continuous-time quantum walks for MAX-CUT are hot
• Mixing and Decoherence in Continuous-Time Quantum Walks on Cycles
• Isolated Vertices in Continuous-Time Quantum Walks on Dynamic Graphs
• Quantum Walk on the Line through Potential Barriers
• Conditional Probability Distributions of Finite Absorbing Quantum Walks
• On the Need for Large Quantum Depth
• One-Dimensional Quantum Walks with a Position-Dependent Coin
• Anyonic Quantum Walks
• Squash: A Scalable Quantum Mapper Considering Ancilla Sharing
• Improved Upper Bounds for the Hitting Times of Quantum Walks
• Digital quantum simulation framework for energy transport in an open quantum system
• Levinson's theorem for graphs
• The Lackadaisical Quantum Walker is NOT Lazy at all
• Quantum walks and their algorithmic applications
• Quantum Depth in the Random Oracle Model
• QSW_MPI: a framework for parallel simulation of quantum stochastic walks
• Probability distributions for Markov chains based quantum walks
• A novel approach for quantum financial simulation and quantum state preparation
• Quantum walker as a probe for its coin parameter
• Directionally-Unbiased Unitary Optical Devices in Discrete-Time Quantum Walks
• Sensitivity of quantum speedup by quantum annealing to a noisy oracle
• Limitations on the simulation of non-sparse Hamiltonians
• Continuous-Time Classical and Quantum Random Walk on Direct Product of Cayley Graphs
• A note on the classical lower bound for a quantum walk algorithm
• Tree Search and Quantum Computation
• Unveiling and exemplifying the unitary equivalence of discrete time quantum walk models
• New Developments in Quantum Algorithms
• Complete classification of trapping coins for quantum walks on the 2D square lattice
• How to Compute Using Quantum Walks
• Coins Make Quantum Walks Faster
• Simplifying Continuous-Time Quantum Walks on Dynamic Graphs
• Asymptotic entanglement in the discrete-time quantum walk
• Localization of discrete time quantum walks on the glued trees
• Quantum Simulation of a Quantum Stochastic Walk
• Quantum-walk search in motion
• Applications of the Adversary Method in Quantum Query Algorithms
• Quantum algorithm for estimating volumes of convex bodies
• Quipper: Concrete Resource Estimation in Quantum Algorithms
• Quantum walk, entanglement and thermodynamic laws
• Reachability Analysis of Quantum Markov Decision Processes
• Quantum Algorithms for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems
• An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation
• Grover Walks on a Line with Absorbing Boundaries
• Discrete time Dirac quantum walk in 3+1 dimensions
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
• Mixing in Continuous Quantum Walks on Graphs
• Quantum computation and the evaluation of tensor networks
• A Note on Oracle Separations for BQP
• An HHL-Based Algorithm for Computing Hitting Probabilities of Quantum Random Walks
• Quantum walks on directed graphs
• Quantum Cellular Automata from Lattice Field Theories
• Symmetry of distribution for the one-dimensional Hadamard walk
• On Quantum Cellular Automata
• Adjustable self-loop on discrete-time quantum walk and its application in spatial search
• Quantum smoothed particle hydrodynamics algorithm inspired by quantum walks
• Grover Speedup from Many Forms of the Zeno Effect
• Identifying network topologies via quantum walk distributions
• On state transfer in Cayley graphs for abelian groups
• Role of symmetry in quantum search via continuous-time quantum walk
• Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
• Experimental pairwise entanglement estimation for an N-qubit system :A machine learning approach for programming quantum hardware
• Central limit theorems for open quantum random walks on the crystal lattices
• Search of clustered marked states with lackadaisical quantum walks
• Quantum Walk Search through Potential Barriers
• Quantum Snake Walk on Graphs
• Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
• Limit properties of global interaction stochastic quantum walks on directed graphs
• Limit theorems and absorption problems for quantum random walks in one dimension
• History Dependent Quantum Random Walks as Quantum Lattice Gas Automata
• Universal Mixing of Quantum Walk on Graphs
• How to Compile Some NAND Formula Evaluators
• Taming Quantum Time Complexity
• Approximating Hamiltonian dynamics with the Nyström method
• SQUWALS: A Szegedy QUantum WALks Simulator
• Search by quantum walks on two-dimensional grid without amplitude amplification
• Open system approach to Neutrino oscillations in a quantum walk framework
• A framework for optimal quantum spatial search using alternating phase-walks
• A Complete Characterization of Pretty Good State Transfer on Paths
• Experimental realization of universal quantum gates and six-qubit entangled state using photonic quantum walk
• Transfiguration of Quantum Walks on a line
• Improving the query complexity of quantum spatial search in two dimensions
• Graphs of unitary matrices
• Quantum walks on embedded hypercubes: Nonsymmetric and nonlocal cases
• Where to quantum walk
• From open quantum walks to unitary quantum walks
• Induced on-demand revival in coined quantum walks on infinite $d$-dimensional lattices
• Path-sum solution of the Weyl Quantum Walk in 3+1 dimensions
• GPGPU based simulations for one and two dimensional quantum walks
• The 7 faces of quantum NP
• Estimation of one-dimensional discrete-time quantum walk parameters by using machine learning algorithms
• Practical implementation of a quantum backtracking algorithm
• Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
• Quantum Computing's Classical Problem, Classical Computing's Quantum Problem
• Can graph properties have exponential quantum speedup?
• Hitting statistics from quantum jumps
• Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
• Two-Particle Scattering on Non-Translation Invariant Line Lattices
• Quantum Cellular Automaton Model for the Generalized Dirac Equation
• Coherence as resource in scattering quantum walk search on complete graph
• Exponential speedups for quantum walks in random hierarchical graphs
• Quantum Stochastic Walk Models for Quantum State Discrimination
• Correlation effects in a discrete quantum random walk
• How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem
• Enhancing quantum state transfer efficiency in binary-tree spin networks by partially collapsing measurements
• Symmetry in quantum walks
• Revivals in One-dimensional Quantum Walks with a Time and Spin-dependent Phase Shift
• Entanglement and its Role in Shor's Algorithm
• Entanglement for discrete-time quantum walks on the line
• Unbounded quantum-classical separation in sample complexity for sphere center finding
• Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
• Optimizing Quantum Walk Search on a Reduced Uniform Complete Multi-Partite Graph
• Perfect State Transfer in Laplacian Quantum Walk
• Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Quantum walk in symmetric Cayley graph over ${\mathbb{Z}}_2^n$
• Quantum evolution kernel : Machine learning on graphs with programmable arrays of qubits
• Reductions in finite-dimensional quantum mechanics: from symmetries to operator algebras and beyond
• A Critical and Moving-Forward View on Quantum Image Processing
• Limit Theorems for the Discrete-Time Quantum Walk on a Graph with Joined Half Lines
• How symmetric is too symmetric for large quantum speedups?
• Perfect state transfer, graph products and equitable partitions
• Exact Quantum Algorithms for the Leader Election Problem
• Investigation of Continuous-Time Quantum Walk Via Spectral Distribution Associated with Adjacency Matrix
• Estimating mixing properties of local Hamiltonian dynamics and continuous quantum random walks is PSPACE-hard
• Two-Dimensional Quantum Walk of Correlated Photons
• Quantum walk mixing is faster than classical on periodic lattices
• Classical and Quantum Random Walks to Identify Leaders in Criminal Networks
• Source Independent Quantum Walk Random Number Generation
• Spin-Boson Model to Demonstrate Quantum Tunneling in Biomolecules using IBM Quantum Computer
• Two-dimensional quantum central limit theorem by quantum walks
• Quantum Algorithms and Covering Spaces
• Mixing of Quantum Walks on Generalized Hypercubes
• Searching via nonlinear quantum walk on the 2D-grid
• Spectral analysis of discrete-time quantum walks in the quarter plane
• Perfect state transfer on quotient graphs
• Continuous-time quantum walks on semi-regular spidernet graphs via quantum probability theory
• Quantum Algorithm for Commutativity Testing of a Matrix Set
• Quantum Fractional Revival on Graphs
• Numerical Solutions of the spectral problem for arbitrary self-adjoint extensions of the 1D Schroedinger equation
• Impact of Bivariate Gaussian Potentials on Quantum Walks for Spatial Search
• Conserved Quantities in Linear and Nonlinear Quantum Search
• A Lattice Problem in Quantum NP
• Using Quantum Computers to Learn Physics
• Temporal Fluctuations of Continuous-Time Quantum Random Walks on Circles
• Spatial search using the discrete time quantum walk
• Anderson localization for electric quantum walks and skew-shift CMV matrices
• Implementing Quantum Gates Using Length-3 Dynamic Quantum Walks
• Perfect State Transfer in Weighted Cubelike Graphs
• Photon-Number Conserved Universal Quantum Logic Employing Continuous-Time Quantum Walk on Dual-Rail Qubit Arrays
• Two-particle scattering on general graphs
• Quantum Stochastic Walks for Portfolio Optimization: Theory and Implementation on Financial Networks
• Exceptional configurations of quantum walks with Grover's coin
• Quantum Imaginary-Time Evolution with Polynomial Resources in Evolution Time
• Characterization of anomalous diffusion in one-dimensional quantum walks
• Equivalent Laplacian and Adjacency Quantum Walks on Irregular Graphs
• Quantum Search of Spatial Regions
• Continuous-time quantum walks on the symmetric group
• Low Rank Approximation in Simulations of Quantum Algorithms
• Quantum Algorithm For Solving Nonlinear Algebraic Equations
• Projection Theorem for Discrete-Time Quantum Walks
• Quantum Walks on Necklaces and Mixing
• Quantum walks advantage on the dihedral group for uniform sampling problem
• Reversion of Quantum Walks via interventions on coin space
• Partition of graphs and quantum walk based search algorithms
• Quantum walks under superposition of causal order
• Response to glassy disorder in coin on spread of quantum walker
• Asymptotic analysis of the one-dimensional quantum walks by the Tsallis and Rényi entropies
• Faster Search of Clustered Marked States with Lackadaisical Quantum Walks
• Quantum walk on a comb with infinite teeth
• Continuous-time quantum walks on ultrametric spaces
• Quantum Walks, Feynman Propagators and Graph Topology on an IBM Quantum Computer
• Hierarchical System Mapping for Large-Scale Fault-Tolerant Quantum Computing
• Non-uniform mixing of quantum walk on cycles
• Graph identification by quantum walks
• Mixing of Quantum Walk on Circulant Bunkbeds
• A Novel Clustering Algorithm Based on Quantum Random Walk
• Perfect edge state transfer on cubelike graphs
• Uniform mixing on integral abelian Cayley graph
• Quantum walks: a Markovian perspective