Ramsey numbers and adiabatic quantum computing

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\ge 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\le s\le 7$. We then discuss the algorithm's experimental implementation, and close by showing that Ramsey number computation belongs to the quantum complexity class QMA.

4 pages, 1 table, no figures, published version

References in corpus (3)

• Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
• Experimental implementation of an adiabatic quantum optimization algorithm
• A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation

Cited by in corpus (35)

• Adiabatic Quantum Computing
• Digitized adiabatic quantum computing with a superconducting circuit
• Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
• Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
• Experimental determination of Ramsey numbers
• Quantum Annealing for Constrained Optimization
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Driver Hamiltonians for constrained optimization in quantum annealing
• Experimental quantum annealing: case study involving the graph isomorphism problem
• Graph isomorphism and adiabatic quantum computing
• Readiness of Quantum Optimization Machines for Industrial Applications
• Solving the Graph Isomorphism Problem with a Quantum Annealer
• Constrained quantum annealing of graph coloring
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• Exact representations of many body interactions with RBM neural networks
• A Performance Estimator for Quantum Annealers: Gauge selection and Parameter Setting
• Adiabatic Quantum Optimization for Associative Memory Recall
• Lower bounds for Ramsey numbers as a statistical physics problem
• Theorem on the existence of a nonzero energy gap in adiabatic quantum computation
• Collective dynamics of phase-repulsive oscillators solves graph coloring problem
• Exact solution of bond percolation on small arbitrary graphs
• The relationship between minimum gap and success probability in adiabatic quantum computing
• Localization in the constrained quantum annealing of graph coloring
• Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer
• Determine Ramsey numbers on a quantum computer
• Performance Models for Split-execution Computing Systems
• Generalized Ramsey numbers through adiabatic quantum optimization
• Quadratic constrained mixed discrete optimization with an adiabatic quantum optimizer
• Adiabatic Quantum Programming: Minor Embedding With Hard Faults
• Hypergraph Ramsey Numbers and Adiabatic Quantum Algorithm
• The Distribution of Ramsey Numbers
• Computing Hypergraph Ramsey Numbers by Using Quantum Circuit
• Toward Computing Bounds for Ramsey Numbers Using Quantum Annealing
• Improving adiabatic quantum factorization via chopped random-basis optimization
• An Adiabatic Quantum Algorithm for Determining Gracefulness of A Graph