Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915429251809280 |
|---|---|
| author | Montanez-Barrera, J. A. Michielsen, Kristel |
| author_facet | Montanez-Barrera, J. A. Michielsen, Kristel |
| contents | The Quantum Approximate Optimization Algorithm (QAOA) is a promising algorithm for solving combinatorial optimization problems (COPs), with performance governed by variational parameters $\{γ_i, β_i\}_{i=0}^{p-1}$. While most prior work has focused on classically optimizing these parameters, we demonstrate that fixed linear ramp schedules, linear ramp QAOA (LR-QAOA), can efficiently approximate optimal solutions across diverse COPs. Simulations with up to $N_q=42$ qubits and $p=400$ layers suggest that the success probability scales as $P(x^*) \approx 2^{-η(p) N_q + C}$, where $η(p)$ decreases with increasing $p$. For example, in Weighted Maxcut instances, $η(10) = 0.22$ improves to $η(100) = 0.05$. Comparisons with classical algorithms, including simulated annealing, Tabu Search, and branch-and-bound, show a scaling advantage for LR-QAOA. We show results of LR-QAOA on multiple QPUs (IonQ, Quantinuum, IBM) with up to $N_q = 109$ qubits, $p=100$, and circuits requiring 21,200 CNOT gates. Finally, we present a noise model based on two-qubit gate counts that accurately reproduces the experimental behavior of LR-QAOA. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_09169 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems Montanez-Barrera, J. A. Michielsen, Kristel Quantum Physics Optimization and Control The Quantum Approximate Optimization Algorithm (QAOA) is a promising algorithm for solving combinatorial optimization problems (COPs), with performance governed by variational parameters $\{γ_i, β_i\}_{i=0}^{p-1}$. While most prior work has focused on classically optimizing these parameters, we demonstrate that fixed linear ramp schedules, linear ramp QAOA (LR-QAOA), can efficiently approximate optimal solutions across diverse COPs. Simulations with up to $N_q=42$ qubits and $p=400$ layers suggest that the success probability scales as $P(x^*) \approx 2^{-η(p) N_q + C}$, where $η(p)$ decreases with increasing $p$. For example, in Weighted Maxcut instances, $η(10) = 0.22$ improves to $η(100) = 0.05$. Comparisons with classical algorithms, including simulated annealing, Tabu Search, and branch-and-bound, show a scaling advantage for LR-QAOA. We show results of LR-QAOA on multiple QPUs (IonQ, Quantinuum, IBM) with up to $N_q = 109$ qubits, $p=100$, and circuits requiring 21,200 CNOT gates. Finally, we present a noise model based on two-qubit gate counts that accurately reproduces the experimental behavior of LR-QAOA. |
| title | Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems |
| topic | Quantum Physics Optimization and Control |
| url | https://arxiv.org/abs/2405.09169 |