# Presentation: 119273

## Merlin-Arthur Games and Stoquastic Hamiltonians 

- B.M. Terhal, IBM Research
- based on work with Bravyi, Bessen, DiVincenzo & Oliveira.
- quant-ph/0611021 & quant-ph/0606140

## Quantum Complexity Theory

- Heuristic methods have been developed to solve classical problems (simplex method for linear programming, simulated annealing, Monte Carlo methods).
-  Classical complexity theory aims at making rigorous what problems can be solved efficiently and which ones are hard (and how hard they are).
- Physicists have developed (heuristic) methods to solve quantum problems (perturbation theory, WKB approximation, mean-field theory etc. etc.)
-  Quantum complexity theory aims at showing which problems a classical machine can solve efficiently, which ones a quantum computer can do better, and which ones are hard and how hard.
- The how hard-aspect is sometimes characterized in terms of interaction of an ordinary human being (Arthur) with an all-powerful prover (Merlin).

## NP

- Success story of complexity theory in physics: the notion of NP and
- NP-completeness.
- Is the question PNP a mathematics or physics question:
- A mathematical question with physical consequences, a universe where
- P=NP would probably be much different.
- Useful notion of NP-completeness.

## Satisfiability

- The k-SAT problem:
- Let x be an n-bit string.
- Let Ci be a constraint that depends only on the value of some k bits of x. A bitstring x can either satisfy or not satisfy the constraint Ci depending on the value of these k bits.
- Take a set of constraints Ci for i=1 to m with m=poly(n).
- Q: Is there a bit string that satisfies all m constraints?
- If yes, a prover can give you the bitstring and you can check the m constraints.
- If no, no prover can convince you that there is such bitstring.
- k-SAT is NP-complete

## Beyond NP

- What is the physical relevance of these classes?
- What are the ‘complete’-problems?

- QMA (or Quantum NP)

- MA

- NP

- Stoquastic MA

- MA ~probabilistic version of NP
- QMA ~quantum version of NP

## Definitions

|  | Interaction between Arthur
and Merlin | Arthur runs | Arthur runs V(..,x) |
| --- | --- | --- | --- |
| NP | Proof y by Merlin | Polynomial time algorithm (in |x|) with input y | If Yes, there exists a y, V(y,x)=1
If No, for all y, V(y,x)=0 |
| QMA | Quantum proof  by Merlin
 | Poly-time quantum 
algorithm
 | If Yes, there exists a state  , Prob(V;,x)   2/3
If No, for all states , Prob(V,,x)  1/3
 |
| MA | Proof y by Merlin | Poly-time probabilistic 
algorithm with input y | If Yes, there exists a y, Prob(V;y,x)=1
If No, for all y Prob(V;y,x)  1/3

 |

## The Story

-  The Quantum Ising Spin Glass problem is complete for QMA.
- Note that QMA allows for an error if the answer is yes (if yes, Arthur decides yes with probability at least (say) 2/3). Note that NP and MA
- do not have this error (MA allows for error in no-instances)
-  For the class QMA1 in which Arthur decides Yes with probability 1,
- the complete problem is the quantum satisfiability problem.
-  For MA the complete problem (first known MA-complete problem) is the stoquastic satisfiability problem. Relation to stoquastic Hamiltonians and classical satisfiability problem.
-  For stoquastic MA (weird class) the complete problem is the
- Stoquastic Ising Spin Glass problem.
- Beliefs in computer science: MA=NP=Stoquastic MA=AM

## Quantum Ising Spin Glass

- Quantum Ising Spin Glass (QISP):
- Given is a k-local Hamiltonian H=i Hi on n qubits and
- given  <   (with |-|  1/poly(n)). ||Hi||  poly(n).  We are promised that
- the ground-state energy (H)) is either    or  .
- Q: Is there a state with energy less than ?
- k-local means that the Hamiltonian is a sum of terms each of which acts
- non-trivially on at most k qubits.
- Kitaev: 5-local QISP is QMA-complete.
- Strongest results to date: 2-local QISP on qudits of a 1-D chain is
- QMA-complete (Aharonov,Gottesman, Kempe, Irani).
- Quantum Ising Spin glass is also called the local Hamiltonian problem.

## Quantum k-SAT

