Universal Computation by Quantum Walk

2008/06/12 by Andrew M. Childs · 38 citations
Computer Science · Physics and Astronomy · #Adjacency matrix #Algorithm #Computation #Computer science #Eigenvalues and eigenvectors #Feynman diagram #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum algorithm #Quantum computer #Quantum mechanics #Quantum network #Quantum walk #quant-ph

paper · pdf · doi:10.1103/physrevlett.102.180501

published as Phys. Rev. Lett. 102, 180501 (2009) · 9 pages

arxiv created 2008/06/12 · openalex publication_date 2009/05/04 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

In some of the earliest work on quantum computing, Feynman showed how to implement universal quantum computation with a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any quantum computation encoded in some graph. The main idea is to implement quantum gates by scattering processes.

Citations

• Spatial search and the Dirac equation
• Quantum Computation and Decision Trees
• Exponential algorithmic speedup by a quantum walk
• Quantum Algorithms for the Triangle Problem
• Spatial search by quantum walk
• Computational power of symmetric Hamiltonians
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Cited by

• Frequency-Space Mechanics: A Sequence and Coordinate-Free Representation for Protein Function Prediction
• Non-stabilizerness generation in a multi-particle quantum walk
• Quantum walk of a Bose-Einstein condensate in the Brillouin zone
• Quantum walks and wavepacket dynamics on a lattice with twisted photons
• Implementation of Leaking Quantum Walks on a Photonic Processor
• Driving quantum-walk spreading with the coin operator
• Chiral quantum walks
• Average position in quantum walks with a U(2) coin
• Optimization by a quantum reinforcement algorithm
• Path-sum solution of the Weyl quantum walk in 3 + 1 dimensions
• Coined quantum walks on weighted graphs
• Elephant quantum walk
• Spontaneous parametric downconversion and quantum walk topology
• Emerging quantum computing algorithms for quantum chemistry
• Driven Quantum Walks
• Converting Quasiclassical States into Arbitrary Fock State Superpositions in a Superconducting Circuit
• Experimental simulation of shift operators in a quantum processor
• Short-time behavior of continuous-time quantum walks on graphs
• Isolated vertices in continuous-time quantum walks on dynamic graphs
• Implementation of a 3 × 3 directionally-unbiased linear optical multiport
• Reversion of Quantum Walks via interventions on coin space
• Molecular realization of a quantum NAND tree
• Perfect State Transfer in Weighted Cubelike Graphs
• Efficient scheme for experimental quantification of non-Markovianity in high-dimensional systems
• Generalized eigenfunctions for quantum walks via path counting approach
• Out-of-time-ordered correlators and quantum walks
• Probability distributions for Markov chain based quantum walks
• Quantum walks with dynamical control: graph engineering, initial state preparation and state transfer
• Limits of quantum speedup in photosynthetic light harvesting
• Quantum Walks-Based Adaptive Distribution Generation with Efficient CUDA-Q Acceleration
• Shannon Entropy and Diffusion Coefficient in Parity-Time Symmetric Quantum Walks
• Weak limit of the three-state quantum walk on the line
• Quantum walks of two interacting anyons in one-dimensional optical lattices
• Percolation induced effects in two-dimensional coined quantum walks: analytic asymptotic solutions
• Quantum walks with memory provided by recycled coins and a memory of the coin-flip history
• Classical-like behavior in quantum walks with inhomogeneous, time-dependent coin operators
• Efficient quantum circuits for continuous-time quantum walks on composite graphs
• On the Convergence of Markov Chain Distribution within Quantum Walk Circuit Subspace
• Asymptotic properties of the Dirac quantum cellular automaton

Related

• Universal quantum walks and adiabatic algorithms by 1D Hamiltonians
• Universal computation by multi-particle quantum walk
• Quantum Algorithms and Covering Spaces
• Where to quantum walk
• Formal languages analysed by quantum walks