Can quantum adiabatic evolution solve optimization problems much faster than classical computers? One piece of evidence for this has been their apparent advantage in "tunneling" through barriers to escape local minima. However, I will argue that quantum Monte Carlo is at most polynomially slower than stoquastic quantum adiabatic optimization under a wide variety of settings.
I will then discuss some prospects for demonstrating quantum supremacy with a near term quantum computer. I will explain the difficulties in achieving this using adiabatic evolution and will explain the possibility of achieving this with low depth quantum circuits.
This is based on joint work with Elizabeth Crosson (arXiv:1601.03030)
and Edward Farhi (arXiv:1602.07674).
Copyright. All Rights Reserved.