Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-06T19:21:49.667Z Has data issue: false hasContentIssue false

7 - Extended Measurement Calculus

Published online by Cambridge University Press:  05 July 2014

By
Vincent Danos ,
Elham Kashefi ,
Prakash Panangaden  and
Simon Perdrix
Edited by
Simon Gay  and
Ian Mackie
Vincent Danos
Affiliation:
University of Edinburgh
Elham Kashefi
Affiliation:
University of Edinburgh
Prakash Panangaden
Affiliation:
McGill University
Simon Perdrix
Affiliation:
University of Edinburgh
Simon Gay
Affiliation:
University of Glasgow
Ian Mackie
Affiliation:
Imperial College London
Get access

Summary

Abstract

Measurement-based quantum computation (MBQC) has emerged as a new approach to quantum computation where the notion of measurement is the main driving force of computation. This is in contrast with the more traditional circuit model that takes unitary operations as fundamental. Among measurement-based quantum computation methods the recently introduced one-way quantum computer stands out as basic and fundamental. The key idea is to start from an entangled state and then use measurements and one-qubit unitaries, which may be dependent on the outcomes of measurements, to guide the computation. The main point is that one never has to perform unitaries on more than one qubit at a time after the initial preparation of an entangled state. The “programs” that one writes in this model are traditionally called “patterns.”

In this chapter, we develop a rigorous mathematical model underlying measurement-based quantum computation. We give syntax, operational semantics, denotational semantics, and an algebra of programs derived from the denotational semantics. We also present a rewrite theory and prove a general standardization theorem that allows all programs to be put in a semantically equivalent standard form. Standardization has far-reaching consequences: a new physical architecture based on performing all the entanglement in the beginning, parallelization by exposing the dependency structure of measurements, and expressiveness theorems.

We use our general measurement calculus not just to formalize the one-way model but also several other measurement-based models, e.g., Teleportation, Phase, and Pauli models, and present compositional embeddings of them into and from the one-way model.

