Computational Notions of Quantum Min-Entropy
arXiv:1704.07309
Abstract
We initiate the study of computational entropy in the quantum setting. We investigate to what extent the classical notions of computational entropy generalize to the quantum setting, and whether quantum analogues of classical theorems hold. Our main results are as follows. (1) The classical Leakage Chain Rule for pseudoentropy can be extended to the case that the leakage information is quantum (while the source remains classical). Specifically, if the source has pseudoentropy at least , then it has pseudoentropy at least conditioned on an -qubit leakage. (2) As an application of the Leakage Chain Rule, we construct the first quantum leakage-resilient stream-cipher in the bounded-quantum-storage model, assuming the existence of a quantum-secure pseudorandom generator. (3) We show that the general form of the classical Dense Model Theorem (interpreted as the equivalence between two definitions of pseudo-relative-min-entropy) does not extend to quantum states. Along the way, we develop quantum analogues of some classical techniques (e.g. the Leakage Simulation Lemma, which is proven by a Non-uniform Min-Max Theorem or Boosting). On the other hand, we also identify some classical techniques (e.g. Gap Amplification) that do not work in the quantum setting. Moreover, we introduce a variety of notions that combine quantum information and quantum complexity, and this raises several directions for future work.
arXiv comment59 pages. This version: 1. the leakage chain rule for min-entropy is removed. 2. the nonuniform quantum min-max is proved by MMWU method rather than epsilon-net. 3. The model of quantum leakage-resilient stream cipher is detailed. 4. Some bugs in the proof of the leakage simulation lemma by boosting are fixed and also a bug in the quantum min-max theorem by KL-projection
References in corpus (15)
- Optimal Quantum Cloning Machines
- The operational meaning of min- and max-entropy
- Fully device independent quantum key distribution
- Measuring measurement
- Quantum speedup of Monte Carlo methods
- Most quantum states are too entangled to be useful as computational resources
- Trevisan's extractor in the presence of quantum side information
- Are random pure states useful for quantum computation?
- The Bounded Storage Model in The Presence of a Quantum Adversary
- Efficient Quantum Pseudorandomness
- Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions
- Impossibility of Growing Quantum Bit Commitments
- Equilibrium Value Method for the Proof of QIP=PSPACE
- A Note on Quantum Security for Post-Quantum Cryptography
- Modulus Computational Entropy