{'fraction_non_alphanumeric': 0.055405560661764705, 'fraction_numerical': 0.014562270220588236, 'mean_word_length': 4.096911140389401, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 26, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Fidelity witnesses for fermionic quantum simulations

The experimental interest and developments in quantum spin-1/2-chains has increased uninterruptedly over the last decade. In many instances, the target quantum simulation belongs to the broader class of non-interacting fermionic models, constituting an important benchmark. In spite of this class being analytically efficiently tractable, no direct certification tool has yet been reported for it. In fact, in experiments, certification has almost exclusively relied on notions of quantum state tomography scaling very unfavorably with the system size. Here, we develop experimentally-friendly fidelity witnesses for all pure fermionic Gaussian target states. Their expectation value yields a tight lower bound to the fidelity and can be measured efficiently. We derive witnesses in full generality in the Majorana-fermion representation and apply them to experimentally relevant spin-1/2 chains. Among others, we show how to efficiently certify strongly out-of-equilibrium dynamics in critical Ising chains. At the heart of the measurement scheme is a variant of importance sampling specially tailored to overlaps between covariance matrices. The method is shown to be robust against finite experimental-state infidelities.

Quantum simulators are specific-purpose quantum devices that are able to efficiently simulate phenomena of interest thought to be not directly accessible otherwise [1]. Already at scales of tens of particles they have the potential to outperform today's most powerful supercomputers and help us explain unclear physical effects, as well as give boosts in crucial technological areas [2]. In addition, they constitute an intermediate milestone towards the ultimate goal of realizing largescale universal quantum computers. This has fuelled impressive experimental advances in multiple quantum technologies [3][4][5][6][7][8]. A type of quantum many-body systems to whom experimental simulations have devoted considerable efforts over the last decade are given by one-dimensional (1D) lattices of interacting spin-1/2 particles, or spin-1/2 chains, for short. In particular, even though they call into the efficiently classically simulable regime, the well-known transverse-field (TF) Ising and XY models have risen to constitute important basic testbeds for the most advances experimental simulations, e.g. with ion-trap [9][10][11][12], superconducting-circuit [13] and circuit quantum electrodynamics [14] platforms.
At least two facts justify the significant interest in these specific models. The first one is that they display a vast physical richness: For instance, the TF Ising model-which is, actually, a subclass of the TF XY model-features a quantum phase transition [15][16][17][18] as well as topologically and spectrally interesting effects [19][20][21][22][23], and is relevant for quantum speed-ups in certain optimization problems [24]. The second one is that, for nearest-neighbor interactions, they can be analytically solved, e.g. by mapping them into systems of freei.e., non-interacting-fermions [15]. This allows for in-depth theoretical studies of their dynamics [25][26][27][28][29][30]. From a broader perspective, these models belong to a more general class of exactly solvable systems known as non-interacting quantum systems, also referred to as fermionic linear optics [31][32][33][34][35][36][37].
This class is the fermionic counterpart of the Gaussian formalism for bosons [38,39], which plays a major role in quantum information and quantum optics. It includes, e.g., tightbinding models important in condensed-matter physics, certain interacting bosonic chains that can be fermionized [40][41][42], and spin-1/2 systems in 2-dimensional lattices, such as the celebrated Kitaev's honeycomb model [35], which exhibits non-Abelian excitations.
Unfortunately, the exact analytical solution of a model does not imply that one can efficiently certify the correctness of an uncharacterised experimental simulation of it. Furthermore, even if the computational complexity of the target simulation is low, the number of measurements required for its certification can be exponentially high in the lattice size without the adequate certification method. This is the case, e.g., for full state tomography (FST). Certification tools not relying on FST exist [43][44][45][46][47][48][49][50][51][52], each one efficient on a different subclass of simulations. However, none of these can efficiently handle fermionic linear optics. In fact, almost all [9-11, 13, 14] the above-mentioned experiments relied on FST. The simulation of Ref. [12], in contrast, was certified with matrix-product state tomography [46]. This is a powerful method that covers a broad class of chains but tolerates little long-range entanglement, so that non-trivial evolutions are in practice tractable only over short times [12,46]. Indeed, generic spin chains out of the equilibrium [53], or even very natural, static freefermionic states [54,55], involve large amounts of entanglement along the lattice. Today, a major roadblock for further experimental progress in spin-chain simulations (and in manybody quantum technologies in general) is their certification.
Here, we develop efficient fidelity witnesses for all pure fermionic Gaussian target states. These are experimentallyfriendly observables whose expectation value (on an arbitrary experimental state) yields a tight lower bound to the fidelity arXiv:1703.03152v2 [quant-ph] 24 May 2018 with the target. Hence, they allow for unconditional certification, i.e., without any a-priori knowledge of the experimental setup or imperfections. We derive the witnesses in full generality in the Majorana-fermion representation, and then apply them to experimentally relevant spin-1/2 chains as examples. Among others, we show how to efficiently certify any sudden quench (i.e., strongly out-of-equilibrium dynamics) in a critical TF Ising chain with nearest-neighbor interactions. The measurement scheme relies on a new variant of importance sampling tailored to overlaps between covariance matrices, which is potentially interesting on its own. As a result, the number of measurements required for the certification only has a modest scaling with the lattice size, i.e., a small sample complexity, for which we present upper bounds. Moreover, the method is robust against finite experimentalstate infidelities, in the sense of there always existing a closed ball of valid states that are correctly accepted by the certification test. Finally, we provide also a totally general construction, not restricted to fermions or Gaussian states, of (possibly non-efficient) fidelity witnesses for arbitrary pure target states, which may also be useful in other scenarios.
Preliminaries. Consider a system of L spin-less fermionic atoms, from now on referred to as fermionic modes, with creation and annihilation operators f † j and f j , respectively, for j = 1, 2, . . . , L, satisfying the canonical anti-commutation with anti-commutation relations {m j , m k } = 2 δ j,k . We say that the fermionic system is free, Gaussian, or linear-optical [31][32][33][34][35][36][37], if it is governed by a quadratic Hamiltonian where A = −A ∈ R 2L×2L is called the coupling matrix. The term "free" or "non-interacting" stems from the fact that H is unitarily equivalent to a Hamiltonian of L fermions not featuring any off-diagonal couplings. In the bosonic realm, this is the defining property of Gaussian systems [38,39], which justifies the term "Gaussian". In turn, what is linear about "fermionic linear-optics" is the time evolution of the mode operators in the Heisenberg picture, where U (t) := e −iHt , for t ∈ R, is a fermionic Gaussian unitary and Q(t) := e tA ∈ SO(2L) its representation in mode space [56], see Appendix A for a simple derivation. Finally, it is useful to introduce, for any state (Gaussian or not), the real anti-symmetric covariance matrix M ( ) with elements Figure 1. Geometrical representation of a fidelity witness. A pure target state t lies at the boundary of state space. For any fixed fidelity threshold FT, the valid experimental states are defined by F ≥ FT (green). The states with F < FT are invalid (red). A fidelity witness W defines a hyper-plane (straight line), to the left of which only valid states are found and to the right of which both valid as well as invalid ones are found. The certification test consists of accepting all states on the left and rejecting all those on the right. Hence, a significant subset of valid states is sacrificed, as in weak-membership problems. However, in return, the experimental estimation is considerably more efficient than in schemes attempting to separate the valid from the invalid states (strong-membership problems).
This matrix contains the expectation values of the single-mode densities n j := f † j f j as well as the two-mode currents f † j f k + h.c. and pairing terms f † j f † k + h.c. . Fidelity witnesses. We consider throughout a (known) pure target state t and an arbitrary, unknown experimental preparation p . Their closeness is measured by their fidelity where the last equality holds because t is pure. With this, the pivotal notion of our work can be defined: Definition 1 (Fidelity witnesses). An observable W is a fidelity witness for t if, for F W ( p ) := tr[W p ], it holds that i) F W ( p ) = 1 if, and only if, p = t , and ii) F W ( p ) ≤ F for all states p .
The term "witness" refers to the property that, for any fixed threshold F T , finding F W ( p ) ≥ F T witnesses that F ≥ F T ; but if F W ( p ) < F T is found, then nothing can be said about F (see Fig. 1). This is the least information about p needed to certify its fidelity with t . The situation is reminiscent of entanglement witnesses [57], which detect some entangled states and discard all non-entangled ones. The difference is that fidelity witnesses explicitly realise the extremality-based intuition of "corralling valid states against the boundary". Specific witnesses have been built for ground states of local Hamiltonians [46,52,58] and Gaussian as well as non-Gaussian output states of bosonic linear-optical circuits [50]. In Appendix B, we present (possibly non-efficient) fidelity witnesses of arbitrary target states with no assumption other than they being pure. A special case of such generic construction is the following (efficient) witnesses for the free-fermionic setting.
Any L-mode pure fermionic Gaussian target state t can be written as for a fermionic Gaussian unitary U , as defined below Eq. (3), where ω := (ω 1 , . . . , ω L ) is any L-bit string. The ket |ω represents the Fock-basis state vector with ω j (= 0 or 1) excitations in mode j, i.e., n j |ω = ω j |ω , for j = 1, . . . , L, and n j : , the total fermion-number operator in the locally-flipped basis in which ω is the is the null string, i.e. n (ω) |ω = 0. In other words, |ψ t represents the so-called Fermi-sea state and the eigenstates of n (ω) its excitations. In Appendix B, we show that the observable is a fidelity witness for t . Expression (7) is the fermionic analogue of the bosonic Gausssian-state witnesses of Ref. [50], with a crucial difference: While for bosons only the Fockbasis state vector |0 is Gaussian, for fermions all 2 L Fockbasis vectors |ν are Gaussian as they satisfy Wick's theorem [34]. In fact, for mixed states, all single-mode states are Gaussian, in sharp contrast to the bosonic case. Measurement scheme. Taking the expectation value of Eq. (7) with state p yields (see Appendix C) where M ( p ) and M ( t ) are the covariance matrices of t and p , respectively. This expression holds also for bosonic Gaussian witnesses [50] and turns out very useful for the measurement of F W ( p ). We call Ω : Then Eqs. (4) and (8) imply that if one measures on p all |Ω| ≤ 2L 2 + L observables i[m j , m k ]/2 with indices in Ω, then one can estimate F W ( p ). However, this is not the most efficient procedure (see Appendices D and E). A more efficient approach is to exploit importance sampling techniques, where a subset of the |Ω| observables is randomly selected for measurement according to its importance for W. These techniques have been applied in Hilbert space to the estimation of state overlaps, where they yield efficient schemes only for a specific type of target states [47,48]. Here we apply them in mode space to efficiently estimate overlaps between fully general covariance matrices. The starting point is to identify a random variable X and an importance distribution P := {P µ } µ , with X taking the value X µ with probability P µ , such that tr M ( p ) M ( t ) is expressed as the mean value of X, i.e., Then, if one can experimentally sample X from P , E[X] can be approximated by the finite-sample average X * := N m=1 X µ(m) /N , where X µ(m) is the value of X at the mth experimental run and N is the total sample size (number of runs). Next, we present a choice of X and P particularly suited to estimate F W ( p ).
To this end, let us first definem j,k as the projector onto the eigenstate of the observable im j m k with eigenvalue β = ±1, for (j, k) ∈ Ω. Then, identifying µ with the triple (β, j, k) and using the short-hand notation we choose and This choice satisfies Eq. (9), as explicitly shown in Appendix D. In the experiment, in turn, for each run, one chooses (j, k) according to P j,k := |M j,k ( t )|/|M ( t )| and measures im j m k on p , which outputs β with probability Substituting the obtained (j, k) and β in Eq. (11), one samples X β,j,k with probability P β,j,k , as desired. As for the experimental accessibility of the observables, for the relevant case of spin-1/2 chains each im j m k corresponds to a product of Pauli matrices, as discussed below.
This single-shot importance-sampling approach does not necessarily yield a good estimate of each individual entry of M ( p ), as unlikely observables according to P j,k are measured seldomly. The method is specially tailored to directly obtain F W ( p ). In fact, the resulting estimate X * yields an excellent approximation of tr M ( p ) M ( t ) (in a formal sense given by Theorem 2 below), with which the right-hand side of Eq. (8) can be immediately evaluated. This gives our final finite-sample estimate F * W ( p ) of F W ( p ). Sample complexity. The scaling in L of the minimum (over all estimation strategies) number N ,δ (W) of measurement runs required to estimate F W ( p ), up to statistical error at most and with failure probability at most δ, i.e., such that for all p , is called the sample complexity [49,50,59] of estimating F W ( p ). In Appendix D we compute the number of runs required with the measurement scheme described above, which sets the following upper bound on N ,δ (W).
Theorem 2 (Sample complexity of F W ). Let > 0, δ ∈ (0, 1), t given by Eq. (6), and W by Eq. (7). Then Eq. (10) implies that the right-hand side of Eq. (14) is never larger than 2 ln(2/δ)L 4 / 2 . The scaling is thus polynomial in L for all t , which means that the scheme is efficient in the lattice size. Furthermore, for the physically-relevant case of t being the unique ground state of a local gapped Hamiltonian, the correlations tr [m j , m k ] t decay exponentially with |j − k| [60]. Then, |M ( t )| ∼ L log(L), which leads to Finally, in Appendix E, we study also a measurement scheme without importance sampling (where all |Ω| observables are measured) but exploiting the fact that all commuting observables with indices in Ω can be measured simultaneously in each run. This gives the bound N ,δ (W) ≤ O 2 ln(2 |Ω|/δ)L 4 / 2 , which, since |Ω| ≤ 2L 2 + L, scales logarithmically worse in L than in Eq. (14). We suspect that the bound in Eq. (14) is close to being tight.
Spin-1/2 chains. We denote a local spin operator acting at site k by σ α k = 1 where σ α for α = x, y, z are the Pauli matrices and 1 2 is the single-qubit identity. Via the Jordan-Wigner transformation [61,62] the Hamiltonian in Eq. (2) is equivalent [15] to the experimentally-relevant [9][10][11][12][13][14] spin-1/2 Hamiltonian where J x k , J y k ∈ R and B k ∈ R are respectively constant coupling and transverse-field strengths. Since these spin-1/2 chains are equivalent to free-fermionic systems for all parameter regimes, certifying quantum simulations of, e.g., adiabatic ground state preparations as well as sudden quenches amounts to certifying pure fermionic Gaussian states, as described above. Finally, note that Eqs. (15) map each im j m k to a product of Pauli matrices, as anticipated in the measurement scheme above.
Sudden quenches in critical Ising chains. The 1D nearestneighbor TF Ising Hamiltonian is given by Eq. (16) with J x k = J, J y = 0, and B k = B, for all k = 1, . . . , L, where J, B > 0. In a typical quench, the initial ground state |ψ(0) := |↑ ⊗L at a non-critical regime J = 0 < B, where |↑ is an eigenvector of σ z , is evolved under the critical regime J = B, so as to generate a strong out-ofequilibrium evolution. These quenches are particularly challenging to certify [12,46] because the time-evolved state vector |ψ(t) rapidly acquires large amounts of entanglement. Let us consider the simulation of such a quench by a digital quantum simulator, which approximates the continuous time evolution with a Trotter-Suzuki pulse sequence  Discussion. We have shown how to certify experimental states of dimension 2 2 L with at most O(L 4 ) measurements, with no assumption whatsoever on the experimental imperfections, for all pure fermionic Gaussian target states. Moreover, for targets given by ground states of gapped free-fermionic Hamiltonians, the number of experimental repetitions reduces to O L 2 log 2 (L) . In addition, in Appendix F we prove that there always exists a closed ball of valid states that are correctly accepted by the certification test, so that the test is robust against finite experimental deviations.
Our results are directly relevant to recent experiments with spin chains [7, 9-11, 13, 14, 63] as well as potential implementations of Kitaev's honeycomb model [64,65]. In real-life digital simulations [11,13,14], apart from the Trotterisation errors, also heating and noise will of course be present. The fidelity witnesses offer an excellent tool for experimentally quantifying, in an an inexpensive way, the detrimental effect of such imperfections on the simulation's performance.
Free-fermionic models are classically tractable, but the importance of their quantum simulations comes from the fact that they constitute a testbed for experimental many-body quantum technologies, with certified simulations of classically intractable models as ultimate goal. In this respect, the direct-certification tools developed here may help bridge the gap between the experimental certification of proof-ofprinciple simulations and classically intractable ones.

