Machine Learning-Derived Entanglement Witnesses

In this work, we show a correspondence between linear support vector machines (SVMs) and entanglement witnesses, and use this correspondence to generate entanglement witnesses for bipartite and tripartite qubit (and qudit) target entangled states. An SVM allows for the construction of a hyperplane that clearly delineates between separable states and the target entangled state; this hyperplane is a weighted sum of observables ('features') whose coefficients are optimized during the training of the SVM. In contrast to other methods such as deep neural networks, the training of an SVM is a convex optimization problem and always yields an 'optimal' solution. <span> <span>We demonstrate with this method the ability to obtain witnesses that require only local measurements even when the target state is a non-stabilizer state.</span></span> Furthermore, we show that SVMs are flexible enough to allow us to rank features, and to reduce the number of features systematically while bounding the inference error. This programmatic approach will allow us to streamline the detection of entangled states in experiment.

Quantum entanglement is an essential resource in quantum information processing, playing an important role in many applications in quantum information processing including quantum cryptography @ekert1991quantum_QKD, quantum computation @briegel2009measurement, and sensing @pirandola2018advances_sensing. <span> <span> Recent work has shown the utility of high-dimensional photonic states for quantum communications @ali2007large [@zhong2015photon], quantum imaging @chen2014quantum, and quantum information processing @lu2019quantum in general; in quantum nonlinear photonics, where the generation of entangled photons beyond $N = 2$ remains challenging and hampered by loss, the use of high-dimensional ($d>2$) states of biphotons instead has become the more appealing and robust alternative @kues2017chip [@imany2019high]. </span></span> It is therefore crucial to have an efficient method that allows us to experimentally detect the presence of entanglement in high-dimensional ($d$), though not necessarily high-particle number ($N$), quantum systems. The brute force approach is to fully characterize a system by performing quantum state tomography and calculating separability measures from the recovered density matrix. However, tomography is experimentally and computationally demanding; for a state consisting of $N$ particles, with each residing in a d-dimensional Hilbert space, we would have to perform $M = 
O(d^{2N})$ measurements. In addition to the sheer number of measurements required, there is also the computational cost of regression to recover the density matrix. With full characterization of a high-dimensional quantum state being so expensive experimentally and computationally, classification of a state becomes a more attractive option.

<span> <span> Recent studies of the entangled-separable quantum state classifiers have utilized aspects of machine learning, such as neural networks @ma2018transforming_ML_Entangle, and convex hull colemanryan@example.org. Yet others have attempted to replaced the conventional maximal-likelihood estimation of density matrices @DFVJames_2001 with deep learning approaches @lohani2020machine. </span></span> However, the number of features (or observables) taken as input into such systems required to provide correct classification and estimation often grow to the number required for full state tomography.

A more efficient approach is to construct an observable known as an entanglement witness $\hat{W}$. The expectation value of this observable would give a non-negative value for all separable states, while a target entangled state would give a negative value. Simply measuring the expectation value $\langle\hat{W}\rangle$ for a given system is enough to tell us if it is close to the desired entangled state, without the need to find the full density matrix. There is also at least a quadratic reduction in the number of measurements required, $O(d^N)$ [^1] , compared to $O(d^{2N})$ for state tomography.

There is extensive literature on constructing entanglement witnesses. These include using the stabilizer formalism @toth2005entanglement_stabilizer to derive witnesses for multi-partite, graph and cluster states. Witnesses can also be constructed through the 'fidelity method' @bourennane2004experimental: $$W=cI-|\psi_{\mathrm{target}}\rangle \langle \psi_{\mathrm{target}} |,$$ with $c$ simply a classical c-number, and $|\psi_{\mathrm{target}}\rangle $ the target state. However, this often results in witnesses that require a large number of measurements @bourennane2004experimental.

In this work, we use the correspondence between linear support vector machines (SVMs) @vapnik1963pattern and entanglement witnesses to derive witnesses for entangled states. An SVM is a supervised machine learning (ML) technique that uses a hyperplane to perform binary classification. This is analogous to the action of an entanglement witness $W$; on one side of the hyperplane lie all the separable states ($tr(\rho W)\geq 0$), while the other side ($tr(\rho W)< 0$) contains only entangled states, including the target state.

