††thanks<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Detecting and quantifying entanglement on near-term quantum devices

Kun Wang  Zhixin Song  Xuanqiang Zhao  Zihe Wang  Xin Wang  Institute for
Quantum Computing, Baidu Research, Beijing 100193, China

###### Abstract

Quantum entanglement is a key resource in quantum technology, and its
quantification is a vital task in the current Noisy Intermediate-Scale Quantum
(NISQ) era. This paper combines hybrid quantum-classical computation and
quasi-probability decomposition to propose two variational quantum algorithms,
called Variational Entanglement Detection (VED) and Variational Logarithmic
Negativity Estimation (VLNE), for detecting and quantifying entanglement on
near-term quantum devices, respectively. VED makes use of the positive map
criterion and works as follows. Firstly, it decomposes a positive map into a
combination of quantum operations implementable on near-term quantum devices.
It then variationally estimates the minimal eigenvalue of the final state,
obtained by executing these implementable operations on the target state and
averaging the output states. Deterministic and probabilistic methods are
proposed to compute the average. At last, it asserts that the target state is
entangled if the optimized minimal eigenvalue is negative. VLNE builds upon a
linear decomposition of the transpose map into Pauli terms and the recently
proposed trace distance estimation algorithm. It variationally estimates the
well-known logarithmic negativity entanglement measure and could be applied to
quantify entanglement on near-term quantum devices. Experimental and numerical
results on the Bell state, isotropic states, and Breuer states show the
validity of the proposed entanglement detection and quantification methods.

##  I Introduction

It is widely believed that we are now in the Noisy Intermediate Scale Quantum
(NISQ) era Preskill (2018), where quantum computers with $50$-$100$ qubits are
available while noise in quantum gates severely limits the quantum circuits
that can be executed reliably. It thus becomes important to make the best use
of today’s NISQ devices to design practical applications. One promising scheme
for near-term quantum applications is the variational quantum algorithms (VQA)
McClean  _et al._ (2016), which have been applied to solve many tasks
including Hamiltonian ground and excited states preparation Peruzzo  _et al._
(2014); Nakanishi  _et al._ (2019), quantum state distance estimation Cerezo
_et al._ (2020a); Chen  _et al._ (2020), quantum metrology Beckey  _et al._
(2020); Koczor  _et al._ (2019), and quantum data compression Romero  _et al._
(2017); Wan  _et al._ (2017); Cao and Wang (2020). These variational quantum
algorithms involve evaluating and optimizing loss functions that depend on
parameters in parameterized quantum circuits (PQC). They are regarded as well-
suited for execution on NISQ devices by combining quantum computers with
classical computers. We refer the readers to Endo  _et al._ (2020); Cerezo
_et al._ (2020b) for a detailed review on VQA.

Quantum entanglement Horodecki  _et al._ (2009), the most nonclassical
manifestation of quantum mechanics, has been identified as invaluable resource
enabling a tremendous number of tasks ranging from quantum information
processing Bennett and Wiesner (1992); Bennett  _et al._ (1993), quantum
cryptography Bell (1964); Clauser  _et al._ (1970); Ekert (1991), quantum
algorithms Shor (1994); Jozsa (1997); Childs and Van Dam (2010), quantum
communication Bennett  _et al._ (1999, 2002), to measurement-based quantum
computing Raussendorf and Briegel (2001); Raussendorf  _et al._ (2003); Gross
and Eisert (2007); Briegel  _et al._ (2009). As so, the ability to manipulate
quantum entanglement is the cornerstone to achieve real applications of
quantum technologies. A number of theoretical and experimental methods have
been proposed in the past $20$ years for entanglement detection and
quantification Horodecki  _et al._ (2009); Gühne and Tóth (2009); Friis  _et
al._ (2019). For example, entanglement can be detected via entanglement
witnesses Horodecki  _et al._ (1996); Gühne and Lütkenhaus (2006), Bell’s
inequalities Bell and Bell (2004), quantum Fisher information Pezzé and Smerzi
(2009), realignment criterion Chen and Wu (2002); Rudolph (2005), range
criterion Horodecki (1997), and majorization criterion Nielsen and Kempe
(2001), to name a few. These methods commonly assume that prior information
about the target state is known. A direct way to obtain such information is to
perform quantum state tomography and reconstruct the density matrix D’Ariano
_et al._ (2003); Steffen  _et al._ (2006). However, tomography becomes
unrealistic as the number of required measurement settings scales
exponentially with the size of the system. Briefly speaking, though there are
many methods proposed for detecting and quantifying quantum entanglement, they
are not specially designed for near-term quantum devices and thus are not
directly applicable in most cases, rendering reliable detection and
quantification of quantum entanglement on near-term quantum devices a vital
challenge.

In this paper, we combine VQA and the quasi-probability decomposition
technique Buscemi  _et al._ (2013, 2014); Pashayan  _et al._ (2015); Temme
_et al._ (2017); Endo  _et al._ (2018); Takagi (2020); Jiang  _et al._ (2020)
to propose the Variational Entanglement Detection (VED) and Variational
Logarithmic Negativity Estimation (VLNE) algorithms, aiming to detect and
quantify quantum entanglement on near-term quantum devices, respectively. VED
uses criteria based on positive maps as a bridge and works as follows. Given
an unknown target bipartite quantum state, it firstly decomposes the chosen
positive map into a linear combination of NISQ implementable quantum
operations. Then, it variationally estimates the minimal eigenvalue of the
final state, which is obtained by executing these quantum operations on the
target state and averaging the output states. Two methods are proposed to
compute the average: the first one averages the output states according to the
quasi-probability distribution, and the second one estimates the average via
the sampling technique and is probabilistic. At last, it asserts that the
target state is entangled if the optimized minimal eigenvalue is negative.
Following the idea of VED, VLNE variationally computes the well-known log-
negativity entanglement measure, building on a linear decomposition of the
transpose map into Pauli terms and the recently proposed trace distance
estimation algorithm. Our main contributions can be summarized as follows:

  1. 1.

We combine VQA and the quasi-probability decomposition technique to propose
the VED framework, contributing a feasible solution for detecting entanglement
on near-term quantum devices.

  2. 2.

We combine VQA and the quasi-probability decomposition technique to propose
the VLNE algorithm that could estimate the well-known logarithmic negativity
Plenio (2005a), which may lead to various applications in near-term quantum
information processing.

Experimental and numerical results reveal the validity of the proposed
entanglement detection and quantification methods.

Our paper is structured as follows. In Sec. II, we set the notations and
briefly summarize the entanglement criteria based on positive maps. In Sec.
III, we present our first main result: the VED framework. In Sec. IV, we
elaborate on three prominent positive maps to illustrate how the VED framework
is applied. In Sec. V, we present our second main result: the VLNE framework,
which estimates the logarithmic negativity entanglement measure. In Secs. VI
and VII, experiments on IBM-Q and numerical simulations on Paddle Quantum are
conducted on various bipartite quantum states of interests to show the
validity of the proposed methods. We finally conclude in Sec. VIII.

##  II Preliminaries

###  II.1 Notations

In this section, we set the notation and define several quantities that will
be used throughout this paper. We will frequently use symbols such as
$\mathcal{H}_{A}$ and $\mathcal{H}_{B}$ to denote Hilbert spaces associated
with quantum systems $A$ and $B$, respectively. We use $d_{A}$ to denote the
dimension of the system $A$. The set of linear operators acting on $A$ is
denoted by ${\cal L}(\mathcal{H}_{A})$. We write an operator with subscript to
indicate the system that the operator acts on, e.g., $X_{AB}$, and write
$X_{A}\mathrel{\mathop{\mathchar 58\relax}}=\operatorname{Tr}_{B}X_{AB}$. For
a linear operator $X\in{\cal L}(\mathcal{H}_{A})$, we define its modulus
$|X|\mathrel{\mathop{\mathchar 58\relax}}=\sqrt{X^{\dagger}X}$, where
$X^{\dagger}$ is the adjoint operator of $X$. The trace norm of $X$ is defined
as $\|X\|_{1}\mathrel{\mathop{\mathchar 58\relax}}=\operatorname{Tr}|X|$. We
use $X\geq 0$ to indicate that $A$ is positive semidefinite. A quantum map
${\cal N}$ that transforms linear operators to linear operators in the system
$A$ is abbreviated as ${\cal N}_{A\to A}$. We use the calligraphic letters
(e.g., ${\cal N}$, ${\cal R}$, and ${\cal O}$) to represent linear quantum
maps and use ${\operatorname{id}}_{A}$ to represent the identity map on system
$A$. We say ${\cal N}_{A\to A}$ is trace-preserving if
$\operatorname{Tr}[{\cal N}(X)]=\operatorname{Tr}[X]$ for arbitrary $X\in{\cal
L}({\cal H}_{A})$, is positive if ${\cal N}(X)\geq 0$ for arbitrary $X\geq 0$,
and is completely positive if ${\operatorname{id}}_{R}\otimes{\cal N}$ is
positive for arbitrary reference system $R$.

Given a Hermitian operator $X$ in system $A$, we denote by $\lambda_{\min}(X)$
its minimal eigenvalue. We have the following variational characterization:

$\displaystyle\lambda_{\min}(X)=\min_{|\psi\rangle}\langle\psi|X|\psi\rangle,$
(1)

where the minimization ranges over the set of pure states on system $A$.

We use $\mathbb{R}$ to represent the real field. We introduce the sign
function $\operatorname{sgn}\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}\to\\{\pm 1,0\\}$ as $\forall x<0$,
$\operatorname{sgn}(x)=-1$; $\forall x>0$, $\operatorname{sgn}(x)=1$; and
$\operatorname{sgn}(0)=0$. All logarithms are in base $2$ in this paper.

###  II.2 Pauli operators and Pauli channels

The four Pauli operators in the qubit space are defined as

$\displaystyle I\equiv\sigma_{0}$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix},$ $\displaystyle
X\equiv\sigma_{1}$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix},$ (2a) $\displaystyle
Y\equiv\sigma_{2}$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\begin{pmatrix}0&-i\\\ i&0\end{pmatrix},$ $\displaystyle
Z\equiv\sigma_{3}$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}.$ (2b)

They provide a basis for the qubit linear operators, i.e., arbitrary qubit
linear operator can be decomposed w.r.t. this basis. For the $n$-qubit case,
one can construct a set of Pauli operators, which we call the Pauli set, as

$\displaystyle\bm{P}_{n}\mathrel{\mathop{\mathchar
58\relax}}=\left\\{\bigotimes_{k=1}^{n}\sigma_{q_{k}}\;\middle|\;q_{k}=0,1,2,3\right\\}\equiv\left\\{I,X,Y,Z\right\\}^{\otimes
n}.$ (3)

The $n$-qubit Pauli set has size $|\bm{P}_{n}|=4^{n}$. Note that $\bm{P}_{n}$
forms a basis for the $n$-qubit linear operators. One can see from (3) that
each Pauli operator $P\in\bm{P}_{n}$ can be represented uniquely by a
_quaternary_ sequence:

$\displaystyle\bm{q}=q_{1}\cdots q_{n},\quad\text{with}\quad q_{k}=0,1,2,3.$
(4)

As so, we use $P_{\bm{q}}$ to represent the $n$-qubit Pauli operator that is
uniquely determined by the sequence $\bm{q}$. Since each qubit Pauli operator
is unitary, so is each $n$-qubit Pauli operator, due to the construction.
Given a Pauli operator $P\in\bm{P}_{n}$, we denote by ${\cal
P}(\cdot)\mathrel{\mathop{\mathchar 58\relax}}=P(\cdot)P^{\dagger}$ its
induced Pauli channel.

