# Using Machine Learning for Quantum Annealing Accuracy Prediction
## 1 Introduction  
Quantum annealing is an emerging technology with the potential to provide high quality solutions to NP-hard problems. In this work, we focus on the devices built by D-Wave Systems, Inc., specifically the D-Wave 2000Q annealer, designed to minimize functions of the following form,  
\[H(x_{1},\ldots,x_{n})=\sum_{i=1}^{N}h_{i}x_{i}+\sum_{i<j}l_{ij}x_{i}x_{j}, \tag{1}\]  
where \(x_{i}\) are unknown binary variables. The linear weights \(h_{i}\in\mathbb{R}\) and the quadratic coupler weights \(l_{ij}\in\mathbb{R}\) are chosen by the user and define the problem under investigation. If \(x_{i}\in\{0,1\}\), Equation (1) is called a _quadratic unconstrained binary optimization (QUBO)_ problem, and if \(x_{i}\in\{-1,+1\}\) it is called an _Ising model_. Both QUBO and Ising model formulations are equivalent [1]. Many important NP-hard problems can be expressed as the minimization of a function of the form of Equation (1), see [2]. In the remainder of the article, we focus on the QUBO formulation. The D-Wave 2000Q device aims to minimize a function of the form of Equation (1) via a process called quantum annealing. For this, Equation (1) is mapped to a physical system, consisting of hardware qubits which are situated on the D-Wave chip. Those areinitialized in a superposition (enforced by a so-called transverse field), with no information about the problem (Equation (1)) at the start. During annealing, the system transitions from the initial superposition of all qubits to the actual problem Hamiltonian of Equation (1), where it is hoped that a slow transition gives the system enough time to arrange itself in an energy minimum along the path. After annealing, a solution of Equation (1) is read off from the hardware qubits. Although solutions returned by the D-Wave 2000Q annealer for minimization problems of the type of Equation (1) are typically of very high quality, they are not guaranteed to be optimal. In fact, there is no guarantee that the solutions returned by a D-Wave device keep any level of accuracy. In this article, we aim to identify those types of QUBOs that are solvable on D-Wave 2000Q with given hardware parameters, without actually using the annealer. This could help decide on what resources (annealing time, number of reads) should be allocated to some problem of interest in advance. We focus on the maximum clique (MC) problem, and explore two different types of classifications. First, we train a binary machine learning classification model on basic problem characteristics (such as density of the input graph) to discriminate between solvable and unsolvable instances of MC. The resulting model also allows us to rank the features used for training by importance. Classification is performed using the open source machine learning package _scikit-learn_ in Python (2016). Second, we show that the decision problem of whether an MC instance will be solved optimally by D-Wave can be predicted with high accuracy by a simple decision tree on the same basic problem characteristics. Third, we train a machine learning regression model to predict the clique size returned by the annealer. Let \(G=(V,E)\) be a graph (referred to as _original graph_) consisting of a vertex set \(V\subseteq\{1,\ldots,n\}\) and edge set \(E\subseteq V\times V\). A _clique_ in \(G\) is any subgraph \(C\) of \(G\) that is _complete_, i.e., there is an edge between each pair of vertices of \(C\). The MC problem asks us to find a clique of maximum size, called a _maximum clique_, which is an NP-hard problem with many applications. To solve an instance of MC on the D-Wave annealer, we proceed as follows:  
1. The task of finding a maximum clique has to be mapped to a formulation of the type of Equation (1).