APPENDIX
In this appendix, we present the technicalities of the calculations mentioned in the main text and additionally provide some further details about our methods. The first section recalls generally known facts concerning fermionic linear optics. The next three sections concern fidelity witnesses. The next two are on sample complexities for evaluating the Gaussian fidelity witness with an estimate. In the last section we provide details to robustness properties of the fidelity witness and the corresponding certification test.

A. Methods of fermionic linear optics
This section gives more details on results of fermionic linear optics used in the main text. The first sub-subsection discusses unitary evolution in this formalism. The second subsubsection contains details on the Jordan-Wigner transformation, covariance matrices of spin product states and which spin operators need to be measured to measure the fermionic covariance matrix. Finally we shortly comment on the numerical simulations.
a. Gaussian dynamics The Heisenberg evolution of Majorana operators is given as follows.
Note that the propagator is manifestly real and there is no i in the exponent because A is antisymmetric.
Proof. We begin by noticing that m j (t) is differentiable and take a time-derivative obtaining which is the Heisenberg equation of motion. We further notice that which means that we need to evaluate the commutator at t = 0. Next we calculate the commutator which gives This allows us to write the above Heisenberg equation of motion explicitly as This linear system of 2L ordinary differential equations is solved by where Q = e tA ∈ SO(2L). Indeed, this becomes apparent if one considers a vector m = (m 1 , . . . , m 2L ) then we get in vector notation Given this we easily obtain the evolution equation for the covariance matrix M ( (t)) j,k = 0)) j ,k . This in matrix notation gives M ( (t)) = (Q(t)M ( (0))Q(t) ) j,k .
b. Using the Jordan-Wigner transformation This paragraph shows how to use the Jordan-Wigner transformation to translate between spins and fermions. We first identify covariance matrices of simple states.
Lemma 4 (Vacuum covariance matrix). In the notation In general if |ω is a computational basis state with ω ∈ {0, 1} ×L (identifying |0 = |↑ and |1 = |↓ ) we have Proof. The first statement follows directly from the second for ω k = 0 for all k.
To show the latter, we first observe that σ z k = −im 2k−1 m 2k . Indeed using we get Next we observe that σ x k ω = σ y k ω = 0 and σ z k ω = (−1) ω k so the only non-vanishing elements are In an experiment based on qubits the fermionic covariance matrix can be measured by making the following Pauli measurements.
Lemma 5 (Fermion spin correlation dictionary). For j < k we have • Odd-even • Even-even Proof.
The remaining relations follow similarly and by again using (33).
Considering the reversed direction of this dictionary, we find that the product of two spin operators is a product of again two Majorana operators only when the spins are neighboring in the Jordan-Wigner transformation from which we obtain the following corollary. The translation invariant case is physically the most relevant case for which the following result first appeared in [15] and we state it to make explicit which couplings we have used in our simulations.

