This question refers principally to the article where for a low-depth circuit QAOA, the output cannot be efficiently simulated classically. I am wondering how this kind of quantum supremacy matters for optimization. Any insights would be interesting here.


In the article you mentioned it is said that classical algorithms can beat some cases of (quantum ) QAOA's as is proved in this article. So finding cases where quantum QAOA can still beat classical algorithms and can run on NISQ devices with low depth circuits is still exciting and promissing.

The article uses plausible conjectures from complexity theory to show that there are choices of γ, β and cost function C for which the output of a quantum computer running the (p = 1) QAOA could not be mimicked with a classical device.

Quantum supremacy is not necessary for optimization problems but can it make more worthwhile. In a recent paper it is shown that you really can find quantum speedup using a few hundreds of qubits.

In the mean time you can try solving optimization problems with Qiskit or pyQuil with some max-cut examples on my github.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.