# Optimal verification of entangled states with local measurements

Sam Pallister<EMAIL_ADDRESS>School of Mathematics, University
of Bristol, UK  Quantum Engineering Centre for Doctoral Training, University
of Bristol, UK  Noah Linden<EMAIL_ADDRESS>School of Mathematics,
University of Bristol, UK  Ashley Montanaro<EMAIL_ADDRESS>School of Mathematics, University of Bristol, UK

###### Abstract

Consider the task of verifying that a given quantum device, designed to
produce a particular entangled state, does indeed produce that state. One
natural approach would be to characterise the output state by quantum state
tomography; or alternatively to perform some kind of Bell test, tailored to
the state of interest. We show here that neither approach is optimal amongst
local verification strategies for two qubit states. We find the optimal
strategy in this case and show that quadratically fewer total measurements are
needed to verify to within a given fidelity than in published results for
quantum state tomography, Bell test, or fidelity estimation protocols. We also
give efficient verification protocols for any stabilizer state. Additionally,
we show that requiring that the strategy be constructed from local, non-
adaptive and non-collective measurements only incurs a constant-factor penalty
over a strategy without these restrictions.

Efficient and reliable quantum state preparation is a necessary step for all
quantum technologies. However, characterisation and verification of such
devices is typically a time-consuming and computationally difficult process.
For example, tomographic reconstruction of a state of 8 ions required taking
$\sim 650,000$ measurements over 10 hours, and a statistical analysis that
took far longer Häffner  _et al._ (2005); verification of a few-qubit photonic
state is similarly challenging Carolan  _et al._ (2014); Laing and O’Brien
(2012). This is also the case in tomography of continuous-variable systems
Lvovsky and Raymer (2009); Bellini  _et al._ (2012); Amosov  _et al._ (2012).
One may instead resort to non-tomographic methods to verify that a device
reliably outputs a particular state, but such methods typically either: (a)
assume that the output state is within some special family of states, for
example in compressed sensing Flammia  _et al._ (2012); Gross  _et al._ (2010)
or matrix product state tomography Cramer  _et al._ (2010); or (b) extract
only partial information about the state, such as when estimating entanglement
witnesses Tóth and Gühne (2005a, b).

Here, we derive the optimal local verification strategy for common entangled
states and compare its performance to bounds for non-adaptive quantum state
tomography in Sugiyama  _et al._ (2013) and the fidelity estimation protocol
in Flammia and Liu (2011). Specifically, we demonstrate non-adaptive
verification strategies for arbitrary two-qubit states and stabilizer states
of $N$ qubits that are constructed from local measurements, and require
quadratically fewer copies to verify to within a given fidelity than for these
previous protocols. Moreover, the requirement that the measurements be local
incurs only a constant factor penalty over the best non-local strategy, even
if collective and adaptive measurements are allowed.

## Premise.

Colloquially, a quantum state verification protocol is a procedure for gaining
confidence that the output of some device is a particular state over any
other. However, for any scheme involving measurements on a finite number of
copies of the output state, one can always find an alternative state within
some sufficiently small distance that is guaranteed to fool the verifier.
Furthermore, the outcomes of measurements are, in general, probabilistic and a
verification protocol collects a finite amount of data; and so any statement
about verification can only be made up to some finite statistical confidence.
The only meaningful statement to make in this context is the statistical
inference that the state output from a device sits within a ball of a certain
small radius (given some metric) of the correct state, with some statistical
confidence. Thus the outcome of a state verification protocol is a statement
like: “the device outputs copies of a state that has $99\%$ fidelity with the
target, with $90\%$ probability”. Note that this is different to the setting
of state tomography; a verification protocol answers the question: “Is the
state ${|{\psi}\rangle}?$” rather than the more involved tomographic question:
“Which state do I have?”. Hence, unlike tomography, a verification protocol
may give no information about the true state if the protocol fails.

We now outline the framework for verification protocols that we consider. Take
a verifier with access to some set of allowed measurements, and a device that
produces states $\sigma_{1},\sigma_{2},\ldots\sigma_{n}$ which are supposed to
all be ${|{\psi}\rangle}$, but may in practice be different from
${|{\psi}\rangle}$ or each other. We have the promise that either
$\sigma_{i}={|{\psi}\rangle}\\!{\langle{\psi}|}$ for all $i$, or
${\langle{\psi}|}\sigma_{i}{|{\psi}\rangle}\leq 1-\epsilon$ for all $i$. The
verifier must determine which is the case with worst-case failure probability
$\delta$.

The protocol proceeds as follows. For each $\sigma_{i}$, the verifier randomly
draws a binary-outcome projective measurement $\\{P_{j},\mathds{1}-P_{j}\\}$
from a prespecified set $\mathcal{S}$ with some probability $\mu^{i}_{j}$.
Label the outcomes “pass” and “fail”; in a “pass” instance the verifier
continues to state $\sigma_{i+1}$, otherwise the protocol ends and the
verifier concludes that the state was not ${|{\psi}\rangle}$. If the protocol
passes on all $n$ states, then the verifier concludes that the state was
${|{\psi}\rangle}$. We impose the constraint that every $P_{j}\in\mathcal{S}$
_always_ accepts when $\sigma_{i}={|{\psi}\rangle}\\!{\langle{\psi}|}$,
$\forall i$ (i.e. that ${|{\psi}\rangle}$ is in the “pass” eigenspace of every
projector $P_{j}\in\mathcal{S}$). This may seem a prohibitively strong
constraint, but we later demonstrate that it is both achievable for the sets
of states we consider and is always asymptotically favourable to the verifier.

The maximal probability that the verifier passes on copy $i$ is

$\text{Pr}[\text{Pass on copy }i]=\max_{\begin{subarray}{c}\sigma\\\
{\langle{\psi}|}\sigma{|{\psi}\rangle}\leq
1-\epsilon\end{subarray}}\operatorname{tr}(\Omega_{i}\sigma),$ (1)

where $\Omega_{i}=\sum_{j}\mu_{j}^{i}P_{j}$. However, the verifier seeks to
minimise this quantity for each $\Omega_{i}$ and hence it suffices to take a
fixed set of probabilities and projectors $\\{\mu_{j},P_{j}\\}$, independent
of $i$. Then the verifier-adversary optimisation is

$\min_{\Omega}\max_{\begin{subarray}{c}\sigma\\\
{\langle{\psi}|}\sigma{|{\psi}\rangle}\leq
1-\epsilon\end{subarray}}\operatorname{tr}(\Omega\sigma)\coloneqq
1-\Delta_{\epsilon},$ (2)

where $\Omega=\sum_{j}\mu_{j}P_{j}$. We call $\Omega$ a strategy.
$\Delta_{\epsilon}$ is the expected probability that the state $\sigma$ fails
a single measurement. Then the maximal worst-case probability that the
verifier fails to detect that we are in the “bad” case that
${\langle{\psi}|}\sigma_{i}{|{\psi}\rangle}\leq 1-\epsilon$ for all $i$ is
$(1-\Delta_{\epsilon})^{n}$, so to achieve confidence $1-\delta$ it is
sufficient to take

$n\geq\frac{\ln\delta^{-1}}{\ln((1-\Delta_{\epsilon})^{-1})}\approx\frac{1}{\Delta_{\epsilon}}\ln\delta^{-1}.$
(3)

Protocols of this form satisfy some useful operational properties:

  1. A.

_Non-adaptivity_. The strategy is fixed from the outset and depends only on
the mathematical description of ${|{\psi}\rangle}$, rather than the choices of
any prior measurements or their measurement outcomes.

  2. B.

_Future-proofing_. The strategy is independent of the infidelity $\epsilon$,
and gives a viable strategy for any choice of $\epsilon$. Thus an
experimentalist is able to arbitrarily decrease the infidelity $\epsilon$
within which verification succeeds by simply taking more total measurements
following the strategy prescription, rather than modifying the prescription
itself. The experimentalist is free to choose an arbitrary $\epsilon>0$ and be
guaranteed that the strategy still works in verifying ${|{\psi}\rangle}$.

One may consider more general non-adaptive verification protocols given
$\mathcal{S}$ and $\\{\sigma_{i}\\}$, where measurements do not output “pass”
with certainty given input ${|{\psi}\rangle}$, and the overall determination
of whether to accept or reject is based on a more complicated estimator built
from the relative frequency of “pass” and “fail” outcomes. However, we show in
the Supplemental Material that these strategies require, asymptotically,
quadratically more measurements in $\epsilon$ than those where
${|{\psi}\rangle}$ is always accepted. We will also see that the protocol
outlined above achieves the same scaling with $\epsilon$ and $\delta$ as the
globally optimal strategy, up to a constant factor, and so any other strategy
(even based on non-local, adaptive or collective measurements) would yield
only at most constant-factor improvements.

Given no constraints on the verifier’s measurement prescription, the optimal
strategy is to just project on to ${|{\psi}\rangle}$. In this case, the fewest
number of measurements needed to verify to confidence $1-\delta$ and fidelity
$1-\epsilon$ is
$n_{opt}=\frac{-1}{\ln\left(1-\epsilon\right)}\ln\frac{1}{\delta}\approx\frac{1}{\epsilon}\ln\frac{1}{\delta}$
(see the Supplemental Material). However, in general the projector
${|{\psi}\rangle}\\!{\langle{\psi}|}$ will be non-local, which has the
disadvantage of being harder to implement experimentally. This is particularly
problematic in quantum optics, for example, where deterministic, unambiguous
discrimination of a complete set of Bell states is impossible Vaidman and
Yoran (1999); Calsamiglia and Lütkenhaus (2001); Ewert and van Loock (2014).
Thus, for each copy there is a fixed probability of the measurement returning
a “null” outcome; hence, regardless of the optimality of the verification
strategy, merely the probability of its successful operation decreases
exponentially with the number of measurements. Instead, we seek optimal
measurement strategies that satisfy some natural properties that make them
both physically realisable and useful to a real-world verifier. We impose the
following properties:

  1. 1.

_Locality_. $\mathcal{S}$ contains only measurements corresponding to local
observables, acting on a single copy of the output state.

  2. 2.

_Projective measurement_. $\mathcal{S}$ contains only binary-outcome,
projective measurements, rather than more elaborate POVMs.

  3. 3.

_Trust_. The physical operation of each measurement device is faithful to its
mathematical description; it behaves as expected, without experimental error.

Thus for multipartite states we only consider strategies where each party
locally performs a projective measurement on a single copy, and the parties
accept or reject based on their collective measurement outcomes. We also
highlight the trust requirement to distinguish from self-testing protocols
Mayers and Yao (2004); McKague  _et al._ (2012); Yang and Navascués (2013).

Given this prescription and the set of physically-motivated restrictions, we
now derive the optimal verification strategy for some important classes of
states. To illustrate our approach, we start with the case of a Bell state
before generalising to larger classes of states.

## Bell state verification.

Consider the case of verifying the Bell state
${|{\Phi^{+}}\rangle}=\frac{1}{\sqrt{2}}({|{00}\rangle}+{|{11}\rangle})$. If
we maintain a strategy where all measurements accept ${|{\Phi^{+}}\rangle}$
with certainty, then it must be the case that
$\Omega{|{\Phi^{+}}\rangle}={|{\Phi^{+}}\rangle}$. The optimisation problem
for the verifier-adversary pair is then given by $\Delta_{\epsilon}$:

$\Delta_{\epsilon}=\max_{\Omega}\min_{\begin{subarray}{c}\sigma\\\
{\langle{\psi}|}\sigma{|{\psi}\rangle}\leq
1-\epsilon\end{subarray}}\operatorname{tr}[\Omega({|{\Phi^{+}}\rangle}\\!{\langle{\Phi^{+}}|}-\sigma)].$
(4)

However, we show in the Supplemental Material that it is never beneficial for
the adversary to: (a) choose a non-pure $\sigma$; or (b) to pick a $\sigma$
such that ${\langle{\psi}|}\sigma{|{\psi}\rangle}<1-\epsilon$. Rewrite
$\sigma={|{\psi_{\epsilon}}\rangle}\\!{\langle{\psi_{\epsilon}}|}$, where
${|{\psi_{\epsilon}}\rangle}=\sqrt{1-\epsilon}{|{\Phi^{+}}\rangle}+\sqrt{\epsilon}{|{\psi^{\bot}}\rangle}$
for some state ${|{\psi^{\bot}}\rangle}$ such that
$\braket{\Phi^{+}}{\psi^{\bot}}=0$. Then,

$\displaystyle\Delta_{\epsilon}$
$\displaystyle=\max_{\Omega}\min_{{|{\psi^{\bot}}\rangle}}\epsilon({\langle{\Phi^{+}}|}\Omega{|{\Phi^{+}}\rangle}-{\langle{\psi^{\bot}}|}\Omega{|{\psi^{\bot}}\rangle})$
$\displaystyle-2\sqrt{\epsilon(1-\epsilon)}\text{Re}{\langle{\Phi^{+}}|}\Omega{|{\psi^{\bot}}\rangle}.$
(5)

Given that $\Omega{|{\Phi^{+}}\rangle}={|{\Phi^{+}}\rangle}$, we can simplify
by noting that ${\langle{\Phi^{+}}|}\Omega{|{\Phi^{+}}\rangle}=1$ and
${\langle{\Phi^{+}}|}\Omega{|{\psi^{\bot}}\rangle}=0$. Thus,

$\displaystyle\Delta_{\epsilon}$
$\displaystyle=\max_{\Omega}\min_{{|{\psi^{\bot}}\rangle}}\epsilon(1-{\langle{\psi^{\bot}}|}\Omega{|{\psi^{\bot}}\rangle})$
$\displaystyle=\epsilon(1-\min_{\Omega}\max_{{|{\psi^{\bot}}\rangle}}{\langle{\psi^{\bot}}|}\Omega{|{\psi^{\bot}}\rangle}),$
(6)

where the verifier controls $\Omega$ and the adversary controls
${|{\psi^{\bot}}\rangle}$. Given that ${|{\Phi^{+}}\rangle}$ is itself an
eigenstate of $\Omega$, the worst-case scenario for the verifier is for the
adversary to choose ${|{\psi^{\bot}}\rangle}$ as the eigenstate of $\Omega$
with the next largest eigenvalue. If we diagonalise $\Omega$ we can write
$\Omega={|{\Phi^{+}}\rangle}\\!{\langle{\Phi^{+}}|}+\sum_{j=1}^{3}\nu_{j}{|{\psi^{\bot}_{j}}\rangle}\\!{\langle{\psi^{\bot}_{j}}|}$,
where $\braket{\Phi^{+}}{\psi^{\bot}_{j}}=0\;\forall j$. The adversary picks
the state ${|{\psi^{\bot}_{\text{max}}}\rangle}$ with corresponding eigenvalue
$\nu_{\text{max}}=\max_{j}\nu_{j}$. Now, consider the trace of $\Omega$: if
$\operatorname{tr}(\Omega)<2$ then the strategy must be a convex combination
of local projectors, at least one of which is rank 1. However, the only rank 1
projector that satisfies $P^{+}{|{\Phi^{+}}\rangle}={|{\Phi^{+}}\rangle}$ is
$P^{+}={|{\Phi^{+}}\rangle}\\!{\langle{\Phi^{+}}|}$, which is non-local; and
therefore $\operatorname{tr}(\Omega)\geq 2$. Combining this with the
expression for $\Omega$ above gives
$\operatorname{tr}(\Omega)=1+\sum_{j}\nu_{j}\geq 2$. It is always beneficial
to the verifier to saturate this inequality, as any extra weight on the
subspace orthogonal to ${|{\Phi^{+}}\rangle}$ can only increase the chance of
being fooled by the adversary. Thus the verifier is left with the optimisation