We will limit ourselves to local measurements; the ansatz we will use for the witness is: $$\hat{W} = \sum_{k_1, k_2, \cdots, k_N}  a_{k_1, k_2, \cdots, k_N} 
    \sigma_{k_1} \otimes \sigma_{k_2} \otimes \cdots \otimes \sigma_{k_N},
    \label{eqn:W_expect}$$ with each term in the witness simply being a string of (generalized) Pauli matrices $\sigma_k \in \{I,X, Y, Z\}$, and the length of the string corresponding to the number $N$ of qubits (qudits) in the system. <span>In the case of qudits ($d>2$), each Pauli 'string' would be a sum of the generalized Pauli string and its Hermitian conjugate.</span>

The training of the SVM consists of first generating the separable and entangled states. For each of these states, the expectation values of all the Pauli strings ($x_{\vec{k}}\equiv  \langle \sigma_{k_1} \otimes \sigma_{k_2} \otimes \cdots \otimes \sigma_{k_N} \rangle $) are then computed; these will be the 'features' used to train the SVM. Optimization of the SVM involves varying the coefficients $a_{\vec{k}}$ so that the weighted sum of the features ($\langle\hat{W}\rangle = \sum_{\vec{k}} a_{\vec{k}} x_{\vec{k}}$) gives the correct classification for each state. We note that, unlike many other ML techniques such as deep learning, the training of an SVM is convex; if a solution exists for the given target state and ansatz, the *optimal* SVM [^2] will be found.

In what follows, we will demonstrate that our SVM approach allows for the derivation of entanglement witnesses for bipartite and tripartite qubit states, as well as bipartite qudit states, and show how the technique can be extended to higher dimensions and particles. <span> In particular, we recover a witness for tripartite W-state that utilizes only local measurements, but requireing far fewer features than what has previously been demonstrated @guhne2003investigating [@bourennane2004experimental] and comparable noise tolerance. </span> Additionally, we show that our SVM formalism allows for the programmatic removal of features, i.e., reducing the number of experimental measurements, in exchange for a lower tolerance to white noise, in a manner similar to @Sciara_PhysRevLett.122.120501.

Basic Scheme and Application to a Simple Example
================================================

As we saw in Eqn \[eqn:W\_expect\] and the discussion that followed, an SVM is a linear classifier that takes a weighted sum of 'features' (expectation values $x_{\vec{k}}$ ) of an object (quantum state) and predicts whether it belongs in one class (entangled) or another (separable). More formally, we can write the classifier as: $$\begin{array}{l}
    y = \sum a_{\vec{k}} x_{\vec{k}}  \\
    \mathrm{If\ separable: \ } y\geq 0 \\
    \mathrm{If \ entangled: \ } y< 0. 
    \end{array}$$ The coefficients $a_{\vec{k}}$ are 'learned' by using a set of training examples, each with label $\hat{y}$ and features $x_{\vec{k}}$; the labels for entangled states will be $\hat{y} = -1$, and $\hat{y} = +1$ for separable states. The learning involves the minimization of the loss function: $$\mathcal{L} =\frac{1}{T}\sum_{t=1}^T \left[\mathrm{max}(0,1- \hat{y}^{(t)} \cdot y^{(t)})\right]^{m}+\lambda\sum_{\vec{k}} |a_{\vec{k}}|,
\label{eqn:lossfunc}$$ with respect to the coefficients $a_{\vec{k}}$. The first summation is over all training examples $T$, $\hat{y}^{(t)}$ (${y}^{(t)}$) is the label (prediction) for a particular example, $m = 1$ or 2, and the second summation (over $\vec{k}$) is a regularization term (whose relative importance can be varied with a scaling factor, $\lambda$) to limit the number of non-zero features.

The first term of the loss function (Eqn \[eqn:lossfunc\]) is known as the hinge loss. When $m$ is equal to either 1 or 2, the loss function is a convex function of the coefficients $a_{\vec{k}}$; that is, the loss function has only a single global minimum for a set of training examples, though the trained coefficients for $m = 1$ will be different from $m=2$. We will often choose $m=1$ so that there are fewer non-zero features present (the SVM uses 'sparse' features); however, $m = 2$ is often needed when the entangled states are very nearly 'touching' the separable states and a fine boundary is required @lee2013study.