Lemma 7 (Transverse field Ising model). The Hamiltonian of the transverse field Ising model
maps to free fermions under the Jordan-Wigner transformation and the couplings matrix read Note, that for compactness we write in the main text A(J) ≡ A(J, 0) and A(B) ≡ A(0, B). c. Comments on numerics The numerical code used to obtain Fig. 2 in main text is available at [66]. We use Wick's formula [34] to calculate | n k=1 σ z k | = Pf(M 1...2n ) where Pf denotes the Pffafian which can be calculated using the package PFAPACK [67].
B. Proof that Eq. (7) yields a fidelity witness and general witness construction Here we first provide an expression for a fidelity witness of any arbitrary, totally generic pure target state, not restricted to the Gaussian fermionic setting.
The fact that the observable W in Eq. (7) defines a fidelity witness for the free-fermionic target state in Eq. (6) follows from Proposition 8 taking N = 2 L − 1, identifying l with an L-bit string ν = ω, and taking λ ν = L j=1 [(1 − ω j )ν j + ω j (1 − ν j )] and P ν = U |ν ν | U † . Proof of Proposition 8. We start with Property i in Def. 1. Let p be such that tr[W p ] = 1. Then ∆ −1 N k=1 λ l tr[P k p ] = 0. As all terms are non-negative, we have tr[P k p ] = 0. From this we write 1 = tr[ p 1] = tr[ p t ] + N k=1 tr[P k p ] = tr[ p t ], which means, since t is pure, that p = t . The converse direction starting from p = t follows from tr[ t P k ] = 0.
We now prove Property ii in Def. 1. For any state vector |ψ we have This means that which one may write t W = 1 − ∆ −1 N k=1 λ l P l , where denotes semidefinite dominance. This relation can be used in order to lower bound the fidelity. If we write the preparation state in its eigenbasis p = k p k |k k| 0, then we find the following Thus we arrive at C. Proof of Eq. (8): Fidelity-witness in terms of covariance matrices Before the proof, let us first provide useful facts from fermionic linear optics theory. The covariance matrix of any Fock state vector |ω is given, introducing the short-hand notation M ω := M ( |ω ω |) by This is readily seen from the fact that i and that all other covariance matrix entries are zero. Put differently, fermionic Fock states are of the most simple product form. In order to introduce coherences in the system one can rotate the state by a Gaussian unitary U with mode action Q which then yields Proof of Eq. (8). In order to evaluate the witness we notice that the numbering operator of mode k is and This allows us to write the projector n (ω) as We therefore have where the definition of the covariance matrix (4) has been used. AsM := M (U † p U ) = Q M ( p ) Q is antisymmetric, we can writeM 2k−1,2k as (60) We further notice that (53) allows us to write From the definition of M ( t ) = Q M ω Q we finally obtain In this section, we compute the number of experimental runs required to get a finite-sample estimate F * W ( p ) of F W ( p ) satisfying Eq. (13) with the measurement scheme with single-shot importance sampling described in the main text. This sets the upper bound on N ,δ (W) in Eq. (14), proving Theorem 2.
Proof of Theorem 2. We begin by noting that one can directly evaluate F W ( p ) from the value of Indeed, if |X * − X | ≤ 4 , then |F * W ( p ) − F W ( p )| ≤ . We define conditional probability P β|j,k := tr m (β) j,k p (65) and the sampling distribution for By Bayes' theorem, we have that P β,j,k = P β|j,k P j,k is a well-defined probability distribution. Additionally, we define the importance sampling variable which is distributed over P β,j,k . With these definitions we check that the average of X gives X We now use Hoeffding's inequality to see that this results in a ( , δ)-evaluation promise. We have We would like the RHS to be upper bounded by δ so we obtain which is the sample complexity, i.e., yielding the inequality (14).

