Combinatorial optimization via highly efficient quantum walks
We present a highly efficient quantum circuit for performing continuous time quantum walks (CTQWs) over an exponentially large set of combinatorial objects, provided that the objects can be indexed efficiently. CTQWs form the core mixing operation of a generalized version of the quantum approximate...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2020-06-01
|
| Series: | Physical Review Research |
| Online Access: | http://doi.org/10.1103/PhysRevResearch.2.023302 |
| _version_ | 1797211403897012224 |
|---|---|
| author | S. Marsh J. B. Wang |
| author_facet | S. Marsh J. B. Wang |
| author_sort | S. Marsh |
| collection | DOAJ |
| description | We present a highly efficient quantum circuit for performing continuous time quantum walks (CTQWs) over an exponentially large set of combinatorial objects, provided that the objects can be indexed efficiently. CTQWs form the core mixing operation of a generalized version of the quantum approximate optimization algorithm, which works by “steering” the quantum amplitude into high-quality solutions. The efficient quantum circuit holds the promise of finding high-quality solutions to certain classes of NP-hard combinatorial problems such as the Travelling Salesman Problem, maximum set splitting, graph partitioning, and lattice path optimization. |
| first_indexed | 2024-04-24T10:25:57Z |
| format | Article |
| id | doaj.art-703a80d8611148a4a6d884e080a3348c |
| institution | Directory Open Access Journal |
| issn | 2643-1564 |
| language | English |
| last_indexed | 2024-04-24T10:25:57Z |
| publishDate | 2020-06-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review Research |
| spelling | doaj.art-703a80d8611148a4a6d884e080a3348c2024-04-12T16:55:10ZengAmerican Physical SocietyPhysical Review Research2643-15642020-06-012202330210.1103/PhysRevResearch.2.023302Combinatorial optimization via highly efficient quantum walksS. MarshJ. B. WangWe present a highly efficient quantum circuit for performing continuous time quantum walks (CTQWs) over an exponentially large set of combinatorial objects, provided that the objects can be indexed efficiently. CTQWs form the core mixing operation of a generalized version of the quantum approximate optimization algorithm, which works by “steering” the quantum amplitude into high-quality solutions. The efficient quantum circuit holds the promise of finding high-quality solutions to certain classes of NP-hard combinatorial problems such as the Travelling Salesman Problem, maximum set splitting, graph partitioning, and lattice path optimization.http://doi.org/10.1103/PhysRevResearch.2.023302 |
| spellingShingle | S. Marsh J. B. Wang Combinatorial optimization via highly efficient quantum walks Physical Review Research |
| title | Combinatorial optimization via highly efficient quantum walks |
| title_full | Combinatorial optimization via highly efficient quantum walks |
| title_fullStr | Combinatorial optimization via highly efficient quantum walks |
| title_full_unstemmed | Combinatorial optimization via highly efficient quantum walks |
| title_short | Combinatorial optimization via highly efficient quantum walks |
| title_sort | combinatorial optimization via highly efficient quantum walks |
| url | http://doi.org/10.1103/PhysRevResearch.2.023302 |
| work_keys_str_mv | AT smarsh combinatorialoptimizationviahighlyefficientquantumwalks AT jbwang combinatorialoptimizationviahighlyefficientquantumwalks |