Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.04597

Efficient Quantum State Identity Testing

Shih-Han Hung, Ming-Hsien Tsai

quant-phSubmitted Oct 3, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

Abstract

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$.

Comments
24 pages

Related papers

Almost Tight Sample Complexity Analysis of Quantum Identity Testing by Pauli Measurements

Nengkun Yu

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., each$n$-qubit Pauli measurement has a one-bit outcome. We prove that for an$n$-qubit quantum system, the sample complexity of this problem is$\Theta \left({\mathrm {poly}(n)\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)$if only Pauli measurements are allowed. In other words, we provide simple algorithms to determine whether two$n$-qubit quantum states,$\rho $and$\sigma $, are identical or$\epsilon $-far in trace distance using Pauli measurements, using$O\left({\min \{n^{4},n^{3}+\log ^{3}(1/\epsilon)\}\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)$copies of$\rho $and$\sigma $. Interestingly,$\mathcal {O}\left({\frac {4^{n}}{\epsilon ^{2}}}\right)$copies are not sufficient under this setting.

IEEE Transactions on Information Theory•Apr 27, 2023•3 citations

Optimal copy complexity of quantum state cloning

Sangwoo Jeon, Vaughn Sohn, Changhun Oh

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-\varepsilon$ requires and is achievable with $N=Θ(Mrd/\varepsilon)$ 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.

quant-pharXiv:2608.24484•Aug 26, 2026•0 citations

Sample-optimal learning of stabilizer states

Rebecca Chang, Matthias C. Caro, Martin Larocca +1 more

It is well-known that learning a pure $n$-qubit stabilizer state $|ψ\rangle$ both requires, and can be accomplished with, access to a number of copies of $|ψ\rangle$ 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+\lceil\log_2(1/δ)\rceil-3\leq L_δ(n)\leq n+\left\lceil\log_2(1/δ)\right\rceil+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+\left\lceil\log_2(1/δ)\right\rceil+4$ queries, the $n$-dependence of which we show to be optimal. Our proof technique, which involves Fourier analysis on the abelian group $\mathbb{Z}_4^n \times \mathbb{F}_2^{n(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.

quant-pharXiv:2609.10974•Sep 11, 2026•0 citations

Improved Quantum Algorithms for Fidelity Estimation

András Gilyén, Alexander Poremba

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.

arXiv:2203.15993•Mar 30, 2022•14 citations

On the Power of Adaptivity in Testing Quantum States in Fidelity

Jan Seyfried, Sayantan Sen, Marco Tomamichel

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\otimesρ_C$, or is far from being a product. The sample complexities of these problems are now well-understood for a decision gap $\varepsilon$ 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 $Θ(d^{3/2}/\varepsilon^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 $\widetildeΘ(r^{3/2}/\varepsilon)$ samples. For equivalence testing and independence testing, we provide adaptive algorithms using $\widetilde{O}(\min\{d^{3/2}/\varepsilon^2,d^{9/4}/\varepsilon\})$ and $\widetilde{O}(\min\{(d_Ad_C)^{3/2}/\varepsilon^2,d_A^{9/4}d_C^{3/4}/\varepsilon\})$ samples, for $d_A\geq d_C$, respectively. Our main technique is a framework that uses partial learning and a reduction to testing in $\ell_2$-distance, adapted from the distribution testing literature. We show that adaptivity matters for equivalence testing in fidelity by proving that $\widetildeΩ(1/\varepsilon^2)$ samples are necessary in the non-adaptive case even for qubits, showing a separation from certification.

quant-pharXiv:2609.08733•Sep 9, 2026•0 citations

Testing identity of collections of quantum states: sample complexity analysis

Marco Fanizza, Raffaele Salvia, Vittorio Giovannetti

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}.

arXiv:2103.14511•Quantum•Sep 11, 2023•1 citation
We study the following quantum state identity problem: given access to copies of nnn unknown pure quantum states, the goal is to determine whether every pair has fidelity at least 1−ε1-\varepsilon1−ε 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 ε∈(0,1/4)\varepsilon\in(0,1/4)ε∈(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/δ))O(\log(n/δ)\log(2/δ))O(log(n/δ)log(2/δ)) copies of each input state to succeed with probability at least 1−δ1-δ1−δ. The second uses the Schur transform to reduce the sample complexity to O(log⁡(n/δ))O(\log(n/δ))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/δ))Ω(\log(n/δ))Ω(log(n/δ)) for any quantum algorithm with failure probability at most δ≤1/2−cδ\le 1/2-cδ≤1/2−c, for any constant c>0c>0c>0, establishing that the second algorithm achieves the optimal dependence on both nnn and δδδ for fixed ε\varepsilonε.
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., eachnnn-qubit Pauli measurement has a one-bit outcome. We prove that for annnn-qubit quantum system, the sample complexity of this problem isΘ(poly(n)⋅4nϵ2)\Theta \left({\mathrm {poly}(n)\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)Θ(poly(n)⋅ϵ24n​)if only Pauli measurements are allowed. In other words, we provide simple algorithms to determine whether twonnn-qubit quantum states,$\rho andandand\sigma ,areidenticalor, are identical or,areidenticalor\epsilon −farintracedistanceusingPaulimeasurements,using-far in trace distance using Pauli measurements, using−farintracedistanceusingPaulimeasurements,usingO\left({\min \{n^{4},n^{3}+\log ^{3}(1/\epsilon)\}\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)copiesofcopies ofcopiesof\rho andandand\sigma .Interestingly,. Interestingly,.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 ddd-dimensional states of rank at most rrr: producing MMM additional copies with worst-case fidelity at least 1−ε1-\varepsilon1−ε requires and is achievable with N=Θ(Mrd/ε)N=Θ(Mrd/\varepsilon)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=1M=1M=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 nnn-qubit stabilizer state ∣ψ⟩|ψ\rangle∣ψ⟩ both requires, and can be accomplished with, access to a number of copies of ∣ψ⟩|ψ\rangle∣ψ⟩ linear in nnn. However, the precise constant coefficient of this scaling does not appear to have been determined. Here we prove that Lδ(n)L_δ(n)Lδ​(n), the smallest number of copies from which a quantum procedure can identify any stabilizer state with failure probability at most 0<δ<1/80<δ<1/80<δ<1/8, satisfies n+⌈log⁡2(1/δ)⌉−3≤Lδ(n)≤n+⌈log⁡2(1/δ)⌉+4n+\lceil\log_2(1/δ)\rceil-3\leq L_δ(n)\leq n+\left\lceil\log_2(1/δ)\right\rceil+4n+⌈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 nnn-qubit Clifford unitary from 2n+⌈log⁡2(1/δ)⌉+42n+\left\lceil\log_2(1/δ)\right\rceil+42n+⌈log2​(1/δ)⌉+4 queries, the nnn-dependence of which we show to be optimal. Our proof technique, which involves Fourier analysis on the abelian group Z4n×F2n(n−1)/2\mathbb{Z}_4^n \times \mathbb{F}_2^{n(n-1)/2}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ρ_{AC}=ρ_A\otimesρ_CρAC​=ρA​⊗ρC​, or is far from being a product. The sample complexities of these problems are now well-understood for a decision gap ε\varepsilonε in trace distance: in the single-copy measurement setting with ddd-dimensional states, all three tasks can be solved using the same non-adaptive approach, which uses Θ(d3/2/ε2)Θ(d^{3/2}/\varepsilon^2)Θ(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 rrr does not benefit from adaptivity and requires Θ~(r3/2/ε)\widetildeΘ(r^{3/2}/\varepsilon)Θ(r3/2/ε) samples. For equivalence testing and independence testing, we provide adaptive algorithms using O~(min⁡{d3/2/ε2,d9/4/ε})\widetilde{O}(\min\{d^{3/2}/\varepsilon^2,d^{9/4}/\varepsilon\})O(min{d3/2/ε2,d9/4/ε}) and O~(min⁡{(dAdC)3/2/ε2,dA9/4dC3/4/ε})\widetilde{O}(\min\{(d_Ad_C)^{3/2}/\varepsilon^2,d_A^{9/4}d_C^{3/4}/\varepsilon\})O(min{(dA​dC​)3/2/ε2,dA9/4​dC3/4​/ε}) samples, for dA≥dCd_A\geq d_CdA​≥dC​, respectively. Our main technique is a framework that uses partial learning and a reduction to testing in ℓ2\ell_2ℓ2​-distance, adapted from the distribution testing literature. We show that adaptivity matters for equivalence testing in fidelity by proving that Ω~(1/ε2)\widetildeΩ(1/\varepsilon^2)Ω(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}.