Rostock 2019 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
Q: Fachverband Quantenoptik und Photonik
Q 3: Quantum Information (Quantum Computing) I
Q 3.5: Talk
Monday, March 11, 2019, 11:45–12:00, S HS 001 Chemie
Comparison of QAOA with Quantum and Simulated Annealing — •Michael Streif1,2 and Martin Leib1 — 1Data:Lab, Volkswagen Group, Ungererstr. 69, 80805 München, Germany — 2Physikalisches Institut, Universität Freiburg, Herrmann-Herder-Straße 3, 79104 Freiburg, Germany
Demonstrating the advantage of quantum computers over their classical counterparts is the space race of our current scientific world. Good candidates in the near future are hybrid algorithms, which combine the power of digital computation with the quantum nature. The Quantum Approximate Optimization Algorithm (QAOA) is a such a hybrid algorithm, designed to solve combinatorial optimization problems, and showing promising indication for near-term quantum supremacy. Consequently, it is crucial to find suitable problems and to gauge strengths and weaknesses of QAOA within the zoo of available classical and quantum algorithms. We present a comparison between QAOA and two widely studied competing methods, Quantum Annealing (QA) and Simulated Annealing (SA). To achieve this, we define a subclass of k-local spin glass instances, characterized by their spectral properties, which are exactly solvable with QAOA. Within this class, we find 4-local instances which are hard to solve with both QA and SA. Our results thus define a first demarcation between QAOA, SA and QA.