CaltechAUTHORS
  A Caltech Library Service

Adversarial hypothesis testing and a quantum stein's lemma for restricted measurements

Brandão, Fernando G. S. L. and Harrow, Aram W. and Lee, James R. and Peres, Yuval (2014) Adversarial hypothesis testing and a quantum stein's lemma for restricted measurements. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science. Association for Computing Machinery , New York, NY, pp. 183-194. ISBN 9781450326988. https://resolver.caltech.edu/CaltechAUTHORS:20200730-074813402

[img] PDF - Published Version
See Usage Policy.

693Kb
[img] PDF - Submitted Version
See Usage Policy.

599Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200730-074813402

Abstract

Recall the classical hypothesis testing setting with two convex sets of probability distributions P and Q. One receives either n i.i.d. samples from a distribution p ∈ P or from a distribution q ∈ Q and wants to decide from which set the points were sampled. It is known that the optimal exponential rate at which errors decrease can be achieved by a simple maximum-likelihood ratio test which does not depend on p or q, but only on the sets P and Q. We consider an adaptive generalization of this model where the choice of p ∈ P and q ∈ Q can change in each sample in some way that depends arbitrarily on the previous samples. In other words, in the kth round, an adversary, having observed all the previous samples in rounds 1, ..., κ-1, chooses p_κ ∈ P and q_κ ∈ Q, with the goal of confusing the hypothesis test. We prove that even in this case, the optimal exponential error rate can be achieved by a simple maximum-likelihood test that depends only on P and Q. We then show that the adversarial model has applications in hypothesis testing for quantum states using restricted measurements. For example, it can be used to study the problem of distinguishing entangled states from the set of all separable states using only measurements that can be implemented with local operations and classical communication (LOCC). The basic idea is that in our setup, the deleterious effects of entanglement can be simulated by an adaptive classical adversary. We prove a quantum Stein's Lemma in this setting: In many circumstances, the optimal hypothesis testing rate is equal to an appropriate notion of quantum relative entropy between two states. In particular, our arguments yield an alternate proof of Li and Winter's recent strengthening of strong subadditivity for quantum relative entropy.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1145/2554797.2554816DOIArticle
https://arxiv.org/abs/1308.6702arXivDiscussion Paper
https://resolver.caltech.edu/CaltechAUTHORS:20200730-074100066Related ItemJournal Article
ORCID:
AuthorORCID
Brandão, Fernando G. S. L.0000-0003-3866-9378
Harrow, Aram W.0000-0003-3220-7682
Additional Information:© 2014 is held by the owner/author(s). Publication rights licensed to ACM. We are grateful to Keiji Matsumoto for helpful conversations about hypothesis testing, and AWH and FGSLB also thank the Mittag-Leffler Institute for their hospitality while some of this work was done. FB was funded by EPSRC. AWH was funded by NSF grant CCF-1111382 and ARO contract W911NF-12-1-0486. JRL was supported by NSF grants CCF-1217256 and CCF-0905626.
Funders:
Funding AgencyGrant Number
Engineering and Physical Sciences Research Council (EPSRC)UNSPECIFIED
NSFCCF-1111382
Army Research Office (ARO)W911NF-12-1-0486
NSFCCF-1217256
NSFCCF-0905626
Subject Keywords:quantum information theory, entanglement testing, composite hypothesis testing
Record Number:CaltechAUTHORS:20200730-074813402
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200730-074813402
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104653
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:30 Jul 2020 15:47
Last Modified:30 Jul 2020 15:47

Repository Staff Only: item control page