# Using Machine Learning for Quantum Annealing Accuracy Prediction
## 3 Experimental Results
### Fixed Annealing Time and Fixed UTC Prefactor
#### 3.1.1 Classification  
We start by looking at the classification problem. After fitting a decision tree classifier with _scikit-learn_, we obtain the tree displayed in Figure 2.  
Several observations regarding Figure 2 are noteworthy. First, the tree is sufficiently simple to allow for a manual classification of MC instances into solvable and unsolvable ones by D-Wave 2000Q. The most decisive feature turns out to be the largest eigenvalue of the adjacency matrix of the input graph. If it is larger than the threshold given in Figure 2,the number of edges in the unembedded problem graph seems to be a good predictor of solvability. This is sensible, since less connections in the unembedded problem tend to facilitate embedding and solving on D-Wave. However, further work is needed to understand how to the 5'th largest eigenvalue of the adjacency matrix of the input graph comes into play. Here, a smaller 5'th largest eigenvalue tends to facilitate solvability. Finally, the second largest eigenvalue of the unbedded problem graph (as before, smaller eigenvalues tend to facilitate solvability) and, moreover, the number of edges in the input graph (smaller instances tend to be more likely to be solvable than larger ones) tend to be good predictors of solvability--a finding which seems straightforward.  
Although the importance of the 5'th largest eigenvalue (of the adjacency matrix of the input graph) is a surprising result, the predictive power of the largest and second largest eigenvalues is sensible, since those are well known to predict a variety of structural properties of a graph, see [22; 23]: for instance, the largest eigenvalue is related to the largest degree of a graph. In two follow-up experiments, removing only the 5'th largest eigenvalue from the set of predictors turned out to decrease performance marginally (the accuracy decreases by 0.37%, and the recall decreases by 0.51%). Removing all eigenvalues apart from the largest one seems to decrease performance more substantially (the accuracy drops by 2.9%, but the recall goes up by 0.83%).  
One may wonder whether the nodes of the decision tree labeled as \"Solvable\" correspond to subclasses of graphs for which MC can be solved exactly in polynomial time or are easier in any other way, but there is no published work to support such hypothesis. In fact, we are aware of no research that links properties of the 5'th largest eigenvalue with any other non-trivial graph property.  
An evaluation of the decision tree of Figure 2 on the unseen validation data yields the confusion matrix given in Table 1. We observe that our machine learning model is able to accurately classify solvable instances with a probability of around 83.7%, and unsolvable ones with a probability of around 84.1%.  
Figure 2: Decision tree for classification of MC instances into solvable and unsolvable, using the features outlined in Section 2. Setting of fixed annealing time and fixed UTC prefactor. Left branches denote _true_ bifurcations, right branches denote _false_ bifurcations. Green leaves are solvable cases, red leaves are unsolvable cases, and inner nodes are colored in blue.