Speedup of high-order unconstrained binary optimization using quantum Z2 lattice gauge theory
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916654811709440 |
|---|---|
| author | Wang, Bi-Ying Cui, Xiaopeng Zeng, Qingguo Zhan, Yemin Yung, Man-Hong Shi, Yu |
| author_facet | Wang, Bi-Ying Cui, Xiaopeng Zeng, Qingguo Zhan, Yemin Yung, Man-Hong Shi, Yu |
| contents | An important and difficult problem in optimization is the high-order unconstrained binary optimization, which can represent many optimization problems more efficient than quadratic unconstrained binary optimization, but how to quickly solve it has remained difficult. Here we present an approach by mapping the high-order unconstrained binary optimization to quantum Z2 lattice gauge theory defined on the dual graph, and propose the gauged local quantum annealing, which is the local quantum annealing protected by the gauge symmetry. We present the quantum algorithm and its corresponding quantum-inspired classical algorithm for this problem, and achieve algorithmic speedup by using gauge symmetry. By running the quantum-inspired classical algorithm, we demonstrate that the gauged local quantum annealing reduces the computational time by one order of magnitude from that of the local quantum annealing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_05958 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Speedup of high-order unconstrained binary optimization using quantum Z2 lattice gauge theory Wang, Bi-Ying Cui, Xiaopeng Zeng, Qingguo Zhan, Yemin Yung, Man-Hong Shi, Yu Quantum Physics An important and difficult problem in optimization is the high-order unconstrained binary optimization, which can represent many optimization problems more efficient than quadratic unconstrained binary optimization, but how to quickly solve it has remained difficult. Here we present an approach by mapping the high-order unconstrained binary optimization to quantum Z2 lattice gauge theory defined on the dual graph, and propose the gauged local quantum annealing, which is the local quantum annealing protected by the gauge symmetry. We present the quantum algorithm and its corresponding quantum-inspired classical algorithm for this problem, and achieve algorithmic speedup by using gauge symmetry. By running the quantum-inspired classical algorithm, we demonstrate that the gauged local quantum annealing reduces the computational time by one order of magnitude from that of the local quantum annealing. |
| title | Speedup of high-order unconstrained binary optimization using quantum Z2 lattice gauge theory |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2406.05958 |