Abstract
Measurement-based quantum computation has emerged from the physics community as a new approach to quantum computation where measurements rather than unitary transformations are the main driving force of computation. Among measurement-based quantum computation methods the recently introduced one-way quantum computer [RB01] stands out as basic and fundamental.
In this work we a concrete syntax and an algebra of these patterns derived from a formal semantics. We developed a rewrite theory and proved a general standardization theorem which allows all patterns to be put in a semantically equivalent standard form.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bennett, C., Brassard, G., Crepeau, C., Jozsa, R., Peres, A., Wootters, W.: Teleporting an unknown quantum state via dual classical and EPR channels. Phys Rev Lett 10(5), 1895–1899 (1993), citeseer.ist.psu.edu/bennett93teleporting.html
Deutsch, D.: Quantum computers. Computer Bulletin 3(2), 24 (1987)
Vincent Danos, Elham Kashefi, and Prakash Panangaden. The measurement calculus. Available from www.cs.mcgill.ca/~prakash/pubs.html
Danos, V., Kashefi, E., Panangaden, P.: Robust and parsimonious realisations of unitaries in the one-way model. Phys. Rev. A 72 (2005)
Gottesman, D., Chuang, I.L.: Quantum teleportation is a universal computational primitive. Nature, 390–402 (1999)
Grover, L.K.: A framework for fast quantum mechanical algorithms. In: Proceedings of STOC 1998 – Symposium on Theory of Computing, pp. 53–62 (1998)
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Nielsen, M.A.: Optical quantum computation using cluster states. Phys. Rev. Lett. 93(4), 40503 (2004)
Raussendorf, R., Briegel, H.-J.: A one-way quantum computer. Physical Review Letters 86(5188) (2001)
Raussendorf, R., Browne, D.E., Briegel, H.-J.: Measurement-based quantum computation on cluster states. Phys. Rev. A 68(022312) (2003)
Selinger, P.: Towards a quantum programming language. Mathematical Structures in Computer Science 14(4), 527 (2004)
Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: Proceedings of FOCS 1994 – Symposium on Foundations of Computer Science, p. 124 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Danos, V., Kashefi, E., Panangaden, P. (2006). The One Way to Quantum Computation. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds) Automata, Languages and Programming. ICALP 2006. Lecture Notes in Computer Science, vol 4052. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11787006_2
Download citation
DOI: https://doi.org/10.1007/11787006_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35907-4
Online ISBN: 978-3-540-35908-1
eBook Packages: Computer ScienceComputer Science (R0)