$\min\nu_{\text{max}}=\min\max_{k}\nu_{k},\quad\sum_{k}\nu_{k}=1.$ (7)

This expression is optimised for $\nu_{j}=\frac{1}{3},j=1,2,3$. In this case,
$\Omega=\frac{\mathds{1}}{3}$ on the subspace orthogonal to the state
${|{\Phi^{+}}\rangle}$. Then we can rewrite $\Omega$ as

$\Omega=\frac{1}{3}(P^{+}_{XX}+P^{+}_{-YY}+P^{+}_{ZZ}),$ (8)

where $P^{+}_{XX}$ is the projector onto the positive eigensubspace of the
tensor product of Pauli matrices $XX$ (and likewise for $-YY$ and $ZZ$). The
operational interpretation of this optimal strategy is then explicit: for each
copy of the state, the verifier randomly chooses a measurement setting from
the set $\\{XX,-YY,ZZ\\}$ all with probability $\frac{1}{3}$, and accepts only
on receipt of outcome “+1” on all $n$ measurements. Note that we could expand
$\Omega$ differently, for example by conjugating each term in the above
expression by any local operator that leaves ${|{\Phi^{+}}\rangle}$ alone; the
decomposition above is only one of a family of optimal strategies. As for
scaling, we know that
$\Delta_{\epsilon}=\epsilon(1-\nu_{\text{max}})=\frac{2\epsilon}{3}$, and the
number of measurements needed to verify the Bell state ${|{\Phi^{+}}\rangle}$
is then
$n_{opt}=\left[\ln\left(\frac{3}{3-2\epsilon}\right)\right]^{-1}\ln{\frac{1}{\delta}}\approx\frac{3}{2\epsilon}\ln\frac{1}{\delta}$.
Note that this is only worse than the optimal non-local strategy by a factor
of $1.5$.

In comparison, consider instead verifying a Bell state by performing a CHSH
test. Then even in the case of trusted measurements, the total number of
measurements scales like $O\left(\frac{1}{\epsilon^{2}}\right)$ Sugiyama
(2014), which is quadratically worse than the case of measuring the
stabilizers $\\{XX,-YY,ZZ\\}$. This suboptimal scaling is shared by the known
bounds for non-adaptive quantum state tomography with single-copy measurements
in Sugiyama  _et al._ (2013) and fidelity estimation in Flammia and Liu
(2011). See da Silva  _et al._ (2011); Ferrie and Blume-Kohout (2016);
Struchalin  _et al._ (2016) for further discussion of this scaling in
tomography. Additionally, two-qubit tomography potentially requires five times
as many measurement settings. We also note that a similar quadratic
improvement was derived in adaptive quantum state tomography in Mahler  _et
al._ (2013), in the sample-optimal tomographic scheme in Haah  _et al._ (2016)
and in the quantum state certification scheme in Bădescu  _et al._ (2017);
however, the schemes therein assume access to either non-local or collective
measurements.

## Arbitrary states of two qubits.

The goal is unchanged for other pure states of two qubits: we seek strategies
that accept the target state with certainty, and hence achieve the asymptotic
advantage outlined for Bell states above. It is not clear a priori that such a
strategy exists for general states, in a way that is as straightforward as the
previous construction. However, we show that for any two-qubit state not only
does such a strategy exist, but we can optimise within the family of allowable
strategies and give an analytic expression with optimal constant factors.

We first remark that we can restrict to states of the form
${|{\psi_{\theta}}\rangle}=\sin\theta{|{00}\rangle}+\cos\theta{|{11}\rangle}$
without loss of generality, as any state is locally equivalent to a state of
this form, for some $\theta$. Specifically, given any two qubit state
${|{\psi}\rangle}$ with optimal strategy $\Omega_{opt}$, a locally equivalent
state $(U\otimes V){|{\psi}\rangle}$ has optimal strategy $(U\otimes
V)\Omega_{opt}(U\otimes V)^{\dagger}$. The proof of this statement can be
found in the Supplemental Material. Given the restriction to this family of
states, we can now write down an optimal verification protocol.

Figure 1: The number of measurements needed to verify the state
$\Ket{\psi_{\theta}}=\sin\theta\Ket{00}+\cos\theta\Ket{11}$, as a function of
$\theta$, using the optimal strategy. See Eq. 10. Here, $1-\epsilon=0.99$ and
$1-\delta=0.9$.

Figure 2: A comparison of the total number of measurements required to verify
to fidelity $1-\epsilon$ for the strategy derived here, versus the known
bounds for estimation up to fidelity $1-\epsilon$ using non-adaptive
tomography in Sugiyama  _et al._ (2013) and the fidelity estimation protocol
in Flammia and Liu (2011), and the globally optimal strategy given by
projecting onto $\Ket{\psi}$. Here, $1-\delta=0.9$ and $\theta=\frac{\pi}{8}$.

######  Theorem 1.

Any optimal strategy for verifying a state of the form
${|{\psi_{\theta}}\rangle}=\sin\theta{|{00}\rangle}+\cos\theta{|{11}\rangle}$
for $0<\theta<\frac{\pi}{2}$, $\theta\neq\frac{\pi}{4}$ that accepts
${|{\psi_{\theta}}\rangle}$ with certainty and satisfies the properties of
locality, trust and projective measurement, can be expressed as a strategy
involving four measurement settings:

$\displaystyle\Omega_{opt}$ $\displaystyle=\alpha(\theta)P^{+}_{ZZ}$
$\displaystyle+\frac{1-\alpha(\theta)}{3}\sum_{k=1}^{3}\left[\mathds{1}-({|{u_{k}}\rangle}\otimes{|{v_{k}}\rangle})({\langle{u_{k}}|}\otimes{\langle{v_{k}}|})\right],$
for $\displaystyle\alpha(\theta)=\frac{2-\sin(2\theta)}{4+\sin(2\theta)},$ (9)

where $P^{+}_{ZZ}$ is the projector onto the positive eigenspace of the Pauli
operator $ZZ$, and the sets of states $\\{{|{u_{k}}\rangle}\\}$ and
$\\{{|{v_{k}}\rangle}\\}$ are written explicitly in the Supplemental Material.
The number of measurements needed to verify to within infidelity $\epsilon$
and with power $1-\delta$ satisfies

$n_{opt}\approx(2+\sin\theta\cos\theta)\epsilon^{-1}\ln\delta^{-1}.$ (10)

The proof of this theorem is included in the Supplemental Material. Note that
the special cases for ${|{\psi_{\theta}}\rangle}$ where $\theta=0$,
$\theta=\frac{\pi}{2}$ and $\theta=\frac{\pi}{4}$ are omitted from this
theorem. In these cases, ${|{\psi_{\theta}}\rangle}$ admits a wider choice of
measurements that accept with certainty. We have already treated the Bell
state case $\theta=\frac{\pi}{4}$ above. In the other two cases, the state
${|{\psi_{\theta}}\rangle}$ is product and hence the globally optimal
measurement, just projecting onto ${|{\psi_{\theta}}\rangle}$, is a valid
local strategy. We note that this leads to a discontinuity in the number of
measurements needed as a function of $\theta$, for fixed $\epsilon$ (as seen
in Fig. 2). This arises since our strategies are designed to have the optimal
scaling $\left(O\left(\frac{1}{\epsilon}\right)\right)$ for fixed $\theta$,
achieved by having strategies that accept ${|{\psi}\rangle}$ with probability
$1$.

As for scaling, in Fig. 2 the number of measurements required to verify a
particular two-qubit state of this form, for three protocols, is shown. The
optimal protocol derived here gives a marked improvement over the previously
published bounds for both tomography Sugiyama  _et al._ (2013) and fidelity
estimation Flammia and Liu (2011) for the full range of $\epsilon$, for the
given values of $\theta$ and $\delta$. The asymptotic nature of the advantage
for the protocol described here implies that the gap between the optimal
scheme and tomography only grows as the requirement on $\epsilon$ becomes more
stringent. Note also that the optimal local strategy is only marginally worse
than the best possible strategy of just projecting onto ${|{\psi}\rangle}$.

## Stabilizer states.

Additionally, it is shown in the Supplemental Material that we can construct a
strategy with the same asymptotic advantage for any stabilizer state, by
drawing measurements from the stabilizer group (where now we only claim
optimality up to constant factors). The derivation is analogous to that for
the Bell state above, and given that the Bell state is itself a stabilizer
state, the strategy above is a special case of the stabilizer strategy
discussed below. For a state of $N$ qubits, a viable strategy constructed from
stabilizers must consist of at least the $N$ stabilizer generators of
${|{\psi}\rangle}$. This is because a set of $k<N$ stabilizers stabilizes a
subspace of dimension at least $2^{N-k}$, and so in this case there always
exists at least one orthogonal state to ${|{\psi}\rangle}$ accessible to the
adversary that fools the verifier with certainty. In this minimal case, the
number of required measurements is $n_{opt}^{s.g.}\approx
N\epsilon^{-1}\ln\delta^{-1}$, with this bound saturated by measuring all
stabilizer generators with equal weight. Conversely, constructing a
measurement strategy from the full set of $2^{N}-1$ linearly independent
stabilizers requires a number of measurements
$n_{opt}^{stab}\approx\frac{2^{N}-1}{2^{(N-1)}}\epsilon^{-1}\ln\delta^{-1}$,
again with this bound saturated by measuring each stabilizer with equal
weight. For growing $N$, the latter expression for the number of measurements
is bounded from above by $2\epsilon^{-1}\ln\delta^{-1}$, which implies that
there is a local strategy for any stabilizer state, of an arbitrary number of
qubits, which requires at most twice as many measurements as the optimal non-
local strategy. Note that this strategy may not be exactly optimal; for
example, the state ${|{00}\rangle}$ is also a stabilizer state, and in this
case applying the measurement ${|{00}\rangle}\\!{\langle{00}|}$ is both
locally implementable and provably optimal. Thus, the exactly optimal strategy
may depend more precisely on the structure of the individual state itself.
However, the stabilizer strategy is only inferior by a small constant factor.
In comparison to the latter strategy constructed from every stabilizer, the
former strategy constructed from only the $N$ stabilizer generators of
${|{\psi}\rangle}$ has scaling that grows linearly with $N$. Thus there is
ultimately a trade-off between number of measurement settings and total number
of measurements required to verify within a fixed fidelity.

In principle, the recipe derived here to extract the optimal strategy for a
state of two qubits can be applied to any pure state. However, we anticipate
that deriving this strategy, including correct constants, may be somewhat
involved (both analytically and numerically) for states of greater numbers of
qubits.

Following the completion of this work, we became aware of Dimić and Dakić
(2017) which, among other results, applies a similar protocol to the Bell
state verification strategy in the context of entanglement detection.

###### Acknowledgements.

The authors thank Jeremy Adcock, Sam Morley-Short, Tony Short and Chris
Sparrow for helpful discussions, and thank Borivoje Dakic for pointing out
Dimić and Dakić (2017). SP was supported by the Bristol Quantum Engineering
Centre for Doctoral Training, EPSRC grant EP/L015730/1. AM was supported by
EPSRC Early Career Fellowship EP/L021005/1. No new data were created during
this study.

## References

  * Häffner  _et al._ (2005) H. Häffner, W. Hänsel, C. F. Roos, J. Benhelm, D. Chek-al Kar, M. Chwalla, T. Körber, U. D. Rapol, M. Riebe, P. O. Schmidt, C. Becher, O. Gühne, W. Dür, and R. Blatt, Nature 438, 643 (2005).
  * Carolan  _et al._ (2014) J. Carolan, J. D. A. Meinecke, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, Nature Photonics 8, 621 (2014).
  * Laing and O’Brien (2012) A. Laing and J. L. O’Brien, arXiv:1208.2868 (2012).
  * Lvovsky and Raymer (2009) A. I. Lvovsky and M. G. Raymer, Reviews of Modern Physics 81, 299 (2009).
  * Bellini  _et al._ (2012) M. Bellini, A. S. Coelho, S. N. Filippov, V. I. Man’ko, and A. Zavatta, Physical Review A 85, 052129 (2012).
  * Amosov  _et al._ (2012) G. G. Amosov, Y. A. Korennoy, and V. I. Man’ko, Physical Review A 85, 052119 (2012).
  * Flammia  _et al._ (2012) S. T. Flammia, D. Gross, Y.-K. Liu, and J. Eisert, New Journal of Physics 14, 095022 (2012).
  * Gross  _et al._ (2010) D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert, Physical Review Letters 105, 150401 (2010).
  * Cramer  _et al._ (2010) M. Cramer, M. B. Plenio, S. T. Flammia, R. Somma, D. Gross, S. D. Bartlett, O. Landon-Cardinal, D. Poulin, and Y.-K. Liu, Nature Communications 1, 149 (2010).
  * Tóth and Gühne (2005a) G. Tóth and O. Gühne, Physical Review Letters 94, 060501 (2005a).
  * Tóth and Gühne (2005b) G. Tóth and O. Gühne, Physical Review A 72, 022340 (2005b).
  * Sugiyama  _et al._ (2013) T. Sugiyama, P. S. Turner, and M. Murao, Physical Review Letters 111, 160406 (2013).
  * Flammia and Liu (2011) S. T. Flammia and Y.-K. Liu, Physical Review Letters 106, 230501 (2011).
  * Vaidman and Yoran (1999) L. Vaidman and N. Yoran, Physical Review A 59, 116 (1999).
  * Calsamiglia and Lütkenhaus (2001) J. Calsamiglia and N. Lütkenhaus, Applied Physics B 72, 67 (2001).
  * Ewert and van Loock (2014) F. Ewert and P. van Loock, Physical Review Letters 113, 140403 (2014).
  * Mayers and Yao (2004) D. Mayers and A. Yao, Quantum Information & Computation 4, 273 (2004).
  * McKague  _et al._ (2012) M. McKague, T. H. Yang, and V. Scarani, Journal of Physics A: Mathematical and Theoretical 45, 455304 (2012).
  * Yang and Navascués (2013) T. H. Yang and M. Navascués, Physical Review A 87, 050102 (2013).
  * Sugiyama (2014) T. Sugiyama,  _Finite Sample Analysis in Quantum Estimation_ (Springer, 2014).
  * da Silva  _et al._ (2011) M. P. da Silva, O. Landon-Cardinal, and D. Poulin, Physical Review Letters 107, 210404 (2011).
  * Ferrie and Blume-Kohout (2016) C. Ferrie and R. Blume-Kohout, Physical Review Letters 116, 090407 (2016).
  * Struchalin  _et al._ (2016) G. I. Struchalin, I. A. Pogorelov, S. S. Straupe, K. S. Kravtsov, I. V. Radchenko, and S. P. Kulik, Physical Review A 93, 012103 (2016).
  * Mahler  _et al._ (2013) D. H. Mahler, L. A. Rozema, A. Darabi, C. Ferrie, R. Blume-Kohout, and A. M. Steinberg, Physical Review Letters 111, 183601 (2013).
  * Haah  _et al._ (2016) J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu, in  _Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016_ (ACM Press, New York, New York, USA, 2016) pp. 913–925.
  * Bădescu  _et al._ (2017) C. Bădescu, R. O’Donnell, and J. Wright, arXiv:1708.06002 (2017).
  * Dimić and Dakić (2017) A. Dimić and B. Dakić, arXiv:1705.06719 (2017).
  * Gottesman (1997) D. Gottesman,  _Stabilizer Codes and Quantum Error Correction_ , Ph.D. thesis, Caltech (1997).
  * Gottesman (1996) D. Gottesman, Physical Review A 54, 1862 (1996).
  * Nielsen and Chuang (2010) M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (Cambridge University Press, 2010) p. 676.
  * Hein (2005) M. Hein,  _Entanglement in graph states_ , Ph.D. thesis, University of Innsbruck (2005).
  * Cover and Thomas (2006) T. M. Cover and J. A. Thomas,  _Elements of Information Theory_ (Wiley-Interscience, 2006).

