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

Journal of Physics A Mathematical and General

The clock of a quantum computer

Bruno Apolloni, Diego de Falco

Published Nov 14, 2002• 9 citations
Publisher

Abstract

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.

DOI
10.1088/0305-4470/35/47/305

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

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

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

Clocks in Feynman's computer and Kitaev's local Hamiltonian: Bias, gaps, idling, and pulse tuning

Libor Caha, Zeph A. Landau, Daniel Nagaj

We present a collection of results about the clock in Feynman's computer construction and Kitaev's local Hamiltonian problem. First, by analyzing the spectra of quantum walks on a line with varying end-point terms, we find a better lower bound on the gap of the Feynman Hamiltonian, which translates into a less strict promise gap requirement for the quantum-Merlin-Arthur--complete local Hamiltonian problem. We also translate this result into the language of adiabatic quantum computation. Second, introducing an idling clock construction with a large state space but fast Cesaro mixing, we provide a way for achieving an arbitrarily high success probability of computation with Feynman's computer with only a logarithmic increase in the number of clock qubits. Finally, we tune and thus improve the costs (locality and gap scaling) of implementing a (pulse) clock with a single excitation.

arXiv:1712.07395•Physical Review A•Jun 5, 2018•34 citations

Decoherent histories for a particle coupled to a von Neumann apparatus

Francesc S. Roig

Using the Gell-Mann and Hartle formalism of generalized quantum mechanics of closed systems, we study coarse-grained decoherent histories. The system under consideration is one-dimensional and consists of a particle coupled to a von Neumann apparatus that measures its position. The particle moves in a quadratic potential; in particular we consider a driven harmonic oscillator. The real line is divided into intervals of the same length, and coarse-grained histories are defined by the arithmetic average of the initial and final position of the particle to be within one of these intervals. The position of the pointer correlates with this arithmetic average. In addition a constant term is added to this average, which is a result of the presence of a driving force on the oscillator. We investigate decoherence for such histories via the decoherence functional for the particle-apparatus. An exact expression for this functional has been derived. If the particle or the pointer of the apparatus is in an exact position state initially, then exact decoherence ensues, and the relative probability for such histories is obtained. If the initial state of the particle, which is centered at some arbitrary point in the $x$-axis, is narrow compared to the width of the intervals on the $x$-axis, then we obtain approximate decoherence. The same result follows if the initial state of the pointer is narrow. In these two situations, we evaluate expressions for the decoherence functional qualitatively and quantitatively. In the latter case we obtain the first two terms in an expansion in powers of the width of the initial state of the particle or the pointer respectively. Approximate relative probabilities can be assigned in this case, and we have obtained an expansion up to second order in powers of the width of the initial state for an expression for an upper bound of these probabilities.

arXiv:1405.5961•May 23, 2014•1 citation

Analysis and limitations of modified circuit-to-Hamiltonian constructions

Johannes Bausch, Elizabeth Crosson

Feynman's circuit-to-Hamiltonian construction connects quantum computation and ground states of many-body quantum systems. Kitaev applied this construction to demonstrate QMA-completeness of the local Hamiltonian problem, and Aharanov et al. used it to show the equivalence of adiabatic computation and the quantum circuit model. In this work, we analyze the low energy properties of a class of modified circuit Hamiltonians, which include features like complex weights and branching transitions. For history states with linear clocks and complex weights, we develop a method for modifying the circuit propagation Hamiltonian to implement any desired distribution over the time steps of the circuit in a frustration-free ground state, and show that this can be used to obtain a constant output probability for universal adiabatic computation while retaining the Ω(T−2) scaling of the spectral gap, and without any additional overhead in terms of numbers of qubits.Furthermore, we establish limits on the increase in the ground energy due to input and output penalty terms for modified tridiagonal clocks with non-uniform distributions on the time steps by proving a tight O(T−2) upper bound on the product of the spectral gap and ground state overlap with the endpoints of the computation. Using variational techniques which go beyond the Ω(T−3) scaling that follows from the usual geometrical lemma, we prove that the standard Feynman-Kitaev Hamiltonian already saturates this bound. We review the formalism of unitary labeled graphs which replace the usual linear clock by graphs that allow branching and loops, and we extend the O(T−2) bound from linear clocks to this more general setting. In order to achieve this, we apply Chebyshev polynomials to generalize an upper bound on the spectral gap in terms of the graph diameter to the context of arbitrary Hermitian matrices.

