nLab quantum computation

Skip the Navigation Links | Home Page | All Pages | Latest Revisions | Discuss this page |
Contents

Context

Computation

constructive mathematics, realizability, computability

intuitionistic mathematics

propositions as types, proofs as programs, computational trinitarianism

Constructive mathematics

Realizability

Computability

Quantum systems

quantum logic


quantum physics


quantum probability theory – observables and states


quantum information


quantum computation

quantum algorithms:

Contents

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 the computational trilogy, quantum computation is the computation corresponding to (some kind of) quantum logic/linear type theory.

Usually quantum gates are understood/required to implement unitary operators on a given Hilbert space of quantum states, which implies that quantum comptuation is a form of reversible computation. This implies its susceptibility to noise and the practical need for quantum error correction and/or topological quantum stabilization.

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, in line with the general idea of parameterized quantum systems):

From Miszczak 11


From Nagarajan, Papanikolaou Williams 07

See the list of references below.

The paradigm of classically controlled quantum computation applies in particular (Kim & Swingle 17) to the currently and near-term available noisy intermediate-scale quantum (NISQ) computers (Preskill 18, see the references below), which are useful for highly specialized tasks (only) and need to be emdedded in and called from a more comprehensive classical computing environment.

This, in turn, applies particularly to applications like quantum machine learning (Benedetti, Lloyd, Sack & Fiorentini 19, TensorFlow Quantum, for more see the references there).

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 controlquantum data
intuitionistic typesdependent linear types

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

Examples

References

General

The idea of quantum computation was first expressed in:

  • Yuri I. Manin, Introduction to: Computable and Uncomputable, Sov. Radio (1980) [Russian original: pdf], Enlish translation on p. 69-77 of Mathematics as Metaphor: Selected essays of Yuri I. Manin, Collected Works 20, AMS (2007) [ISBN:978-0-8218-4331-4]

    Perhaps, for a better understanding of [molecular bilogy], we need a mathematical theory of quantum automata.

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

  • Paul Benioff, Quantum Mechanical Models of Turing Machines That Dissipate No Energy, Phys. Rev. Lett. 48 1581 (1982) [doi:10.1103/PhysRevLett.48.1581]

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

    because nature isn’t classical, dammit, if you want to make a simulation of nature, you’d better make it quantum mechanical

The notion of quantum logic gates and quantum circuits was first made explicit in:

The terminology q-bit goes back to:

The potential practical relevance of quantum computation was highlighted early on via toy examples

such as the Deutsch-Jozsa algorithm:

and became widely appreciated in 1996/1997 with the discovery of several practically interesting algorithms exhibiting “quantum supremacy”, such as:

in quantum chemistry

in search algorithms (Grover's algorithm)

and in (quantum) cryptography (Shor's algorithm)

Review:

Quantum computation became widely thought to be not just a theoretical but a plausible practical possibility with the understanding of quantum error correction:

Early review:

Textbook accounts:

Introducing the notion of quantum supremacy and highlighting its relation to quantum entanglement:

  • John Preskill: Quantum computing and the entanglement frontier: pp. 63-80 in: The Theory of the Quantum World – Proceedings of the 25th Solvay Conference on Physics, World Scientific (2013) [arXiv:1203.5813, doi:10.1142/8674, slides: pdf]

Further introduction and survey:

See also:

Discussion in terms of monoidal category-theory and finite quantum mechanics in terms of dagger-compact categories:

Experimental demonstration of “quantum supremacy” (“quantum advantage”):

Review:

Quantum programming languages

The first proposal towards formalizing quantum programming languages was:

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

General:

See also:

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:

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

functional programming languages for quantum computation:

QPL:

Quipper:

QML:

QWIRE:

On classically controlled quantum computation:

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

specifically with Quipper:

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:

Classically controlled quantum computing

Theory of classically controlled quantum computing? and parameterized quantum circuits?:

Application of classically controlled quantum computation:

  • Isaac H. Kim, Brian Swingle, Robust entanglement renormalization on a noisy quantum computer (arXiv:1711.07500)

    (in terms of holographic tensor network states)

  • Sukin Sim, Peter D. Johnson, Alan Aspuru-Guzik, Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms, Adv. Quantum Technol. 2 (2019) 1900070 (arXiv:1905.10876)

  • Mateusz Ostaszewski, Edward Grant, Marcello Benedetti, Structure optimization for parameterized quantum circuits, Quantum 5, 391 (2021) (arXiv:1905.09692)

  • Ruslan Shaydulin et al., A Hybrid Approach for Solving Optimization Problems on Small Quantum Computers (doi:10.1109/MC.2019.2908942)

  • Eneko Osaba, Esther Villar-Rodriguez, Izaskun Oregi, Aitor Moreno-Fernandez-de-Leceta, Focusing on the Hybrid Quantum Computing – Tabu Search Algorithm: new results on the Asymmetric Salesman Problem (arXiv:2102.05919)

in particular in quantum machine learning:

  • Marcello Benedetti, Erika Lloyd, Stefan Sack, Mattia Fiorentini, Parameterized quantum circuits as machine learning models, Quantum Science and Technology 4, 043001 (2019) (arXiv:1906.07682)

  • D. Zhu et al. Training of quantum circuits on a hybrid quantum computer, Science Advances, 18 Oct 2019: Vol. 5, no. 10, eaaw9918 (doi: 10.1126/sciadv.aaw9918)

  • Andrea Mari, Thomas R. Bromley, Josh Izaac, Maria Schuld, Nathan Killoran, Transfer learning in hybrid classical-quantum neural networks, Quantum 4, 340 (2020) (arXiv:1912.08278)

  • Thomas Hubregtsen, Josef Pichlmeier, Patrick Stecher, Koen Bertels, Evaluation of Parameterized Quantum Circuits: on the relation between classification accuracy, expressibility and entangling capability, Quantum Machine Intelligence volume 3, Article number: 9 (2021) (arXiv:2003.09887, doi:10.1007/s42484-021-00038-w)

  • TensorFlow.org (Google), Hybrid quantum classical models

Noisy intermediate-scale quantum computing

  • Nikolaj Moll et al., Quantum optimization using variational algorithms on near-term quantum devices, Quantum Science and Technology, Volume 3, Number 3 2018 (arXiv:1710.01022)

  • John Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2018-08-06, volume 2, page 79 (arXiv:1801.00862, doi:10.22331/q-2018-08-06-79)

  • Daniel Koch, Brett Martin, Saahil Patel, Laura Wessing, and Paul M. Alsing, Demonstrating NISQ era challenges in algorithm design on IBM’s 20 qubit quantum computer, AIP Advances 10, 095101 (2020) (doi:10.1063/5.0015526)

  • Frank Leymann, Johanna Barzen, The bitter truth about gate-based quantum algorithms in the NISQ era, Quantum Sci. Technol. 5 044007 (2020) (doi:10.1088/2058-9565/abae7d)

Quantum programming via monads

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

As linear logic

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

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

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

Last revised on October 2, 2022 at 06:54:35. See the history of this page for a list of all contributions to it.

EditDiscussPrevious revisionChanges from previous revisionHistory (80 revisions) Cite Print Source