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.2871

Interacting quantum walks

Dario Tamascelli

Published Oct 15, 2009• 0 citations
arXivHTMLPDF

Abstract

In this work we present the quantum mechanical computer proposed by Feynman in 1985 and, since then, widely cited but seldom used. The main feature of the model is the presence of a built in clocking mechanism managing for the ordered application of the computational primitives to the input/output register.
DOI
10.48550/arxiv.0910.2871

Related papers

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,043 citations

Quantum Walk Computing: Theory, Implementation, and Application

Xiaogang Qiang, Shixin Ma, Haijing Song

The classical random walk formalism plays an important role in a wide range of applications. Its quantum counterpart, the quantum walk, is proposed as an important theoretical model for quantum computing. By exploiting quantum effects such as superposition, interference, and entanglement, quantum walks and their variations have been extensively studied for achieving computing power beyond that of classical computing and have been broadly used in designing quantum algorithms for algebraic and optimization problems, graph and network analysis, and quantum Hamiltonian and biochemical process simulations. Moreover, quantum walk models have been proven capable of universal quantum computation. Unlike conventional quantum circuit models, quantum walks provide a feasible path for implementing application-specific quantum computing, particularly in the noisy intermediate-scale quantum era. Recently, remarkable progress has been achieved in implementing a wide variety of quantum walks and quantum walk applications, which demonstrates the great potential of quantum walks. In this review, we provide a thorough summary of quantum walks and quantum walk computing, including theories and characteristics, physical implementations, and applications. We also discuss the challenges facing quantum walk computing, which aims to realize a practical quantum computer in the near future.

arXiv:2404.04178•Intelligent Computing•Jan 1, 2024•77 citations

How to Compute 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.

arXiv:2004.01329•Electronic Proceedings in Theoretical Computer Science•Apr 1, 2020•11 citations

Feynman's contribution

Joachim Stolze, Dieter Suter

This chapter contains sections titled: Simulating physics with computers Quantum mechanical computers

Wiley eBooks•May 26, 2004•0 citations

QUANTUM TIMING AND SYNCHRONIZATION PROBLEMS

Diego de Falco, Dario Tamascelli

Feynman's model of a quantum computer provides an example of a continuous-time quantum walk. Its clocking mechanism is an excitation of a basically linear chain of spins with occasional controlled jumps which allow for motion on a planar graph. The spreading of the wave packet poses limitations on the probability of ever completing the s elementary steps of a computation: an additional amount of storage space δ is needed in order to achieve an assigned completion probability. In this note we study the END instruction, viewed as a measurement of the position of the clocking excitation: a π-pulse indefinitely freezes the contents of the input/output register, with a probability depending only on the ratio δ/s.

arXiv:quant-ph/0504024•International Journal of Modern Physics B•Feb 20, 2004•4 citations

Grover's algorithm on a Feynman computer

Diego de Falco, Dario Tamascelli

We present an implementation of Grover's algorithm in the framework of Feynman's cursor model of a quantum computer. The cursor degrees of freedom act as a quantum clocking mechanism, and allow Grover's algorithm to be performed using a single, time-independent Hamiltonian. We examine issues of locality and resource usage in implementing such a Hamiltonian. In the familiar language of Heisenberg spin–spin coupling, the clocking mechanism appears as an excitation of a basically linear chain of spins, with occasional controlled jumps that allow for motion on a planar graph: in this sense our model implements the idea of ‘timing’ a quantum algorithm using a continuous-time random walk. In this context we examine some consequences of the entanglement between the states of the input/output register and the states of the quantum clock.

arXiv:quant-ph/0610130•Journal of Physics A Mathematical and General•Jan 6, 2004•7 citations
The classical random walk formalism plays an important role in a wide range of applications. Its quantum counterpart, the quantum walk, is proposed as an important theoretical model for quantum computing. By exploiting quantum effects such as superposition, interference, and entanglement, quantum walks and their variations have been extensively studied for achieving computing power beyond that of classical computing and have been broadly used in designing quantum algorithms for algebraic and optimization problems, graph and network analysis, and quantum Hamiltonian and biochemical process simulations. Moreover, quantum walk models have been proven capable of universal quantum computation. Unlike conventional quantum circuit models, quantum walks provide a feasible path for implementing application-specific quantum computing, particularly in the noisy intermediate-scale quantum era. Recently, remarkable progress has been achieved in implementing a wide variety of quantum walks and quantum walk applications, which demonstrates the great potential of quantum walks. In this review, we provide a thorough summary of quantum walks and quantum walk computing, including theories and characteristics, physical implementations, and applications. We also discuss the challenges facing quantum walk computing, which aims to realize a practical quantum computer in the near future.
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.
Feynman's model of a quantum computer provides an example of a continuous-time quantum walk. Its clocking mechanism is an excitation of a basically linear chain of spins with occasional controlled jumps which allow for motion on a planar graph. The spreading of the wave packet poses limitations on the probability of ever completing the s elementary steps of a computation: an additional amount of storage space δ is needed in order to achieve an assigned completion probability. In this note we study the END instruction, viewed as a measurement of the position of the clocking excitation: a π-pulse indefinitely freezes the contents of the input/output register, with a probability depending only on the ratio δ/s.
We present an implementation of Grover's algorithm in the framework of Feynman's cursor model of a quantum computer. The cursor degrees of freedom act as a quantum clocking mechanism, and allow Grover's algorithm to be performed using a single, time-independent Hamiltonian. We examine issues of locality and resource usage in implementing such a Hamiltonian. In the familiar language of Heisenberg spin–spin coupling, the clocking mechanism appears as an excitation of a basically linear chain of spins, with occasional controlled jumps that allow for motion on a planar graph: in this sense our model implements the idea of ‘timing’ a quantum algorithm using a continuous-time random walk. In this context we examine some consequences of the entanglement between the states of the input/output register and the states of the quantum clock.