Type
Chapter
Information
Semantic Techniques in Quantum Computation , pp. 235 - 310
Publisher: Cambridge University Press
Print publication year: 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abramsky, S., and Coecke, B. (2004) A categorical semantics of quantum protocols. In Press, I. C. S., editor, Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science (LiCS). Quant-ph/0402130.Google Scholar
Aliferis, P., and Leung, D. W. (2004) Computation by measurements: a unifying picture. Physical Review A 70. Quant-ph/0404082.CrossRefGoogle Scholar
Barendregt, H. P. (1984) The Lambda Calculus, Its Syntax and Semantics. Studies in Logic. North-Holland.Google Scholar
Benjamin, S., Eisert, J., and Stace, T. M. (2005) Optical generation of matter qubit graph states. New Journal of Physics 7. Quant-ph/0506110.CrossRefGoogle Scholar
Benjamin, S. C., Browne, D. E., Fitzsimons, J., and Morton, J. J. L. (2006) Brokered graph state quantum computing. New Journal of Physics 8. Quant-ph/0509209.CrossRefGoogle Scholar
Bennett, C., Brassard, G., Crepeau, C., Jozsa, R., Peres, A., and Wootters, W. (1993) Teleporting an unknown quantum state via dual classical and EPR channels. Physical Review Letters.Google Scholar
Bernstein, E., and Vazirani, U. (1997) Quantum complexity theory. SIAM Journal of Computing 5(26).Google Scholar
Bravyi, S., and Kitaev, A. (2005) Universal quantum computation with ideal clifford gates and noisy ancillas. Physical Review A 71. Quant-ph/0403025.CrossRefGoogle Scholar
Broadbent, A., and Kashefi, E. (2009) On parallelizing quantum circuits. Theoretical Computer Science.Google Scholar
Browne, D., Kashefi, E., Mhalla, M., and Perdrix, S. (2007) Generalized flow and determinism in measurement-based quantum computation. New Journal of Physics 9.CrossRefGoogle Scholar
Browne, D. E., and Rudolph, T. (2005) Resource-efficient linear optical quantum computation. Physical Review Letters 95. Quant-ph/0405157.CrossRefGoogle ScholarPubMed
Chen, Q., Cheng, J., Wang, K. L., and Du, J. (2006) Efficient construction of two-dimensional cluster states with probabilistic quantum gates. Physical Review A 73. Quant-ph/0507066.CrossRefGoogle Scholar
Childs, A. M., Leung, D. W., and Nielsen, M. A. (2005) Unified derivations of measurement-based schemes for quantum computation. Physical Review A 71. Quant-ph/0404132.CrossRefGoogle Scholar
Clark, S. R., Alves, C. M., and Jaksch, D. (2005) Efficient generation of graph states for quantum computation. New Journal of Physics 7. Quant-ph/0406150.CrossRefGoogle Scholar
Danos, V, and Kashefi, E. (2005) Pauli measurements are universal. In Selinger (2005b).Google Scholar
Danos, V, and Kashefi, E. (2006) Determinism in the one-way model. Physical Review A.Google Scholar
Danos, V, Kashefi, E., Olivier, H., and Silva, M. (2006) A direct approach to fault-tolerance in measurement-based quantum computation via teleportation. New Journal of Physics. Quant-ph/0611273.Google Scholar
Danos, V, Kashefi, E., and Panangaden, P. (2005) Parsimonious and robust realizations of unitary maps in the one-way model. Physical Review A 72.CrossRefGoogle Scholar
Danos, V, Kashefi, E., and Panangaden, P. (2007) The measurement calculus. Journal of ACM.Google Scholar
Dawson, C. M., Haselgrove, H. L., and Nielsen, M. A. (2006) Noise thresholds for optical cluster-state quantum computation. Physical Review A 73. Quant-ph/0601066.CrossRefGoogle Scholar
de Beaudrap, N. (2008) Finding flows in the one-way measurement model. Physical Review A 77.CrossRefGoogle Scholar
de Beaudrap, N., Danos, V, and Kashefi, E. (2006) Phase map decomposition for unitaries. Quant-ph/0603266.Google Scholar
de Beaudrap, N., Danos, V, Kashefi, E., and Roetteler, M. (2008) Quadratic form expansions for unitaries. In Theory ofQuantum Computation, Communication, and Cryptography Third Workshop, TQC 2008 Tokyo, Japan, number 5106 in Lecture Notes in Computer Science.Google Scholar
den Nest, M. V., Dehaene, J., and Moor, B. D. (2004a) An efficient algorithm to recognize local clifford equivalence of graph states. Physical Review A 70. Quant-ph/0405023.Google Scholar
den Nest, M. V., Dehaene, J., and Moor, B. D. (2004b) Graphical description of the action of local clifford transformations on graph states. Physical Review A 69. Quant-ph/0308151.Google Scholar
Deutsch, D. (1985) Quantum theory, the Church-Turing principle and the universal quantum computer. In Proceedings of the Royal Society of London, volume A 400.Google Scholar
Deutsch, D. (1989) Quantum computational networks. Proceedings of the Royal Society of London A 425.CrossRefGoogle Scholar
Diestel, R. (2005) Graph Theory. Springer-Verlag.Google Scholar
Duncan, R. (2005) An abstract approach to entanglement. Mathematical Structures In Quantum Informatics, QDay II.Google Scholar
Dür, W., Aschauer, H., and Briegel, H. J. (2003) Multiparticle entanglement purification for graph state. Physical Review Letters 91. Quant-ph/0303087.CrossRefGoogle Scholar
Dürr, C., and Santha, M. (1996) A decision procedure for unitary linear quantum cellular automata. In Proceedings of FOCS'96 – Symposium on Foundations of Computer Science. LNCS. Quant-ph/9604007.Google Scholar
Gilbert, G., Hamrick, M., and Weinstein, Y. S. (2005) Efficient construction of photonic quantum computational clusters. Quant-ph/0512110.Google Scholar
Gottesman, D., and Chuang, I. L. (1999) Quantum teleportation is a universal computational primitive. Nature 402.Google Scholar
Gottesman, D. (1997) Stabilizer codes and quantum error correction. Ph.D. thesis, California Institute of Technology.Google Scholar
Griffiths, R., and Niu, C. (1996) Semiclassical Fourier transform for quantum computation. Physical Review Letters 76:3228–3231.CrossRefGoogle ScholarPubMed
Hartmann, L., Dur, W., and Briegel, H. J. (2005) Steady state entanglement in open and noisy quantum systems at high temperature. Quant-ph/0512219.Google Scholar
Hein, M., Eisert, J., and Briegel, H. J. (2004) Multi-party entanglement in graph states. Physical Review A 69. Quant-ph/0307130.CrossRefGoogle Scholar
Jorrand, P., and Perdrix, S. (2005) Unifying quantum computation with projective measurements only and one-way quantum computation. In Ozhigov, Y. I., editor, Quantum Informatics 2004, volume 5833 of SPIE Proceedings. Quant-ph/0404125.Google Scholar
Jozsa, R. (2005) An introduction to measurement based quantum computation. Quant-ph/0508124.Google Scholar
Kay, A., Pachos, J. K., and Adams, C. S. (2006) Graph-state preparation and quantum computation with global addressing of optical lattices. Physical Review A 73.CrossRefGoogle Scholar
Leung, D. W. (2004) Quantum computation by measurements. International Journal of Quantum Information 2(1). Quant-ph/0310189.CrossRefGoogle Scholar
Mhalla, M., and Perdrix, S. (2004) Complexity of graph state preparation. Quant-ph/0412071.Google Scholar
Mhalla, M., and Perdrix, S. (2008) Finding optimal flows efficiently. In Proceedings of 35th International Colloquium on Automata, Languages and Programming.Google Scholar
Moore, C., and Nilsson, M. (2002) Parallel quantum computation and quantum codes. SIAM Journal on Computing 31.Google Scholar
Nielsen, M. A. (2003) Universal quantum computation using only projective measurement, quantum memory, and preparation of the 0 state. Physical Review A 308.Google Scholar
Nielsen, M. A. (2004) Optical quantum computation using cluster states. Physical Review Letters 93. Quant-ph/0402005.CrossRefGoogle ScholarPubMed
Nielsen, M. A., and Chuang, I. L. (2000) Quantum Computation and Quantum Information. Cambridge University Press.Google Scholar
Perdrix, S. (2003) State transfer instead of teleportation in measurement-based quantum computation. International Journal of Quantum Information 3(1). Quant-ph/0402204.Google Scholar
Perdrix, S. (2006) Formal models of quantum computation: resources, abstract machines and measurement-based quantum computation. Ph.D. thesis, Institut National Polytechnique de Grenoble, Laboratoire Leibniz.Google Scholar
Perdrix, S. (2007) Towards minimal resources of measurement-based quantum computation. New Journal of Physics 9.CrossRefGoogle Scholar
Perdrix, S., and Jorrand, P. (2004) Measurement-based quantum turing machines and their universality. Quant-ph/0404146.Google Scholar
Raussendorf, R., Anders, S., and Briegel, H. J. (2004) Fault-tolerant quantum computation using graph states. Communication to the Quantum Information and Quantum Control Conference, Fields Institute, Toronto. http://atlas-conferences.com/c/a/n/n/80.htm.Google Scholar
Raussendorf, R., and Briegel, H. J. (2001) A one-way quantum computer. Physical Review Letters 86.CrossRefGoogle ScholarPubMed
Raussendorf, R., and Briegel, H. J. (2002) Computational model underlying the one-way quantum computer. Quantum Information & Computation 2. Quant-ph/0108067.Google Scholar
Raussendorf, R., Browne, D. E., and Briegel, H. J. (2003) Measurement-based quantum computation on cluster states. Physical Review A 68.CrossRefGoogle Scholar
Schlingemann, D. (2003) Cluster states, algorithms and graphs. Quant-ph/0305170.Google Scholar
Schumacher, B., and Werner, R. F. (2004) Reversible quantum cellular automata. Quant-ph/0405174.Google Scholar
Selinger, P. (2004) Towards a quantum programming language. Mathematical Structures in Computer Science 14(4).CrossRefGoogle Scholar
Selinger, P. (2005a) Dagger compact closed categories and completely positive maps. In Selinger (2005b).Google Scholar
Selinger, P., editor (2005b) Proceedings of the 3nd International Workshop on Quantum Programming Languages, Electronic Notes in Theoretical Computer Science.Google Scholar
Tame, M. S., Paternostro, M., Kim, M. S., and Vedral, V. (2004) Toward a more economical cluster state quantum computation. Quant-ph/0412156.Google Scholar
Tame, M. S., Paternostro, M., Kim, M. S., and Vedral, V. (2006) Natural three-qubit interactions in one-way quantum computing. Physical Review A 73. Quant-ph/0507173.CrossRefGoogle Scholar
Unruh, D. (2005) Quantum programs with classical output streams. In Selinger (2005b).Google Scholar
van Dam, W. (1996) Quantum cellular automata. Master's thesis, Computer Science, Nijmegen.Google Scholar
Walther, P., k. J., Resch, Rudolph, T., Schenck, E., Weinfurter, H., Vedral, V., Aspelmeyer, M., and Zeilinger, A. (2005) Experimental one-way quantum computing. Nature 434. Quant-ph/0503126.CrossRefGoogle ScholarPubMed
Watrous, J. (1995) On one-dimensional quantum cellular automata. In Proceedings of FOCS'95 – Symposium on Foundations of Computer Science. LNCS.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×