Toward Computing Bounds for Ramsey Numbers Using Quantum Annealing

Combinatorial optimization problems such as graph partitioning [1], community detection [2], centrality [3], and routing [4] are NP-complete problems that can be solved approximately using quantum-classical or quantum-only methods with a quantum annealer (QA). In this paper we explore using QAs as a tool in combinatorial mathematics research. We provide a method for solving the monochromatic triangle (MCT) problem framed as a quadratic unconstrained binary optimization (QUBO) problem. This is followed by a description of the Ramsey number problem. MCT is quadratic, while the Ramsey problem can be higher order. A novel technique for order reduction is presented that is applicable to Ramsey problems as well as others.

We explore the effectiveness of QA on both the MCT and Ramsey problems. Both problems are important in their own right. MCT is a basic building block to the wider theory of coloring problems. Ramsey theory on the other hand is a specific coloring problem which, to the uninitiated, has a surprising number of applications ranging from number theory to network design [5] [6].

Quantum annealing describes quantum phenomena which can be used to find the minimum of an Ising glass spin model. In this model each bit (or qubit) in the solution string is represented as a $\{\pm 1\}$. In this work however we shall view everything under the QUBO perspective which is equivalent to the Ising model via a linear transformation of variables. The QUBO formulation can be written as

where $\vec{x}$ is a vector of binary variables, $\{0,1\}$, and $Q$ is a real symmetric matrix. Upon consideration of this form one may realize the problem is to find the minimization of a multi-variable quadratic polynomial given that only binary inputs are allowed, hence the name. QA devices are designed to minimize QUBOs or at least find good approximations of the minimum energy. The problem of minimizing a QUBO is NP-Hard [7]. This means that many challenging problems may easily be reframed as a QUBO and thus be solved using a QA device. The challenge becomes then to find efficient ways to restate whatever the question of interest is as a QUBO.

The D-Wave Advantage 4.1 QA was used in this work. It has more than $5,000$ qubits and $35,000$ couplers arranged in a Pegasus topology. This allows for a a maximum fully connected graph of 177 logical qubits [8]. This means that when a problem is sent to a quantum annealer, it must be $2$-local (or quadratic) and also embed into the local topology of the annealing device. Chains of qubits, meaning multiple qubits forming a chain by adjacency may be linked together to represent a single logical qubit to aid in the embedding process. Some problems were run directly on the quantum device. However, due to the size of the problems, a quantum-classical approach was required most of the time. D-Wave’s LEAP hybrid solver [9, 10, 11] with the Advantage 4.1 device was used in this case. Largely this is not due to the raw limit on the number of qubits in the device, but rather a limitation on the connectivity of the device. When embedding problems on quantum hardware beyond a certain size, more than one physical qubit is required to represent one logical variable so that all variables which need to be adjacent in the system are. This embedding is entirely dependent on the shape of the problem and the topology of the quantum hardware using minor embedding with tools like Minorminer [12]. One can also control with the hybrid methods how long the problem is allowed to run for using the hybrid machines by specifying a time limit.

Order reduction in the context of this work is the concept of taking a polynomial unconstrained binary optimization problem and reducing its degree, generally till it is quadratic. This is important as the “natural” way to convert some problems to an unconstrained binary optimization problem is inherently of higher order. And QA, as well as some classical techniques, work only with unconstrained binary optimization problems which are at most quadratic. There exists a standard procedure for order reduction, sometimes referred to as the Rosenberg technique [13], which works as follows.

Suppose one had the unconstrained binary optimization problem $x_{1}x_{2}x_{3}$. This is cubic and so to use a QA device we need to reduce it to quadratic. The idea is to replace $x_{1}x_{2}$ with an ancillary variable $a$. To do so, we need to guarantee that $a=x_{1}x_{2}$. This is achieved using the polynomial

which is $0$ whenever $a=x_{1}x_{2}$ and $>0$ whenever $a\neq x_{1}x_{2}$. One should then multiply $x_{1}x_{2}-2ax_{1}-2ax_{2}+3a$ by a constraint weight which is larger than the minimal achievable value of the original optimization problem. For degrees larger than $3$ one just iterates the above process. For $x_{1}x_{2}x_{3}...x_{n}$ one would use $a_{1}=x_{1}x_{2}$, $a_{2}=a_{1}x_{3}$ and so on in the same way as above. Additionally one should minimize the number of ancillary variables added in this way by choosing which variables to pair up carefully.

