Experimental determination of Ramsey numbers

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\le m\le 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.

manuscript: 5 pages; 1 table, 3 figures; Supplementary Information: 18 pages, 1 table, 13 figures; version to appear in Physical Review Letters

References in corpus (1)

• Experimental signature of programmable quantum annealing

Cited by in corpus (55)

• Ising formulations of many NP problems
• Quantum information processing with superconducting circuits: a review
• Quantum annealing with more than one hundred qubits
• Architectural considerations in the design of a superconducting quantum annealing processor
• Experimental signature of programmable quantum annealing
• Quantum Optimization of Fully-Connected Spin Glasses
• Adiabatic Quantum Simulation of Quantum Chemistry
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Quantum Annealing for Constrained Optimization
• Bayesian Network Structure Learning Using Quantum Annealing
• Forecasting financial crashes with quantum computing
• Driver Hamiltonians for constrained optimization in quantum annealing
• Graph isomorphism and adiabatic quantum computing
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Finding spin-glass ground states using quantum walks
• New Quantum Codes from Evaluation and Matrix-Product Codes
• Probing Entanglement in Adiabatic Quantum Optimization with Trapped Ions
• Hamiltonian gadgets with reduced resource requirements
• Comparative Study of the Performance of Quantum Annealing and Simulated Annealing
• Stabilizer quantum codes from $J$-affine variety codes and a new Steane-like enlargement
• Constrained quantum annealing of graph coloring
• Analog Nature of Quantum Adiabatic Unstructured Search
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
• How to test the "quantumness" of a quantum computer?
• Weightless neural network parameters and architecture selection in a quantum computer
• Adiabatic Quantum Optimization for Associative Memory Recall
• Lower bounds for Ramsey numbers as a statistical physics problem
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Practical designs for permutation symmetric problem Hamiltonians on hypercubes
• Kinetic energy of a trapped Fermi gas at finite temperature
• Quadratization in discrete optimization and quantum mechanics
• Counterdiabatic Reverse Annealing
• Theorem on the existence of a nonzero energy gap in adiabatic quantum computation
• Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results
• Deep learning optimal quantum annealing schedules for random Ising models
• NSQUID arrays as conveyers of quantum information
• Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer
• Localization in the constrained quantum annealing of graph coloring
• Determine Ramsey numbers on a quantum computer
• Performance Models for Split-execution Computing Systems
• Generalized Ramsey numbers through adiabatic quantum optimization
• Mapping constrained optimization problems to quantum annealing with application to fault diagnosis
• Decoding quantum error correction with Ising model hardware
• Quadratic constrained mixed discrete optimization with an adiabatic quantum optimizer
• Quantum Annealing and Computation: A Brief Documentary Note
• Recursive simulation of quantum annealing
• Relation of classical non-equilibrium dynamics and quantum annealing
• Noise Effects on Diabatic Quantum Annealing Protocols
• Toward Computing Bounds for Ramsey Numbers Using Quantum Annealing
• Electronic Structure Calculations and the Ising Hamiltonian
• Statistical Analysis of Quantum Annealing
• An Adiabatic Quantum Algorithm for Determining Gracefulness of A Graph
• 2D implementation of quantum annealing algorisms for fourth order binary optimization problems
• The Distribution of Ramsey Numbers