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

Physical Review A

Realization of universal adiabatic quantum computation with fewer physical resources

Qian-Heng Duan, Ping‐Xing Chen

Published Oct 19, 2011• 5 citations
Publisher

Abstract

The adiabatic quantum computation (AQC) has been proved to be equivalent with the standard circuit model. To realize AQC, we have to realize the target Hamiltonian. However, usually the target Hamiltonian contains $k$-local terms where $k\ensuremath{\ge}3$ which is difficult to realize in experiment. It has been proved that a $k$-local Hamiltonian can be reduced to a two-local one. However, the reduction process needs a lot of auxiliary qubits which makes the system very complicated. Here we show that one can reduce a three-local Hamiltonian to a two-local one using only one third of the auxiliary qubits the previous approach needs and, in special cases, only three auxiliary qubits.

DOI
10.1103/physreva.84.042332

Related papers

Adiabatic Quantum Computation With Flux Qubits, First Experimental Results

S. H. W. van der Ploeg, A. Izmalkov, M. Grajcar +10 more

Controllable adiabatic evolution of a multi-qubit system can be used for adiabatic quantum computation (AQC). This evolution ends at a configuration where the Hamiltonian of the system encodes the solution of the problem to be solved. As a first steps towards realization of AQC we have investigated two, three and four flux qubit systems. These systems were characterized by making use of a radio-frequency method. We designed two-qubit systems with coupling energies up to several kelvins. For the three-flux-qubit systems we determined the complete ground-state flux diagram in the three dimensional flux space around the qubits common degeneracy point. We show that the system's Hamiltonian can be completely reconstructed from our measurements. Our concept for the implementation of AQC, by making use of flux qubits, is discussed.

arXiv:cond-mat/0702580•IEEE Transactions on Applied Superconductivity•Jun 1, 2007•16 citations

Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. Part 1: The "deduc-reduc" method and its application to quantum factorization of numbers

Richard Tanburn, Emile Okada, Nike Dattani

Adiabatic quantum computing has recently been used to factor 56153 [Dattani & Bryans, arXiv:1411.6758] at room temperature, which is orders of magnitude larger than any number attempted yet using Shor's algorithm (circuit-based quantum computation). However, this number is still vastly smaller than RSA-768 which is the largest number factored thus far on a classical computer. We address a major issue arising in the scaling of adiabatic quantum factorization to much larger numbers. Namely, the existence of many 4-qubit, 3-qubit and 2-qubit interactions in the Hamiltonians. We showcase our method on various examples, one of which shows that we can remove 94% of the 4-qubit interactions and 83% of the 3-qubit interactions in the factorization of a 25-digit number with almost no effort, without adding any auxiliary qubits. Our method is not limited to quantum factoring. Its importance extends to the wider field of discrete optimization. Any CSP (constraint-satisfiability problem), psuedo-boolean optimization problem, or QUBO (quadratic unconstrained Boolean optimization) problem can in principle benefit from the "deduction-reduction" method which we introduce in this paper. We provide an open source code which takes in a Hamiltonian (or a discrete discrete function which needs to be optimized), and returns a Hamiltonian that has the same unique ground state(s), no new auxiliary variables, and as few multi-qubit (multi-variable) terms as possible with deduc-reduc.

arXiv:1508.04816•Aug 19, 2015•8 citations

Adiabatic quantum simulators

Jacob Biamonte, V. Bergholm, James Daniel Whitfield +2 more

In his famous 1981 talk, Feynman proposed that unlike classical computers, which would presumably experience an exponential slowdown when simulating quantum phenomena, a universal quantum simulator would not. An ideal quantum simulator would be controllable, and built using existing technology. In some cases, moving away from gate-model-based implementations of quantum computing may offer a more feasible solution for particular experimental implementations. Here we consider an adiabatic quantum simulator which simulates the ground state properties of sparse Hamiltonians consisting of one- and two-local interaction terms, using sparse Hamiltonians with at most three-local interactions. Properties of such Hamiltonians can be well approximated with Hamiltonians containing only two-local terms. The register holding the simulated ground state is brought adiabatically into interaction with a probe qubit, followed by a single diabatic gate operation on the probe which then undergoes free evolution until measured. This allows one to recover e.g. the ground state energy of the Hamiltonian being simulated. Given a ground state, this scheme can be used to verify the QMA-complete problem LOCAL HAMILTONIAN, and is therefore likely more powerful than classical computing.

