{'fraction_non_alphanumeric': 0.03597021870637506, 'fraction_numerical': 0.009120521172638436, 'mean_word_length': 4.789601293103448, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quasiprobabilistic state-overlap estimator for NISQ devices

As quantum technologies mature, the development of tools for benchmarking their ability to prepare and manipulate complex quantum states becomes increasingly necessary. A key concept, the state overlap between two quantum states, offers a natural tool to verify and cross-validate quantum simulators and quantum computers. Recent progress in controlling and measuring large quantum systems has motivated the development of state overlap estimators of varying efficiency and experimental complexity. Here, we demonstrate a practical approach for measuring the overlap between quantum states based on a factorable quasiprobabilistic representation of the states, and compare it with methods based on randomised measurements. Assuming realistic noisy intermediate scale quantum (NISQ) devices limitations, our quasiprobabilistic method outperforms the best circuits designed for state-overlap estimation for n-qubit states, with n>2. For n<7, our technique outperforms also the currently best direct estimator based on randomised local measurements, thus establishing a niche of optimality.

The SWAP test, also known as the "equality algorithm", is the gold-standard primitive for estimating the overlap between two unknown quantum states directly (i.e., without expensive tomographic reconstructions). Originally introduced in the context of communicationcomplexity problems [1], it is nowadays a key subroutine for a variety of quantum algorithms, ranging from quantum kernel-based machine learning (e.g. support vector machines, Gaussian processes, clustering, and principal component analysis [2][3][4][5][6]), to training deep quantum neural networks [7] (e.g. for state or circuit learning), or validation of quantum devices.
Although conceptually simple, the SWAP test is unpractical for noisy intermediate-scale quantum (NISQ) circuits. In the standard approach, the test involves a SWAP gate between two n-qubit registers (that carry the input states) controlled by an ancillary qubit, i.e. an n-qubit Fredkin gate. Due to limited hardware connectivity, this gate must be synthesised by a deep circuit that rapidly consumes all the available quantum-depth budget. E.g., for 1D circuits with nearest-neighbour connectivity, the standard way of exactly synthesising the 2-qubit Fredkin gate requires a circuit of 212 layers. But devoting such a large amount of quantum hardware on an operationally simple task goes against the NISQ mantra "run easy tasks classically and save the quantum hardware for the actually hard subroutines".
In this spirit, important simplifications have been attained. For instance, a classical machine-learning approach [8] has recently revealed an alternative exact synthesis of the n-qubit Fredkin gate using fewer gates. Additionally, an even shallower circuit for the state overlap has been found that exploits transversal Bell measurements across the n-qubit registers and requires no ancillary qubit [9]. Nevertheless, these approaches are still not practical enough for NISQ devices. In particular, synthesising Bell measurements between distant qubits with circuits of limited-connectivity still requires circuit depths that rapidly become prohibitive as n increases.
In a conceptually different approach, some entanglement-free methods to direct overlap estimation [10,11] were proposed.
A recent work in this direction presents an estimator based on singlequbit random measurement choices correlated between both platforms through classical communication [12]. Nevertheless, its numerical analysis focuses mostly on the overlap of a state with itself (purity), leaving aside the more general case between different states, required in most algorithmic applications of the SWAP test. In fact, no comparison with the aforementioned entanglement-based approaches was reported there.
In this paper we demonstrate an entanglement-free technique for direct state-overlap estimation, built upon a recently studied factorable probabilistic representation of quantum states [13]. In similar fashion to Ref. [12], we employ single-qubit measurements, but require no measurement coordination between both system registers. In addition, instead of focusing on state purities, we investigate general overlaps between arbitrary state pairs. For n-qubit states, with n < 7, we find our approach to present the lowest mean absolute error. We also compare our technique against circuit-based approaches, that classically simulate noisy implementations of two different SWAP test variants. In this context, we analyse the average statistical error of our method against their total average error (statistical plus systematic due to gate error accumulation). For typical noise parameters of current hardware implementations, our method considerably outperforms (in terms of mean absolute error) the ancilla-qubit based SWAP tests already for all n ≥ 2 and the Bell-measurement variant for all n ≥ 3, while the sample complexity remains well below that of full state tomography or even quantum compressed sensing [14,15].
The method we present here is also related to estimation from classical shadows [16], an efficient approach to approximate linear functions of quantum systems without arXiv:2112.11618v1 [quant-ph] 22 Dec 2021 fully characterising them. In particular, the shadow fidelity estimator probes a given state and compare it with a classical description of a target state. Although we sample both (unknown) states, we can see both methods as different variants of the same overall strategy. In fact, particular choices in our construction leads to a particular instance of their estimator, and vice-versa.
Our numerical results rely on an efficient tensornetwork construction (based on locally-purified density operators [17]) tailored for non-unitary dynamics. This allows for realistic simulations of multiqubit gate noise in quantum circuits. b )] ab . Informationcompleteness allows us to write any n-qubit state ρ as [13]