To illustrate the training of the SVM, we use a simple illustrative example. Let us find the entanglement witness for the bipartite qubit Bell-state: $$|\psi_{\mathrm{target}}\rangle = \frac{1}{\sqrt{2}}
       \left(  |0 0\rangle +  |1 1\rangle    \right),
       \notag$$ with $|0\rangle$ and $|1\rangle$ being the eigenstates of the Pauli matrix $\sigma_{z}$. We can construct a set of density matrices (representing the class of entangled states) by adding white noise to the target state: $$\rho_{\mathrm{ent}}(p) = (1-p)|\psi_{\mathrm{target}}\rangle\langle\psi_{\mathrm{target}}| + \frac{p}{4}\mathcal{I},
    \label{eq:werner}$$ and varying $p$ uniformly over the range $\left[0, \frac{2}{3}\right)$. Each training example for the entangled class will consist of the label $\hat{y}(p) = -1$ and the features $\{x_{\vec{k}}(p)\} = \{ tr(\rho_{ent}(p) \sigma_{k_1}\otimes \sigma_{k_2})  \}$.

On the other hand, when constructing the training data for bipartite separable states we can simply use pure states, due to the linear nature of the entanglement witness. [^3] The separable states are sampled in a Haar-distributed fashion; each training example $|\psi_{sep}\rangle $ for the separable class consists of the label $\hat{y} = +1$ and features $\{x_{\vec{k}}\} = \{ \langle{\psi_{sep}}|\sigma_{k_1}\otimes \sigma_{k_2}) |{\psi_{sep}}\rangle \}$.

Four thousand examples of each class are generated using `NumPy`, a linear algebra library in `Python`, and the ML library `SciKit-Learn` @scikit-learn is used to train the SVM. The process is repeated for the three other Bell states, and the results are tabulated in Table \[tab:bellstates\]. Only features in the trained SVM with coefficients whose absolute value greater than 0.01 are shown; all other features are discarded. The witness is verified using $10^4$ samples of separable states and $10^4$ samples of entangled states with noise in the range of $p\in[0, \frac{1}{4}]$. The SVM is observed to give the right classification 100% of the time.

<span> c | c</span> Target State & Witness\
$|\Phi^{+}\rangle = \frac{1}{\sqrt{2}}\left( |00\rangle +|11\rangle \right)$ & $ I\otimes {I} - X\otimes {X} + Y\otimes{Y} - Z\otimes{Z}$\
\
$|\Phi^{-}\rangle = \frac{1}{\sqrt{2}}\left( |00\rangle - |11\rangle \right)$ & $ I\otimes {I} + X\otimes {X} - Y\otimes{Y} - Z\otimes{Z}$\
\
$|\Psi^{+}\rangle = \frac{1}{\sqrt{2}}\left( |01\rangle + |10\rangle \right)$ & $ I\otimes {I} - X\otimes {X} - Y\otimes{Y} + Z\otimes{Z}$\
\
$|\Psi^{-}\rangle = \frac{1}{\sqrt{2}}\left(  |01\rangle - |10\rangle \right)$ & $ I\otimes {I} + X\otimes {X} + Y\otimes{Y} + Z\otimes{Z}$\

Application of the Method to Tripartite Qubit States
====================================================

In this section, we will extend the method presented in Section I to the tripartite qubit states: $$\begin{split}
|{GHZ}\rangle & = \frac{1}{\sqrt{2}}\left( |000\rangle+ |111\rangle  \right), \\
|{W}\rangle & = \frac{1}{\sqrt{2}}\left( |001\rangle+ |010\rangle   + |100\rangle \right)
\end{split}
\label{eq:GHZ_W}$$

We first point out that, unlike the bipartite Bell states, the GHZ and W states are not interconvertible with the use of local unitary operations. They belong to separate classes of entanglement. Furthermore, *separable* states in tripartite systems can be further divided into (1) fully-separable ($fs$) states: $$\rho^{(1,2,3)}_{fs} = \rho_1 \otimes \rho_2 \otimes \rho_3
    \nonumber$$ and (2) bi-separable ($bs$) states: $$\rho^{(1,2,3)}_{bs} =  \rho^{(i)} \otimes \rho^{(j,k)}_{ent}
    \nonumber$$ where $i,j,k$ are any combination of the particle labels 1,2, and 3, and $\rho_{ent}^{(j,k)}$ is a non-separable state of particles $j$ and $k$. Training data for $\rho^{(1,2,3)}_{bs}$ is generated by sampling over the Hilbert-Schmidt-distributed space of single-qubit and bi-qubit density matrices. As for the entangled state, we again use the Werner state (Eqn. \[eq:werner\] ) to generate the training data for that class of states.

