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:1904.03218 · Leibniz international proceedings in informatics

Quantum Closeness Testing: A Streaming Algorithm and Applications

Nengkun Yu

Published Apr 5, 2019• 14 citations
arXivHTMLPDF

Abstract

In this paper, we study the quantum identity testing problem, i.e., testing whether two given quantum states are identical, and quantum independence testing problem, i.e., testing whether a given multipartite quantum state is in tensor product form. For the quantum identity testing problem of 𝒟(ℂ^d) system, we provide a deterministic measurement scheme that uses 𝒪(d²/ε²) copies via independent measurements with d being the dimension of the state and ε being the additive error. For the independence testing problem 𝒟(ℂ^d₁⊗ℂ^{d₂}⊗⋯⊗ℂ^{d_m}) system, we show that the sample complexity is Θ̃((Π_{i = 1}^m d_i)/ε²) via collective measurements, and 𝒪((Π_{i = 1}^m d_i²)/ε²) via independent measurements. If randomized choice of independent measurements are allowed, the sample complexity is Θ(d^{3/2}/ε²) for the quantum identity testing problem, and Θ̃((Π_{i = 1}^m d_i^{3/2})/ε²) for the quantum independence testing problem.

DOI
10.4230/lipics.itcs.2021.11

Related papers

Efficient Independence Testing for Quantum states

Nengkun Yu

We provide simple and efficient testers of problems about quantum independence by collective measurements and independent measurements, respectively. We show that given mixed states $\rho,\sigma\in \mathcal{D}(\mathbb{C}^{d})$, $O(\frac{d^2}{\epsilon^2})$ copies are sufficient to test whether $\rho=\sigma$ using independent measurements. Together with the identity tester in collective measurements setting \cite{BOW17}, we prove the following. Given multipartite mixed state $\rho\in \mathcal{D}(\mathbb{C}^{d_1}\otimes \mathbb{C}^{d_2}\otimes\cdots\otimes\mathbb{C}^{d_m})$, $\tilde{O}(\frac{\Pi_{i=1}^m d_i}{\epsilon^2})$ copies are sufficient and necessary to test whether $\rho$ is independent, i.e., in the tensor product form, by collective measurements, and $O(\frac{\Pi_{i=1}^m d_i^2}{\epsilon^2})$ copies are sufficient by independent measurements. Given $\rho_1,\rho_2, \cdots,\rho_n\in \mathcal{D}(\mathbb{C}^{d})$ in the query model, and $O(\frac{d}{\epsilon^2})$ copies are sufficient and necessary to test whether $\rho_i$s are all identical by collective measurements, $O(\frac{d^2}{\epsilon^2})$ copies are sufficient by independent measurements. Given $\rho_1,\rho_2, \cdots,\rho_n\in \mathcal{D}(\mathbb{C}^{d_1}\otimes \mathbb{C}^{d_2}\otimes\cdots\otimes\mathbb{C}^{d_m})$, $\tilde{O}(\frac{\Pi_{i=1}^m d_i}{\epsilon^2})$ copies are sufficient and necessary to test whether $\rho_i$s are independent by collective measurements, and $O(\frac{\Pi_{i=1}^m d_i^2}{\epsilon^2})$ copies are sufficient by independent measurements. The identity testing and independence testing in $\mathcal{D}(\mathbb{C}^{d_1}\otimes \mathbb{C}^{d_2})$ can be accomplished with $O(\frac{d_1^2d_2^2}{\epsilon^2})$ copies using just local measurements, respectively. This technique is used to provide efficient testers of conditional independence for classical-quantum-quantum states.

•Apr 5, 2019•3 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

Efficient Quantum State Identity Testing

Shih-Han Hung, Ming-Hsien Tsai

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

quant-pharXiv:2610.04597•Oct 6, 2026•0 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

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

Quantum chi-squared tomography and mutual information testing

Steven T. Flammia, Ryan O’Donnell

For quantum state tomography on rank- r dimension- d states, we show that O~(r.5d1.5/ϵ)≤O~(d2/ϵ) copies suffice for accuracy ϵ with respect to (Bures) χ2 -divergence, and O~(rd/ϵ) copies suffice for accuracy ϵ with respect to quantum relative entropy. The best previous bound was O~(rd/ϵ)≤O~(d2/ϵ) with respect to infidelity; our results are an improvement since infidelity is bounded above by both the relative entropy and the χ2 -divergence. For algorithms that are required to use single-copy measurements, we show that O~(r1.5d1.5/ϵ)≤O~(d3/ϵ) copies suffice for χ2 -divergence, and O~(r2d/ϵ) suffice for relative entropy.Using this tomography algorithm, we show that O~(d2.5/ϵ) copies of a d×d -dimensional bipartite state suffice to test if it has quantum mutual information 0 or at least ϵ . As a corollary, we also improve the best known sample complexity for the classical version of mutual information testing to O~(d/ϵ) .

