Nonstoquastic Hamiltonians and quantum annealing of an Ising spin glass

Layla Hormozi, Ethan Brown, Giuseppe Carleo, Matthias Troyer

Physical review. B./Physical review. B · 2017 · 98 citations · 23 references

DOIFull text

Open access

Concepts

TL;DR

Quantum annealers use quantum effects to solve hard optimization problems, yet it remains unclear when they outperform classical methods. The study investigates whether quantum annealers that are hard to simulate classically—specifically nonstoquastic systems—offer greater optimization power than their stoquastic counterparts. The authors compare stoquastic annealers, which are efficiently classically simulable, with nonstoquastic annealers, which lack efficient classical treatments, to assess their performance on a prototypical optimization problem. On average, stoquastic annealers excel on easier instances, whereas nonstoquastic annealers gain a significant advantage on the hardest instances.

Abstract

Quantum annealers are computing machines that utilize quantum effects to solve hard optimization problems. Understanding the circumstances under which quantum annealers are more efficient than other optimization methods is a challenging open problem. A clue to this conundrum comes from studying the complexity of quantum annealers. In general, the complexity of a physical system relates to how efficiently the system can be simulated by classical algorithms. One then asks: if some class of quantum annealers are hard to simulate classically, are they also more powerful optimization machines? Here, the authors study quantum annealers belonging to two different complexity classes: the so-called ``stoquastic'' systems, which can be efficiently simulated with classical algorithms, and ``nonstoquastic'' systems, currently with no efficient classical treatment. Applied to a prototypical optimization problem, the authors observe that, on average, the stoquastic systems perform better on easier instances of the problem, while the more complex nonstoquastic annealers show significant advantage when applied to the hardest instances. The authors conjecture that the performance of the nonstoquastic Hamiltonians is closely related to their internal structure during the annealing process and elucidate how properties such as magnetic frustration can play a key role in devising more powerful quantum annealers.

References

23