We study the following quantum state identity problem: given access to copies of $n$ unknown pure quantum states, the goal is to determine whether every pair has fidelity at least $1-\varepsilon$ or some pair has fidelity at most $\varepsilon$. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter $\varepsilon\in(0,1/4)$, we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes $O(\log(n/δ)\log(2/δ))$ copies of each input state to succeed with probability at least $1-δ$. The second uses the Schur transform to reduce the sample complexity to $O(\log(n/δ))$, through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of $Ω(\log(n/δ))$ for any quantum algorithm with failure probability at most $δ\le 1/2-c$, for any constant $c>0$, establishing that the second algorithm achieves the optimal dependence on both $n$ and $δ$ for fixed $\varepsilon$.
AI Summary
The paper studies identity testing for $n$ unknown pure states: distinguish whether every pair has fidelity at least $1-\varepsilon$, or some pair has fidelity at most $\varepsilon$, given copies of each state. Unlike the identical-or-orthogonal setting, approximate identity can make the permutation test reject valid yes instances with probability approaching one.
For $0<\varepsilon<1/4$, writing $\gamma=1/2-\sqrt{\varepsilon}$, two algorithms achieve error at most $\delta$. A random-matching protocol uses $O(\gamma^{-2}\log(n/\delta)\log(2/\delta))$ copies per state and constant quantum depth, using parallel destructive swap tests with classical processing. Its analysis shows that one low-fidelity pair forces $\Omega(n)$ witness pairs with fidelity at most $(1+\sqrt{\varepsilon})/2$, so a random matching detects a witness with constant probability.
A second protocol uses $O(\gamma^{-2}\log(n/\delta))$ copies per state. Schur-basis measurements jointly sample the commuting Jucys–Murphy observables; forward and reverse input orderings yield simultaneous estimators of each state's total pairwise fidelity. Concentration bounds separate the promises. The Schur-transform implementation costs $\widetilde O(\gamma^{-2}\log(n/\delta)\min\{n^4,nd^4\})$ gates.
A lower bound of $\Omega(\log(n/\delta)/\log(1/\varepsilon))$, for $\delta\leq1/2-c$ and fixed $c>0$, establishes optimal dependence on $n$ and $\delta$ at fixed $\varepsilon$. It follows from phase-randomized qubit ensembles reducing to binomial hypothesis testing, together with binary state discrimination.
The stated limitations are the restriction to $\varepsilon<1/4$, unresolved optimal dependence on $\varepsilon$, and pure inputs; mixed-state fidelity is not directly estimated by swap tests.
Little sign of AI-generated textAI use disclosed
The results of this paper were developed through conversations with ChatGPT 5.6-Sol. The manuscript was written by the authors, drawing on the output of these conversations.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
We study the following quantum state identity problem: given access to copies of n unknown pure quantum states, the goal is to determine whether every pair has fidelity at least 1−ε or some pair has fidelity at most ε. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter ε∈(0,1/4), we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes O(log(n/δ)log(2/δ)) copies of each input state to succeed with probability at least 1−δ. The second uses the Schur transform to reduce the sample complexity to O(log(n/δ)), through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of Ω(log(n/δ)) for any quantum algorithm with failure probability at most δ≤1/2−c, for any constant c>0, establishing that the second algorithm achieves the optimal dependence on both n and δ for fixed ε.
The paper studies identity testing for n unknown pure states: distinguish whether every pair has fidelity at least 1−ε, or some pair has fidelity at most ε, given copies of each state. Unlike the identical-or-orthogonal setting, approximate identity can make the permutation test reject valid yes instances with probability approaching one.
For 0<ε<1/4, writing γ=1/2−ε, two algorithms achieve error at most δ. A random-matching protocol uses O(γ−2log(n/δ)log(2/δ)) copies per state and constant quantum depth, using parallel destructive swap tests with classical processing. Its analysis shows that one low-fidelity pair forces Ω(n) witness pairs with fidelity at most (1+ε)/2, so a random matching detects a witness with constant probability.
A second protocol uses O(γ−2log(n/δ)) copies per state. Schur-basis measurements jointly sample the commuting Jucys–Murphy observables; forward and reverse input orderings yield simultaneous estimators of each state's total pairwise fidelity. Concentration bounds separate the promises. The Schur-transform implementation costs O(γ−2log(n/δ)min{n4,nd4}) gates.
A lower bound of Ω(log(n/δ)/log(1/ε)), for δ≤1/2−c and fixed c>0, establishes optimal dependence on n and δ at fixed ε. It follows from phase-randomized qubit ensembles reducing to binomial hypothesis testing, together with binary state discrimination.
The stated limitations are the restriction to ε<1/4, unresolved optimal dependence on ε, and pure inputs; mixed-state fidelity is not directly estimated by swap tests.
This paper studies the quantum identity testing problem, a quantum analogue of distribution identity testing. The goal is to determine whether a quantum state is identical to another fixed quantum state, using as few state samples as possible. Rather than general entangled measurements, we consider the less powerful but experimentally friendly Pauli measurements. We follow the standard setting where Pauli measurements are regarded as two-outcome measurements, i.e., eachn-qubit Pauli measurement has a one-bit outcome. We prove that for ann-qubit quantum system, the sample complexity of this problem isΘ(poly(n)⋅ϵ24n)if only Pauli measurements are allowed. In other words, we provide simple algorithms to determine whether twon-qubit quantum states,$\rho and\sigma ,areidenticalor\epsilon −farintracedistanceusingPaulimeasurements,usingO\left({\min \{n^{4},n^{3}+\log ^{3}(1/\epsilon)\}\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)copiesof\rho and\sigma .Interestingly,\mathcal {O}\left({\frac {4^{n}}{\epsilon ^{2}}}\right)$copies are not sufficient under this setting.
Quantum state cloning is the task of approximately producing additional copies of an unknown quantum state from a finite number of input copies. The optimal cloning fidelity is known exactly for pure states, but no comparable characterization is known for general mixed states. We determine the optimal asymptotic copy complexity for d-dimensional states of rank at most r: producing M additional copies with worst-case fidelity at least 1−ε requires and is achievable with N=Θ(Mrd/ε) input copies. Remarkably, the lower bound already holds for a family of states with a fixed flat spectrum, while the matching upper bound is achieved by random purification followed by optimal pure-state cloning. For M=1, we further show that high-fidelity tomography can be coherently converted into cloning with comparable error, revealing an operational origin of the matching cloning and tomography complexities.
It is well-known that learning a pure n-qubit stabilizer state ∣ψ⟩ both requires, and can be accomplished with, access to a number of copies of ∣ψ⟩ linear in n. However, the precise constant coefficient of this scaling does not appear to have been determined. Here we prove that Lδ(n), the smallest number of copies from which a quantum procedure can identify any stabilizer state with failure probability at most 0<δ<1/8, satisfies n+⌈log2(1/δ)⌉−3≤Lδ(n)≤n+⌈log2(1/δ)⌉+4. We present a polynomial-time quantum learning algorithm that saturates this bound, achieving a constant factor improvement in sample-complexity over previously known approaches. As an immediate corollary, we obtain via the Choi-Jamiolkowski isomorphism an algorithm for learning an unknown n-qubit Clifford unitary from 2n+⌈log2(1/δ)⌉+4 queries, the n-dependence of which we show to be optimal. Our proof technique, which involves Fourier analysis on the abelian group Z4n×F2n(n−1)/2, seems to be qualitatively different to previous approaches to stabilizer state learning, and may be of some independent interest; in particular, it admits natural generalisations to further problems in quantum learning theory.
Fidelity is a fundamental measure for the closeness of two quantum states, which is important both from a theoretical and a practical point of view. Yet, in general, it is difficult to give good estimates of fidelity, especially when one works with mixed states over Hilbert spaces of very high dimension. Although, there has been some progress on fidelity estimation, all prior work either requires a large number of identical copies of the relevant states, or relies on unproven heuristics. In this work, we improve on both of these aspects by developing new and efficient quantum algorithms for fidelity estimation with provable performance guarantees in case at least one of the states is approximately low-rank. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation, as well as density matrix exponentiation and quantum spectral sampling. As a complementary result, we prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general, by giving a sample complexity lower bound that depends polynomially on the dimension. Moreover, if circuit descriptions for the relevant states are provided, we show that the task is hard for the complexity class called (honest verifier) quantum statistical zero knowledge via a reduction to a closely related result by Watrous.
We study the problems of quantum state certification, equivalence testing and independence testing. In certification, given samples of an unknown quantum state ρ and the description of a state σ, the goal is to test whether ρ=σ, or whether ρ and σ are far in a given distance measure. In equivalence testing, σ is also unknown and only accessible via samples. Independence testing decides whether ρAC=ρA⊗ρC, or is far from being a product. The sample complexities of these problems are now well-understood for a decision gap ε in trace distance: in the single-copy measurement setting with d-dimensional states, all three tasks can be solved using the same non-adaptive approach, which uses Θ(d3/2/ε2) samples and is optimal in general, even without adaptivity.
In this work, we consider decision gaps expressed in fidelity and study possible separations between these problems and how adaptivity can help. We prove that certification with respect to fidelity for a state σ of rank r does not benefit from adaptivity and requires Θ(r3/2/ε) samples. For equivalence testing and independence testing, we provide adaptive algorithms using O(min{d3/2/ε2,d9/4/ε}) and O(min{(dAdC)3/2/ε2,dA9/4dC3/4/ε}) samples, for dA≥dC, respectively. Our main technique is a framework that uses partial learning and a reduction to testing in ℓ2-distance, adapted from the distribution testing literature. We show that adaptivity matters for equivalence testing in fidelity by proving that Ω(1/ε2) samples are necessary in the non-adaptive case even for qubits, showing a separation from certification.
We study the problem of testing identity of a collection of unknown quantum states given sample access to this collection, each state appearing with some known probability. We show that for a collection of d -dimensional quantum states of cardinality N , the sample complexity is O(Nd/ϵ2) , with a matching lower bound, up to a multiplicative constant. The test is obtained by estimating the mean squared Hilbert-Schmidt distance between the states, thanks to a suitable generalization of the estimator of the Hilbert-Schmidt distance between two unknown states by Bădescu, O'Donnell, and Wright \cite{Badescu2019}.