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

Efficient Independence Testing for Quantum states

Nengkun Yu

Published Apr 5, 2019• 4 citations
OpenAlex

Abstract

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.

Related papers

Quantum Closeness Testing: A Streaming Algorithm and Applications

Nengkun Yu

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.

arXiv:1904.03218•Leibniz international proceedings in informatics•Apr 5, 2019•22 citations

Entanglement is Necessary for Optimal Quantum Property Testing

Sébastien Bubeck, Sitan Chen, Jerry Zheng Li

There has been a surge of progress in recent years in developing algorithms for testing and learning quantum states that achieve optimal copy complexity [1]–[6]. Unfortunately, they require the use of entangled measurements across many copies of the underlying state and thus remain outside the realm of what is currently experimentally feasible. A natural question is whether one can match the copy complexity of such algorithms using only independent-but possibly adaptively chosen-measurements on individual copies. We answer this in the negative for arguably the most basic quantum testing problem: deciding whether a given$d$-dimensional quantum state is equal to or$\epsilon$-far in trace distance from the maximally mixed state. While it is known how to achieve optimal$O(d/\epsilon^{2})$copy complexity using entangled measurements, we show that with independent measurements,$\Omega(d^{4/3}/\epsilon^{2})$is necessary, even if the measurements are chosen adaptively. This resolves a question posed in [7]. To obtain this lower bound, we develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing, which may be of independent interest.

arXiv:2004.07869•Annual Symposium on Foundations of Computer Science•Nov 1, 2020•59 citations

Comparison of mixed quantum states

Shengshi Pang, Shengjun Wu

In this article, we study the problem of comparing mixed quantum states: given $n$ unknown mixed quantum states, can one determine whether they are identical or not with an unambiguous quantum measurement? We first study the universal comparison of mixed quantum states, and prove that this task is generally impossible to accomplish. Then, we focus on the unambiguous comparison of $n$ mixed quantum states arbitrarily chosen from a set of $k$ mixed quantum states. The condition for the existence of an unambiguous measurement operator which can produce a conclusive result when the unknown states are actually the same and the condition for the existence of an unambiguous measurement operator when the unknown states are actually different are studied independently. We derive a necessary and sufficient condition for the existence of the first measurement operator, and a necessary condition and two sufficient conditions for the second. Furthermore, we find that the sufficiency of the necessary condition for the second measurement operator has a simple and interesting dependence on $n$ and $k$. At the end, a unified condition is obtained for the simultaneous existence of these two unambiguous measurement operators.

arXiv:1003.5145•Physical Review A•Jul 29, 2011•8 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

Tight Bounds for Quantum State Certification with Incoherent Measurements

Sitan Chen, Jerry Zheng Li, Brice Huang +1 more

We consider the problem of quantum state certification, where we are given the description of a mixed state $\sigma\in\mathbb{C}^{d\times d},n$ copies of a mixed state $\rho\in\mathbb{C}^{d\times d}$, and $\varepsilon\gt 0$, and we are asked to determine whether $\rho=\sigma$ or whether $\|\rho-\sigma\|_{1}\gt \varepsilon$. When $\sigma$ is the maximally mixed state $\frac{1}{d}I_{d}$, this is known as mixedness testing. We focus on algorithms which use incoherent measurements, i.e. which only measure one copy of $\rho$ at a time. Unlike those that use entangled, multi-copy measurements, these can be implemented without persistent quantum memory and thus represent a large class of protocols that can be run on current or near-term devices. For mixedness testing, there is a folklore algorithm which uses incoherent measurements and only needs $O(d^{3/2}/\varepsilon^{2})$ copies. The algorithm is non-adaptive, that is, its measurements are fixed ahead of time, and is known to be optimal for non-adaptive algorithms. However, when the algorithm can make arbitrary incoherent measurements, the best known lower bound is only $\Omega(d^{4/3}/\varepsilon^{2})$ [5], and it has been an outstanding open problem to close this polynomial gap. In this work: •We settle the copy complexity of mixedness testing with incoherent measurements and show that $\Omega(d^{3/2}/\varepsilon^{2})$ copies are necessary. This fully resolves open questions of [15] and [5].•We show that the instance-optimal bounds for state certification to general $\sigma$ first derived in [7] for non-adaptive measurements also hold for arbitrary incoherent measurements. Qualitatively, our results say that adaptivity does not help at all for these problems. Our results are based on new techniques that allow us to reduce the problem to understanding the concentration of certain matrix martingales, which we believe may be of independent interest.

