arXiv:1409.7745 · Physical Review Letters

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

David Gosset, Barbara M. Terhal, Anna Vershynina

Published Apr 6, 2015• 47 citations

Abstract

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.

DOI: 10.1103/physrevlett.114.140501

Related papers

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

Jan 1, 201622 citations

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

Barbara M. Terhal, Seth Lloyd

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.

Institute of Physics eBooksFeb 1, 20161 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.01278New Journal of PhysicsFeb 12, 201623 citations

Universal quantum walks and adiabatic algorithms by 1D Hamiltonians

Bradley A. Chase, Andrew J. Landahl

We construct a family of time-independent nearest-neighbor Hamiltonians coupling eight-state systems on a 1D ring that enables universal quantum computation. Hamiltonians in this family can achieve universality either by driving a continuous-time quantum walk or by terminating an adiabatic algorithm. In either case, the universality property can be understood as arising from an efficient simulation of a programmable quantum circuit. Using gadget perturbation theory, one can demonstrate the same kind of universality for related Hamiltonian families acting on qubits in 2D. Our results demonstrate that simulating 1D chains of spin-7/2 particles is BQP-hard, and indeed BQP-complete because the outputs of decision problems can be encoded in the outputs of such simulations.

arXiv:0802.1207Feb 8, 200816 citations

Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation

Dorit Aharonov, Wim van Dam, Julia Kempe +3 more

The model of adiabatic quantum computation is a relatively recent model of quantum computation that has attracted attention in the physics and computer science communities. We describe an efficient adiabatic simulation of any given quantum circuit. This implies that the adiabatic computation model and the standard circuit-based quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models allows one to state the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of Hamiltonians.

SIAM ReviewJan 1, 2008395 citations

On fixed-gap adiabatic quantum computation

Ari Mizel

Quantum computation has revolutionary potential for speeding algorithms and for simulating quantum systems such as molecules. We report here a quantum computer design that performs universal quantum computation within a single non-degenerate ground state protected from decohering noise by an energy gap that we argue is system-size-independent. Closely analogous to a traditional electric circuit, it substantially changes the requirements for quantum computer construction, easing measurement, timing, and heating problems. Using the standard adiabatic condition, we present evidence that this design permits "quantum concurrent processing" distributing a quantum computation among extra qubits to perform a quantum algorithm of N gates in an amount of time that scales with the square root of N. One consequence of our work is a fixed gap version of adiabatic quantum computation, which several arguments hinted could be impossible.

arXiv:1002.0846Feb 4, 20101 citation