Publications Note: publication databases are available at these sites: The Institute for Quantum Computing, University of Waterloo Institute for Quantum Information Science, University of Calgary A) Refereed Contributions 1. Articles in refereed publications - published or accepted 2006 M. Adcock, R. Cleve, K. Iwama, R. Putra and S. Yamashita. Quantum lower bounds for the Goldreich-Levin problem. Information Processing Letters 97(5):208-211, 2006. A. Ambainis, D. Gottesman. Two-way entanglement purification for finite block size. IEEE Transactions on Information Theory, 52:748-753, 2006. S. Bandyopadhyay and B. C. Sanders. Quantum teleportation of composite systems via mixed entangled states. Physical Review A 74:032310, 2006. D. W. Berry, G. Ahokas, R. Cleve and B. C. Sanders. Efficient quantum algorithms for simulating sparse Hamiltonians. Communications in Mathematical Physics, 24 July 2006. (accepted or in press). D. W. Berry, A. I. Lvovsky and B. C. Sanders. Efficiency limits for linear optical processing of single photons and single-rail qubits. Journal of the Optical Society of America B, 15 July 2006. (accepted or in press). G. Gour, S. Bandyopadhyay and B. C. Sanders. Dual monogamy inequality for entanglement. Journal of Mathematical Physics, 28 September 2006. (accepted or in press). K. Horodecki, D. Leung, H.-K. Lo, J. Oppenheim. Quantum key distribution based on arbitrarily-weak distillable entangled states. Physical Review Letters 96, 070501, 2006. A. Nayak and J. Salzman. Limits on the ability of quantum states to convey classical messages. Journal of the ACM, 53(1):184-206, 2006. B. C. Sanders, G. Gour, and D. A. Meyer. Deterministic entanglement of assistance in quantum networks. Canadian Journal of Physics 84(S2):1-6, 2006. A. J. Scott. Tight informationally complete quantum measurements. Journal of Physics A: Mathematical and General 39(43):13507-13530, 2006. A. J. Scott,T. A. Brun, C. M. Caves and R. Schack, Hypersensitivity and chaos signatures in the quantum baker's maps. Journal of Physics A: Mathematical and General 39(43):13405-13433, 2006. A. J. Scott, J. Walgate and B. C. Sanders. Optimal fingerprinting strategies with one-sided error, Quantum Information and Computation, 5 July 2006. (accepted or in press). G. Smith and D. Leung. Typical entanglement of stabilizer states. Physical Review A 74, 062314, 2006. 2005 A. Abeyesinghe, P. Hayden, G. Smith, and A. Winter. Optimal superdense coding of entangled states. arXiv:quant-ph/0407061. Accepted to IEEE Trans. Inf. Th., 2005. Mark Adcock, Richard Cleve, Kazuo Iwama, Raymond Putra, Shigeru Yamashita. Quantum lower bounds for the Goldreich-Levin problem. Information processing Letters, Accepted 2005. C. Ahn, A. Doherty, P. Hayden, and A. Winter. On the distributed compression of quantum information. arXiv:quant-ph/0403042. Accepted to IEEE Trans. Inf. Th., 2005. Jonathan Baugh, Osama Moussa, Colm Ryan, Ashwin Nayak, and Raymond Laflamme. A spin-based heat engine: Experimental implementation of heat-bath algorithmic cooling. Nature. Provisionally accepted, 2005. S. D. Bartlett, P. Hayden, and R. W. Spekkens. Random subspaces for encryption based on a private shared Cartesian frame. arXiv:quant-ph/0506260. Accepted to Phys. Rev. A, 2005. C. H. Bennett, P. Hayden, D. W. Leung, P. W. Shor, and A. Winter. Remote prepa- ration of quantum states. IEEE Trans. Inf. Th., 51(1):56-74, 2005. arXiv:quant- ph/0307100. D. W. Berry, A. I. Lvovsky, and B. C. Sanders. Interconvertibility of single-rail optical qubits. Optics Letters (accepted), 2005. J.-C. Boileau, R. Laflamme M. Laforest, and C. R. Myers. Robust quantum communi- cation using a polarization-entangled photon pair. Physical Review Letters, 93:220501, 2005. J.-C. Boileau, K. Tamaki, J. Batuwantudawe, and R. Laflamme. Higher security thresh- olds for quantum key distribution by improved analysis of dark counts. 2005. quant- ph/0502140. J.-C. Boileau, K. Tamaki, J. Batuwantudawe, and R. Laflamme. Unconditional security of three state quantum key distribution protocols. Physical Review Letters, 94:040503, 2005. N. Boulant C. Ramanathan S. Lloyd D. G. Cory P. Cappellaro, J. Emerson. Entanglement assisted metrology. Phys. Rev. Lett., 94:020502, 2005. M. D. Bowdrey, J. A. Jones, E. Knill, and R. Laflamme. Compiling gate networks on an ising quantum computer. Physical Review A, page 032315, 2005. quant-ph/0506006. G. Brassard, A. Broadbent, and A. Tapp. Quantum pseudo-telepathy. Foundations of Physics, 35(11), November 2005. G. Brassard, A. Broadbent, and A. Tapp. Recasting mermin's multi-player game into the framework of pseudo-telepathy. Quantum Information and Computation (QIC), 35(7), November 2005. G. Brassard, A. A. Methot, and A. Tapp. Minimum entangled state dimension required for pseudo-telepathy. Foundations of Physics, 5(4), 2005. Anne Broadbent and Andre Allan Methot. On the power of non-local boxes. Theoretical Computer Science, To appear. A. Childs, D.W. Leung, and M. Nielsen. Unified derivations of measurement-based schemes for quantum computation. Phys. Rev. A, 71:032318, 2005. arXive e-print quant-ph/0404132. S. Daftuar and P. Hayden. Quantum state transformations and the Schubert calculus. Ann. Phys., 315(1):80-122, 2005. arXiv:quant-ph/0410052. S. Ghose, P. M. Alsing, B. C. Sanders, and I. H. Deutsch. Entanglement and the quantum-to-classical transition. Physical Review A, 72(1):014102, July 2005. G. Gour, D. A. Meyer, and B. C. Sanders. Deterministic entanglement of assistance and monogamy constraints. Physical Review A (in press), 2005. A. Harrow and D. Leung. Bidirectional coherent classical communication. Quant. Inf. Comp., 5:380-395, 2005. arXive e-print quant-ph/0412126. P. Hayden. Putting certainty in the bank. Nature, 436:633-634, 2005. P. Hayden, D. Leung, and G. Smith. Multiparty data hiding of quantum information. Phys. Rev. A, 71:062339, 2005. arXive e-print quant-ph/0407152. P. Hayden, D. W. Leung, and G. Smith. Multiparty data hiding of quantum informa- tion. Phys. Rev. A, 71:062339.1-062339.9, 2005. arXiv:quant-ph/0407152. R.T. Horn, A. J. Scott, J.Walgate, R. Cleve, A. I. Lvovsky, and B. C. Sanders. Classical and quantum fingerprinting with shared randomness and one-sided error. Quantum Information and Computation, 5(3):258-271, May 2005. V. Kendon and B. C. Sanders. Complementarity and quantum walks. Physical Review A, 71(2):022307/1-022307/7, February 2005. D. Kribs, R. Laflamme, and D. Poulin. A unifed and generalized approach to quantum error correction. Physical Review Letters, 94:180501, 2005. H.-K. Lo and T.-M. Ko. Some attacks on quantum-based cryptographic protocols. Quantum Information and Computation, 5:40, 2005. Hoi-Kwong Lo, H. F. Chau, and M. Ardehali. E±cient quantum key distribution scheme and proof of its unconditional security. Journal of Cryptology, 18:133, 2005. Hoi-Kwong Lo, Xiongfeng Ma, and Kai Chen. Decoy state quantum key distribution. Physical Review Letters, 94:230504, 2005. Hoi-Kwong Lo. Getting something out of nothing. Quantum Information and Computation, 4:413, 2005. Xiongfeng Ma, Bing Qi, Yi Zhao, and Hoi-Kwong Lo. Practical decoy state for quantum key distribution. Physical Review A, 72:012326, 2005. C. Marriott and J. Watrous. Quantum arthur-merlin games. Computational Complexity, 14(2):122-152, 2005. Ashwin Nayak and Julia Salzman. Limits on the ability of quantum states to convey classical messages. Journal of the ACM. Accepted, 2005. C.A. Ryan, J. Emerson, D. Poulin, C. Negrevergne, and R. Laflamme. Characterization of complex quantum dynamics with a scalable nmr information processor. Physical Review Letters, to appear, 2005. 22 J. Watrous. Bipartite subspaces having no bases distinguishable by local operations and classical communication. Physical Review Letters, 95(8): article 080505, 2005. J. Watrous. Notes on super-operator norms induced by Schatten norms. Quantum Information and Computation, 5(1):58-68, 2005. 2004 P. Aliferis and D.W. Leung. Computation by measurements: A unifying picture. Phys. Rev. A, 70:062314, 2004. arXive e-print quant-ph/0404082. Andris Ambainis. A new protocol and lower bounds for quantum coin flipping. J. Comput. Syst. Sci., 68(2):398-416, 2004. E. Bach, S. Coppersmith, M. Goldschen, R. Joynt, and J. Watrous. One-dimensional quantum walks with absorbing boundaries. Journal of Computer and System Sciences, 69(4):562-592, 2004. D. W. Berry, S. Scheel, C. R. Myers, B. C. Sanders, P. L Knight, and R. Laflamme. Improving single photon sources via linear optics and photodetection. In Proceedings of the Conference on Fluctuations and Noise in Photonics and Quantum Optics II, volume 5468 of AIP Proceedings, pages 25-28, Gran Canaria, Spain, May 2004. SPIE's First International Symposium on Optical Science and Technology. D. W. Berry, S. Scheel, C. R. Myers, B. C. Sanders, P. L. Knight, and R. Laflamme. Post-processing with linear optics for improving the quality of single-photon sources. New Journal of Physics, 6(4), 2004. 13 D. W. Berry, S. Scheel, B. C. Sanders, and P. L. Knight. Improving single-photon sources via linear optics and photodetection. Physical Review A, 69(3), March 2004. J.-C. Boileau, D. Gottesman, R. Laflamme, D. Poulin, and R.W. Spekkens. Robust polarization-based quantum key distribution over collective-noise channel. Physical Review Letters, 92:17901, 2004. J. Niel de Beaudrap. One-qubit Fingerprinting schemes. Physical Review A, 69:article 022307, 2004. S. Ghose and B. C. Sanders. Entanglement dynamics in chaotic systems. Physical Review Letters, 70(6):062315, December 2004. A. Harrow and H.-K. Lo. A tight lower bound on the classical communication cost of entanglement dilution. IEEE Transactions on Information Theory, 50:319, 2004. A. Harrow, P. Hayden, and D. W. Leung. Superdense coding of quantum states. Phys. Rev. Lett., 92:187901.1-187901.4, 2004. arXiv:quant-ph/0307221. Daniel Gottesman, Hoi-Kwong Lo, Norbert Lutkenhaus, and John Preskill. Security of quantum key distribution with imperfect devices. Quantum Information and Com- putation, 4:325, 2004. G. Gour and B. C. Sanders. Remote preparation and distribution of bipartite entangled states. Physical Review Letters, 93(26):260501, December 2004. 17 P. Hayden, R. Jozsa, D. Petz, and A. Winter. Structure of states which satisfy strong subadditivity of quantum entropy with equality. Commun. Math. Phys., 246(2):359- 374, 2004. arXiv:quant-ph/0304007. P. Hayden and C. King. Correcting quantum channels by measuring the environment. Quantum information and computation, 5(2):156-160, 2005. arXiv:quant-ph/0409026. P. Hayden, D. W. Leung, P. W. Shor, and A. Winter. Randomizing quantum states: Constructions and applications. Commun. Math. Phys., 250(2):371-391, 2004. arXiv:quant-ph/0307104. R.T. Horn, S. A. Babichev, K.-P. Marzlin, A. I. Lvovsky, and B. C. Sanders. Single qubit optical quantum fingerprinting. Physical Review Letters, 95(15):150502, October 2004. Iordanis Kerenidis and Ashwin Nayak. Weak coin flipping with small bias. Information Processing Letters, 89(3):131-135, February 2004. D. W. Leung. Quantum computation by measurements. Int. J. Q. Info., 2:33-43, 2004. arXive e-print quant-ph/0310189. D. Poulin D. Cory J. Emerson, S. Lloyd. Estimation of the local density of states on a quantum computer, Phys. Rev. A 69, 050305(R) (2004). X.Wang, S. Ghose, B. C. Sanders, and B. Hu. Entanglement as a signature of quantum chaos. Physical Review E, 70(1):16217-1-8, July 2004. J. Watrous. Many copies may be required for entanglement distillation. Physical Review Letters, 93(1): article 010502, 2004. 2003 L. Qian B. Qi, A. Tausz and H.-K. Lo. High-resolution, large dynamic range ¯ber length measurement based on frequency-shifted asymmetrical sagnac interferometer. Accepted by Optics Letters, 2005. Harry Buhrman, Christoph Durr, Mark Heiligman, Peter Hoyer, Friederic Magniez, Miklos Santha, and Ronald de Wolf. Quantum algorithms for element distinctness. SIAM Journal on Computing, 34(6):1324-1330, 2005. Harry Buhrman, Peter Hoyer, Serge Massar, and Hein Roehrig. Combinatorics and quantum nonlocality. Physical Review Letters, 91:047903, 2003. Daniel Gottesman and Hoi-Kwong Lo. Proof of security of quantum key distribution with two-way classical communications. IEEE Transactions on Information Theory, 49:457, 2003. P. Hayden and A. Winter. On the communication cost of entanglement transformations. Phys. Rev. A, 67:012326.1-012326.8, 2003. arXiv:quant-ph/0204092. J.A. Holbrook, D.W. Kribs, and R. Laflamme. Noiseless subsystems and the structure of the commutant in quantum error correction. Quantum Information Processing, 2:381-419, 2003. H.-K. Lo. Method for decoupling error correction from privacy ampli¯cation. New Journal of Physics, 5:36, 2003. A. Abeyesinghe and P. Hayden. Generalized remote state preparation: Trading cbits, qubits and ebits in quantum communication. Phys. Rev. A, 68:062319.1-062319.9, 2003. arXiv:quant-ph/0308143. T. Brun, H. Klauck, A. Nayak, M. Roetteler, and C. Zalka. Comment on \probabilistic quantum memories". Physical Review Letters, 91(20):article 209801, 2003. Todd A Brun, Hilary A Carteret, and Andris Ambainis. The quantum to classical transition for random walks. Physical Review Letters, 91:130602, 2003. Todd A Brun, Hilary A Carteret, and Andris Ambainis. Quantum walks driven by many coins. Physical Review A, 67:052317, 2003. W. van Dam and P. Hayden. Embezzling entangled quantum states (in press as Universal entanglement transformations without communication). Phys. Rev. A, 67(6):060302.1-060302.3, 2003. arXiv:quant-ph/0201041. - submitted P. Aliferis and D.W. Leung. Fault-tolerant quantum computation with graph states, 2005. arXive e-print quant-ph/0503130. A Tausz B. Qi, L. Qian and H.-K. Lo. Frequency-shifted mach-zehnder interferometer for locating multiple weak reflections along a ¯ber link. Submitted to IEEE Photonics Technology Letters, 2005. H. Buhrman, M. Christandl, P. Hayden, H.-K. Lo, and S. Wehner. On the (im)possibility of quantum string commitment. arXiv:quant-ph/0504078, 2005. 14 Claude Crepeau, Jean-Raymond Simard, and Alain Tapp. Classical and quantum strategies for two-prover bit commitments. In submitted to STOC06. P. Hayden, D. W. Leung, and A. Winter. Aspects of generic entanglement. arXiv:quant-ph/0407049. Submitted to Commun. Math. Phys., 2005. M. Saraceno S. Lloyd D. Cory J. Emerson, Y. Weinstein. Pseudo-random unitary operators for quantum information processing. 302:2098, 2003. Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, and David Zuckerman. Interaction in quantum communication. IEEE Transactions on Information Theory. Submitted. Hoi-Kwong Lo. Classical-communication cost in distributed quantum-information pro- cessing: a generalization of quantum-communication complexity. Physical Review A, 62:012313, 2000. Hoi-Kwong Lo. Cryptography's quantum barrier. Physics World, 2001. Frederic Magniez and Ashwin Nayak. Quantum complexity of testing group commutativity. Algorithmica. Submitted 2. Other refereed contributions - papers in refereed conference proceedings 2006 A. Ambainis, R. Spalek. Quantum algorithms for matching and network flows. Proceedings of STACS'06, Lecture Notes in Computer Science, 3884, pp. 172-183, 2006. A. Ambainis, K. Iwama, A. Kawachi, R. Raymond, S. Yamashita. Robust quantum algorithms for oracle identification. Proceedings of SWAT'06, Lecture Notes in Computer Science, vol. 4059, pp. 280-291, 2006. H. Buhrman, R. Cleve, M. Laurent, N. Linden, A. Schrijver, F. Unger. New limits on fault-tolerant quantum computation. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 411-419, 2006. J. Watrous. Zero-knowledge against quantum attacks. Proceedings of the 38th ACM Symposium on Theory of Computing (STOC 2006), pp. 296-305, 2006. 2005 Andris Ambainis, Julia Kempe, and Alexander Rivosh. Coins make quantum walks faster. In SODA, pages 1099-1108, 2005. M. Ben-Or, M. Horodecki, D. Leung, D. Mayers, and J. Oppenheim. The universal composable security of quantum key distribution. In Theory of Cryptography Conference, LNCS 3378, Ed. J. Kilian, volume 3378, pages 386-406, 2005. arXive e-print quant-ph/0409078. K. Chen and H.-K. Lo. Conference key agreement and quantum sharing of classical secrets with noisy ghz states. IEEE ISIT (International Symposium on Information Theory) 2005, 2005. B. Fortescue and H.-K. Lo. Inefficiency and classical communication bounds for con- version between partially entangled pure bipartite states. Physical Review A, 72, 2005. S. Ghose and B. C. Sanders. Analysis of non-gaussian states of light as a resource for quantum information processing with continuous variables. In Proceedings of the Conference on Quantum Communications and Quantum Imaging III, volume 5893, San Diego, August 2005. SPIE Annual Meeting. G. Gutoski. Upper bounds for quantum interactive proofs with competing provers. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pages 334-343, 2005. G. Gutoski and J. Watrous. Quantum interactive proofs with competing provers. In Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science, volume 3404 of Lecture Notes in Computer Science, pages 605-616. Springer- Verlag, 2005. Peter Hoyer. The phase matrix. In Proceedings of the 16th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, page To appear, 2005. Peter Hoyer and Robert Spalek. Lower bounds on quantum query complexities. Bulletin of the European Association for Theoretical Computer Science, 87:78-103, October 2005. R. Jain, J. Radhakrishnan, and P. Sen. Prior entanglement, message compression and privacy in quantum communication. In IEEE Conference on Computational Complexity, pages 285-296, 2005. Friederic Magniez and Ashwin Nayak. Quantum complexity of testing group commutativity. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, pages 1312-1324. Springer- Verlag, July 11-15 2005. Lisboa, Portugal. J. Radhakrishnan, M. Roetteler, and P. Sen. On the power of random bases in fourier sampling: Hidden subgroup problem in the heisenberg group. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), volume 3580 of Lecture Notes in Computer Science, pages 1399-1411. Springer-Verlag, 2005. B. Rosgen and J. Watrous. On the hardness of distinguishing mixed-state quantum computations. In Proceedings of the 20th Annual Conference on Computational Com- plexity, pages 344-354, 2005. B. C. Sanders. Classical vs quantum Fingerprinting. In IEEE Computer Society, editor,The Thirty-Fifth International Symposium on Multiple-Valued Logic (ISMVL 2005),pages 1-4, Tokyo, May 2005. University of Calgary. B. C. Sanders and S. Bandyopadhyay. Concatenated quantum teleportation? In Proceedings of the Conference on Quantum Communications and Quantum Imaging III, volume 5893, San Diego, August 2005. SPIE Annual Meeting. K. Tamaki and H.-K. Lo. Unconditionally secure key distillation from multi-photons in a single-photon polarization-based quantum key distribution. IEEE ISIT (Interna- tional Symposium on Information Theory) 2005, 2005. J. Yard, I. Devetak, and P. Hayden. Capacity theorems for quantum multiple ac- cess channels. In Proceedings of the 2005 IEEE Symposium on Information Theory, Adelaide, Australia, pages 884-888, September 2005. J. Yard, I. Devetak, and P. Hayden. Sending classical and quantum information over quantum multiple access channels. In Proceedings of the Ninth Canadian Workshop on Information Theory, Montreal, Canada, pages 387-390, June 2005. 2004 Andris Ambainis. Quantum walk algorithm for element distinctness. In FOCS, pages 22-31, 2004. Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, and Shigeru Yamashita. Quantum identification of boolean oracles. In STACS, pages 105-116, 2004. Andris Ambainis and Adam Smith. Small pseudo-random families of matrices: Deran- domizing approximate quantum encryption. In APPROX-RANDOM, 2004. D. Mayers, C. Crepeau, P. Dumais and L. Salvail. Computational collapse of quan- tum state with application to oblivious transfer. In proceedings of the 1st Theoretical Cryptography Conference, volume 2951 of Lecture Notes in Computer Science, pages 374-393. Springer-Verlag, 2004. R. Cleve, P. Hoyer, B. Toner, and J. Watrous. Consequences and limits of nonlocal strategies. In Proceedings of the 19th Annual IEEE Conference on Computational Complexity, pages 236-249, 2004. N. Lutkenhaus D. Gottesman, H.-K. Lo and J. Preskill. Security of quantum key distri- bution with imperfect devices. IEEE ISIT (International Symposium on Information Theory) 2004, 2004. Mark Ettinger, Peter Hoyer, and Emanuel Knill. The quantum query complexity of the hidden subgroup problem is polynomial. Information Processing Letters, 91(1):43-48, 16 July 2004. S. Ghose, P. M. Alsing, I. H. Deutch, and B. C. Sanders. The quantum to classical transition in entangled systems via continuous measurements. In The Seventh In- ternational Conference on Quantum Communication, Measurement and Computing, volume 734 of AIP Proceedings, pages 61-66, Glasgow, United Kingdom, July 2004. SPIE Annual Meeting. P. Hayden. Entanglement in random subspaces. In Proceedings of the Seventh International Conference on Quantum Communication, Measurement and Computing, pages 226-229. American Institute of Physics, 2004. arXiv:quant-ph/0409157. V. Kendon and B. C. Sanders. Complementarity in quantum walks. In The Seventh International Conference on Quantum Communication, Measurement and Computing, volume 734 of AIP Proceedings, pages 133-138, Glasgow, United Kingdom, July 2004. SPIE Annual Meeting. Hoi-Kwong Lo. Quantum key distribution with vacua and dim pulses as decoy states. IEEE ISIT (International Symposium on Information Theory) 2004, 2004. B. C. Sanders, R. Horn, and K.-P. Marzlin. Single-qubit optical quantum ¯ngerprint- ing. In Proceedings of the Conference on Quantum Communications and Quantum Imaging II, volume 5551 of AIP Proceedings, pages 137-143, Denver, August 2004. SPIE Annual Meeting. 2003 Scott Aaronson and Andris Ambainis. Quantum search of spatial regions. In FOCS, pages 200-209, 2003. Andris Ambainis. Polynomial degree vs. quantum query complexity. In FOCS, pages 230-239, 2003. Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, and Avi Wigderson. The quantum communication complexity of sampling. SIAM J. Comput., 32(6):1570-1585, 2003. D. P. DiVincenzo, P. Hayden, and B. M. Terhal. Hiding quantum data. Found. Phys., 33(11):1629-1647, 2003. arXiv:quant-ph/0207147. Invited contribution to `David Mer- min Festschrift'. D. P. DiVincenzo, M. Horodecki, D. Leung, J. Smolin, and B. M. Terhal. Locking classical correlation in quantum states. Phys. Rev. Lett., 92:067902, 2004. arXive e-print quant-ph/0303088. V. Galliard, A. Tapp, and S. Wolf. The impossibility of pseudo-telepathy without quantum entanglement. In Proceedings of the 2003 IEEE International Symposium on Information Theory (ISITE3), 2003. H. Gerhardt and J.Watrous. Continuous-time quantum walks on the symmetric group. In Proceedings of the 7th International Workshop on Randomization and Approxima- tion Techniques in Computer Science, volume 2764 of Lecture Notes in Computer Science, pages 290-301. Springer-Verlag, 2003. A. W. Harrow and H. K. Lo. A tight lower bound on the classical communication cost of entanglement dilution. IEEE ISIT (International Symposium on Information Theory) 2003. Hoi-Kwong Lo. Error correction and security in quantum cryptography. IEEE ISIT (International Symposium on Information Theory) 2003, 2003. - monographs, books, and book chapters P. Hayden. Capacities enhanced by entanglement. To appear in the Encyclopedia of Mathematical Physics, Elsevier, 2005. B) Non-refereed contributions 1. Papers in non-refereed conference proceedings 2. Theses 2006 Hugue Blier. Preuves interactives classiques. Master's thesis, Universite de Montréal, Québec, 2006. Christoph Dankert. Efficient simulation of random quantum states and operators. Master's thesis, University of Waterloo, 2006. Paul Dickinson. Approximate Private Quantum Channels. Master's thesis, University of Waterloo, 2006. Dmitry Gavinsky. Shared Randomness and Entanglement in Communication Complexity. PhD thesis, University of Calgary, 2006. 2005 Jamie Batuwantudawe. New techniques for security proofs of quantum cryptography, Master's thesis, University of Waterloo, Waterloo, Ontario, 2005. Gus Gutoski. Short Quantum Games, Master's thesis, University of Calgary, 2005. Yuki Kelly Itakura. Quantum algorithm for commutativity testing of a matrix set. Master's thesis, University of Waterloo, Waterloo, Ontario, Canada, September 2005. 2004 Mark Adcock. The Classical and Quantum Complexity of the Goldreich-Levin Problem with Applications to Bit Commitment. Master's thesis, University of Calgary, Calgary, Alberta, Canada, 2004. J. Niel de Beaudrap. Applying quantum information to fingerprinting schemes and algebraic structures. Master's thesis, University of Calgary, Calgary, Alberta, Canada, 2004. Richard Cannings. Security in Quantum Cryptography. Master's thesis, University of Calgary, Calgary, Alberta, Canada, 2004. José M Fernandez. De Computatione Quantica. PhD thesis, Université de Montréal, 2004. Heath Gerhardt. Continuous-time quantum walks on the symmetric group. Master's thesis, University of Calgary, Calgary, Alberta, Canada, 2004. David Poulin. Emergence of a classical world from within quantum theory, PhD thesis, University of Waterloo,  2004 (recipient of the Univeristy of Waterloo Alumni Gold Medal). 3. Technical and internal reports 2006 F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via Quantum Walk. Technical Report arXiv:quant-ph/0608026, 2006. R. Jain and A. Nayak. Accessible versus Holevo Information for a Binary Random Variable. Technical Report ArXiv:quant-ph/0603278, 2006. D. Leung, J. Oppenheim, A. Winter, Quantum network communication -- the butterfly and beyond. Technical Report arXiv:quant-ph/0608223, 2006. R. Cleve, W. Slofstra, F. Unger, S. Upadhyay. Strong parallel repetition theorem for quantum XOR proof systems. Technical Report arXiv:quant-ph/0608146, 2006. C. Dankert, R. Cleve, J. Emerson, E. Livine. Exact and approximate unitary 2-designs: constructions and applications. Technical Report arXiv:quant-ph/0606161, 2006. 2005 D. W. Leung, A. Childs, and H.-K. Lo. Two-way quantum communication channels. arXiv:quant-ph/0506039, 2005. C. Negreverne, D. Poulin, R. Laflamme, C. Ryan, J. Emerson. Characterisation of complex dynamics on a scalable quantum processor. A. Childs, D. Leung, and H.-K. Lo. Two-way quantum communication channels, 2005. arXive e-print quant-ph/0506039. P. Hayden H.-K. Lo S. Wehner H. Buhrman, M. Christandl. On the (im)possibility of quantum string commitment,. http://arxiv.org/abs/quant-ph/0504078, 2005. Peter Hoyer and Robert Spalek. Quantum fan-out is powerful. 1:81-103, 2005. Peter Hoyer and Robert Spalek. Tight adversary bounds for composite functions, September 2005. D. Kribs, R. Laflamme, D. Poulin, and M. Lesosky. Operator quantum error correction. 2005. quant-ph/0504189. S. Lloyd J. Emerson, E. Livine. Convergence conditions for random quantum circuits. H.-K. Lo and J. Preskill. Phase randomization improves the security of quantum key distribution,. http://arxiv.org/abs/quant-ph/0504209, 2005. K. Zyczkowski J. Emerson, R. Alicki. Scalable noise estimation with random unitary operators, 2005. A. J. Scott, J. Walgate, and B. C. Sanders. Optimal fingerprinting strategies with one-sided error. quant-ph/0507048, 2005. J. Yard, I. Devetak, and P. Hayden. Capacity theorems for quantum multiple access channels - part I: Classical-quantum and quantum-quantum capacity regions. arXiv:quant-ph/0501045, 2005 2004 K. Chen and H.-K. Lo. Multi-partite quantum cryptographic protocols with noisy ghz states,. http://www.lanl.gov/abs/quant-ph/0404133, 2004. J.A. Holbrook, D.W. Kribs, R. Laflamme, and D. Poulin. Noiseless subsystems for collective rotation channels in quantum information theory. 2004. X. Ma H.-K. Lo Y. Zhao, B. Qi and L. Qian. Experimental quantum key distribution with decoy states. http://arxiv.org/abs/quant-ph/0503192, 2005. K. Tamaki and H.-K. Lo. Quantum key distribution: Beyond no-cloning theorem. http://arxiv.org/abs/quant-ph/0412035, 2004. 2003 J. Emerson A. Farid E. Fortunato T. F. Havel D. Cory M. A. Pravia, N. Boulant. Robust control of quantum information, 2003. P. Hayden, B. M. Terhal, and A. Uhlmann. On the LOCC classification of bipartite density matrices. arXiv:quant-ph/0011095, 2000. W. van Dam and P. Hayden. Renyi-entropic bounds on quantum communication. arXiv:quant-ph/0204093. J. Emerson T. F. Havel D. Cory N. Boulant, S. Furuta. Incoherent noise and quantum control.