Towards large-scale quantum optimization solvers with few qubits

Area of Science:

• Quantum Computing
• Combinatorial Optimization
• Algorithm Development

Background:

• Quantum computing offers potential for more efficient combinatorial optimization solvers.
• Current mainstream quantum approaches require a large number of qubits, limiting near-term applications.
• A bottleneck exists in developing practical quantum advantage for optimization problems.

Purpose of the Study:

• Introduce a qubit-efficient variational solver for MaxCut problems.
• Address the limitations of qubit requirements in near-term quantum hardware.
• Demonstrate high performance and mitigation of barren plateaus.

Main Methods:

• Developed a variational solver for MaxCut problems using n qubits for m binary variables.
• Analyzed the scaling of parameters and circuit depth.
• Analytically proved super-polynomial mitigation of barren plateaus through qubit-efficient encoding.

Main Results:

• Numerical simulations for m=7000 yielded solutions competitive with state-of-the-art classical solvers.
• Experiments with 17 trapped-ion qubits for m=2000 achieved MaxCut approximation ratios beyond the hardness threshold (0.941).
• The solver exhibits mild linear and sublinear scalings in parameters and circuit depth, respectively.

Conclusions:

• The proposed qubit-efficient encoding mitigates barren plateaus, enhancing quantum solver performance.
• The findings present a promising route for solving commercially relevant problems on near-term quantum devices.
• This work offers valuable heuristics for quantum-inspired solvers.