Jump to content

Quantum programming: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Citation bot (talk | contribs)
Bots
5,074,026 edits
m Add: isbn, series, year, pages, issue, volume, bibcode, class, asin. Removed accessdate with no specified URL. Removed parameters. You can use this bot yourself. Report bugs here.
Better sections
Line 1: Line 1:
{{redirect|Quantum language|QUANTUM-LANGUAGE-PARSE-SYNTAX-GRAMMAR|David Wynn Miller}}
{{redirect|Quantum language|QUANTUM-LANGUAGE-PARSE-SYNTAX-GRAMMAR|David Wynn Miller}}
'''Quantum programming''' is the process of [[Assembly language|assembling]] sequences of instructions, called quantum programs, that are capable of running on a [[Quantum computing|quantum computer]]. Quantum [[programming language]]s help express [[quantum algorithm]]s using high-level constructs.<ref>{{Cite book| author=Jarosław Adam Miszczak |title= High-level Structures in Quantum Computing | asin=1608458512 }}</ref> Currently, the point of many quantum languages is not so much to provide a tool for programmers, but to provide tools for researchers to understand better how quantum computation works and how to reason formally about quantum algorithms. However, recent developments in quantum computer prototypes have led to the emergence of quantum [[Instruction set architecture|instruction sets]] that are more focused on programming hardware.
'''Quantum programming''' is the process of [[Assembly language|assembling]] sequences of instructions, called quantum programs, that are capable of running on a [[Quantum computing|quantum computer]]. Quantum [[programming language]]s help express [[quantum algorithm]]s using high-level constructs.<ref>{{Cite book| author=Jarosław Adam Miszczak |title= High-level Structures in Quantum Computing | asin=1608458512 }}</ref> Currently, the point of many quantum languages is not so much to provide a tool for programmers, but to provide tools for researchers to understand better how quantum computation works and how to reason formally about quantum algorithms. However, recent developments in quantum computer prototypes have led to the emergence of quantum [[Instruction set architecture|instruction sets]] that are more focused on programming hardware.

One can single out two main groups of quantum programming languages: imperative quantum programming languages and functional quantum programming languages.