arXiv:2305.18519•Quantum•Jun 20, 2024•12 citations
In this paper, we study the quantum identity testing problem, i.e., testing whether two given quantum states are identical, and quantum independence testing problem, i.e., testing whether a given multipartite quantum state is in tensor product form. For the quantum identity testing problem of 𝒟(ℂ^d) system, we provide a deterministic measurement scheme that uses 𝒪(d²/ε²) copies via independent measurements with d being the dimension of the state and ε being the additive error. For the independence testing problem 𝒟(ℂ^d₁⊗ℂ^{d₂}⊗⋯⊗ℂ^{d_m}) system, we show that the sample complexity is Θ̃((Π_{i = 1}^m d_i)/ε²) via collective measurements, and 𝒪((Π_{i = 1}^m d_i²)/ε²) via independent measurements. If randomized choice of independent measurements are allowed, the sample complexity is Θ(d^{3/2}/ε²) for the quantum identity testing problem, and Θ̃((Π_{i = 1}^m d_i^{3/2})/ε²) for the quantum independence testing problem.
We provide simple and efficient testers of problems about quantum independence by collective measurements and independent measurements, respectively. We show that given mixed states ρ,σ∈D(Cd)\rho,\sigma\in \mathcal{D}(\mathbb{C}^{d})ρ,σ∈D(Cd), O(d2ϵ2)O(\frac{d^2}{\epsilon^2})O(ϵ2d2​) copies are sufficient to test whether ρ=σ\rho=\sigmaρ=σ using independent measurements. Together with the identity tester in collective measurements setting \cite{BOW17}, we prove the following. Given multipartite mixed state ρ∈D(Cd1⊗Cd2⊗⋯⊗Cdm)\rho\in \mathcal{D}(\mathbb{C}^{d_1}\otimes \mathbb{C}^{d_2}\otimes\cdots\otimes\mathbb{C}^{d_m})ρ∈D(Cd1​⊗Cd2​⊗⋯⊗Cdm​), O~(Πi=1mdiϵ2)\tilde{O}(\frac{\Pi_{i=1}^m d_i}{\epsilon^2})O~(ϵ2Πi=1m​di​​) copies are sufficient and necessary to test whether ρ\rhoρ is independent, i.e., in the tensor product form, by collective measurements, and O(Πi=1mdi2ϵ2)O(\frac{\Pi_{i=1}^m d_i^2}{\epsilon^2})O(ϵ2Πi=1m​di2​​) copies are sufficient by independent measurements. Given ρ1,ρ2,⋯ ,ρn∈D(Cd)\rho_1,\rho_2, \cdots,\rho_n\in \mathcal{D}(\mathbb{C}^{d})ρ1​,ρ2​,⋯,ρn​∈D(Cd) in the query model, and O(dϵ2)O(\frac{d}{\epsilon^2})O(ϵ2d​) copies are sufficient and necessary to test whether ρi\rho_iρi​s are all identical by collective measurements, O(d2ϵ2)O(\frac{d^2}{\epsilon^2})O(ϵ2d2​) copies are sufficient by independent measurements. Given ρ1,ρ2,⋯ ,ρn∈D(Cd1⊗Cd2⊗⋯⊗Cdm)\rho_1,\rho_2, \cdots,\rho_n\in \mathcal{D}(\mathbb{C}^{d_1}\otimes \mathbb{C}^{d_2}\otimes\cdots\otimes\mathbb{C}^{d_m})ρ1​,ρ2​,⋯,ρn​∈D(Cd1​⊗Cd2​⊗⋯⊗Cdm​), O~(Πi=1mdiϵ2)\tilde{O}(\frac{\Pi_{i=1}^m d_i}{\epsilon^2})O~(ϵ2Πi=1m​di​​) copies are sufficient and necessary to test whether ρi\rho_iρi​s are independent by collective measurements, and O(Πi=1mdi2ϵ2)O(\frac{\Pi_{i=1}^m d_i^2}{\epsilon^2})O(ϵ2Πi=1m​di2​​) copies are sufficient by independent measurements. The identity testing and independence testing in D(Cd1⊗Cd2)\mathcal{D}(\mathbb{C}^{d_1}\otimes \mathbb{C}^{d_2})D(Cd1​⊗Cd2​) can be accomplished with O(d12d22ϵ2)O(\frac{d_1^2d_2^2}{\epsilon^2})O(ϵ2d12​d22​​) copies using just local measurements, respectively. This technique is used to provide efficient testers of conditional independence for classical-quantum-quantum states.
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}.
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ε.
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.
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.
For quantum state tomography on rank- r dimension- d states, we show that O~(r.5d1.5/ϵ)≤O~(d2/ϵ) copies suffice for accuracy ϵ with respect to (Bures) χ2 -divergence, and O~(rd/ϵ) copies suffice for accuracy ϵ with respect to quantum relative entropy. The best previous bound was O~(rd/ϵ)≤O~(d2/ϵ) with respect to infidelity; our results are an improvement since infidelity is bounded above by both the relative entropy and the χ2 -divergence. For algorithms that are required to use single-copy measurements, we show that O~(r1.5d1.5/ϵ)≤O~(d3/ϵ) copies suffice for χ2 -divergence, and O~(r2d/ϵ) suffice for relative entropy.Using this tomography algorithm, we show that O~(d2.5/ϵ) copies of a d×d -dimensional bipartite state suffice to test if it has quantum mutual information 0 or at least ϵ . As a corollary, we also improve the best known sample complexity for the classical version of mutual information testing to O~(d/ϵ) .