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.
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.
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.
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 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.
How many samples of a quantum state are required to learn a complete description of it? As we will see in this thesis, the fine-grained answer depends on the measurements available to the learner, but in general it is at least Ω(d^2/ϵ^2) where d is the dimension of the state and ϵ the trace distance accuracy. Optimal algorithms for this task -- known as quantum state tomography -- make use of powerful, yet highly impractical entangled measurements, where some joint measurement is performed on all copies of the state. What can be accomplished without such measurements, where one must perform measurements on individual copies of the states? \n \nIn Chapter 2 we show a relationship between the recently proposed quantum online learning framework and quantum state tomography. Specifically, we show that tomography can be accomplished using online learning algorithms in a black-box manner and O(d^4/ϵ^4) two-outcome measurements on separate copies of the state. The interpretation of this approach is that the experimentalist uses informative measurements to teach the learner by helping it make "mistakes" on measurements as early as possible. \n \nWe move on to proving lower bounds on tomography in Chapter 3. First, we review a known lower bound for entangled measurements as well as a Ω(d^3/ϵ^2) lower bound in the setting where non-entangled measurements are made non-adaptively, both due to Ref.[18]. We then derive a novel bound of Ω(d^4/ϵ^2) samples when the learner is further restricted to observing a constant number of outcomes (e.g., two-outcome measurements). This implies that the folklore "Pauli tomography" algorithm is optimal in this setting. \n \nUnderstanding the power of adaptive measurements, where measurement choices can depend on previous outcomes, is currently an open problem. In Chapter 4 we present two scenarios in which adapting on previous outcomes makes no difference to the number of samples required. In the first, the learner is limited to adapting on at most o(d^2/ϵ^2) of the previous outcomes. In the second, measurements are drawn from some set of at most exp(O(d)) measurements. In particular, this second lower bound implies that adaptivity makes no difference in the regime of efficiently implementable measurements, in the context of quantum computing. \n \nFinally, we apply the above technique to the problems of classical shadows and shadow tomography to obtain similar lower bounds. Here, one is interested only in determining the expectations of some fixed set of observables. We once again find that, for the worst-case input of observables, adaptivity makes no difference to the sample complexity when considering efficient, non-entangled measurements. As a corollary, we find a straightforward algorithm for shadow tomography is optimal in this setting.
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.
There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.