-  Ground-state of Hamiltonian is not always the one which is the ground-state of
- each individual term in the Hamiltonian. `frustration free property’
- So a different question to ask is: is there a state which is the ground-state
- of each local term in a quantum Ising spin glass Hamiltonian?
- Such state satisfies all local constraints. We can always shift the Hamiltonian
- such that the energy of this satisfying state is 0.
- Then the satisfying state has the property of being in the null-space of
- a bunch of k-local projectors....
- Quantum k-SAT on n qubits:
- Given a set of k-local projectors i on n qubits and   1/poly(n). Either
- 	- there is a state that is in the space spanned by all projectors i.
- (yes-instance),
- 	- or any state  there exists an i such that <| i |>  1-  (no-instance).
- (Note we are switching null-space and +1 space here...)

## Connection with classical k-SAT

- Classical k-SAT problem can be viewed as quantum k-SAT where
- the projectors are diagonal in computation basis.
- Some bit-strings in +1 space, some in null-space.
- Promise on no-instances is not needed.
- There is something in between diagonal k-local projectors and
- general k-local projectors....the stoquastic k-SAT problem

## Stoquastic Hamiltonians

- Physicists have known for a long time that not all Hamiltonians are created equal. Some are more quantum than other’s.
- Physics lingo: “Avoid the sign-problem”, “Quantum ground-state problem mapped onto classical partition function problem”, Green’s function Monte Carlo techniques”
- What is exactly the property of these Hamiltonians and what does this feature
- do to the complexity of the lowest-eigenvalue problem, the power of these
- Hamiltonians for implementing an adiabatic quantum computer, etc?

## Stoquastic Hamiltonians

- General definition: stoquastic Hamiltonians are real and have non-positive off-diagonal elements in some standard (product) basis |i>.
- Then G=I-t H for some (real) t is a non-negative matrix (in this basis) or
- consider the nonnegative Gibbs matrix G=e-H
- .
- Perron-Frobenius: Eigenvector with largest eigenvalue of G (ground-state of H) has the property that  |>=i i |i> where i  0.
- P(i)=i/i i  is a probability distribution.
- Our excuses for the word stoquastic....introduced not without reason.

## Examples of Stoquastic Hamiltonians

- Particles in a potential; Hamiltonian is a sum of a diagonal potential term in
- position |x> and off-diagonal negative kinetic terms (-d2/dx2).
- All of classical and quantum mechanics.
- Quantum transverse Ising model
- Ferromagnetic Heisenberg models (modeling interacting spins on lattices)
- Jaynes-Cummings Hamiltonian (describing atom-laser interaction),
- spin-boson model, bosonic Hubbard models, Bose-Einstein condensates etc.
- D-Wave’s Orion quantum computer...
- Non-stoquastic are typically fermionic systems, charged particles in a
- magnetic field.
- Stoquastic Hamiltonians are ubiquitous in nature.
- Note that we only consider ground-state properties of these Hamiltonians.

## Local Stoquastic Hamiltonians

- Remember k-local Hamiltonians are those that can be written as a
- sum of terms acting non-trivially on k qubits (qudits).
- Our results hold for local term-wise stoquastic Hamiltonians, each
- local term is stoquastic.
- Side Remark:
- Local termwise-stoquastic is not necessarily the same as local stoquastic:
-  2-local on qubits: termwise-stoquastic is stoquastic.
-  3-local on qubits: there is a counter-example of a Hamiltonian which is
- stoquastic but not term-wise stoquastic (also allowing 1-local unitary
- transformations).

## Stoquastic k-SAT

- Quantum k-SAT: remember we have a collection of projectors i (m=poly(n)
- of them). Now we demand that i are projectors with nonnegative entries in the
- computational basis. Thus H=i (I-i) is stoquastic.
- (in fact termwise-stoquastic, i.e. each Hi is stoquastic).
- How to prove that this problem is a complete problem for the classical class
- MA? Sketch of ideas:
- Completeness for a problem Q:
- 1. Prove that a problem Q is in the class.
- 2. Prove that any problem in the class can be reduced to Q (“if we can solve Q
- we can solve any problem in the class”)

## Stoquastic k-SAT

- Completeness for a problem Q:
- 1. Prove that a problem Q is in the class.
- 2. Prove that any problem in the class can be reduced to Q (“if we can solve Q
- we can solve any problem in the class”)
- Kitaev showed 2. for the quantum Ising spin glass by converting Arthur’s
- quantum verifying circuit into a Hamiltonian.
- We do 2. by treating a probabilistic verifying circuit as a restricted quantum
- circuit and applying Kitaev’s construction to obtain a restricted Hamiltonian.
- This Hamiltonian turns out to be stoquastic!
- In MA, if answer is yes, verifying circuit with proof always outputs yes
- (zero error)
- This results in a Hamiltonian where the ground-state (in the yes-case)
- satisfies each local constraint, i.e the stoquastic k-SAT problem.

## Containment in MA

- .
- Given a set of k-local projectors i (m=poly(n) of them)
- with nonnegative entries in the computational basis and   1/poly(n).
- -Yes-instance: there is a state that is in the space spanned by all
- projectors i.
- - No-instance: for any state  there exists an i such that <| i |>  1-
- Consider the nonnegative (symmetric) matrix G= m-1 i i.
- - Yes-instance: the largest eigenvalue of G is 1.
- - No-instance: the largest eigenvalue of G is less than 1-/m

## Containment in MA

- The idea of the proof:
- Merlin provides starting point to a random walk on n bit strings. The random walk is a true random walk in case of a Yes-instance. Arthur will test whether the transition probabilities during the walk sum up to 1 and do a final test (which depends on the starting point). In case of a no-instance there is a high probability that some test fails. If a test fails, Arthur decides No.

## MA (versus NP)

- Special version of stoquastic k-SAT problem can be viewed as
- a bunch of constraints (like SAT) and relations.
- Graph with vertices which are n-bit strings.
- Vertex x is good when bit-string is in the support of all projectors.
- We have an edge between vertex x and x’ when there exists an i such that <x|i|x’> > 0. Graph has degree m (is poly(n))
- Special Stoquastic k-SAT problem that is still MA-complete:
- Does the graph contain a disconnected sub-graph of only good vertices?
- How to prove that there is such sub-graph when sub-graph can be
- exponentially large? Walk around on sub-graph starting from point provided by prover. Promise guarantees that in the no-case after some poly(n) time you will get to a bad vertex.
- Note that you would explore only a set with poly(n) vertices (chosen by random walk)

## Discussion

- Adiabatic evolution with general (local) Hamiltonians is universal for
- quantum computation.
- What is the power of adiabatic quantum computation with stoquastic
- (local) Hamiltonians? Can we classically simulate it?
- Do heuristic methods/approximation algorithms work better
- for stoquastic Hamiltonians? Problem is still `hard’ but more ‘classically hard’.