AQC 2016 - Adiabatic Quantum Computer vs. Diffusion Monte Carlo

Channel:
United States Google TechTalks
Subscribers:
348,000
Published on ● Video Link: https://www.youtube.com/watch?v=D7FIHejPA68


Duration: 22:07
2,529 views
11

A Google TechTalk, June 29, 2016, presented by Stephen Jordan (NIST)
ABSTRACT: While adiabatic quantum computation using general Hamiltonians has been proven to be universal for quantum computation, the vast majority of research so far, both experimental and theoretical, focuses on stoquastic Hamiltonians. Conventional wisdom amongst Monte Carlo practitioners states that Monte Carlo simulations of stoquastic adiabatic computation will not suffer from the sign problem and will therefore converge efficiently. If this could be turned into a theorem it would prove that stoquastic adiabatic computers are incapable of exponential speedup over classical computation.

The two major classes of Monte Carlo simulation algorithms are path integral Monte Carlo and diffusion Monte Carlo. In 2013, Hastings constructed a class of counterexamples in which path integral Monte Carlo will fail to efficiently simulate stoquastic adiabatic dynamics due to topological obstructions. Diffusion Monte Carlo algorithms should not be affected by topological obstructions. We are nevertheless able to construct a counterexample in which a non-topological obstruction prevents diffusion Monte Carlo from efficiently simulating a stoquastic adiabatic process. On typical instances such simulations may nevertheless work well. In fact, we introduce a new variant of diffusion Monte Carlo, which we call Substochastic Monte Carlo, tailored to simulating stoquastic adiabatic processes.

In practice, we find that this performs so well that our Monte Carlo simulations of adiabatic optimization are good classical optimization heuristics in their own right, competitive with the best previous known heuristic solvers for Max-kSAT at k=2,3,4.

Michael Jarret, Joint Center for Quantum Information and Computer Science, University of Maryland, Brad Lackey, Joint Center for Quantum Information and Computer Science, University of Maryland

Presented at the Adiabatic Quantum Computing Conference, June 26-29, 2016, at Google's Los Angeles office.



Other Videos By Google TechTalks


2016-11-21AQC 2016 - Controlled Interactions Between Superconducting Qubits for Adiabatic Quantum Simulations
2016-11-21AQC 2016 - Testing Adiabatic Quantum Computers Using Simple Quantum Simulation
2016-11-21AQC 2016 - A Quantum-Assisted Algorithm for Sampling Applications in Machine Learning
2016-11-10What is in Common Between Quantum Computer and Solar System?
2016-11-10Simulating the Quantum World on a Classical Computer
2016-10-20AQC 2016 - Coupled Quantum Fluctuations and Quantum Annealing
2016-10-20AQC 2016 - Max-k-SAT, Multi-Body Frustration, & Multi-Body Sampling on a Two Local Ising System
2016-10-20AQC 2016 - Boosting Quantum Annealer Performance via Quantum Persistence
2016-10-20AQC 2016 - Avoiding Negative Sign Problem in Simulation of Quantum Annealilng
2016-10-20AQC2016 - Classical Modeling of Quantum Tunneling
2016-10-20AQC 2016 - Adiabatic Quantum Computer vs. Diffusion Monte Carlo
2016-10-20AQC 2016 - Floquet Quantum Annealing with Superconducting Circuit
2016-10-20AQC 2016 - Simulated Annealing Comparison Between All-to-All Connectivity Schemes
2016-10-20AQC 2016 - Parity Adiabatic Quantum Computing
2016-10-20AQC 2016 - Towards Quantum Supremacy with Pre-Fault-Tolerant Devices
2016-10-20AQC 2016 - Scaling Analysis & Instantons for Thermally-Assisted Tunneling and Quantum MC Simulations
2016-10-20AQC 2016 - The Quantum Spin Glass Transition on the Regular Random Graph
2016-10-20AQC 2016 - A Fully-Programmable Measurement-Feedback OPO Ising Machine with All-to-All Connectivity
2016-10-20AQC 2016 - Origin and Suppression of 1/f Magnetic Flux Noise
2016-10-20AQC 2016 - Building Quantum Annealer v2.0
2016-10-20AQC 2016 - Roadmap for Building a Quantum Computer


Tags:
google techtalks
quantum computing