Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0806.1972 · Physical Review Letters

Universal Computation by Quantum Walk

Andrew M. Childs

Published May 4, 2009• 1,001 citations
arXivHTMLPDF

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.

DOI
10.1103/physrevlett.102.180501

Related papers

Universal quantum computation using the discrete-time quantum walk

Neil B. Lovett, Sally Cooper, Matthew Everitt +2 more

A proof that continuous-time quantum walks are universal for quantum computation, using unweighted graphs of low degree, has recently been presented by A. M. Childs [Phys. Rev. Lett. 102, 180501 (2009)]. We present a version based instead on the discrete-time quantum walk. We show that the discrete-time quantum walk is able to implement the same universal gate set and thus both discrete and continuous-time quantum walks are computational primitives. Additionally, we give a set of components on which the discrete-time quantum walk provides perfect state transfer.

arXiv:0910.1024•Physical Review A•Apr 30, 2010•510 citations

Universal quantum computation by discontinuous quantum walk

Michael S. Underwood, David L. Feder

Quantum walks are the quantum-mechanical analog of random walks, in which a quantum ``walker'' evolves between initial and final states by traversing the edges of a graph, either in discrete steps from node to node or via continuous evolution under the Hamiltonian furnished by the adjacency matrix of the graph. We present a hybrid scheme for universal quantum computation in which a quantum walker takes discrete steps of continuous evolution. This ``discontinuous'' quantum walk employs perfect quantum-state transfer between two nodes of specific subgraphs chosen to implement a universal gate set, thereby ensuring unitary evolution without requiring the introduction of an ancillary coin space. The run time is linear in the number of simulated qubits and gates. The scheme allows multiple runs of the algorithm to be executed almost simultaneously by starting walkers one time step apart.

arXiv:1008.3578•Physical Review A•Oct 7, 2010•56 citations

Quantum Walk Schemes for Universal Quantum Computation

Michael S. Underwood

