Improving Quantum Optimization to Achieve Quadratic Time Complexity
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , , , , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912201071132672 |
|---|---|
| author | Jiang, Ji Huang, Peisheng Wu, Zhiyi Sun, Xuandong Guo, Zechen Huang, Wenhui Zhang, Libo Zhou, Yuxuan Zhang, Jiawei Guo, Weijie Linpeng, Xiayu Liu, Song Ren, Wenhui Tao, Ziyu Chu, Ji Niu, Jingjing Zhong, Youpeng Yu, Dapeng |
| author_facet | Jiang, Ji Huang, Peisheng Wu, Zhiyi Sun, Xuandong Guo, Zechen Huang, Wenhui Zhang, Libo Zhou, Yuxuan Zhang, Jiawei Guo, Weijie Linpeng, Xiayu Liu, Song Ren, Wenhui Tao, Ziyu Chu, Ji Niu, Jingjing Zhong, Youpeng Yu, Dapeng |
| contents | Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for achieving quantum advantage in combinatorial optimization. However, its variational framework presents a long-standing challenge in selecting circuit parameters. In this work, we prove that the energy expectation produced by QAOA can be expressed as a trigonometric function of the final-level mixer parameter. Leveraging this insight, we introduce Penta-O, a level-wise parameter-setting strategy that eliminates the classical outer loop, maintains minimal sampling overhead, and ensures non-decreasing performance. This method is broadly applicable to the generic quadratic unconstrained binary optimization formulated as the Ising model. For a $p$-level QAOA, Penta-O achieves an unprecedented quadratic time complexity of $\mathcal{O}(p^2)$ and a sampling overhead proportional to $5p+1$. Through experiments and simulations, we demonstrate that QAOA enhanced by Penta-O achieves near-optimal performance with exceptional circuit depth efficiency. Our work provides a versatile tool for advancing variational quantum algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_13469 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improving Quantum Optimization to Achieve Quadratic Time Complexity Jiang, Ji Huang, Peisheng Wu, Zhiyi Sun, Xuandong Guo, Zechen Huang, Wenhui Zhang, Libo Zhou, Yuxuan Zhang, Jiawei Guo, Weijie Linpeng, Xiayu Liu, Song Ren, Wenhui Tao, Ziyu Chu, Ji Niu, Jingjing Zhong, Youpeng Yu, Dapeng Quantum Physics Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for achieving quantum advantage in combinatorial optimization. However, its variational framework presents a long-standing challenge in selecting circuit parameters. In this work, we prove that the energy expectation produced by QAOA can be expressed as a trigonometric function of the final-level mixer parameter. Leveraging this insight, we introduce Penta-O, a level-wise parameter-setting strategy that eliminates the classical outer loop, maintains minimal sampling overhead, and ensures non-decreasing performance. This method is broadly applicable to the generic quadratic unconstrained binary optimization formulated as the Ising model. For a $p$-level QAOA, Penta-O achieves an unprecedented quadratic time complexity of $\mathcal{O}(p^2)$ and a sampling overhead proportional to $5p+1$. Through experiments and simulations, we demonstrate that QAOA enhanced by Penta-O achieves near-optimal performance with exceptional circuit depth efficiency. Our work provides a versatile tool for advancing variational quantum algorithms. |
| title | Improving Quantum Optimization to Achieve Quadratic Time Complexity |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2501.13469 |