# Using Machine Learning for Quantum Annealing Accuracy Prediction
## 1 Introduction
As shown in ([PERSON], 1998; [PERSON], 1998), the QUBO function \[H=-A\sum_{i\in V}x_{i}+B\sum_{(i,j)\in\mathbb{E}}x_{i}x_{j},\] (2) \[x_{i}\in\{0,1\}\text{ for all }i\in V,\text{ achieves a minimum if and only if the vertices }i\in V\text{ for which }x_{i}=1\text{ form a maximum clique, where the two constants can be chosen as }A=1\text{, }B=2\text{ }\text  
graph, the easier it will be to embed it onto the D-Wave 2000Q hardware, and the larger the embeded problems \(P\) can be. 3. After annealing, it is not guaranteed that chained qubits on the Chimera graph take the same value, even though they represent the same logical qubit. This phenomenon is called a _broken chain_. To obtain an interpretable solution of logical qubits, definite values have to be assigned to each logical qubit occurring in Equation (1). Although there is no unique way to accomplish this task, D-Wave offers several default methods to _unembed_ chains. Those include _majority vote_ or _minimize energy_. Majority vote sets the value of a chained qubit to the value (zero or one) taken most often among the hardware qubits which represent the logical qubit. In case of a draw, an unbiased coin flip is used. The minimize energy option determines the final value of all logical qubits via a post-processing step using some form of gradient descent. We employ majority vote in the remainder of the article. Applying machine learning to predict features of a quantum device is a timely area of research. Existing work mostly focuses on gate quantum computing. For instance, machine learning is employed to help tune the behavior of quantum systems, such as computing the overlap of two quantum states [5], quantum circuit optimization [6; 7], or readout of states with higher assignment fidelities under noise conditions [8]. Other works address parameter tuning of variational quantum algorithms [9] or the quantum approximate optimization algorithm (QAOA) algorithm of [10], see [11]. The closest to our approach is [12], wherein the authors use machine learning techniques to identify graph problems that are easy to solve using QAOA. However, they use the quantum gate model and their specific objective is a bit different--to decide whether QAOA or the classical Goemans-Williamson algorithm will perform better on instances of the maximum cut problem. In contrast, we compare the quality of the solution found with the quantum algorithm against an optimal solution, and our optimization problem is the maximum clique problem. Somewhat related, in [13; 14] the authors use a differential evolution optimizer to tune three parameters of D-Wave 2000Q, namely spin reversal, anneal offsets, and chain weights. However, machine learning methods are not used, and the objective is to optimize parameters, rather than predict performance. Figure 1: The hardware graph \(H\) of D-Wave 2000Q is a \(12\times 12\) array of unit cells, wherein each unit cell is a \(4\times 4\) bipartite graph. The depicted graph is the hardware connectivity graph of the D-Wave 2000Q machine at Los Alamos National Laboratory, showing a few of its qubits disabled due to hardware errors. The particular connectivity structure of the hardware graph is referred to as a _Chimera graph_. Finally, some authors have addressed the difficulty of solving NP-hard problems to optimality by trying to develop classical approximation algorithms for them or proving the difficulty of their prediction. For the MC problem, it has been shown in [15] that for every positive \(\varepsilon\), no polynomial-time algorithm exists that approximately computes the maximum clique size to within a factor of \(O(n^{1-\varepsilon})\), unless P = NP, which indicates the MC problem is hard to solve even approximately. There have also been results establishing the fixed-parameter intractability of the MC problem [16]. The difference between those results and our work is that we do not try to determine the difficulty of any particular instance of the MC clique problem per se, but how difficult that problem is for the D-Wave 2000Q quantum annealer.