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

Physics

Putting “Quantumness” to the Test

Graeme Smith, John A. Smolin

Published Sep 25, 2013• 15 citations
Publisher

Abstract

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.

DOI
10.1103/physics.6.105

Related papers

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•97 citations

Experimental determination of Ramsey numbers with quantum annealing

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. It has found applications in mathematics, theoretical computer science, information theory, and classical error correcting codes. Ramsey numbers mark the threshold at which order first appears and are notoriously difficult to calculate due to their explosive rate of growth. Recently, a quantum algorithm has been proposed that calculates the two-color Ramsey numbers R(m,n). Here we present results of an experimental implementation of this algorithm based on quantum annealing 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 quantum algorithm that has been done to date.

•Jan 9, 2012•12 citations

Ramsey Numbers and Adiabatic Quantum Computing

Frank Gaitan, Lane Clark

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.

arXiv:1103.1345•Physical Review Letters•Jan 5, 2012•69 citations

Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. Part 2: The "split-reduc" method and its application to quantum determination of Ramsey numbers

Emile Okada, Richard Tanburn, Nikesh S. Dattani

Quantum annealing has recently been used to determine the Ramsey numbers R(m,2) for 3 < m < 9 and R(3,3) [Bian et al. (2013) PRL 111, 130505]. This was greatly celebrated as the largest experimental implementation of an adiabatic evolution algorithm to that date. However, in that computation, more than 66% of the qubits used were auxiliary qubits, so the sizes of the Ramsey number Hamiltonians used were tremendously smaller than the full 128-qubit capacity of the device used. The reason these auxiliary qubits were needed was because the best quantum annealing devices at the time (and still now) cannot implement multi-qubit interactions beyond 2-qubit interactions, and they are also limited in their capacity for 2-qubit interactions. We present a method which allows the full qubit capacity of a quantum annealing device to be used, by reducing multi-qubit and 2-qubit interactions. With our method, the device used in the 2013 Ramsey number quantum computation could have determined R(16,2) and R(4,3) with under 10 minutes of runtime.

arXiv:1508.07190•Aug 28, 2015•0 citations

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

Quantum Adiabatic Evolution for Pattern Recognition Problem

E. Rezaei Fard, Korosh Aghayar

Quantum pattern recognition algorithm for two-qubit systems has been implemented by quantum adiabatic evolution. We will estimate required running time for this algorithm by means of an analytical solution of time-dependent Hamiltonian since the time complexity of adiabatic quantum evolution is a limitation on the quantum computing. These results can be useful for experimental implementation .

Chinese Physics Letters•Dec 1, 2017•2 citations
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.
Ramsey theory is a highly active research area in mathematics that studies the emergence of order in large disordered structures. It has found applications in mathematics, theoretical computer science, information theory, and classical error correcting codes. Ramsey numbers mark the threshold at which order first appears and are notoriously difficult to calculate due to their explosive rate of growth. Recently, a quantum algorithm has been proposed that calculates the two-color Ramsey numbers R(m,n). Here we present results of an experimental implementation of this algorithm based on quantum annealing 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 quantum algorithm that has been done to date.
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.
Quantum annealing has recently been used to determine the Ramsey numbers R(m,2) for 3 < m < 9 and R(3,3) [Bian et al. (2013) PRL 111, 130505]. This was greatly celebrated as the largest experimental implementation of an adiabatic evolution algorithm to that date. However, in that computation, more than 66% of the qubits used were auxiliary qubits, so the sizes of the Ramsey number Hamiltonians used were tremendously smaller than the full 128-qubit capacity of the device used. The reason these auxiliary qubits were needed was because the best quantum annealing devices at the time (and still now) cannot implement multi-qubit interactions beyond 2-qubit interactions, and they are also limited in their capacity for 2-qubit interactions. We present a method which allows the full qubit capacity of a quantum annealing device to be used, by reducing multi-qubit and 2-qubit interactions. With our method, the device used in the 2013 Ramsey number quantum computation could have determined R(16,2) and R(4,3) with under 10 minutes of runtime.