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 onl... View more
 A. S. Holevo, “Statistical problems in quantum physics,” in Proceedings of the Second Japan-USSR Symposium on Probability Theory, ser. Lecture Notes in Mathematics, vol. 330. Springer, 1973, pp. 104-119.
 S. Dziembowski and U. Maurer, “Optimal randomizer efficiency in the bounded-storage model,” Journal of Cryptology, vol. 17, no. 1, pp. 5-26, 2004, conference version appeared in Proc. of STOC '02.
 S. Vadhan, “On constructing locally computable extractors and cryptosystems in the bounded storage model,” in Advances in Cryptology - CRYPTO 2003, 2003, pp. 61-77.
 A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, “Dense quantum coding and a lower bound for 1-way quantum automata,” in Proceedings of the 31th ACM Symposium on Theory of Computing, 1999, quant-ph/9804043.
 A. Nayak, “Optimal lower bounds for quantum automata and random access codes,” in Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999, pp. 369-377, quant-ph/9904093.
 R. Jain, J. Radhakrishnan, and P. Sen, “Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states,” in The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS '02), 2002.
 C. H. Bennett, G. Brassard, and J.-M. Robert, “Privacy amplification by public discussion,” SIAM Journal on Computing, vol. 17, no. 2, pp. 210-229, 1988.
 C. H. Bennett, G. Brassard, C. Cre´peau, and U. Maurer, “Generalized privacy amplification,” IEEE Transaction on Information Theory, vol. 41, no. 6, pp. 1915-1923, 1995.
 N. Nisan and D. Zuckerman, “Randomness is linear in space,” Journal of Computer and System Sciences, vol. 52, pp. 43-52, 1996, a preliminary version appeared at STOC '93.
 M. Christandl, R. Renner, and A. Ekert, “A generic security proof for quantum key distribution,” February 2004, available at http://arxiv.org/abs/quant-ph/0402131.