Investigating Quantum Annealing on large arbitrary graphs using Truncated Wigner Approximation

Quantum annealing (QA) is a heuristic optimization method that can be used to approximate solutions for NP-hard problems like the traveling salesman problem, Max-Cut, etc., which are of great importance to industry. QA is a strong contender for achieving quantum supremacy for these kinds of problems on near term quantum computers. However, there is no mathematical proof for the quantum advantage and current experimental scales are too small to draw objective conclusions. We use truncated Wigner approximation (TWA) a semiclassical approximation which, through Monte-Carlo sampling, takes lowest order quantum-fluctuations into account, to numerically simulate QA on classical hardware. Through TWA we are able to simulate QA for fully arbitrary graphs with sizes exceeding several hundreds of nodes, which allows us to investigate the scaling of the annealing time with the graph size for fixed approximation errors and compare the behavior of QA to classical known P/NP-Hard approximation limits.