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:2309.09331 · Physical Review A

Efficiency of Feynman's quantum computer

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

Published Feb 14, 2025• 1 citation
arXivHTMLPDF

Abstract

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

DOI
10.1103/physreva.111.022615

Related papers

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

Time-optimal Qubit mapping

Chi Zhang, Ari B. Hayes, Longfei Qiu +3 more

Rapid progress in the physical implementation of quantum computers gave birth to multiple recent quantum machines implemented with superconducting technology. In these NISQ machines, each qubit is physically connected to a bounded number of neighbors. This limitation prevents most quantum programs from being directly executed on quantum devices. A compiler is required for converting a quantum program to a hardware-compliant circuit, in particular, making each two-qubit gate executable by mapping the two logical qubits to two physical qubits with a link between them. To solve this problem, existing studies focus on inserting SWAP gates to dynamically remap logical qubits to physical qubits. However, most of the schemes lack the consideration of time-optimality of generated quantum circuits, or are achieving time-optimality with certain constraints. In this work, we propose a theoretically time-optimal SWAP insertion scheme for the qubit mapping problem. Our model can also be extended to practical heuristic algorithms. We present exact analysis results by using our model for quantum programs with recurring execution patterns. We have for the first time discovered an optimal qubit mapping pattern for quantum fourier transformation (QFT) on 2D nearest neighbor architecture. We also present a scalable extension of our theoretical model that can be used to solve qubit mapping for large quantum circuits.

International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)•Apr 11, 2021•87 citations

Designing and implementing small quantum circuits and algorithms

B. C. Travaglione

It appears, in principle, that the laws of quantum mechanics allow a quantum computer to solve certain mathematical problems more rapidly than can be done using a classical computer. However, in order to build such a quantum computer a number of technological problems need to be overcome. A stepping stone to this goal is the implementation of relatively simple quantum algorithms using current experimental techniques.This paper explores small scale quantum algorithms from two different perspectives. Firstly, it will be shown how small scale quantum algorithms can be tailored to fit current schemes for implementing a quantum computer. Secondly, I will review a simple model of computation, based on read-only-memory. This model allows the comparison of the space-efficiency of reversible error-free classical computation with reversible, error-free quantum computation. The quantum model has been shown to be more powerful than the classical model.

ACM/IEEE Design Automation Conference (DAC)•Jan 1, 2003•0 citations

Designing and implementing small quantum circuits and algorithms

B. C. Travaglione

It appears, in principle, that the laws of quantum mechanics allow a quantum computer to solve certain mathematical problems more rapidly than can be done using a classical computer. However, in order to build such a quantum computer a number of technological problems need to be overcome. A stepping stone to this goal is the implementation of relatively simple quantum algorithms using current experimental techniques.This paper explores small scale quantum algorithms from two different perspectives. Firstly, it will be shown how small scale quantum algorithms can be tailored to fit current schemes for implementing a quantum computer. Secondly, I will review a simple model of computation, based on read-only-memory. This model allows the comparison of the space-efficiency of reversible error-free classical computation with reversible, error-free quantum computation. The quantum model has been shown to be more powerful than the classical model.

ACM/IEEE Design Automation Conference (DAC)•Jun 2, 2003•1 citation

Fast universal quantum computation with railroad-switch local Hamiltonians

Daniel Nagaj

We present two universal models of quantum computation with a time-independent, frustration-free Hamiltonian. The first construction uses 3-local (qubit) projectors and the second one requires only 2-local qubit-qutrit projectors. We build on Feynman’s Hamiltonian computer idea [R. Feynman, Optics News 11, 11 (1985)] and use a railroad-switch-type clock register. The resources required to simulate a quantum circuit with L gates in this model are O(L) small-dimensional quantum systems (qubits or qutrits), a time-independent Hamiltonian composed of O(L) local, constant norm, projector terms, the possibility to prepare computational basis product states, a running time O(L log2 L), and the possibility to measure a few qubits in the computational basis. Our models also give a simplified proof of the universality of 3-local adiabatic quantum computation.

arXiv:0908.4219•Journal of Mathematical Physics•Jun 1, 2010•41 citations

Modeling Feynman's quantum computer using stochastic high level Petri nets

Leo Ojala, Elina Parviainen, Olli-Matti Penttinen +2 more

