Generalized Ramsey numbers through adiabatic quantum optimization

DOI10.1007/S11128-016-1363-3zbMATH Open1348.81176arXiv1606.01078OpenAlexW2417068188MaRDI QIDQ331397FDOQ331397

Authors: Mani Ranjbar, William G. Macready, Frank Gaitan, Lane Clark 

Publication date: 27 October 2016

Published in: Quantum Information Processing (Search for Journal in Brave)

Abstract: Ramsey theory is an active research area in combinatorics whose central theme is the emergence of order in large disordered structures, with Ramsey numbers marking the threshold at which this order first appears. For generalized Ramsey numbers $r(G,H)$, the emergent order is characterized by graphs $G$ and $H$. In this paper we: (i) present a quantum algorithm for computing generalized Ramsey numbers by reformulating the computation as a combinatorial optimization problem which is solved using adiabatic quantum optimization; and (ii) determine the Ramsey numbers $r(mathcal{T}_m,mathcal{T}_n)$ for trees of order $m,n=6,7,8$, most of which were previously unknown.

Full work available at URL: https://arxiv.org/abs/1606.01078

Recommendations

• Hypergraph Ramsey numbers and adiabatic quantum algorithm
• Computing hypergraph Ramsey numbers by using quantum circuit
• Adiabatic quantum optimization with qudits
• A quantum adiabatic algorithm for multiobjective combinatorial optimization
• A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
• The quantum adiabatic optimization algorithm and local minima
• The complexity of the quantum adiabatic algorithm
• Random matrix approach to quantum adiabatic evolution algorithms
• Efficiently embedding QUBO problems on adiabatic quantum computers
• Optimization on large interconnected graphs and networks using adiabatic quantum computation

zbMATH Keywords

combinatorial optimizationRamsey theoryadiabatic quantum algorithmsgeneralized Ramsey numberstree Ramsey numbers

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• Title not available (Why is that?)
• Practical graph isomorphism. II.
• Title not available (Why is that?)
• Tabu Search—Part I
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ramsey numbers for graphs with five vertices
• Some small ramsey numbers
• Generalized Ramsey Theory for Graphs. II. Small Diagonal Numbers
• Generalized Ramsey theory for graphs, X: Double stars
• Small Ramsey numbers
• Some tree-star Ramsey numbers
• Generalized Ramsey theory for graphs. III: Small off-diagonal numbers
• SIMULATION OF QUANTUM ADIABATIC SEARCH IN THE PRESENCE OF NOISE
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• Computing hypergraph Ramsey numbers by using quantum circuit
• Hypergraph Ramsey numbers and adiabatic quantum algorithm
• Computation of Ramsey numbers by P systems with active membranes

Uses Software

• OEIS

This page was built for publication: Generalized Ramsey numbers through adiabatic quantum optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q331397)