###  II.3 Entanglement detection via positive maps

Let $\rho_{AB}$ be a bipartite quantum state in the composite system $AB$. By
definition $\rho_{AB}$ is _separable_ if it can be decomposed into a convex
combination of tensor products of states describing local systems as Werner
(1989)

$\displaystyle\rho_{AB}=\sum_{x}p_{x}|\psi_{x}\rangle\\!\langle\psi_{x}|_{A}\otimes|\phi_{x}\rangle\\!\langle\phi_{x}|_{B},$
(5)

where $p_{x}\geq 0$, $\sum_{x}p_{x}=1$, and $\\{|\psi_{x}\rangle\\}_{x}$ and
$\\{|\phi_{x}\rangle\\}_{x}$ are two sets of pure states in systems $A$ and
$B$, respectively. Otherwise, $\rho_{AB}$ is _entangled_. Given the
definition, it is natural to ask whether a given unknown bipartite quantum
state is separable or entangled, known as the _separability problem_. This
problem has been shown to be NP-hard Gurvits (2003); Gharibian (2008). There
are many separability criteria that have been proposed to determine the
separability or entanglement of bipartite quantum states as necessary
conditions Gühne and Tóth (2009); Horodecki  _et al._ (2009).

One of the most celebrated criteria for distinguishing separable states from
entangled states are the positive map criterion. The core of the positive map
criterion is that one subjects a subsystem of $\rho_{AB}$ to a positive (but
not completely positive) map ${\cal N}_{B\to B}$ that preserves the positivity
of inputs. If $\rho_{AB}$ is a product state, i.e., it is of the form
$\rho_{A}\otimes\rho_{B}$, the resulting operator $\rho_{A}\otimes{\cal
N}(\rho_{B})$ is still positive. Consequently, due to the linearity, an
arbitrary separable state is mapped into some positive operator by this map.
On the other hand, if $\rho_{AB}$ is entangled, the output operator ${\cal
N}_{B\to B}(\rho_{AB})$ may be no longer positive; the transpose map is a
prominent example Peres (1996). That is to say, the negative spectrum of the
output operator indicates entanglement of the input state. Mathematically, the
positive map criterion states that a bipartite quantum state $\rho_{AB}$ is
separable if and only if for arbitrary system $C$ and arbitrary positive (but
not completely positive) map ${\cal N}_{B\to C}$, it holds that ${\cal
N}_{B\to C}(\rho_{AB})\geq 0$ Horodecki  _et al._ (1996).

Despite its proven efficiency in entanglement detection, the positive map
criterion is not directly applicable in practice, especially on recent NISQ
devices. This is an immediate consequence of the fact that generically
positive but not completely positive maps do not represent physically
implementable quantum operations Kraus (1983) and thus cannot be realized in
near-term quantum devices. In the following, we show how to overcome this
obstacle and employ the positive map criterion to detect entanglement on NISQ
devices.

##  III Quantum entanglement detection

In this section, we integrate variational quantum algorithms with the quasi-
probability decomposition technique Buscemi  _et al._ (2013, 2014); Pashayan
_et al._ (2015); Temme  _et al._ (2017); Endo  _et al._ (2018); Takagi (2020);
Jiang  _et al._ (2020) to propose a bipartite entanglement detection framework
specially designed for near-term quantum devices, using positive map criterion
as a bridge. For simplicity, we assume $A$ and $B$ are two $n$-qubit quantum
systems throughout this section. However, we remark that the proposed
framework can applied to bipartite systems with different dimensions directly.

Let $\Delta$ be a discrete set of quantum operations that are implementable in
the near-term quantum devices. For example, one may choose $\Delta$ to be the
set of implementable operations introduced in Endo  _et al._ (2018); Takagi
(2020). Alternatively, one may set $\Delta$ to be the set of Pauli channels
induced by Pauli operators from the Pauli set (3). For a positive (but not
completely positive) and trace-preserving map ${\cal N}_{B\to B}$, we assume
that it can be decomposed w.r.t. $\Delta$ as

$\displaystyle{\cal N}(\cdot)=\sum_{{\cal O}\in\Delta}r_{{\cal O}}{\cal
O}(\cdot),\;r_{{\cal O}}\in\mathbb{R}.$ (6)

Note that such a decomposition always exists if $\Delta$ contains a universal
basis Endo  _et al._ (2018). The trace-preserving condition imposes
$\sum_{{\cal O}}r_{{\cal O}}=1$. We emphasize that there must exist negative
coefficients $r_{{\cal O}}$ since otherwise, ${\cal N}$ is completely
positive. Given a bipartite quantum state $\rho_{AB}$, we have

$\displaystyle\sigma_{AB}\mathrel{\mathop{\mathchar 58\relax}}={\cal N}_{B\to
B}(\rho_{AB})=\sum_{{\cal O}\in\Delta}r_{{\cal O}}{\cal O}_{B\to
B}(\rho_{AB}).$ (7)

To see if $\rho_{AB}$ can be detected by ${\cal N}$, i.e., if $\rho_{AB}$ is
entangled from ${\cal N}$’s perspective, we need to check if the output state
$\sigma_{AB}$ has a negative eigenvalue or not. Denote by
$\lambda_{\min}(\sigma_{AB})$ as the smallest eigenvalue of $\sigma_{AB}$. By
the positive map criterion, if $\rho_{AB}$ is separable, then it must hold
that $\lambda_{\min}(\sigma_{AB})\geq 0$. Equivalently, if
$\lambda_{\min}(\sigma_{AB})<0$, we safely conclude that $\rho_{AB}$ is
entangled and it can be detected by the positive map ${\cal N}_{B\to B}$. This
highlights the importance of computing or estimating
$\lambda_{\min}(\sigma_{AB})$ in entanglement detection.

###  III.1 Deterministic detection

As we have argued, $\sigma_{AB}$ cannot be obtained directly via ${\cal
N}(\rho)$ since ${\cal N}$ does not represent physically implementable quantum
operations. Fortunately, the decomposition (7) empowers us an effective way to
simulate the role of ${\cal N}$ and reconstruct $\sigma_{AB}$ as an average of
a set of output states, obtained using quantum circuits implementable in near-
term devices. This decomposition technique, combined with the variational
quantum algorithm, enables a general framework that estimates
$\lambda_{\min}(\sigma_{AB})$, whose value can witness the entanglement of the
input state $\rho_{AB}$. We call this framework the _Variational Entanglement
Detection (VED)_. The core idea is to use the linear decomposition (7) of the
target state $\sigma_{AB}$ and the framework goes as follows. First of all, by
(1) it holds that

$\displaystyle\lambda_{\min}(\sigma_{AB})$
$\displaystyle=\min_{|\psi\rangle_{AB}}\langle\psi|\sigma_{AB}|\psi\rangle$
(8) $\displaystyle=\min_{|\psi\rangle_{AB}}\sum_{{\cal O}\in\Delta}r_{\cal
O}\langle\psi|{\cal O}(\rho_{AB})|\psi\rangle,$ (9)

where the minimization ranges over all pure bipartite quantum states
$|\psi\rangle_{AB}$ in $AB$. We use a variational quantum circuit with
parameters $\bm{\alpha}$ to prepare the test state $|\psi\rangle$. More
precisely, we choose a parametrized quantum circuit ansatz that generates a
unitary $U(\bm{\alpha})$ and prepare the test state via
$|\psi\rangle=U(\bm{\alpha})|0\rangle^{\otimes 2n}$. Each inner product
$\langle\psi|{\cal O}(\rho)|\psi\rangle$ in (9) can be estimated via the
canonical Swap Test subroutine Buhrman  _et al._ (2001), as both
$U(\bm{\alpha})$ and ${\cal O}$ can be implemented in near-term devices.
However, this subroutine costs a total number of $4n+1$ qubits and requires a
$4n$-qubit SWAP gate, which is resource consuming when $n$ becomes large. Here
we explore the special structure of the overlap $\langle\psi|{\cal
O}(\rho)|\psi\rangle$ and propose an qubit efficient estimating procedure
which uses $2n$ qubits and avoids the use of expensive SWAP gate. First of
all, notice that

$\displaystyle\;\langle\psi(\bm{\alpha})|{\cal
O}(\rho_{AB})|\psi(\bm{\alpha})\rangle$ (10) $\displaystyle=$
$\displaystyle\;\operatorname{Tr}\left[{\cal
O}(\rho_{AB})U_{\bm{\alpha}}|0^{2n}\rangle\langle
0^{2n}|U_{\bm{\alpha}}^{\dagger}\right]$ (11) $\displaystyle=$
$\displaystyle\;\langle 0^{2n}|U_{\bm{\alpha}}^{\dagger}{\cal
O}(\rho_{AB})U_{\bm{\alpha}}|0^{2n}\rangle,$ (12)

where the second equality follows from the cyclic property of trace function.
Since each ${\cal O}$ is implementable on near-term quantum devices, we may
use $\rho_{AB}$ as input to the quantum circuit implementing ${\cal O}$, and
estimate the overlap $\langle\psi|{\cal O}(\rho_{AB})|\psi\rangle$ using the
quantum circuit illustrated in Fig. 1. The overlap is obtained by counting the
relative frequency of the measurement outcome $0^{2n}$. Then, we repeat the
estimation procedure $|\Delta|$ times, where $|\Delta|$ is the size of
$\Delta$, to obtain the overlaps for different ${\cal O}$ in (9). With these
data in hand, we compute the following loss function

$\displaystyle L(\bm{\alpha})\mathrel{\mathop{\mathchar 58\relax}}=\sum_{{\cal
O}\in\Delta}r_{\cal O}\langle\psi(\bm{\alpha})|{\cal
O}(\rho_{AB})|\psi(\bm{\alpha})\rangle.$ (13)

At last, we perform gradient-based optimization methods including SGD Kiefer
_et al._ (1952) and Adam Kingma and Ba (2014) to minimize the loss function
$L(\bm{\alpha})$ by varying the parameters $\bm{\alpha}$, whose value will
determine the separability of the input state $\rho_{AB}$. More precisely, if
$L(\bm{\alpha})$ is negative, we conclude that $\rho_{AB}$ is entangled, since
by the positive map criterion, separable states cannot yield a negative
spectrum.

Taking into account the noise in NISQ quantum devices, we may introduce a
tolerance threshold $\delta>0$ so that $L(\bm{\alpha})<-\delta$ implies the
input state is entangled. This threshold $\delta$ can be set with prior
knowledge about the noise characterization on the NISQ devices. What’s more,
for the purpose of entanglement detection, it is unnecessary to minimize
$L(\bm{\alpha})$ since the condition $L(\bm{\alpha})<0$ is sufficient to
assert that the input state is entangled. Based on this observation, we can
terminate the optimization procedure that minimizes the loss function
$L(\alpha)$ in advance to save the optimization cost. The detailed VED
framework is summarized in Algorithm 1. We name it the deterministic VED to
distinguish it from the probabilistic framework described in the next section.

Figure 1: The simplified quantum circuit that estimates the overlap
$\langle\psi|{\cal O}(\rho_{AB})|\psi\rangle$ in (12) for a given
implementable operation ${\cal O}$, where
$|\psi\rangle\mathrel{\mathop{\mathchar
58\relax}}=U_{\bm{\alpha}}|0\rangle^{\otimes 2n}$ is the parameterized input
state. Algorithm 1 Deterministic VED

1: Input: $2n$-qubit quantum state $\rho_{AB}$, decomposition (6) of the
positive map ${\cal N}$, parameterized quantum circuits $U(\bm{\alpha})$ with
initial parameters $\bm{\alpha}$, and tolerance $\delta$;