Bar graphs indicating the non-zero coefficients for the two derived witnesses (Eqn. \[eq:GHZ\_W\]) are shown in Fig. \[fig:W\_GHZ\]. The coefficients are normalized to a maximum value of 1; any coefficients with a magnitude of less than 0.01 is removed. We note that the SVM-derived witness for the GHZ state is equivalent to the theoretical witness obtained with Mermin's inequality, with the features corresponding to the stabilizers of the GHZ state @toth2005entanglement_stabilizer. This agreement further validates the SVM scheme.

What is noteworthy, though, is the witness derived for the W state, a non-stabilizer state. For such a state, it is not possible to find stabilizing operators that are the tensor products of single-qubit operations @toth2005entanglement_stabilizer [@zhan2020detecting__Unfaithful]. Therefore, witnesses derived in previous works for the W state required non-local measurements. However, using our method, we have found a witness that requires only local measurements. To the best of our knowledge, we have arrived at a novel $W$ state witness. It tolerates white noise up to $p$ = 0.47 (Fig. \[fig:RFE\]b), which is as performant as witnesses that use non-local operators @zhan2020detecting__Unfaithful.

We note that the witnesses derived can be further simplified. We can systematically reduce the number of features in the witness to lower experimental complexity, but at the expense of lower noise tolerance, by using the Recursive Feature Elimination (RFE) algorithm from the SciKit-Learn library @scikit-learn. The goal of RFE is to eliminate non-essential features by recursively considering smaller and smaller subsets of the original features using a greedy algorithm. Initially, RFE takes the SVM we trained and ranks the coefficients by their magnitudes, with the lowest one pruned away; then the model is trained again with the remaining features. This process is repeated until the desired number of features is reached. For our purpose, we obtain the bare minimum witness by continuously removing features until the accuracy on the training set drops below 100%. Figure \[fig:RFE\] shows the noise tolerance $p$ before and after the RFE algorithm has been run on the $W-$state witness.

![ Barplot showing the normalized non-zero coefficients (exceeding 0.01) of the SVM-derived witnesses for the a) GHZ state and b) W state. Below each plot is the witness written out; the operator $Per\{\cdot\}$ denotes the sum of all possible permutations of the operators within the brackets. \[fig:W\_GHZ\] ](GHZ_W_States.png){width="8.5cm"}

![ Systematic removal of features from a witness using Recursive Feature Elimination (RFE). a) The $W$ state witness derived by the SVM initially has 8 coefficients, including the intercept term ($I\otimes I\otimes I$ - the $\otimes$ symbol has been neglected to save space). b) This witness has a noise tolerance of up to 0.47. Histogram showing the spectrum of expectation values for entangled states (green), fully-separable states (blue) and biseparable states (orange). c) In each iteration of the RFE algorithm we discard the least important feature (the feature whose coefficient has the smallest magnitude). We find that the minimum number of coefficients that the witness can have without misclassifying separable states is 5. d) However, this reduction decreases the noise tolerance $p\leq$ 0.26. \[fig:RFE\] ](RFE_Figure_EricMod.png){width="8.5cm"}

In contrast to @Sciara_PhysRevLett.122.120501, where features were removed from the witness to reduce experimental complexity, here we do not derive the initial witness from either the fidelity witness or stabilizer formalism. The witness is derived using the SVM method, constrained by only a very straightforward ansatz (Eqn \[eqn:W\_expect\]).

Bipartite Qudits
================

In the case of particles residing in higher dimensional ($d>2$) Hilbert spaces, the ansatz witness (Eqn \[eqn:W\_expect\]) would need to be constructed with generalized Pauli matrices. However, these matrices exist only for dimensions that are prime $P$ (or powers of prime $P^d$); the eigenvectors of the matrices correspond to mutually-unbiased bases (MUBs), while the eigenvalues are complex.

