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: amenable to Quantum Monte Carlo techniques
without sign-problems, “Quantum ground-state problem mapped
onto classical partition function problem”
What is exactly the property of these Hamiltonians and what
does this feature do to the complexity of determining the lowesteigenvalue, the power of these Hamiltonians for implementing
an adiabatic quantum computer, etc?
Stoquastic Hamiltonians
More examples of stoquastic
Stoquastic 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
Why Complexity of Stoquastic
• Understand power of stoquastic adiabatic computation. Does it go
beyond classical computation?
Remember general adiabatic quantum computation is universal for
quantum computation.
• Common stoquastic physical systems which are studied by classical
Monte Carlo techniques; does a quantum computer provide any
advantage. Can we do a rigorous analysis of these heuristic
• Nonnegative sparse matrices such as G are not uncommon in the real
world, e.g. adjacency matrix of internet graph of which Google’s
Pagerank algorithm determines the largest eigenvector (see recent
proposal for a stoquastic adiabatic algorithm to determine PageRank
vector by Garnerone, Zanardi & Lidar)
Adiabatic Quantum
Computation (AQC)
Quantum Simulated Annealing
A class of stoquastic frustrationfree Hamiltonians
Technical Question
Technical Solution
Technical Solution
Conclusion for stoquastic
frustration-free AQC
Questions for stoquastic
Different Approach
Sampling from ground-state
Simulating stoquastic AQC?
Partition Function Estimation
Partition Function Estimation
Overview (if you like complexity

similar documents