Bibliography

The papers are arranged according to the lecture in which they were referred to.

• May 4,6:
  
  1. For 2 into 1 oblivious transfer or random access encoding:
     A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani. Dense quantum coding and quantum finite automata. Journal of the ACM, 49(4):1--16, July 2002.
  2. For quantum fingerprinting:
     H. Buhrman, R. Cleve, J. Watrous and R. de Wolf. Quantum Fingerprinting. Physical Review Letters, 87(16): article 167902, 2001.

• May 11:
  
  1. For the Nayak bound:
     A. Nayak. Optimal lower bounds for quantum automata and random access codes. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 369--376, 1999.
  2. For Yao's lemma:
     A.C.-C. Yao. Quantum circuit complexity. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pp. 352--361, 1993.
  3. For the set disjointness protocol:
     H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and computation. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 63--68, 1998.

• May 13,18,20:
  
  1. For Raz's protocol:
     R. Raz. Exponential separation of quantum and classical communication complexity. In Proceedings of the thirty-first Annual ACM Symposium on Theory of Computing, pages 358--367, 1999.
  2. For sampling disjoint subsets:
     A. Ambainis, L. Schulman, A. Ta-Shma, U. Vazirani, and A. Wigderson. The Quantum Communication Complexity of Sampling. SIAM Journal on Computing, 32:1570-1585, 2003. Earlier version in FOCS'98.
  3. For the set disjointness lower bound:
     Alexander Razborov. Quantum Communication Complexity of Symmetric Predicates. Izvestiya: Mathematics, Vol. 67, No. 1, pages 145--159, 2003. Russian version in Izvestiya Rossiiskoi Academii Nauk (seriya matematicheskaya), Vol. 67, No 1, 2003, pages 159-176.

• May 21,25;   June 1,3:
  
  1. For information theory basics:
     M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000.
  2. For the strong coin flipping schema:
     D. Aharonov, A. Ta-Shma, U. Vazirani, and A. Yao. Quantum bit escrow. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 705--714, 2000.
  3. For the best known strong coin flipping protocol:
     Andris Ambainis. A new protocol and lower bounds for quantum coin flipping. Journal of Computer and System Sciences, Volume 68, Issue 2, pages 398-416, March 2004.
     Also see:
     R.W. Spekkens and T. Rudolph. Degrees of concealment and bindingness in quantum bit commitment protocols. Physical Review A, 65, article no. 012310, 2002.
     For the analysis presented in class, see:
     Iordanis Kerenidis and Ashwin Nayak. Weak Coin Flipping with Small Bias. Information Processing Letters, 89(3), pp. 131--135, 2004.

• June 3,8:
  
  1. For CSS codes:
     A.R. Calderbank and P. W. Shor. Good quantum error-correcting codes exist. Physical Review A, 54, pp. 1098--1106, 1996.
     Also see:
     Andrew Steane. Multiple particle interference and quantum error correction. Proceedings of the Royal Society of London A 452, p. 2551, 1996.

• June 10,11,15,17:
  
  1. For the Shor-Preskill proof of security for the BB84 QKD protocol:
     Peter W. Shor and John Preskill. Simple Proof of Security of the BB84 Quantum Key Distribution Protocol. Physical Review Letters 85, pages 441--444, 2000.

• June 22, 29; July 6, 8, 9, 13:
  
  1. For the Szegedy quantization of classical walks:
     (An updated version to be posted shortly.)
     Mario Szegedy. Spectra of Quantized Walks and a $\sqrt{\delta\epsilon}$ rule. LANL Quantum Physics preprint quant-ph/0403120, January 2004.
  2. For previous work on quantum walks and algorithms based on them:
     Andris Ambainis. Quantum walks and their algorithmic applications. LANL Quantum Physics preprint quant-ph/0403120, May 2004.

• July 13, 29:
  
  1. For the polynomial method:
     R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum Lower Bounds by Polynomials. Journal of the ACM, 48(4):778-797, 2001.
  2. For degree lower bounds for symmetric functions:
     Ramamohan Paturi. On the degree of polynomials that approximate symmetric Boolean functions. In Proceedings of the twenty-fourth annual ACM Symposium on Theory of Computing, pp. 468--474, 1992.

• August 3:
  
  1. For the Ambainis method for query lower bounds:
     A. Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750-767, 2002.
  2. For a survey on query lower bounds:
     A. Ambainis. Quantum query algorithms and lower bounds. In Proceedings of FOTFS III, to appear.