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.7: Talk

Monday, March 11, 2019, 12:15–12:30, S HS 001 Chemie

Correspondence of Quantum and Classical Hardness for QAOA Algorithms with MAX-SAT problems — •Martin Leib and Michael Streif — Data:Lab Volkswagen AG, Munich, Germany

The Quantum Approximate Optimization Algorithm (QAOA) has emerged in recent years as one of the leading contenders of quantum algorithms that can be executed on noisy intermediate scale quantum computing devices. QAOA belongs to a class of classical-quantum hybrid algorithms where a parametrized quantum circuit is optimized by a classical outer training-loop. We examine potential signs of quantum advantage by gauging the complexity involved in the outer classical training loop as well as the entanglement build up in the quantum circuit during training and for the fully trained circuit. To achieve this we create random instances of MAX-SAT problems where we tune the complexity with the ratio of variables to clauses. We solve these instances with QAOA runs and examine for each complexity class the involved complexity of the outer training loop and the amount of entanglement build up during training and for the final trained circuit.