Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1103.1345 · Physical Review Letters

Ramsey Numbers and Adiabatic Quantum Computing

Frank Gaitan, Lane Clark

Published Jan 5, 2012• 67 citations
arXivHTMLPDF

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.

DOI
10.1103/physrevlett.108.010501

Related papers

HYPERGRAPH RAMSEY NUMBERS AND ADIABATIC QUANTUM ALGORITHM

Ri Qu, Su-li Zhao, Yan-ru Bao +1 more

Gaitan and Clark [Phys. Rev. Lett.108 (2012) 010501] have recently presented a quantum algorithm for the computation of the Ramsey numbers R(m, n) using adiabatic quantum evolution (AQE). We consider that the two-color Ramsey numbers R(m, n; r) for r-uniform hypergraphs can be computed by using the similar ways in Phys. Rev. Lett.108 (2012) 010501. In this paper, we show how the computation of R(m, n; r) can be mapped to a combinatorial optimization problem whose solution be found using AQE.

arXiv:1204.2483•International Journal of Quantum Information•Sep 1, 2012•1 citation

Experimental Determination of Ramsey Numbers

Zhengbing Bian, Fabián A. Chudak, William G. Macready +2 more

Ramsey theory is a highly active research area in mathematics that studies the emergence of order in large disordered structures. Ramsey numbers mark the threshold at which order first appears and are extremely difficult to calculate due to their explosive rate of growth. Recently, an algorithm that can be implemented using adiabatic quantum evolution has been proposed that calculates the two-color Ramsey numbers R(m,n). Here we present results of an experimental implementation of this algorithm and show that it correctly determines the Ramsey numbers R(3,3) and R(m,2) for 4≤m≤8. The R(8,2) computation used 84 qubits of which 28 were computational qubits. This computation is the largest experimental implementation of a scientifically meaningful adiabatic evolution algorithm that has been done to date.

arXiv:1201.1842•Physical Review Letters•Sep 25, 2013•108 citations

Putting “Quantumness” to the Test

Graeme Smith, John A. Smolin

Ramsey theory is a highly active research area in mathematics that studies the emergence of order in large disordered structures.Ramsey numbers mark the threshold at which order first appears and are extremely difficult to calculate due to their explosive rate of growth.Recently, an algorithm that can be implemented using adiabatic quantum evolution has been proposed that calculates the two-color Ramsey numbers Rðm; nÞ.Here we present results of an experimental implementation of this algorithm and show that it correctly determines the Ramsey numbers Rð3; 3Þ and Rðm; 2Þ for 4 m 8.The Rð8; 2Þ computation used 84 qubits of which 28 were computational qubits.This computation is the largest experimental implementation of a scientifically meaningful adiabatic evolution algorithm that has been done to date.

Physics•Sep 25, 2013•14 citations

Graph isomorphism and adiabatic quantum computing

Frank Gaitan, Lane Clark

