Lower Bounds on Circuit Depth of the Quantum Approximate Optimization Algorithm

Understand

The quantum approximate optimization algorithm (QAOA) is a method of approximately solving combinatorial optimization problems.

• While QAOA is developed to solve a broad class of combinatorial optimization problems, it is not clear which classes of problems are best suited for it.
• One factor in demonstrating quantum advantage is the relationship between a problem instance and the circuit depth required to implement the QAOA method.
• As errors in NISQ devices increases exponentially with circuit depth, identifying lower bounds on circuit depth can provide insights into when quantum advantage could be feasible.