Quantum Sequential Hypothesis Testing

• URL: http://arxiv.org/abs/2011.10773v2
• Date: Fri, 7 May 2021 10:08:10 GMT
• Title: Quantum Sequential Hypothesis Testing
• Abstract summary: We introduce sequential analysis in quantum information processing, by focusing on the fundamental task of quantum hypothesis testing. We obtain ultimate lower bounds on the average number of copies needed to accomplish the task. For qubit states we derive explicit expressions for the minimum average number of copies and show that a sequential strategy based on fixed local measurements outperforms the best collective measurement.
• Score: 1.1545092788508222
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce sequential analysis in quantum information processing, by focusing on the fundamental task of quantum hypothesis testing. In particular our goal is to discriminate between two arbitrary quantum states with a prescribed error threshold, $\epsilon$, when copies of the states can be required on demand. We obtain ultimate lower bounds on the average number of copies needed to accomplish the task. We give a block-sampling strategy that allows to achieve the lower bound for some classes of states. The bound is optimal in both the symmetric as well as the asymmetric setting in the sense that it requires the least mean number of copies out of all other procedures, including the ones that fix the number of copies ahead of time. For qubit states we derive explicit expressions for the minimum average number of copies and show that a sequential strategy based on fixed local measurements outperforms the best collective measurement on a predetermined number of copies. Whereas for general states the number of copies increases as $\log 1/\epsilon$, for pure states sequential strategies require a finite average number of samples even in the case of perfect discrimination, i.e., $\epsilon=0$.

Related papers

• Random Projections for Multi-Copy Quantum Algorithms [3.995502708329505]
  Estimating nonlinear properties of quantum states is a central task in quantum information science.<n>Standard protocols based on swap tests require coherent operations on the full Hilbert space.<n>We introduce a framework for multi-copy measurements based on random projections onto lower-dimensional subspaces.
  arXiv  Detail & Related papers  (2026-06-18T13:49:14Z)
• Quantum Sequential Universal Hypothesis Testing [62.751483592497806]
  Quantum hypothesis testing (QHT) concerns the statistical inference of unknown quantum states.<n>We introduce the quantum sequential universal test (QSUT), a novel framework for sequential QHT in the general case of composite hypotheses.<n> QSUT builds on universal inference, and it alternates between adaptive local measurements aimed at exploring the hypothesis space and joint measurements optimized for maximal discrimination.
  arXiv  Detail & Related papers  (2025-08-29T12:50:04Z)
• Bounds in Sequential Unambiguous Discrimination of Multiple Pure Quantum States [1.9662978733004601]
  We derive performance bounds for sequential methods when applied to the discrimination of a set of pure states. The gap between these bounds is minimal, scaling logarithmically with the number of distinct states.
  arXiv  Detail & Related papers  (2025-04-30T14:46:04Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  We introduce a new toolkit for analyzing cloning games.<n>This framework allows us to analyze a new cloning game based on binary phase states.<n>We show that the binary phase variantally optimal bound offers quantitative insights into information scrambling in idealized models of black holes.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• Keep Guessing? When Considering Inference Scaling, Mind the Baselines [45.21178011740911]
  Scaling inference compute in large language models consistently increases the coverage (fraction of problems solved) as the number of samples increases. We conjecture that this observed improvement is partially due to the answer distribution of standard evaluation benchmarks, which is skewed towards a relatively small set of common answers.
  arXiv  Detail & Related papers  (2024-10-20T18:43:05Z)
• Sample-Optimal Quantum State Tomography for Structured Quantum States in One Dimension [25.333797381352973]
  We study whether the number of state copies can saturate the information theoretic bound (i.e., $O(n)$) using physical quantum measurements. We propose a projected gradient descent (PGD) algorithm to solve the constrained least-squares problem and show that it can efficiently find an estimate with bounded recovery error.
  arXiv  Detail & Related papers  (2024-10-03T15:26:26Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• Lower bounds for learning quantum states with single-copy measurements [3.2590610391507444]
  We study the problems of quantum tomography and shadow tomography using measurements performed on individual copies of an unknown $d$-dimensional state. In particular, this rigorously establishes the optimality of the folklore Pauli tomography" algorithm in terms of its complexity.
  arXiv  Detail & Related papers  (2022-07-29T02:26:08Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Distributed quantum inner product estimation [14.222887950206658]
  A benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers. No quantum communication can be performed between the two physical platforms due to hardware constraints. We show that the sample complexity must be at least $Omega(max1/varepsilon2,sqrtd/varepsilon)$, even in the strongest setting.
  arXiv  Detail & Related papers  (2021-11-05T05:35:03Z)
• Optimal Adaptive Strategies for Sequential Quantum Hypothesis Testing [87.17253904965372]
  We consider sequential hypothesis testing between two quantum states using adaptive and non-adaptive strategies. We show that these errors decrease exponentially with decay rates given by the measured relative entropies between the two states.
  arXiv  Detail & Related papers  (2021-04-30T00:52:48Z)
• Efficient Verification of Anticoncentrated Quantum States [0.38073142980733]
  I present a novel method for estimating the fidelity $F(mu,tau)$ between a preparable quantum state $mu$ and a classically specified target state $tau$. I also present a more sophisticated version of the method, which uses any efficiently preparable and well-characterized quantum state as an importance sampler.
  arXiv  Detail & Related papers  (2020-12-15T18:01:11Z)
• Entanglement is Necessary for Optimal Quantum Property Testing [15.58122727889318]
  We show that with independent measurements, $Omega(d4/3/epsilon2)$ is necessary, even if the measurements are chosen adaptively. We develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing.
  arXiv  Detail & Related papers  (2020-04-16T18:28:39Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.