2: Initialize $L(\bm{\alpha})=0$;

3: for all ${\cal O}\in\Delta$ such that $r_{{\cal O}}\neq 0$ do

4: Apply $U_{\bm{\alpha}}$ to $|0\rangle^{\otimes 2n}$ and obtain test state
$|\psi\rangle=U_{\bm{\alpha}}|0\rangle^{\otimes 2n}$;

5: Input $\rho_{AB}$ and compute the overlap $c_{\cal
O}\mathrel{\mathop{\mathchar 58\relax}}=\langle\psi|{\cal
O}(\rho_{AB})|\psi\rangle$ using the quantum circuit in Fig. 1;

6: Update the loss function $L(\bm{\alpha})=L(\bm{\alpha})+r_{\cal O}c_{\cal
O}$, where $r_{\cal O}$ is given by the decomposition (6);

7: end for

8: Perform optimization methods to minimize $L(\bm{\alpha})$; terminate the
optimization if the error tolerance is satisfied: $L(\bm{\alpha})<-\delta$;

9: Output ”Entangled” if the optimized $L(\bm{\alpha})<-\delta$.

###  III.2 Probabilistic detection

In Algorithm 1, we have used a brute-force approach, where we iterate over the
set of implementable operations $\Delta$, to estimate the loss function
$L(\bm{\alpha})$. Actually, $L(\bm{\alpha})$ can be estimated in a
probabilistic way using the sampling technique, by virtue of the quasi-
probability decomposition (6). This new method would be beneficial when the
number of decomposed operations in (6) with non-zero coefficients is large
while the sampling cost is relatively low. Now we describe the sampling method
accurately. First of all, notice that the decomposition (6) induces a quasi-
probability distribution $\\{r_{{\cal O}}\\}_{{\cal O}\in\Delta}$ over
$\Delta$. From this quasi-probability distribution, we can construct a
probability distribution $\\{p_{{\cal O}}\\}_{{\cal O}\in\Delta}$ using the
canonical technique, i.e.,

$\displaystyle p_{{\cal O}}\mathrel{\mathop{\mathchar
58\relax}}=\frac{|r_{\cal O}|}{\gamma},\quad\gamma\mathrel{\mathop{\mathchar
58\relax}}=\sum_{{\cal O}\in\Delta}|r_{{\cal O}}|.$ (14)

Substituting (14) into (13) yields

$\displaystyle L(\bm{\alpha})$ $\displaystyle=\gamma\sum_{{\cal
O}\in\Delta}\operatorname{sgn}(r_{\cal O})p_{{\cal
O}}\langle\psi(\bm{\alpha})|{\cal O}(\rho_{AB})|\psi(\bm{\alpha})\rangle$ (15)
$\displaystyle=\mathbb{E}_{{\cal O}}\left[\gamma\operatorname{sgn}(r_{\cal
O})\langle\psi(\bm{\alpha})|{\cal
O}(\rho_{AB})|\psi(\bm{\alpha})\rangle\right],$ (16)

where $\mathbb{E}(X)$ denotes the expectation of the random variable $X$, and
the expectation in (16) is evaluated w.r.t. the probability distribution
$\\{p_{{\cal O}}\\}_{{\cal O}\in\Delta}$. Based on (16), we propose Algorithm
2, which can be viewed as a probabilistic version of Algorithm 1. In
particular, Algorithm 2 replaces the brute-force approach (steps 3-7) in
Algorithm 1 with the sampling approach, yielding a probabilistic algorithm.

Algorithm 2 Probabilistic VED

1: Input: $2n$-qubit quantum state $\rho_{AB}$, decomposition (6) of the
positive map ${\cal N}$, parameterized quantum circuits $U(\bm{\alpha})$ with
initial parameters $\bm{\alpha}$, error tolerance $\delta$, and fail
probability $\varepsilon$.

2: Initialize $L^{\prime}(\bm{\alpha})=0$;

3: Compute $\gamma$ defined in (14) and set
$M=2\gamma^{2}\log(2/\varepsilon)/\delta^{2}$;

4: for all $m=1,\cdots,M$ do

5: Apply $U_{\bm{\alpha}}$ to $|0\rangle^{\otimes 2n}$ and obtain test state
$|\psi\rangle=U_{\bm{\alpha}}|0\rangle^{\otimes 2n}$;

6: Sample a quantum operation ${\cal O}^{(m)}$ from $\Delta$ according to the
probability distribution $\\{p_{{\cal O}}\\}_{{\cal O}\in\Delta}$ in (14); Let
$r^{(m)}$ be the coefficient of ${\cal O}^{(m)}$ in (6);

7: Input $\rho_{AB}$ and compute the overlap
$c^{(m)}\mathrel{\mathop{\mathchar 58\relax}}=\langle\psi|{\cal
O}^{(m)}(\rho)|\psi\rangle$ using the quantum circuit in Fig. 1;

8: Compute $L^{(m)}=\gamma\operatorname{sgn}(r^{(m)})c^{(m)}$;

9: end for

10: Compute the loss function
$L^{\prime}(\bm{\alpha})=\frac{1}{M}\sum_{m=1}^{M}L^{(m)}$;

11: Perform optimization methods to minimize $L^{\prime}(\bm{\alpha})$;
terminate the optimization if the error tolerance is satisfied:
$L^{\prime}(\bm{\alpha})<-\delta$;

12: Output ”Entangled” if the optimized $L^{\prime}(\bm{\alpha})<-\delta$.

Let’s analyze Algorithm 2 in depth. First, we remark that the obtained
$L^{\prime}(\bm{\alpha})$ in step 11 of Algorithm 2 is an unbiased estimator
of true value $L(\bm{\alpha})$ due to (16). Second, since
$|L^{(m)}|\leq\gamma$, we can apply the Hoeffding inequality Hoeffding (1994)
to ensure that $M=2\gamma^{2}\log(2/\varepsilon)/\delta^{2}$ number of samples
would estimate the true value $L(\bm{\alpha})$ within error $\delta$ with
success probability no less than $1-\varepsilon$, i.e.,

$\displaystyle
p\left(|L^{\prime}(\bm{\alpha})-L(\bm{\alpha})|\leq\delta\right)\geq
1-\varepsilon.$ (17)

This confirms the validity of the sampling procedure (steps 4-9) of Algorithm
2. We call $\gamma$ the _sampling cost_ since it determines $M$, the number of
samples required to achieve the desired precision. At last, we examine the
success probability of the algorithm, given the success probability condition
(17) of the sampling procedure. Assume the optimization procedure repeats $K$
times. The overall success probability of Algorithm 2 is no less than
$1-K\varepsilon$, as a direct corollary of (17) and the union bound. That is
to say, if Algorithm 2 outputs ”Entangled”, $\rho_{AB}$ is entangled with
probability larger than $1-K\varepsilon$.

To summarize, we have proposed two variational entanglement detection methods.
Algorithm 1 is _deterministic_ in the sense that whenever it outputs
”Entangled”, one can safely assert that $\rho_{AB}$ is entangled. On the other
hand, Algorithm 2 is _probabilistic_ in the sense that even if it outputs
”Entangled”, one can only declare that $\rho_{AB}$ is entangled with certain
success probability. Nevertheless, when the number of decomposed operations in
(6) with non-zero coefficients is large while the simulation cost $\gamma$ is
relatively low, the latter method may be beneficial. In this case, one can
reduce the number of iterations via sampling and thus save computational
resources. Algorithm 2 scarifies precision for efficiency in entanglement
detection.

##  IV Prominent positive maps

In Sec. III we have outlined the general deterministic and probabilistic VED
frameworks for detecting entanglement via positive map criterion. In this
section, we elaborate on three prominent positive maps—the transpose map Peres
(1996), the reduction map Cerf  _et al._ (1999), and the enhanced reduction
map Breuer (2006); Hall (2006)—to illustrate how the deterministic VED
framework works. We choose the set of NISQ implementable quantum operations
$\Delta$ to be the set of Pauli channels induced by Pauli operators from the
Pauli set (3), i.e.,

$\displaystyle\Delta\mathrel{\mathop{\mathchar 58\relax}}=\left\\{{\cal
P}\;\middle|\;{\cal P}(\cdot)=P(\cdot)P^{\dagger},P\in\bm{P}_{n}\right\\}.$
(18)

For each of the three positive maps under consideration, we firstly decompose
it w.r.t. $\Delta$ as (6) and then adopt the variational framework summarized
in Algorithm 1 to fulfill entanglement detection. However, we remind that not
all positive maps can be decomposed w.r.t. the set of Pauli channels.

Here are remarks for the three criteria under consideration. First, the
reduction criterion is strictly weaker than both the transpose criterion and
the enhanced reduction criterion, in the sense that the states that can be
detected by the first criterion can also be detected by the latter two
criteria. Second, there is no inclusion relation between the PPT criterion and
the enhanced reduction criterion. That is, there are states that can be
detected by one but not by the other. As so, given an unknown state, one may
execute VED twice, one adopts the PPT criterion, and the other adopts the
enhanced reduction criterion. The state is necessarily entangled if at least
one of these two VEDs output ”Entangled.” We also show by example how VED
works in qutrit systems in Appendix A, utilizing the Choi map Choi (1975,
1980).

###  IV.1 PPT criterion

A necessary condition for entanglement detection is the positive partial
transpose (PPT) criterion Peres (1996), which we briefly review as follows.
Let $\rho_{AB}$ be a bipartite quantum state. We can express it as

$\displaystyle\rho_{AB}=\sum_{ijkl}\alpha_{ijkl}|i\rangle\\!\langle
j|_{A}\otimes|k\rangle\\!\langle l|_{B},$ (19)

where $\\{|i\rangle\\}_{i}$ and $\\{|k\rangle\\}_{k}$ are the computational
bases of $A$ and $B$, respectively. Its partial transpose with respect to
system $B$ is defined as

$\displaystyle\rho^{T_{B}}_{AB}\mathrel{\mathop{\mathchar 58\relax}}=$
$\displaystyle\;({\operatorname{id}}_{A}\otimes T_{B})(\rho_{AB})$ (20)
$\displaystyle=$ $\displaystyle\;\sum_{ijkl}\alpha_{ijkl}|i\rangle\\!\langle
j|\otimes(|k\rangle\\!\langle l|)^{T}$ (21) $\displaystyle=$
$\displaystyle\;\sum_{ijkl}\alpha_{ijkl}|i\rangle\\!\langle
j|\otimes|l\rangle\\!\langle k|,$ (22)

where $T_{B}$ denotes the transpose map on system $B$. The PPT criterion says
that if $\rho_{AB}$ is separable, then $\rho^{T_{B}}_{AB}\geq 0$. Conversely,
the negative spectrum witnesses entanglement of $\rho_{AB}$. What’s more, the
PPT criterion is not only necessary but also sufficient for separability of
the $2\otimes 2$ and $2\otimes 3$ cases Stormer (1963); Woronowicz (1976);
Horodecki  _et al._ (1996).

We begin with the two-qubit bipartite quantum state case. Notice that the
qubit transpose map admits the following decomposition w.r.t. $\Delta$
specialized in (18):

$\displaystyle T(\rho)=\frac{\rho+X\rho X-Y\rho Y+Z\rho Z}{2},$ (23)

where $X,Y,Z$ are the Pauli matrices defined in (2). The validity of this
decomposition can be checked by direct calculation. Substituting (23) into
(22), we obtain

