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:1205.3782 · Science

Universal Computation by Multiparticle Quantum Walk

Andrew M. Childs, David Gosset, Zak Webb

Published Feb 14, 2013• 456 citations
arXivHTMLPDF

Abstract

Computing Power of Quantum Mechanics There is much interest in developing quantum computers in order to perform certain tasks much faster than, or that are intractable for, a classical computer. A general quantum computer, however, requires the fabrication and operation a number of quantum logic devices (see the Perspective by Franson ). Broome et al. (p. 794 , published online 20 December) and Spring et al. (p. 798 , published online 20 December) describe experiments in which single photons and quantum interference were used to perform a calculation (the permanent of a matrix) that is very difficult on a classical computer. Similar to random walks, quantum walks on a graph describe the movement of a walker on a set of predetermined paths; instead of flipping a coin to decide which way to go at each point, a quantum walker can take several paths at once. Childs et al. (p. 791 ) propose an architecture for a quantum computer, based on quantum walks of multiple interacting walkers. The system is capable of performing any quantum operation using a subset of its nodes, with the size of the subset scaling favorably with the complexity of the operation.

DOI
10.1126/science.1229957

Related papers

Boson Sampling on a Photonic Chip

Justin B. Spring, Benjamin J. Metcalf, Peter C. Humphreys +11 more

Computing Power of Quantum Mechanics There is much interest in developing quantum computers in order to perform certain tasks much faster than, or that are intractable for, a classical computer. A general quantum computer, however, requires the fabrication and operation a number of quantum logic devices (see the Perspective by Franson ). Broome et al. (p. 794 , published online 20 December) and Spring et al. (p. 798 , published online 20 December) describe experiments in which single photons and quantum interference were used to perform a calculation (the permanent of a matrix) that is very difficult on a classical computer. Similar to random walks, quantum walks on a graph describe the movement of a walker on a set of predetermined paths; instead of flipping a coin to decide which way to go at each point, a quantum walker can take several paths at once. Childs et al. (p. 791 ) propose an architecture for a quantum computer, based on quantum walks of multiple interacting walkers. The system is capable of performing any quantum operation using a subset of its nodes, with the size of the subset scaling favorably with the complexity of the operation.

arXiv:1212.2622•Science•Dec 21, 2012•836 citations

Photonic Boson Sampling in a Tunable Circuit

Matthew A. Broome, Alessandro Fedrizzi, Saleh Rahimi-Keshari +4 more

Computing Power of Quantum Mechanics There is much interest in developing quantum computers in order to perform certain tasks much faster than, or that are intractable for, a classical computer. A general quantum computer, however, requires the fabrication and operation a number of quantum logic devices (see the Perspective by Franson ).Broomeet al.(p. 794 , published online 20 December) andSpringet al.(p. 798 , published online 20 December) describe experiments in which single photons and quantum interference were used to perform a calculation (the permanent of a matrix) that is very difficult on a classical computer. Similar to random walks, quantum walks on a graph describe the movement of a walker on a set of predetermined paths; instead of flipping a coin to decide which way to go at each point, a quantum walker can take several paths at once.Childset al.(p. 791 ) propose an architecture for a quantum computer, based on quantum walks of multiple interacting walkers. The system is capable of performing any quantum operation using a subset of its nodes, with the size of the subset scaling favorably with the complexity of the operation.

arXiv:1212.2234•Science•Dec 21, 2012•632 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

A random walk approach to quantum algorithms

Viv M. Kendon

The development of quantum algorithms based on quantum versions of random walks is placed in the context of the emerging field of quantum computing. Constructing a suitable quantum version of a random walk is not trivial; pure quantum dynamics is deterministic, so randomness only enters during the measurement phase, i.e. when converting the quantum information into classical information. The outcome of a quantum random walk is very different from the corresponding classical random walk owing to the interference between the different possible paths. The upshot is that quantum walkers find themselves further from their starting point than a classical walker on average, and this forms the basis of a quantum speed up, which can be exploited to solve problems faster. Surprisingly, the effect of making the walk slightly less than perfectly quantum can optimize the properties of the quantum walk for algorithmic applications. Looking to the future, even with a small quantum computer available, the development of quantum walk algorithms might proceed more rapidly than it has, especially for solving real problems.

arXiv:quant-ph/0609035•Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Oct 18, 2006•116 citations

How to computer using quantum walks

Viv M. Kendon

Quantum walks are widely and successfully used to model diverse physical processes. This leads to computation of the models, to explore their properties. Quantum walks have also been shown to be universal for quantum computing. This is a more subtle result than is often appreciated, since it applies to computations run on qubit-based quantum computers in the single walker case, and physical quantum walks in the multi-walker case (quantum cellular automata). Nonetheless, quantum walks are powerful tools for quantum computing when correctly applied. In this paper, I explain the relationship between quantum walks as models and quantum walks as computational tools, and give some examples of their application in both contexts.

•Apr 3, 2020•9 citations

How to Compute Using Quantum Walks

Viv Kendon

