Experimental Determination of Ramsey Numbers

(Left to Right) Zhengbing Bian, Fabian Chudak, William G. Macready, Lane Clark

Authors: Zhengbing Bian¹, Fabian Chudak¹, William G. Macready¹, 
Lane Clark², Frank Gaitan³

Affiliation:
¹D-Wave Systems Inc., Burnaby, British Columbia, Canada
²Dept. of Mathematics, Southern Illinois University, Carbondale, Illinois, USA
³Laboratory for Physical Sciences, College Park, Maryland, USA

                                                                       Frank Gaitan 

Ramsey numbers are most easily introduced through the Party Problem. Here a host is assembling a guest list of N people. She wonders whether the list might contain a group of m guests who are mutual friends, or a group of n guests who are mutual strangers. Surprisingly, it can be proved [1] that there exists a threshold size R(m,n) for the guest list such that: (i) if N ≥ R(m,n), then all guest lists are sure to contain a clique of m mutual friends or one of n mutual strangers, and (ii) if N < R(m,n), then a guest list exists which contains no group of m mutual friends or n mutual strangers. The threshold value R(m,n) is known as a two-color Ramsey number.

It proves fruitful to convert the N-person guest list into an N-vertex graph by associating each guest with a distinct vertex in the graph. We draw a red (blue) edge between two vertices if the two corresponding people know (do not know) each other. Thus, if m (n) guests all know (do not know) each other, there will be a red (blue) edge connecting any two of the m (n) corresponding vertices. The m (n) mutual friends (strangers) are said to form a red m-clique (blue n-clique). In this way, each N-person guest list is associated with a particular red/blue coloring of the edges of a complete N-vertex graph (in which every pair of vertices is joined by an edge). The threshold result for the Party Problem is now the following statement about graphs: if N ≥ R(m,n), then every red-blue edge coloring of a complete N-vertex graph will contain either a red m-clique or a blue n-clique, while if N < R(m,n), a red/blue coloring exists which has no red m-clique or blue n-clique. The use of two colors is why R(m,n) is called a two-color Ramsey number. Figure 1 shows a 6-vertex graph that contains two blue 3-cliques and no red 3-cliques.

Figure 1: A 6-vertex graph representing a Guest List in which there are: (i) two cliques of three people that are mutual strangers: Guests 1, 2, and 3, and Guests 4, 5, and 6; and (ii) no cliques of three mutual friends.

As m and n increase, the threshold R(m,n) grows extremely rapidly, and even for quite small values of m and n, becomes extraordinarily difficult to compute. In fact, for m, n ≥ 3, only nine values of R(m,n) are currently known [2]. To dramatize the difficulty of calculating R(m,n), Spencer [3] recounts a famous vignette due to Paul Erdos in which aliens have invaded earth and threaten to destroy it in one year unless humans can correctly determine R(5,5). Erdos noted that this could probably be done if all the best minds and most powerful computers were focused on the task. In this case, the appropriate response to the alien demand would be to get busy. However, Erdos pointed out that if the aliens had instead demanded R(6,6), earthlings should immediately launch a first-strike on the aliens as there is little hope of meeting their demand.

In 2012 a quantum algorithm for computing two-color Ramsey numbers appeared which was based on adiabatic quantum evolution [4]. The essential step in constructing the Ramsey number algorithm was to transform a Ramsey number computation into an optimization problem whose solution is an N-vertex graph that has the smallest total count of red m-cliques and blue n-cliques. The optimization cost function assigns to each graph the total count of red m-cliques and blue n-cliques that it contains. Thus, if N < R(m,n), an optimal graph will have zero cost, corresponding to a guest list with no m-clique of friends or n-clique of strangers. On the other hand, if N ≥ R(m,n), then an optimal graph has non-zero cost since all guest lists will have a red m-clique or blue n-clique. The Ramsey number quantum algorithm associates each graph with a unique quantum state of the qubit-register and constructs the qubit interactions so that the energy of this state (the Ramsey energy) is the value of the graph’s cost function. By design, the minimum Ramsey energy is the minimum value of the cost function, and the associated quantum state identifies a minimum cost graph which is thus a solution of the optimization problem.