One of the first and simplest models of a quantum computer was introduced by Richard Feynman (1985). The aim of our study is to extend the application area of Petri nets, which have been very successfully used to model classical engineering systems, by modeling the use and operation of Feynman's quantum computer. Originally, Feynman could not give a time bound for the completion of his computer's computation; a periodical measurement procedure was needed giving rise to a specific computational approach. We have chosen Feynman's NOT-computer, in the form of two /spl radic/NOT gates in series, as our object of demonstration; its use and operation are modeled in detail using stochastic high level Petri net formalism.

Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics•Nov 13, 2002•2 citations
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 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.
Rapid progress in the physical implementation of quantum computers gave birth to multiple recent quantum machines implemented with superconducting technology. In these NISQ machines, each qubit is physically connected to a bounded number of neighbors. This limitation prevents most quantum programs from being directly executed on quantum devices. A compiler is required for converting a quantum program to a hardware-compliant circuit, in particular, making each two-qubit gate executable by mapping the two logical qubits to two physical qubits with a link between them. To solve this problem, existing studies focus on inserting SWAP gates to dynamically remap logical qubits to physical qubits. However, most of the schemes lack the consideration of time-optimality of generated quantum circuits, or are achieving time-optimality with certain constraints. In this work, we propose a theoretically time-optimal SWAP insertion scheme for the qubit mapping problem. Our model can also be extended to practical heuristic algorithms. We present exact analysis results by using our model for quantum programs with recurring execution patterns. We have for the first time discovered an optimal qubit mapping pattern for quantum fourier transformation (QFT) on 2D nearest neighbor architecture. We also present a scalable extension of our theoretical model that can be used to solve qubit mapping for large quantum circuits.
It appears, in principle, that the laws of quantum mechanics allow a quantum computer to solve certain mathematical problems more rapidly than can be done using a classical computer. However, in order to build such a quantum computer a number of technological problems need to be overcome. A stepping stone to this goal is the implementation of relatively simple quantum algorithms using current experimental techniques.This paper explores small scale quantum algorithms from two different perspectives. Firstly, it will be shown how small scale quantum algorithms can be tailored to fit current schemes for implementing a quantum computer. Secondly, I will review a simple model of computation, based on read-only-memory. This model allows the comparison of the space-efficiency of reversible error-free classical computation with reversible, error-free quantum computation. The quantum model has been shown to be more powerful than the classical model.
It appears, in principle, that the laws of quantum mechanics allow a quantum computer to solve certain mathematical problems more rapidly than can be done using a classical computer. However, in order to build such a quantum computer a number of technological problems need to be overcome. A stepping stone to this goal is the implementation of relatively simple quantum algorithms using current experimental techniques.This paper explores small scale quantum algorithms from two different perspectives. Firstly, it will be shown how small scale quantum algorithms can be tailored to fit current schemes for implementing a quantum computer. Secondly, I will review a simple model of computation, based on read-only-memory. This model allows the comparison of the space-efficiency of reversible error-free classical computation with reversible, error-free quantum computation. The quantum model has been shown to be more powerful than the classical model.
We present two universal models of quantum computation with a time-independent, frustration-free Hamiltonian. The first construction uses 3-local (qubit) projectors and the second one requires only 2-local qubit-qutrit projectors. We build on Feynman’s Hamiltonian computer idea [R. Feynman, Optics News 11, 11 (1985)] and use a railroad-switch-type clock register. The resources required to simulate a quantum circuit with L gates in this model are O(L) small-dimensional quantum systems (qubits or qutrits), a time-independent Hamiltonian composed of O(L) local, constant norm, projector terms, the possibility to prepare computational basis product states, a running time O(L log2 L), and the possibility to measure a few qubits in the computational basis. Our models also give a simplified proof of the universality of 3-local adiabatic quantum computation.
One of the first and simplest models of a quantum computer was introduced by Richard Feynman (1985). The aim of our study is to extend the application area of Petri nets, which have been very successfully used to model classical engineering systems, by modeling the use and operation of Feynman's quantum computer. Originally, Feynman could not give a time bound for the completion of his computer's computation; a periodical measurement procedure was needed giving rise to a specific computational approach. We have chosen Feynman's NOT-computer, in the form of two /spl radic/NOT gates in series, as our object of demonstration; its use and operation are modeled in detail using stochastic high level Petri net formalism.