Can I read Obstructions To Classically Simulating The Quantum Adiabatic Algorithm on EtoBox?

Obstructions To Classically Simulating The Quantum Adiabatic Algorithm by Hastings, M. B.; Freedman, M. H. is a scholarly article available to read on EtoBox.

What is Obstructions To Classically Simulating The Quantum Adiabatic Algorithm about?

We consider the adiabatic quantum algorithm for systems with "no sign problem", such as the transverse field Ising mode, and analyze the equilibration time for quantum Monte Carlo (QMC) on these systems. We ask: if the spectral gap is only inverse polynomially small, will equilibration methods based on slowly changing the Hamiltonian parameters in the QMC simulation succeed in a polynomial time? We show that this is not true, by constructing counter-examples. Some examples are Hamiltonians where the space of configurations where the wavefunction has non-negligible amplitude has a nontrivial fundamental group, causing the space of trajectories in imaginary time to break into disconnected components, with only negligible probability outside these components. For the simplest example we give with an abelian fundamental group, QMC does not equilibrate but still solves the optimization problem. More severe effects leading to failure to solve the optimization can occur when the fundamental group is a free group on two generators. Other examples where QMC fails have a trivial fundamental group, but still use ideas from topology relating group presentations to simplicial complexes. We defi

Author

Hastings, M. B.; Freedman, M. H.

Published

2013

Language

EN