Theory of Quantum Computation

TheWorkshoponTheoryofQuantumComputation, Communication, andCr- tography (TQC) focuses on theoretical aspects of quantum computation, qu- tum communication, and quantum cryptography, which are part of a larger interdisciplinary ?eld that casts information science in a quantum mechanical framework. The third TQC was held from January 30 to February 1, 2008, at the U- versity of Tokyo, Tokyo, Japan. It consisted of invited talks, contributed talks and a poster session. A selection of these contributors were invited to submit a paper to this Lecture Notes in Computer Science (LNCS) proceedings. The ?eld of quantum information processing is rapidly growing in depth and in breadth. TQC is a workshop dedicated to the presentation and discussion of original research. While most research in quantum information is published in a wide range of journals and conference proceedings in computer science, physics, mathematics and other traditional areas of science, there is a growing nicheforhigh-qualityjournalsandproceedingsdedicatedtoresearchinquantum information. TQC is one of the ?rst such conferences or workshops that has decided to publish a selection of the submissions in an o?cial proceedings of the workshop to be published in the LNCS series. We are extremely fortunate to have had the support and advice of our P- gramCommittee(listedhere)andareverygratefulforalltheirhardwork.Wealso appreciatethehelpofthefollowingadditionalreviewers: Jean-ChristianBoileau, Jop Briet, David Feder, Francois Le Gall, Hector Garcia, Tohya Hiroshima, and CaseyMyers. WealsoextendoursincerethankstothelocalOrganizingCommitteeforpulling togetherallthelocalandlogisticalaspectsoftheworkshopsosuccessfully. Lastly, many thanks to NTT for sponsoring TQC 2008, to the University of Tokyo for their generous support, and to Springer for agreeing to publish these proceedings in the LNCS series.