In general, there are $d+1$ MUBs \[cite\] when $d$ is prime. The set of corresponding Pauli matrices are: $$S = \{ X, Z,  XZ, XZ^2, \cdots, XZ^{d-1}\},$$ where $X$ is the row-shifted $d$-dimensional identity matrix: $$X = 
   \begin{pmatrix} 
    0 &         0 &         \cdots &        0 &         1  \\
    1 &         0 &         \cdots &        0 &         0  \\
    \vdots &    \vdots &    \ddots &        \vdots &    \vdots \\
    0 &         0 &         \cdots &        1 &         0  \\
   \end{pmatrix} 
   \label{eq:Xgenpauli}$$ and $Z$ is the diagonal matrix: $$Z = 
   \begin{pmatrix} 
    1 &         0 &                 \cdots &        0 &         0  \\
    0 &         \omega &        \cdots &        0 &         0  \\
   \vdots &     \vdots &            \ddots &        \vdots & \vdots \\
    0 &         0 &     \cdots &        \omega^{d-2} &  0 \\
    0 &         0 &         \cdots &        0 &         \omega^{d-1} \\
   \end{pmatrix},\  \omega \equiv e^{j\frac{2\pi}{d}}.
   \label{eq:Zgenpauli}$$

From Eq \[eq:Zgenpauli\], we see that the eigenvalues of these generalized Pauli matrices are complex. Limiting the dimensionality to $d=3$, the set of generalized Pauli matrices for each particle becomes: $$\sigma_1, \sigma_2 \in \{I,V,X,Y,Z,V^\dagger, X^\dagger, Y^\dagger, Z^\dagger\},
\nonumber$$ with $Y \equiv XZ$ and $V \equiv XZ^2$.

The ansatz for the witness given in Eqn \[eqn:W\_expect\] is modified so that it will give real expectation values @Sciara_PhysRevLett.122.120501; the modification involves hermitianizing each term in the summation: $$\hat{W} = \sum_{k_1, k_2}  a_{k_1, k_2} 
     \left(  \sigma_{k_1} \otimes \sigma_{k_2}  +  \sigma_{k_1}^\dagger \otimes \sigma_{k_2}^\dagger \right).
\nonumber$$

Once again, to generate the training data, the separable states are constructed in a Haar-distributed manner, and the entangled states are generated by adding white noise to the target pure state (Eqn. \[eq:werner\]). The results for three different states are shown in the form of a histogram in Fig \[fig:d=3\]; each state is trained with a maximum white noise content of $p = 0.125$. Even then, the derived witnesses can tolerate significantly more white noise than is present in the training data.

![ The SVM-derived coefficients of the witnesses for three target bipartite entangled states are shown. The features with coefficients whose magnitudes exceed than 0.01 are highlighted, and the tolerable white noise for each witness (state) is given on the right hand side. \[fig:d=3\] ](Fig_d=3_.png){width="8cm"}

We perform convergence testing to investigate how much training data is required for the SVM-derived witness to converge (Fig \[fig:converge\]). We vary the training data size from 6000 to 100,000. For each training data size, a witness for the target state $|\psi\rangle  = \frac{1}{\sqrt{3}}\left( |00\rangle + |11\rangle +|22\rangle \right)$ is trained five times, each with different randomly-generated data. The ratio of the standard deviation of each non-zero coefficient $S_{a_k}$ to its mean value coefficient $\langle a_k \rangle$ is plotted. What we observe from Fig. \[fig:converge\] is that the coefficients have negligible uncertainty (within 2$\%$) and converge to the asymptotic value when training data consisting of more than 100,000 states points are used.

For a bipartite separable state, with each particle occupying a $d>2$ Hilbert space ($d$ being prime or a prime power), a pure separable state is defined by $4(d-1)^2$ independent parameters; roughly (and naively) speaking, this means we need $\sim 10^{4(d-1)^2}$ amount of training data to find the witness for a $d$-dimensional bipartite entangled target state ($\sim 10^{16}$ data points for $d = 3$). Empirically (Fig. \[fig:converge\]), though, the actual size of the dataset to obtain a reasonably good witness seems to be much smaller ($\sim 10^{5}$). This gives us confidence that we can efficiently extend our SVM-based method to higher dimensions and more particles.

