Source-linked AI summary
Realizable Hamiltonians for Universal Adiabatic Quantum Computers
Jacob D. Biamonte, Peter J. Love
TL;DR
General 2-local Hamiltonian universality leaves the required physical interaction types unrestricted, motivating simpler realizable models. The paper proves that ZZXX and ZX interaction sets achieve QMA-completeness and universal adiabatic computation by directly realizing or perturbatively approximating the needed real-valued terms. These models are presented as practical candidates for experimental implementations.
Problem
Existing universality proofs use general 2-local Hamiltonians, so the minimal physically required interaction set remains an open practical and theoretical question.
Method
The paper reduces real-valued Hamiltonians to restricted ZZXX and ZX models using perturbative gadgets that approximate missing Pauli-product terms.
Results
The ZZXX and ZX Hamiltonians are QMA-complete and universal for adiabatic quantum computation, with gadget approximations achieving O(ε) error.
Takeaways & Limitations
The reported Hamiltonians are simple 2-local models of practical interest and support universal adiabatic, gate-model, autonomous, and measurement-based quantum computation.
Abstract
from arXiv · showhide
It has been established that local lattice spin Hamiltonians can be used for universal adiabatic quantum computation. However, the 2-local model Hamiltonians used in these proofs are general and hence do not limit the types of interactions required between spins. To address this concern, the present paper provides two simple model Hamiltonians that are of practical interest to experimentalists working towards the realization of a universal adiabatic quantum computer. The model Hamiltonians presented are the simplest known QMA-complete 2-local Hamiltonians. The 2-local Ising model with 1-local transverse field which has been realized using an array of technologies, is perhaps the simplest quantum spin model but is unlikely to be universal for adiabatic quantum computation. We demonstrate that this model can be rendered universal and QMA-complete by adding a tunable 2-local transverse XX coupling. We also show the universality and QMA-completeness of spin models with only 1-local Z and X fields and 2-local ZX interactions.
I. THE PROBLEM
The paper reviews the circuit-to-adiabatic construction, in which a history-state Hamiltonian encodes computation through input, clock, and propagation terms. This motivates seeking physically realizable Hamiltonians with restricted interactions.
- I. THE PROBLEM: The full construction combines input, clock, clock-initialization, and propagation terms into a Hamiltonian whose ground state is the history state.The paper presents this construction as a key building block for QMA-completeness and circuit-to-adiabatic equivalence.
- I. THE PROBLEM: The history state represents a circuit’s entire time evolution using a T-qubit unary clock.The circuit has T gates and n logical qubits, with clock and logical-qubit operators separated in the construction.
- I. THE PROBLEM: H_in enforces the valid classical input at time zero by placing the corresponding input state in the low-energy eigenspace.It acts on all n logical qubits and the first clock qubit.
- I. THE PROBLEM: H_clock restricts the clock to valid unary states, while H_clockint penalizes an incorrect first-qubit value at time zero.The clock Hamiltonian has a ferromagnetic domain-wall interpretation.
- I. THE PROBLEM: H_prop enforces correct computation by summing T terms, each checking propagation from time t−1 to t.For boundary times, the corresponding clock term omits one clock qubit.
A. The QMA-completeness of real-valued Hamiltonians
The paper establishes QMA-completeness and adiabatic universality for real-valued local Hamiltonians, then targets two restricted interaction sets using perturbative gadgets. These sets realize the required real Pauli products directly or approximately.
- A. The QMA-completeness of real-valued Hamiltonians: 5-local real Hamiltonian is QMA-complete because the standard construction can use real-valued gates and real-valued wavefunctions.The earlier proof remains intact apart from changing the gates used in the circuits.
- A. The QMA-completeness of real-valued Hamiltonians: The gate sequence R_ij(φ)R_ij(π/2) recovers a universal gate, and discrete self-inverse universal gate sets can also be constructed.The set {C-NOT, X, cosψX + sinψZ} is universal when ψ is not a multiple of π/4.
- A. The QMA-completeness of real-valued Hamiltonians: 2-local real Hamiltonian is QMA-complete and universal for adiabatic quantum computation after gadget reductions from higher-locality terms.The reductions use gadgets that reduce 3-local Hamiltonian terms to 2-local terms.
- A. The QMA-completeness of real-valued Hamiltonians: The real-valued construction needs only pairwise products drawn from I, X, and Z operators, including XZ, ZX, XX, and ZZ.The listed operator set also includes one-local identity, X, and Z terms.
- A. The QMA-completeness of real-valued Hamiltonians: Perturbation-theory gadgets are used to approximate the missing terms in the restricted ZZXX and ZX Hamiltonians.The paper’s next sections construct gadgets for the relevant absent interactions.
B. The ZZXX gadget
The ZZXX gadget uses an ancillary penalty Hamiltonian and perturbative virtual excitations to approximate otherwise unavailable interactions. Its effective Hamiltonian and ground state remain close to the target with O(ε) error.
- B. The ZZXX gadget: The penalty Hamiltonian separates the ancilla into a low-energy |0⟩ subspace and a δ-energy |1⟩ subspace.Both subspaces remain degenerate over the states of qubits i and j.
- B. The ZZXX gadget: The perturbation V=V1+V2+V3 breaks low-energy degeneracy, with V2 driving virtual ancilla excitations and V3 applying a σ_z operation during those transitions.The resulting process couples σ_z on qubit i with σ_x on qubit j.
- B. The ZZXX gadget: The gadget’s self-energy is expanded perturbatively and projected onto the low-energy subspace to obtain an effective Hamiltonian.Only V2 connects the low- and high-energy subspaces, while V1 and V3 act within them as specified.
- B. The ZZXX gadget: Existing physical interactions are dressed by the gadget, modifying coupling constants, adding an overall energy shift, and introducing a small σ_zσ_z correction.The correction depends on the strength of the σ_z term in the physical interaction.
- B. The ZZXX gadget: O(ε) bounds on the self-energy approximation imply O(ε) eigenvalue error and a close ground-state wavefunction for the gadget.The required spectral-gap scaling uses r≥3 in the stated inverse-polynomial bound.
- B. The ZZXX gadget: The ZZXX Hamiltonian directly realizes all required terms except σ_zσ_x and σ_xσ_z, which the gadget approximates with O(ε) error.This establishes efficient approximation of all terms in the real-valued target operator set.
C. The ZZ from ZX gadget
The ZZ from ZX gadget uses a penalty Hamiltonian and perturbation to realize an effective ZZ interaction from a ZX Hamiltonian, with controlled approximation error.
- C. The ZZ from ZX gadget: The gadget applies V = V1 + V2 to qubits i, j, and ancillary qubit k to generate an effective ZZ interaction.The perturbative Hamiltonian is diagrammed in Fig. 2, with an overall energy shift of A/2.
- C. The ZZ from ZX gadget: V1 preserves the low- and high-energy subspaces, while V2 couples them and vanishes within each subspace.These projection properties determine which perturbative terms contribute to the low-energy effective Hamiltonian.
- C. The ZZ from ZX gadget: The physical interaction is taken to be a ZX Hamiltonian, whose dressed form is expressed through modified coupling coefficients.The construction accounts for the effects of dressing when the physical interaction between qubits i and j is ZX.
- C. The ZZ from ZX gadget: Only the local Z field strengths are modified in this gadget.The perturbation parameters and penalty scale are chosen so the self-energy approximates the target with controlled error.
- C. The ZZ from ZX gadget: The construction achieves O(ǫ) approximation error when the penalty scale satisfies the stated inverse-power conditions.The error bound includes the condition ||V||^4δ^-3 < ǫ, requiring r ≥1.
D. The XX from ZX gadget
The XX from ZX gadget uses an ancilla penalty in the σx basis and perturbative coupling to realize an effective XX interaction while controlling dressing effects and approximation error.
- D. The XX from ZX gadget: The penalty Hamiltonian separates low- and high-energy subspaces in which ancilla k occupies |+⟩ and |−⟩, respectively.V1 acts within the subspaces, whereas V2 couples them and is zero within each subspace.
- D. The XX from ZX gadget: The gadget applies V = V1 + V2 to qubits i, j, and ancillary qubit k, with the penalty term on k defined in the σx basis.Fig. 3 represents the perturbative Hamiltonian from Eq. (34) and includes an overall energy shift of A/2.
- D. The XX from ZX gadget: The desired XX term appears at second order, while third-order terms dress the physical interaction Y between qubits i and j.The low-energy self-energy expansion includes the dressed interaction and an explicit σx_iσx_j contribution.
- D. The XX from ZX gadget: The physical interaction Y is assumed to be ZX, and dressing modifies only the local X field strengths.The dressed Hamiltonian is described using new coupling strengths.
- D. The XX from ZX gadget: The self-energy can be made O(ǫ) close to the target Hamiltonian by choosing δ ≥ Ēǫ^-1.The expansion is taken in the regime z = O(1) ≪ δ.
- D. The XX from ZX gadget: Together with the ZZ and σzσx constructions, the XX gadget completes the realization of target interactions needed for the theorem.The summary states that the gadgets realize σxσx and σzσz terms with O(ǫ) error.
II. CONCLUSION
The paper presents simple, experimentally relevant Hamiltonians for universal adiabatic quantum computation and identifies them as the simplest known QMA-complete 2-local Hamiltonians.
- II. CONCLUSION: The σxσx coupler is realizable through capacitive coupling of flux qubits and spin models implemented with polar molecules.A σzσx coupler for flux qubits is also identified.
- II. CONCLUSION: The ZX and ZZXX Hamiltonians enable gate-model, autonomous, measurement-based, and universal adiabatic quantum computation.The paper also notes potential usefulness for quantum annealing.
- II. CONCLUSION: The reported Hamiltonians are intended to support practical construction of a universal adiabatic quantum computer.Their relevance follows from both their simple interaction structure and identified physical implementations.