Determine Ramsey numbers on a quantum computer
arXiv:1510.01884 · doi:10.1103/PhysRevA.93.032301
Abstract
We present a quantum algorithm for computing the Ramsey numbers whose computational complexity grows super-exponentially with the number of vertices of a graph on a classical computer. The problem is mapped to a decision problem on a quantum computer, a probe qubit is coupled to a register that represents the problem and detects the energy levels of the problem Hamiltonian. The decision problem is solved by determining whether the probe qubit exhibits resonance dynamics. The algorithm shows a quadratic speedup over its classical counterparts, and the degenerate ground state problem in the adiabatic quantum evolution algorithm for this problem is avoided.
10 pages, 3 figures
References in corpus (5)
- Universal digital quantum simulation with trapped ions
- Experimental determination of Ramsey numbers
- Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
- A quantum algorithm for solving some discrete mathematical problems by probing their energy spectra
- A quantum algorithm for obtaining the energy spectrum of a physical system without guessing its eigenstates