Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable...

Area of Science:

• Quantum computing
• Computational complexity
• Algorithm analysis

Background:

• The quantum approximate optimization algorithm (QAOA) is a prominent quantum algorithm for optimization.
• Its capability to solve classically intractable problems is not yet fully understood.
• The low autocorrelation binary sequences (LABS) problem presents a significant computational challenge.

Purpose of the Study:

• To investigate the performance of QAOA on the classically intractable LABS problem.
• To compare QAOA's scaling with state-of-the-art classical solvers.
• To demonstrate experimental progress in executing QAOA for LABS on quantum hardware.

Main Methods:

• Extensive noiseless numerical simulations of QAOA up to 40 qubits.
• Comparison with branch-and-bound solvers for the LABS problem.
• Experimental execution of QAOA on Quantinuum trapped-ion processors with error detection.

Main Results:

• QAOA with fixed parameters demonstrates better runtime scaling than classical branch-and-bound solvers for LABS.
• The combination of QAOA and quantum minimum finding achieves the best empirical scaling for the LABS problem.
• Successful experimental demonstration of QAOA for LABS on trapped-ion quantum processors.

Conclusions:

• QAOA shows potential for tackling classically intractable optimization problems.
• QAOA, particularly when combined with quantum minimum finding, offers a promising algorithmic approach for quantum speedups.
• Experimental validation on trapped-ion processors supports QAOA's utility in practical quantum computation.