Can adaptive strategies outperform non-adaptive ones for quantum hypothesis selection? We exhibit problems where adaptive strategies provably reduce the number of required samples by a factor four in the worst case, and possibly more when the actual difficulty of the problem makes it possible. In addition, we exhibit specific hypotheses classes for which there is a provable polynomial separation between adaptive and non-adaptive strategies-a specificity of the quantum framework that does not appear in classical testing.
Can adaptive strategies outperform non-adaptive ones for quantum hypothesis selection? We exhibit problems where adaptive strategies provably reduce the number of required samples by a factor four in the worst case, and possibly more when the actual difficulty of the problem makes it possible. In addition, we exhibit specific hypotheses classes for which there is a provable polynomial separation between adaptive and non-adaptive strategies-a specificity of the quantum framework that does not appear in classical testing.
We consider sequential hypothesis testing between two quantum states using adaptive and non-adaptive strategies. In this setting, samples of an unknown state are requested sequentially and a decision to either continue or to accept one of the two hypotheses is made after each test. Under the constraint that the number of samples is bounded, either in expectation or with high probability, we exhibit adaptive strategies that minimize both types of misidentification errors. Namely, we show that these errors decrease exponentially (in the stopping time) with decay rates given by the measured relative entropies between the two states. Moreover, if we allow joint measurements on multiple samples, the rates are increased to the respective quantum relative entropies. We also fully characterize the achievable error exponents for non-adaptive strategies and provide numerical evidence showing that adaptive measurements are necessary to achieve our bounds.
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 present a broad investigation of asymptotic binary hypothesis testing, when each hypothesis represents asymptotically many independent instances of a quantum channel, and the tests are based on using the unknown channel multiple times and observing its output at the end. Unlike the familiar setting of quantum states as hypotheses, there is a fundamental distinction between adaptive and non-adaptive strategies with respect to the channel uses, and we introduce a number of further variants of the discrimination tasks by imposing different restrictions on the test strategies. Our main result is the first separation between adaptive and non-adaptive symmetric hypothesis testing exponents for quantum channels, which we derive from a general lower bound on the error probability for non-adaptive strategies; the concrete example we analyze is a pair of entanglement-breaking channels. Full details in [1].
We present a broad investigation of asymptotic binary hypothesis testing, when each hypothesis represents asymptotically many independent instances of a quantum channel, and the tests are based on using the unknown channel and observing its output. Unlike the familiar setting of quantum states as hypotheses, there is a fundamental distinction between adaptive and non-adaptive strategies with respect to the channel uses, and we introduce a number of further variants of the discrimination tasks by imposing different restrictions on the test strategies. The following results are obtained: (1) The first separation between adaptive and non-adaptive symmetric hypothesis testing exponents for quantum channels, which we derive from a general lower bound on the error probability for non-adaptive strategies; the concrete example we analyze is a pair of entanglement-breaking channels. (2) We prove that for classical-quantum channels, adaptive and non-adaptive strategies lead to the same error exponents both in the symmetric (Chernoff) and asymmetric (Hoeffding, Stein) settings. (3) We prove, in some sense generalizing the previous statement, that for general channels adaptive strategies restricted to classical feed-forward and product state channel inputs are not superior in the asymptotic limit to non-adaptive product state strategies. (4) As an application of our findings, we address the discrimination power of quantum channels and show that adaptive strategies with classical feedback and no quantum memory at the input do not increase the discrimination power of entanglement-breaking channel beyond non-adaptive tensor product input strategies.
Adaptiveness is a key principle in information processing including statistics and machine learning. We investigate the usefulness adaptive methods in the framework of asymptotic binary hypothesis testing, when each hypothesis represents asymptotically many independent instances of a quantum channel, and the tests are based on using the unknown channel and observing outputs. Unlike the familiar setting of quantum states as hypotheses, there is a fundamental distinction between adaptive and nonadaptive strategies with respect to the channel uses, and we introduce a number of further variants of the discrimination tasks by imposing different restrictions on the test strategies. The following results are obtained: (1) We prove that for classical-quantum channels, adaptive and nonadaptive strategies lead to the same error exponents both in the symmetric (Chernoff) and asymmetric (Hoeffding, Stein) settings. (2) The first separation between adaptive and nonadaptive symmetric hypothesis testing exponents for quantum channels, which we derive from a general lower bound on the error probability for nonadaptive strategies; the concrete example we analyze is a pair of entanglement-breaking channels. (3) We prove, in some sense generalizing the previous statement, that for general channels adaptive strategies restricted to classical feed-forward and product state channel inputs are not superior in the asymptotic limit to nonadaptive product state strategies. (4) As an application of our findings, we address the discrimination power of an arbitrary quantum channel and show that adaptive strategies with classical feedback and no quantum memory at the input do not increase the discrimination power of the channel beyond nonadaptive tensor product input strategies.
Quantum phase estimation is one of the most important tools in quantum algorithms. It can be made non-adaptive (meaning all applications of the unitary Uφ happen simultaneously) without using more applications of Uφ, albeit at the expense of using many more qubits. It is also known that there is no advantage for adaptive algorithms in the case where the phase that needs to be estimated is arbitrary or is uniformly random. Here we give examples of a special case of phase estimation, with a promise on the values that the unknown phase can take, where adaptive methods are provably better than non-adaptive methods by a factor of nearly 2 in the number of uses of Uφ. We also prove some upper bounds on the maximum advantage that adaptive algorithms for phase estimation can achieve over non-adaptive ones.