nLab
quantum computation

Idea

General

Quantum computation is computation in terms of quantum information theory, possibly implemented on quantum computers, hence on physical systems for which phenomena of quantum mechanics are not negligible. In terms of computational trinitarianism quantum computation is the computation corresponding to (some kind of) quantum logic.

Specifically, topological quantum computation is (or is meant to be) quantum computation implemented on physical systems governed by topological quantum field theory, such as Chern-Simons theory. A prominent example of this is the (fractional) quantum Hall effect in solid state physics.

Classical control, quantum data

Any practical quantum computer will be classically controlled (Knill 96, Ömer 03, Nagarajan, Papanikolaou & Williams 07, Devitt 14):

From Miszczak 11

From Nagarajan, Papanikolaou Williams 07

Quantum languages and quantum circuits

A natural way (via computational trinitarianism) to understand quantum programming languages is as linear logic/linear type theory (Pratt 92, for more see at quantum logic) with categorical semantics in non-cartesian symmetric monoidal categories (Abramsky & Coecke 04, Abramsky & Duncan 05, Duncan 06, Lago-Faffian 12). .

The corresponding string diagrams are known as quantum circuit diagrams.

In fact, languages for classically controlled quantum computation should be based on dependent linear type theory (Vakar 14, Vakar 15, Vakar 17, Sec. 3, Lundfall 17, Lundfall 18, following Schreiber 14) with categorical semantics in indexed monoidal categories:

classical control	quantum data
intuitionistic types	dependent linear types

This idea of classically controlled quantum programming via dependent linear type theory has been implemented for the Quipper language in FKS 20, FKRS 20.

Related entries

• Bloch region, quantum operation

• Grover's algorithm

• Shor's algorithm

• quantum error correction

• quantum information theory

• quantum circuit

• quantum logic, linear logic

• topological quantum computing

• quantum Hall effect, Chern-Simons theory.

• superoperator

• computable physics

• quantum probability

References

General

The idea of quantum computation was first expressed in:

• Paul Benioff, The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines, J Stat Phys 22, 563–591 (1980) (doi:10.1007/BF01011339)

• Richard Feynman, Simulating physics with computers, Int J Theor Phys 21, 467–488 (1982) (doi:10.1007/BF02650179)

It became a plausible practical possibility with the understanding of quantum error correction in

• Peter W. Shor, Scheme for reducing decoherence in quantum computer memory, Phys. Rev. A 52, R2493(R) 1995 (doi:10.1103/PhysRevA.52.R2493)

• Andrew M. Steane, Error Correcting Codes in Quantum Theory, Phys. Rev. Lett. 77, 793 1996 (doi:10.1103/PhysRevLett.77.793)

• Robert Calderbank, Peter W. Shor, Good Quantum Error-Correcting Codes Exist, Phys. Rev. A, Vol. 54, No. 2, pp. 1098-1106, 1996 (doi:10.1103/PhysRevA.54.1098)

Introduction and survey:

• Michael A. Nielsen, Isaac L. Chuang, Quantum computation and quantum information, Cambridge University Press 2000 (pdf)

• Giuliano Benenti, Giulio Casati, Davide Rossini, Principles of Quantum Computation and Information, World Scientific (2004, 2018) (doi:10.1142/10909, 2004 pdf)

• John Preskill, Quantum Computation lecture notes, since 2004 (web)

• Jens Eisert, M. M. Wolf, Quantum computing, In: Handbook of Nature-Inspired and Innovative Computing, Springer 2006 (arXiv:quant-ph/0401019)

• Greg Kuperberg, A concise introduction to quantum probability, quantum mechanics, and quantum computation, 2005 (pdf)

• Michael Loceff, A course in quantum computing, 2013 (pdf)

• Wikipedia, Quantum computation

• Scott Aaronson, Lecture notes Quantum Computing Since Democritus 2006 (web)

• National Academies of Sciences, Engineering, and Medicine, Quantum Computing: Progress and Prospects, The National Academies Press 2019 (doi:10.17226/25196)

Quantum programming languages

On quantum programming languages (programming languages for quantum computation):

General:

• Jarosław Adam Miszczak, Models of quantum computation and quantum programming languages, Bull. Pol. Acad. Sci.-Tech. Sci., Vol. 59, No. 3 (2011), pp. 305-324 (arXiv:1012.6035)

• Jarosław Adam Miszczak, High-level Structures for Quantum Computing, Morgan&Claypool 2012 (doi:10.2200/S00422ED1V01Y201205QMC006, pdf)

See also:

• Wikipedia, Quantum programming

Surveys of existing languages:

• Simon Gay, Quantum programming languages: Survey and bibliography, Mathematical Structures in Computer Science16(2006) (doi:10.1017/S0960129506005378, pdf)