E. Sample complexity for entrywise evaluation
Here, we compute the number of experimental runs required to get a finite-sample estimate F * W ( p ) of F W ( p ) satisfying Eq. (13) with a measurement scheme that does not exploit importance sampling, i.e., where all |Ω| observables are deterministically measured, but that exploits the fact that commuting observables with indices in Ω can be measured simultaneously in each run. As we show, the resulting bound is less tight than the one in Eq. (14). More precisely, we consider a procedure where all |Ω| observables are measured the same number of times and we obtain the sample complexity N ,δ (W) = 4Lη.
We denote the estimator of M by M * . The fact that the covariance matrix entries are bounded and lie in the interval −1 < M µ < 1 allows us to use Hoeffding's inequality. Taking b = ln(2|Ω|/δ) and making a union bound we find where we have used that P[A ∪ B] ≤ P[A] + P[B] for any probability measure P. We check that 2|Ω|e −b = δ and additionally and therefore we have Eq. (13) follows thanks to the following Lemma which tells us that one can efficiently estimate the fidelity lower bound from estimates of the covariance matrix of p with small errors.
Lemma 9 (Stability). The fidelity lower bound F W ( p ) is Lipschitz continuous with Lipschitz constant L 3/2 / √ 2 with respect to the max-norm, i.e., for any two covariance matrices M and M * we have for the respective values of the fidelity witnesses In the following proof, we denote the trace-norm by · 1 , the Schatten 2-norm (or Frobenius norm) by · 2 , and the spectral norm by · ∞ .
Proof of Lemma 9. Let where we have used that · ∞ unitarily invariant and that J L ∞ = 1 in the last step. It remains to show that M 1 ≤ 2L. But for any 2L × 2L matrix M it holds that where we have used (i) a general norm inequality for the Schatten 1-and 2-norm, (ii) that the Schatten 2-norm is the same as the vector 2-norm of the vectorized matrix, (iii) a general norm inequality for the vector 2-norm and the vector ∞-norm, and (iv) that the vector ∞-norm of a vectorized matrix is the max-norm of the matrix. Note that the bound (83) is tight for general matrices, as can be seen by choosing M as the discrete Fourier transform matrix on C 2L . Inserting Eq. (83) into (82) completes the proof.
Finally, in order to derive the sample complexity, we need to partition the set [2L] × [2L] such that the corresponding elements of the covariance matrix commute. We do it by considering bands parallel to the diagonal of the covariance matrix. Let us consider the non-trivial elements closest to the diagonal µ = (i, i + 1). We bi-partition this band into indices starting with an even or an odd number. By construction, all associated covariance matrix observables will commute. As there are in total 2L − 1 such off-diagonals, the total number of i.i.d. state preparations is bounded by Since |Ω| ≤ 2L 2 + L, this scaling is logarithmically worse in L than in Eq. (14).