arXiv:1002.0368•AIP Advances•May 27, 2011•54 citations

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•40 citations

Hamiltonian gadgets with reduced resource requirements

Yudong Cao, Ryan Babbush, Jacob Biamonte +1 more

Application of the adiabatic model of quantum computation requires efficient encoding of the solution to computational problems into the lowest eigenstate of a Hamiltonian that supports universal adiabatic quantum computation. Experimental systems are typically limited to restricted forms of two-body interactions. Therefore, universal adiabatic quantum computation requires a method for approximating quantum many-body Hamiltonians up to arbitrary spectral error using at most two-body interactions. Hamiltonian gadgets, introduced around a decade ago, offer the only current means to address this requirement. Although the applications of Hamiltonian gadgets have steadily grown since their introduction, little progress has been made in overcoming the limitations of the gadgets themselves. In this experimentally motivated theoretical study, we introduce several gadgets which require significantly more realistic control parameters than similar gadgets in the literature. We employ analytical techniques which result in a reduction of the resource scaling as a function of spectral error for the commonly used subdivision, three- to two-body and $k$-body gadgets. Accordingly, our improvements reduce the resource requirements of all proofs and experimental proposals making use of these common gadgets. Next, we numerically optimize these gadgets to illustrate the tightness of our analytical bounds. Finally, we introduce a gadget that simulates a $YY$ interaction term using Hamiltonians containing only ${X,Z,XX,ZZ}$ terms. Apart from possible implications in a theoretical context, this work could also be useful for a first experimental implementation of these key building blocks by requiring less control precision without introducing extra ancillary qubits.

arXiv:1311.2555•Physical Review A•Jan 12, 2015•35 citations

An Alternative Approach to Construct the Initial Hamiltonian of the Adiabatic Quantum Computation

Qian-Heng Duan, Shuo Zhang, Wei Wu +1 more

The adiabatic quantum computation (AQC) has been proven to be equivalent to the standard circuit model. Conventionally, AQC evolves from the initial Hamiltonian which has a uniform equal superposition of the computational basis to the final Hamiltonian whose ground state encodes the solution to a computation problem. We propose an alternative approach to construct the initial Hamiltonian of the AQC which has an unequal superposition of the possible solutions to the problem and show that an educated guess can improve the performance of AQC.