• Sunita Garhwal, Maryam Ghorani , Amir Ahmad, Quantum Programming Language: A Systematic Review of Research Topic and Top Cited Languages, Arch Computat Methods Eng 28, 289–310 (2021) (doi:10.1007/s11831-019-09372-6)

Quantum programming via quantum logic understood as linear type theory interpreted in symmetric monoidal categories:

• Vaughan Pratt, Linear logic for generalized quantum mechanics, in Proc. of Workshop on Physics and Computation (PhysComp’92) (pdf, web)

• Samson Abramsky, Bob Coecke, A categorical semantics of quantum protocols , Proceedings of the 19th IEEE conference on Logic in Computer Science (LiCS’04). IEEE Computer Science Press (2004) (arXiv:quant-ph/0402130)

• Samson Abramsky, Ross Duncan, A Categorical Quantum Logic, Mathematical Structures in Computer Science, Volume 16, Issue 3 (2006) pp. 469 - 489 (arXiv:quant-ph/0512114, doi:10.1017/S0960129506005275)

• Ross Duncan, Types for Quantum Computing, 2006 (pdf)

• Ugo Dal Lago, Claudia Faggian, On Multiplicative Linear Logic, Modality and Quantum Circuits, EPTCS 95, 2012, pp. 55-66 (arXiv:1210.0613)

The corresponding string diagrams are known in quantum computation as quantum circuit diagrams:

• Giuliano Benenti, Giulio Casati, Davide Rossini, Chapter 3 of: Principles of Quantum Computation and Information, World Scientific 2018 (doi:10.1142/10909, 2004 pdf)

• Miszczak 12, Sec. 4.3

functional programming languages for quantum computation:

QPL:

• Peter Selinger, Towards a quantum programming language, Mathematical Structures in Computer Science 14(4):527–586, 2004 (doi:10.1017/S0960129504004256, pdf, web)

Quipper:

• Peter Selinger, The Quipper Language (web)

• Alexander Green, Peter LeFanu Lumsdaine, Neil Ross, Peter Selinger, Benoît Valiron, Quipper: A Scalable Quantum Programming Language, ACM SIGPLAN Notices 48(6):333-342, 2013 (arXiv:1304.3390)

• Alexander Green, Peter LeFanu Lumsdaine, Neil Ross, Peter Selinger, Benoît Valiron, An Introduction to Quantum Programming in Quipper, Lecture Notes in Computer Science 7948:110-124, Springer, 2013 (arXiv:1304.5485)

• Jonathan Smith, Neil Ross, Peter Selinger, Benoît Valiron, Quipper: Concrete Resource Estimation in Quantum Algorithms, QAPL 2014 (arXiv:1412.0625)

• Francisco Rios, Peter Selinger, A Categorical Model for a Quantum Circuit Description Language, EPTCS 266, 2018, pp. 164-178 (arXiv:1706.02630)

QML:

• Thorsten Altenkirch, Jonathan Grattage, A functional quantum programming language, Logic in Computer Science, 2005. Proceedings. 20th Annual IEEE Symposium on, 26-29 June 2005 Page(s):249 - 258 (arXiv:quant-ph/0409065, doi:10.1109/LICS.2005.1, pdf)

• Jonathan Grattage, An overview of QML with a concrete implementation in Haskell, talk at Quantum Physics and Logic 2008, ENTCS: Proceedings of QPL V - DCV IV, 157-165, Reykjavik, Iceland, 2008 (arXiv:0806.2735)

QWIRE:

• Jennifer Paykin, Robert Rand, Steve Zdancewic, QWIRE: a core language for quantum circuits, POPL 2017: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming LanguagesJanuary 2017 Pages 846–858 (doi:10.1145/3009837.3009894)

  (using the exponential modality between linear type theory and intuitionistic type theory)

• Jennifer Paykin, Linear/non-Linear Types For Embedded Domain-Specific Languages, 2018 (upenn:2752)

• Jennifer Paykin, Steve Zdancewic, A HoTT Quantum Equational Theory, talk at QPL2019 (arXiv:1904.04371)

  (using ambient homotopy type theory)

On classically controlled quantum computation:

• Bernhard Ömer, Structured Quantum Programming, 2003/2009 (pdf)

Quantum programming via dependent linear type theory/indexed monoidal (∞,1)-categories:

• Urs Schreiber, Quantization via Linear Homotopy Types (arXiv:1402.7041)

• Peng Fu, Kohei Kishida, Peter Selinger, Linear Dependent Type Theory for Quantum Programming Languages, LICS ‘20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer ScienceJuly 2020 Pages 440–453 (arXiv:2004.13472, doi:10.1145/3373718.3394765, pdf, video)

specifically with Quipper:

