# A Convex Hull-Based Machine Learning Algorithm for Multipartite Entanglement Classification
## 2 The Construction of the Classifier  
### Convex Hull Approximation  
As with the detection of entanglement, a natural question is asked: how is it decided which class a given state belongs to? However, methods for distinguishing between the GHZ class and the W class are very rare. For the detection of entanglement, the entanglement witness [23] can be used, as the W class states form a convex set. However, it is not clear how one can show that a state is tripartite entangled and belongs to the W class. This cannot be accomplished with witnesses; since they are designed to show that a state lies outside a convex set, they fail to prove that a state is inside a convex set. The traditional entanglement witness is used as a separability-entanglement classifier. An observable \(\mathcal{W}\) is called an entanglement witness (or witness for short) if \(\mathit{Tr}(\mathcal{W}\varrho_{s})\geq 0\) for all separable \(\varrho_{s}\) and \(\mathit{Tr}(\mathcal{W}\varrho_{e})<0\) for at least one entangled \(\varrho_{e}\) holds. Thus, if one measures \(\mathit{Tr}(\mathcal{W}\varrho)<0\), then one knows for sure that the state \(\varrho\) is entangled. From a geometric point of view, both the state spaces and the entangled spaces form a convex set. The witness forms a hyperplane in the space, dividing it into two parts. However, the boundaries of the convex set are so complicated that direct application of supervised learning to the classification will not be satisfying. In addition, due to the lack of prior knowledge for training, the neural network cannot provide an acceptable accuracy. In a study in 2018, researchers proposed a method of classification for entangled states and separable states via constructing a convex hull approximating the set of entangled states [24]. Entangled states form a convex set in the spaces, and as shown in Figure 1, W states also form a convex set inside the set of GHZ states. Therefore, inspired by [24], we introduce the convex hull approximation [25] here. The construction of convex hull is one of the most fundamental problems in computational geometry. Here, we approximate the W states from inside, for the W state space is a close convex set, and its critical points are all the pure W states [17]. We define a convex hull as follows:  
\[\mathcal{C}=\mathit{conv}(\{c_{1},\,\dots,\,c_{n}\}) \tag{4}\]  
where \(c_{1},\,\dots,\,c_{n}\in\mathcal{X}\) are pure W states sampled randomly. \(\mathcal{C}\) is said to be a convex hull approximation (CHA) of the W state space. To find the critical points, we propose an iterative algorithm in Section 3.2.2. With the increasing of the number of critical points, the convex hull approaches the W state space. In other words, \(\mathcal{C}\) will be a more accurate CHA of the W state space if we construct it with more pure W states. With this we can approximately tell whether a state \(\rho\) is a W state or not by testing if its feature vector is in \(\mathcal{C}\). This is equivalent to determining whether the feature vector can be written as a convex combination of \(c_{i}\) by solving the following linear programming:  
\[\mathit{max}\,\,\alpha\quad\mathit{s.t.}\,\,\alpha p\in\mathcal{C} \tag{5}\]  
The constraint condition is equivalent to the following expansion:  
\[\alpha p=\sum_{i=1}^{m}\lambda_{i}c_{i},\quad\lambda_{i}\geq 0,\quad\sum_{i} \lambda_{i}=1 \tag{6}\]  
Here, \(\alpha=\alpha(\mathcal{C},p)\) is a function of \(\mathcal{C}\) and \(p\), and \(p\) is the feature vector of the state \(\rho\) to be tested. If \(\alpha(\mathcal{C},p)\geq 1\), then \(p\) is in \(\mathcal{C}\), and thus \(\rho\) is a W state; otherwise, \(\rho\) it is highly possible that this is a GHZ state. A schematic picture of the convex hull approximation is shown in Figure 2.  
Then, we propose an iterative algorithm for detecting the W states. At the first step, we use a few critical points (i.e., pure W states to build a CHA \(\mathcal{C}\)).