$\displaystyle\rho^{T_{B}}_{AB}\mathrel{\mathop{\mathchar 58\relax}}=$
$\displaystyle\;({\operatorname{id}}_{A}\otimes T_{B})(\rho_{AB})$ (24)
$\displaystyle=$ $\displaystyle\;\frac{1}{2}(\rho+X_{B}\rho X_{B}-Y_{B}\rho
Y_{B}+Z_{B}\rho Z_{B}),$ (25)

where the quantum operation $X_{B}\rho_{AB}X_{B}$ should be understood as
$(I_{A}\otimes X_{B})\rho_{AB}(I_{A}\otimes X_{B})$, and similarly for $Y\rho
Y$ and $Z\rho Z$. Adapting the decomposition (25) into Algorithm 1, we
successfully apply the proposed VED to accomplish the PPT criterion in the
qubit case.

Now we show the above detection method can be generalized to the multi-qubit
bipartite quantum state case. Let $\bm{B}\equiv B_{1}B_{2}\cdots B_{n}$ be a
composite system with $n$ qubits, i.e., $B_{i}$ represents the $i$-th qubit
system. A key observation is that the transpose operation satisfies the tensor
product property: transposing the composite system $\bm{B}$ is equivalent to
transposing the local qubit systems $B_{i}$ individually. More precisely,

$\displaystyle T_{\bm{B}}=\bigotimes_{i=1}^{n}T_{B_{i}},$ (26)

where $T_{B_{i}}$ is the transpose operation on the $i$-th qubit. Eqs. (26)
and (23) together give $T_{\bm{B}}$ a linear combination into Pauli channels
of $4^{n}$ terms in total. Using this decomposition, we may apply VED
(Algorithm 1 or Algorithm 2) to accomplish the multi-qubit PPT criterion
deterministically or probabilistically.

###  IV.2 Reduction criterion

In this section, we first review the reduction criterion Cerf  _et al._ (1999)
and then propose a variational algorithm implementing this criterion within
the VED framework described in III.

$\displaystyle{\cal R}_{B\to B}(X_{B})\mathrel{\mathop{\mathchar
58\relax}}=\operatorname{Tr}[X_{B}]I_{B}-X_{B},$ (27)

which is known as the _reduction map_. The reduction criterion says that if a
bipartite quantum state $\rho_{AB}$ is separable, then it must hold that

$\displaystyle\sigma_{AB}\mathrel{\mathop{\mathchar
58\relax}}=\left({\operatorname{id}}_{A}\otimes{\cal R}_{B\to
B}\right)(\rho_{AB})\geq 0.$ (28)

Equivalently, if $\sigma_{AB}$ has negative eigenvalues, then $\rho_{AB}$ is
entangled. It is based on this observation that our variational algorithm
works.

To apply the framework in III, we have first to decompose ${\cal R}_{B\to B}$
into a linear combination of Pauli channels. Indeed, we can do so since

$\displaystyle{\cal R}_{B\to B}(\rho_{B})\mathrel{\mathop{\mathchar
58\relax}}=$ $\displaystyle\;\operatorname{Tr}[\rho_{B}]I_{B}-\rho_{B}$ (29)
$\displaystyle=$
$\displaystyle\;\frac{1}{2^{n}}\sum_{\bm{q}\in\\{0,1,2,3\\}^{\otimes n}}{\cal
P}_{\bm{q}}(\rho_{B})I_{B}-\rho_{B}$ (30) $\displaystyle=$
$\displaystyle\;\frac{1-2^{n}}{2^{n}}\rho_{B}+\frac{1}{2^{n}}\sum_{\bm{q}\neq\bm{0}}{\cal
P}_{\bm{q}}(\rho_{B}),$ (31)

where $\bm{0}\equiv(0,\cdots,0)$ of size $n$, and the second equality follows
from the twirling property of Pauli channels (Wilde, 2016, Exercise 4.7.3).
Using this decomposition, we can call Algorithm 1 or Algorithm 2 to accomplish
the reduction criterion.

Specially, in the qubit case where $n=1$, the reduction map is of the form

$\displaystyle{\cal R}_{B\to B}(\rho)=\frac{-\rho+X\rho X+Y\rho Y+Z\rho
Z}{2}.$ (32)

As one might see, deterministic VED using the reduction criterion is not
efficient in the multi-qubit case since it has to compute exponentially many
numbers of overlaps: for a $2n$-qubit bipartite quantum state, one has to
compute $4^{n}$ overlaps. In Section IV.5, we consider another version with
better efficiency by exploring the simple structure of the reduction map (27).

On the other hand, probabilistic VED using the reduction criterion is also not
efficient due to the sampling cost $\gamma\approx 2^{n}$ for ${\cal R}$. This
observation leads to a simple way to improve the efficiency of the
probabilistic VED. For example, we introduce the trace-preserving reduction
map, defined via

$\displaystyle\widehat{{\cal R}}_{B\to B}(\rho)\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{2^{n}-1}{\cal R}_{B\to B}(\rho_{B}).$ (33)

One can check that as a positive map, $\widehat{{\cal R}}$ has the same
entanglement detection range as the original reduction map ${\cal R}$. On the
contrary, the sampling cost of $\widehat{{\cal R}}$ is $\gamma=1+1/2^{n}$,
which is exponentially smaller than that of ${\cal R}$. This implies that
probabilistic VED using the trace-preserving reduction map $\widehat{{\cal
R}}$ is very efficient in terms of the number of samples consumed. However,
the efficiency is achieved at the cost of the high precision required in
estimating the minimal eigenvalue of $\widehat{{\cal R}}(\rho_{AB})$, which
decreases exponentially in $n$ in general. We point out this is a trade off
between efficiency and precision. Similar arguments can be applied to the
transpose map and the enhanced reduction map discussed in the next section.

###  IV.3 Enhanced reduction criterion

In this section, we consider an enhanced version of the reduction map Breuer
(2006); Hall (2006) for bipartite quantum states. This enhanced criterion is
based on an elementary positive map which operates on state spaces with _even_
dimension. It is known that the enhanced reduction criterion detects many
bound entangled states (states that satisfy the PPT criterion). As before, we
first review this enhanced reduction criterion and show how to combine it with
the VED framework proposed in Sec. III to detect entanglement.

Define the following anti-symmetric unitary in a $n$-qubit Hilbert space:

$\displaystyle U_{a}=\operatorname{antidiag}(1,-1,1,-1,\cdots,1,-1),$ (34)

where $\operatorname{antidiag}$ means anti-diagonal. For example, when $n=2$,
the corresponding anti-symmetric unitary has the form

$\displaystyle U_{a}=\begin{bmatrix}0&0&0&1\\\ 0&0&-1&0\\\ 0&1&0&0\\\
-1&0&0&0\end{bmatrix}=X\otimes iY.$ (35)

Indeed, one can check that the $n$-qubit $U_{a}$ can be decomposed w.r.t. the
Pauli set as $U_{a}=X\otimes\cdots\otimes X\otimes iY$, where there are $n-1$
$X$ operators in the tensor product. Based on $U_{a}$, we define the following
map Breuer (2006)

$\displaystyle{\cal K}_{B\to B}(\rho_{B})\mathrel{\mathop{\mathchar
58\relax}}={\cal R}_{B\to B}(\rho_{B})-U_{a}T_{B}(\rho)U_{a}^{\dagger},$ (36)

where ${\cal R}_{B\to B}$ is the reduction map defined in (27) and $T_{B}$ is
the transpose map defined in (22). This map has been shown to be positive but
not completely positive Breuer (2006). What’s more, this map improves the
reduction criterion and can detect bound entangled states that cannot be
detected by the PPT criterion. Substituting the Pauli decomposition (31) of
${\cal R}$ and the Pauli decomposition (26) of $T_{B}$ into (36) and
regrouping the Pauli terms, we obtain a Pauli decomposition of ${\cal K}$,
where there is a total number of $4^{n}$ Pauli terms. Using on this
decomposition, we can use VED (Algorithm 1 or Algorithm 2) to accomplish the
enhanced reduction criterion.

###  IV.4 Discussion on the measurement cost

Note that another way to detect and quantify entanglement of a state
$\rho_{AB}$ is to obtain its density matrix via quantum state tomography
Nielsen and Chuang (2011). Full density matrix reconstruction of an unknown
$(n_{A}+n_{B})$-qubit state in the worst-case costs exponential copies of the
state O’Donnell and Wright (2016); Haah  _et al._ (2017), e.g.,
$\widetilde{\Omega}(4^{n_{A}+n_{B}})$ measurement results are necessary to
reconstruct a matrix close to $\rho$ in the sense of trace distance Haah  _et
al._ (2017). Using the learned density matrix, we can either numerically apply
a positive map on it or compute the fidelity between $\rho_{AB}$ and any
entangled target states. However, such methods are resource-demanding compared
to the VED framework.

To use the decomposed maps for entanglement detection on the state
$\rho_{AB}$, we can apply them either to subsystem $A$ or to subsystem $B$,
which requires $poly(D)4^{\min\\{n_{A},n_{B}\\}}$ measurement results with
circuit depth $D$ in gradient-based optimization loops. Besides the
measurement cost, methods based on state tomography need vast memory to store
and process the density matrix on a classical computer, which are resource-
demanding as well. The VED framework, on the other hand, doesn’t require such
classical memory and post-processing.

###  IV.5 VED based on reduction criterion without decomposition

In Sec. IV.2 we have shown how VED uses the reduction criterion to detect
entanglement; it works by decomposing the reduction map ${\cal R}$ into a
linear combination of Pauli channels and then variationally estimate the
minimal eigenvalue of the averaged output state.

Here we propose another variational entanglement detection algorithm for the
reduction criterion, motivated by the simple structure of the reduction map.
The intuition behind this protocol is as follows. We know that $\rho_{AB}$ is
entangled if ${\cal R}_{B\to B}(\rho_{AB})$ is not semidefinite positive.
Using (1), this means that

$\displaystyle\;\min_{|\psi_{AB}\rangle}\langle\psi|{\cal R}_{B\to
B}(\rho_{AB})|\psi\rangle$ (37) $\displaystyle=$
$\displaystyle\;\min_{|\psi_{AB}\rangle}\langle\psi|(I_{A}\otimes\rho_{B}-\rho_{AB})|\psi\rangle$
(38) $\displaystyle=$
$\displaystyle\;\min_{|\psi_{AB}\rangle}\left\\{\operatorname{Tr}[\psi_{B}\rho_{B}]-\operatorname{Tr}[\psi_{AB}\rho_{AB}]\right\\}<0,$
(39)

where the minimization ranges over all pure bipartite quantum states
$|\psi_{AB}\rangle$ in system $AB$,
$\psi_{AB}\equiv|\psi\rangle\\!\langle\psi|_{AB}$ and
$\psi_{B}\mathrel{\mathop{\mathchar
58\relax}}=\operatorname{Tr}_{A}\psi_{AB}$. From Eq. (39), one can see that it
suffices to compute the difference of two overlaps and then variationally
estimate the minimal eigenvalue. The crucial point is that the number of
overlaps is independent on the dimension of the $n$-qubit system $B$. This new
detection method could save a large amount of computing resources when $n$
becomes large. The improved VED based on the reduction criterion is summarized
in Algorithm 3.

Algorithm 3 Improved VED based on reduction criterion

1: Input: $2n$-qubit quantum state $\rho_{AB}$, parameterized quantum circuits
$U(\bm{\alpha})$ with initial parameters $\bm{\alpha}$, and tolerance
$\delta$;

2: Apply $U(\bm{\alpha})$ to $|00\rangle_{AB}$ on system $AB$ and obtain the
test state $|\psi\rangle_{AB}=U(\bm{\alpha})|00\rangle_{AB}$;