In the graph isomorphism (GI) problem two $N$-vertex graphs $G$ and ${G}^{\ensuremath{'}}$ are given and the task is to determine whether there exists a permutation of the vertices of $G$ that preserves adjacency and transforms $G\ensuremath{\rightarrow}{G}^{\ensuremath{'}}$. If yes, then $G$ and ${G}^{\ensuremath{'}}$ are said to be isomorphic; otherwise they are nonisomorphic. The GI problem is an important problem in computer science and is thought to be of comparable difficulty to integer factorization. In this paper we present a quantum algorithm that solves arbitrary instances of GI and which also provides an approach to determining all automorphisms of a given graph. We show how the GI problem can be converted to a combinatorial optimization problem that can be solved using adiabatic quantum evolution. We numerically simulate the algorithm's quantum dynamics and show that it correctly (i) distinguishes nonisomorphic graphs; (ii) recognizes isomorphic graphs and determines the permutation(s) that connect them; and (iii) finds the automorphism group of a given graph $G$. We then discuss the GI quantum algorithm's experimental implementation, and close by showing how it can be leveraged to give a quantum algorithm that solves arbitrary instances of the NP-complete subgraph isomorphism problem. The computational complexity of an adiabatic quantum algorithm is largely determined by the minimum energy gap $\ensuremath{\Delta}(N)$ separating the ground and first-excited states in the limit of large problem size $N\ensuremath{\gg}1$. Calculating $\ensuremath{\Delta}(N)$ in this limit is a fundamental open problem in adiabatic quantum computing, and so it is not possible to determine the computational complexity of adiabatic quantum algorithms in general, nor consequently, of the specific adiabatic quantum algorithms presented here. Adiabatic quantum computing has been shown to be equivalent to the circuit model of quantum computing, and so development of adiabatic quantum algorithms continues to be of great interest.

arXiv:1304.5773•Physical Review A•Feb 28, 2014•51 citations

Toward computing bounds for Ramsey numbers using quantum annealing

Joel E. Pion, Susan M. Mniszewski

Abstract Quantum annealing is a powerful tool for solving and approximating combinatorial optimization problems, such as graph partitioning, community detection, centrality, routing problems, and more. In this paper we explore the use of quantum annealing as a tool for use in exploring combinatorial mathematics research problems. We consider the monochromatic triangle problem and the Ramsey number problem, both examples of graph coloring. Conversion to quadratic unconstrained binary optimization (QUBO) form is required to run on quantum hardware. While the monochromatic triangle problem is quadratic by nature, the Ramsey number problem requires the use of order reduction methods for a quadratic formulation. The goal is to provide a method for producing special colorings of graphs which if successful would provide lower bounds for certain Ramsey numbers. We discuss implementations, limitations, and results when running on the D-Wave Advantage quantum annealer.

arXiv:2311.04405•Quantum Information Processing•Jul 11, 2025•1 citation

Determining Ramsey numbers on a quantum computer

Hefeng Wang

We present a quantum algorithm for computing the Ramsey numbers whose computational complexity grows superexponentially with the number of vertices of a graph on a classical computer. The problem is mapped to a decision problem on a quantum computer, and 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 detecting the decay dynamics of the probe qubit.

arXiv:1510.01884•Physical Review A•Mar 1, 2016•8 citations
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.
Ramsey theory is a highly active research area in mathematics that studies the emergence of order in large disordered structures. Ramsey numbers mark the threshold at which order first appears and are extremely difficult to calculate due to their explosive rate of growth. Recently, an algorithm that can be implemented using adiabatic quantum evolution has been proposed that calculates the two-color Ramsey numbers R(m,n). Here we present results of an experimental implementation of this algorithm and show that it correctly determines the Ramsey numbers R(3,3) and R(m,2) for 4≤m≤8. The R(8,2) computation used 84 qubits of which 28 were computational qubits. This computation is the largest experimental implementation of a scientifically meaningful adiabatic evolution algorithm that has been done to date.
Ramsey theory is a highly active research area in mathematics that studies the emergence of order in large disordered structures.Ramsey numbers mark the threshold at which order first appears and are extremely difficult to calculate due to their explosive rate of growth.Recently, an algorithm that can be implemented using adiabatic quantum evolution has been proposed that calculates the two-color Ramsey numbers Rðm; nÞ.Here we present results of an experimental implementation of this algorithm and show that it correctly determines the Ramsey numbers Rð3; 3Þ and Rðm; 2Þ for 4 m 8.The Rð8; 2Þ computation used 84 qubits of which 28 were computational qubits.This computation is the largest experimental implementation of a scientifically meaningful adiabatic evolution algorithm that has been done to date.
In the graph isomorphism (GI) problem two NNN-vertex graphs GGG and ${G}^{\ensuremath{'}}$ are given and the task is to determine whether there exists a permutation of the vertices of GGG that preserves adjacency and transforms $G\ensuremath{\rightarrow}{G}^{\ensuremath{'}}$. If yes, then GGG and ${G}^{\ensuremath{'}}$ are said to be isomorphic; otherwise they are nonisomorphic. The GI problem is an important problem in computer science and is thought to be of comparable difficulty to integer factorization. In this paper we present a quantum algorithm that solves arbitrary instances of GI and which also provides an approach to determining all automorphisms of a given graph. We show how the GI problem can be converted to a combinatorial optimization problem that can be solved using adiabatic quantum evolution. We numerically simulate the algorithm's quantum dynamics and show that it correctly (i) distinguishes nonisomorphic graphs; (ii) recognizes isomorphic graphs and determines the permutation(s) that connect them; and (iii) finds the automorphism group of a given graph GGG. We then discuss the GI quantum algorithm's experimental implementation, and close by showing how it can be leveraged to give a quantum algorithm that solves arbitrary instances of the NP-complete subgraph isomorphism problem. The computational complexity of an adiabatic quantum algorithm is largely determined by the minimum energy gap $\ensuremath{\Delta}(N)$ separating the ground and first-excited states in the limit of large problem size $N\ensuremath{\gg}1$. Calculating $\ensuremath{\Delta}(N)$ in this limit is a fundamental open problem in adiabatic quantum computing, and so it is not possible to determine the computational complexity of adiabatic quantum algorithms in general, nor consequently, of the specific adiabatic quantum algorithms presented here. Adiabatic quantum computing has been shown to be equivalent to the circuit model of quantum computing, and so development of adiabatic quantum algorithms continues to be of great interest.
Abstract Quantum annealing is a powerful tool for solving and approximating combinatorial optimization problems, such as graph partitioning, community detection, centrality, routing problems, and more. In this paper we explore the use of quantum annealing as a tool for use in exploring combinatorial mathematics research problems. We consider the monochromatic triangle problem and the Ramsey number problem, both examples of graph coloring. Conversion to quadratic unconstrained binary optimization (QUBO) form is required to run on quantum hardware. While the monochromatic triangle problem is quadratic by nature, the Ramsey number problem requires the use of order reduction methods for a quadratic formulation. The goal is to provide a method for producing special colorings of graphs which if successful would provide lower bounds for certain Ramsey numbers. We discuss implementations, limitations, and results when running on the D-Wave Advantage quantum annealer.