Quantum walks are widely and successfully used to model diverse physical processes. This leads to computation of the models, to explore their properties. Quantum walks have also been shown to be universal for quantum computing. This is a more subtle result than is often appreciated, since it applies to computations run on qubit-based quantum computers in the single walker case, and physical quantum walks in the multi-walker case (quantum cellular automata). Nonetheless, quantum walks are powerful tools for quantum computing when correctly applied. In this paper, I explain the relationship between quantum walks as models and quantum walks as computational tools, and give some examples of their application in both contexts.

arXiv:2004.01329•Electronic Proceedings in Theoretical Computer Science•Apr 1, 2020•10 citations
Computing Power of Quantum Mechanics There is much interest in developing quantum computers in order to perform certain tasks much faster than, or that are intractable for, a classical computer. A general quantum computer, however, requires the fabrication and operation a number of quantum logic devices (see the Perspective by Franson ). Broome et al. (p. 794 , published online 20 December) and Spring et al. (p. 798 , published online 20 December) describe experiments in which single photons and quantum interference were used to perform a calculation (the permanent of a matrix) that is very difficult on a classical computer. Similar to random walks, quantum walks on a graph describe the movement of a walker on a set of predetermined paths; instead of flipping a coin to decide which way to go at each point, a quantum walker can take several paths at once. Childs et al. (p. 791 ) propose an architecture for a quantum computer, based on quantum walks of multiple interacting walkers. The system is capable of performing any quantum operation using a subset of its nodes, with the size of the subset scaling favorably with the complexity of the operation.
Computing Power of Quantum Mechanics There is much interest in developing quantum computers in order to perform certain tasks much faster than, or that are intractable for, a classical computer. A general quantum computer, however, requires the fabrication and operation a number of quantum logic devices (see the Perspective by Franson ). Broome et al. (p. 794 , published online 20 December) and Spring et al. (p. 798 , published online 20 December) describe experiments in which single photons and quantum interference were used to perform a calculation (the permanent of a matrix) that is very difficult on a classical computer. Similar to random walks, quantum walks on a graph describe the movement of a walker on a set of predetermined paths; instead of flipping a coin to decide which way to go at each point, a quantum walker can take several paths at once. Childs et al. (p. 791 ) propose an architecture for a quantum computer, based on quantum walks of multiple interacting walkers. The system is capable of performing any quantum operation using a subset of its nodes, with the size of the subset scaling favorably with the complexity of the operation.
Computing Power of Quantum Mechanics There is much interest in developing quantum computers in order to perform certain tasks much faster than, or that are intractable for, a classical computer. A general quantum computer, however, requires the fabrication and operation a number of quantum logic devices (see the Perspective by Franson ).Broomeet al.(p. 794 , published online 20 December) andSpringet al.(p. 798 , published online 20 December) describe experiments in which single photons and quantum interference were used to perform a calculation (the permanent of a matrix) that is very difficult on a classical computer. Similar to random walks, quantum walks on a graph describe the movement of a walker on a set of predetermined paths; instead of flipping a coin to decide which way to go at each point, a quantum walker can take several paths at once.Childset al.(p. 791 ) propose an architecture for a quantum computer, based on quantum walks of multiple interacting walkers. The system is capable of performing any quantum operation using a subset of its nodes, with the size of the subset scaling favorably with the complexity of the operation.
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.
The development of quantum algorithms based on quantum versions of random walks is placed in the context of the emerging field of quantum computing. Constructing a suitable quantum version of a random walk is not trivial; pure quantum dynamics is deterministic, so randomness only enters during the measurement phase, i.e. when converting the quantum information into classical information. The outcome of a quantum random walk is very different from the corresponding classical random walk owing to the interference between the different possible paths. The upshot is that quantum walkers find themselves further from their starting point than a classical walker on average, and this forms the basis of a quantum speed up, which can be exploited to solve problems faster. Surprisingly, the effect of making the walk slightly less than perfectly quantum can optimize the properties of the quantum walk for algorithmic applications. Looking to the future, even with a small quantum computer available, the development of quantum walk algorithms might proceed more rapidly than it has, especially for solving real problems.
Quantum walks are widely and successfully used to model diverse physical processes. This leads to computation of the models, to explore their properties. Quantum walks have also been shown to be universal for quantum computing. This is a more subtle result than is often appreciated, since it applies to computations run on qubit-based quantum computers in the single walker case, and physical quantum walks in the multi-walker case (quantum cellular automata). Nonetheless, quantum walks are powerful tools for quantum computing when correctly applied. In this paper, I explain the relationship between quantum walks as models and quantum walks as computational tools, and give some examples of their application in both contexts.
Quantum walks are widely and successfully used to model diverse physical processes. This leads to computation of the models, to explore their properties. Quantum walks have also been shown to be universal for quantum computing. This is a more subtle result than is often appreciated, since it applies to computations run on qubit-based quantum computers in the single walker case, and physical quantum walks in the multi-walker case (quantum cellular automata). Nonetheless, quantum walks are powerful tools for quantum computing when correctly applied. In this paper, I explain the relationship between quantum walks as models and quantum walks as computational tools, and give some examples of their application in both contexts.