F. Robustness of the certification test
Ref. [50] established a framework of certification where the notion of robust quantum state certification has been defined. In particular, in such a certification test, one desires to accept states above a threshold fidelity F T and requires to reject states below F T . But a realistic certification test cannot resolve fidelities F very close to F T and thus one needs to allow for a fidelity region that remains undetermined. This idea leads to a robust certification test [50,52], where one allows for a fidelity gap ∆ < 1 − F T . A robust test is guaranteed to accept a preparation p if F ≥ F T + ∆, to reject it if F < F T , and possibly accept it in the intermediate region. These conditions for the test concern the exact fidelity and need to be translated to a statement concerning the estimate of the witness F * W ( p ). We will show that for all preparations p in a certain class of states S ⊥ (∆, ) it suffices to compare the estimator F * W ( p ) to the number F T + . In other words, such test is robust i) if p is such that F < F T then in the same time the witness will testify this i.e. F * W ( p ) < F T + . This means that whenever the test has to reject a preparation, then it will.
ii) if F ≥ F T + ∆ then we have F * W ( p ) ≥ F T + . That is, whenever the fidelity is larger then the threshold fidelity enlarged by the fidelity gap, then the preparation is accepted by the test.
Note, that if F ∈ [F T , F T + ∆], then the certification test might accept or reject the preparation. Specifically, the class S ⊥ (∆, ) characterizes the set of preparations p where the witness behaves as a weak oracle separating F ≤ F T from F ≥ F T + ∆. We now construct this class. With a given target state U |ω and its corresponding fidelity witness in mind, we define a mismatch parameter of some preparation state p to be Let us note that the preparation p can be decomposed with the Hilbert-Schmidt inner product into the target state t and a orthogonal contribution ⊥ : Using linearity of our witness for this decomposition yields Therefore the mismatch content has the properties n ⊥ ( t ) = 0 and n ⊥ ( p ) = (1 − F )n ⊥ ( ⊥ ). For a given maximum estimation error 0 < < (1 − F T )/2, fidelity gap ∆ > 2 and fidelity threshold F T < 1 we define the mismatch content threshold It is a convex set containing mixtures of states with possibly very large mismatch content n ⊥,T and which includes the target state t in its interior. The following theorem states that our fidelity witness leads to a robust certification test.
Theorem 10 (Robust certification of pure Gaussian states). Let F T < 1 be a threshold fidelity, δ > 0 a maximal failure probability , 0 < < (1 − F T )/2 a maximal estimation error and 2 < ∆ < 1−F T a fidelity gap. Let t be a pure Gaussian state and p a preparation state. Let F * W ( p ) be the estimator of the fidelity witness from Theorem 2. The test accepting the preparation if F * W ( p ) ≥ F T + and rejecting if F * W ( p ) < F T + yields a robust certification of t if p ∈ S ⊥ (∆, ). For states with high enough fidelity F > 1 − L −2 the witness yields a non-trivial lower bound F W ( p ) ≥ 0.
Proof. The rejection Property i) follows by observing that according to Theorem 2 we have with probability at least 1 − δ that from which it follows that Next we use that the fidelity witness is a lower bound to the fidelity F and that in case i) we have F < F T to get the chain Therefore, if F < F T then F * W ( p ) < F T + . In this step we did not need to assume anything on the preparation p .
Secondly, we show that the test has the acceptance Property ii) as well. We now use F ≥ F T + ∆ and assume that n ⊥ ( p ) ≤ n ⊥,T to obtain from Eq. (86) F W ( p ) = 1 − (1 − F )n ⊥ ≥ 1 − n ⊥,T + F n ⊥,T ≥ 1 − n ⊥,T + (F T + ∆)n ⊥,T which with the definition of the mismatch content (87) becomes Therefore, we find with probability at least 1−δ the inequality for the estimator of the fidelity witness These two steps show that the test is robust for ∈ S ⊥ (∆, ). Finally let us assume F T ≥ 1−L −2 . We need to show that if F ≥ F T + ∆ then F * W ( p ) ≥ F T + . By Fuchs-van der Graaf inequality we have D( p , t ) ≤ √ 1 − F ≤ √ 1 − F T = L −1 . From this bound it follows that From this bound, we find Note that the witness is exact F W ( p ) = F for preparation state vectors supported on the Hilbert space subspace Span({U |∅ , U f † 1 |∅ , . . . , U f † L |∅ }). Finally, Eq. (86) allows to intuitively understand when exactly the witness fails to be an oracle, which we illustrate with one last example.

Example: symmetry breaking
Consider a scenario, where the system has initially a Z 2 symmetry between the vacuum |∅ and the fully occupied state vector 1 , and then at some point spontaneous symmetry breaking occurs such that the system must choose one of the two states. If the preparation is given by p = U (1 − λ) |∅ ∅ | + λ|1 1| U † then the mismatch is a very good way of quantifying the fidelity of symmetry breaking, namely n ⊥ ( p ) = λ 1|N |1 = λL is a good order parameter. The mismatch is low for λ 1/L which occurs for high values of our witness and it therefore allows to show that the system chose the vacuum in the Z 2 symmetry breaking. Note, that the mismatch parameter will be high for many-particle GHZ states, but those are expected to be unstable and will not occur for no reason e.g. due to incoherent noise. In particular, low mismatch is also a natural assumption when certifying a digital simulation of the transverse field Ising Hamiltonian. As a final corollary to this example, note that for an L-mode system we have n (ω) = L and therefore for all states in a ball defined by − t 1 ≤ 1/L we will find F W ( p ) ≥ 0.