Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.19035 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912914388025344 |
|---|---|
| author | Chernyavskiy, Andrey Yu. Kulikov, Denis A. Bantysh, Boris I. Bogdanov, Yurii I. Fedorov, Aleksey K. Kiktenko, Evgeniy O. |
| author_facet | Chernyavskiy, Andrey Yu. Kulikov, Denis A. Bantysh, Boris I. Bogdanov, Yurii I. Fedorov, Aleksey K. Kiktenko, Evgeniy O. |
| contents | We study a modified fixed-point version of the Quantum Approximate Optimization Algorithm (fpQAOA), in which parameters are trained on small instances and transferred to larger problems. Our scheme combines three key ingredients: (i) targeting approximate rather than exact solutions through the success probability at a prescribed approximation ratio (AR), (ii) scaling the circuit depth linearly with the problem size using a two-parameter sin-cos angle encoding, and (iii) normalizing QUBO Hamiltonians by their Frobenius norm. Across several ensembles of random QUBO instances, we observe that these modifications yield a non-increasing (and often decreasing) median number of quantum circuit runs ("shots") required to achieve AR $α=0.95$, while the per-shot complexity remains polynomial. Extrapolation indicates an effectively constant $O(1)$ sampling complexity under this combined fpQAOA construction. Strikingly, removing any single component of the scheme restores exponential growth in the number of required shots, highlighting the synergistic nature of the three modifications. Our results provide the first systematic evidence that fpQAOA can achieve scalable approximate performance with polynomial-depth circuits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_19035 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improving QAOA to find approximate QUBO solutions in O(1) shots Chernyavskiy, Andrey Yu. Kulikov, Denis A. Bantysh, Boris I. Bogdanov, Yurii I. Fedorov, Aleksey K. Kiktenko, Evgeniy O. Quantum Physics We study a modified fixed-point version of the Quantum Approximate Optimization Algorithm (fpQAOA), in which parameters are trained on small instances and transferred to larger problems. Our scheme combines three key ingredients: (i) targeting approximate rather than exact solutions through the success probability at a prescribed approximation ratio (AR), (ii) scaling the circuit depth linearly with the problem size using a two-parameter sin-cos angle encoding, and (iii) normalizing QUBO Hamiltonians by their Frobenius norm. Across several ensembles of random QUBO instances, we observe that these modifications yield a non-increasing (and often decreasing) median number of quantum circuit runs ("shots") required to achieve AR $α=0.95$, while the per-shot complexity remains polynomial. Extrapolation indicates an effectively constant $O(1)$ sampling complexity under this combined fpQAOA construction. Strikingly, removing any single component of the scheme restores exponential growth in the number of required shots, highlighting the synergistic nature of the three modifications. Our results provide the first systematic evidence that fpQAOA can achieve scalable approximate performance with polynomial-depth circuits. |
| title | Improving QAOA to find approximate QUBO solutions in O(1) shots |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2509.19035 |