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:1311.6101 · Journal of Physics A Mathematical and Theoretical

Space-time circuit-to-Hamiltonian construction and its applications

Nikolas P. Breuckmann, Barbara M. Terhal

Published Apr 23, 2014• 37 citations
arXivHTMLPDF

Abstract

The circuit-to-Hamiltonian construction translates dynamics (a quantum circuit and its output) into statics (the groundstate of a circuit Hamiltonian) by explicitly defining a quantum register for a clock. The standard Feynman–Kitaev construction uses one global clock for all qubits while we consider a different construction in which a clock is assigned to each interacting qubit. This makes it possible to capture the spatio-temporal structure of the original quantum circuit into features of the circuit Hamiltonian. The construction is inspired by the original two-dimensional interacting fermion model in Mizel et al (2001 Phys. Rev. A 63 040302). We prove that for one-dimensional quantum circuits the gap of the circuit Hamiltonian is appropriately lowerbounded so that the applications of this construction for quantum Merlin–Arthur (and partially for quantum adiabatic computation) go through. For one-dimensional quantum circuits, the dynamics generated by the circuit Hamiltonian corresponds to the diffusion of a string around the torus.

DOI
10.1088/1751-8113/47/19/195304

Related papers

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

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

Adiabatic and Hamiltonian computing on a 2D lattice with simple two-qubit interactions

Seth Lloyd, Barbara M. Terhal

We show how to perform universal Hamiltonian and adiabatic computing using a time-independent Hamiltonian on a 2D grid describing a system of hopping particles which string together and interact to perform the computation. In this construction, the movement of one particle is controlled by the presence or absence of other particles, an effective quantum field effect transistor that allows the construction of controlled-NOT and controlled-rotation gates. The construction translates into a model for universal quantum computation with time-independent two-qubit ZZ and XX + YY interactions on an (almost) planar grid. The effective Hamiltonian is arrived at by a single use of first-order perturbation theory avoiding the use of perturbation gadgets. The dynamics and spectral properties of the effective Hamiltonian can be fully determined as it corresponds to a particular realization of a mapping between a quantum circuit and a Hamiltonian called the space–time circuit-to-Hamiltonian construction. Because of the simple interactions required, and because no higher-order perturbation gadgets are employed, our construction is potentially realizable using superconducting or other solid-state qubits.

arXiv:1509.01278•New Journal of Physics•Feb 12, 2016•30 citations

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

Universal Adiabatic Quantum Computation via the Space-Time Circuit-to-Hamiltonian Construction

David Gosset, Barbara M. Terhal, Anna Vershynina

We show how to perform universal adiabatic quantum computation using a Hamiltonian which describes a set of particles with local interactions on a two-dimensional grid. A single parameter in the Hamiltonian is adiabatically changed as a function of time to simulate the quantum circuit. We bound the eigenvalue gap above the unique ground state by mapping our model onto the ferromagnetic XXZ chain with kink boundary conditions; the gap of this spin chain was computed exactly by Koma and Nachtergaele using its q-deformed version of SU(2) symmetry. We also discuss a related time-independent Hamiltonian which was shown by Janzing to be capable of universal computation. We observe that in the limit of large system size, the time evolution is equivalent to the exactly solvable quantum walk on Young's lattice.

arXiv:1409.7745•Physical Review Letters•Apr 6, 2015•47 citations

Adiabatic Quantum Computation

Friederike Anna Dziemba

The quantum adiabatic theorem ensures that a slowly changing system, initially prepared in its ground state, will evolve to its final ground state with arbitrary precision. As a first result this thesis extends the original theorem to projection operators keeping the statement valid for Hamiltonians with degenerate ground spaces. Yet the main focus of this work lies in studying the efficiency of quantum circuit simulations by adabatic quantum computation. The standard Hamiltonian construction by Kitaev is based on a path graph reflecting the $L$ computation steps and influencing the scaling of the necessary evolution time by its spectral gap of $\mathcal{O}\left(\frac{1}{L^2}\right)$. Aspiring to an improved running time we generalize Kitaev's Hamiltonian to so-called standard graph Hamiltonians based on graph families with a different spectral gap. In this generalized construction the first two time derivatives of the Hamiltonian and the fraction of initial vertices appear as additional parameters of running time. In a first step the time derivatives can be proven to be constant. Expansion results from spectral graph theory however impose a trade-off between the spectral gap and the fraction of initial vertices as well as the fraction of final vertices which corresponds to the probability for obtaining the correct computational output. Graphs with spectral gap $\mathcal{O}\left(\frac{1}{L^k}\right)$, $k<2$, turn out to contradict very likely, graphs with $k<1$ even for sure at least one of the efficiency criterias for running time, output probability or Hamiltonian implementation. The above results may also be obstacles for a possible quantum PCP-theorem in complexity theory claiming the local Hamiltonian problem with constant gap to be QMA-complete since the very same Kitaev Hamiltonian is constructed in the QMA-hardness proof for the Local Hamiltonian problem.