Random walks are a powerful tool for the efficient implementation of algorithms in classical computation. Their quantum-mechanical analogues, called quantum walks, hold similar promise. Quantum walks provide a model of quantum computation that has recently been shown to be equivalent in power to the standard circuit model. As in the classical case, quantum walks take place on graphs and can undergo discrete or continuous evolution, though quantum evolution is unitary and therefore deterministic until a measurement is made. This thesis considers the usefulness of continuous-time quantum walks to quantum computation from the perspectives of both their fundamental power under various formulations, and their applicability in practical experiments. In one extant scheme, logical gates are effected by scattering processes. The results of an exhaustive search for single-qubit operations in this model are presented. It is shown that the number of distinct operations increases exponentially with the number of vertices in the scattering graph. A catalogue of all graphs on up to nine vertices that implement single-qubit unitaries at a specific set of momenta is included in an appendix. I develop a novel scheme for universal quantum computation called the discontinuous quantum walk, in which a continuous-time quantum walker takes discrete steps of evolution via perfect quantum state transfer through small `widget' graphs. The discontinuous quantum-walk scheme requires an exponentially sized graph, as do prior discrete and continuous schemes. To eliminate the inefficient vertex resource requirement, a computation scheme based on multiple discontinuous walkers is presented. In this model, n interacting walkers inhabiting a graph with 2n vertices can implement an arbitrary quantum computation on an input of length n, an exponential savings over previous universal quantum walk schemes. This is the first quantum walk scheme that allows for the application of quantum error correction. The many-particle quantum walk can be viewed as a single quantum walk undergoing perfect state transfer on a larger weighted graph, obtained via equitable partitioning. I extend this formalism to non-simple graphs. Examples of the application of equitable partitioning to the analysis of quantum walks and many-particle quantum systems are discussed.

•Jan 1, 2013•0 citations

Faster Computation with the Generalized Laplacian Quantum Walk

Jonas Duda, Thomas G. Wong

Quantum walks are the quantum analogues of classical random walks or Markov chains. They are universal models of quantum computing, and they underpin a variety of quantum algorithms. We prove that a continuous-time quantum walk effected by a generalized Laplacian, which can arise in spin chains, can solve a computational problem more quickly than typical quantum walks governed by the standard Laplacian or adjacency matrix. This generalized Laplacian consists of the standard Laplacian plus a real-valued multiple of the degree matrix, and we prove that as the magnitude of the multiple of the degree matrix is increased, its corresponding quantum walk can search the complete bipartite graph with multiple marked vertices in time that approaches the optimal. This raises the potential for the generalized Laplacian quantum walk to be a useful method for developing additional faster quantum algorithms.

quant-pharXiv:2609.10429•Sep 10, 2026•0 citations

Computational power of single qubit discrete-time quantum walk

Shivani Singh, Prateek Chawla, Anupam Sarkar +1 more

Abstract Quantum walk has been regarded as a primitive to universal quantum computation. By using the operations required to describe the single particle discrete-time quantum walk on a position space we demonstrate the realization of the universal set of gates on two-and three-qubit system. The idea is to reap the effective Hilbert space of the single qubit and the position space on which it evolves in superposition of position space in order to realize multi-qubit states and universal set of quantum gates on them. Realization of many non-trivial gates in the form of engineering arbitrary states is simpler in the proposed quantum walk model when compared to the circuit based model of computation. We will also discuss the scalability of the model and some propositions for using lesser number of qubits in realizing larger qubit systems.

•Feb 23, 2021•3 citations

Universal quantum computing using single-particle discrete-time quantum walk

Shivani Singh, Prateek Chawla, Anupam Sarkar +1 more

Quantum walk has been regarded as a primitive to universal quantum computation. In this paper, we demonstrate the realization of the universal set of quantum gates on two- and three-qubit systems by using the operations required to describe the single particle discrete-time quantum walk on a position space. The idea is to utilize the effective Hilbert space of the single qubit and the position space on which it evolves in order to realize multi-qubit states and universal set of quantum gates on them. Realization of many non-trivial gates and engineering arbitrary states is simpler in the proposed quantum walk model when compared to the circuit based model of computation. We will also discuss the scalability of the model and some propositions for using lesser number of qubits in realizing larger qubit systems.

arXiv:1907.04084•Scientific Reports•Jun 2, 2021•39 citations
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.
A proof that continuous-time quantum walks are universal for quantum computation, using unweighted graphs of low degree, has recently been presented by A. M. Childs [Phys. Rev. Lett. 102, 180501 (2009)]. We present a version based instead on the discrete-time quantum walk. We show that the discrete-time quantum walk is able to implement the same universal gate set and thus both discrete and continuous-time quantum walks are computational primitives. Additionally, we give a set of components on which the discrete-time quantum walk provides perfect state transfer.
Quantum walks are the quantum-mechanical analog of random walks, in which a quantum ``walker'' evolves between initial and final states by traversing the edges of a graph, either in discrete steps from node to node or via continuous evolution under the Hamiltonian furnished by the adjacency matrix of the graph. We present a hybrid scheme for universal quantum computation in which a quantum walker takes discrete steps of continuous evolution. This ``discontinuous'' quantum walk employs perfect quantum-state transfer between two nodes of specific subgraphs chosen to implement a universal gate set, thereby ensuring unitary evolution without requiring the introduction of an ancillary coin space. The run time is linear in the number of simulated qubits and gates. The scheme allows multiple runs of the algorithm to be executed almost simultaneously by starting walkers one time step apart.
Random walks are a powerful tool for the efficient implementation of algorithms in classical computation. Their quantum-mechanical analogues, called quantum walks, hold similar promise. Quantum walks provide a model of quantum computation that has recently been shown to be equivalent in power to the standard circuit model. As in the classical case, quantum walks take place on graphs and can undergo discrete or continuous evolution, though quantum evolution is unitary and therefore deterministic until a measurement is made. This thesis considers the usefulness of continuous-time quantum walks to quantum computation from the perspectives of both their fundamental power under various formulations, and their applicability in practical experiments. In one extant scheme, logical gates are effected by scattering processes. The results of an exhaustive search for single-qubit operations in this model are presented. It is shown that the number of distinct operations increases exponentially with the number of vertices in the scattering graph. A catalogue of all graphs on up to nine vertices that implement single-qubit unitaries at a specific set of momenta is included in an appendix. I develop a novel scheme for universal quantum computation called the discontinuous quantum walk, in which a continuous-time quantum walker takes discrete steps of evolution via perfect quantum state transfer through small `widget' graphs. The discontinuous quantum-walk scheme requires an exponentially sized graph, as do prior discrete and continuous schemes. To eliminate the inefficient vertex resource requirement, a computation scheme based on multiple discontinuous walkers is presented. In this model, n interacting walkers inhabiting a graph with 2n vertices can implement an arbitrary quantum computation on an input of length n, an exponential savings over previous universal quantum walk schemes. This is the first quantum walk scheme that allows for the application of quantum error correction. The many-particle quantum walk can be viewed as a single quantum walk undergoing perfect state transfer on a larger weighted graph, obtained via equitable partitioning. I extend this formalism to non-simple graphs. Examples of the application of equitable partitioning to the analysis of quantum walks and many-particle quantum systems are discussed.
Quantum walks are the quantum analogues of classical random walks or Markov chains. They are universal models of quantum computing, and they underpin a variety of quantum algorithms. We prove that a continuous-time quantum walk effected by a generalized Laplacian, which can arise in spin chains, can solve a computational problem more quickly than typical quantum walks governed by the standard Laplacian or adjacency matrix. This generalized Laplacian consists of the standard Laplacian plus a real-valued multiple of the degree matrix, and we prove that as the magnitude of the multiple of the degree matrix is increased, its corresponding quantum walk can search the complete bipartite graph with multiple marked vertices in time that approaches the optimal. This raises the potential for the generalized Laplacian quantum walk to be a useful method for developing additional faster quantum algorithms.
Abstract Quantum walk has been regarded as a primitive to universal quantum computation. By using the operations required to describe the single particle discrete-time quantum walk on a position space we demonstrate the realization of the universal set of gates on two-and three-qubit system. The idea is to reap the effective Hilbert space of the single qubit and the position space on which it evolves in superposition of position space in order to realize multi-qubit states and universal set of quantum gates on them. Realization of many non-trivial gates in the form of engineering arbitrary states is simpler in the proposed quantum walk model when compared to the circuit based model of computation. We will also discuss the scalability of the model and some propositions for using lesser number of qubits in realizing larger qubit systems.
Quantum walk has been regarded as a primitive to universal quantum computation. In this paper, we demonstrate the realization of the universal set of quantum gates on two- and three-qubit systems by using the operations required to describe the single particle discrete-time quantum walk on a position space. The idea is to utilize the effective Hilbert space of the single qubit and the position space on which it evolves in order to realize multi-qubit states and universal set of quantum gates on them. Realization of many non-trivial gates and engineering arbitrary states is simpler in the proposed quantum walk model when compared to the circuit based model of computation. We will also discuss the scalability of the model and some propositions for using lesser number of qubits in realizing larger qubit systems.