Hamiltonian Complexity Initiative

What is the computational complexity of simulating a given Hamiltonian? What is the computational complexity of finding its ground state?

These questions are fundamental to condensed matter physics, to computational complexity but also have deep practical merit. Ground state quantum computation (e.g. adiabatic quantum computation) utilize properties of the ground states of Hamiltonians to compute.

Adiabatic quantum computing generally relies on the idea of embedding a problem instance into a physical system, such that the systems lowest energy configuration stores the problem instance solution. While any quantum algorithm can be run on a universal adiabatic quantum computer in principle, combinatorial optimisation problems appear to be the most suitable choice for near-term devices. Recent experimental progress has resulted in annealers with hundreds of spins and studying the quantum properties of these devices has sparked dramatic interest and debate in this rapidly growing area. More generally, several notable results have emerged on the topic of ground state computation and the quest for a universal adiabatic quantum computer continues.  These have paved a path towards a unified view of computer science and physics, formed by studying the computational complexity of evolving a physical system into its ground state.  Our work has been driven mainly by these questions:

  1. what is the simplistic model that realizes universal adiabatic quantum computation?
  2. how do you embed problems into the ground states of Ising lattices and (2.1) how do you best implement general perturbation gadgets (which reduce many body interactions into two-body ones)? and
  3. what are the best target applications for a quantum computer to outperform the best classical devices?

(Here is our organizational profile outlining the capacity of this research topic for funding bodies.)

What is the simplest universal adiabatic quantum computing model?

D-wave Systems Inc. creates devices that realize the Ising model.  We have proven that an additional XX interaction renders the ground-state energy problem universal for adiabatic quantum computing – establishing the contemporary experimental target.

Realizable Hamiltonians for Universal Adiabatic Quantum Computers 
Jacob Biamonte and Peter Love
Physical Review A 78, 012352 (2008)

The main result of this paper is well-regarded proof that the tunable sparse two-body model (with XX and ZZ interactions)

$$ h = \sum_{i,j}J_{ij}Z^iZ^j +\sum_{i,j}K_{ij}X^iX^j$$

has a QMA-complete (quantum analog of the complexity class, randomized NP) ground state problem.

How do you embed problems and reduce many-body interactions into two-body ones?

We have developed non-perturbative methods to decompose many-body Ising interactions into two-body interactions.  For further details, see our page on the Ising Hamiltonian formulation of Boolean operations and gates.

Non-perturbative k-body to two-body Commuting Conversion Hamiltonians and Embedding Problem Instances into Ising Spins
Jacob Biamonte
Physical Review A 77, 052331 (2008)

Ground State Spin Logic
James Whitfield, Mauro Faccin and Jacob Biamonte
European Physics Letters 99, 57004 (2012)

The above results are established for the case of the Ising model Hamiltonian.  To address the embedding program in the general case one relies on the so called, Hamiltonian gadgets.  In the following, we reduce the spectral gap needed to realize the common gadgets, and we further introduce gadgets which made it possible to realize quantum chemistry algorithms with adiabatic quantum computers.

Hamiltonian Gadgets with Reduced Resource Requirements
Yudong Cao, Ryan Babbush, Sabre Kais and Jacob Biamonte
Physical Review A 91, 012315 (2015)

What will universal adiabatic quantum computers be used for?

Developing dedicated simulators for physics and quantum chemistry seems to represent the best target application.  We  have devised protocols to simulate physics and chemistry using adiabatic quantum computers and addressed the general resource requirements needed to realize pertubative gadgets.

Adiabatic Quantum Simulators
Jacob Biamonte, Ville Bergholm, James Whitfield, Joe Fitzsimons and Alan Aspuru-Guzik
AIP Advances 1, 022126 (2011)

What are some of our references?

In 1982, Barahona [1] showed that finding the ground state of the random field Ising model is NP-hard. Such observations fostered approaches to solving problems based on classical ͓[2] and later quantum annealing [3]. The idea of using the ground-state properties of a quantum system for computation found its full expression in the adiabatic model of quantum computation [4, 5].

[1] On the computational complexity of Ising spin glass models, F. Barahona, J. Phys. A 15, 3241 (1982) [PDF]

[2] S. Kirkpatrick et al., Science 220, 671 (1983)

[3] J. Brooke, D. Bitko, T. Rosenbaum, and G. Aeppli, Science
284, 779 (1999)

[4]  Quantum Computation by Adiabatic Evolution, E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Science
292, 472 (2001) arXiv:quant-ph/0001106

[5]  Quantum Search by Local Adiabatic Evolution, Jeremie Roland, Nicolas J. Cerf, Phys. Rev. A 65, 042308 (2002) arXiv:quant-ph/0107015

Based on a series of results, the proof of the polynomial equivalence between quantum circuits and adiabatic evolutions by Aharonov et al. ͓[6].  Kempe, Kitaev, and Regev subsequently proved QMA-completeness of 2- LOCAL HAMILTONIAN ͓[7]. Oliveira and Terhal then showed that universality remains even when the two-local Hamiltonians act on particles in a subgraph of the two-dimensional ͑2D͒ square lattice ͓[8]. Any QMA-complete Hamiltonian may realize universal adiabatic quantum computation, and so these results are also of interest for the implementation of quantum computation.

[6] D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, SIAM J. Comput. 37, 166 (2007) arXiv:quant-ph/0405098

[7]  The Complexity of the Local Hamiltonian Problem, J. Kempe, A. Kitaev, and O. Regev, SIAM J. Comput. 35, 1070 (2006) arXiv:quant-ph/0406180

[8]  The complexity of quantum spin systems on a two-dimensional square lattice, R. Oliveira and B. Terhal, Quant. Inf, Comp. Vol. 8, No. 10, pp. 0900-0924 (2008) arXiv:quant-ph/0504050

Physical Review A 78, 012352 (2008)

Realizable Hamiltonians for Universal Adiabatic Quantum Computers 
Jacob Biamonte and Peter Love
Physical Review A 78, 012352 (2008)
[expand title=”abstract and link”]

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



AIP Advances 1, 022126 (2011)

Adiabatic Quantum Simulators
Jacob Biamonte, Ville Bergholm, James Whitfield, Joe Fitzsimons and Alan Aspuru-Guzik
AIP Advances 1, 022126 (2011)
[expand title=”abstract and link”]

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



Phys. Rev. A 91, 012315 (2015)

Hamiltonian gadgets with reduced resource requirements
Yudong Cao, Ryan Babbush, Jacob Biamonte and Sabre Kais
Phys. Rev. A 91, 012315 (2015)
[expand title=”abstract and link”]

Abstract. 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 2-body interactions. Therefore, universal adiabatic quantum computation requires a method for approximating quantum many-body Hamiltonians up to arbitrary spectral error using at most 2-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, 3- to 2-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 new gadgets to illustrate the tightness of our analytical bounds. Finally, we introduce a new 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.



Towards universal adiabatic quantum computation
The Second International Workshop on Adiabatic Quantum Computing (AQC 2013), IOP Institute of Physics, London,  March 6th to 8th

Related Popular Media

[vsw id=”ZW-PL8gNKTg” source=”youtube” width=”960″ height=”540″ autoplay=”no”]

Leave a Reply

Your email address will not be published. Required fields are marked *