3: Compute the overlap between state $\psi_{B}$ and $\rho_{B}$ on subsystem
$B$ using the Swap Test and obtain
$c_{1}=\operatorname{Tr}[\psi_{B}\rho_{B}]$;

4: Apply $U(\bm{\alpha})$ to $|00\rangle_{AB}$ on system $AB$ and obtain the
test state $|\psi\rangle_{AB}=U(\bm{\alpha})|00\rangle_{AB}$;

5: Compute the overlap between state $\psi_{AB}$ and $\rho_{AB}$ using the
Swap Test and obtain $c_{2}=\operatorname{Tr}[\psi_{AB}\rho_{AB}]$;

6: Compute the loss function $L(\bm{\alpha})=c_{1}-c_{2}$;

7: Perform optimization methods to minimize $L(\bm{\alpha})$; terminate the
optimization if the error tolerance is satisfied: $L(\bm{\alpha})<-\delta$.

8: Output ”Entangled” if the optimized $L(\bm{\alpha})<-\delta$.

We remark that this idea can also be adopted to improve the efficiency of VED
using the enhanced reduction criterion.

##  V Quantum entanglement quantification

One of the most well-known entanglement measure is the logarithmic negativity
Vidal and Werner (2002); Plenio (2005b), which has various applications in
quantum information theory. For a bipartite state $\rho_{AB}$, its logarithmic
negativity is defined as

$\displaystyle E_{N}(\rho_{AB})\mathrel{\mathop{\mathchar
58\relax}}=\log\|\rho_{AB}^{T_{B}}\|_{1}.$ (40)

Based on the recently developed near-term quantum algorithm for trace distance
estimation Chen  _et al._ (2020) and the fact that $E_{N}$ is defined via the
transpose map $T_{B}$, we introduce a variational quantum algorithm to
estimate $E_{N}$ using an ancillary qubit system $R$. According to (Chen  _et
al._ , 2020, Corollary 3), it holds that

$\displaystyle\|\rho_{AB}^{T_{B}}\|_{1}$
$\displaystyle=2\max_{U}\operatorname{Tr}|0\rangle\\!\langle
0|_{R}Q_{R}-\operatorname{Tr}\rho_{AB}^{T_{B}}$ (41)
$\displaystyle=2\max_{U}\operatorname{Tr}|0\rangle\\!\langle 0|_{R}Q_{R}-1,$
(42)

where $Q_{R}=\operatorname{Tr}_{AB}Q_{ABR}$,
$Q_{ABR}=U(\rho_{AB}^{T_{B}}\otimes|0\rangle\\!\langle 0|_{R})U^{\dagger}$,
and the maximization ranges over all unitaries on the composite system $ABR$.
Note that the second equality follows from the fact that $T_{B}$ is trace-
preserving. Following the idea of VED, we may decompose the transpose map
$T_{B}$ appeared in the operator $Q_{ABR}$ (correspondingly, $Q_{R}$) into a
linear combination of Pauli terms via (25) and (26), compute the overlaps in
(42) one by one, and then variationally estimate the maximal value. For
illustrative purposes, we give Algorithm 4, the _Variational Logarithmic
Negativity Estimation (VLNE)_ , as an example of estimating the logarithmic
negativity of a two-qubit quantum state $\rho_{AB}$. However, we emphasize
that method outlined in Algorithm 4 can be easily generalized to quantify
multi-qubit bipartite entanglement, as the transpose operation satisfies the
preferable tensor product property (26). What’s more, Algorithm 4 can be
modified to use the sampling technique to estimate the average state,
following the idea illustrated in Algorithm 2.

Algorithm 4 Variational Logarithmic Negativity Estimation

1: Input: a $2$-qubit quantum state $\rho_{AB}$ and parameterized circuits
$U_{ABR}(\bm{\alpha})$ with initial parameters $\bm{\alpha}$;

2: Apply $U_{ABR}(\bm{\alpha})$ respectively to
$\displaystyle\rho_{AB}\otimes|0\rangle\\!\langle 0|_{R},$ (43)
$\displaystyle(I_{A}\otimes X_{B})\rho_{AB}(I_{A}\otimes
X_{B})\otimes|0\rangle\\!\langle 0|_{R},$ (44) $\displaystyle(I_{A}\otimes
Y_{B})\rho_{AB}(I_{A}\otimes Y_{B})\otimes|0\rangle\\!\langle 0|_{R},$ (45)
$\displaystyle(I_{A}\otimes Z_{B})\rho_{AB}(I_{A}\otimes
Z_{B})\otimes|0\rangle\\!\langle 0|_{R},$ (46) and obtain the states
$\sigma^{(0)}$, $\sigma^{(1)}$, $\sigma^{(2)}$, $\sigma^{(3)}$, respectively.

3: Obtain $o_{j}=\operatorname{Tr}[\sigma^{(j)}_{R}|0\rangle\\!\langle
0|_{R}]$ for $j=0,1,2,3$ by measurements on system $R$.

4: Compute the loss function ${\cal L}_{1}\mathrel{\mathop{\mathchar
58\relax}}=-(o_{0}+o_{1}-o_{2}+o_{3})/2$.

5: Perform optimization methods to minimize ${\cal L}_{1}(\bm{\alpha})$;

6: Compute $\beta=2|{\cal L}_{1}|-1$ as the estimated trace norm of
$\rho_{AB}^{T_{B}}$;

7: Output $\log\beta$ as the estimated logarithmic negativity.

One may also evaluate the entanglement measures Chen  _et al._ (2014); Zhu
_et al._ (2017); Wang  _et al._ (2019) based on the sandwiched Rényi relative
entropy Müller-Lennert  _et al._ (2013); Wilde  _et al._ (2014) of order
$1/2$, making use of the recently proposed variational quantum algorithm
estimating the fidelity between two quantum states Chen  _et al._ (2020).

##  VI Experiments in IBMQ

In this section, we discuss how to apply the VED framework to detect the two-
qubit maximally entangled state $|\Phi\rangle\mathrel{\mathop{\mathchar
58\relax}}=(|00\rangle+|11\rangle)/\sqrt{2}$ on IBM-Q superconducting quantum
hardware accessible to the public. The specific quantum device used is ibmq-
santiago (5 qubits) with a quantum volume of $32$. The positive map adopted
here for detection purpose is the qubit reduction map ${\cal R}_{B\to B}$
defined in Eq. (27). After implementing the decomposed reduction map by $4$
Pauli terms as Eq. (32), we use a parametrized quantum circuit
$U(\bm{\alpha})$ to prepare $4$ identical test states
$\psi_{AB}(\bm{\alpha})=U(\bm{\alpha})|00\rangle\\!\langle
00|_{AB}U^{\dagger}(\bm{\alpha})$ and compute the loss function defined in Eq.
(13). The PQC used is depicted in Fig. 2 with three randomly initialized
parameters $\bm{\alpha}=(\alpha_{1},\alpha_{2},\alpha_{3})$. During the
optimization procedure, we apply the gradient descent algorithm Lemaréchal
(2012) to guide the learning process where the analytical gradient is
calculated via the following parameter-shift rule Mitarai  _et al._ (2018):

$\displaystyle\frac{\partial{\cal
L}(\bm{\alpha})}{\partial\alpha_{j}}\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{2}\left[{\cal
L}\left(\alpha_{j}+\frac{\pi}{2}\right)-{\cal
L}\left(\alpha_{j}-\frac{\pi}{2}\right)\right].$ (47)

$\Qcircuit@C=0.8em@R=0.5em{\lstick{|0\rangle}&\gate{R_{y}(\alpha_{1})}\gate{R_{z}(\alpha_{3})}\qw\ctrl{1}\qw\raisebox{-38.74988pt}{
$\Bigg{\\}}\,|\psi\rangle$ }\\\
\lstick{|0\rangle}\gate{R_{y}(\alpha_{2})}\qw\qw\targ\qw}$ Figure 2:
Parameterized two-qubit quantum circuit $U(\bm{\alpha})$ used for preparing
the test state $\psi_{AB}(\bm{\alpha})$ on the ibmq-santiago hardware. The
parameters $\bm{\alpha}$ are randomly initialized as
$(\alpha_{1},\alpha_{2},\alpha_{3})=(3.2292,4.8579,5.4691)$.

Due to the finite sampling restriction for measurements, the optimization
procedure essentially falls into the regime of Stochastic Gradient Descent
(SGD) Kiefer  _et al._ (1952). The optimized loss values converges to ${\cal
L}_{\min}\approx-0.43$. The gap between the experiment data and simulation
result $\lambda_{\text{min}}=-0.5$ is due to various hardware noises on the
ibmq-santiago processor. One can further adopt error mitigation methods Endo
_et al._ (2020) to improve the result. This result proves the validity of our
VED framework. Note that if we adopt the termination setup in Algorithm 1, it
will require much fewer optimization iterations ($4$ to $5$ rounds are
sufficient) to obtain the detection result. As mentioned in Ref. Coles  _et
al._ (2018), the communication bottleneck between the IBM-Q hardware and
classical optimizer blocks us from efficiently conducting experiments without
any specified reservation. This leads to a $9$-minutes waiting time on average
for each circuit evaluation from the IBM-Q cloud service. As a comparison, we
conduct numerical simulations on Quantum Leaf platform and receive a similar
result by repeating the simulation on qiskit-Aer simulator. We summarize the
experimental and numerical results in Fig. 3.

Figure 3: Estimated $\lambda_{\text{min}}$ by VED using the reduction
criterion on the Bell state $|\Phi\rangle$. The red curve records the results
from ibmq-santiago with shots = $8192$ for each circuit evaluation. The blue
curve records the simulation results on Quantum Leaf platform using the Baidu
Quleaf simulator Qul (2020). Learning rate in the gradient descent algorithm
is set to be LR $=0.5$.

##  VII Numerical simulations

In this section, we carry out numerical simulations that apply VED to detect a
variety of bipartite quantum states of interest to investigate the performance
of VED and its motivated entanglement quantification algorithm. All
simulations, including optimization loops, are conducted using the Paddle
Quantum Pad (2020) toolkit on the PaddlePaddle Deep Learning Platform Pad ; Ma
_et al._ (2019).

###  VII.1 Entanglement detection

For the entanglement detection purpose, we adopt the circuit ansatz shown in
Fig. 4 to prepare the test state $|\psi\rangle_{AB}$. It consists of
parameterized single-qubit gates
$U_{3}(\theta,\phi,\varphi)=R_{z}(\phi)R_{y}(\theta)R_{z}(\varphi)$ and
circular layers of CNOT gates. Note that this ansatz can be easily generalized
to multi-qubit case.

$\Qcircuit@C=0.8em@R=0.5em{&\gate{U_{3}(\theta_{0,0},\theta_{0,1},\theta_{0,2})}\ctrl{1}\qw\targ\qw\cdots\quad\gate{U_{3}(\theta_{2,0},\theta_{2,1},\theta_{2,2})}\qw\\\
\gate{U_{3}(\theta_{0,3},\theta_{0,4},\theta_{0,5})}\targ\ctrl{1}\qw\qw\cdots\quad\gate{U_{3}(\theta_{2,3},\theta_{2,4},\theta_{2,5})}\qw\\\
\gate{U_{3}(\theta_{0,6},\theta_{0,7},\theta_{0,8})}\qw\targ\ctrl{-2}\qw^{\quad\quad\quad\,\times
2}\cdots\quad\gate{U_{3}(\theta_{2,6},\theta_{2,7},\theta_{2,8})}\qw\gategroup{1}{2}{3}{5}{2.07em}{--}}$
Figure 4: Three qubit parameterized ansatz $U(\bm{\alpha})$ used for VED. The
quantum circuit within the dotted block is repeated twice.