Chinese Physics Letters•Jan 1, 2013•18 citations
The adiabatic quantum computation (AQC) has been proved to be equivalent with the standard circuit model. To realize AQC, we have to realize the target Hamiltonian. However, usually the target Hamiltonian contains kkk-local terms where k\ensuremath≥3k\ensuremath{\ge}3k\ensuremath≥3 which is difficult to realize in experiment. It has been proved that a kkk-local Hamiltonian can be reduced to a two-local one. However, the reduction process needs a lot of auxiliary qubits which makes the system very complicated. Here we show that one can reduce a three-local Hamiltonian to a two-local one using only one third of the auxiliary qubits the previous approach needs and, in special cases, only three auxiliary qubits.
Controllable adiabatic evolution of a multi-qubit system can be used for adiabatic quantum computation (AQC). This evolution ends at a configuration where the Hamiltonian of the system encodes the solution of the problem to be solved. As a first steps towards realization of AQC we have investigated two, three and four flux qubit systems. These systems were characterized by making use of a radio-frequency method. We designed two-qubit systems with coupling energies up to several kelvins. For the three-flux-qubit systems we determined the complete ground-state flux diagram in the three dimensional flux space around the qubits common degeneracy point. We show that the system's Hamiltonian can be completely reconstructed from our measurements. Our concept for the implementation of AQC, by making use of flux qubits, is discussed.
Adiabatic quantum computing has recently been used to factor 56153 [Dattani & Bryans, arXiv:1411.6758] at room temperature, which is orders of magnitude larger than any number attempted yet using Shor's algorithm (circuit-based quantum computation). However, this number is still vastly smaller than RSA-768 which is the largest number factored thus far on a classical computer. We address a major issue arising in the scaling of adiabatic quantum factorization to much larger numbers. Namely, the existence of many 4-qubit, 3-qubit and 2-qubit interactions in the Hamiltonians. We showcase our method on various examples, one of which shows that we can remove 94% of the 4-qubit interactions and 83% of the 3-qubit interactions in the factorization of a 25-digit number with almost no effort, without adding any auxiliary qubits. Our method is not limited to quantum factoring. Its importance extends to the wider field of discrete optimization. Any CSP (constraint-satisfiability problem), psuedo-boolean optimization problem, or QUBO (quadratic unconstrained Boolean optimization) problem can in principle benefit from the "deduction-reduction" method which we introduce in this paper. We provide an open source code which takes in a Hamiltonian (or a discrete discrete function which needs to be optimized), and returns a Hamiltonian that has the same unique ground state(s), no new auxiliary variables, and as few multi-qubit (multi-variable) terms as possible with deduc-reduc.
In his famous 1981 talk, Feynman proposed that unlike classical computers, which would presumably experience an exponential slowdown when simulating quantum phenomena, a universal quantum simulator would not. An ideal quantum simulator would be controllable, and built using existing technology. In some cases, moving away from gate-model-based implementations of quantum computing may offer a more feasible solution for particular experimental implementations. Here we consider an adiabatic quantum simulator which simulates the ground state properties of sparse Hamiltonians consisting of one- and two-local interaction terms, using sparse Hamiltonians with at most three-local interactions. Properties of such Hamiltonians can be well approximated with Hamiltonians containing only two-local terms. The register holding the simulated ground state is brought adiabatically into interaction with a probe qubit, followed by a single diabatic gate operation on the probe which then undergoes free evolution until measured. This allows one to recover e.g. the ground state energy of the Hamiltonian being simulated. Given a ground state, this scheme can be used to verify the QMA-complete problem LOCAL HAMILTONIAN, and is therefore likely more powerful than classical computing.
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.
Application of the adiabatic model of quantum computation requires efficient encoding of the solution to computational problems into the lowest eigenstate of a Hamiltonian that supports universal adiabatic quantum computation. Experimental systems are typically limited to restricted forms of two-body interactions. Therefore, universal adiabatic quantum computation requires a method for approximating quantum many-body Hamiltonians up to arbitrary spectral error using at most two-body interactions. Hamiltonian gadgets, introduced around a decade ago, offer the only current means to address this requirement. Although the applications of Hamiltonian gadgets have steadily grown since their introduction, little progress has been made in overcoming the limitations of the gadgets themselves. In this experimentally motivated theoretical study, we introduce several gadgets which require significantly more realistic control parameters than similar gadgets in the literature. We employ analytical techniques which result in a reduction of the resource scaling as a function of spectral error for the commonly used subdivision, three- to two-body and kkk-body gadgets. Accordingly, our improvements reduce the resource requirements of all proofs and experimental proposals making use of these common gadgets. Next, we numerically optimize these gadgets to illustrate the tightness of our analytical bounds. Finally, we introduce a gadget that simulates a YYYYYY interaction term using Hamiltonians containing only X,Z,XX,ZZ{X,Z,XX,ZZ}X,Z,XX,ZZ terms. Apart from possible implications in a theoretical context, this work could also be useful for a first experimental implementation of these key building blocks by requiring less control precision without introducing extra ancillary qubits.
The adiabatic quantum computation (AQC) has been proven to be equivalent to the standard circuit model. Conventionally, AQC evolves from the initial Hamiltonian which has a uniform equal superposition of the computational basis to the final Hamiltonian whose ground state encodes the solution to a computation problem. We propose an alternative approach to construct the initial Hamiltonian of the AQC which has an unequal superposition of the possible solutions to the problem and show that an educated guess can improve the performance of AQC.