The most prominent representatives of the first group are QCL,<ref>{{cite web |author=Bernhard Omer |title=The QCL Programming Language |url=http://tph.tuwien.ac.at/~oemer/qcl.html}}</ref> LanQ <ref>{{cite web |author=Hynek Mlnařík |title=LanQ – a quantum imperative programming language |url=http://lanq.sourceforge.net/}}</ref> and Q|SI>.<ref name=":0" />
The most prominent representatives of the first group are QCL,<ref>{{cite web |author=Bernhard Omer |title=The QCL Programming Language |url=http://tph.tuwien.ac.at/~oemer/qcl.html}}</ref> LanQ <ref>{{cite web |author=Hynek Mlnařík |title=LanQ – a quantum imperative programming language |url=http://lanq.sourceforge.net/}}</ref> and Q|SI>.<ref name=":0" />
Line 10: Line 8:
Simon Gay's [http://www.dcs.gla.ac.uk/~simon/quantum Quantum Programming Languages Survey] provides information on the state of research and a comprehensive bibliography of resources about quantum programming as of 2007. Recent book ''Foundations of Quantum Programming''<ref name=":1">{{Cite book|url=https://www.worldcat.org/oclc/945735387|title=Foundations of quantum programming|last=Mingsheng|first=Ying|isbn=9780128025468|location=Cambridge, MA|oclc=945735387}}</ref> provides a systematic exposition for the research of semantics of quantum programming languages, analysis and verification of quantum programs as well as a comprehensive bibliography as of 2016.
Simon Gay's [http://www.dcs.gla.ac.uk/~simon/quantum Quantum Programming Languages Survey] provides information on the state of research and a comprehensive bibliography of resources about quantum programming as of 2007. Recent book ''Foundations of Quantum Programming''<ref name=":1">{{Cite book|url=https://www.worldcat.org/oclc/945735387|title=Foundations of quantum programming|last=Mingsheng|first=Ying|isbn=9780128025468|location=Cambridge, MA|oclc=945735387}}</ref> provides a systematic exposition for the research of semantics of quantum programming languages, analysis and verification of quantum programs as well as a comprehensive bibliography as of 2016.


== Quantum Instruction Sets and Intermediate Representations ==
== Quantum instruction sets ==
Quantum instruction sets are used to turn higher level algorithms into physical instructions that can be executed on quantum processors. Sometimes these instructions are specific to a given hardware platform, e.g. [[ion trap]]s or [[Superconducting quantum computing|superconducting qubits]].
Quantum instruction sets are used to turn higher level algorithms into physical instructions that can be executed on quantum processors. Sometimes these instructions are specific to a given hardware platform, e.g. [[ion trap]]s or [[Superconducting quantum computing|superconducting qubits]].


=== OpenQASM ===
=== OpenQASM ===
{{main|OpenQASM}}
OpenQASM<ref>{{Citation|title=qiskit-openqasm: OpenQASM specification|date=2017-07-04|url=https://github.com/IBM/qiskit-openqasm|publisher=International Business Machines|accessdate=2017-07-06}}</ref> is the intermediate representation introduced by IBM for use with their [[IBM Quantum Experience|Quantum Experience]].
OpenQASM<ref>{{Citation|title=qiskit-openqasm: OpenQASM specification|date=2017-07-04|url=https://github.com/IBM/qiskit-openqasm|publisher=International Business Machines|accessdate=2017-07-06}}</ref> is the intermediate representation introduced by IBM for use with their [[IBM Quantum Experience|Quantum Experience]].


=== Quil ===
=== Quil ===
{{main|Quil (instruction set architecture)}}
Quil is an instruction set architecture for quantum computing that first introduced a shared quantum/classical memory model. It was introduced by Robert Smith, Michael Curtis, and William Zeng in ''A Practical Quantum Instruction Set Architecture''.<ref>{{cite arxiv|last=Smith|first=Robert S.|last2=Curtis|first2=Michael J.|last3=Zeng|first3=William J.|date=2016-08-10|title=A Practical Quantum Instruction Set Architecture|eprint=1608.03355|class=quant-ph}}</ref> Many quantum algorithms (including [[quantum teleportation]], [[quantum error correction]], simulation,<ref>{{Cite journal|last=McClean|first=Jarrod R.|last2=Romero|first2=Jonathan|last3=Babbush|first3=Ryan|last4=Aspuru-Guzik|first4=Alán|date=2016-02-04|title=The theory of variational hybrid quantum-classical algorithms|arxiv=1509.04279|journal=New Journal of Physics|volume=18|issue=2|pages=023023|doi=10.1088/1367-2630/18/2/023023|issn=1367-2630|bibcode=2016NJPh...18b3023M}}</ref><ref>{{cite arxiv|last=Rubin|first=Nicholas C.|date=2016-10-21|title=A Hybrid Classical/Quantum Approach for Large-Scale Studies of Quantum Systems with Density Matrix Embedding Theory|eprint=1610.06910|class=quant-ph}}</ref> and optimization algorithms<ref>{{cite arxiv|last=Farhi|first=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|date=2014-11-14|title=A Quantum Approximate Optimization Algorithm|eprint=1411.4028|class=quant-ph}}</ref>) require a shared memory architecture. The following example demonstrates the classical control flow needed to do quantum teleportation of the qubit in register 0 to register 2:
# Create Bell Pair
H 0
CNOT 0 1
# Teleport
CNOT 2 0
H 2
MEASURE 2 [0]
MEASURE 0 [1]
# Classically communicate measurements
JUMP-UNLESS @SKIP [1]
X 1
LABEL @SKIP
JUMP-UNLESS @END [0]
Z 1
LABEL @END


Quil is an instruction set architecture for quantum computing that first introduced a shared quantum/classical memory model. It was introduced by Robert Smith, Michael Curtis, and William Zeng in ''A Practical Quantum Instruction Set Architecture''.<ref>{{cite arxiv|last=Smith|first=Robert S.|last2=Curtis|first2=Michael J.|last3=Zeng|first3=William J.|date=2016-08-10|title=A Practical Quantum Instruction Set Architecture|eprint=1608.03355|class=quant-ph}}</ref> Many quantum algorithms (including [[quantum teleportation]], [[quantum error correction]], simulation,<ref>{{Cite journal|last=McClean|first=Jarrod R.|last2=Romero|first2=Jonathan|last3=Babbush|first3=Ryan|last4=Aspuru-Guzik|first4=Alán|date=2016-02-04|title=The theory of variational hybrid quantum-classical algorithms|arxiv=1509.04279|journal=New Journal of Physics|volume=18|issue=2|pages=023023|doi=10.1088/1367-2630/18/2/023023|issn=1367-2630|bibcode=2016NJPh...18b3023M}}</ref><ref>{{cite arxiv|last=Rubin|first=Nicholas C.|date=2016-10-21|title=A Hybrid Classical/Quantum Approach for Large-Scale Studies of Quantum Systems with Density Matrix Embedding Theory|eprint=1610.06910|class=quant-ph}}</ref> and optimization algorithms<ref>{{cite arxiv|last=Farhi|first=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|date=2014-11-14|title=A Quantum Approximate Optimization Algorithm|eprint=1411.4028|class=quant-ph}}</ref>) require a shared memory architecture.
Quil is being developed for the superconducting quantum processors developed by [[Rigetti Computing]] through the Forest [[Cloud-based quantum computing|quantum programming API]].<ref>{{Cite web|url=http://spectrum.ieee.org/tech-talk/computing/software/rigetti-launches-fullstack-quantum-computing-service-and-quantum-ic-fab|title=Rigetti Launches Full-Stack Quantum Computing Service and Quantum IC Fab|website=IEEE Spectrum: Technology, Engineering, and Science News|language=en|access-date=2017-07-06}}</ref><ref>{{Cite web|url=https://quantumcomputingreport.com/news/rigetti-quietly-releases-beta-of-forest-platform-for-quantum-programming-in-the-cloud/|title=Rigetti Quietly Releases Beta of Forest Platform for Quantum Programming in the Cloud {{!}} Quantum Computing Report|website=quantumcomputingreport.com|language=en-US|access-date=2017-07-06}}</ref> A Python library called pyQuil was introduced to develop Quil programs with higher level constructs. A Quil backend is also supported by other quantum programming environments.<ref>{{Cite web|url=https://ornl-qci.github.io/xacc/accelerators/rigetti|title=XACC Rigetti Accelerator|website=ornl-qci.github.io|access-date=2017-07-06}}</ref><ref>{{Citation|last=Doiron|first=Nick|title=jsquil: Quantum computer instructions for JavaScript developers|date=2017-03-07|url=https://github.com/mapmeld/jsquil|accessdate=2017-07-06}}</ref>


== Imperative quantum programming languages ==
== Quantum programming languages ==


There are two main groups of quantum programming languages: imperative quantum programming languages and functional quantum programming languages.
=== Quantum pseudocode ===
Quantum pseudocode proposed by E. Knill is the first formalized language for description of [[quantum algorithm]]s. It was introduced and, moreover, was tightly connected with a model of quantum machine called [[Quantum Random Access Machine]] (QRAM).


=== Quantum computing language ===
=== Imperative languages ===
Quantum Computation Language (QCL) is one of the first implemented quantum [[programming languages]].<ref>{{cite web|url=http://tph.tuwien.ac.at/~oemer/qcl.html |title=QCL - A Programming Language for Quantum Computers |website=tuwien.ac.at |date= |accessdate=2017-07-20}}</ref> Its [[syntax]] resembles the syntax of the [[C programming language]] and its classical [[data type]]s are similar to primitive data types in C. One can combine classical code and quantum code in the same program.


==== Quantum pseudocode ====
The basic built-in quantum data type in QCL is the qureg (quantum register). It can be interpreted as an array of qubits (quantum bits).
Quantum pseudocode proposed by E. Knill is the first formalized language for description of [[quantum algorithm]]s. It was introduced and, moreover, was tightly connected with a model of quantum machine called [[Quantum Random Access Machine]] (QRAM).


==== QCL ====
qureg x1[2]; // 2-qubit quantum register x1
qureg x2[2]; // 2-qubit quantum register x2
H(x1); // Hadamard operation on x1
H(x2[1]); // Hadamard operation on the first qubit of the register x2


{{main|Quantum computation language}}
Since the qcl interpreter uses qlib simulation library, it is possible to observe the internal state of the quantum machine during execution of the quantum program.


Quantum Computation Language (QCL) is one of the first implemented quantum [[programming languages]].<ref>{{cite web|url=http://tph.tuwien.ac.at/~oemer/qcl.html |title=QCL - A Programming Language for Quantum Computers |website=tuwien.ac.at |date= |accessdate=2017-07-20}}</ref> The most important feature of QCL is the support for user-defined operators and functions. Its [[syntax]] resembles the syntax of the [[C programming language]] and its classical [[data type]]s are similar to primitive data types in C. One can combine classical code and quantum code in the same program.
qcl> dump
: STATE: 4 / 32 qubits allocated, 28 / 32 qubits free
0.35355 |0> + 0.35355 |1> + 0.35355 |2> + 0.35355 |3>
+ 0.35355 |8> + 0.35355 |9> + 0.35355 |10> + 0.35355 |11>


====Q|SI>====
Note that the dump operation is different from measurement, since it does not influence the state of the quantum machine and can be realized only using a simulator.

The QCL standard library provides standard quantum operators used in quantum algorithms such as:

* controlled-not with many target qubits,
* [[Hadamard operation]] on many qubits,
* parse and controlled phase.

The most important feature of QCL is the support for user-defined operators and functions. Like in modern programming languages, it is possible to define new operations which can be used to manipulate quantum data. For example:

operator diffuse (qureg q) {
H(q); // Hadamard Transform
Not(q); // Invert q
CPhase(pi, q); // Rotate if q=1111..
!Not(q); // undo inversion
!H(q); // undo Hadamard Transform
}

defines inverse about the mean operator used in [[Grover's algorithm]]. This allows one to define algorithms on a higher level of abstraction and extend the library of functions available for programmers.

====Syntax====
*Data types
**Quantum - qureg, quvoid, quconst, quscratch, qucond
**Classical - int, real, complex, boolean, string, vector, matrix, tensor
*Function types
**qufunct - Pseudo-classic operators. Can only change the permutation of basic states.
**operator - General unitary operators. Can change the amplitude.
**procedure - Can call measure, print, and dump inside this function. This function is non-invertible.
*Built-in functions
**Quantum
***qufunct - Fanout, Swap, Perm2, Perm4, Perm8, Not, CNot
***operator - Matrix2x2, Matrix4x4, Matrix8x8, Rot, Mix, H, CPhase, SqrtNot, X, Y, Z, S, T
***procedure - measure, dump, reset
**Classical
***Arithmetic - sin, cos, tan, log, sqrt, ...
***Complex - Re, Im, conj

===Q|SI>===
Q|SI><ref name=":0">{{Cite journal|last=Liu|first=Shusen|last2=Zhou|first2=li|last3=Guan|first3=Ji|last4=He|first4=Yang|last5=Duan|first5=Runyao|last6=Ying|first6=Mingsheng|date=2017-05-09|title=Q&#124;SI>: A Quantum Programming Language|url=http://engine.scichina.com/doi/10.1360/N112017-00095|journal=SCIENTIA Sinica Information|volume=47|issue=10|pages=1300|doi=10.1360/N112017-00095}}</ref> is a platform embedded in .Net language supporting quantum programming in a quantum extension of while-language.<ref>{{Cite journal|last=Ying|first=Mingsheng|date=January 2012|title=Floyd–hoare Logic for Quantum Programs|url=http://doi.acm.org/10.1145/2049706.2049708|journal=ACM Trans. Program. Lang. Syst.|volume=33|issue=6|pages=19:1–19:49|doi=10.1145/2049706.2049708|issn=0164-0925}}</ref><ref name=":1" /> This platform includes a compiler of the quantum while-language<ref>{{Cite journal|last=Ying|first=Mingsheng|last2=Feng|first2=Yuan|date=2010|title=A Flowchart Language for Quantum Programming|url=https://www.computer.org/csdl/trans/ts/2011/04/tts2011040466-abs.html|journal=IEEE Transactions on Software Engineering|volume=37|issue=4|pages=466–485|doi=10.1109/TSE.2010.94|issn=0098-5589}}</ref> and a chain of tools for the simulation of quantum computation, optimisation of quantum circuits, termination analysis of quantum programs,<ref>{{Cite journal|last=Ying|first=Mingsheng|last2=Yu|first2=Nengkun|last3=Feng|first3=Yuan|last4=Duan|first4=Runyao|title=Verification of quantum programs|url=http://linkinghub.elsevier.com/retrieve/pii/S0167642313000774|journal=Science of Computer Programming|volume=78|issue=9|pages=1679–1700|doi=10.1016/j.scico.2013.03.016|year=2013}}</ref> and verification of quantum programs.<ref>{{Cite journal|last=Ying|first=Mingsheng|last2=Ying|first2=Shenggang|last3=Wu|first3=Xiaodi|date=2017|title=Invariants of Quantum Programs: Characterisations and Generation|url=http://doi.acm.org/10.1145/3009837.3009840|journal=Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages|series=POPL 2017|location=New York, NY, USA|publisher=ACM|pages=818–832|doi=10.1145/3093333.3009840|isbn=9781450346603|volume=52}}</ref><ref>{{cite arxiv|last=Liu|first=Tao|last2=Li|first2=Yangjia|last3=Wang|first3=Shuling|last4=Ying|first4=Mingsheng|last5=Zhan|first5=Naijun|date=2016-01-15|title=A Theorem Prover for Quantum Hoare Logic and Its Applications|eprint=1601.03835|class=cs.LO}}</ref>
Q|SI><ref name=":0">{{Cite journal|last=Liu|first=Shusen|last2=Zhou|first2=li|last3=Guan|first3=Ji|last4=He|first4=Yang|last5=Duan|first5=Runyao|last6=Ying|first6=Mingsheng|date=2017-05-09|title=Q&#124;SI>: A Quantum Programming Language|url=http://engine.scichina.com/doi/10.1360/N112017-00095|journal=SCIENTIA Sinica Information|volume=47|issue=10|pages=1300|doi=10.1360/N112017-00095}}</ref> is a platform embedded in .Net language supporting quantum programming in a quantum extension of while-language.<ref>{{Cite journal|last=Ying|first=Mingsheng|date=January 2012|title=Floyd–hoare Logic for Quantum Programs|url=http://doi.acm.org/10.1145/2049706.2049708|journal=ACM Trans. Program. Lang. Syst.|volume=33|issue=6|pages=19:1–19:49|doi=10.1145/2049706.2049708|issn=0164-0925}}</ref><ref name=":1" /> This platform includes a compiler of the quantum while-language<ref>{{Cite journal|last=Ying|first=Mingsheng|last2=Feng|first2=Yuan|date=2010|title=A Flowchart Language for Quantum Programming|url=https://www.computer.org/csdl/trans/ts/2011/04/tts2011040466-abs.html|journal=IEEE Transactions on Software Engineering|volume=37|issue=4|pages=466–485|doi=10.1109/TSE.2010.94|issn=0098-5589}}</ref> and a chain of tools for the simulation of quantum computation, optimisation of quantum circuits, termination analysis of quantum programs,<ref>{{Cite journal|last=Ying|first=Mingsheng|last2=Yu|first2=Nengkun|last3=Feng|first3=Yuan|last4=Duan|first4=Runyao|title=Verification of quantum programs|url=http://linkinghub.elsevier.com/retrieve/pii/S0167642313000774|journal=Science of Computer Programming|volume=78|issue=9|pages=1679–1700|doi=10.1016/j.scico.2013.03.016|year=2013}}</ref> and verification of quantum programs.<ref>{{Cite journal|last=Ying|first=Mingsheng|last2=Ying|first2=Shenggang|last3=Wu|first3=Xiaodi|date=2017|title=Invariants of Quantum Programs: Characterisations and Generation|url=http://doi.acm.org/10.1145/3009837.3009840|journal=Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages|series=POPL 2017|location=New York, NY, USA|publisher=ACM|pages=818–832|doi=10.1145/3093333.3009840|isbn=9781450346603|volume=52}}</ref><ref>{{cite arxiv|last=Liu|first=Tao|last2=Li|first2=Yangjia|last3=Wang|first3=Shuling|last4=Ying|first4=Mingsheng|last5=Zhan|first5=Naijun|date=2016-01-15|title=A Theorem Prover for Quantum Hoare Logic and Its Applications|eprint=1601.03835|class=cs.LO}}</ref>


==== Q language ====
A complete quantum teleportation example can be illustrated as the following code segment in Q|SI>,
class TestQuantMulti1 : QEnv //Quantum Teleportation
{
public Reg r3 = new Reg("r3");
public Quantum Alice = MakeQBit("{[1/sqrt(5); sqrt(4)/sqrt(5)]}");
public Quantum Bob1 = MakeDensityOperator("{[0.5 0.5;0.5 0.5]}");//|0>+|1>
public Quantum Bob2 = MakeDensityOperator("{[1 0;0 0]}");
U.Emit hGate = MakeU("{[1/sqrt(2) 1/sqrt(2); 1 / sqrt(2) -1 / sqrt(2)]}");
U.Emit CNot = MakeU("{[1 0 0 0;0 1 0 0;0 0 0 1;0 0 1 0]}");//1->2 Cnot
U.Emit xGate = MakeU("{[0 1; 1 0]}");
U.Emit zGate = MakeU("{[1 0;0 -1]}");
M.Emit m = MakeM("{[1 0;0 0],[0 0;0 1]}");
protected override void run()
{
CNot(Bob1, Bob2); //Prepare |00>+|11> for Bob
CNot(Alice, Bob1);
hGate(Alice);
QIf(m(Bob1),
() =>
{ },
() =>
{
xGate(Bob2);
});
QIf(m(Alice),
() =>
{ },
() =>
{
zGate(Bob2);
});
Register(r3, m(Bob2));
}
}

=== Q language ===
Q Language is the second implemented imperative quantum programming language.<ref>{{cite web|url=https://web.archive.org/web/20090620011647/http://sra.itc.it/people/serafini/qlang/ |title=Software for the Q language |website=archive.org |date=2001-11-23 |accessdate=2017-07-20}}</ref> Q Language was implemented as an extension of C++ programming language. It provides classes for basic quantum operations like QHadamard, QFourier, QNot, and QSwap, which are derived from the base class Qop. New operators can be defined using C++ class mechanism.
Q Language is the second implemented imperative quantum programming language.<ref>{{cite web|url=https://web.archive.org/web/20090620011647/http://sra.itc.it/people/serafini/qlang/ |title=Software for the Q language |website=archive.org |date=2001-11-23 |accessdate=2017-07-20}}</ref> Q Language was implemented as an extension of C++ programming language. It provides classes for basic quantum operations like QHadamard, QFourier, QNot, and QSwap, which are derived from the base class Qop. New operators can be defined using C++ class mechanism.


Line 145: Line 48:
The computation process is executed using a provided simulator. Noisy environments can be simulated using parameters of the simulator.
The computation process is executed using a provided simulator. Noisy environments can be simulated using parameters of the simulator.


=== qGCL ===
==== qGCL ====
Quantum Guarded Command Language (qGCL) was defined by P. Zuliani in his PhD thesis. It is based on [[Guarded Command Language]] created by [[Edsger Dijkstra]].
Quantum Guarded Command Language (qGCL) was defined by P. Zuliani in his PhD thesis. It is based on [[Guarded Command Language]] created by [[Edsger Dijkstra]].


It can be described as a language of quantum programs specification.
It can be described as a language of quantum programs specification.


=== QMASM ===
==== QMASM ====


Quantum Macro Assembler (QMASM) is a low-level language specific to quantum annealers such as the D-Wave.<ref>Scott Pakin, [http://ieeexplore.ieee.org/document/7761637/ "A Quantum Macro Assembler"], Proceedings of the 20th Annual IEEE High Performance Extreme Computing Conference 2016</ref>
Quantum Macro Assembler (QMASM) is a low-level language specific to quantum annealers such as the D-Wave.<ref>Scott Pakin, [http://ieeexplore.ieee.org/document/7761637/ "A Quantum Macro Assembler"], Proceedings of the 20th Annual IEEE High Performance Extreme Computing Conference 2016</ref>


== Functional quantum programming languages ==
=== Functional languages ===
During the last few years many quantum programming languages based on the [[functional programming]] paradigm were proposed. Functional programming languages are well-suited for reasoning about programs.
During the last few years many quantum programming languages based on the [[functional programming]] paradigm were proposed. Functional programming languages are well-suited for reasoning about programs.


=== QFC and QPL ===
==== QFC and QPL ====
QFC and QPL are two closely related quantum programming languages defined by Peter Selinger. They differ only in their syntax: QFC uses a flow chart syntax, whereas QPL uses a textual syntax. These languages have classical control flow but can operate on quantum or classical data. Selinger gives a denotational semantics for these languages in a category of
QFC and QPL are two closely related quantum programming languages defined by Peter Selinger. They differ only in their syntax: QFC uses a flow chart syntax, whereas QPL uses a textual syntax. These languages have classical control flow but can operate on quantum or classical data. Selinger gives a denotational semantics for these languages in a category of
[[superoperator]]s.
[[superoperator]]s.


=== QML ===
==== QML ====


[http://sneezy.cs.nott.ac.uk/QML/ QML] is a [[Haskell (programming language)|Haskell]]-like quantum programming language by Altenkirch and Grattage.<ref name="qml1"/> Unlike Selinger's QPL, this language takes duplication, rather than discarding, of quantum information as a primitive operation. Duplication in this context is understood to be the operation that maps <math>|\phi\rangle</math> to <math>|\phi\rangle\otimes|\phi\rangle</math>, and is not to be confused with the impossible operation of [[no cloning theorem|cloning]]; the authors claim it is akin to how sharing is modeled in classical languages. QML also introduces both classical and quantum control operators, whereas most other languages rely on classical control.
[http://sneezy.cs.nott.ac.uk/QML/ QML] is a [[Haskell (programming language)|Haskell]]-like quantum programming language by Altenkirch and Grattage.<ref name="qml1"/> Unlike Selinger's QPL, this language takes duplication, rather than discarding, of quantum information as a primitive operation. Duplication in this context is understood to be the operation that maps <math>|\phi\rangle</math> to <math>|\phi\rangle\otimes|\phi\rangle</math>, and is not to be confused with the impossible operation of [[no cloning theorem|cloning]]; the authors claim it is akin to how sharing is modeled in classical languages. QML also introduces both classical and quantum control operators, whereas most other languages rely on classical control.
Line 167: Line 70:
An [[operational semantics]] for QML is given in terms of [[quantum circuit]]s, while a [[denotational semantics]] is presented in terms of [[superoperator]]s, and these are shown to agree. Both the operational and denotational semantics have been implemented (classically) in Haskell.<ref>Jonathan Grattage, [http://sneezy.cs.nott.ac.uk/qml/compiler QML: A Functional Quantum Programming Language (compiler)], 2005–2008</ref>
An [[operational semantics]] for QML is given in terms of [[quantum circuit]]s, while a [[denotational semantics]] is presented in terms of [[superoperator]]s, and these are shown to agree. Both the operational and denotational semantics have been implemented (classically) in Haskell.<ref>Jonathan Grattage, [http://sneezy.cs.nott.ac.uk/qml/compiler QML: A Functional Quantum Programming Language (compiler)], 2005–2008</ref>


=== LIQUi|> ===
==== LIQUi|> ====
LIQUi|> (pronounced 'liquid') is a quantum simulation extension on the [[F Sharp (programming language)|F#]] programming language.<ref>{{cite web|url=http://stationq.github.io/Liquid/|title=The Language Integrated Quantum Operations Simulator |website=github.io |date=|accessdate=2017-07-20}}</ref> It is currently being developed by the Quantum Architectures and Computation Group (QuArC) <ref>Quantum Architectures and Computation Group (QuArC), https://www.microsoft.com/en-us/research/group/quantum-architectures-and-computation-group-quarc/, 2011</ref> part of the StationQ efforts at Microsoft Research. LIQUi|> seeks to allow theorists to experiment with quantum algorithm design before physical quantum computers are available for use.<ref>{{cite web|url=https://stationq.microsoft.com/ |title=StationQ |website=microsoft.com |date=|accessdate=2017-07-20}}</ref>
LIQUi|> (pronounced 'liquid') is a quantum simulation extension on the [[F Sharp (programming language)|F#]] programming language.<ref>{{cite web|url=http://stationq.github.io/Liquid/|title=The Language Integrated Quantum Operations Simulator |website=github.io |date=|accessdate=2017-07-20}}</ref> It is currently being developed by the Quantum Architectures and Computation Group (QuArC) <ref>Quantum Architectures and Computation Group (QuArC), https://www.microsoft.com/en-us/research/group/quantum-architectures-and-computation-group-quarc/, 2011</ref> part of the StationQ efforts at Microsoft Research. LIQUi|> seeks to allow theorists to experiment with quantum algorithm design before physical quantum computers are available for use.<ref>{{cite web|url=https://stationq.microsoft.com/ |title=StationQ |website=microsoft.com |date=|accessdate=2017-07-20}}</ref>


It includes a programming language, optimization and scheduling algorithms, and quantum simulators. LIQUi|> can be used to translate a quantum algorithm written in the form of a high-level program into the low-level machine instructions for a quantum device.<ref>Language-Integrated Quantum Operations: LIQUi|>, [https://www.microsoft.com/en-us/research/project/language-integrated-quantum-operations-liqui/], 2016</ref>
It includes a programming language, optimization and scheduling algorithms, and quantum simulators. LIQUi|> can be used to translate a quantum algorithm written in the form of a high-level program into the low-level machine instructions for a quantum device.<ref>Language-Integrated Quantum Operations: LIQUi|>, [https://www.microsoft.com/en-us/research/project/language-integrated-quantum-operations-liqui/], 2016</ref>


=== Quantum lambda calculi ===
==== Quantum lambda calculi ====
Quantum lambda calculi are extensions of the classical [[lambda calculus]] introduced by [[Alonzo Church]] and [[Stephen Cole Kleene]] in the 1930s. The purpose of quantum lambda calculi is to extend quantum programming languages with a theory of [[higher-order functions]].
Quantum lambda calculi are extensions of the classical [[lambda calculus]] introduced by [[Alonzo Church]] and [[Stephen Cole Kleene]] in the 1930s. The purpose of quantum lambda calculi is to extend quantum programming languages with a theory of [[higher-order functions]].


Line 182: Line 85:
In 2004, Selinger and Valiron defined a [[strongly typed]] lambda calculus for quantum computation with a type system based on [[linear logic]].
In 2004, Selinger and Valiron defined a [[strongly typed]] lambda calculus for quantum computation with a type system based on [[linear logic]].


=== Quipper ===
==== Quipper ====


[http://www.mathstat.dal.ca/~selinger/quipper/ Quipper] was published in 2013.<ref>{{cite web |author1=Alexander S. Green |author2=Peter LeFanu Lumsdaine |author3=Neil J. Ross |author4=Peter Selinger |author5=Benoît Valiron |title=The Quipper Language (website) |url=http://www.mathstat.dal.ca/~selinger/quipper/}}</ref> It is implemented as an embedded language, using [[Haskell (programming language)|Haskell]] as the host language.<ref>{{cite journal |author1=Alexander S. Green |author2=Peter LeFanu Lumsdaine |author3=Neil J. Ross |author4=Peter Selinger |author5=Benoît Valiron |title=An Introduction to Quantum Programming in Quipper |arxiv=1304.5485|year=2013 |doi=10.1007/978-3-642-38986-3_10 |journal=Lecture Notes in Computer Science |volume=7948 |pages=110–124|series=Lecture Notes in Computer Science |isbn=978-3-642-38985-6 }}</ref> For this reason, quantum programs written in Quipper are written in [[Haskell (programming language)|Haskell]] using provided libraries. For example, the following code implements preparation of a superposition
[http://www.mathstat.dal.ca/~selinger/quipper/ Quipper] was published in 2013.<ref>{{cite web |author1=Alexander S. Green |author2=Peter LeFanu Lumsdaine |author3=Neil J. Ross |author4=Peter Selinger |author5=Benoît Valiron |title=The Quipper Language (website) |url=http://www.mathstat.dal.ca/~selinger/quipper/}}</ref> It is implemented as an embedded language, using [[Haskell (programming language)|Haskell]] as the host language.<ref>{{cite journal |author1=Alexander S. Green |author2=Peter LeFanu Lumsdaine |author3=Neil J. Ross |author4=Peter Selinger |author5=Benoît Valiron |title=An Introduction to Quantum Programming in Quipper |arxiv=1304.5485|year=2013 |doi=10.1007/978-3-642-38986-3_10 |journal=Lecture Notes in Computer Science |volume=7948 |pages=110–124|series=Lecture Notes in Computer Science |isbn=978-3-642-38985-6 }}</ref> For this reason, quantum programs written in Quipper are written in [[Haskell (programming language)|Haskell]] using provided libraries. For example, the following code implements preparation of a superposition

Revision as of 18:13, 19 November 2017

"Quantum language" redirects here. For QUANTUM-LANGUAGE-PARSE-SYNTAX-GRAMMAR, see David Wynn Miller.

Quantum programming is the process of assembling sequences of instructions, called quantum programs, that are capable of running on a quantum computer. Quantum programming languages help express quantum algorithms using high-level constructs.[1] Currently, the point of many quantum languages is not so much to provide a tool for programmers, but to provide tools for researchers to understand better how quantum computation works and how to reason formally about quantum algorithms. However, recent developments in quantum computer prototypes have led to the emergence of quantum instruction sets that are more focused on programming hardware.

The most prominent representatives of the first group are QCL,[2] LanQ [3] and Q|SI>.[4]

Efforts are underway to develop functional programming languages for quantum computing. Examples include Selinger's QPL,[5] and the Haskell-like language QML by Altenkirch and Grattage.[6][7] Higher-order quantum programming languages, based on lambda calculus, have been proposed by van Tonder,[8] Selinger and Valiron [9] and by Arrighi and Dowek.[10]

Simon Gay's Quantum Programming Languages Survey provides information on the state of research and a comprehensive bibliography of resources about quantum programming as of 2007. Recent book Foundations of Quantum Programming[11] provides a systematic exposition for the research of semantics of quantum programming languages, analysis and verification of quantum programs as well as a comprehensive bibliography as of 2016.

Quantum instruction sets

Quantum instruction sets are used to turn higher level algorithms into physical instructions that can be executed on quantum processors. Sometimes these instructions are specific to a given hardware platform, e.g. ion traps or superconducting qubits.

OpenQASM

Main article: OpenQASM

OpenQASM[12] is the intermediate representation introduced by IBM for use with their Quantum Experience.

Quil

Main article: Quil (instruction set architecture)

Quil is an instruction set architecture for quantum computing that first introduced a shared quantum/classical memory model. It was introduced by Robert Smith, Michael Curtis, and William Zeng in A Practical Quantum Instruction Set Architecture.[13] Many quantum algorithms (including quantum teleportation, quantum error correction, simulation,[14][15] and optimization algorithms[16]) require a shared memory architecture.

Quantum programming languages

There are two main groups of quantum programming languages: imperative quantum programming languages and functional quantum programming languages.

Imperative languages

Quantum pseudocode

Quantum pseudocode proposed by E. Knill is the first formalized language for description of quantum algorithms. It was introduced and, moreover, was tightly connected with a model of quantum machine called Quantum Random Access Machine (QRAM).

QCL

Main article: Quantum computation language

Quantum Computation Language (QCL) is one of the first implemented quantum programming languages.[17] The most important feature of QCL is the support for user-defined operators and functions. Its syntax resembles the syntax of the C programming language and its classical data types are similar to primitive data types in C. One can combine classical code and quantum code in the same program.

Q|SI>

Q|SI>[4] is a platform embedded in .Net language supporting quantum programming in a quantum extension of while-language.[18][11] This platform includes a compiler of the quantum while-language[19] and a chain of tools for the simulation of quantum computation, optimisation of quantum circuits, termination analysis of quantum programs,[20] and verification of quantum programs.[21][22]

Q language

Q Language is the second implemented imperative quantum programming language.[23] Q Language was implemented as an extension of C++ programming language. It provides classes for basic quantum operations like QHadamard, QFourier, QNot, and QSwap, which are derived from the base class Qop. New operators can be defined using C++ class mechanism.

Quantum memory is represented by class Qreg. 

   Qreg x1; // 1-qubit quantum register with initial value 0
   Qreg x2(2,0); // 2-qubit quantum register with initial value 0

The computation process is executed using a provided simulator. Noisy environments can be simulated using parameters of the simulator.

qGCL

Quantum Guarded Command Language (qGCL) was defined by P. Zuliani in his PhD thesis. It is based on Guarded Command Language created by Edsger Dijkstra.

It can be described as a language of quantum programs specification.

QMASM

Quantum Macro Assembler (QMASM) is a low-level language specific to quantum annealers such as the D-Wave.[24]

Functional languages

During the last few years many quantum programming languages based on the functional programming paradigm were proposed. Functional programming languages are well-suited for reasoning about programs.

QFC and QPL

QFC and QPL are two closely related quantum programming languages defined by Peter Selinger. They differ only in their syntax: QFC uses a flow chart syntax, whereas QPL uses a textual syntax. These languages have classical control flow but can operate on quantum or classical data. Selinger gives a denotational semantics for these languages in a category of superoperators.

QML

QML is a Haskell-like quantum programming language by Altenkirch and Grattage.[6] Unlike Selinger's QPL, this language takes duplication, rather than discarding, of quantum information as a primitive operation. Duplication in this context is understood to be the operation that maps to , and is not to be confused with the impossible operation of cloning; the authors claim it is akin to how sharing is modeled in classical languages. QML also introduces both classical and quantum control operators, whereas most other languages rely on classical control.

An operational semantics for QML is given in terms of quantum circuits, while a denotational semantics is presented in terms of superoperators, and these are shown to agree. Both the operational and denotational semantics have been implemented (classically) in Haskell.[25]

LIQUi|>

LIQUi|> (pronounced 'liquid') is a quantum simulation extension on the F# programming language.[26] It is currently being developed by the Quantum Architectures and Computation Group (QuArC) [27] part of the StationQ efforts at Microsoft Research. LIQUi|> seeks to allow theorists to experiment with quantum algorithm design before physical quantum computers are available for use.[28]

It includes a programming language, optimization and scheduling algorithms, and quantum simulators. LIQUi|> can be used to translate a quantum algorithm written in the form of a high-level program into the low-level machine instructions for a quantum device.[29]

Quantum lambda calculi

Quantum lambda calculi are extensions of the classical lambda calculus introduced by Alonzo Church and Stephen Cole Kleene in the 1930s. The purpose of quantum lambda calculi is to extend quantum programming languages with a theory of higher-order functions.

The first attempt to define a quantum lambda calculus was made by Philip Maymin in 1996.[30] His lambda-q calculus is powerful enough to express any quantum computation. However, this language can efficiently solve NP-complete problems, and therefore appears to be strictly stronger than the standard quantum computational models (such as the quantum Turing machine or the quantum circuit model). Therefore, Maymin's lambda-q calculus is probably not implementable on a physical device.

In 2003, André van Tonder defined an extension of the lambda calculus suitable for proving correctness of quantum programs. He also provided an implementation in the Scheme programming language.[31]

In 2004, Selinger and Valiron defined a strongly typed lambda calculus for quantum computation with a type system based on linear logic.

Quipper

Quipper was published in 2013.[32] It is implemented as an embedded language, using Haskell as the host language.[33] For this reason, quantum programs written in Quipper are written in Haskell using provided libraries. For example, the following code implements preparation of a superposition 

   import Quipper
   
   spos :: Bool -> Circ Qubit
   spos b = do q <- qinit b
               r <- hadamard q
               return r

References

  1. ^ Jarosław Adam Miszczak. High-level Structures in Quantum Computing. ASIN 1608458512. {{cite book}}: Check |asin= value (help)
  2. ^ Bernhard Omer. "The QCL Programming Language".
  3. ^ Hynek Mlnařík. "LanQ – a quantum imperative programming language".
  4. ^ a b Liu, Shusen; Zhou, li; Guan, Ji; He, Yang; Duan, Runyao; Ying, Mingsheng (2017-05-09). "Q|SI>: A Quantum Programming Language". SCIENTIA Sinica Information. 47 (10): 1300. doi:10.1360/N112017-00095.
  5. ^ Peter Selinger, "Towards a quantum programming language", Mathematical Structures in Computer Science 14(4):527-586, 2004.
  6. ^ a b Jonathan Grattage: QML Research (website)
  7. ^ T. Altenkirch, V. Belavkin, J. Grattage, A. Green, A. Sabry, J. K. Vizzotto, QML: A Functional Quantum Programming Language (website)
  8. ^ Andre van Tonder, "A Lambda Calculus for Quantum Computation", SIAM J. Comput., 33(5), 1109–1135. (27 pages), 2004. Also available from arXiv:quant-ph/0307150
  9. ^ Peter Selinger and Benoît Valiron, "A lambda calculus for quantum computation with classical control", Mathematical Structures in Computer Science 16(3):527-552, 2006.
  10. ^ Pablo Arrighi, Gilles Dowek, "Linear-algebraic lambda-calculus: higher-order, encodings and confluence", 2006
  11. ^ a b Mingsheng, Ying. Foundations of quantum programming. Cambridge, MA. ISBN 9780128025468. OCLC 945735387.
  12. ^ qiskit-openqasm: OpenQASM specification, International Business Machines, 2017-07-04, retrieved 2017-07-06
  13. ^ Smith, Robert S.; Curtis, Michael J.; Zeng, William J. (2016-08-10). "A Practical Quantum Instruction Set Architecture". arXiv:1608.03355 [quant-ph].
  14. ^ McClean, Jarrod R.; Romero, Jonathan; Babbush, Ryan; Aspuru-Guzik, Alán (2016-02-04). "The theory of variational hybrid quantum-classical algorithms". New Journal of Physics. 18 (2): 023023. arXiv:1509.04279. Bibcode:2016NJPh...18b3023M. doi:10.1088/1367-2630/18/2/023023. ISSN 1367-2630.
  15. ^ Rubin, Nicholas C. (2016-10-21). "A Hybrid Classical/Quantum Approach for Large-Scale Studies of Quantum Systems with Density Matrix Embedding Theory". arXiv:1610.06910 [quant-ph].
  16. ^ Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (2014-11-14). "A Quantum Approximate Optimization Algorithm". arXiv:1411.4028 [quant-ph].
  17. ^ "QCL - A Programming Language for Quantum Computers". tuwien.ac.at. Retrieved 2017-07-20.
  18. ^ Ying, Mingsheng (January 2012). "Floyd–hoare Logic for Quantum Programs". ACM Trans. Program. Lang. Syst. 33 (6): 19:1–19:49. doi:10.1145/2049706.2049708. ISSN 0164-0925.
  19. ^ Ying, Mingsheng; Feng, Yuan (2010). "A Flowchart Language for Quantum Programming". IEEE Transactions on Software Engineering. 37 (4): 466–485. doi:10.1109/TSE.2010.94. ISSN 0098-5589.
  20. ^ Ying, Mingsheng; Yu, Nengkun; Feng, Yuan; Duan, Runyao (2013). "Verification of quantum programs". Science of Computer Programming. 78 (9): 1679–1700. doi:10.1016/j.scico.2013.03.016.
  21. ^ Ying, Mingsheng; Ying, Shenggang; Wu, Xiaodi (2017). "Invariants of Quantum Programs: Characterisations and Generation". Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages. POPL 2017. 52. New York, NY, USA: ACM: 818–832. doi:10.1145/3093333.3009840. ISBN 9781450346603.
  22. ^ Liu, Tao; Li, Yangjia; Wang, Shuling; Ying, Mingsheng; Zhan, Naijun (2016-01-15). "A Theorem Prover for Quantum Hoare Logic and Its Applications". arXiv:1601.03835 [cs.LO].
  23. ^ "Software for the Q language". archive.org. 2001-11-23. Retrieved 2017-07-20.
  24. ^ Scott Pakin, "A Quantum Macro Assembler", Proceedings of the 20th Annual IEEE High Performance Extreme Computing Conference 2016
  25. ^ Jonathan Grattage, QML: A Functional Quantum Programming Language (compiler), 2005–2008
  26. ^ "The Language Integrated Quantum Operations Simulator". github.io. Retrieved 2017-07-20.
  27. ^ Quantum Architectures and Computation Group (QuArC), https://www.microsoft.com/en-us/research/group/quantum-architectures-and-computation-group-quarc/, 2011
  28. ^ "StationQ". microsoft.com. Retrieved 2017-07-20.
  29. ^ Language-Integrated Quantum Operations: LIQUi|>, [1], 2016
  30. ^ Philip Maymin, "Extending the Lambda Calculus to Express Randomized and Quantumized Algorithms", 1996
  31. ^ André van Tonder. "A lambda calculus for quantum computation (website)".
  32. ^ Alexander S. Green; Peter LeFanu Lumsdaine; Neil J. Ross; Peter Selinger; Benoît Valiron. "The Quipper Language (website)".
  33. ^ Alexander S. Green; Peter LeFanu Lumsdaine; Neil J. Ross; Peter Selinger; Benoît Valiron (2013). "An Introduction to Quantum Programming in Quipper". Lecture Notes in Computer Science. Lecture Notes in Computer Science. 7948: 110–124. arXiv:1304.5485. doi:10.1007/978-3-642-38986-3_10. ISBN 978-3-642-38985-6.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Quantum_programming&oldid=811127793"