nLab
quantum computation

Idea

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.

There are arguments that a good formal context for quantum computing is (via computational trinitarianism) linear logic/linear type theory (e.g. Lago-Faffian 12). See also at quantum logic.

Programing languages

• A functional programming language for quantum computing is Quipper.

Related entries

• Bloch region, quantum operation

• Shor's algorithm?

• quantum information theory

• quantum circuit

• quantum logic, linear logic

• quantum Hall effect, Chern-Simons theory.

• superoperator

• computable physics

References

General

General discussions include

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

• 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)

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 (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

See also the references at finite quantum mechanics in terms of dagger-compact categories.

In terms of monads

Discussion of aspects of quantum computing 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)

• Thorsten Altenkirch, Jonathan Grattage, A functional quantum programming language (pdf)

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

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)

category: computer science, physics