Qubit-efficient quantum combinatorial-optimization solver
Abstract
Quantum optimization solvers typically rely on one-variable-to-one-qubit mapping. However, the low qubit count on current quantum computers is a major obstacle in competing against classical methods. Here, we develop a qubit-efficient algorithm that overcomes this limitation by mapping a candidate bit string solution to an entangled wave function of fewer qubits. We propose a variational quantum circuit generalizing the quantum approximate optimization ansatz (QAOA). Extremizing the ansatz for Sherrington-Kirkpatrick spin glass problems, we show valuable properties such as the concentration of ansatz parameters and derive performance guarantees. This approach could benefit near-term intermediate-scale and future fault-tolerant small-scale quantum devices.
Fields of Study & Subjects
Quantum Computing Algorithms and Architecture
Publication details
- Journal / source
- Physical Review Applied
- Publisher
- American Physical Society (APS)
- Volume
- 25
- Issue
- 3
- Publication date
- 23 February 2026
- Language
- EN