I. OVERLAP ESTIMATION VIA A QUASI-PROBABILISTIC REPRESENTATION
where P ρ (a) = Tr(ρM (n) a ) and τ can be defined as the pseudoinverse of T (however, as we show below, other choices of τ are possible). Since the POVM elements are not orthogonal, the associated probabilities do not refer to exclusive events, and therefore P ρ is called a quasiprobability.
Let us now proceed to characterise all choices of τ . Noticing that decomposition (1) holds for any operator, we can apply it to ρ = M (n) b and obtain for any b, b . This yields the relation Any matrix satisfying (3) is called a generalised inverse for T ; in particular, the pseudoinverse fulfils this condition. Analogously, again from the completeness of the POVM, it is straightforward to check that (3) conversely implies (1) (see Appendix A). This proves the following observation. Notice that we can use different tensors τ 1 , τ 2 for representing different quantum states. Using this fact to represent states ρ and σ, we find their overlap is given by

Lemma 1. Eq. (1) holds for any state ρ if and only if
This provides a practical way of estimating the overlap Tr(ρσ). First, we repeatedly measure M (n) on ρ and σ. This can be done separately and at different times. Then, according to the obtained outcomes a, b, we approximate the above expectation value by an average of the matrix elementsτ = [τ 1 T τ t 2 ] ab (see Fig. 1). This approximation generates a statistical error, which we now consider. Recall that representation (1) allows to reconstruct entangled states ρ as combinations of the separable operators M a , implying thatτ forcibly has negative entries. This negativity can be quantified in terms of the range ν = max a,b [τ ] ab − min a,b [τ ] ab . Moreover, it controls the number of samples that our method requires in general, as stated in the following.