• Peng Fu, Kohei Kishida, Neil Ross, Peter Selinger, A Tutorial Introduction to Quantum Circuit Programming in Dependently Typed Proto-Quipper, in I. Lanese, M. Rawski (eds.) Reversible Computation RC 2020. Lecture Notes in Computer Science, vol 12227 (arXiv:2005.08396, doi:10.1007/978-3-030-52482-1_9)

On quantum software verification:

with Quipper:

• Linda Anticoli, Carla Piazza, Leonardo Taglialegne, Paolo Zuliani, Towards Quantum Programs Verification: From Quipper Circuits to QPMC, In: Devitt S., Lanese I. (eds) Reversible Computation. RC 2016. Lecture Notes in Computer Science, vol 9720. Springer, Cham (doi:10.1007/978-3-319-40578-0_16)

with QWIRE:

• Robert Rand, Jennifer Paykin, Steve Zdancewic, QWIRE Practice: Formal Verification of Quantum Circuits in Coq, EPTCS 266, 2018, pp. 119-132 (arXiv:1803.00699)

Classically controlled quantum computing

• Emanuel Knill, Conventions for quantum pseudocode, 1996 (LA-UR-96-2724, pdf)

• Bernhard Ömer, Structured Quantum Programming, 2003/2009 (pdf)

• Rajagopal Nagarajan, Nikolaos Papanikolaou, David Williams, Simulating and Compiling Code for the Sequential Quantum Random Access Machine, Electronic Notes in Theoretical Computer Science Volume 170, 6 March 2007, Pages 101-124 (doi:10.1016/j.entcs.2006.12.014)

• Jarosław Adam Miszczak, Models of quantum computation and quantum programming languages, Bull. Pol. Acad. Sci.-Tech. Sci., Vol. 59, No. 3 (2011), pp. 305-324 (arXiv:1012.6035)

• Simon J. Devitt, Classical Control of Large-Scale Quantum Computers, In: S. Yamashita, S. Minato (eds.) Reversible Computation Lecture Notes in Computer Science, vol 8507. Springer 2014 (arXiv:1405.4943, doi:10.1007/978-3-319-08494-7_3)

Quantum programming via monads

Discussion of aspects of quantum programming in terms of monads in functional programming are in

• Thorsten Altenkirch, Alexander Green, The quantum IO monad, in Semantic Techniques in Quantum Computation, January 2009, appeared in 2010 (pdf, talk slides)

• J. K. Vizzotto, Thorsten Altenkirch, A. Sabry, Structuring quantum effects: superoperators as arrows (arXiv:quant-ph/0501151)

As linear logic

Discussion of quantum computation as the internal linear logic/linear type theory of compact closed categories is in

• Samson Abramsky, Ross Duncan, A Categorical Quantum Logic, Mathematical Structures in Computer Science, 2006 (arXiv:quant-ph/0512114)

• Ross Duncan, Types for quantum mechanics, 2006 (pdf, slides)

• Ugo Dal Lago, Claudia Faggian, On Multiplicative Linear Logic, Modality and Quantum Circuits, EPTCS 95, 2012, pp. 55-66 (arXiv:1210.0613)

An exposition along these lines is in

• John Baez, Mike Stay, Physics, topology, logic and computation: a rosetta stone, arxiv/0903.0340; in “New Structures for Physics”, ed. Bob Coecke, Lecture Notes in Physics 813, Springer, Berlin, 2011, pp. 95-174

In terms of dagger-compact categories

Discussion in terms of finite quantum mechanics in terms of dagger-compact categories:

• Jamie Vicary, Section 3 of: The Topology of Quantum Algorithms, (LICS 2013) Proceedings of 28th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 93-102 (arXiv:1209.3917)

Topological quantum computing

topological quantum computation is discussed in

• Michael Freedman, Alexei Kitaev, Michael J. Larsen, Zhenghan Wang, Topological Quantum Computation (arXiv:quant-ph/0101025)

• Zhenghan Wang, Topologization of electron liquids with Chern-Simons theory and quantum computation (arXiv:cond-mat/0601285)

• Michael Freedman, Michael Larsen, Zhenghan Wang, A modular functor which is universal for quantum computation (arXiv:quant-ph/0001108)

• Alexei Kitaev, Fault-tolerant quantum computation by anyons, Annals Phys. 303 (2003) 2-30 (arXiv:quant-ph/9707021)

Relation to tensor networks

Relation to tensor networks, specifically matrix product states:

• Yiqing Zhou, E. Miles Stoudenmire, Xavier Waintal, What limits the simulation of quantum computers?, arXiv:2002.07730

Experimental realization

• Han-Shen Zhong et al. Quantum computational advantage using photons, Science 370, n. 6523 (2020) 1460-1463 doi

category: computer science, physics