Adversarial hypothesis testing and a quantum Stein’s Lemma for restricted measurements
© 1963-2012 IEEE. Recall the classical hypothesis testing setting with two sets of probability distributions P and Q. One receives either n i.i.d. samples from a distribution p in P or from a distribution q in Q and wants to decide from which set the points were sampled. It is known that the optimal...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/132520 |
| _version_ | 1826190378891476992 |
|---|---|
| author | Brandao, Fernando GSL Harrow, Aram W Lee, James R Peres, Yuval |
| author_facet | Brandao, Fernando GSL Harrow, Aram W Lee, James R Peres, Yuval |
| author_sort | Brandao, Fernando GSL |
| collection | MIT |
| description | © 1963-2012 IEEE. Recall the classical hypothesis testing setting with two sets of probability distributions P and Q. One receives either n i.i.d. samples from a distribution p in P or from a distribution q in 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 in P and q in Q can change in each sample in some way that depends arbitrarily on the previous samples. In other words, in the k{th} round, an adversary, having observed all the previous samples in rounds 1,ldots,k-1 , chooses p_{k} in P and q_{k} in 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 von Neumann entropy. |
| first_indexed | 2024-09-23T08:39:23Z |
| format | Article |
| id | mit-1721.1/132520 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:39:23Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1325202021-09-21T04:04:17Z Adversarial hypothesis testing and a quantum Stein’s Lemma for restricted measurements Brandao, Fernando GSL Harrow, Aram W Lee, James R Peres, Yuval © 1963-2012 IEEE. Recall the classical hypothesis testing setting with two sets of probability distributions P and Q. One receives either n i.i.d. samples from a distribution p in P or from a distribution q in 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 in P and q in Q can change in each sample in some way that depends arbitrarily on the previous samples. In other words, in the k{th} round, an adversary, having observed all the previous samples in rounds 1,ldots,k-1 , chooses p_{k} in P and q_{k} in 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 von Neumann entropy. 2021-09-20T18:22:49Z 2021-09-20T18:22:49Z 2020-10-27T13:45:45Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/132520 en 10.1109/TIT.2020.2979704 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Brandao, Fernando GSL Harrow, Aram W Lee, James R Peres, Yuval Adversarial hypothesis testing and a quantum Stein’s Lemma for restricted measurements |
| title | Adversarial hypothesis testing and a quantum Stein’s Lemma for restricted measurements |
| title_full | Adversarial hypothesis testing and a quantum Stein’s Lemma for restricted measurements |
| title_fullStr | Adversarial hypothesis testing and a quantum Stein’s Lemma for restricted measurements |
| title_full_unstemmed | Adversarial hypothesis testing and a quantum Stein’s Lemma for restricted measurements |
| title_short | Adversarial hypothesis testing and a quantum Stein’s Lemma for restricted measurements |
| title_sort | adversarial hypothesis testing and a quantum stein s lemma for restricted measurements |
| url | https://hdl.handle.net/1721.1/132520 |
| work_keys_str_mv | AT brandaofernandogsl adversarialhypothesistestingandaquantumsteinslemmaforrestrictedmeasurements AT harrowaramw adversarialhypothesistestingandaquantumsteinslemmaforrestrictedmeasurements AT leejamesr adversarialhypothesistestingandaquantumsteinslemmaforrestrictedmeasurements AT peresyuval adversarialhypothesistestingandaquantumsteinslemmaforrestrictedmeasurements |