TheWorkshoponTheoryofQuantumComputation,Communication,andCr- tography (TQC) is an annual workshop on theoretical aspects of quantum - formation processing. The goal of the workshop is to foster developments in this rapidly growing,interdisciplinary ?eld by providinga forum for the presentation and discussion of original research. The fourth iteration of TQC was held during May 1113, 2009, at the - stitute for Quantum Computing at the University of Waterloo in Waterloo, Ontario, Canada. The workshop included invited talks, contributed talks, and a poster session, as well as a rump session consisting of short talks on recent developments. Authors of selected contributed talks were invited to submit a paper to these proceedings. TQC 2009 would not have been possible without the contributions of - merous individuals and organizations, and we sincerely thank them for their support. In putting together the scienti c program,we were very grateful for the hard work and advice of the Program Committee, listed herein. We also appreciate the help of the following additional reviewers: Roger Colbeck, Markus Grassl, Stefan Hengl, Tohya Hiroshima, Min-Hsiu Hsieh, Akinori Kawachi, Harumichi Nishimura, Rudy Raymond, Douglas Stebila, and Tzu-Chieh Wei. The logistics of the workshop were expertly managed by the Local Organ- ing Committee, also listed herein, and we thank them for their e orts to make the workshop a success. We are also thankful for the assistance of Kim Kuntz, WendyReibel,AlisonConwayandSharonMcCalla,whoprovidedadministrative support, and Colin Bell, who helped with computing and audiovisual resources.
