Ramsey numbers and adiabatic quantum computing |
| |
Authors: | Gaitan Frank Clark Lane |
| |
Affiliation: | Laboratory for Physical Sciences, 8050 Greenmead Dr, College Park, Maryland 20740, USA. |
| |
Abstract: | The graph-theoretic Ramsey numbers are notoriously difficult to calculate. In fact, for the two-color Ramsey numbers R(m,n) with m, n≥3, only nine are currently known. We present a quantum algorithm for the computation of the Ramsey numbers R(m,n). We show how the computation of R(m,n) can be mapped to a combinatorial optimization problem whose solution can be found using adiabatic quantum evolution. We numerically simulate this adiabatic quantum algorithm and show that it correctly determines the Ramsey numbers R(3,3) and R(2,s) for 5≤s≤7. We then discuss the algorithm's experimental implementation, and close by showing that Ramsey number computation belongs to the quantum complexity class quantum Merlin Arthur. |
| |
Keywords: | |
本文献已被 PubMed 等数据库收录! |
|