The adiabatic quantum evolution algorithm [5] is used to transform a fiducial state of the qubit register into a state with lowest Ramsey energy. The Ramsey number algorithm implements the following iterative procedure. It starts with graphs with N < R(m,n), and carries out the above described adiabatic quantum evolution. At the end of the evolution, the qubit state is measured and the Ramsey energy is determined from the measurement result. In the adiabatic limit, for N < R(m,n), the measured Ramsey energy will be zero. The number of vertices N is then increased by one, the adiabatic evolution and measurement is re-run, and the Ramsey energy re-computed. This process is repeated until a non-zero Ramsey energy is first found. In the adiabatic limit, the final value of N is the Ramsey number R(m,n) since it is the smallest N value for which all graphs have a non-zero cost and thus contain a red m-clique or blue n-clique. Ref. [5] tested the algorithm via numerical simulations and it correctly found the Ramsey numbers R(3,3) = 6 and R(m,2) = m for 5 ≤ m ≤ 7.

Figure 2: Image of the harness used to lower the D-Wave One 128 qubit chip into a dilution refrigerator. The chip can be seen at the bottom of the harness.

Recently, the Ramsey number quantum algorithm was successfully implemented on a D-Wave One quantum annealing device [6]. Quantum annealing [7] can be used to drive the adiabatic dynamics of the Ramsey number algorithm even at finite temperature and in the presence of decoherence. The D-Wave One processor is a chip that contains 128 rf SQUID flux qubits. The chip is shown in Figure 2 at the end of a harness which is used to place it in a dilution refrigerator that operates at 20mK.

The chip used in the Ramsey number experiments contained 106 useable qubits. Figure 3 shows the chip layout, where the grey circles correspond to useable qubits, and the white circles to qubits that could not be calibrated into the desired tolerance range and so were not used. The edges joining qubits represent couplers that allow the qubits to interact and which can take on programmed values.

Figure 3: Layout of the 128 qubit chip. The chip architecture is a 4x4 array of unit cells, with each unit cell containing 8 qubits. Qubits are labeled from 1 to 128, and edges between qubits indicate couplers which may take programmable values. Grey qubits indicate usable qubits, while white qubits indicate qubits which, due to fabrication defects, could not be calibrated to operating tolerances and were not used. All Ramsey number experiments were done on a chip with 106 usable qubits.

Figure 4 shows an 8-qubit unit cell in the chip. Each red loop highlights one of the rf SQUID flux qubits. Programming the Ramsey number cost function onto the D-Wave One chip requires embedding the optimization variables into the qubit architecture in a way that respects the qubit-qubit couplings on the chip. Figure 5 shows the embedding used to determine the Ramsey number R(8,2). Once the cost function for a given Ramsey number has been programmed on to the chip, 100,000 quantum annealing sweeps and measurements were carried out, and the resulting Ramsey energies binned into a histogram.

In all cases considered, the lowest Ramsey energy found was identical to the minimum Ramsey energy which was known from previous work [4]. The protocol for the Ramsey number algorithm was carried out and the value of N at which the minimum Ramsey energy first became non-zero was identified with the Ramsey number R(m,n). The experiments correctly determined that R(3,3) = 6, and R(m,2) = m for 4 ≤ m ≤ 8. Although all Ramsey numbers found in Ref. [6] correspond to known Ramsey numbers, it is possible that future hardware generations may be large enough to allow unknown Ramsey numbers to be found.

Figure 4: A single 8 qubit unit cell. Each red loop highlights an rf SQUID flux qubit.

Figure 5: Embedding used to compute the Ramsey number R(8,2) that produced the needed qubit couplings. In low energy states, like-colored qubits have the same Bloch vector and constitute a single effective qubit. This allows an indirect coupling of qubits that are not directly coupled on the chip.

References:
[1] Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, "Ramsey Theory" (Wiley, NY, 1990).
[2] See Wikipedia page on Ramsey's_theorem for a list of all known two-color Ramsey numbers, as well as bounds on R(m,n) when its value is not known, for m, n ≤ 10.
[3] Joel Spencer, "Ten Lectures on the Probabilistic Method", 2nd ed. (SIAM, Philadelphia, 1994).
[4] Frank Gaitan and Lane Clark, "Ramsey Numbers and Adiabatic Quantum Computing", Physical Review Letters 108, 010501 (2012). Abstract.
[5] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser, "Quantum Computation by Adiabatic Evolution", arXiv:quant-ph/0001106 (2000).
[6] Zhengbing Bian, Fabian Chudak, William G. Macready, Lane Clark, and Frank Gaitan, "Experimental Determination of Ramsey Numbers", Physical Review Letters, 111, 130505 (2013). Abstract.
[7] Tadashi Kadowaki and Hidetoshi Nishimori, "Quantum annealing in the transverse Ising model", Physical Review E 58, 5355 (1998). Abstract; Giuseppe E. Santoro, Roman Martoňák, Erio Tosatti, Roberto Car, "Theory of Quantum Annealing of an Ising Spin Glass", Science 295, 2427 (2002). Abstract.