Supplemental Material: Optimal verification of entangled states with local
measurements

The contents of the following supplemental material are as follows: in
Appendix A, we set up a formal framework for state verification protocols. In
Appendix B we simplify the form of the protocol using the set of physically-
motivated strategy requirements outlined in the main body. Appendix C is
concerned with deriving the optimal strategy for states of two qubits, in
particular proving Theorem 1; and in Appendix D we derive efficient
verification strategies for stabilizer states. Finally, Appendix E outlines
the hypothesis testing framework necessary for this paper.

##  Appendix A Quantum state verification

We first set up a formal framework for general state verification protocols.
We assume that we have access to a device $\mathcal{D}$ that is supposed to
produce copies of a state ${|{\psi}\rangle}$. However, $\mathcal{D}$ might not
work correctly, and actually produces (potentially mixed) states
$\sigma_{1},\sigma_{2},\dots$ such that $\sigma_{i}$ might not be equal to
${|{\psi}\rangle}\\!{\langle{\psi}|}$. In order to distinguish this from the
case where the device works correctly by making a reasonable number of uses of
$\mathcal{D}$, we need to have a promise that these states are sufficiently
far from ${|{\psi}\rangle}$. So we are led to the following formulation of our
task:

Distinguish between the following two cases:

  1. (a).

(Good) $\sigma_{i}={|{\psi}\rangle}\\!{\langle{\psi}|}$ for all $i$;

  2. (b).

(Bad) For some fixed $\epsilon$,
$F({|{\psi}\rangle},\sigma_{i}):=\braket{\psi}{\sigma_{i}}{\psi}\leq
1-\epsilon$ for all $i$.

Given a verifier with access to a set of available measurements $\mathcal{S}$,
the protocols we consider for completing this task are of the following form:

Protocol Quantum state verification

1:for $i=1$ to $n$ do

2: Two-outcome measurement $M_{i}\in\mathcal{S}$ on $\sigma_{i}$, where
$M_{i}$’s outcomes are associated with “pass” and “fail”

3: if “fail” is returned then

4: Output “reject”

5:Output “accept”

We impose the conditions that in the good case, the protocol accepts with
certainty, whereas in the bad case, the protocol accepts with probability at
most $\delta$; we call $1-\delta$ the _statistical power_ of the protocol. We
then aim to find a protocol that minimises $n$ for a given choice of
${|{\psi}\rangle}$, $\epsilon$ and $\mathcal{S}$, such that these constraints
are satisfied. Insisting that the protocol accepts in the good case with
certainty implies that all measurements in $\mathcal{S}$ are guaranteed to
pass in this case. This is a desirable property in itself, but one could
consider more general non-adaptive protocols where measurements do not output
“pass” with certainty on ${|{\psi}\rangle}$, and the protocol determines
whether to accept based on an estimator constructed from the relative
frequency of “pass” and “fail” outcomes across all $n$ copies. We show in
Appendix E that this class of protocols has quadratically worse scaling in
$\epsilon$ than protocols where each measurement passes with certainty on
${|{\psi}\rangle}$.

We make the following observations about this framework:

  1. 1.

Given no restrictions on $M_{i}$, the optimal protocol is simply for each
measurement to project onto ${|{\psi}\rangle}$. In fact, this remains optimal
even over the class of more general protocols making use of adaptivity or
collective measurements. One can see this as follows: if a two-outcome
measurement $M$ (corresponding to the whole protocol) is described by
measurement operators $P$ (accept) and $I-P$ (reject), then if $M$ accepts
${|{\psi}\rangle}^{\otimes n}$ with certainty, we must have
$P={|{\psi}\rangle}\\!{\langle{\psi}|}^{\otimes n}+P^{\prime}$ for some
residual positive semidefinite operator $P^{\prime}$. Then replacing $P$ with
${|{\psi}\rangle}\\!{\langle{\psi}|}^{\otimes n}$ gives at least as good a
protocol, as the probability of accepting ${|{\psi}\rangle}$ remains 1, while
the probability of accepting other states cannot increase.

The probability of acceptance in the bad case after $n$ trials is then at most
$(1-\epsilon)^{n}$, so it is sufficient to take

$n\geq\frac{\ln\delta^{-1}}{\ln((1-\epsilon)^{-1})}\approx\epsilon^{-1}\ln\delta^{-1}$
(S1)

to achieve statistical power $1-\delta$. This will be the yardstick against
which we will compare our more restricted protocols below.

  2. 2.

We assume that the states $\sigma_{i}$ are independently and adversarially
chosen. This implies that if (as we will consider below) $\mathcal{S}$
contains only projective measurements and does not contain the measurement
projecting onto ${|{\psi}\rangle}\\!{\langle{\psi}|}$, it is necessary to
choose the measurement $M_{i}$ at random from $\mathcal{S}$ and unknown to the
adversary. Otherwise, we could be fooled with certainty by the adversary
choosing $\sigma_{i}$ to have support only in the “pass” eigenspace of $M_{i}$
for each copy $i$.

  3. 3.

We can be explicit about the optimisation needed to derive the optimal
protocol in this adversarial setting. As protocols of the above form reject
whenever a measurement fails, the adversary’s goal at the $i$’th step is to
maximise the probability that the measurement $M_{i}$ at that step passes on
$\sigma_{i}$. If the $j$’th measurement setting in $\mathcal{S}$, $M^{j}$, is
picked from $\mathcal{S}$ at step $i$ with probability $\mu_{j}^{i}$, the
largest possible overall probability of passing for copy $i$ is

$\text{Pr}[\text{Pass on copy
}i]=\max_{\sigma_{i},\braket{\psi}{\sigma_{i}}{\psi}\leq
1-\epsilon}\sum_{j}\mu^{i}_{j}\operatorname{tr}(P_{j}\sigma_{i}),$ (S2)

where we denote the corresponding “pass” projectors $P_{j}$. We can write
$\Omega_{i}=\sum_{j}\mu_{j}^{i}P_{j}$, and then

$\text{Pr}[\text{Pass on copy }i]=\max_{\sigma,\braket{\psi}{\sigma}{\psi}\leq
1-\epsilon}\operatorname{tr}(\Omega_{i}\sigma).$ (S3)

As the verifier, we wish to minimise this expression over all $\Omega_{i}$, so
we end up with a final expression that does not depend on $i$. This leads us
to infer that optimal protocols of this form can be assumed to be non-adaptive
in two senses: they do not depend on the outcome of previous measurements
(which is clear, as the protocol rejects if it ever sees a “fail” outcome);
and they also do not depend on the measurement choices made previously.

Therefore, in order to find an optimal verification protocol, our task is to
determine

$\min_{\Omega}\max_{\sigma,\braket{\psi}{\sigma}{\psi}\leq
1-\epsilon}\operatorname{tr}(\Omega\sigma),$ (S4)

where $\Omega$ is an operator of the form $\Omega=\sum_{j}\mu_{j}P_{j}$ for
$P_{j}\in\mathcal{S}$ and some probability $\mu_{j}$. We call such operators
strategies. If $\mathcal{S}$ contained all measurement operators (or even all
projectors), $\Omega$ would be an arbitrary operator satisfying
$0\leq\Omega\leq I$. However, this notion becomes nontrivial when one
considers restrictions on $\mathcal{S}$. Here, we focus on the experimentally
motivated case where $\mathcal{S}$ contains only projective measurements that
can be implemented via local operations and classical postprocessing.

  4. 4.

In a non-adversarial scenario, it may be acceptable to fix the measurements in
$\Omega$ in advance, with appropriate frequencies $\mu_{j}$. Then, given $n$,
a strategy $\Omega=\sum_{j}\mu_{j}P_{j}$ corresponds to a protocol where for
each $j$ we deterministically make $\mu_{j}n$ measurements
$\\{P_{j},I-P_{j}\\}$. For large $n$, and fixed $\sigma_{i}=\sigma$, this will
achieve similar performance to the above protocol.

  5. 5.

More complicated protocols with adaptive or collective measurements, or
measurements with more than two outcomes, cannot markedly improve on the
strategies derived here. We do not treat these more general strategies
explicitly, but note that the protocols we will describe based on local
projective measurements already achieve the globally optimal bound (S1) up to
constant factors, so any gain from these more complex approaches would be
minor.

##  Appendix B Verification strategy optimisation

In this appendix, we simplify the form of the optimisation in S4 using the
strategy requirements outlined previously. We start by making the following
useful observation:

######  Lemma 2.

We can assume without loss of generality that, in (S4), $\sigma$ is pure.

###### Proof.

Assume the adversary chooses a fixed density matrix $\sigma$, which is
globally optimal: it forces the verifier to accept $\sigma$ with the greatest
probability among states $\sigma$ such that
$\braket{\psi}{\sigma}{\psi}\coloneqq r\leq 1-\epsilon$. The probability of
accepting this $\sigma$ given strategy $\Omega$ is then

$\Pr[\text{Accept }\sigma]=\operatorname{tr}(\Omega\sigma).$ (S5)

We have asserted that $\Omega$ accepts ${|{\psi}\rangle}$ with certainty:
${\langle{\psi}|}\Omega{|{\psi}\rangle}=1$. However, for this to be the case
$\Omega$ must have ${|{\psi}\rangle}$ as an eigenstate with eigenvalue $1$;
thus we can write

$\Omega={|{\psi}\rangle}\\!{\langle{\psi}|}+\sum_{j}c_{j}{|{\psi^{\bot}_{j}}\rangle}\\!{\langle{\psi^{\bot}_{j}}|}$
(S6)

where the states $\\{{|{\psi^{\bot}_{j}}\rangle}\\}$ are a set of mutually
orthogonal states orthogonal to ${|{\psi}\rangle}$. Then

$\displaystyle\Pr[\text{Accept }\sigma]$
$\displaystyle={\langle{\psi}|}\sigma{|{\psi}\rangle}+\sum_{j}c_{j}{\langle{\psi^{\bot}_{j}}|}\sigma{|{\psi^{\bot}_{j}}\rangle}$
(S7)
$\displaystyle=r+\sum_{j}c_{j}{\langle{\psi^{\bot}_{j}}|}\sigma{|{\psi^{\bot}_{j}}\rangle}.$
(S8)

We can write

$\sigma=a{|{\psi}\rangle}\\!{\langle{\psi}|}+b\sigma^{\bot}+c{|{\psi}\rangle}\\!{\langle{\Phi^{\bot}}|}+c^{*}{|{\Phi^{\bot}}\rangle}\\!{\langle{\psi}|},$
(S9)

where $\sigma^{\bot}$ is a density matrix entirely supported in the subspace
spanned by the states ${|{\psi^{\bot}_{j}}\rangle}$, and
${|{\Phi^{\bot}}\rangle}$ is a vector in the subspace spanned by
${|{\psi^{\bot}_{j}}\rangle}$. We know that $a=r$ as
${\langle{\psi}|}\sigma{|{\psi}\rangle}=r$, and $b=1-r$ as
$\operatorname{tr}(\sigma)=1$. Now, note that the probability of accepting
$\sigma$ does not depend on the choice of ${|{\Phi^{\bot}}\rangle}$. Thus
$\operatorname{tr}(\Omega\sigma)$ is maximised when
$\sigma^{\bot}={|{\psi^{\bot}_{max}}\rangle}\\!{\langle{\psi^{\bot}_{max}}|}$,
where ${|{\psi^{\bot}_{max}}\rangle}$ is the orthogonal state in the spectral
decomposition of $\Omega$ with largest eigenvalue, $c_{max}$. Thus

$\max_{\sigma}\operatorname{tr}(\Omega\sigma)=r+(1-r)c_{max},$ (S10)

which is achieved by any density matrix of the form

$\sigma=r{|{\psi}\rangle}\\!{\langle{\psi}|}+(1-r){|{\psi^{\bot}_{max}}\rangle}\\!{\langle{\psi^{\bot}_{max}}|}+c{|{\psi}\rangle}\\!{\langle{\Phi^{\bot}}|}+c^{*}{|{\Phi^{\bot}}\rangle}\\!{\langle{\psi}|}.$
(S11)

Note that the pure state $\sigma={|{\phi}\rangle}\\!{\langle{\phi}|}$ for
${|{\phi}\rangle}=\sqrt{r}{|{\psi}\rangle}+\sqrt{1-r}{|{\psi^{\bot}_{max}}\rangle}$
is of this form, and so we can assume that the adversary makes this choice. ∎

Given that the state $\sigma$ can be taken to be pure and that the fidelity
$F({|{\psi}\rangle},\sigma)\leq 1-\epsilon$, we write
$\sigma={|{\psi_{\bar{\epsilon}}}\rangle}\\!{\langle{\psi_{\bar{\epsilon}}}|}$,
where
${|{\psi_{\bar{\epsilon}}}\rangle}:=\sqrt{1-\bar{\epsilon}}{|{\psi}\rangle}+\sqrt{\bar{\epsilon}}{|{\psi^{\bot}}\rangle}$
and $\braket{\psi}{\psi^{\bot}}=0$, for some $\bar{\epsilon}\geq\epsilon$
chosen by the adversary, to be optimised later. Denote

$\min_{\Omega}\max_{\begin{subarray}{c}\sigma\\\
{\langle{\psi}|}\sigma{|{\psi}\rangle}\leq
1-\epsilon\end{subarray}}\operatorname{tr}(\Omega\sigma)\coloneqq
1-\Delta_{\epsilon}.$ (S12)

Then the optimisation problem becomes to determine $\Delta_{\epsilon}$, where

$\displaystyle\Delta_{\epsilon}=\max_{\Omega}\min_{{|{\psi^{\bot}}\rangle},\bar{\epsilon}\geq\epsilon}\bar{\epsilon}(1-{\langle{\psi^{\bot}}|}\Omega{|{\psi^{\bot}}\rangle})-2\sqrt{\bar{\epsilon}(1-\bar{\epsilon})}\text{Re}({\langle{\psi}|}\Omega{|{\psi^{\bot}}\rangle})$
(S13) $\displaystyle\text{and }\Omega{|{\psi}\rangle}={|{\psi}\rangle}.$

This expression can be simplified given that
$\Omega{|{\psi}\rangle}={|{\psi}\rangle}$. In particular, we then know that
${\langle{\psi^{\bot}}|}\Omega{|{\psi}\rangle}=0$ for any choice of orthogonal
state ${|{\psi^{\bot}}\rangle}$. Thus the term
$\sqrt{\bar{\epsilon}(1-\bar{\epsilon})}\text{Re}({\langle{\psi}|}\Omega{|{\psi^{\bot}}\rangle})$
automatically vanishes. We are then left with the optimisation

$\displaystyle\Delta_{\epsilon}=\max_{\Omega}\min_{{|{\psi^{\bot}}\rangle},\bar{\epsilon}\geq\epsilon}\bar{\epsilon}(1-{\langle{\psi^{\bot}}|}\Omega{|{\psi^{\bot}}\rangle}),$
(S14) $\displaystyle\text{where }\Omega{|{\psi}\rangle}={|{\psi}\rangle}.$

As for the optimisation of $\bar{\epsilon}$, note that it is the goal of the
adversary to make $\Delta_{\epsilon}$ as small as possible; and so they are
obliged to set $\bar{\epsilon}=\epsilon$. Then the optimisation becomes