####  VII.1.1 Four-qubit isotropic states

The four-qubit isotropic state family is defined as (Horodecki and Horodecki,
1999, Eq. (32))

$\displaystyle\rho^{\text{iso}}_{\bm{A}\bm{B}}(p)\mathrel{\mathop{\mathchar
58\relax}}=p\Phi_{\bm{AB}}+(1-p)\frac{I_{\bm{AB}}}{16},$ (48)

where $p\in[0,1]$ is a parameter, $\Phi_{\bm{AB}}$ is the four-qubit maximally
entangled state, and $I_{\bm{AB}}$ is the identity operator in $\bm{AB}$ in
which $\bm{A}\equiv A_{1}A_{2}$ and $\bm{B}\equiv B_{1}B_{2}$. The qubit
systems $A_{1}$ and $A_{2}$ are at Alice’s hand, while the qubit systems
$B_{1}$ and $B_{2}$ are at Bob’s hand. Intuitively, the isotropic state is a
convex combination of the maximally entangled state $\Phi_{\bm{AB}}$ and the
maximally mixed state $I_{\bm{AB}}/16$. It has been shown that
$\rho^{\text{iso}}_{\bm{AB}}(p)$ is separable (w.r.t. the
$\bm{A}{\mathrel{\mathop{\mathchar 58\relax}}}\bm{B}$ cut) if and only if
$p\leq 1/5$ Horodecki and Horodecki (1999).

We numerically carry out Algorithm 1 together with the three prominent
positive maps—the PPT criterion, the reduction criterion, and the enhanced
reduction criterion—introduced in Sec. IV, using four-qubit isotropic states
as inputs. The minimized loss values of these three maps obtained by our
simulations on the isotropic states are represented by different markers in
Fig. 5. As can be seen from this figure, VED can successfully identify the
range of $p$ for which the corresponding isotropic state can be detected by
each positive map. The markers representing results from simulations fall on
the lines that give the minimums of the loss function $L(\bm{\alpha})$,
verifying the validity and viability of our VED framework. Note that for
detecting entanglement in four-qubit isotropic states, all three maps are both
necessary and sufficient. However, this phenomenon is not universal for all
four-qubit states, as we shall see in the experiment using Breuer states.

Figure 5: Numerical results on the four-qubit isotropic states defined in
(48). Each line depicts the smallest eigenvalue of every isotropic state with
parameter $p\in[0,1]$ under the corresponding map. This line of the smallest
eigenvalues is a lower bound of the loss function $L(\bm{\alpha})$. Each
marker depicts the minimized loss value obtained by simulations (sim) of
Algorithm 1 on a chosen isotropic state, aligning with the theoretical line.

####  VII.1.2 Four-qubit Breuer states

As we have mentioned in Sec. IV.3, there are states that can be detected by
the enhanced reduction criterion yet cannot be detected by the PPT criterion.
In this section, we use the proposed VED framework to numerically consolidate
this statement. The four-qubit Breuer state family is defined as (Breuer,
2006, Eq. (7))

$\displaystyle\rho^{\text{Breuer}}_{\bm{A}\bm{B}}(\lambda)\mathrel{\mathop{\mathchar
58\relax}}=\begin{pmatrix}\frac{1-\lambda}{3}&0&0&0\\\
0&\frac{1+2\lambda}{6}&\frac{1-4\lambda}{6}&0\\\
0&\frac{1-4\lambda}{6}&\frac{1+2\lambda}{6}&0\\\
0&0&0&\frac{1-\lambda}{3}\end{pmatrix},$ (49)

where $\lambda\in[0,1]$ is a parameter, $\bm{A}\equiv A_{1}A_{2}$, and
$\bm{B}\equiv B_{1}B_{2}$. The qubit systems $A_{1}$ and $A_{2}$ are at
Alice’s hand while the qubit systems $B_{1}$ and $B_{2}$ are at Bob’s hand. It
has been shown that $\rho^{\text{Breuer}}$ is separable (w.r.t. the
$\bm{A}{\mathrel{\mathop{\mathchar 58\relax}}}\bm{B}$ cut) if and only if
$\lambda=0$ and can be detected by the enhanced reduction criterion Breuer
(2006). On the other hand, it has positive partial transpose if and only if
$\lambda\leq 1/6$ Breuer (2006), witnessing the power of the enhanced
reduction criterion.

Following the same line of the case of the isotropic state, we carry out
Algorithm 1 on the three criteria using four-qubit Breuer states as inputs.
The minimized loss values obtained by our simulations on selected Breuer
states are represented in Fig. 6 by markers, which again aligns with the
theoretical lines. From the numeric results, we can see that while the
enhanced reduction criterion is sill necessary and sufficient for entanglement
detection in the four-qubit Breuer states, neither the reduction criterion nor
the PPT criterion can detect all entangled states in the Breuer state family,
attesting the advantage of the enhanced reduction criterion in this case.

Figure 6: Numerical results on the four-qubit Breuer states defined in (49).
Each line depicts the smallest eigenvalue of every Breuer state with parameter
$p\in[0,1]$ under the corresponding map. This line of the smallest eigenvalues
is a lower bound of the loss function $L(\bm{\alpha})$. Each marker depicts
the minimized loss value obtained by simulations (sim) of Algorithm 1 on a
chosen Breuer state, aligning with the theoretical line.

###  VII.2 Logarithmic negativity estimation

For simulations of variational entanglement quantification with logarithmic
negativity, we adopt the hardware efficient ansatz used for trace distance
estimation in Chen  _et al._ (2020) where the circuit depth is $4$. The
simulations are carried out on two-qubit isotropic states, which is defined as

$\displaystyle\rho^{\text{iso}}_{AB}(p)\mathrel{\mathop{\mathchar
58\relax}}=p\Phi_{AB}+(1-p)\frac{I_{AB}}{4},$ (50)

where $\Phi_{AB}$ is the two-qubit maximally entangled state. As shown in Fig.
7, the logarithmic negativity of a two-qubit isotropic state is positive if
and only if its parameter $p>1/3$, which matches the range of $p$ where the
corresponding isotropic states are entangled. The estimated logarithmic
negativities by our method, which are represented by markers in Fig. 7, agree
with the precisely calculated values given by the blue line.

Figure 7: Numerical results on the two-qubit isotropic states. The blue line
represents the precisely calculated logarithmic negativity of isotropic states
with parameter $p\in[0,1]$. The yellow markers depict the estimated
logarithmic negativity by simulations of Algorithm 4 on selected isotropic
states.

##  VIII Conclusion and outlook

In this work, we combined two novel techniques that find crucial applications
in the NISQ quantum devices, the variational quantum algorithms and the quasi-
probability decomposition method, to propose the Variational Entanglement
Detection (VED) and Variational Logarithmic Negativity Estimation (VLNE)
frameworks, contributing feasible solutions to detect and quantify
entanglement on near-term devices. VED is built upon the positive map
criterion and works as follows. Firstly, it decomposes a chosen positive map
into a linear combination of NISQ implementable quantum operations. Then, it
variationally estimates the minimal eigenvalue of the output state of some
positive map acting on the target bipartite state. Two methods are proposed to
generate the output state: the first one averaged the output states according
to the quasi-probability distribution; the second one estimated the average
via the sampling technique. At last, it asserts that the target state is
entangled if the optimized minimal eigenvalue is negative, guaranteed by the
positive map criterion. We elaborated three well-known positive maps to
illustrate how the VED framework is applied. Following the idea of VED, VLNE
variationally computes the log-negativity entanglement measure, relying on a
linear decomposition of the transpose map into Pauli terms and the recently
proposed trace distance estimation algorithm. Experimental and numerical
results on various bipartite states of interest have validated the proposed
entanglement detection and quantification methods.

We expect that the VED framework can be upgraded to detect more entangled
states. A crucial step towards this aim is to explore what kind of positive
maps can be decomposed into a linear combination of Pauli channels. In Sec. V
we showed by case how to variationally compute the log-negativity entanglement
measure. It would be meaningful to design novel quantum algorithms to estimate
other distance-based entanglement measures Vedral  _et al._ (1997); Vedral and
Plenio (1998); Rains (2001); Datta (2009); Zhu  _et al._ (2017).

## Acknowledgements

We thank Runyao Duan for helpful suggestions. XW would like to thank Youle
Wang for useful discussions.

