# Using Machine Learning for Quantum Annealing Accuracy Prediction
## 2 Methods
### Classification  
Our task is to relate graph features to a given binary indicator from D-Wave expressing if an instance could be solved by the annealer to optimality. Several avenues exist to accomplish this task, for instance via (penalized) linear regression or logistic regression, or via more sophisticated machine learning models. The following highlights some of the challenges. First, in order to have a well-defined decision problem for finding maximum cliques, we require a ground truth determined with a classical method. We define an instance of MC to be solvable by the D-Wave 2000Q if the clique determined by D-Wave has size equal to the maximum clique size found with the function _graph_clique_number_ of the _NetworkX_ package in Python [19; 20], which is an exact solver. In this case, the class label was set to 1 (solvable), and 0 otherwise. Second, a couple of choices have to be made, both regarding the machine learning model for regression, as well as the set of graph features selected for prediction. We decided to use a decision tree classifier for two main reasons: The classifier achieved good performance in the classification task we consider and, most importantly, it allows us to obtain an interpretable output in the form of a decision tree. The decision tree highlights in what order or importance the features contribute to solvability on the D-Wave 2000Q, and by tuning the decision tree for simplicity, it allows one to (manually) determine with high probability in advance if an instance is likely solvable. Third, an assortment of graph-related features has to be selected to serve as inputs to the machine learning model. Those features are selected to cover a wide variety of potential metrics impacting solvability, however the list below is neither exhaustive nor rigorously proven. The following features went into the machine learning model threefold (unless noted otherwise), precisely for the original input graph \(G\), its unembedded graph \(P\) of the MC problem, and its embedded graph \(P^{\prime}\) on the Chimera architecture (see Section 1):  
1. the graph density (_Graph_Density_);
2. the minimal, maximal, and average degree of any vertex (_Graph_Min_Degree_, _Graph_Max_Degree_, and _Graph_Mean_Degree_);
3. the number of triangles in the input and unembedded graphs (_Graph_Num_Triangles_);
4. the number of nodes and edges (_Graph_Num_Nodes_ and _Graph_Num_Edges_);
5. the five largest eigenvalues of the adjacency matrix (_Graph_Largest_Eigenvalue_, _Graph_2 nd_Largest_Eigenvalue_, etc., up to _Graph_5 th_Largest_Eigenvalue_), and the spectral gap (the difference between the moduli of the two largest eigenvalues) of the adjacency matrix (_Graph_Spectral_Gap_). For brevity of notation, we refer with \"eigenvalue of a graph\" to the eigenvalue of its adjacency matrix. Additionally, for the embedded graph \(P^{\prime}\) on the Chimera architecture, we included the following features into the model:  
1. the minimal, maximal, and average chain length occurring in the embedding (_Min_Chain_Length_, _Max_Chain_Length_, and _Avg_Chain_Length_);
2. the chain strength computed with D-Wave's _uniform torque compensation_ feature (_Chain_Strength_), see [18], using either a fixed UTC prefactor (Section 3.1) or a randomly selected one in \([0.5,3]\) (Section 3.2);
3. the annealing time (in microseconds), which was selected uniformly at random in \([1,2000]\) (_Annealing_Time_). In total, there were 46 features that were included as inputs to the machine learning model. Using those features of the training MC instances and their maximum clique result computed by the D-Wave 2000Q annealer, we train a machine learning classifier implemented in the _sklearn.tree.DecisionTreeClassifier()_ class provided in _scikit-learn_[3]. After performing a grid search across the following parameters, we selected _max_depth=5, random_state=0_, and _min_impurity_decrease=0.005_. All other parameters were kept at their default values.