Theorem 1. Let ρ, σ be n-qubit states and {τ
The proof follows directly from Hoeffding's inequality. Hence, we see the sample complexity scales exponentially on the number of qubits according to ν, which encodes the sample complexity overhead inherent to the quasiprobabilictic representation.

II. NUMERICAL EXPERIMENTS
We performed numerical experiments to validate our estimator by taking n tensor copies of the 6-outcome POVM where |a is an eigenvector of either X, Y, or Z, and τ 1 = τ 2 = T + , where T + denotes the pseudoinverse of T . Due to the freedom in the choice per equation Eq. (3), we considered different POVMs for our experiments. We performed a brute-force search on the 4-, 6-, and 8-outcome qubit POVMs by incrementally varying the angles between Bloch-vectors representing the POVM elements. This revealed the Pauli-6 POVM as the optimal choice. We also used a Markov chain Monte Carlo [18,19] dynamics to simulate a random walk on the set of solutions to Eq. (3) for minimising ν. However, both searches provided only worse negativities. This is further detailed in Ref. [20].
We numerically investigate the number of samples N required to make the estimation's absolute error, |Tr(ρσ)− 1 N iτ i |, lower than a fixed threshold. We estimate the overlap of pure product and entangled pairs of states, constructed as matrix-product states from random local tensors. In agreement with Ref. [12], we find that the latter is a slightly simpler problem. In Fig. 2, we present the obtained scaling for the fixed error bound of 0.05. To minimise numerical fluctuations, we check the number of samples required to make the average error of 5 random pairs lower than this bound, for 100 batches of 5 states. For more details, we refer to our computational appendix [21].

III. CONNECTION WITH PREVIOUS APPROACHES
We now investigate other overlap estimators, which we simulate in order to compare them with the quasiprobabilistic method. These alternative methods are separated in two groups. We start from the ones that require coherently-controlled operations between the two systems, described as quantum circuits. Next, we consider two direct estimators based on random measurements and the theory of unitary t-designs.
Entanglement-based approaches.-There are various quantum circuits designed specifically for calculating the overlap between quantum states. However, considering realistic implementations, most NISQ devices have a series of restrictions in common. For instance, the number of implementable quantum gates is limited, as is the connectivity between different qubits. In addition, although the single-qubit gate noise is usually negligible, the noise present in multiqubit gate implementations cannot be ignored. To address these points in our simulations of noisy circuits, we used the locally purified density operator (LPDO) paradigm, designed for simulating non-unitary evolutions in tensor networks language (see Appendix B).
Based on that, we benchmark our method considering quantum computers with the following features: (i) the set of implementable gates comprises noiseless singlequbit gates and noisy CNOTs; (ii) the circuits are onedimensional; and (iii) the interactions between the qubits are limited to nearest-neighbours, meaning that longdistance CNOTs have to be compiled via first-neighbour CNOTs. The optimal compilation then adds 4(d − 1) extra CNOTs to the original circuit, where d is the distance between the qubits in the long-distance CNOT. We assume the noisy CNOTs are well modelled by an ideal CNOT followed by a depolarising channel. This yields a circuit structure with increasing infidelity. We emphasise the one-dimensional structure is considered only for simplicity and illustrative purposes. Our conclusions hold also for 2D structures, but the corresponding classical simulation is more expensive.
Under these conditions, let us recall three circuits for state overlap. The first is the standard SWAP test [1], which requires a single-qubit measurement on the ancillary qubit. Similarly, the improved SWAP test circuit [8] optimises the compilation of the standard circuit in view of constraint (i), demanding a lower number of layers and CNOTs but maintaining the single-qubit measurement on the ancilla. Finally, on a different line, the Bell-basis circuit [9] requires a global measurement on the Bell basis in exchange of reducing the number of gates and layers. With the limited connectivity assumption (iii), these circuits already involve a high number of CNOT gates for a small number of qubits (see Table I In these approaches, on top of the statistical error of estimating the expectation value of an observable, we have the systemic noise arising from the implementation of two-qubit gates. In contrast, using the quasi-probabilistic direct approach we obtain a qualitative advantage since the estimation (4) can be as accurate as needed, as long as the number of samples is large enough. As shown in Fig. 3, even for a modest number of samples we already see a clear advantage to our method in the cases of 2-and 3-qubit states. Random unitary-based methods.-We now compare our estimator with the two state-of-the-art direct techniques for calculating state overlaps. The first technique [12] applies the same random measurements on both states, coordinated by means of classical communication. Nevertheless, it is also entanglement-free and allows for independent interaction with each system. Next, it uses the theory of unitary t-designs for approximating the overlap. The direct performance comparison with our method (Fig. 4) shows that our approach presents a lower mean absolute error for n-qubit states, with n < 7.   [12], for a fixed budget of 10,000 samples, for random pure product and pure entangled states. In the latter, we used 100 samples from each of 100 random measurements. The mean absolute error was computed over 200 instances and the average overlap was ≈ 0.6 in both cases.
However, our method is outperformed for states involving more qubits. This is confirmed by the sample complexity required to obtain an error bound of 0.05, ∼ 2 1.1n , shown in Fig. 2, while the reported corresponding scaling of the random measurements method is ∼ 2 0.8n . Finally, we discuss the connection of our results with shadow estimation [16,22], a recently proposed method to efficiently estimate linear functions of quantum states. The so-called classical shadow of a state ρ, given by the inverse of the map M(ρ) = E U,b (U |b b|U † ), is obtained by taking the average over some ensemble of unitaries U to ρ and subsequently measuring on the computational basis {|b b|} b . Whenever the unitaries are chosen from the local Clifford group, the corresponding shadow fidelity estimator matches Eq. (4), for M (1) a as in Eq. (5) and for a particular choice of τ 1 , τ 2 (see Appendix C). Therefore, these specific instances of each estimator share the same performance [16].

IV. FINAL DISCUSSION
While efficient entanglement-based quantum algorithms for approximating the overlap of quantum states exist, the currently available devices imply unavoidable systematic errors. Therefore, direct and entanglement-free methods may provide an advantage in the estimation of state overlaps in the near term. These typically present only statistical errors and treat the overlap estimation as a sample-complexity problem. Among the entanglementfree direct estimators, we show that our method presents the lowest mean absolute error for n-qubits states, with n < 7. We also identify that the quasiprobabilistic construction shares some common elements with the shadow fidelity estimation approach. Moreover, for particular choices on each of the methods, the constructed estimators are the same.
Our work opens up avenues for future explorations. In here, we have used a quasiprobabilistic representation specifically for estimating the fidelity between quantum states. However, these representations can be used to describe not only quantum states, but also quantum measurements, unitary evolution, and open system quantum dynamics [23][24][25][26]. Can they be efficiently used for classical simulations of quantum circuits? For what circuits the associated sample-complexity overhead becomes too expensive? It would be interesting to investigate the interplay between these figures in the context of classical-quantum simulations.
In the main text, we showed that given an informationally-complete POVM {M a } and its associated matrix [T ij ] ij = Tr(M i M j ), if the representation ρ = a,a P ρ (a)τ aa M a holds for any quantum state, then τ satisfies T = T τ T . Here we will show the converse, completing the proof of Lemma 1.
From completeness, we can write any state as ρ = Assuming T = T τ T , we obtain Since this holds for all j, we conclude

B. THE LPDO PARADIGM
Numerical simulations with the full density matrix of size 2 n × 2 n quickly become prohibitive due to the large memory requirements. Hence, in order to compare these approaches efficiently, we describe our quantum states as locally purified density operators (LPDOs), within the tensor networks paradigm. This framework is particularly useful since we perform a simulation of noisy quantum circuits, in which the implementation of each CNOT is followed by the performance of a depolarising channel on the respective qubits. Hence, the updated circuit state is mixed.
The canonical choice for representing operators with tensor networks are matrix product operators (MPO) [27]. A drawback of this approach is that applying completely positive maps to the state can still lead to the MPO becoming non-positive due to truncation errors. The locally purified density operator method solves this issue by representing the state as = XX † , where the purification operator X is given by a tensor network where 1 ≤ p l ≤ P , 1 ≤ k l ≤ K and 1 ≤ b l ≤ D. Here, P is called the physical dimension, K is the Kraus dimension and D is the bond dimension. Hence we can guarantee the positivity of our tensor network at the cost of introducing an additional dimension k l into our local tensors A [l] . In general, applying an entangling gate increases the cardinality of b l , while applying a depolarising channel increases the cardinality of k l . In order to keep the simulation efficient, we must ensure the bounds D and K, called bond dimension and Kraus dimension, respectively, are respected. To do so, whenever these bounds are exceeded we truncate the corresponding description via a singular value decomposition on the respective tensors; for truncations on the Kraus dimension, the LPDO formalism guarantees that the final description refers to a positive semi-definite operators and our description of the circuit remains valid.
We can control the accuracy of the simulation by increasing D and K and keeping track of a runtime lower bound estimate of the state fidelity. Let = X † X and σ = Y † Y . Then the fidelity is given by From Lemma 1 in [28] we know that, Let X be a locally purified description of a quantum state with local tensors {A [n] } that is in mixed canonical form with respect to a local tensor A [lcp] . If a single tensor A [ncp] is compressed by a discarding singular values in either the Kraus or bond dimensions the error, then by lemma 6 in [28] we know that and subsequently where X is the compressed tensor. By the triangle inequality, the two norm errors introduced by the discarded weights can at most sum up. Hence the true operator norm is lower bounded by the sum of all discarded weight errors With d the number of trunctations and δ k the discarded weights. This brings the final runtime fidelity estimate to In all our noisy experiments, we apply depolarizing channels only to the two qubit gates, since single qubit gate noisy tends to be small in experimental settings. The channel is given by where {K m } is a set of Kraus operators with where λ ∈ [0, 1] is the depolarising factor. The tensor networks formalism is also convenient for describing our quasi-probabilistic method, since the involved POVM and its corresponding τ matrix are factorable and act locally, so the tensor contractions are done most efficiently. For more more details on our implementations, please see our computational appendix [21].

C. EXPLICIT CONNECTION TO SHADOW ESTIMATION
Our method requires an IC-POVM and at least one choice of a generalised inverse for T, i.e. a matrix τ satisfying T = T τ T , where T is the associated matrix of the POVM. We used the Pauli-6 POVM (Eq. (5)) and τ = T + , the pseudoinverse of T ; however, there are infinitely many matrices that satisfy Eq. (3).
On the other hand, the classical shadows technique [16] uses unitaries {U i }, randomly chosen from a distribution µ, and measurements on the computational basis |a = |0 , |1 to reconstruct any n-qubit state ρ as where a = a + 1 mod 2 and we use that fact that I = M i,0 + M i,1 for i = 1, 2, 3. Hence, we can rewrite the square bracket as We finish recognising the final expression as a quasiprobabilistic representation by rescaling the operators M i,a using the 1/3 factor to obtain the elements of the Pauli-6 POVM (which leads to a rescalingτ → 3τ ).
These observations were our motivation to investigate the plurality of τ 's and its optimisations, that lead to Lemma 1. However, as reported in the main text, we concluded that the pseudoinverse T + is the best option. Indeed, it is actually equivalent toτ , as one can check thatτ T = T + T , and therefore the relevant tensor for our overlap estimation method, τ T τ , is the same in both cases.