$\displaystyle\Delta_{\epsilon}=\epsilon$
$\displaystyle\max_{\Omega}\min_{{|{\psi^{\bot}}\rangle}}(1-{\langle{\psi^{\bot}}|}\Omega{|{\psi^{\bot}}\rangle}),$
(S15) $\displaystyle\text{where }\Omega{|{\psi}\rangle}={|{\psi}\rangle}.$

Note that this expression implies that any $\Omega$ where
$\Omega{|{\psi}\rangle}={|{\psi}\rangle}$ automatically satisfies the _future-
proofing_ property: firstly that $\Omega$ is independent of $\epsilon$, but
also that the strategy must be viable for any choice of $\epsilon$ (i.e. there
must not be a choice of $\epsilon$ where $\Delta_{\epsilon}=0$). For an
initial choice $\Delta_{\epsilon}>0$, we have that
$1-{\langle{\psi^{\bot}}|}\Omega{|{\psi^{\bot}}\rangle}>0$ and so
$\Delta_{\epsilon^{\prime}}>0$ for any $0<\epsilon^{\prime}<\epsilon$. Thus
the verifier is free to decrease $\epsilon$ arbitrarily without fear of the
strategy failing. Note also that this condition may not be automatically
guaranteed if the verifier chooses an $\Omega$ such that
$\Omega{|{\psi}\rangle}\neq{|{\psi}\rangle}$.

Regarding the optimisation problem in S15, for an arbitrary state
${|{\psi}\rangle}$ on $n$ qubits it is far from clear how to: (a) construct
families of viable $\Omega$ (built from local projective measurements) that
accept ${|{\psi}\rangle}$ with certainty; (b) to then solve this optimisation
problem over those families of $\Omega$. For the remainder of this work, we
focus on states of particular experimental interest where we can solve the
problem: arbitrary states of 2 qubits, and stabilizer states.

##  Appendix C States of two qubits

We now derive the optimal verification strategy for an arbitrary pure state of
two qubits. We first give the proof of the statement in the main text that
optimal strategies for locally equivalent states are easily derived by
conjugating the strategy with the local map that takes one state to the other.
Hence, we can restrict our consideration to verifying states of the form
${|{\psi}\rangle}=\sin\theta{|{00}\rangle}+\cos\theta{|{11}\rangle}$ without
loss of generality. Specifically:

######  Lemma 3.

Given any two qubit state ${|{\psi}\rangle}$ with optimal strategy
$\Omega_{opt}$, a locally equivalent state $(U\otimes V){|{\psi}\rangle}$ has
optimal strategy $(U\otimes V)\Omega_{opt}(U\otimes V)^{\dagger}$.

###### Proof.

We must show that strategy $\Omega^{\prime}=(U\otimes V)\Omega_{opt}(U\otimes
V)^{\dagger}$ is both a valid strategy, and is optimal for verifying
${|{\psi^{\prime}}\rangle}=(U\otimes V){|{\psi}\rangle}$.

_Validity_ : If $\Omega_{opt}=\sum_{j}\mu_{j}P_{j}$ is a convex combination of
local projectors, then so is $\Omega^{\prime}$:

$\displaystyle\Omega^{\prime}=(U\otimes V)\Omega(U\otimes V)^{\dagger}$
$\displaystyle=\sum_{j}\mu_{j}(U\otimes V)P_{j}(U\otimes V)^{\dagger}$
$\displaystyle=\sum_{j}\mu_{j}P^{\prime}_{j}.$ (S16)

Also, if $\Omega_{opt}{|{\psi}\rangle}={|{\psi}\rangle}$ then
$\Omega^{\prime}{|{\psi^{\prime}}\rangle}={|{\psi^{\prime}}\rangle}$:

$\displaystyle\Omega_{opt}{|{\psi}\rangle}={|{\psi}\rangle}$
$\displaystyle\Rightarrow(U\otimes V)\Omega{|{\psi}\rangle}=p_{opt}(U\otimes
V){|{\psi}\rangle}$ (S17) $\displaystyle\Rightarrow(U\otimes V)\Omega(U\otimes
V)^{\dagger}(U\otimes V){|{\psi}\rangle}=(U\otimes V){|{\psi}\rangle}$
$\displaystyle\Rightarrow\Omega^{\prime}{|{\psi^{\prime}}\rangle}={|{\psi^{\prime}}\rangle}.$

_Optimality_ : The performance of a strategy is determined by the maximum
probability of accepting an orthogonal state ${|{\psi^{\bot}}\rangle}$. For
the strategy-state pairs $(\Omega_{opt},{|{\psi}\rangle})$ and
$(\Omega^{\prime},{|{\psi^{\prime}}\rangle})$, we denote this parameter
$q_{opt}$ and $q^{\prime}$, respectively. Then

$\displaystyle q_{opt}$
$\displaystyle=\max_{{|{\psi^{\bot}}\rangle}}{\langle{\psi^{\bot}}|}\Omega_{opt}{|{\psi^{\bot}}\rangle}=\max_{{|{\phi}\rangle},\braket{\psi}{\phi}=0}{\langle{\phi}|}\Omega_{opt}{|{\phi}\rangle}$
(S18) $\displaystyle=\max_{(U\otimes
V){|{\phi}\rangle},{\langle{\psi}|}(U\otimes V)^{\dagger}(U\otimes
V){|{\phi}\rangle}=0}{\langle{\phi}|}(U\otimes V)^{\dagger}(U\otimes
V)\Omega_{opt}(U\otimes V)^{\dagger}(U\otimes V){|{\phi}\rangle}$ (S19)
$\displaystyle=\max_{{|{\phi^{\prime}}\rangle},\braket{\psi^{\prime}}{\phi^{\prime}}=0}{\langle{\phi^{\prime}}|}\Omega^{\prime}{|{\phi^{\prime}}\rangle}=q^{\prime}.$
(S20)

So applying the same local rotation to the strategy and the state results in
no change in the performance of the strategy. Thus the following simple proof
by contradiction holds: assume that there is a better strategy for verifying
${|{\psi^{\prime}}\rangle}$, denoted $\Omega^{\prime\prime}$. But then the
strategy $(U\otimes V)^{\dagger}\Omega^{\prime\prime}(U\otimes V)$ must have a
better performance for verifying ${|{\psi}\rangle}$ than $\Omega_{opt}$, which
is a contradiction. Thus $\Omega^{\prime}$ must be the optimal strategy for
verifying ${|{\psi^{\prime}}\rangle}$. ∎

We will now prove Theorem 1 from the main body. However, we first prove a
useful lemma - that no optimal strategy can contain the identity measurement
(where the verifier always accepts regardless of the tested state). In the
following discussion, we denote the projector
$\Pi\coloneqq\mathds{1}-{|{\psi}\rangle}\\!{\langle{\psi}|}$. For a strategy
$\Omega$ where $\Omega{|{\psi}\rangle}={|{\psi}\rangle}$, the quantity of
interest which determines $\Delta_{\epsilon}$ in (S15) is the maximum
probability of accepting an orthogonal state ${|{\psi^{\bot}}\rangle}$:

$q\coloneqq\|\Pi\Omega\Pi\|=\max_{{|{\psi^{\bot}}\rangle}}{\langle{\psi^{\bot}}|}\Omega{|{\psi^{\bot}}\rangle}.$
(S21)

If a strategy is augmented with an accent or subscript, the parameter $q$
inherits that accent or subscript.

######  Lemma 4.

Consider an operator $0\leq\Omega\leq 1$,
$\Omega{|{\psi}\rangle}={|{\psi}\rangle}$ of the form
$\Omega=(1-\alpha)\Omega_{1}+\alpha\mathds{1}$ for $0\leq\alpha\leq 1$. Then
$q\geq q_{1}$.

###### Proof.

For arbitrary ${|{\psi^{\perp}}\rangle}$ such that
$\braket{\psi}{\psi^{\perp}}=0$,
$\braket{\psi^{\perp}}{\Omega}{\psi^{\perp}}=(1-\alpha)\braket{\psi^{\perp}}{\Omega_{1}}{\psi^{\perp}}+\alpha$.
This is maximised by choosing ${|{\psi^{\perp}}\rangle}$ such that
$\braket{\psi^{\perp}}{\Omega_{1}}{\psi^{\perp}}=q_{1}$, giving
$q=(1-\alpha)q_{1}+\alpha\geq q_{1}$. ∎

We are now in a position to prove Theorem 1. Note that the special cases where
${|{\psi}\rangle}$ is a product state ($\theta=0$ or $\frac{\pi}{2}$) or a
Bell state ($\theta=\frac{\pi}{4}$) are treated separately.

######  Theorem 1 (restated).

Any optimal strategy for verifying a state of the form
${|{\psi}\rangle}=\sin\theta{|{00}\rangle}+\cos\theta{|{11}\rangle}$ for
$0<\theta<\frac{\pi}{2}$, $\theta\neq\frac{\pi}{4}$ that accepts
${|{\psi_{\theta}}\rangle}$ with certainty and satisfies the properties of
locality, trust and projective measurement, can be expressed as a strategy
involving four measurement settings:

$\Omega^{opt}=\frac{2-\sin(2\theta)}{4+\sin(2\theta)}P^{+}_{ZZ}+\frac{2(1+\sin(2\theta))}{3(4+\sin(2\theta))}\sum_{k=1}^{3}(\mathds{1}-{|{\phi_{k}}\rangle}\\!{\langle{\phi_{k}}|}),$
(S22)

where the states ${|{\phi_{k}}\rangle}$ are

$\displaystyle{|{\phi_{1}}\rangle}$
$\displaystyle=\left(\frac{1}{\sqrt{1+\tan\theta}}{|{0}\rangle}+\frac{e^{\frac{2\pi
i}{3}}}{\sqrt{1+\cot\theta}}{|{1}\rangle}\right)\otimes\left(\frac{1}{\sqrt{1+\tan\theta}}{|{0}\rangle}+\frac{e^{\frac{\pi
i}{3}}}{\sqrt{1+\cot\theta}}{|{1}\rangle}\right),$ (S23)
$\displaystyle{|{\phi_{2}}\rangle}$
$\displaystyle=\left(\frac{1}{\sqrt{1+\tan\theta}}{|{0}\rangle}+\frac{e^{\frac{4\pi
i}{3}}}{\sqrt{1+\cot\theta}}{|{1}\rangle}\right)\otimes\left(\frac{1}{\sqrt{1+\tan\theta}}{|{0}\rangle}+\frac{e^{\frac{5\pi
i}{3}}}{\sqrt{1+\cot\theta}}{|{1}\rangle}\right),$ (S24)
$\displaystyle{|{\phi_{3}}\rangle}$
$\displaystyle=\left(\frac{1}{\sqrt{1+\tan\theta}}{|{0}\rangle}+\frac{1}{\sqrt{1+\cot\theta}}{|{1}\rangle}\right)\otimes\left(\frac{1}{\sqrt{1+\tan\theta}}{|{0}\rangle}-\frac{1}{\sqrt{1+\cot\theta}}{|{1}\rangle}\right).$
(S25)

The number of measurements needed to verify to within fidelity $\epsilon$ and
statistical power $1-\delta$ is

$n_{opt}\approx(2+\sin\theta\cos\theta)\epsilon^{-1}\ln\delta^{-1}.$ (S26)

###### Proof.

The strategy $\Omega$ can be written as a convex combination of local
projectors. We can group the projectors by their action according to two local
parties, Alice and Bob, and then it must be expressible as a convex
combination of five types of terms, grouped by trace:

$\Omega=c_{1}\sum_{i}\mu_{i}(\rho^{i}_{1}\otimes\sigma^{i}_{1})+c_{2}\sum_{j}\nu_{j}(\rho^{j}_{2}\otimes\sigma^{j}_{2}+\rho_{2}^{j\bot}\otimes\sigma_{2}^{j\bot})+c_{3}\sum_{k}\eta_{k}(\mathds{1}-\rho^{k}_{3}\otimes\sigma^{k}_{3})+c_{4}\sum_{l}[\zeta_{l}(\rho^{l}_{4}\otimes\mathds{1})+\xi_{l}(\mathds{1}\otimes\sigma^{l}_{4})]+c_{5}\mathds{1}\otimes\mathds{1},$
(S27)

where $\rho^{k}_{i}$ and $\sigma^{k}_{i}$ are single-qubit pure states and the
subscript denotes the type of term in question. The state $\rho^{j\bot}$ is
the density matrix defined by $\operatorname{tr}(\rho^{j}\rho^{j\bot})=0$.
Qualitatively, given two local parties Alice and Bob with access to one qubit
each, and projectors with outcomes $\\{\lambda,\bar{\lambda}\\}$, the terms
above correspond to the following strategies: (1) Alice and Bob both apply a
projective measurement and accept if both outcomes are $\lambda$; (2) Alice
and Bob both apply a projective measurement and accept if both outcomes agree;
(3) Alice and Bob both apply a projective measurement and accept unless both
outcomes are $\lambda$; (4) Alice or Bob applies a projective measurement and
accepts on outcome $\lambda$, and the other party abstains; and (5) both Alice
and Bob accept without applying a measurement.

We show in Appendix E that strategies that accept ${|{\psi}\rangle}$ with
certainty have a quadratic advantage in scaling in terms of epsilon. Given
this, we enforce this constraint from the outset and then show that a viable
strategy can still be constructed. For the general strategy in Eq. S27 to
accept ${|{\psi}\rangle}$ with certainty, each term in its expansion must
accept ${|{\psi}\rangle}$ with certainty. However, this is impossible to
achieve for some of the terms in the above expansion. In particular, we show
that the terms $(\rho\otimes\sigma)$, $(\rho\otimes\mathds{1})$ and
$(\mathds{1}\otimes\sigma)$ cannot accept ${|{\psi}\rangle}$ with certainty,
and the form of the term $(\rho\otimes\sigma+\rho^{\bot}\otimes\sigma^{\bot})$
is restricted.

$\mathit{(\rho\otimes\sigma)}$: given that $\rho$ and $\sigma$ are pure, write
$\rho\otimes\sigma={|{u}\rangle}\\!{\langle{u}|}\otimes{|{v}\rangle}\\!{\langle{v}|}$,
and so this term only accepts ${|{\psi}\rangle}$ with certainty if
$\|({|{u}\rangle}\\!{\langle{u}|}\otimes{|{v}\rangle}\\!{\langle{v}|}){|{\psi}\rangle}\|=1$.
However, for $0<\theta<\frac{\pi}{2}$ the state ${|{\psi}\rangle}$ is
entangled and this condition cannot be satisfied.

$\mathit{(\rho\otimes\mathds{1})}$ or $\mathit{(\mathds{1}\otimes\sigma)}$:
For the term $(\rho\otimes\mathds{1})$, reexpress $\rho$ in terms of its Pauli
expansion: $\rho\otimes\mathds{1}=\frac{1}{2}(\mathds{1}+\alpha X+\beta
Y+\gamma Z)\otimes\mathds{1}$, for $-1\leq\alpha,\beta,\gamma\leq 1$. Then the
condition that this term accepts with probability $p=1$ is

${\langle{\psi}|}\frac{1}{2}(\mathds{1}+\alpha X+\beta Y+\gamma
Z)\otimes\mathds{1}{|{\psi}\rangle}=1.$ (S28)

By inserting the definition of ${|{\psi}\rangle}$, this becomes
$\frac{1}{2}(1-\gamma\cos(2\theta))=1$, which is unsatisfiable for
$0<\theta<\frac{\pi}{2}$. It is readily checkable that an identical condition
is derived for the term $\mathds{1}\otimes\sigma$, given the symmetry of the
state ${|{\psi}\rangle}$ under swapping.