## References

  * Preskill (2018) J. Preskill, Quantum 2, 79 (2018).
  * McClean  _et al._ (2016) J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik, New Journal of Physics 18, 023023 (2016).
  * Peruzzo  _et al._ (2014) A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’brien, Nature communications 5, 4213 (2014).
  * Nakanishi  _et al._ (2019) K. M. Nakanishi, K. Mitarai, and K. Fujii, Physical Review Research 1, 033062 (2019).
  * Cerezo  _et al._ (2020a) M. Cerezo, A. Poremba, L. Cincio, and P. J. Coles, Quantum 4, 248 (2020a).
  * Chen  _et al._ (2020) R. Chen, Z. Song, X. Zhao, and X. Wang, arXiv:2012.05768 , 1 (2020), arXiv:2012.05768 .
  * Beckey  _et al._ (2020) J. L. Beckey, M. Cerezo, A. Sone, and P. J. Coles, arXiv: 2010.10488 , 1 (2020), arXiv:2010.10488 .
  * Koczor  _et al._ (2019) B. Koczor, S. Endo, T. Jones, Y. Matsuzaki, and S. C. Benjamin, arXiv:1908.08904 , 1 (2019), arXiv:1908.08904 .
  * Romero  _et al._ (2017) J. Romero, J. P. Olson, and A. Aspuru-Guzik, Quantum Science and Technology 2, 045001 (2017), arXiv:1612.02806 .
  * Wan  _et al._ (2017) K. H. Wan, O. Dahlsten, H. Kristjánsson, R. Gardner, and M. S. Kim, npj Quantum Information 3, 36 (2017), arXiv:1612.01045 .
  * Cao and Wang (2020) C. Cao and X. Wang, arXiv preprint arXiv:2012.08331 (2020), arXiv:2012.08331 .
  * Endo  _et al._ (2020) S. Endo, Z. Cai, S. C. Benjamin, and X. Yuan, arXiv:2011.01382 , 1 (2020), arXiv:2011.01382 .
  * Cerezo  _et al._ (2020b) M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, arXiv:2012.09265 , 1 (2020b), arXiv:2012.09265 .
  * Horodecki  _et al._ (2009) R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Reviews of Modern Physics 81, 865 (2009).
  * Bennett and Wiesner (1992) C. H. Bennett and S. J. Wiesner, Physical Review Letters 69, 2881 (1992).
  * Bennett  _et al._ (1993) C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, Physical review letters 70, 1895 (1993).
  * Bell (1964) J. S. Bell, Physics Physique Fizika 1, 195 (1964).
  * Clauser  _et al._ (1970) J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, Physical Review Letters 24, 549 (1970).
  * Ekert (1991) A. K. Ekert, Physical Review Letters 67, 661 (1991).
  * Shor (1994) P. W. Shor, in  _Proceedings 35th annual symposium on foundations of computer science_ (Ieee, 1994) pp. 124–134.
  * Jozsa (1997) R. Jozsa, arXiv preprint quant-ph/9707034 (1997).
  * Childs and Van Dam (2010) A. M. Childs and W. Van Dam, Reviews of Modern Physics 82, 1 (2010).
  * Bennett  _et al._ (1999) C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, Physical Review Letters 83, 3081 (1999).
  * Bennett  _et al._ (2002) C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, IEEE Transactions on Information Theory 48, 2637 (2002).
  * Raussendorf and Briegel (2001) R. Raussendorf and H. J. Briegel, Physical Review Letters 86, 5188 (2001).
  * Raussendorf  _et al._ (2003) R. Raussendorf, D. E. Browne, and H. J. Briegel, Physical review A 68, 022312 (2003).
  * Gross and Eisert (2007) D. Gross and J. Eisert, Physical review letters 98, 220503 (2007).
  * Briegel  _et al._ (2009) H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest, Nature Physics 5, 19 (2009).
  * Gühne and Tóth (2009) O. Gühne and G. Tóth, Physics Reports 474, 1 (2009).
  * Friis  _et al._ (2019) N. Friis, G. Vitagliano, M. Malik, and M. Huber, Nature Reviews Physics 1, 72 (2019), arXiv:1906.10929 .
  * Horodecki  _et al._ (1996) M. Horodecki, P. Horodecki, and R. Horodecki, Physics Letters A 223, 1 (1996).
  * Gühne and Lütkenhaus (2006) O. Gühne and N. Lütkenhaus, Physical review letters 96, 170502 (2006).
  * Bell and Bell (2004) J. S. Bell and J. S. Bell,  _Speakable and unspeakable in quantum mechanics: Collected papers on quantum philosophy_ (Cambridge university press, 2004).
  * Pezzé and Smerzi (2009) L. Pezzé and A. Smerzi, Physical review letters 102, 100401 (2009).
  * Chen and Wu (2002) K. Chen and L.-A. Wu, arXiv preprint quant-ph/0205017 (2002).
  * Rudolph (2005) O. Rudolph, Quantum Information Processing 4, 219 (2005).
  * Horodecki (1997) P. Horodecki, Physics Letters A 232, 333 (1997).
  * Nielsen and Kempe (2001) M. A. Nielsen and J. Kempe, Physical Review Letters 86, 5184 (2001).
  * D’Ariano  _et al._ (2003) G. M. D’Ariano, M. G. Paris, and M. F. Sacchi, Advances in Imaging and Electron Physics 128, 206 (2003).
  * Steffen  _et al._ (2006) M. Steffen, M. Ansmann, R. C. Bialczak, N. Katz, E. Lucero, R. McDermott, M. Neeley, E. M. Weig, A. N. Cleland, and J. M. Martinis, Science 313, 1423 (2006).
  * Buscemi  _et al._ (2013) F. Buscemi, M. Dall’Arno, M. Ozawa, and V. Vedral, arXiv:1312.4240 , 1 (2013), arXiv:1312.4240 .
  * Buscemi  _et al._ (2014) F. Buscemi, M. Dall’Arno, M. Ozawa, and V. Vedral, International Journal of Quantum Information 12, 1 (2014), arXiv:1409.2237 .
  * Pashayan  _et al._ (2015) H. Pashayan, J. J. Wallman, and S. D. Bartlett, Physical Review Letters 115, 070501 (2015).
  * Temme  _et al._ (2017) K. Temme, S. Bravyi, and J. M. Gambetta, Physical Review Letters 119, 180509 (2017).
  * Endo  _et al._ (2018) S. Endo, S. C. Benjamin, and Y. Li, Physical Review X 8, 031027 (2018).
  * Takagi (2020) R. Takagi, arXiv preprint arXiv:2006.12509 (2020).
  * Jiang  _et al._ (2020) J. Jiang, K. Wang, and X. Wang, (2020), arXiv:2012.10959v1, 2012.10959 .
  * Plenio (2005a) M. B. Plenio, Physical review letters 95, 090503 (2005a).
  * Werner (1989) R. F. Werner, Physical Review A 40, 4277 (1989).
  * Gurvits (2003) L. Gurvits, in  _Proceedings of the thirty-fifth annual ACM symposium on Theory of computing_ (ACM, 2003) pp. 10–19.
  * Gharibian (2008) S. Gharibian, arXiv arXiv:0810.4507 (2008).
  * Peres (1996) A. Peres, Physical Review Letters 77, 1413 (1996).
  * Kraus (1983) K. Kraus,  _States, effects, and Operations_ (Springer-Verlag, Berlin, 1983).
  * Buhrman  _et al._ (2001) H. Buhrman, R. Cleve, J. Watrous, and R. De Wolf, Physical Review Letters 87, 167902 (2001).
  * Kiefer  _et al._ (1952) J. Kiefer, J. Wolfowitz, _et al._ , The Annals of Mathematical Statistics 23, 462 (1952).
  * Kingma and Ba (2014) D. P. Kingma and J. Ba, arXiv preprint arXiv:1412.6980 (2014).
  * Hoeffding (1994) W. Hoeffding, in  _The Collected Works of Wassily Hoeffding_ (Springer, 1994) pp. 409–426.
  * Cerf  _et al._ (1999) N. J. Cerf, C. Adami, and R. M. Gingrich, Physical Review A 60, 898 (1999).
  * Breuer (2006) H.-P. Breuer, Physical Review Letters 97, 080501 (2006).
  * Hall (2006) W. Hall, Journal of Physics A: Mathematical and General 39, 14119 (2006).
  * Choi (1975) M.-D. Choi, Linear Algebra and its Applications 12, 95 (1975).
  * Choi (1980) M.-D. Choi, Journal of Operator Theory , 271 (1980).
  * Stormer (1963) E. Stormer, Acta Mathematica 110, 233 (1963).
  * Woronowicz (1976) S. L. Woronowicz, Reports on Mathematical Physics 10, 165 (1976).
  * Wilde (2016) M. M. Wilde,  _Quantum Information Theory 2nd Edition_ (Cambridge University Press, 2016).
  * Nielsen and Chuang (2011) M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information_ (Cambridge University Press, 2011).
  * O’Donnell and Wright (2016) R. O’Donnell and J. Wright, in  _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_ (2016) pp. 899–912.
  * Haah  _et al._ (2017) J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu, IEEE Transactions on Information Theory 63, 5628 (2017).
  * Vidal and Werner (2002) G. Vidal and R. F. Werner, Physical Review A 65, 032314 (2002).
  * Plenio (2005b) M. B. Plenio, Physical Review Letters 95, 090503 (2005b).
  * Chen  _et al._ (2014) L. Chen, M. Aulbach, and M. Hajdušek, Physical Review A 89, 042305 (2014).
  * Zhu  _et al._ (2017) H. Zhu, M. Hayashi, and L. Chen, Journal of Physics A: Mathematical and Theoretical 50, 475303 (2017).
  * Wang  _et al._ (2019) K. Wang, X. Wang, and M. M. Wilde, arXiv preprint arXiv:1911.07433 (2019).
  * Müller-Lennert  _et al._ (2013) M. Müller-Lennert, F. Dupuis, O. Szehr, S. Fehr, and M. Tomamichel, Journal of Mathematical Physics 54, 122203 (2013).
  * Wilde  _et al._ (2014) M. M. Wilde, A. Winter, and D. Yang, Communications in Mathematical Physics 331, 593 (2014).
  * Lemaréchal (2012) C. Lemaréchal, Doc Math Extra 251, 254 (2012).
  * Mitarai  _et al._ (2018) K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, Physical Review A 98, 032309 (2018).
  * Coles  _et al._ (2018) P. J. Coles, S. Eidenbenz, S. Pakin, A. Adedoyin, J. Ambrosiano, P. Anisimov, W. Casper, G. Chennupati, C. Coffrin, H. Djidjev, _et al._ , arXiv , arXiv (2018).
  * Qul (2020) “Baidu Quleaf Simulator,”  (2020).
  * Pad (2020) “Paddle Quantum,”  (2020).
  * (81) “https://github.com/paddlepaddle/paddle,” .
  * Ma  _et al._ (2019) Y. Ma, D. Yu, T. Wu, and H. Wang, Frontiers of Data and Domputing 1, 105 (2019).
  * Horodecki and Horodecki (1999) M. Horodecki and P. Horodecki, Physical Review A 59, 4206 (1999).
  * Vedral  _et al._ (1997) V. Vedral, M. B. Plenio, M. A. Rippin, and P. L. Knight, Physical Review Letters 78, 2275 (1997).
  * Vedral and Plenio (1998) V. Vedral and M. B. Plenio, Physical Review A 57, 1619 (1998).
  * Rains (2001) E. M. Rains, IEEE Transactions on Information Theory 47, 2921 (2001).
  * Datta (2009) N. Datta, IEEE Transactions on Information Theory 55, 2816 (2009).

##  Appendix A Qutrit entanglement detection via the Choi map

In this Appendix, we show by example how VED can be adapted to detect the
entanglement of an unknown two-qutrit state via the celebrated Choi map Choi
(1975, 1980). To be specific, the Choi map is defined as follows

$\Phi_{C}(\rho)\mathrel{\mathop{\mathchar
58\relax}}=\begin{bmatrix}\rho_{1,1}+\rho_{2,2}&-\rho_{1,2}&-\rho_{1,3}\\\
-\rho_{2,1}&\rho_{2,2}+\rho_{3,3}&-\rho_{2,3}\\\
-\rho_{3,1}&-\rho_{3,2}&\rho_{3,3}+\rho_{1,1}\end{bmatrix},$ (51)

where $\rho_{i,j}$ is the element of $\rho$ in the $i$-th row and $j$-th
column. This map is the first known example of a positive map that is
indecomposable (i.e., it cannot be decomposed into a sum of a completely
positive map and a completely copositive map). The Choi map in particular can
be used to detect entanglement of some PPT states (states that can not be
detected by the transpose map).

For the qutrit system, the generalized Pauli matrices are defined through the
unitary boost and shift operators

$\displaystyle X=\begin{bmatrix}0&0&1\\\ 1&0&0\\\
0&1&0\end{bmatrix}\quad\text{and}\quad Z=\begin{bmatrix}1&0&0\\\ 0&\omega&0\\\
0&0&\omega^{2}\end{bmatrix},$ (52)

where $\omega\mathrel{\mathop{\mathchar 58\relax}}=e^{2\pi i/3}$ is the $3$-th
root of unity. The Choi map can be decomposed w.r.t. $X$ and $Z$ as follows:

$\displaystyle\Phi_{C}(\rho)$
$\displaystyle=\frac{1}{3}[X^{2}Z\rho(X^{2}Z)^{\dagger}+X^{2}Z^{2}\rho(X^{2}Z^{2})^{\dagger}+X^{2}\rho(X^{2})^{\dagger}]$
$\displaystyle\qquad+\frac{2}{3}[Z\rho
Z^{\dagger}+Z^{2}\rho(Z^{2})^{\dagger}]-\frac{1}{3}\rho.$ (53)

Based on (53), one could adopt the deterministic VED in Algorithm 1 or the
probabilistic VED in Algorithm 2 to detect entanglement on qutrit systems by
considering

$\displaystyle\min_{\psi(\bm{\alpha})}\langle\psi(\bm{\alpha})|\Phi_{C}(\rho_{AB})|\psi(\bm{\alpha})\rangle,$
(54)

where the test state $\psi(\bm{\alpha})$ can be generated by parameterized
quantum circuits.


[Bui et al., 2018]
Thang D Bui, Cuong V Nguyen, Siddharth Swaroop, and Richard E Turner.
Partitioned variational inference: A unified framework encompassing
federated and continual learning.
arXiv preprint arXiv:1811.11206, 2018.

