# Towards large-scale quantum optimization solvers with few qubits

**Authors:** Marco Sciorilli, Lucas Borges, Taylor L. Patti, Diego García-Martín, Giancarlo Camilo, Anima Anandkumar, Leandro Aolita  
**arXiv:** [2401.09421](https://arxiv.org/abs/2401.09421)  
**Date:** 2024-01-17  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2401.09421v1/

## Key points

- Authors introduce a variational quantum solver for combinatorial optimizations with a large number of binary variables using only n qubits
- Number of parameters and circuit depth scale linearly and sublinearly in m, respectively
- Qubit-efficient encoding mitigates barren plateaus effectively, leading to unparalleled performance levels
- Solutions obtained are competitive in quality compared to state-of-the-art classical solvers for m=7000
- Experiment with n=17 trapped-ion qubits for m=2000 showcases MaxCut approximation ratios surpassing the hardness threshold of 0.941
- Research offers a novel approach for quantum-inspired solvers and addresses commercially-relevant problems using near-term quantum devices
- Provides insights into resource analysis through experimental deployments, highlighting precise quantum and classical resources
- Acknowledges support from various entities and individuals who contributed to the research efforts

## Summary

In their paper titled "Towards large-scale quantum optimization solvers with few qubits," authors Marco Sciorilli, Lucas Borges, Taylor L. Patti, Diego García-Martín, Giancarlo Camilo, Anima Anandkumar, and Leandro Aolita introduce a variational quantum solver designed for combinatorial optimizations involving a large number of binary variables ($m=\mathcal{O}(n^k)$) using only $n$ qubits, where $k>1$ is tunable. The study demonstrates that the number of parameters and circuit depth exhibit mild linear and sublinear scalings in $m$, respectively. Notably, the authors analytically establish that the specific qubit-efficient encoding incorporated in the solver effectively mitigates barren plateaus in a super-polynomial manner as an inherent feature. This breakthrough leads to unparalleled performance levels for quantum solvers. Through numerical simulations conducted for $m=7000$, the results show that the solutions obtained are competitive in quality when compared to state-of-the-art classical solvers. Additionally, an experiment involving $n=17$ trapped-ion qubits for $m=2000" showcases MaxCut approximation ratios surpassing the hardness threshold of 0.941. This achievement represents the highest quality achieved experimentally for problems of this scale. The findings presented by Sciorilli et al. not only offer a novel approach for quantum-inspired solvers but also pave the way towards addressing commercially-relevant problems using near-term quantum devices. The study provides valuable insights into resource analysis through four experimental deployments, highlighting precise quantum resources (number of qubits and gate count) alongside classical resources (number of epochs). The authors acknowledge support from various entities and express gratitude to individuals who contributed to their research efforts. Overall, this research contributes significantly to advancing quantum optimization techniques and underscores the potential of leveraging quantum computing capabilities for solving complex real-world problems efficiently.