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:0910.1024 · Physical Review A

Universal quantum computation using the discrete-time quantum walk

Neil B. Lovett, Sally Cooper, Matthew Everitt, Matt Trevers, Viv M. Kendon

Published Apr 30, 2010• 510 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.81.042330

Related papers

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

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 Computing by Quantum Walk on Quantum Slide

Fan Wang, Bin Cheng, Zi‐Wei Cui +1 more

Continuous-time quantum walk is one of the alternative approaches to quantum computation, where a universal set of quantum gates can be achieved by scattering a quantum walker on some specially-designed structures embedded in a sparse graph [Childs, Phys. Rev. Lett. 2009]. Recent advances in femtosecond laser-inscribed optical waveguides represent a promising physical platform for realizing this quantum-walk model of quantum computation. However, the major challenge is the problem of preparing a plane-wave initial state. Previously, the idea of quantum slide has been proposed and experimentally realized for demonstrating the working principle of NAND tree [Wang et al. Phy. Rev. Lett. 2020]. Here we show how quantum slide can be further applied to realize universal quantum computation, bypassing the plane-wave requirement. Specifically, we apply an external field to the perfect-state-transfer chain, which can generate a moving Gaussian wave packet with an arbitrary momentum. When the phase is properly tuned, the universal gate set in Childs' proposal can be realized in our scheme. Furthermore, we show that the gate fidelities increase with the length of the slide, and can reach unity asymptotically.

arXiv:2211.08659•Nov 16, 2022•0 citations

Discrete-time quantum walk approach to state transfer

Paweł Kurzyński, Antoni Wójcik

We show that a quantum-state transfer, previously studied as a continuous-time process in networks of interacting spins, can be achieved within the model of discrete-time quantum walks with a position-dependent coin. We argue that, due to additional degrees of freedom, discrete-time quantum walks allow one to observe effects which cannot be observed in the corresponding continuous-time case. First, we study a discrete-time version of the engineered coupling protocol due to Christandl et al. [Phys. Rev. Lett. 92, 187902 (2004)] and then we discuss the general idea of conversion between continuous-time quantum walks and discrete-time quantum walks.

arXiv:1103.4185•Physical Review A•Jun 13, 2011•76 citations

Multi-qubit quantum computing using discrete-time quantum walks on closed graphs

Prateek Chawla, Shivani Singh, Aman Agarwal +2 more

Universal quantum computation can be realised using both continuous-time and discrete-time quantum walks. We present a version based on single particle discrete-time quantum walk to realize multi-qubit computation tasks. The scalability of the scheme is demonstrated by using a set of walk operations on a closed lattice form to implement the universal set of quantum gates on multi-qubit system. We also present a set of experimentally realizable walk operations that can implement Grover's algorithm, quantum Fourier transformation and quantum phase estimation algorithms. An elementary implementation of error detection and correction is also presented. Analysis of space and time complexity of the scheme highlights the advantages of quantum walk based model for quantum computation on systems where implementation of quantum walk evolution operations is an inherent feature of the system.

arXiv:2004.05956•Scientific Reports•Jul 26, 2023•12 citations

Universal Computation by Quantum Walk

Andrew M. Childs

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.

arXiv:0806.1972•Physical Review Letters•May 4, 2009•1,001 citations
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.
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-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.
Continuous-time quantum walk is one of the alternative approaches to quantum computation, where a universal set of quantum gates can be achieved by scattering a quantum walker on some specially-designed structures embedded in a sparse graph [Childs, Phys. Rev. Lett. 2009]. Recent advances in femtosecond laser-inscribed optical waveguides represent a promising physical platform for realizing this quantum-walk model of quantum computation. However, the major challenge is the problem of preparing a plane-wave initial state. Previously, the idea of quantum slide has been proposed and experimentally realized for demonstrating the working principle of NAND tree [Wang et al. Phy. Rev. Lett. 2020]. Here we show how quantum slide can be further applied to realize universal quantum computation, bypassing the plane-wave requirement. Specifically, we apply an external field to the perfect-state-transfer chain, which can generate a moving Gaussian wave packet with an arbitrary momentum. When the phase is properly tuned, the universal gate set in Childs' proposal can be realized in our scheme. Furthermore, we show that the gate fidelities increase with the length of the slide, and can reach unity asymptotically.
We show that a quantum-state transfer, previously studied as a continuous-time process in networks of interacting spins, can be achieved within the model of discrete-time quantum walks with a position-dependent coin. We argue that, due to additional degrees of freedom, discrete-time quantum walks allow one to observe effects which cannot be observed in the corresponding continuous-time case. First, we study a discrete-time version of the engineered coupling protocol due to Christandl et al. [Phys. Rev. Lett. 92, 187902 (2004)] and then we discuss the general idea of conversion between continuous-time quantum walks and discrete-time quantum walks.
Universal quantum computation can be realised using both continuous-time and discrete-time quantum walks. We present a version based on single particle discrete-time quantum walk to realize multi-qubit computation tasks. The scalability of the scheme is demonstrated by using a set of walk operations on a closed lattice form to implement the universal set of quantum gates on multi-qubit system. We also present a set of experimentally realizable walk operations that can implement Grover's algorithm, quantum Fourier transformation and quantum phase estimation algorithms. An elementary implementation of error detection and correction is also presented. Analysis of space and time complexity of the scheme highlights the advantages of quantum walk based model for quantum computation on systems where implementation of quantum walk evolution operations is an inherent feature of the system.