arXiv:1609.08571•Quantum•Sep 19, 2018•39 citations
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 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.
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 ).
We present a collection of results about the clock in Feynman's computer construction and Kitaev's local Hamiltonian problem. First, by analyzing the spectra of quantum walks on a line with varying end-point terms, we find a better lower bound on the gap of the Feynman Hamiltonian, which translates into a less strict promise gap requirement for the quantum-Merlin-Arthur--complete local Hamiltonian problem. We also translate this result into the language of adiabatic quantum computation. Second, introducing an idling clock construction with a large state space but fast Cesaro mixing, we provide a way for achieving an arbitrarily high success probability of computation with Feynman's computer with only a logarithmic increase in the number of clock qubits. Finally, we tune and thus improve the costs (locality and gap scaling) of implementing a (pulse) clock with a single excitation.
Using the Gell-Mann and Hartle formalism of generalized quantum mechanics of closed systems, we study coarse-grained decoherent histories. The system under consideration is one-dimensional and consists of a particle coupled to a von Neumann apparatus that measures its position. The particle moves in a quadratic potential; in particular we consider a driven harmonic oscillator. The real line is divided into intervals of the same length, and coarse-grained histories are defined by the arithmetic average of the initial and final position of the particle to be within one of these intervals. The position of the pointer correlates with this arithmetic average. In addition a constant term is added to this average, which is a result of the presence of a driving force on the oscillator. We investigate decoherence for such histories via the decoherence functional for the particle-apparatus. An exact expression for this functional has been derived. If the particle or the pointer of the apparatus is in an exact position state initially, then exact decoherence ensues, and the relative probability for such histories is obtained. If the initial state of the particle, which is centered at some arbitrary point in the xxx-axis, is narrow compared to the width of the intervals on the xxx-axis, then we obtain approximate decoherence. The same result follows if the initial state of the pointer is narrow. In these two situations, we evaluate expressions for the decoherence functional qualitatively and quantitatively. In the latter case we obtain the first two terms in an expansion in powers of the width of the initial state of the particle or the pointer respectively. Approximate relative probabilities can be assigned in this case, and we have obtained an expansion up to second order in powers of the width of the initial state for an expression for an upper bound of these probabilities.
Feynman's circuit-to-Hamiltonian construction connects quantum computation and ground states of many-body quantum systems. Kitaev applied this construction to demonstrate QMA-completeness of the local Hamiltonian problem, and Aharanov et al. used it to show the equivalence of adiabatic computation and the quantum circuit model. In this work, we analyze the low energy properties of a class of modified circuit Hamiltonians, which include features like complex weights and branching transitions. For history states with linear clocks and complex weights, we develop a method for modifying the circuit propagation Hamiltonian to implement any desired distribution over the time steps of the circuit in a frustration-free ground state, and show that this can be used to obtain a constant output probability for universal adiabatic computation while retaining the Ω(T−2) scaling of the spectral gap, and without any additional overhead in terms of numbers of qubits.Furthermore, we establish limits on the increase in the ground energy due to input and output penalty terms for modified tridiagonal clocks with non-uniform distributions on the time steps by proving a tight O(T−2) upper bound on the product of the spectral gap and ground state overlap with the endpoints of the computation. Using variational techniques which go beyond the Ω(T−3) scaling that follows from the usual geometrical lemma, we prove that the standard Feynman-Kitaev Hamiltonian already saturates this bound. We review the formalism of unitary labeled graphs which replace the usual linear clock by graphs that allow branching and loops, and we extend the O(T−2) bound from linear clocks to this more general setting. In order to achieve this, we apply Chebyshev polynomials to generalize an upper bound on the spectral gap in terms of the graph diameter to the context of arbitrary Hermitian matrices.