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.
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 consider the classic question of state tomography: given copies of an unknown quantum state ρ∈Cd×d, output ρ which is close to ρ in some sense, e.g. trace distance or fidelity. When one is allowed to make coherent measurements entangled across all copies, Θ(d2/ε2) copies are necessary and sufficient to get trace distance ε [18], [29]. Unfortunately, the protocols achieving this rate incur large quantum memory overheads that preclude implementation on near-term devices. On the other hand, the best known protocol using incoherent (single-copy) measurements uses O(d3/ε2) copies [24], and multiple papers have posed it as an open question to understand whether or not this rate is tight [6], [18]. In this work, we fully resolve this question, by showing that any protocol using incoherent measurements, even if they are chosen adaptively, requires Ω(d3/ε2) copies, matching the upper bound of [24]. We do so by a new proof technique which directly bounds the “tilt” of the posterior distribution after measurements, which yields a surprisingly short proof of our lower bound, and which we believe may be of independent interest. While this implies that adaptivity does not help for tomography with respect to trace distance, we show that it actually does help for tomography with respect to infidelity. We give an adaptive algorithm that outputs a state which is γ-close in infidelity to ρ using only O(d3/γ) copies, which is optimal for incoherent measurements. In contrast, it is known [18] that any nonadaptive algorithm requires Ω(d3/γ2) copies. While it is folklore that in 2 dimensions, one can achieve a scaling of O(1/γ), to the best of our knowledge, our algorithm is the first to achieve the optimal rate in all dimensions.
In this work, we consider the fundamental task of quantum state certification: given copies of an unknown quantum state ρ, test whether it matches some target state σ or is ε-far from it. For certifying d-dimensional states, Θ(d/ε2) copies of ρ are known to be necessary and sufficient. However, the algorithm achieving this complexity makes fully entangled measurements over all O(d/ε2) copies of ρ. Often, one is interested in certifying states to a high precision; this makes such joint measurements intractable even for low-dimensional states. Thus, we study whether one can obtain optimal rates for quantum state certification and related testing problems while only performing measurements on t copies at once, for some 1<t≪d/ε2. While it is well-understood how to use intermediate entanglement to achieve optimal quantum state learning, the only protocol known to achieve optimal testing is the one using fully entangled measurements.
Our main result is a smooth copy complexity upper bound for state certification as a function of t, which achieves a near-optimal rate at t=d2. In the high-precision regime, i.e., for ε<d1, this is a strict improvement over the entanglement used by the aforementioned optimal protocol. We also extend our techniques to develop new algorithms for the related tasks of mixedness testing and purity estimation, and show tradeoffs achieving the optimal rates for these problems at t=d2 as well. Our algorithms are based on novel reductions from testing to learning and leverage recent advances in quantum state tomography in a non-black-box fashion. We complement our testing upper bounds with a (nearly) matching lower bound that holds in the high-precision regime, implying that one must take t≥Ω(d2) to achieve the optimal rate for certification.
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 givend-dimensional quantum state is equal to orϵ-far in trace distance from the maximally mixed state. While it is known how to achieve optimalO(d/ϵ2)copy complexity using entangled measurements, we show that with independent measurements,Ω(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.
We consider the problem of quantum state certification, where we are given the description of a mixed state σ∈Cd×d,n copies of a mixed state ρ∈Cd×d, and ε>0, and we are asked to determine whether ρ=σ or whether ∥ρ−σ∥1>ε. When σ is the maximally mixed state d1Id, this is known as mixedness testing. We focus on algorithms which use incoherent measurements, i.e. which only measure one copy of ρ 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) 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) [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) copies are necessary. This fully resolves open questions of [15] and [5].•We show that the instance-optimal bounds for state certification to general σ 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.
We consider the problem of quantum state certification, where one is given n copies of an unknown d-dimensional quantum mixed state ρ, and one wants to test whether ρ is equal to some known mixed state σ or else is є-far from σ. The goal is to use notably fewer copies than the Ω(d2) needed for full tomography on ρ (i.e., density estimation). We give two robust state certification algorithms: one with respect to fidelity using n = O(d/є) copies, and one with respect to trace distance using n = O(d/є2) copies. The latter algorithm also applies when σ is unknown as well. These copy complexities are optimal up to constant factors.
We study hypothesis testing (aka state certification) in the non-identically distributed setting. A recent work (Garg et al. 2023) considered the classical case, in which one is given (independent) samples from T unknown probability distributions p1,…,pT on [d]={1,2,…,d}, and one wishes to accept/reject the hypothesis that their average pavg equals a known hypothesis distribution q. Garg et al. showed that if one has just c=2 samples from each pi, and provided T≫ε2d+ε41, one can (whp) distinguish pavg=q from dTV(pavg,q)>ε. This nearly matches the optimal result for the classical iid setting (namely, T≫ε2d). Besides optimally improving this result (and generalizing to tolerant testing with more stringent distance measures), we study the analogous problem of hypothesis testing for non-identical quantum states. Here we uncover an unexpected phenomenon: for any d-dimensional hypothesis state σ, and given just a single copy (c=1) of each state ρ1,…,ρT, one can distinguish ρavg=σ from Dtr(ρavg,σ)>ε provided T≫d/ε2. (Again, we generalize to tolerant testing with more stringent distance measures.) This matches the optimal result for the iid case, which is surprising because doing this with c=1 is provably impossible in the classical case. We also show that the analogous phenomenon happens for the non-iid extension of identity testing between unknown states. A technical tool we introduce may be of independent interest: an Efron-Stein inequality, and more generally an Efron-Stein decomposition, in the quantum setting.