Generalized Ramsey numbers through adiabatic quantum optimization

DOI10.1007/S11128-016-1363-3zbMATH Open1348.81176OpenAlexW2417068188MaRDI 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)

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

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)

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.

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

Cites Work

• scientific article; zbMATH DE number 4162920 (Why is no real title available?)
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 3520446 (Why is no real title available?)
• scientific article; zbMATH DE number 734955 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 863494 (Why is no real title available?)
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3390794 (Why is no real title available?)
• Generalized Ramsey Theory for Graphs. II. Small Diagonal Numbers
• Generalized Ramsey theory for graphs, X: Double stars
• Generalized Ramsey theory for graphs. III: Small off-diagonal numbers
• Practical graph isomorphism. II.
• Ramsey numbers for graphs with five vertices
• SIMULATION OF QUANTUM ADIABATIC SEARCH IN THE PRESENCE OF NOISE
• Small Ramsey numbers
• Some small ramsey numbers
• Some tree-star Ramsey numbers
• Tabu Search—Part I

Cited In (4)

• Solving Ramsey number algorithm based on set theory
• 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)