![ Convergence testing. How big must the training data be for us to be able to generate a witness whose coefficients converge to its asymptotic value? The target state $|\psi\rangle  = \frac{1}{\sqrt{3}}\left( |00\rangle + |11\rangle +|22\rangle \right)$ is used; its coefficients are shown graphically in Fig. \[fig:d=3\]. The metric for stability is the ratio of the standard deviation of each non-zero coefficient $S_{a_k}$ to its mean value coefficient $\langle a_k \rangle$. The training data size is varied from 6000 to 100,000. \[fig:converge\] ](Fig_converge.png){width="8.5cm"}

Due to the increasing training data size, we will need to implement *online* training of the SVM, which involves training the SVM in batches, with different data fed in at each batch. This is in contrast to *offline* data, where all the data is available to the SVM for training initially. To do this, we implement an SVM structure in Tensorflow @tensorflow2015-whitepaper, using a single input layer (the features), and single output with no hidden layer. The loss function (Eqn \[eqn:lossfunc\]) remains the same, but we instead use Adaptive Momentum (ADAM) @kingma2014adam as the optimizer. For even-higher dimensional data where training sets of $>10^8$ points are required, *online* training will be a necessity.

In summary, we have demonstrated using a linear support vector machine (SVM) to derive entanglement witnesses for both bipartite and tripartite qubit systems, as well as bipartite qutrit systems. This method generates witnesses that require only local measurements and whose tolerance to noise is on par or better than what is currently found in the literature. In addition to deriving witnesses for stabilizer states, our method also yields witnesses to non-stabilizer states. Furthermore, we demonstrate the ability to systematically reduce the number of features in the witness, allowing us to reduce experimental complexity at the expense of poorer noise tolerance. This SVM method is straightforward to extend to higher-dimensions $d$ for bipartite systems, involving online learning, and may also be computationally efficient for deriving the witnesses of systems consisting of larger particle numbers $N$, though further investigation is required.

Acknowledgments
===============

We thank Brian T Kirby for some fruitful discussions. This work was funded by NSERC (National Sciences and Engineering Research Council of Canada) and the US Army Research Laboratory.

<span>23</span>ifxundefined \[1\]<span> ifx<span>\#1</span> </span>ifnum \[1\]<span> \#1firstoftwo secondoftwo </span>ifx \[1\]<span> \#1firstoftwo secondoftwo </span>""\#1""@noop \[0\]<span>secondoftwo</span>sanitize@url \[0\]<span>'\
12'\$12 '&12'\#12'12'\_12'%12</span>@startlink\[1\]@endlink\[0\]@bib@innerbibempty @noop <span>****, ()</span> @noop <span>****,  ()</span> @noop <span>****,  ()</span> @noop <span>****,  ()</span> @noop <span>****,  ()</span> @noop <span>****,  ()</span> @noop <span>****,  ()</span> @noop <span>****,  ()</span> @noop <span>****, ()</span> @noop <span>****,  ()</span> @noop <span>****,  ()</span> [****,  ()](https://doi.org/10.1103/PhysRevA.64.052312) @noop <span>****,  ()</span> @noop <span>****,  ()</span> @noop <span>****,  ()</span> @noop <span>****,  ()</span> @noop <span>****,  ()</span> [****, ()](https://doi.org/10.1103/PhysRevLett.122.120501) @noop <span>****,  ()</span> @noop <span>****,  ()</span> @noop <span> ()</span> [](http://tensorflow.org/) (),  @noop <span> ()</span>

[^1]: For an N-particle d-dimensional space, we posit that $\hat{W}$ will have no more than $(d+1)^N$ features; we arrive at this expression because a particle of dimension $d$ will have at most $(d+1)$ mutually-unbiased bases, with each basis corresponding to its own generalized Pauli matrix $\sigma_k$.

[^2]: By 'optimal', we mean that the hyperplane is 'optimally' trained with respect to the training data and ansatz, not that the resulting witness is 'optimal'.

[^3]: Consider an arbitrary separable state $\rho_{sep} = \sum_i p_i |\psi_{sep,i}\rangle \langle \psi_{sep,i}|$, where $\psi_{sep,i}$ are fully-separable states. Then $tr(\rho_{sep}\hat{W}) = \sum_i p_i \langle \psi_{sep,i}|\hat{W}|\psi_{sep,i}\rangle\geq 0 $. This means that using pure fully-separable states as training examples is equivalent to training with mixed fully-separable states.

{'source': 'arXiv_out/2107'}