arXiv:2204.07155•Annual Symposium on Foundations of Computer Science•Oct 1, 2022•42 citations
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.
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.
There has been a surge of progress in recent years in developing algorithms for testing and learning quantum states that achieve optimal copy complexity [1]–[6]. Unfortunately, they require the use of entangled measurements across many copies of the underlying state and thus remain outside the realm of what is currently experimentally feasible. A natural question is whether one can match the copy complexity of such algorithms using only independent-but possibly adaptively chosen-measurements on individual copies. We answer this in the negative for arguably the most basic quantum testing problem: deciding whether a givenddd-dimensional quantum state is equal to orϵ\epsilonϵ-far in trace distance from the maximally mixed state. While it is known how to achieve optimalO(d/ϵ2)O(d/\epsilon^{2})O(d/ϵ2)copy complexity using entangled measurements, we show that with independent measurements,Ω(d4/3/ϵ2)\Omega(d^{4/3}/\epsilon^{2})Ω(d4/3/ϵ2)is necessary, even if the measurements are chosen adaptively. This resolves a question posed in [7]. To obtain this lower bound, we develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing, which may be of independent interest.
In this article, we study the problem of comparing mixed quantum states: given nnn unknown mixed quantum states, can one determine whether they are identical or not with an unambiguous quantum measurement? We first study the universal comparison of mixed quantum states, and prove that this task is generally impossible to accomplish. Then, we focus on the unambiguous comparison of nnn mixed quantum states arbitrarily chosen from a set of kkk mixed quantum states. The condition for the existence of an unambiguous measurement operator which can produce a conclusive result when the unknown states are actually the same and the condition for the existence of an unambiguous measurement operator when the unknown states are actually different are studied independently. We derive a necessary and sufficient condition for the existence of the first measurement operator, and a necessary condition and two sufficient conditions for the second. Furthermore, we find that the sufficiency of the necessary condition for the second measurement operator has a simple and interesting dependence on nnn and kkk. At the end, a unified condition is obtained for the simultaneous existence of these two unambiguous measurement operators.
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.
We consider the problem of quantum state certification, where we are given the description of a mixed state σ∈Cd×d,n\sigma\in\mathbb{C}^{d\times d},nσ∈Cd×d,n copies of a mixed state ρ∈Cd×d\rho\in\mathbb{C}^{d\times d}ρ∈Cd×d, and ε>0\varepsilon\gt 0ε>0, and we are asked to determine whether ρ=σ\rho=\sigmaρ=σ or whether ∥ρ−σ∥1>ε\|\rho-\sigma\|_{1}\gt \varepsilon∥ρ−σ∥1​>ε. When σ\sigmaσ is the maximally mixed state 1dId\frac{1}{d}I_{d}d1​Id​, this is known as mixedness testing. We focus on algorithms which use incoherent measurements, i.e. which only measure one copy of ρ\rhoρ at a time. Unlike those that use entangled, multi-copy measurements, these can be implemented without persistent quantum memory and thus represent a large class of protocols that can be run on current or near-term devices. For mixedness testing, there is a folklore algorithm which uses incoherent measurements and only needs O(d3/2/ε2)O(d^{3/2}/\varepsilon^{2})O(d3/2/ε2) copies. The algorithm is non-adaptive, that is, its measurements are fixed ahead of time, and is known to be optimal for non-adaptive algorithms. However, when the algorithm can make arbitrary incoherent measurements, the best known lower bound is only Ω(d4/3/ε2)\Omega(d^{4/3}/\varepsilon^{2})Ω(d4/3/ε2) [5], and it has been an outstanding open problem to close this polynomial gap. In this work: •We settle the copy complexity of mixedness testing with incoherent measurements and show that Ω(d3/2/ε2)\Omega(d^{3/2}/\varepsilon^{2})Ω(d3/2/ε2) copies are necessary. This fully resolves open questions of [15] and [5].•We show that the instance-optimal bounds for state certification to general σ\sigmaσ first derived in [7] for non-adaptive measurements also hold for arbitrary incoherent measurements. Qualitatively, our results say that adaptivity does not help at all for these problems. Our results are based on new techniques that allow us to reduce the problem to understanding the concentration of certain matrix martingales, which we believe may be of independent interest.