Ramsey numbers and adiabatic quantum computing

DOI10.1103/PHYSREVLETT.108.010501MaRDI QIDQ6223989zbMATH OpenWikidataFDO

Authors Frank Gaitan, Lane Clark

Publication date 7 March 2011

Full work available at URL https://doi.org/10.1103/PHYSREVLETT.108.010501

Abstract: The graph-theoretic Ramsey numbers are notoriously difficult to calculate. In fact, for the two-color Ramsey numbers $R(m,n)$ with $m,ngeq3$, 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 $5leqsleq7$. We then discuss the algorithm's experimental implementation, and close by showing that Ramsey number computation belongs to the quantum complexity class QMA.

This page was built for publication: Ramsey numbers and adiabatic quantum computing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6223989)