Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2302.10151 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917557573779456 |
|---|---|
| author | Tang, Letian Wang, Haorui Li, Zhengyang Tang, Haozhan Zhang, Chi Li, Shujin |
| author_facet | Tang, Letian Wang, Haorui Li, Zhengyang Tang, Haozhan Zhang, Chi Li, Shujin |
| contents | In this paper, we present a new algorithm for generic combinatorial optimization, which we term quantum dueling. Traditionally, potential solutions to the given optimization problems were encoded in a ``register'' of qubits. Various techniques are used to increase the probability of finding the best solution upon measurement. Quantum dueling innovates by integrating an additional qubit register, effectively creating a ``dueling'' scenario where two sets of solutions compete. This dual-register setup allows for a dynamic amplification process: in each iteration, one register is designated as the 'opponent', against which the other register's more favorable solutions are enhanced through a controlled quantum search. This iterative process gradually steers the quantum state within both registers toward the optimal solution. With a quantitative contraction for the evolution of the state vector, classical simulation under a broad range of scenarios and hyper-parameter selection schemes shows that a quadratic speedup is achieved, which is further tested in more real-world situations. In addition, quantum dueling can be generalized to incorporate arbitrary quantum search techniques and as a quantum subroutine within a higher-level algorithm. Our work demonstrates that increasing the number of qubits allows the development of previously unthought-of algorithms, paving the way for advancement of efficient quantum algorithm design. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_10151 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Quantum Dueling: an Efficient Solution for Combinatorial Optimization Tang, Letian Wang, Haorui Li, Zhengyang Tang, Haozhan Zhang, Chi Li, Shujin Quantum Physics In this paper, we present a new algorithm for generic combinatorial optimization, which we term quantum dueling. Traditionally, potential solutions to the given optimization problems were encoded in a ``register'' of qubits. Various techniques are used to increase the probability of finding the best solution upon measurement. Quantum dueling innovates by integrating an additional qubit register, effectively creating a ``dueling'' scenario where two sets of solutions compete. This dual-register setup allows for a dynamic amplification process: in each iteration, one register is designated as the 'opponent', against which the other register's more favorable solutions are enhanced through a controlled quantum search. This iterative process gradually steers the quantum state within both registers toward the optimal solution. With a quantitative contraction for the evolution of the state vector, classical simulation under a broad range of scenarios and hyper-parameter selection schemes shows that a quadratic speedup is achieved, which is further tested in more real-world situations. In addition, quantum dueling can be generalized to incorporate arbitrary quantum search techniques and as a quantum subroutine within a higher-level algorithm. Our work demonstrates that increasing the number of qubits allows the development of previously unthought-of algorithms, paving the way for advancement of efficient quantum algorithm design. |
| title | Quantum Dueling: an Efficient Solution for Combinatorial Optimization |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2302.10151 |