The above introduction gives a brief look into how quantum annealing works from a practical level as well as an introduction to the standard order reduction techniques when making QUBOs. In the Methods section, definitions and terminology for understanding coloring problems are provided. The MCT problem is described in more detail along with showing our novel approach on how to solve the problem using a QA device. In the following section on Ramsey theory we introduce the standard approach to turning Ramsey problems into polynomial binary optimization problems. Then describe an original method for order reduction for this problem inspired by the solution to the MCT problem. After outlining the main ideas some ways are provided to make the method more efficient. In the last section the results and conclusions made during the experiments is discussed.

First it should be noted that QUBO solvers, quantum or classical, cannot guarantee optimal solutions in reasonable timeframes for sufficiently large problems. Approaching Ramsey problems of interest currently through the lens of constructing a coloring are sufficiently large, else they would not be of interest. Because of this, it must be said that any attempt of this style would have little chance of finding an exact Ramsey number. The primary use of this framework is to improve lower bounds by constructing colorings which avoid their relevant substructures. In addition one can gain empirical evidence that a Ramsey number has been found when no more colorings forbidding certain subgraphs can be made. The most straightforward way to write a binary optimization which searches for a coloring of $K_{m}$ which contains no monochromatic $K_{n}$, i.e. trying to show $R(n)>m$, is

This is completely analogous to what we did for the monochromatic triangle. A novel part of our approach will be how we do the order reduction. Rather than use the standard method which is listed in the background, we will use observation (1) from the previous subsection. The method will be explained using $R(4)$, which ends up with degree $6$ terms. $R(n)$ for $n>4$ can be done similarly with only slight modifications.

In one experiment data was collected on how well the Advantage hardware worked with the MCT algorithm developed in this paper. Table 1 is the data from this experiment. Note each table entry was tested three times. A single number is provided if each trial resulted in the same value, while all three values are provided in increasing size in all other cases. The $n$ column is for what $K_{n}$ was being colored. As one can see simulated annealing achieved the minimum number of triangles for every $n$ tested. The pure quantum method achieved optimal results up to $K_{8}$ and also at $K_{1}0$. The quantum annealing results were never worse than $10\%$ above the minimum and beyond a certain size was generally only $5\%-6\%$ worse than the minimum. The experiment ended at $n=20$ as the embedding time at $n=21$ began to take too long.

In the next experiment we collected the data in Table 2 to compare MCT on non-complete graphs for simulated annealing with hybrid methods and purely quantum methods. Once again each experiment was run three times, with separate listings only if different results appeared. The graphs were randomly generated with roughly $50\%$ edge saturation on each trial. The $n$ column refers to the number of vertices in the graph. Simulated annealing was used as a baseline for the minimum number of triangles and the other methods are compared to simulated annealing and printed as (other method - simulated annealing). One can see that the simulated annealing and hybrid methods always agreed in our trials and presumably found the true minimum. Note the hybrid method was limited to $5$ seconds a run. The purely quantum method found the same coloring as the simulated annealing and hybrid method only for $n=10$ and the raw difference between answers got progressively worse as the graph grew larger. Once again the experiment was capped at $n=30$ as for larger graphs the embedding time began to grow large.

The purely quantum methods were studied to understand how they performed when running the $R(4)$ Ramsey problem. Table 3 is the result. The $n$ column refers to the $n$ in $K_{n}$. And again, each trial was run three times. As $R(4)=18$ the minimum value for each row is $0$, however, the purely quantum runs only found this for $K_{6}$. The number of monochromatic triangles found increased with $n$ as is to be expected as the size of the problem grows.

