Paper Image

Quantum optimization of large combinatorial problems with few qubits

Published on:

17 January 2024

Primary Category:

Quantum Physics

Paper Authors:

Marco Sciorilli,

Lucas Borges,

Taylor L. Patti,

Diego García-Martín,

Giancarlo Camilo,

Anima Anandkumar,

Leandro Aolita


Key Details

Encodes optimization variables into multi-qubit quantum correlations, achieving polynomial compression

Number of parameters and circuit depth scale mildly with problem size

Built-in mitigation of barren plateaus from qubit compression

Numerical solutions competitive with state-of-the-art classical algorithms

17-qubit experiment produces solutions beyond hardness threshold for 2000 variables

AI generated summary

Quantum optimization of large combinatorial problems with few qubits

This paper introduces a new quantum optimization algorithm that can solve large combinatorial optimization problems using only a small number of qubits. It encodes the optimization variables into quantum correlations across multiple qubits, achieving a polynomial compression in qubit number compared to problem size. Remarkably, this compression intrinsically mitigates barren plateaus. The algorithm displays good performance: solutions for problems of size 2000-7000 compete with state-of-the-art classical algorithms. An experiment with 17 qubits produced solutions beyond the computational hardness threshold for a 2000-variable problem.

Answers from this paper


No comments yet, be the first to start the conversation...

Sign up to comment on this paper

Sign Up