Faster algorithms for combinatorial optimization could prove transformative for diverse areas such as logistics, finance and machine learning.
A team of researchers at Google Research has demonstrated the application of the Google Sycamore superconducting qubit quantum processor to combinatorial optimization problems with the Quantum Approximate Optimization Algorithm (QAOA).
They studied performance for problems defined on the planar connectivity graph native to the Google Sycamore hardware. However, they also applied the QAOA to the Sherrington–Kirkpatrick model and MaxCut, non-native problems that require extensive compilation to implement.
For hardware-native problems, which are classically efficient to solve on average, they obtained an approximation ratio that is independent of problem size and observed that performance increases with circuit depth.
For problems requiring compilation, performance decreased with problem size. Circuits involving several thousand gates still present an advantage over random guessing but not over some efficient classical algorithms.
They results suggest that it will be challenging to scale near-term implementations of the QAOA for problems on non-native graphs.
As these graphs are closer to real-world instances, the team has suggested more emphasis should be placed on such problems when using the QAOA to benchmark quantum processors.
The work has been published in Nature Physics.
The post QAOA for non-planar graph problems on a planar superconducting processor appeared first on Swiss Quantum Hub.