Initially, the goal of this paper was to attempt to develop a method using quantum annealing to improve the lower bounds for classical Ramsey numbers. Ramsey theory finds application in a wide variety of areas through engineering, science, and math, often in surprising ways [5]. To summarize the approach described in this paper, the standard approach was taken to converting the coloring problem into a polynomial unconstrained optimization problem. One of the main novelties of the approach comes from the manner of reducing the polynomial to a quadratic, thus allowing QA to be applied. The order reduction method is derived from the solution using quantum annealing to the more basic, but still NP-complete problem called the MCT problem. The aim of this method is to produce example colorings of the graph which improve the lower bound for unknown Ramsey numbers. Using current quantum and quantum-classical methods to compute the greatest lower bound for $R(4)$ there were not enough qubits and connectivity using the methods of this paper, let alone enough qubits for the loftier goal of improving the lower bound for $R(5)$ or $R(6)$. However, the methods were able to produce $K_{4}$-free colorings of $K_{13}$ as well as finding the maximal $K_{3}$-free coloring for $R(3)$. Our methods were unable to proceed past $K_{14}$ for $K_{4}$-free colorings. To have a classical method of comparison, a python simulated annealing package [19] with the ideal Ramsey unconstrained binary optimization given at the beginning of the Ramsey Theory and order reduction sections. The simulated annealing had little issue finding $K_{4}$ monochromatic-free colorings of $K_{15}$ if given a minute or two, although it was unable to do so for $K_{16}$ or $K_{17}$ even with five or ten minutes. The fact that the simulated annealing was so drastically out-performing D-Wave’s LEAP hybrid solver is indicative of the “naturalness” of the problem to be a QUBO. Note an important consideration for the quantum versus classical comparison of ability is that the tests were done with different equations. Simulated annealing does not require a QUBO. So the simulated annealing was solving an equation with an order of magnitude fewer variables. When simulated annealing was used on the order reduced version, the same version used for QA, the results were worse and slower than the hybrid method. Ramsey theory beyond $R(3)$ appears to naturally be of higher order than $2$. This leads to a dramatic increase in variables when converting to quadratic. The simulated annealing required only $105$ variables when searching for $K_{4}$ monochromatic-free colorings of $K_{15}$. Juxtaposing this, the proposed method when reducing the problem to a QUBO when working with $K_{15}$ required $2967$ variables. The actual required number of variables for this method may be slightly smaller as the pre-coloring idea was not optimized in the implementation. The point is that there is an order of magnitude number of variables greater than the original amount added when degree reduction was required. As such, without more advanced hardware in terms of qubit count and connectivity, an advancement in the theory, or some novel quantum-classical approach it is unlikely that QAs could be used to push the bounds of classical Ramsey Theory. Using the current methodology to compute a maximal $R(4)$ graph would require quantum hardware with the capacity for a fully connected graph of 1000 logical qubits. This number was determined as a rough proportional estimate scaling from the number of variables required for $K_{13}$. Then more qubits were added to the estimate to compensate for the additional work given to the classical computer which may not be feasible as the classical computation is the bottleneck from a time perspective in the hybrid method. Note also that if one wanted to use quantum annealing to compute $R(5)$ or beyond, it is at this moment unclear whether the techniques described in this paper continue to be more efficient than the standard order reduction technique described in the introduction. To determine this would require further analysis in a future paper.

A more immediately success story lies in the MCT algorithm which was a lynchpin to the Ramsey Theory algorithm. As mentioned earlier, the results produced for minimal triangle colorings of complete graphs matched known solutions. In addition an interesting observation was made when looking at minimal triangle colorings of known maximal (though notably not maximum) $R(5)$ colorings. The minimal colorings found by our hybrid runs and matching the known data, were surprisingly close to the number of triangles in those maximal $R(5)$ colorings. The minimal number of triangles in a coloring of $K_{42}$ is $2660$ and all the maximal $R(5)$ colorings of $K_{42}$ were within $15$ of this number. Much of the success of the MCT algorithm is attributed to the ability to convert an MCT problem to a QUBO without introducing any auxiliary variables.

We acknowledge the Institutional Computing (IC) QCAP program at LANL for use of their D-Wave quantum computing allocation. We also acknowledge the use of the D-Wave Leap Advantage quantum computing resources. Assigned: Los Alamos Unclassified Report LA-UR-23-32688.

J.E.P. and S.M.M. designed the project. J.E.P. performed the numerical simulations and optimizations. S.M.M. supervised the whole project. All authors contributed to the discussion, analysis of the results and the writing of the manuscript.

This research was supported by the U.S. Department of Energy (DOE) National Nuclear Security Administration (NNSA) Advanced Simulation and Computing (ASC) Beyond Moore’s Law (BNL) program at Los Alamos National Laboratory (LANL). This research has also been funded by the LANL Laboratory Directed Research and Development (LDRD) under project number 20230546DR. JEP and SMM were funded by LANL LDRD. SMM was also funded by ASC BML. Assigned: Los Alamos Unclassified Report LA-UR-23-32688. LANL is operated by Triad National Security, LLC, for the National Nuclear Security Administration of U.S. Department of Energy (Contract No. 89233218NCA000001). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

All author-produced code will be available upon reasonable request