$\mathit{(\rho\otimes\sigma+\rho^{\bot}\otimes\sigma^{\bot})}$: for this term,
we can expand both $\rho$ and $\sigma$ in terms of Pauli operators:

$\displaystyle\rho$ $\displaystyle=\frac{1}{2}(\mathds{1}+\alpha X+\beta
Y+\gamma Z);\quad$ $\displaystyle\rho^{\bot}=\frac{1}{2}(\mathds{1}-\alpha
X-\beta Y-\gamma Z)$ (S29) $\displaystyle\sigma$
$\displaystyle=\frac{1}{2}(\mathds{1}+\alpha^{\prime}X+\beta^{\prime}Y+\gamma^{\prime}Z);\quad$
$\displaystyle\sigma^{\bot}=\frac{1}{2}(\mathds{1}-\alpha^{\prime}X-\beta^{\prime}Y-\gamma^{\prime}Z).$
(S30)

Inserting these expressions and the definition of ${|{\psi}\rangle}$ into the
condition that $p=1$ gives the constraint

$\gamma\gamma^{\prime}+(\alpha\alpha^{\prime}-\beta\beta^{\prime})\sin(2\theta)=1.$
(S31)

Now, we know from the Cauchy-Schwarz inequality that

$\gamma\gamma^{\prime}+(\alpha\alpha^{\prime}-\beta\beta^{\prime})\sin(2\theta)\leq\sqrt{\alpha^{\prime
2}+\beta^{\prime 2}+\gamma^{\prime
2}}\sqrt{\alpha^{2}\sin^{2}(2\theta)+\beta^{2}\sin^{2}(2\theta)+\gamma^{2}}\leq
1,$ (S32)

where the second inequality is derived from the fact that
$\\{\alpha,\beta,\gamma\\}$,
$\\{\alpha^{\prime},\beta^{\prime},\gamma^{\prime}\\}$ are the
parameterisation of a pair of density matrices. There are two ways that this
inequality can be saturated: (a) $\sin(2\theta)=1$; (b)
$\alpha\alpha^{\prime}-\beta\beta^{\prime}=0$, $\gamma\gamma^{\prime}=1$. In
all other cases, the inequality is strict. Thus the constraint in Eq. S31
cannot be satisfied in general. Exception (a) corresponds to
$\theta=\frac{\pi}{4}$, which is omitted from this proof and treated
separately. In exception (b), we have that $\gamma\gamma^{\prime}=1$ and so
either $\gamma=\gamma^{\prime}=1$ or $\gamma=\gamma^{\prime}=-1$. In both
cases we have that

$\rho\otimes\sigma+\rho^{\bot}\otimes\sigma^{\bot}=\left(\frac{\mathds{1}+Z}{2}\otimes\frac{\mathds{1}+Z}{2}\right)+\left(\frac{\mathds{1}-Z}{2}\otimes\frac{\mathds{1}-Z}{2}\right)=P^{+}_{ZZ},$
(S33)

where $P^{+}_{ZZ}$ is the projector onto the positive eigenspace of $ZZ$. This
is the only possible choice for this particular term that accepts
${|{\psi}\rangle}$ with certainty.

We can also make use of Lemma 4 to remove the term
$\mathds{1}\otimes\mathds{1}$. Given this and the restrictions above from
enforcing that $p=1$, the measurement strategy can be written

$\Omega=\alpha
P^{+}_{ZZ}+(1-\alpha)\sum_{k}\eta_{k}(\mathds{1}-\rho_{k}\otimes\sigma_{k}),$
(S34)

where $\sum_{k}\eta_{k}=1$ and $0\leq\alpha\leq 1$.

We’ll try to further narrow down the form of this strategy by _averaging_ ;
i.e. by noting that, as ${|{\psi}\rangle}$ is an eigenstate of a matrix
$M_{\zeta}\otimes M_{-\zeta}$ where

$M_{\zeta}=\begin{pmatrix}1&0\\\ 0&e^{-i\zeta}\end{pmatrix},$ (S35)

then conjugating the strategy by $M_{\zeta}\otimes M_{-\zeta}$ and integrating
over all possible $\zeta$ cannot make the strategy worse; if we consider an
averaged strategy $\langle\Omega\rangle$ such that

$\langle\Omega\rangle=\frac{1}{2\pi}\int_{-\pi}^{\pi}d\zeta(M_{\zeta}\otimes
M_{-\zeta})\Omega(M_{-\zeta}\otimes M_{\zeta}),$ (S36)

then necessarily the performance of $\langle\Omega\rangle$ cannot be worse
than that of $\Omega$. To see this, note that the averaging procedure does not
affect the probability of accepting the state ${|{\psi}\rangle}$. However, for
each particular value of $\zeta$ the optimisation for the adversary may
necessarily lead to different choices for the orthogonal states
${|{\psi^{\bot}(\zeta)}\rangle}$, and so averaging over $\zeta$ cannot be
better for the adversary than choosing the optimal ${|{\psi^{\bot}}\rangle}$
at $\zeta=0$.

We can also consider discrete symmetries of the state ${|{\psi}\rangle}$. In
particular, ${|{\psi}\rangle}$ is invariant under both swapping the two
qubits, and complex conjugation (with respect to the standard basis); by the
same argument, averaging over these symmetries (i.e. by considering
$\Omega^{\prime}=\frac{1}{2}(\Omega+(\text{SWAP})\Omega(\text{SWAP}^{\dagger}))$
and $\Omega^{\prime\prime}=\frac{1}{2}(\Omega+\Omega^{*})$) cannot produce
strategies inferior to the original $\Omega$. Therefore we can consider a
strategy averaged over these families of symmetries of $\Omega$, without any
loss in performance.

This averaging process is useful for three reasons. Firstly, it heavily
restricts the number of free parameters in $\Omega$ requiring optimisation.
Secondly, it allows us to be explicit about the general form of $\Omega$.
Thirdly, the averaging procedures are distributive over addition; and so we
can make the replacement

$\displaystyle\Omega=\alpha
P^{+}_{ZZ}+(1-\alpha)\sum_{k}\eta_{k}(\mathds{1}-\rho_{k}\otimes\sigma_{k})\rightarrow\langle$
$\displaystyle\alpha
P^{+}_{ZZ}+(1-\alpha)\sum_{k}\eta_{k}(\mathds{1}-\rho_{k}\otimes\sigma_{k})\rangle$
$\displaystyle=$ $\displaystyle\alpha
P^{+}_{ZZ}+(1-\alpha)\sum_{k}\eta_{k}\langle\mathds{1}-\rho_{k}\otimes\sigma_{k}\rangle.$
(S37)

Note that a single term $\mathds{1}-\rho_{k}\otimes\sigma_{k}$, may, after
averaging, be a convex combination of multiple terms of the form
$\mathds{1}-\rho\otimes\sigma$. To proceed, we will use this averaging
procedure to show that it suffices to only include a single, post-averaging
term of the form $\langle\mathds{1}-\rho_{k}\otimes\sigma_{k}\rangle$ in the
strategy $\Omega$, and that the resulting operator can be explicitly
decomposed into exactly three measurement settings.

Consider a general operator $\Omega$, expressed as a $4\times 4$ matrix.
First, take the discrete symmetries of ${|{\psi}\rangle}$. Averaging over
complex conjugation in the standard basis implies that the coefficients of
$\langle\Omega\rangle$ are real; and averaging over qubit swapping implies
that $\langle\Omega\rangle$ is symmetric with respect to swapping of the two
qubits. Denote the operator after averaging these discrete symmetries as
$\bar{\Omega}$. Then consider averaging over the continuous symmetry of
${|{\psi}\rangle}$:

$\displaystyle\langle\Omega\rangle$
$\displaystyle=\frac{1}{2\pi}\int_{-\pi}^{\pi}d\zeta(M_{\zeta}\otimes
M_{-\zeta})\bar{\Omega}(M_{-\zeta}\otimes M_{\zeta})$ (S38)
$\displaystyle=\frac{1}{2\pi}\int_{-\pi}^{\pi}d\zeta\begin{pmatrix}1&0&0&0\\\
0&e^{i\zeta}&0&0\\\ 0&0&e^{-i\zeta}&0\\\
0&0&0&1\end{pmatrix}\begin{pmatrix}\omega_{00}&\omega_{01}&\omega_{01}&\omega_{03}\\\
\omega_{01}&\omega_{11}&\omega_{12}&\omega_{13}\\\
\omega_{01}&\omega_{12}&\omega_{11}&\omega_{13}\\\
\omega_{03}&\omega_{13}&\omega_{13}&\omega_{33}\end{pmatrix}\begin{pmatrix}1&0&0&0\\\
0&e^{-i\zeta}&0&0\\\ 0&0&e^{i\zeta}&0\\\ 0&0&0&1\end{pmatrix}$ (S39)
$\displaystyle=\begin{pmatrix}\omega_{00}&0&0&\omega_{03}\\\
0&\omega_{11}&0&0\\\ 0&0&\omega_{11}&0\\\
\omega_{03}&0&0&\omega_{33}\end{pmatrix}.$ (S40)

Thus after averaging using the above symmetries of ${|{\psi}\rangle}$,
$\langle\Omega\rangle$ can be written in the standard basis as

$\langle\Omega\rangle=\begin{pmatrix}a&0&0&b\\\ 0&c&0&0\\\ 0&0&c&0\\\
b&0&0&d\end{pmatrix},$ (S41)

for $a,b,c,d\in\mathbb{R}$. Enforcing that the strategy accepts
${|{\psi}\rangle}$ with certainty yields
$\langle\Omega\rangle{|{\psi}\rangle}={|{\psi}\rangle}$, or explicitly that

$\langle\Omega\rangle=\begin{pmatrix}1-b\cot\theta&0&0&b\\\ 0&c&0&0\\\
0&0&c&0\\\ b&0&0&1-b\tan\theta\end{pmatrix}.$ (S42)

The eigensystem of this operator is then completely specified; besides
${|{\psi}\rangle}$, it has the following eigenvectors:

${|{v_{1}}\rangle}=\cos\theta{|{00}\rangle}-\sin\theta{|{11}\rangle};\quad{|{v_{2}}\rangle}={|{01}\rangle};\quad{|{v_{3}}\rangle}={|{10}\rangle},$
(S43)

with corresponding eigenvalues $\lambda_{1}=1-b\csc\theta\sec\theta$ and
$\lambda_{2}=\lambda_{3}=c$. The maximum probability of accepting a state
orthogonal to ${|{\psi}\rangle}$, $q$, can then be written

$q=\|\Pi\langle\Omega\rangle\Pi\|=\max\\{\lambda_{1},\lambda_{2}\\},$ (S44)

where $\Pi=\mathds{1}-{|{\psi}\rangle}\\!{\langle{\psi}|}$. Therefore, any
reasoning about $q$ can be reduced to reasoning about the pair
$(\lambda_{1},\lambda_{2})$.

Now, we will show that it suffices to only consider a single term of the form
$\langle\mathds{1}-\rho_{k}\otimes\sigma_{k}\rangle$ in the decomposition of
$\Omega$. We write a strategy of this form as

$\Omega=\alpha
P^{+}_{ZZ}+(1-\alpha)\langle\mathds{1}-\rho\otimes\sigma\rangle.$ (S45)

For the term $\langle\mathds{1}-\rho\otimes\sigma\rangle$, we have a
constraint on the trace; if we label the eigenvalues for this term as
$\lambda_{1}^{(3)}$ and $\lambda_{2}^{(3)}$, we have the constraint that
$1+\lambda^{(3)}_{1}+2\lambda_{2}^{(3)}=\operatorname{tr}\langle\mathds{1}-\rho\otimes\sigma\rangle=3\Rightarrow\lambda_{2}^{(3)}=1-\frac{\lambda_{1}^{(3)}}{2}$.
The locus of points satisfying this constraint is plotted in the
$(\lambda_{1},\lambda_{2})$ plane as the thick black line in Fig. S2.
Moreover, we will show that a single term of this form can achieve any valid
choice of $\lambda_{1}^{(3)}$ on this locus (which we defer until we have an
explicit parameterisation of terms of this type; see Eq. S57, below).

However, we also have an additional constraint derived from insisting that the
strategy remains local. For example, the point $(0,1)$ in the
$(\lambda_{1},\lambda_{2})$ plane represents the strategy
$\Omega=\mathds{1}-{|{v_{1}}\rangle}\\!{\langle{v_{1}}|}$, which corresponds
to the strategy where the verifier projects onto ${|{v_{1}}\rangle}$ and
accepts if the outcome is not ${|{v_{1}}\rangle}$. But this type of
measurement is operationally forbidden as ${|{v_{1}}\rangle}$ is entangled.

It can be readily checked that, for an arbitrary $\theta$, it is not possible
to cover the full locus in the range $0\leq\lambda_{1}\leq 1$ with a separable
strategy; instead, there is a fixed lower bound on $\lambda_{1}^{(3)}$. To see
this, write

$\langle\mathds{1}-\rho\otimes\sigma\rangle={|{\psi}\rangle}\\!{\langle{\psi}|}+\lambda_{1}^{(3)}{|{v_{1}}\rangle}\\!{\langle{v_{1}}|}+\frac{2-\lambda_{1}^{(3)}}{2}({|{v_{2}}\rangle}\\!{\langle{v_{2}}|}+{|{v_{3}}\rangle}\\!{\langle{v_{3}}|}).$
(S46)

Then, taking just the $\langle\rho\otimes\sigma\rangle$ part and expressing as
a matrix in the computational basis gives

$\langle\rho\otimes\sigma\rangle=\begin{pmatrix}(1-\lambda_{1}^{(3)})\cos^{2}\theta&0&0&(\lambda_{1}^{(3)}-1)\cos\theta\sin\theta\\\
0&\frac{\lambda_{1}^{(3)}}{2}&0&0\\\ 0&0&\frac{\lambda_{1}^{(3)}}{2}&0\\\
(\lambda_{1}^{(3)}-1)\cos\theta\sin\theta&0&0&(1-\lambda_{1}^{(3)})\sin^{2}\theta\end{pmatrix}.$
(S47)

To enforce separability it is necessary and sufficient to check positivity
under partial transposition, yielding the constraint
$\lambda_{1}^{(3)}-(1-\lambda_{1}^{(3)})\sin(2\theta)\geq 0$. Simple
rearrangement gives a lower bound that must be satisfied for the strategy to
remain separable:

$\lambda_{1}^{(3)}\geq\frac{\sin(2\theta)}{1+\sin(2\theta)}\coloneqq\lambda_{LB}.$
(S48)

This additional locality constraint rules out any point on the black line to
the left of the red point in Fig. S2. The term $P^{+}_{ZZ}$ has parameters
$\lambda_{1}^{ZZ}=1$, $\lambda_{2}^{ZZ}=0$ and so represents a single point in
the $(\lambda_{1},\lambda_{2})$ plane. Thus the parameters
$(\lambda_{1},\lambda_{2})$ for the full strategy $\Omega$ must be represented
by a point in the convex hull of the single point representing the
$P^{+}_{ZZ}$ term and the locus of points representing the trace 3 part - i.e.
in the unshaded region in Fig. S2.

We now show that a strategy that includes more trace 3 terms cannot improve on
the performance of the strategy above. Write this expanded strategy as

$\Omega^{\prime}=\alpha
P^{+}_{ZZ}+(1-\alpha)\langle\sum_{k}\eta_{k}(\mathds{1}-\rho_{k}\otimes\sigma_{k})\rangle,$
(S49)

for $\sum_{k}\eta_{k}=1$. Firstly, we note again that the averaging operations
(SWAP, conjugation via $M_{\zeta}$ and complex conjugation in the standard
basis) are distributive over addition and so we can make the replacement

