Exponential algorithmic speedup by a quantum walk

DOI10.1145/780542.780552zbMath1192.81059arXivquant-ph/0209131OpenAlexW2009948449WikidataQ55966519 ScholiaQ55966519MaRDI QIDQ3581288

Sam Gutmann, Enrico Deotto, Andrew M. Childs, Edward Farhi, Richard Cleve, Daniel A. Spielman

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/0209131

Mathematics Subject Classification ID

Related Items (only showing first 100 items - show all)

Quantum walk on the line through potential barriers ⋮ Quantum entanglement as a new information processing resource ⋮ Duality quantum computer and the efficient quantum simulations ⋮ Perfect state transfer in Laplacian quantum walk ⋮ Quantum state transfer in coronas ⋮ Path-integral solution of the one-dimensional Dirac quantum cellular automaton ⋮ \textit{pyCTQW}: a continuous-time quantum walk simulator on distributed memory computers ⋮ Laplacian pretty good fractional revival ⋮ Quantum lattice algorithms: similarities and connections to some classic finite difference algorithms ⋮ Randomizing quantum walk ⋮ One-dimensional continuous-time quantum walks ⋮ Progress in quantum algorithms ⋮ Searching for antipodal vertices in a symmetric Cayley graph of the group of the Boolean cube ⋮ Grover walks on a line with absorbing boundaries ⋮ Localization of two-particle quantum walk on glued-tree and its application in generating Bell states ⋮ Laplacian versus adjacency matrix in quantum walk search ⋮ Vertices cannot be hidden from quantum spatial search for almost all random graphs ⋮ Path-sum solution of the Weyl quantum walk in 3 + 1 dimensions ⋮ Uniform mixing and association schemes ⋮ Crossover from diffusive to ballistic transport in periodic quantum maps ⋮ Forrelation: A Problem That Optimally Separates Quantum from Classical Computing ⋮ Investigation of continuous-time quantum walk via spectral distribution associated with adjacency matrix ⋮ History dependent quantum random walks as quantum lattice gas automata ⋮ Strong edge geodetic problem in networks ⋮ Quantum walk and its application domains: a systematic review ⋮ Efficient quantum algorithms for simulating sparse Hamiltonians ⋮ Concrete resource analysis of the quantum linear-system algorithm used to compute the electromagnetic scattering cross section of a 2D target ⋮ Dephasing assisted transport on a biomimetic ring structure ⋮ Coherence evolution in two-dimensional quantum walk on lattice ⋮ Perfect edge state transfer on abelian Cayley graphs ⋮ Quantum walks on a circle with optomechanical systems ⋮ Weyl, Dirac and Maxwell quantum cellular automata ⋮ Singular continuous Cantor spectrum for magnetic quantum walks ⋮ One-dimensional three-state quantum walks: Weak limits and localization ⋮ Pair state transfer ⋮ On the relationship between continuous- and discrete-time quantum walk ⋮ Experimental pairwise entanglement estimation for an \(N\)-qubit system. A machine learning approach for programming quantum hardware ⋮ A dynamic programming approach for distributing quantum circuits by bipartite graphs ⋮ Overview: recent development and applications of reduction and lackadaisicalness techniques for spatial search quantum walk in the near term ⋮ Perfect edge state transfer on cubelike graphs ⋮ Long time dynamics of a single-particle extended quantum walk on a one-dimensional lattice with complex hoppings: a generalized hydrodynamic description ⋮ Periodicity of lively quantum walks on cycles with generalized Grover coin ⋮ One-dimensional lackadaisical quantum walks ⋮ Quantum walks on Sierpinski gasket and Sierpinski tetrahedron ⋮ A hybrid classical-quantum clustering algorithm based on quantum walks ⋮ Efficient quantum circuits for continuous-time quantum walks on composite graphs ⋮ EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS ⋮ Tree search and quantum computation ⋮ Intricacies of quantum computational paths ⋮ Perfect state transfer on bi-Cayley graphs over abelian groups ⋮ Quantum stochastic walk models for quantum state discrimination ⋮ Circuit-based digital adiabatic quantum simulation and pseudoquantum simulation as new approaches to lattice gauge theory ⋮ Quantum algorithm design: techniques and applications ⋮ Practical Implementation of a Quantum Backtracking Algorithm ⋮ Two-dimensional quantum walk with position-dependent phase defects ⋮ A quantum walk-assisted approximate algorithm for bounded NP optimisation problems ⋮ Experimental observations of 1D quantum walks in a limited region ⋮ Qswalk: a \textit {Mathematica} package for quantum stochastic walks on arbitrary graphs ⋮ One-dimensional quantum walks with a time and spin-dependent phase shift ⋮ Quantum search algorithm for exceptional vertexes in regular graphs and its circuit implementation ⋮ Anderson localization for electric quantum walks and skew-shift CMV matrices ⋮ Image classification based on quantum K-nearest-neighbor algorithm ⋮ Quantum key distribution with quantum walks ⋮ Green's function approach for quantum graphs: an overview ⋮ Quantum walk on distinguishable non-interacting many-particles and indistinguishable two-particle ⋮ Quantum walks: a comprehensive review ⋮ Time averaged distribution of a discrete-time quantum walk on the path ⋮ Optimal computation with non-unitary quantum walks ⋮ Spatial search using the discrete time quantum walk ⋮ Continuous-time quantum walks on semi-regular spidernet graphs via quantum probability theory ⋮ Universal state transfer on graphs ⋮ Reducing the number of ancilla qubits and the gate count required for creating large controlled operations ⋮ Complexity classes of equivalence problems revisited ⋮ Central limit theorems for open quantum random walks on the crystal lattices ⋮ Quantum computing algorithm for electromagnetic field simulation ⋮ Pretty good state transfer on Cayley graphs over dihedral groups ⋮ Quantum walk public-key cryptographic system ⋮ Quantum approaches to graph colouring ⋮ Graph matching using the interference of continuous-time quantum walks ⋮ Perfect state transfer on weighted abelian Cayley graphs ⋮ Laplacian fractional revival on graphs ⋮ Percolation induced effects in two-dimensional coined quantum walks: analytic asymptotic solutions ⋮ Verification of quantum computation: an overview of existing approaches ⋮ Quantum fractional revival on graphs ⋮ Hitting times of quantum and classical random walks in potential spaces ⋮ Discrete quantum walks hit exponentially faster ⋮ Entropy generation in a model of reversible computation ⋮ Zero transfer in continuous-time quantum walks ⋮ Faster search of clustered marked states with lackadaisical quantum walks ⋮ The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processors ⋮ Simplifying continuous-time quantum walks on dynamic graphs ⋮ Spatial search on Johnson graphs by continuous-time quantum walk ⋮ Perfect state transfer on distance-regular graphs and association schemes ⋮ Fast quantum search of multiple vertices based on electric circuits ⋮ Levinson's theorem for graphs II ⋮ An encryption protocol for NEQR images based on one-particle quantum walks on a circle ⋮ On state transfer in Cayley graphs for abelian groups ⋮ Quantum algorithms for learning symmetric juntas via the adversary bound ⋮ Quantum computation and quantum information ⋮ An improved algorithm for computing hitting probabilities of quantum walks

This page was built for publication: Exponential algorithmic speedup by a quantum walk