Utilizing discrete truncated Wigner approximation to test QAOA and QA on large graph optimization problems

The quantum approximate optimization algorithm (QAOA) and quantum annealing (QA) are both contenders to achieve quantum supremacy on Near-Term non fault-tolerant quantum computers and therefore an advantage on particularly hard problems, such as NP complete ones. However, there is no mathematical proof for the quantum advantage and current experimental scales are too small. Thus there is a need for better understanding of the performance of QAOA and QA on intermediate scales and their sensitivity to dissipation. To make larger system sizes computationally accessible we make use of the discrete truncated Wigner approximation (DTWA), a semiclassical approximation which, through Monte-Carlo sampling, takes lowest order quantum-fluctuations into account. Using DTWA it is possible to simulate several hundreds of spins and therefore reach system sizes which allow real world problems to be solved and a one-to-one comparison to state-of-the-art experiments.