[Casado et al., 2021]
Fernando E. Casado, Dylan Lema, Marcos F. Criado, Roberto Iglesias, Carlos V.
Regueiro, and Senén Barro.
Concept drift detection and adaptation for federated and continual
CoRR, abs/2105.13309, 2021.
URL <https://arxiv.org/abs/2105.13309>.

[Castro et al., 2018]
Francisco M Castro, Manuel J Marín-Jiménez, Nicolás Guil, Cordelia
Schmid, and Karteek Alahari.
End-to-end incremental learning.
In Proceedings of the European conference on computer vision
(ECCV), pp.  233–248, 2018.

[Chen & Chao, 2021]
Hong-You Chen and Wei-Lun Chao.
On bridging generic and personalized federated learning.
arXiv preprint arXiv:2107.00778, 2021.

[Collins et al., 2021]
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai.
Exploiting shared representations for personalized federated
In arXiv preprint arXiv:2102.07078, 2021.

[Das et al., 2020]
Rudrajit Das, Anish Acharya, Abolfazl Hashemi, Sujay Sanghavi, Inderjit S
Dhillon, and Ufuk Topcu.
Faster non-convex federated learning via global and local momentum.
arXiv preprint arXiv:2012.04061, 2020.

[Diao et al., 2021]
Enmao Diao, Jie Ding, and Vahid Tarokh.
Heterofl: Computation and communication efficient federated learning
for heterogeneous clients.
In International Conference on Learning Representations, 2021.
URL <https://openreview.net/forum?id=TNkPBBYFkXg>.

[Dinh et al., 2020]
Canh T Dinh, Nguyen H Tran, and Tuan Dung Nguyen.
Personalized federated learning with moreau envelopes.
In Advances in Neural Information Processing Systems, 2020.

[French, 1999]
Robert M French.
Catastrophic forgetting in connectionist networks.
Trends in cognitive sciences, 30 (4):0
128–135, 1999.

[Goodfellow et al., 2014]
Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David
Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.
Generative adversarial networks, 2014.

[Gower et al., 2019]
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor
Shulgin, and Peter Richtárik.
Sgd: General analysis and improved rates.
In International Conference on Machine Learning, pp.  5200–5209. PMLR, 2019.

[Haddadpour et al., 2021]
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi.
Federated learning with compression: Unified analysis and sharp
In International Conference on Artificial Intelligence and
Statistics, pp.  2350–2358. PMLR, 2021.

[Hanzely & Richtárik, 2020]
Filip Hanzely and Peter Richtárik.
Federated learning of a mixture of global and local models.
arXiv preprint arXiv:2002.05516, 2020.

[Hsu et al., 2019]
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown.
Measuring the effects of non-identical data distribution for
federated visual classification.
arXiv preprint arXiv:1909.06335, 2019.

[Kairouz et al., 2019]
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi
Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham
Cormode, Rachel Cummings, et al.
Advances and open problems in federated learning.
arXiv preprint arXiv:1912.04977, 2019.

[Karimireddy et al., 2020]
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J
Reddi, Sebastian U Stich, and Ananda Theertha Suresh.
Mime: Mimicking centralized stochastic algorithms in federated
arXiv preprint arXiv:2008.03606, 2020a.

[Karimireddy et al., 2020]
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian
Stich, and Ananda Theertha Suresh.
Scaffold: Stochastic controlled averaging for federated learning.
In International Conference on Machine Learning, pp.  5132–5143. PMLR, 2020b.

[Khaled et al., 2020]
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik.
Tighter theory for local sgd on identical and heterogeneous data.
In International Conference on Artificial Intelligence and
Statistics, pp.  4519–4529. PMLR, 2020.

[Kirkpatrick et al., 2017]
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume
Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka
Grabska-Barwinska, et al.
Overcoming catastrophic forgetting in neural networks.
Proceedings of the national academy of sciences, 1140
(13):0 3521–3526, 2017.

[Koloskova et al., 2020]
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian
A unified theory of decentralized sgd with changing topology and
local updates.
In International Conference on Machine Learning, pp.  5381–5393. PMLR, 2020.

[Li et al., 2018]
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and
Virginia Smith.
Federated optimization in heterogeneous networks.
arXiv preprint arXiv:1812.06127, 2018.

[Li et al., 2020]
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith.
Fair resource allocation in federated learning.
In 8th International Conference on Learning Representations,
ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net,
URL <https://openreview.net/forum?id=ByexElSYDr>.

[Li et al., 2021]
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith.
Ditto: Fair and robust federated learning through personalization.
In International Conference on Machine Learning, pp.  6357–6368. PMLR, 2021.

[Li et al., 2020]
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang.
On the convergence of fedavg on non-iid data.
In International Conference on Learning Representations,
URL <https://openreview.net/forum?id=HJxNAnVtDS>.

[Li & Hoiem, 2017]
Zhizhong Li and Derek Hoiem.
Learning without forgetting.
IEEE transactions on pattern analysis and machine
intelligence, 400 (12):0 2935–2947, 2017.

[Lin et al., 2020]
Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi.
Ensemble distillation for robust model fusion in federated learning.
In Advances in Neural Information Processing Systems,

[Lin et al., 2020]
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi.
Don't use large mini-batches, use local sgd.
In International Conference on Learning Representations,
URL <https://openreview.net/forum?id=B1eyO1BFPr>.

[Luo et al., 2021]
Mi Luo, Fei Chen, Dapeng Hu, Yifan Zhang, Jian Liang, and Jiashi Feng.
No fear of heterogeneity: Classifier calibration for federated
learning with non-iid data.
arXiv preprint arXiv:2106.05001, 2021.

[Maltoni & Lomonaco, 2019]
Davide Maltoni and Vincenzo Lomonaco.
Continuous learning in single-incremental-task scenarios.
Neural Networks, 116:0 56–73, 2019.

[McMahan et al., 2017]
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera
y Arcas.
Communication-efficient learning of deep networks from decentralized
In Artificial Intelligence and Statistics, pp.  1273–1282.
PMLR, 2017.

[Mitra et al., 2021]
Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani.
Achieving linear convergence in federated learning under objective
and systems heterogeneity.
arXiv preprint arXiv:2102.07053, 2021.

[Mohri et al., 2019]
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh.
Agnostic federated learning.
In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.),
Proceedings of the 36th International Conference on Machine Learning,
ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of
Proceedings of Machine Learning Research, pp.  4615–4625. PMLR,
URL <http://proceedings.mlr.press/v97/mohri19a.html>.

[Nori et al., 2014]
Aditya Nori, Chung-Kil Hur, Sriram Rajamani, and Selva Samuel.
R2: An efficient mcmc sampler for probabilistic programs.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 28, 2014.

[Patel & Dieuleveut, 2019]
Kumar Kshitij Patel and Aymeric Dieuleveut.
Communication trade-offs for synchronized distributed sgd with large
step size.
In Advances in Neural Information Processing Systems, 2019.

[Rebuffi et al., 2017]
Sylvestre-Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H
icarl: Incremental classifier and representation learning.
In Proceedings of the IEEE conference on Computer Vision and
Pattern Recognition, pp.  2001–2010, 2017.

[Reddi et al., 2021]
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush,
Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan.
Adaptive federated optimization.
In International Conference on Learning Representations, 2021.
URL <https://openreview.net/forum?id=LkFG3lB13U5>.

[Reisizadeh et al., 2020]
Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaie.
Robust federated learning: The case of affine distribution shifts.
In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell,
Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural
Information Processing Systems 33: Annual Conference on Neural Information
Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.

[Rusu et al., 2016]
Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James
Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell.
Progressive neural networks.
arXiv preprint arXiv:1606.04671, 2016.

[Sammut & Webb, 2010]
Claude Sammut and Geoffrey I. Webb (eds.).
Neuro-Dynamic Programming, pp.  716–716.
Springer US, Boston, MA, 2010.
ISBN 978-0-387-30164-8.
URL <https://doi.org/10.1007/978-0-387-30164-8_588>.

[Shoham et al., 2019]
Neta Shoham, Tomer Avidor, Aviv Keren, Nadav Israel, Daniel Benditkis, Liron
Mor-Yosef, and Itai Zeitak.
Overcoming forgetting in federated learning on non-iid data.
CoRR, abs/1910.07796, 2019.
URL <http://arxiv.org/abs/1910.07796>.

[Stich, 2019]
Sebastian U. Stich.
Local SGD converges fast and communicates little.
In International Conference on Learning Representations, 2019.
URL <https://openreview.net/forum?id=S1g2JnRcFX>.

[Stich & Karimireddy, 2020]
Sebastian U Stich and Sai Praneeth Karimireddy.
The error-feedback framework: Better rates for sgd with delayed
gradients and compressed updates.
Journal of Machine Learning Research, 21:0 1–36,

[Wang et al., 2020]
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor.
Tackling the objective inconsistency problem in heterogeneous
federated optimization.
arXiv preprint arXiv:2007.07481, 2020.

[Woodworth et al., 2020]
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro.
Minibatch vs local sgd for heterogeneous distributed learning.
In NeurIPS 2020 - Thirty-fourth Conference on Neural
Information Processing Systems, 2020a.

[Woodworth et al., 2020]
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins,
Brendan Mcmahan, Ohad Shamir, and Nathan Srebro.
Is local sgd better than minibatch sgd?
In International Conference on Machine Learning, pp.  10334–10343. PMLR, 2020b.

[Yao et al., 2020]
Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W. Mahoney.
Pyhessian: Neural networks through the lens of the hessian.
In Xintao Wu, Chris Jermaine, Li Xiong, Xiaohua Hu, Olivera Kotevska,
Siyuan Lu, Weija Xu, Srinivas Aluru, Chengxiang Zhai, Eyhab Al-Masri,
Zhiyuan Chen, and Jeff Saltz (eds.), IEEE International Conference on
Big Data, Big Data 2020, Atlanta, GA, USA, December 10-13, 2020, pp.  581–590. IEEE, 2020.
URL <https://doi.org/10.1109/BigData50022.2020.9378171>.

[Yin et al., 2020]
Dong Yin, Mehrdad Farajtabar, and Ang Li.
SOLA: continual learning with second-order loss approximation.
CoRR, abs/2006.10974, 2020a.
URL <https://arxiv.org/abs/2006.10974>.

[Yin et al., 2020]
Dong Yin, Mehrdad Farajtabar, Ang Li, Nir Levine, and Alex Mott.
Optimization and generalization of regularization-based continual
learning: a loss approximation viewpoint.
arXiv preprint arXiv:2006.10974, 2020b.

[Yoon et al., 2021]
Jaehong Yoon, Wonyong Jeong, Giwoong Lee, Eunho Yang, and Sung Ju Hwang.
Federated continual learning with weighted inter-client transfer.
In International Conference on Machine Learning, pp.  12073–12086. PMLR, 2021.

[Yurochkin et al., 2019]
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia
Hoang, and Yasaman Khazaeni.
Bayesian nonparametric federated learning of neural networks.
In International Conference on Machine Learning, pp.  7252–7261. PMLR, 2019.

[Zenke et al., 2017]
Friedemann Zenke, Ben Poole, and Surya Ganguli.
Continual learning through synaptic intelligence.
In International Conference on Machine Learning, pp.  3987–3995. PMLR, 2017.

[Zhang et al., 2019]
Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George E
Dahl, Christopher J Shallue, and Roger Grosse.
Which algorithmic choices matter at which batch sizes? insights from
a noisy quadratic model.
In Advances in Neural Information Processing Systems, 2019.

[Zinkevich et al., 2010]
Martin Zinkevich, Markus Weimer, Alexander J Smola, and Lihong Li.
Parallelized stochastic gradient descent.
In NIPS, volume 4, pp.  4. Citeseer, 2010.