$\Omega^{\prime}=\alpha
P^{+}_{ZZ}+(1-\alpha)\sum_{k}\eta_{k}\langle\mathds{1}-\rho_{k}\otimes\sigma_{k}\rangle.$
(S50)

Write the composite term
$\sum_{k}\eta_{k}\langle\mathds{1}-\rho_{k}\otimes\sigma_{k}\rangle\coloneqq\Omega_{\text{comp}}$,
with parameters $\lambda_{1}^{\text{comp}}$ and $\lambda_{2}^{\text{comp}}$.
Note that each term in $\Omega_{\text{comp}}$ satisfies both the constraint
from the trace and the constraint from PPT in S48, and hence so does
$\Omega_{\text{comp}}$. Now, each operator in this term shares the same
eigenbasis (namely, the set of states $\\{{|{v_{i}}\rangle}\\}$ in S43). Thus
we know that $\lambda_{1}^{\text{comp}}=\sum_{k}\eta_{k}\lambda_{1,k}$, and
likewise for $\lambda_{2}^{\text{comp}}$; i.e. the strategy parameters for
this composite term are just a convex combination of those for its constituent
parts. A term $\Omega_{\text{comp}}$ is then specified in the
$(\lambda_{1},\lambda_{2})$ plane by a point
$\mathcal{P}_{\text{comp}}=(\lambda_{1}^{\text{comp}},\lambda_{2}^{\text{comp}})\in\text{Conv}(\lambda_{1,k},\lambda_{2,k})$
(i.e. the point $\mathcal{P}_{\text{comp}}$ must lie on the thick black line
bounding the unshaded region in Fig. S2).

Thus we know that $\text{Conv}(\Omega^{\prime})\subseteq\text{Conv}(\Omega)$,
and so any strategy writeable in the form S49 can be replaced by a strategy of
the form S45 with identical parameters $(\lambda_{1},\lambda_{2})$, and hence
identical performance. Thus, we need only consider strategies of the form

$\Omega=\alpha
P^{+}_{ZZ}+(1-\alpha)\langle\mathds{1}-\rho\otimes\sigma\rangle.$ (S51)

We can now be explicit about the form of the above strategy. For $\Omega$ to
accept ${|{\psi}\rangle}$ with certainty, $\rho\otimes\sigma$ must annihilate
${|{\psi}\rangle}$ and so we make the replacement
$\rho\otimes\sigma={|{\tau}\rangle}\\!{\langle{\tau}|}$, where
${|{\tau}\rangle}$ is the most general pure product state that annihilates
${|{\psi}\rangle}$. To be explicit about the form of the state
${|{\tau}\rangle}$, write a general two-qubit separable state as

${|{\tau}\rangle}=(\cos\phi{|{0}\rangle}+e^{i\eta}\sin\phi{|{1}\rangle})\otimes(\cos\xi{|{0}\rangle}+e^{i\zeta}\sin\xi{|{1}\rangle}),$
(S52)

where we take $0\leq\phi,\xi\leq\frac{\pi}{2}$, without loss of generality.
The constraint that this state annihilates
${|{\psi}\rangle}=\sin\theta{|{00}\rangle}+\cos\theta{|{11}\rangle}$ is

$\cos\phi\cos\xi\sin\theta+e^{-i(\eta+\zeta)}\sin\phi\sin\xi\cos\theta=0.$
(S53)

If either $\phi=0$ or $\xi=0$, then $\cos\phi\cos\xi\sin\theta=0$ implying
that $\xi=\frac{\pi}{2}$ or $\phi=\frac{\pi}{2}$, respectively. This yields
the annihilating states ${|{\tau}\rangle}={|{01}\rangle}$ and
${|{\tau}\rangle}={|{10}\rangle}$, respectively. If $\phi,\xi\neq 0$ then from
the imaginary part of Eq. S53 we find that $e^{-i(\eta+\zeta)}=-1$. Then we
can rearrange to give

$\tan\phi\tan\xi=\tan\theta.$ (S54)

Using this constraint and the identities

$\cos\xi=\frac{1}{\sqrt{1+\tan^{2}\xi}};\quad\sin\xi=\frac{\tan\xi}{\sqrt{1+\tan^{2}\xi}},$
(S55)

we can eliminate $\xi$ to yield

${|{\tau}\rangle}=(\cos\phi{|{0}\rangle}+e^{i\eta}\sin\phi{|{1}\rangle})\otimes\left(\frac{\tan\phi}{\sqrt{\tan^{2}\phi+\tan^{2}\theta}}{|{0}\rangle}-\frac{e^{-i\eta}\tan\theta}{\sqrt{\tan^{2}\phi+\tan^{2}\theta}}{|{1}\rangle}\right).$
(S56)

Note that, for $0<\theta<\frac{\pi}{2}$, taking the limits $\phi\rightarrow 0$
and $\phi\rightarrow\frac{\pi}{2}$ we recover the cases
${|{\tau}\rangle}={|{01}\rangle}$ and ${|{\tau}\rangle}={|{10}\rangle}$, up to
irrelevant global phases. Thus we can proceed without loss of generality by
assuming that $\rho\otimes\sigma={|{\tau}\rangle}\\!{\langle{\tau}|}$, where
${|{\tau}\rangle}$ is given by Eq. S56. Averaging over the symmetries of
${|{\psi}\rangle}$ outlined above then yields the following expression:

$\langle\rho\otimes\sigma\rangle=\frac{1}{t^{2}\phi+t^{2}\theta}\begin{pmatrix}s^{2}\phi&0&0&-s^{2}\phi
t\theta\\\ 0&\frac{1}{2}\left(c^{2}\phi t^{2}\theta+s^{2}\phi
t^{2}\phi\right)&0&0\\\ 0&0&\frac{1}{2}\left(c^{2}\phi t^{2}\theta+s^{2}\phi
t^{2}\phi\right)&0\\\ -s^{2}\phi t\theta&0&0&s^{2}\phi
t^{2}\theta\end{pmatrix},$ (S57)

using the shorthand $s$, $c$, $t$ for $\sin$, $\cos$ and $\tan$, respectively.
Given this explicit parameterisation we can extract the eigenvalue
$\lambda_{1}^{(3)}$:

$\lambda_{1}^{(3)}=1-\frac{\sec^{2}\theta\sin^{2}\phi}{\tan^{2}\theta+\tan^{2}\phi}.$
(S58)

It can be shown by simple differentiation w.r.t. $\phi$ that, for fixed
$\theta$, this expression has a minimum at $\lambda_{1}^{(3)}=\lambda_{LB}$.
Also, this expression is a continuous function of $\phi$ and therefore can
take any value up to its maximum (namely, $1$). Hence a single trace 3 term is
enough to achieve any point in the allowable convex hull in Fig. S2. For
convenience we will denote $\tan^{2}\phi=P,\;\tan^{2}\theta=T$ for $0\leq
P\leq\infty$, $0<T<\infty$. The explicit form for the whole strategy is then

$\Omega=\begin{pmatrix}\frac{T+P(P+T+\alpha)}{(1+P)(P+T)}&0&0&\frac{(1-\alpha)P\sqrt{T}}{(1+P)(P+T)}\\\
0&\frac{(1-\alpha)(T+2P+P^{2}+2PT)}{2(1+P)(P+T)}&0&0\\\
0&0&\frac{(1-\alpha)(T+2P+P^{2}+2PT)}{2(1+P)(P+T)}&0\\\
\frac{(1-\alpha)P\sqrt{T}}{(1+P)(P+T)}&0&0&\frac{T+P(1+P+\alpha
T)}{(1+P)(P+T)}\end{pmatrix}.$ (S59)

We now optimise over the two remaining free parameters, $\\{\alpha,\phi\\}$
(or alternatively, $\\{\alpha,P\\}$) for fixed $\theta$ (or fixed $T$). This
optimisation is rather straightforward from inspection (see Fig. S2), and the
reader may wish to skip to the answer in Eq. S66. However, we include an
analytic proof for the sake of completeness. We have shown that it suffices to
consider the eigenvalues $\lambda_{1}$ and $\lambda_{2}$, given in this case
by the expressions

$\lambda_{1}(\alpha,P,T)=1-\frac{P(1-\alpha)(1+T)}{(1+P)(P+T)};\quad\lambda_{2}(\alpha,P,T)=(1-\alpha)\left[1-\frac{T+P^{2}}{2(1+P)(P+T)}\right].$
(S60)

The parameter $q$ is given by the maximum of these two eigenvalues. Note that,
if $P=0$, the expression $\lambda_{1}(\alpha,0,T)=1$ which implies that the
adversary can pick a state that the verifier always accepts, and hence the
strategy fails. Likewise, taking the limit
$\lim_{P\rightarrow\infty}\lambda_{1}(\alpha,P,T)=1$. Thus we must restrict to
the range $0<P<\infty$ to construct a viable strategy for the verifier. The
quantity $q$ is minimised for fixed $T$ when the derivatives with respect to
$P$ and $\alpha$ vanish. First, we calculate the derivatives w.r.t. $\alpha$:

$\frac{\partial\lambda_{1}}{\partial\alpha}=\frac{P(1+T)}{(1+P)(P+T)};\quad\frac{\partial\lambda_{2}}{\partial\alpha}=\frac{-(2P+P^{2}+T+2PT)}{2(1+P)(P+T)}.$
(S61)

Given that $P>0$ and $T>0$, we have that for any choice of $T$,
$\partial_{\alpha}\lambda_{1}>0$ and $\partial_{\alpha}\lambda_{2}<0$. Thus,
one of three cases can occur: (a) for a given choice of $T$ and $P$, the lines
given by $\lambda_{1}$ and $\lambda_{2}$ intersect in the range
$0\leq\alpha\leq 1$ and hence there is a valid $\alpha$ such that $q$ is
minimised when $\lambda_{1}=\lambda_{2}$; (b) for a given choice of $T$ and
$P$, $\lambda_{1}>\lambda_{2}$ in the range $0\leq\alpha\leq 1$ and hence $q$
is minimised when $\alpha=0$; (c) for a given choice of $T$ and $P$,
$\lambda_{1}<\lambda_{2}$ in the range $0\leq\alpha\leq 1$ and hence $q$ is
minimised when $\alpha=1$. However, we note that this final case cannot occur;
it suffices to check that $\lambda_{1}(\alpha=1)>\lambda_{2}(\alpha=1)$, and
from the expressions in (S60) we have that $\lambda_{1}(\alpha=1)=1$ and
$\lambda_{2}(\alpha=1)=0$. As a visual aid for the remaining two cases, see
Fig. S2. In case (a),

$q=\lambda_{1}=\lambda_{2}=\frac{1}{2}+\frac{1}{2}\left(\frac{T+P^{2}}{T+P^{2}+4P(1+T)}\right).$
(S62)

In case (b), we have that

$q=\lambda_{1}(0,P,T)=\frac{T+P^{2}}{(1+P)(P+T)}.$ (S63)

We must also minimise w.r.t. $\phi$; however, we can safely minimise w.r.t.
$P$ as $\partial_{\phi}P>0$ (unless $\phi=0$, but in this case $q=1$ and the
strategy fails). In case (b), we have

$\frac{\partial q}{\partial P}=\frac{(P^{2}-T)(1+T)}{(1+P)^{2}(P+T)^{2}}.$
(S64)

In this case, consider the two points implicitly defined by the constraint
$\lambda_{1}(0,P,T)=\lambda_{2}(0,P,T)$ (drawn as the black points in Fig.
S2). Denote these points $f^{\pm}(T)$. It can be readily checked that in case
(b), $\partial_{P}q<0$ for any $q<f^{-}(T)$, and $\partial_{P}q>0$ for any
$q>f^{+}(T)$. Thus the minimum w.r.t $P$ must occur when
$\lambda_{1}(0,P,T)=\lambda_{2}(0,P,T)$ and hence we can restrict our
attention to case (a) (note Fig. S2). In this case, $\partial_{P}q$ becomes

$\frac{\partial q}{\partial P}=\frac{-2(1+T)(T-P^{2})}{[T+4PT+P(4+P)]^{2}}=0,$
(S65)

which implies that $P=\sqrt{T}$. Substituting in the optimal choices for the
parameters $\\{\alpha,P\\}$ and reexpressing solely in terms of $\theta$ gives
the optimal strategy

$\Omega^{opt}=\frac{2-\sin(2\theta)}{4+\sin(2\theta)}P^{+}_{ZZ}+\frac{2(1+\sin(2\theta))}{4+\sin(2\theta)}\Omega_{3}^{opt},$
(S66)

where $\Omega_{3}^{opt}$ is given by

$\Omega_{3}^{opt}=\mathds{1}-\frac{1}{(1+t)^{2}}\begin{pmatrix}1&0&0&-t\\\
0&t&0&0\\\ 0&0&t&0\\\ -t&0&0&t^{2}\end{pmatrix},\quad t=\tan\theta.$ (S67)

This strategy accepts an orthogonal state with probability

$q_{opt}=\frac{2+\sin(2\theta)}{4+\sin(2\theta)},$ (S68)

implying that the number of measurements needed to verify to within accuracy
$\epsilon$ and with statistical power $1-\delta$ under this test is

$n_{opt}=\frac{\ln\delta^{-1}}{\ln((1-\Delta_{\epsilon})^{-1})}=\frac{\ln\delta^{-1}}{\ln((1-\epsilon(1-q^{opt}))^{-1})}\approx(2+\sin\theta\cos\theta)\epsilon^{-1}\ln\delta^{-1}.$
(S69)

The final step is to show that the operator $\Omega_{3}^{opt}$ can be
decomposed into a small set of locally implementable, projective measurements.
We can do so with a strategy involving only three terms:

$\Omega_{3}^{opt}=\frac{1}{3}\left[\sum_{k=1}^{3}(\mathds{1}-{|{\phi_{k}}\rangle}\\!{\langle{\phi_{k}}|})\right],$
(S70)

where the set of separable states $\\{{|{\phi_{k}}\rangle}\\}$ are the
following:

$\displaystyle{|{\phi_{1}}\rangle}$
$\displaystyle=\left(\frac{1}{\sqrt{1+\tan\theta}}{|{0}\rangle}+\frac{e^{\frac{2\pi
i}{3}}}{\sqrt{1+\cot\theta}}{|{1}\rangle}\right)\otimes\left(\frac{1}{\sqrt{1+\tan\theta}}{|{0}\rangle}+\frac{e^{\frac{\pi
i}{3}}}{\sqrt{1+\cot\theta}}{|{1}\rangle}\right),$ (S71)
$\displaystyle{|{\phi_{2}}\rangle}$
$\displaystyle=\left(\frac{1}{\sqrt{1+\tan\theta}}{|{0}\rangle}+\frac{e^{\frac{4\pi
i}{3}}}{\sqrt{1+\cot\theta}}{|{1}\rangle}\right)\otimes\left(\frac{1}{\sqrt{1+\tan\theta}}{|{0}\rangle}+\frac{e^{\frac{5\pi
i}{3}}}{\sqrt{1+\cot\theta}}{|{1}\rangle}\right),$ (S72)
$\displaystyle{|{\phi_{3}}\rangle}$
$\displaystyle=\left(\frac{1}{\sqrt{1+\tan\theta}}{|{0}\rangle}+\frac{1}{\sqrt{1+\cot\theta}}{|{1}\rangle}\right)\otimes\left(\frac{1}{\sqrt{1+\tan\theta}}{|{0}\rangle}-\frac{1}{\sqrt{1+\cot\theta}}{|{1}\rangle}\right),$
(S73)

which gives a strategy of the required form. ∎

