On the Power of Quantum Memory

Abstract

We address the question whether quantum memory is more powerful than classical memory. In particular, we consider a setting where information about a random n-bit string X is stored in r classical or quantum bits, for r<n, i.e., the stored information is bound to be only partial. Later, a randomly chosen binary question F about X is asked, which has to be answered using only the stored information. The maximal probability of correctly guessing the answer F(X) is then compared for the cases where the storage device is classical or quantum mechanical, respectively. We show that, despite the fact that the measurement of quantum bits can depend arbitrarily on the question F to be answered, the quantum advantage is negligible already for small values of the difference n-r. An implication for cryptography is that privacy amplification by application of a compression function mapping n-bit strings to s-bit strings (for some s<n-r), chosen publicly from a two-universal class of hash functions, remains essentially equally secure when the adversary's memory is allowed to be r quantum rather than only r classical bits.

11 pages; references added and notation simplified; to appear in the July 2005 issue of IEEE Transactions on Information Theory

Cited by in corpus (25)

• Quantum Random Number Generators
• Optimality of Gaussian Attacks in Continuous Variable Quantum Cryptography
• Security in Quantum Cryptography
• Quantum state discrimination and its applications
• Private Randomness Expansion With Untrusted Devices
• Quantum Information Processing with Finite Resources -- Mathematical Foundations
• Leftover Hashing Against Quantum Side Information
• The Bounded Storage Model in The Presence of a Quantum Adversary
• (4,1)-Quantum Random Access Coding Does Not Exist
• Possibility, Impossibility and Cheat-Sensitivity of Quantum Bit String Commitment
• Key Generation: Foundations and a New Quantum Approach
• Sampling of min-entropy relative to quantum knowledge
• Quantum Cryptography Based Solely on Bell's Theorem
• The impossibility of non-signaling privacy amplification
• Security of quantum bit string commitment depends on the information measure
• Duality of privacy amplification against quantum adversaries and data compression with quantum side information
• Fundamental Quantitative Security In Quantum Key Distribution
• Quantum to Classical Randomness Extractors
• Noise Tolerance of the BB84 Protocol with Random Privacy Amplification
• Practical security analysis of two-way quantum key distribution protocols based on non-orthogonal states
• The Physics of Quantum Information: Complementarity, Uncertainty, and Entanglement
• Multiple-copy state discrimination of noisy qubits
• Tomographic readout of an opto-mechanical interferometer
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings
• Multi-matrix rate-compatible reconciliation for quantum key distribution