arXiv:1610.04708•Oct 15, 2016•2 citations
The circuit-to-Hamiltonian construction translates dynamics (a quantum circuit and its output) into statics (the groundstate of a circuit Hamiltonian) by explicitly defining a quantum register for a clock. The standard Feynman–Kitaev construction uses one global clock for all qubits while we consider a different construction in which a clock is assigned to each interacting qubit. This makes it possible to capture the spatio-temporal structure of the original quantum circuit into features of the circuit Hamiltonian. The construction is inspired by the original two-dimensional interacting fermion model in Mizel et al (2001 Phys. Rev. A 63 040302). We prove that for one-dimensional quantum circuits the gap of the circuit Hamiltonian is appropriately lowerbounded so that the applications of this construction for quantum Merlin–Arthur (and partially for quantum adiabatic computation) go through. For one-dimensional quantum circuits, the dynamics generated by the circuit Hamiltonian corresponds to the diffusion of a string around the torus.
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.
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 show how to perform universal Hamiltonian and adiabatic computing using a time-independent Hamiltonian on a 2D grid describing a system of hopping particles which string together and interact to perform the computation. In this construction, the movement of one particle is controlled by the presence or absence of other particles, an effective quantum field effect transistor that allows the construction of controlled-NOT and controlled-rotation gates. The construction translates into a model for universal quantum computation with time-independent two-qubit ZZ and XX + YY interactions on an (almost) planar grid. The effective Hamiltonian is arrived at by a single use of first-order perturbation theory avoiding the use of perturbation gadgets. The dynamics and spectral properties of the effective Hamiltonian can be fully determined as it corresponds to a particular realization of a mapping between a quantum circuit and a Hamiltonian called the space–time circuit-to-Hamiltonian construction. Because of the simple interactions required, and because no higher-order perturbation gadgets are employed, our construction is potentially realizable using superconducting or other solid-state qubits.
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.
We show how to perform universal adiabatic quantum computation using a Hamiltonian which describes a set of particles with local interactions on a two-dimensional grid. A single parameter in the Hamiltonian is adiabatically changed as a function of time to simulate the quantum circuit. We bound the eigenvalue gap above the unique ground state by mapping our model onto the ferromagnetic XXZ chain with kink boundary conditions; the gap of this spin chain was computed exactly by Koma and Nachtergaele using its q-deformed version of SU(2) symmetry. We also discuss a related time-independent Hamiltonian which was shown by Janzing to be capable of universal computation. We observe that in the limit of large system size, the time evolution is equivalent to the exactly solvable quantum walk on Young's lattice.
The quantum adiabatic theorem ensures that a slowly changing system, initially prepared in its ground state, will evolve to its final ground state with arbitrary precision. As a first result this thesis extends the original theorem to projection operators keeping the statement valid for Hamiltonians with degenerate ground spaces. Yet the main focus of this work lies in studying the efficiency of quantum circuit simulations by adabatic quantum computation. The standard Hamiltonian construction by Kitaev is based on a path graph reflecting the LLL computation steps and influencing the scaling of the necessary evolution time by its spectral gap of O(1L2)\mathcal{O}\left(\frac{1}{L^2}\right)O(L21​). Aspiring to an improved running time we generalize Kitaev's Hamiltonian to so-called standard graph Hamiltonians based on graph families with a different spectral gap. In this generalized construction the first two time derivatives of the Hamiltonian and the fraction of initial vertices appear as additional parameters of running time. In a first step the time derivatives can be proven to be constant. Expansion results from spectral graph theory however impose a trade-off between the spectral gap and the fraction of initial vertices as well as the fraction of final vertices which corresponds to the probability for obtaining the correct computational output. Graphs with spectral gap O(1Lk)\mathcal{O}\left(\frac{1}{L^k}\right)O(Lk1​), k<2k<2k<2, turn out to contradict very likely, graphs with k<1k<1k<1 even for sure at least one of the efficiency criterias for running time, output probability or Hamiltonian implementation. The above results may also be obstacles for a possible quantum PCP-theorem in complexity theory claiming the local Hamiltonian problem with constant gap to be QMA-complete since the very same Kitaev Hamiltonian is constructed in the QMA-hardness proof for the Local Hamiltonian problem.