Figure S1: Shaded region: unreachable parameters given a strategy $\Omega$
that is both local and of the form $\Omega=\alpha
P^{+}_{ZZ}+(1-\alpha)\Omega_{3}$, where $\Omega_{3}$ is the trace 3 part.
Here, $\theta=\frac{\pi}{8}$.

Figure S2: A contour map of the function
$q(\alpha,\phi)=\max\\{\lambda_{1}(\alpha,\phi),\lambda_{2}(\alpha,\phi)\\}$
for $\theta=\frac{\pi}{8}$, where the pair $(\lambda_{1},\lambda_{2})$ are
given in S60. The pink curve denotes the minimum w.r.t $\alpha$ given fixed
$\phi$. Above the curve, $\lambda_{1}>\lambda_{2}$; below,
$\lambda_{1}<\lambda_{2}$.

We now briefly treat the special cases that were omitted from the above proof:
$\theta=0,\frac{\pi}{4},\frac{\pi}{2}$.

$\mathit{\theta=0,\theta=\frac{\pi}{2}}$: In these cases, the state
${|{\psi}\rangle}={|{00}\rangle}$ or ${|{\psi}\rangle}={|{11}\rangle}$. Then
the globally optimal strategy, just projecting onto ${|{\psi}\rangle}$, is an
allowed local measurement. Thus in these cases the optimal strategy is to just
apply the projector ${|{00}\rangle}\\!{\langle{00}|}$ or
${|{11}\rangle}\\!{\langle{11}|}$. Given this strategy we have that $p=1$ and
$q=0$, giving a scaling of the number of measurements required as

$n_{opt}\approx\epsilon^{-1}\ln\delta^{-1}.$ (S74)

$\mathit{\theta=\frac{\pi}{4}}$: This case is treated explicitly in the main
body. The optimal strategy is to perform the Pauli measurements $XX$, $-YY$
and $ZZ$ with equal weight; i.e.

$\Omega=\frac{1}{3}(P^{+}_{XX}+P^{+}_{-YY}+P^{+}_{ZZ}),$ (S75)

where $P^{+}_{M}$ is the projector onto the positive eigensubspace of the
operator $M$. In this case, the number of measurements required is

$n_{opt}\approx\frac{3}{2}\epsilon^{-1}\ln\delta^{-1}.$ (S76)

##  Appendix D Stabilizer states

We now discuss verification strategies for stabilizer states. We take
${|{\psi}\rangle}$ to be a stabilizer state of $N$ qubits, namely that there
exists a generating set of $N$ commuting Pauli operators $M_{1},\dots,M_{N}$
on $N$ qubits such that $M_{i}{|{\psi}\rangle}={|{\psi}\rangle}$ for all $i$.
Stabilizer states are ubiquitous in various areas of quantum information, for
example in quantum error correction and measurement-based quantum computing;
for an introduction to the stabilizer formalism, see Gottesman (1997, 1996)
and Nielsen and Chuang (2010) Sec 10.5. We will describe below a strategy
constructed from only stabilizer measurements that accepts ${|{\psi}\rangle}$
with certainty, and hence achieves the same asymptotic scaling in the number
of required measurements with respect to $\epsilon$ as the two-qubit case
above. However, we do not rule out that there may be non-stabilizer strategies
that give a small constant factor improvement over the strategy defined here.

######  Theorem 5.

Write a stabilizer state ${|{\psi}\rangle}$ and strategy
$\Omega=\sum_{j=1}^{K}\mu_{j}P_{j}$, where the set $\\{P_{j}\\}$ are the
projectors onto the positive eigenspace of $K$ linearly independent
stabilizers of ${|{\psi}\rangle}$, for $K\leq 2^{N}-1$. Then the optimal
choice of the parameter $K$ and weights $\mu_{j}$ are
$K=2^{N}-1;\;\mu_{j}=\frac{1}{2^{N}-1}$ for all $j$. The number of
measurements needed to verify to within fidelity $\epsilon$ and statistical
power $1-\delta$ is then

$n_{opt}^{stab}\approx\frac{2^{N}-1}{2^{(N-1)}}\epsilon^{-1}\ln\frac{1}{\delta}.$
(S77)

###### Proof.

Recall that as the verifier accepts ${|{\psi}\rangle}$ with certainty, we are
concerned with the optimisation of $\Delta_{\epsilon}$, which can be written
as

$\displaystyle\Delta_{\epsilon}$
$\displaystyle=\max_{\Omega}\min_{{|{\psi^{\bot}}\rangle}}\epsilon(1-{\langle{\psi^{\bot}}|}\Omega{|{\psi^{\bot}}\rangle})$
(S78)
$\displaystyle=\epsilon(1-\min_{\Omega}\max_{{|{\psi^{\bot}}\rangle}}{\langle{\psi^{\bot}}|}\Omega{|{\psi^{\bot}}\rangle}),$
(S79)

where the maximisation is over positive matrices $\Omega$ such that
$\Omega{|{\psi}\rangle}={|{\psi}\rangle}$.

Now consider $\Omega$ written as a matrix in the basis
$\\{{|{\psi}\rangle},{|{\psi_{j}^{\bot}}\rangle}\\}$, $j=1\ldots(2^{N}-1)$
where the states ${|{\psi_{j}^{\bot}}\rangle}$ are mutually orthogonal and all
orthogonal to ${|{\psi}\rangle}$. Given that
$\Omega{|{\psi}\rangle}={|{\psi}\rangle}$, we know that
${\langle{\psi_{j}^{\bot}}|}\Omega{|{\psi}\rangle}=0\;\forall j$. Then in this
basis $\Omega$ can be written

$\Omega=\begin{pmatrix}1&\mathbf{0}^{\top}\\\
\mathbf{0}&\mathbf{M}\end{pmatrix},$ (S80)

where $\mathbf{0}$ is the $(2^{N}-1)$-dimensional zero vector and $\mathbf{M}$
is a $(2^{N}-1)\times(2^{N}-1)$ Hermitian matrix. Then $\Omega$ must be
writable as
$\Omega={|{\psi}\rangle}\\!{\langle{\psi}|}+\sum_{j=1}^{2^{N}-1}\nu_{j}{|{\phi_{j}}\rangle}\\!{\langle{\phi_{j}}|}$,
where $\sum_{j}\nu_{j}{|{\phi_{j}}\rangle}\\!{\langle{\phi_{j}}|}$ is the
spectral decomposition of $\mathbf{M}$. Given this decomposition, the
optimisation for the adversary is straightforward – pick
${|{\psi^{\bot}}\rangle}$ to be the eigenstate in the decomposition of
$\mathbf{M}$ with largest eigenvalue:
${|{\psi^{\bot}}\rangle}={|{\phi_{max}}\rangle}$ where
$\nu_{max}=\max_{j}\nu_{j}$. Then

$\Delta_{\epsilon}=\epsilon(1-\min_{\Omega}{\langle{\phi_{max}}|}\Omega{|{\phi_{max}}\rangle})=\epsilon(1-\min_{\Omega}\nu_{max}).$
(S81)

Given this choice by the adversary, the verifier is then forced to set the
strategy such that all the eigenvalues of $\mathbf{M}$ are equal; i.e. that
$\mathbf{M}=a\mathds{1}$ for some constant $a$. To see this, consider an
alternative strategy where the eigenvalues $\nu_{j}$ are not equal. Now,
consider rewriting $\Omega$ in terms of stabilizers of ${|{\psi}\rangle}$. For
any stabilizer (i.e. tensor product of Paulis, perhaps with an overall phase)
$M$ over $N$ qubits, the projector onto the positive eigensubspace has
$\operatorname{tr}(P_{M}^{+})=2^{N-1}$. Given that $\Omega$ is built from a
convex combination of these projectors, and recalling from Lemma 4 that
$\Omega$ does not contain an identity term, we also know that
$\operatorname{tr}(\Omega)=2^{N-1}$. However, we have also expanded $\Omega$
as
$\Omega={|{\psi}\rangle}\\!{\langle{\psi}|}+\sum_{j}\nu_{j}{|{\phi_{j}}\rangle}\\!{\langle{\phi_{j}}|}$,
and so

$\operatorname{tr}(\Omega)=1+\sum_{j}\nu_{j}=2^{N-1}.$ (S82)

Then, it is straightforward to see that decreasing any eigenvalue below $a$
must result in an increase in at least one other eigenvalue in order to
maintain this equality, and hence would increase the value of $\nu_{max}$.
Thus the optimal choice for the verifier is to set
$\Omega={|{\psi}\rangle}\\!{\langle{\psi}|}+a\mathds{1}^{\bot}$, where
$\mathds{1}^{\bot}$ is the identity matrix on the subspace orthogonal to
${|{\psi}\rangle}$. Taking the trace of this expression gives

$\operatorname{tr}[{|{\psi}\rangle}\\!{\langle{\psi}|}+a\mathds{1}^{\bot}]=1+(2^{N}-1)a=2^{N-1}.$
(S83)

This can be rearranged for $a$ and then substituted into the expression for
$\Delta_{\epsilon}$, which gives

$\Delta_{\epsilon}=\frac{2^{(N-1)}}{2^{N}-1}\epsilon,$ (S84)

or that the number of stabilizer measurements required to verify
${|{\psi}\rangle}$ is bounded below by

$n_{opt}^{stab}\approx\frac{2^{N}-1}{2^{(N-1)}}\epsilon^{-1}\ln\delta^{-1}.$
(S85)

The optimal
$\Omega={|{\psi}\rangle}\\!{\langle{\psi}|}+\frac{2^{(N-1)}-1}{2^{N}-1}\mathds{1}^{\bot}$
and the optimal scaling above can be achieved by decomposing $\Omega$ into a
strategy involving a maximal set (excluding the identity) of $2^{N}-1$
linearly independent stabilizers, all with equal weight. To see this note that
for a stabilizer group of a state ${|{\psi}\rangle}$ of $N$ qubits, there are
$2^{N}$ linearly independent stabilizers (including the identity element).
Denote these stabilizers $\\{M_{i},i=1\ldots 2^{N}\\}$. Then, we make use of
the fact that Hein (2005)

$\frac{1}{2^{N}}\sum_{i=1}^{2^{N}}M_{i}={|{\psi}\rangle}\\!{\langle{\psi}|}.$
(S86)

Explicitly extracting the identity element gives

$\sum_{i=1}^{2^{N}-1}M_{i}=2^{N}{|{\psi}\rangle}\\!{\langle{\psi}|}-\mathds{1}.$
(S87)

Now, each stabilizer (for any $N$) is a two outcome measurement and so we can
make use of the fact that $M_{i}$ can be written in terms of the projector
onto the positive eigenspace of $M_{i}$, denoted $P^{+}_{i}$, as
$M_{i}=2P^{+}_{i}-\mathds{1}$. Substituting in this expression and rearranging
gives

$\sum_{i=1}^{2^{N}-1}P^{+}_{i}=2^{(N-1)}{|{\psi}\rangle}\\!{\langle{\psi}|}+(2^{(N-1)}-1)\mathds{1}.$
(S88)

Then normalising this expression over $2^{N}-1$ stabilizers yields

$\displaystyle\frac{1}{2^{N}-1}\sum_{i=1}^{2^{N}-1}P^{+}_{i}$
$\displaystyle=\frac{2^{(N-1)}}{2^{N}-1}{|{\psi}\rangle}\\!{\langle{\psi}|}+\frac{2^{(N-1)}-1}{2^{N}-1}\mathds{1}$
$\displaystyle=\frac{2^{(N-1)}+2^{(N-1)}-1}{2^{N}-1}{|{\psi}\rangle}\\!{\langle{\psi}|}+\frac{2^{(N-1)}-1}{2^{N}-1}\mathds{1}^{\bot}$
$\displaystyle={|{\psi}\rangle}\\!{\langle{\psi}|}+\frac{2^{(N-1)}-1}{2^{N}-1}\mathds{1}^{\bot}=\Omega,$
(S89)

where $\mathds{1}^{\bot}$ is the identity matrix on the subspace orthogonal to
${|{\psi}\rangle}$, as required. ∎

Note that for growing $N$, the quantity $n_{opt}^{stab}$ given in Eq. S85 is
bounded above by $2\epsilon^{-1}\ln\delta^{-1}$, which does not depend on $N$,
and implies that this stabilizer strategy requires at most a factor of two
more measurements than the optimal non-local verification strategy (just
projecting onto ${|{\psi}\rangle}$).

One could also consider a reduced strategy that involves measuring fewer
stabilizers. However, given a state of $N$ qubits and a set of $k$
stabilizers, the dimension of the subspace stabilized by this set is at least
$2^{N-k}$. Thus for any choice of $k<N$, there must always exist at least one
state ${|{\psi^{\bot}}\rangle}$ orthogonal to ${|{\psi}\rangle}$ that is
stabilized by every stabilizer in the set. Then, the adversary can construct a
$\sigma$ that always accepts, implying that the verifier has no discriminatory
power between ${|{\psi}\rangle}$ and $\sigma$ and thus the strategy fails.
Consider instead constructing a strategy from the $N$ stabilizer generators of
${|{\psi}\rangle}$, with corresponding projectors $\\{P^{s.g.}_{j}\\}$. Then,
$\Omega=\sum_{j}\mu_{j}P^{s.g.}_{j}$. The set of projectors
$\\{P^{s.g.}_{j}\\}$ commute and so share a common eigenbasis, denoted
$\\{{|{\lambda_{j}}\rangle}\\}$. To optimise this strategy over the weights
$\mu_{j}$, we first need the following lemma:

######  Lemma 6.

Write the unique sets of $N-1$ independent stabilizer generators of
${|{\psi}\rangle}$, $S_{k}=\\{M_{j},j=1\ldots N\\}\setminus M_{k}$, $k=1\ldots
N$. Then each $S_{k}$ corresponds to a state ${|{\lambda_{k}}\rangle}$,
$\braket{\lambda_{k}}{\psi}=0$, such that
$\braket{\lambda_{k}}{\lambda_{l}}=\delta_{kl}$.

###### Proof.

Each set $S_{k}$ stabilizes a space of dimension two, and so a
${|{\lambda_{k}}\rangle}$ where $\braket{\lambda_{k}}{\psi}=0$ exists.
Moreover, the stabilizer generators define an orthogonal eigenbasis of which
${|{\lambda_{k}}\rangle}$ is an element. To show that two sets $S_{k}$ and
$S_{l}$, $k\neq l$, define distinct eigenvectors, assume the converse; that
${|{\lambda_{k}}\rangle}\propto{|{\lambda_{l}}\rangle}$. However, then the set
$S=S_{k}\cup S_{l}$ would stabilize ${|{\lambda_{k}}\rangle}$, which is a
contradiction as $S$ is the full set of stabilizer generators and uniquely
stabilizes ${|{\psi}\rangle}$. ∎

We can now derive the optimal stabilizer generator strategy.

######  Theorem 7.

For a stabilizer state ${|{\psi}\rangle}$ and strategy
$\Omega=\sum_{j=1}^{N}\mu_{j}P^{s.g.}_{j}$, where the set $\\{P^{s.g.}_{j}\\}$
are the projectors onto the positive eigenspace of the stabilizer generators
of ${|{\psi}\rangle}$, the optimal choice of the weights $\mu_{j}$ is
$\mu_{j}=\frac{1}{N}$, for all $j$. The number of measurements needed to
verify to within fidelity $\epsilon$ and statistical power $1-\delta$ is then

$n^{s.g.}_{opt}\approx\frac{N}{\epsilon}\ln\frac{1}{\delta}.$ (S90)

###### Proof.

