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:quant-ph/0610130 · Journal of Physics A Mathematical and General

Grover's algorithm on a Feynman computer

Diego de Falco, Dario Tamascelli

Published Jan 6, 2004• 7 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/0305-4470/37/3/025

Related papers

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

Interacting quantum walks

Dario Tamascelli

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.

arXiv:0910.2871•Oct 15, 2009•0 citations

The clock of a quantum computer

Bruno Apolloni, Diego de Falco

If the physical agent (the 'pointer', or 'cursor', or 'clocking mechanism') that sequentially scans the T lines of a long computer program is a microscopic system, two quantum phenomena become relevant: spreading of the probability distribution of the pointer along the program lines, and scattering of the probability amplitude at the two endpoints of the physical space allowed for its motion. We show that the first effect determines an upper bound O ( T −2/3 ) on the probability of finding the pointer exactly at the END line. By adding an adequate number δ of further empty lines ('telomers'), one can store the result of the computation up to the moment in which the pointer is scattered back into the active region. This leads to a less severe upper bound O (√δ/ T ) on the probability of finding the pointer either at the END line or within the additional empty lines. Our analysis is performed in the context of Feynman's model of quantum computation, the only model, to our knowledge, that explicitly includes a physically plausible quantum clocking mechanism in its considerations.

Journal of Physics A Mathematical and General•Nov 14, 2002•9 citations

Efficiency of Feynman's quantum computer

Ralph Jason Costales, Ali Gunning, T. C. Dorlas

Feynman's circuit-to-Hamiltonian construction enables the mapping of a quantum circuit to a time-independent Hamiltonian. This model introduces a Hilbert space made from an ancillary clock register tracking the progress of the computation. In this paper, we explore the efficiency, or run time, of a quantum computer that directly implements the clock system. This relates to the model's probability of computation completion which we investigate at an established optimal time for an arbitrary number of gates k . The relationship between the run time of the model and the number of gates is obtained both numerically and analytically to be O ( k 5 / 3 ) . In principle, this is significantly more efficient than the well-investigated Feynman-Kitaev model of adiabatic quantum computation with a run time of O ( k 4 ) . We address the challenge which stems from the small window that exists to capture the optimal stopping time, after which there are rapid oscillations of decreasing probability amplitude. We establish a relationship for the time difference between the first and second maximum which scales as O( k 1 / 3 ).

arXiv:2309.09331•Physical Review A•Feb 14, 2025•1 citation

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

Optical Implementation of Grover’s Algorithm: It’s all Done with Mirrors

Paul G. Kwiat, Jay Mitchell, Peter D. D. Schwindt +1 more

The essential operations of a quantum computer can all be accomplished using only standard linear optical elements (e.g., beamsplitters, waveplates, polarizers, etc.), with the individual bits represented by different spatial orpolarization degrees of freedom. The difference from a genuine quantum computer with distinct entangleable registers is that the optical implementation requires a number of elements which grows exponentially with the number of bits. However, by “compiling” the code, and making multiple use of redundant components, the required number of elements can be substantially reduced, allowing the realization of quantum algorithms involving several bits. Here we present a simple optical implementation of Grover’s algorithm for efficiently searching a database. In our example a database of four elements is searched with a single query, in contrast to the classical expected value of 2.25 queries. It is seen that the “quantum” computer in this case is no more than an interferometer, albeit a complicated one. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Kluwer Academic Publishers eBooks•Dec 19, 2005•4 citations
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.
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.
If the physical agent (the 'pointer', or 'cursor', or 'clocking mechanism') that sequentially scans the T lines of a long computer program is a microscopic system, two quantum phenomena become relevant: spreading of the probability distribution of the pointer along the program lines, and scattering of the probability amplitude at the two endpoints of the physical space allowed for its motion. We show that the first effect determines an upper bound O ( T −2/3 ) on the probability of finding the pointer exactly at the END line. By adding an adequate number δ of further empty lines ('telomers'), one can store the result of the computation up to the moment in which the pointer is scattered back into the active region. This leads to a less severe upper bound O (√δ/ T ) on the probability of finding the pointer either at the END line or within the additional empty lines. Our analysis is performed in the context of Feynman's model of quantum computation, the only model, to our knowledge, that explicitly includes a physically plausible quantum clocking mechanism in its considerations.
Feynman's circuit-to-Hamiltonian construction enables the mapping of a quantum circuit to a time-independent Hamiltonian. This model introduces a Hilbert space made from an ancillary clock register tracking the progress of the computation. In this paper, we explore the efficiency, or run time, of a quantum computer that directly implements the clock system. This relates to the model's probability of computation completion which we investigate at an established optimal time for an arbitrary number of gates k . The relationship between the run time of the model and the number of gates is obtained both numerically and analytically to be O ( k 5 / 3 ) . In principle, this is significantly more efficient than the well-investigated Feynman-Kitaev model of adiabatic quantum computation with a run time of O ( k 4 ) . We address the challenge which stems from the small window that exists to capture the optimal stopping time, after which there are rapid oscillations of decreasing probability amplitude. We establish a relationship for the time difference between the first and second maximum which scales as O( k 1 / 3 ).
The essential operations of a quantum computer can all be accomplished using only standard linear optical elements (e.g., beamsplitters, waveplates, polarizers, etc.), with the individual bits represented by different spatial orpolarization degrees of freedom. The difference from a genuine quantum computer with distinct entangleable registers is that the optical implementation requires a number of elements which grows exponentially with the number of bits. However, by “compiling” the code, and making multiple use of redundant components, the required number of elements can be substantially reduced, allowing the realization of quantum algorithms involving several bits. Here we present a simple optical implementation of Grover’s algorithm for efficiently searching a database. In our example a database of four elements is searched with a single query, in contrast to the classical expected value of 2.25 queries. It is seen that the “quantum” computer in this case is no more than an interferometer, albeit a complicated one. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.