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

Please wait, while we are loading the content...

Lattice-based FHE as secure as PKE

On the structure of boolean functions with small spectral norm

Invitation games and the price of stability

Private interactive communication across an adversarial channel

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

Black-box obfuscation for d-CNFs

Attribute-efficient evolvability of linear functions

Testers and their applications

Deterministic compression with uncertain priors

Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems

Decompositions of triangle-dense graphs

Direct sum fails for zero error average communication

Cryptogenography

Non-commutative arithmetic circuits with division

The computational hardness of pricing compound options

Tree codes and a conjecture on exponential sums

Sequential decision making with vector outcomes

Candidate weak pseudorandom functions in $AC^{0}$ ○ $MOD_{2}$

An efficient algorithm for finding the ground state of 1D gapped local hamiltonians

Expanders with respect to Hadamard spaces and random graphs: extended abstract

Faster private release of marginals on small databases

Complexity of approximating CSP with balance / hard constraints

Partial tests, universal tests and decomposability

Rational arguments: single round delegation with sublinear verification

Limits of random oracles in secure computation

Decision trees, protocols and the entropy-influence conjecture

Welfare maximization and truthfulness in mechanism design with ordinal preferences

Capacity of non-malleable codes

Learning mixtures of arbitrary distributions over large discrete domains

Iterated group products and leakage resilience against NC1

Energy-efficient circuit design

On the automorphism groups of strongly regular graphs I

Mechanism design in large games: incentives and privacy

Integer feasibility of random polytopes: random integer programs

High dimensional expanders and property testing

Optimal provision-after-wait in healthcare

Robust device independent quantum key distribution

Locally testable codes and cayley graphs

Coordination mechanisms from (almost) all scheduling policies

Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications

Why do simple algorithms for triangle enumeration work in the real world?

Building one-time memories from isolated qubits: (extended abstract)

Rate-independent computation in continuous chemical reaction networks

Limits of local algorithms over sparse random graphs

Redrawing the boundaries on purchasing data from privacy-sensitive individuals

Multireference alignment using semidefinite programming

Parameterized testability

The truth behind the myth of the folk theorem

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

Content Provider	ACM Digital Library
Author	Brandão, Fernando G.S.L. Peres, Yuval Lee, James R. Harrow, Aram W.
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.
Starting Page	183
Ending Page	194
Page Count	12
File Format	PDF
ISBN	9781450326988
DOI	10.1145/2554797.2554816
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-01-12
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Composite hypothesis testing Entanglement testing Quantum information theory
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements

Optimal sequence of quantum measurements in the sense of Stein's lemma in quantum hypothesis testing

Convexity Properties of the Quantum R\'enyi Divergences, with Applications to the Quantum Stein's Lemma

Strong Converse and Stein's Lemma in the Quantum Hypothesis Testing

A New Proof of the Direct Part of Stein's Lemma in Quantum Hypothesis Testing

A New Proof of the Direct Part of Stein's Lemma in Quantum Hypothesis Testing

Optimal sequence of POVMs in the sense of Stein's lemma in quantum hypothesis testing

Strong converse and Stein's lemma in quantum hypothesis testing

Optimal sequence of POVMs in the sense of Stein's lemma in quantum hypothesis testing," LANL e-print quant-ph/0107004 (2001)

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

Similar Documents

Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements

Optimal sequence of quantum measurements in the sense of Stein's lemma in quantum hypothesis testing

Convexity Properties of the Quantum R\'enyi Divergences, with Applications to the Quantum Stein's Lemma

Strong Converse and Stein's Lemma in the Quantum Hypothesis Testing

A New Proof of the Direct Part of Stein's Lemma in Quantum Hypothesis Testing

A New Proof of the Direct Part of Stein's Lemma in Quantum Hypothesis Testing

Optimal sequence of POVMs in the sense of Stein's lemma in quantum hypothesis testing

Strong converse and Stein's lemma in quantum hypothesis testing

Optimal sequence of POVMs in the sense of Stein's lemma in quantum hypothesis testing," LANL e-print quant-ph/0107004 (2001)

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