If we write a state orthogonal to ${|{\psi}\rangle}$ in the stabilizer
eigenbasis as
${|{\psi^{\bot}}\rangle}=\sum_{k}\alpha_{k}{|{\lambda_{k}}\rangle}$, we have
that

$\displaystyle{\langle{\psi^{\bot}}|}\Omega{|{\psi^{\bot}}\rangle}$
$\displaystyle=\sum_{k,m=1}^{2^{N}}\sum_{j=1}^{N}\bar{\alpha}_{k}\alpha_{m}\mu_{j}{\langle{\lambda_{k}}|}P^{s.g.}_{j}{|{\lambda_{m}}\rangle}$
$\displaystyle=\sum_{k,m=1}^{2^{N}}\sum_{j=1}^{N}\bar{\alpha}_{k}\alpha_{m}\mu_{j}\delta_{km}\epsilon_{jk}$
$\displaystyle=\sum_{k=1}^{2^{N}}\sum_{j=1}^{N}|\alpha_{k}|^{2}\mu_{j}\epsilon_{jk}\coloneqq\sum_{k=1}^{2^{N}}|\alpha_{k}|^{2}E_{k},$
(S91)

where $\epsilon_{jk}=1$ if
$P_{j}{|{\lambda_{k}}\rangle}={|{\lambda_{k}}\rangle}$ and zero otherwise.
This quantity is the _parity-check matrix_ for the set of stabilizers
$\\{P_{j}^{s.g.}\\}$. The quantity of interest with respect to verification is

$q=\min_{\Omega}\max_{{|{\psi^{\bot}}\rangle}}{\langle{\psi^{\bot}}|}\Omega{|{\psi^{\bot}}\rangle}=\min_{\mu_{j}}\max_{\alpha_{k}}\sum_{j,k}|\alpha_{k}|^{2}\mu_{j}\epsilon_{jk},$
(S92)

where the verifier’s minimisation is over the probabilities $\mu_{j}$ with
which a stabilizer generator indexed by $j$ is drawn in the protocol, and the
adversary maximises over the set of amplitudes $\alpha_{k}$ that describes the
state most likely to fool the verifier. Lemma 6 gives that, from the full set
of $2^{N}$ basis states ${|{\lambda_{k}}\rangle}$, there is a subset of $N$
basis states ${|{\lambda_{\tilde{k}}}\rangle}$, $\tilde{k}\in I$ for $|I|=N$,
stabilized by exactly $N-1$ generators; thus for basis states in this subset,
the quantity $\epsilon_{j\tilde{k}}=1-\delta_{j\tilde{k}}$. Then we can
compute the summation over $j$ as

$E_{\tilde{k}}=\sum_{j}\mu_{j}\epsilon_{j\tilde{k}}=\sum_{j}\mu_{j}(1-\delta_{j\tilde{k}})=1-\mu_{\tilde{k}},$
(S93)

using the fact that $\sum_{j}\mu_{j}=1$. Now, each element of $E_{k}$ for
$k\notin I$ is a summation of at most $N-2$ terms, $\mu_{j}$. Thus there
always exists another element $E_{\tilde{k}}$ for $\tilde{k}\in I$ that is at
least as large; and so it is never detrimental to the adversary to shift any
amplitude on the basis state labelled by $k$ to the basis state labelled by
$\tilde{k}$. Thus the optimal choice for the adversary’s state is
${|{\psi^{\bot}}\rangle}\in\text{span}\\{{|{\lambda_{\tilde{k}}}\rangle}:\tilde{k}\in
I\\}$. Given this choice by the adversary, we have that

$q=\min_{\mu_{\tilde{k}}}\max_{\alpha_{\tilde{k}}}\sum_{\tilde{k}}|\alpha_{\tilde{k}}|^{2}(1-\mu_{\tilde{k}})=\min_{\mu_{\tilde{k}}}\max_{\tilde{k}}(1-\mu_{\tilde{k}}).$
(S94)

It is straightforward to see that the optimal choice for the verifier is to
have $\mu_{\tilde{k}}=\frac{1}{N}$, for all $\tilde{k}$; then
$\Omega=\frac{1}{N}\sum{P_{j}^{s.g.}}$. Thus

$q=1-\frac{1}{N}\Rightarrow
n^{s.g.}_{opt}\approx\frac{N}{\epsilon}\ln\frac{1}{\delta}.$ (S95)

∎

Clearly, this scaling is much poorer in $N$ than in the case where the full
set of $2^{N}-1$ linearly independent stabilizers are allowed; indicating a
trade-off between the total number of required measurements and the accessible
number of measurement settings, in this case.

##  Appendix E Concentration inequalities and the relative entropy

In a binary hypothesis test between hypotheses $H_{0}$ and $H_{1}$, the Type I
and Type II errors are, respectively,

Type I $\displaystyle:\quad$ $\displaystyle\text{Pr}[\text{Guess
}H_{1}|H_{0}]$ (S96) Type II $\displaystyle:$
$\displaystyle\text{Pr}[\text{Guess }H_{0}|H_{1}].$ (S97)

In general, in designing an effective hypothesis test there will be a trade-
off between the relative magnitude of these types of error; they cannot be
arbitrarily decreased simultaneously. In an _asymmetric_ hypothesis test, the
goal is to minimise one of these errors given a fixed upper bound on the
other. In this addendum, we prove the following proposition in the context of
asymmetric hypothesis testing:

######  Proposition 8.

Any strategy $\Omega$ that: (a) accepts ${|{\psi}\rangle}$ with certainty,
$p\coloneqq\operatorname{tr}(\Omega{|{\psi}\rangle}\\!{\langle{\psi}|})=1$;
and (b) does not accept $\sigma$ with certainty ($\Delta_{\epsilon}>0$)
requires asymptotically fewer measurements in infidelity $\epsilon$ to
distinguish these states to within a fixed Type II error than the best
protocol based on a strategy $\Omega^{\prime}$ where
$\operatorname{tr}(\Omega^{\prime}{|{\psi}\rangle}\\!{\langle{\psi}|})<1$.

We have inherited notation regarding verification strategies from Appendix A.
Here, hypothesis $H_{0}$ corresponds to accepting the target
${|{\psi}\rangle}$, and hypothesis $H_{1}$ corresponds to accepting the
alternative (that the output was far from ${|{\psi}\rangle}$). Proposition 8
states that, in a framework where we attempt to verify ${|{\psi}\rangle}$ by
repeatedly making two-outcome measurements picked from some set,
asymptotically it is always beneficial to use measurements that accept
${|{\psi}\rangle}$ with certainty. In this case, each measurement is a
Bernoulli trial with some acceptance probability. An example of a protocol
which would not satisfy this property would be estimating the probability of
violating a Bell inequality for a maximally entangled 2-qubit state
${|{\psi}\rangle}$.

In general, the optimum asymptotic rate at which the Type II error can be
minimised in an asymmetric hypothesis test is given by the _Chernoff-Stein
lemma_ :

######  Theorem 9 (Cover and Thomas Cover and Thomas (2006), Theorem 11.8.3.).

Let $X_{1},X_{2}\ldots X_{n}$ be drawn i.i.d. from a probability mass function
$Q$. Then consider the hypothesis test between alternatives $H_{0}$: $Q=P_{0}$
and $H_{1}$: $Q=P_{1}$. Let $A_{n}$ be an acceptance region for the null
hypothesis $H_{0}$; i.e. it is a set consisting of all possible strings of
outcomes with which the conclusion $H_{0}$ is drawn. Denote Type I and Type II
errors after $n$ samples as $\alpha_{n}^{*}$ and $\beta_{n}^{*}$,
respectively. Then for some constraint parameter $0<\chi<\frac{1}{2}$, define

$\delta_{n}^{\chi}=\min_{\begin{subarray}{c}A_{n}\\\
\alpha_{n}^{*}<\chi\end{subarray}}\beta_{n}^{*}.$

Then asymptotically

$\lim_{n\rightarrow\infty}\frac{1}{n}\ln\delta_{n}^{\chi}=-D(P_{0}\ \|P_{1}),$

where $D(P_{0}\|P_{1})$ is the relative entropy between probability
distributions $P_{0}$ and $P_{1}$.

For clarity we drop the sub- and superscript
$\delta_{n}^{\chi}\rightarrow\delta$. The relative entropy typically takes a
pair of probability distributions as arguments, but given that each hypothesis
is concerned only with a single Bernoulli-distributed random variable uniquely
specified by a a pair of real parameters (the quantities $p$ and
$p-\Delta_{\epsilon}$), we will use the shorthand $D(p\|q)$ for real variables
$p$ and $q$. In this case the relative entropy can be expanded as

$D(a\|b)=a\ln\frac{a}{b}+(1-a)\ln\frac{1-a}{1-b}.$ (S98)

Note that in the limit where $a\rightarrow 1$, using that $\lim_{a\rightarrow
1^{-}}(1-a)\ln(1-a)=0$, this expression becomes

$\lim_{a\rightarrow 1^{-}}D(a\|b)=\ln\frac{1}{b}.$ (S99)

After rearranging the expression for the optimal asymptotic Type II error
given by the Chernoff-Stein lemma, we can achieve a test with statistical
power $1-\delta$ by taking a number of measurements

$n>\frac{1}{D\left(p\|p-\Delta_{\epsilon}\right)}\ln\frac{1}{\delta}.$ (S100)

Moreover, this bound is tight in that it gives the correct asymptotic
relationship between $n$, $D$ and $\delta$; generically $\delta$ can be lower
bounded (Cover and Thomas (2006), p666) such that

$\frac{e^{-Dn}}{n+1}\leq\delta\leq e^{-Dn}.$ (S101)

Two important limiting cases of this expression have relevance here. Firstly,
if $p\gg\Delta_{\epsilon}$, then Taylor expanding $n$ for small
$\Delta_{\epsilon}$ gives that it is sufficient to take

$n\geq\frac{2p(1-p)}{\Delta_{\epsilon}^{2}}\ln\frac{1}{\delta}.$ (S102)

Secondly, if $p=1$, then it is sufficient to take

$n\geq\frac{-1}{\ln\left(1-\Delta_{\epsilon}\right)}\ln\frac{1}{\delta}\approx\frac{1}{\Delta_{\epsilon}}\ln\frac{1}{\delta},$
(S103)

which is in agreement with the scaling previously derived in Eq. S1. These are
the limiting cases of the scaling of $n$ with $\Delta_{\epsilon}$. In the
worst case, $n$ scales quadratically in $\Delta_{\epsilon}^{-1}$; however, for
any strategy where the state ${|{\psi}\rangle}$ to be tested is accepted with
certainty, only a total number of measurements linear in
$\Delta_{\epsilon}^{-1}$ are required. Thus asymptotically, a strategy where
$p=1$ is always favourable (i.e. gives a quadratic improvement in scaling with
$\Delta_{\epsilon}$) for any $\Delta_{\epsilon}>0$.

## References

  * Häffner  _et al._ (2005) H. Häffner, W. Hänsel, C. F. Roos, J. Benhelm, D. Chek-al Kar, M. Chwalla, T. Körber, U. D. Rapol, M. Riebe, P. O. Schmidt, C. Becher, O. Gühne, W. Dür, and R. Blatt, Nature 438, 643 (2005).
  * Carolan  _et al._ (2014) J. Carolan, J. D. A. Meinecke, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing, Nature Photonics 8, 621 (2014).
  * Laing and O’Brien (2012) A. Laing and J. L. O’Brien, arXiv:1208.2868 (2012).
  * Lvovsky and Raymer (2009) A. I. Lvovsky and M. G. Raymer, Reviews of Modern Physics 81, 299 (2009).
  * Bellini  _et al._ (2012) M. Bellini, A. S. Coelho, S. N. Filippov, V. I. Man’ko, and A. Zavatta, Physical Review A 85, 052129 (2012).
  * Amosov  _et al._ (2012) G. G. Amosov, Y. A. Korennoy, and V. I. Man’ko, Physical Review A 85, 052119 (2012).
  * Flammia  _et al._ (2012) S. T. Flammia, D. Gross, Y.-K. Liu, and J. Eisert, New Journal of Physics 14, 095022 (2012).
  * Gross  _et al._ (2010) D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert, Physical Review Letters 105, 150401 (2010).
  * Cramer  _et al._ (2010) M. Cramer, M. B. Plenio, S. T. Flammia, R. Somma, D. Gross, S. D. Bartlett, O. Landon-Cardinal, D. Poulin, and Y.-K. Liu, Nature Communications 1, 149 (2010).
  * Tóth and Gühne (2005a) G. Tóth and O. Gühne, Physical Review Letters 94, 060501 (2005a).
  * Tóth and Gühne (2005b) G. Tóth and O. Gühne, Physical Review A 72, 022340 (2005b).
  * Sugiyama  _et al._ (2013) T. Sugiyama, P. S. Turner, and M. Murao, Physical Review Letters 111, 160406 (2013).
  * Flammia and Liu (2011) S. T. Flammia and Y.-K. Liu, Physical Review Letters 106, 230501 (2011).
  * Vaidman and Yoran (1999) L. Vaidman and N. Yoran, Physical Review A 59, 116 (1999).
  * Calsamiglia and Lütkenhaus (2001) J. Calsamiglia and N. Lütkenhaus, Applied Physics B 72, 67 (2001).
  * Ewert and van Loock (2014) F. Ewert and P. van Loock, Physical Review Letters 113, 140403 (2014).
  * Mayers and Yao (2004) D. Mayers and A. Yao, Quantum Information & Computation 4, 273 (2004).
  * McKague  _et al._ (2012) M. McKague, T. H. Yang, and V. Scarani, Journal of Physics A: Mathematical and Theoretical 45, 455304 (2012).
  * Yang and Navascués (2013) T. H. Yang and M. Navascués, Physical Review A 87, 050102 (2013).
  * Sugiyama (2014) T. Sugiyama,  _Finite Sample Analysis in Quantum Estimation_ (Springer, 2014).
  * da Silva  _et al._ (2011) M. P. da Silva, O. Landon-Cardinal, and D. Poulin, Physical Review Letters 107, 210404 (2011).
  * Ferrie and Blume-Kohout (2016) C. Ferrie and R. Blume-Kohout, Physical Review Letters 116, 090407 (2016).
  * Struchalin  _et al._ (2016) G. I. Struchalin, I. A. Pogorelov, S. S. Straupe, K. S. Kravtsov, I. V. Radchenko, and S. P. Kulik, Physical Review A 93, 012103 (2016).
  * Mahler  _et al._ (2013) D. H. Mahler, L. A. Rozema, A. Darabi, C. Ferrie, R. Blume-Kohout, and A. M. Steinberg, Physical Review Letters 111, 183601 (2013).
  * Haah  _et al._ (2016) J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu, in  _Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016_ (ACM Press, New York, New York, USA, 2016) pp. 913–925.
  * Bădescu  _et al._ (2017) C. Bădescu, R. O’Donnell, and J. Wright, arXiv:1708.06002 (2017).
  * Dimić and Dakić (2017) A. Dimić and B. Dakić, arXiv:1705.06719 (2017).
  * Gottesman (1997) D. Gottesman,  _Stabilizer Codes and Quantum Error Correction_ , Ph.D. thesis, Caltech (1997).
  * Gottesman (1996) D. Gottesman, Physical Review A 54, 1862 (1996).
  * Nielsen and Chuang (2010) M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (Cambridge University Press, 2010) p. 676.
  * Hein (2005) M. Hein,  _Entanglement in graph states_ , Ph.D. thesis, University of Innsbruck (2005).
  * Cover and Thomas (2006) T. M. Cover and J. A. Thomas,  _Elements of Information Theory_ (Wiley-Interscience, 2006).