Speedup of high-order unconstrained binary optimization using quantum $${{\mathbb{Z}}}_{2}$$ Z 2 lattice gauge theory
Abstract An important and difficult problem in optimization is the high-order unconstrained binary optimization, which can represent many optimization problems more efficiently than quadratic unconstrained binary optimization, but how to quickly solve it has remained difficult. Here, we present an a...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2025-04-01
|
| Series: | Communications Physics |
| Online Access: | https://doi.org/10.1038/s42005-025-02072-7 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850183941831524352 |
|---|---|
| author | Bi-Ying Wang Xiaopeng Cui Qingguo Zeng Yemin Zhan Man-Hong Yung Yu Shi |
| author_facet | Bi-Ying Wang Xiaopeng Cui Qingguo Zeng Yemin Zhan Man-Hong Yung Yu Shi |
| author_sort | Bi-Ying Wang |
| collection | DOAJ |
| description | Abstract An important and difficult problem in optimization is the high-order unconstrained binary optimization, which can represent many optimization problems more efficiently 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 $${{\mathbb{Z}}}_{2}$$ Z 2 lattice gauge theory 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 | Article |
| id | doaj-art-d221cd27f0cf4780a71bf3dcda8d13b7 |
| institution | OA Journals |
| issn | 2399-3650 |
| language | English |
| publishDate | 2025-04-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Communications Physics |
| spelling | doaj-art-d221cd27f0cf4780a71bf3dcda8d13b72025-08-20T02:17:10ZengNature PortfolioCommunications Physics2399-36502025-04-01811810.1038/s42005-025-02072-7Speedup of high-order unconstrained binary optimization using quantum $${{\mathbb{Z}}}_{2}$$ Z 2 lattice gauge theoryBi-Ying Wang0Xiaopeng Cui1Qingguo Zeng2Yemin Zhan3Man-Hong Yung4Yu Shi5Wilczek Quantum Center, Shanghai Institute for Advanced StudiesDepartment of Physics & State Key Laboratory of Surface Physics, Fudan UniversityShenzhen Institute for Quantum Science and Engineering, Southern University of Science and TechnologyDepartment of Physics & State Key Laboratory of Surface Physics, Fudan UniversityShenzhen Institute for Quantum Science and Engineering, Southern University of Science and TechnologyWilczek Quantum Center, Shanghai Institute for Advanced StudiesAbstract An important and difficult problem in optimization is the high-order unconstrained binary optimization, which can represent many optimization problems more efficiently 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 $${{\mathbb{Z}}}_{2}$$ Z 2 lattice gauge theory 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.https://doi.org/10.1038/s42005-025-02072-7 |
| spellingShingle | Bi-Ying Wang Xiaopeng Cui Qingguo Zeng Yemin Zhan Man-Hong Yung Yu Shi Speedup of high-order unconstrained binary optimization using quantum $${{\mathbb{Z}}}_{2}$$ Z 2 lattice gauge theory Communications Physics |
| title | Speedup of high-order unconstrained binary optimization using quantum $${{\mathbb{Z}}}_{2}$$ Z 2 lattice gauge theory |
| title_full | Speedup of high-order unconstrained binary optimization using quantum $${{\mathbb{Z}}}_{2}$$ Z 2 lattice gauge theory |
| title_fullStr | Speedup of high-order unconstrained binary optimization using quantum $${{\mathbb{Z}}}_{2}$$ Z 2 lattice gauge theory |
| title_full_unstemmed | Speedup of high-order unconstrained binary optimization using quantum $${{\mathbb{Z}}}_{2}$$ Z 2 lattice gauge theory |
| title_short | Speedup of high-order unconstrained binary optimization using quantum $${{\mathbb{Z}}}_{2}$$ Z 2 lattice gauge theory |
| title_sort | speedup of high order unconstrained binary optimization using quantum mathbb z 2 z 2 lattice gauge theory |
| url | https://doi.org/10.1038/s42005-025-02072-7 |
| work_keys_str_mv | AT biyingwang speedupofhighorderunconstrainedbinaryoptimizationusingquantummathbbz2z2latticegaugetheory AT xiaopengcui speedupofhighorderunconstrainedbinaryoptimizationusingquantummathbbz2z2latticegaugetheory AT qingguozeng speedupofhighorderunconstrainedbinaryoptimizationusingquantummathbbz2z2latticegaugetheory AT yeminzhan speedupofhighorderunconstrainedbinaryoptimizationusingquantummathbbz2z2latticegaugetheory AT manhongyung speedupofhighorderunconstrainedbinaryoptimizationusingquantummathbbz2z2latticegaugetheory AT yushi speedupofhighorderunconstrainedbinaryoptimizationusingquantummathbbz2z2latticegaugetheory |