量子プログラミング言語のソースを表示

'''量子プログラミング言語'''（りょうしプログラミングげんご、{{lang-en-short|Quantum programming language}}）とは<!--高水準のコンストラクトを用いて(using high-level constructs)-->{{仮リンク|量子アルゴリズム|en|Quantum algorithm}}の表現を実現するプログラミング言語の総称である<ref>{{cite web  | author=Jarosław Adam Miszczak |url= http://www.amazon.com/High-Level-Structures-Quantum-Computing/dp/1608458512/ |title= High-level Structures in Quantum Computing |accessdate=12 December 2015}}</ref>。量子プログラミング言語は、プログラマーがプログラミングのツールとして使うことを意図したものではなく、研究者の[[量子コンピュータ]]の振舞いの理解を促進し、研究者が量子アルゴリズムを形式的に論ずるツールとして用いることを意図したものである。

量子プログラミング言語は2つの主要なグループに分けることができる。すなわち、命令型量子プログラミング言語（imperative quantum programming languages）と関数型量子プログラミング言語（functional quantum programming languages）の2つである。

命令型量子プログラミング言語のうち、もっとも有名なものはQCLおよびLanQである<ref>{{cite web |author=Bernhard Omer |title=The QCL Programming Language |url=http://tph.tuwien.ac.at/~oemer/qcl.html |accessdate=11 Feb 2016}}</ref><ref>{{cite web |author=Hynek Mlnařík |title=LanQ – a quantum imperative programming language |url=https://lanq.sourceforge.net/|accessdate=11 Feb 2016}}</ref>。

関数型量子プログラミング言語は開発が進められているところであり、例えばSelinger's QPL<ref name="qpl">Peter Selinger, [http://www.mathstat.dal.ca/~selinger/papers.html#qpl "Towards a quantum programming language"], Mathematical Structures in Computer Science 14(4):527-586, 2004.</ref> や、AltenkirchとGrattageによって開発された、[[Haskell]]に似た言語であるQML<ref name="qml1">[http://www.cs.nott.ac.uk/~jjg/qml.html Jonathan Grattage: QML Research<!-- Bot generated title -->] (website)</ref><ref name="qml2">T. Altenkirch, V. Belavkin, J. Grattage, A. Green, A. Sabry, J. K. Vizzotto, [http://sneezy.cs.nott.ac.uk/qml QML: A Functional Quantum Programming Language] (website)</ref>が挙げられる。

[[ラムダ計算]]を基にした高階量子プログラミング言語(Higher-order quantum programming languages)が、van Tonder<ref>Andre van Tonder, [https://doi.org/10.1137/S0097539703432165 "A Lambda Calculus for Quantum Computation"], SIAM J. Comput., 33(5), 1109–1135. (27 pages), 2004. Also available from [https://arxiv.org/abs/quant-ph/0307150 arXiv:quant-ph/0307150]</ref>、SelingerとValiron<ref>Peter Selinger and Benoît Valiron, [http://www.mathstat.dal.ca/~selinger/papers/#qlambda "A lambda calculus for quantum computation with classical control"], Mathematical Structures in Computer Science 16(3):527-552, 2006.</ref>、ArrighiとDowek<ref>Pablo Arrighi, Gilles Dowek, [http://www.arxiv.org/abs/quant-ph/0612199 "Linear-algebraic lambda-calculus: higher-order, encodings and confluence"], 2006</ref>によって提案されている。

サイモン・ゲイ（Simon Gay）のQuantum Programming Languages Survey<ref group="※">[http://www.dcs.gla.ac.uk/~simon/quantum Quantum Programming Languages Survey]</ref>は量子プログラミング言語の研究に関する情報や2007年時点の量子プログラミングに関する包括的な書物の目録を提供している。

== 命令型量子プログラミング言語 ==

=== 量子擬似コード ===
E. Knillによって考案された量子擬似コード(Quantum pseudocode)は最初に形作られた言語であり、量子アルゴリズムを説明するためのものだった。量子擬似コードは、導入後にQuantum Random Access Machine (QRAM)と呼ばれる量子マシンと強く結び付けられた。

=== Quantum computing language ===
{{仮リンク|QCL|en|Quantum Computation Language}}(Quantum Computation Language)<ref group="※">[http://tph.tuwien.ac.at/~oemer/qcl.html QCL - A Programming Language for Quantum Computers]</ref>は最初に実装された量子プログラミング言語である。Quantum Computation Languageの構文は[[C言語]]の構文に似たものであり、Quantum computing languageの「classical data type」はC言語のプリミティブデータ型と似ていた。ひとつの同じプログラムのなかで古典的（量子プログラミング以前の）コードと量子プログラミングのコードを組み合わせることが可能である。

Quantum computing languageで用意された量子データ型はqureg (quantum register)と呼ばれるものである。これはキュービット（qubit, quantum bit, [[量子ビット]]）の配列として解釈することができる。

    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

Quantum computing languageの[[インタプリタ]]はqlib simulation libraryを採用しているため、量子プログラムの実行中に量子マシンの内部状態を観察することが可能である。

    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>

dump operationはmeasurementとは異なることに注意。これはdump operationが量子マシンの状態に影響せず、simulatorを使うことによってのみ実現されるからである。

Quantum computing languageの標準ライブラリは量子アルゴリズムで用いられる量子オペレータを提供している。例えば次のようなものがある。

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

Quantum computing languageのもっとも重要な特徴はユーザー定義オペレータやユーザー定義関数をサポートしていることである。近代のプログラム言語と同様に、量子データを操作する新たなオペレーションを定義することができる。例えば次のようなものである。

    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
    }

これは[[グローバーのアルゴリズム]]で用いられるmean operatorの逆を定義するものである。これによって、より抽象的な水準でアルゴリズムを定義することが可能になり、関数ライブラリをプログラマーが用いることができるように拡張することができる。

====構文====
*データ型
**量子（Quantum） - qureg, quvoid, quconst, quscratch, qucond
**古典（Classical） - int, real, complex, boolean, string, vector, matrix, tensor
*関数型
**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言語 ===
Q言語<ref group="※">[http://sra.itc.it/people/serafini/qlang/ Q Language]</ref>とは2番目に実装された命令型量子プログラミング言語である。Q言語はC++の拡張として実装された。Q言語は基礎クラスQopから派生したQHadamard、QFourier、QNot、QSwapのような基本的な量子オペレーションのためのクラスを提供する。新たなオペレータはC++のクラスメカニズムを用いて定義される。

量子メモリはQregクラスを用いて表現される。

    Qreg x1; // 初期値0の1キュービット quantum register。
    Qreg x2(2,0); // 初期値0の2キュービット quantum register。
<!--The computation process is executed using a provided simulator. Noisy environment can be simulated using parameters of the simulator.-->

=== qGCL ===
Quantum Guarded Command Language (qGCL)はP. Zulianiによって、彼の博士論文において定義された。これは[[エドガー・ダイクストラ]]によって作られた[[Guarded Command Language]]を基にしている。

qGCLは量子プログラムの言語仕様として評されている。
<!--It can be described as a language of quantum programs specification.-->

=== Q# ===
[[Q Sharp|Q#]]は、2017年に[[マイクロソフト]]によって実装された。Quantum Development Kitに含まれており、[[Microsoft Visual Studio|Visual Studio]]を開発環境として利用できる。
<ref>[https://www.microsoft.com/en-us/quantum/development-kit Quantum Development Kit]</ref>

==  関数型量子プログラミング言語 ==
近年、関数プログラミングに基づく様々な量子プログラミング言語が提案されている。関数プログラミング言語はプログラムのreasoningと相性が良い。
<!--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およびQPL ===
QFCとQPLは互いに関連性の強い量子プログラミング言語であり、Peter Selingerによって定義された。QFCとQPLの違いは単に構文の違いによるものである。QFCはflow chart構文を用いているが、QPLはtextual構文を用いている。QFCとQPLは古典的な制御フローを用いているが、量子データと古典的データの双方を扱うことができる。Selingerは[[:en:superoperator]]の分野においてQFCとQPLに[[表示的意味論|表示的意味]]（denotational semantic）を与えている。

=== QML ===
QML<ref group="※">[http://sneezy.cs.nott.ac.uk/QML/ QML]</ref>はAltenkirchとGrattageによって開発されたHaskelによく似た量子プログラミング言語である<ref name="qml1"/>。SelingerのQPLとは違い、QMLは量子情報を廃棄する（discarding）のではなく、primitive operationとして複製(duplication)をする。この文脈でいう「複製」とは<math>|\phi\rangle</math>を<math>|\phi\rangle\otimes|\phi\rangle</math>へ写す操作として理解され、[[量子複製不可能定理|クローニング]]と混同してはいけない。クローニングは不可能な操作である。
<!--[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.

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

=== Quantum lambda calculi ===
Quantum lambda calculiは古典的な[[ラムダ計算]]の拡張である。古典的なラムダ計算は[[:en:Alonzo Church]]と[[:en:Stephen Cole Kleene]]によって1930年代に考案された。Quantum lambda calculiの目的は量子プログラミング言語を[[高階関数]]の理論で拡張することである。

Quantum lambda calculiを定義する最初の試みは1996年のPhilip Mayminによるものである<ref>Philip Maymin, [https://arxiv.org/abs/quant-ph/9612052 "Extending the Lambda Calculus to Express Randomized and Quantumized Algorithms"], 1996</ref>。Mayminによるlambda-q calculusはあらゆる量子計算を表すことができるほど強力であった。しかし、MayminのQuantum lambda calculiは[[NP完全]]の問題を効率的に解くことができ、それゆえに厳密に標準量子計算モデル（[[:en:quantum Turing machine]]モデルや[[:en:quantum circuit]]モデルなど）よりも強力であるように見えた。ゆえに、Mayminのlambda-q calculusは物理的デバイスには実装不可能な可能性がある。

2003年に、André van Tonderは量子プログラムの正当性を証明するのに適している[[ラムダ計算]]の拡張を定義した。また、van Tonderは[[Scheme]]言語における実装を提供した。<ref>{{cite web |author=André van Tonder |title=A lambda calculus for quantum computation (website) |url=http://www.het.brown.edu/people/andre/qlambda|accessdate=11 Feb 2016}}</ref>。

2004年にはSelingerとValironが線形論理を基にしたtype systemを用いて[[強い型付け]]の量子計算用lambda calculusを定義した。

=== Quipper ===
Quipper<ref group="※">[http://www.mathstat.dal.ca/~selinger/quipper/ The Quipper Language]</ref>は2013年に公開されたものである<ref>{{cite web |author=Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger, Benoît Valiron |title=The Quipper Language (website) |url=http://www.mathstat.dal.ca/~selinger/quipper/|accessdate=11 Feb 2016}}</ref>。QuipperはHaskellをホスト言語として用いて埋め込み言語として実装された<ref>{{cite web |author=Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger, Benoît Valiron |title=An Introduction to Quantum Programming in Quipper |url=https://arxiv.org/abs/1304.5485 |year=2013|accessdate=11 Feb 2016}}</ref>。よって、Quipperで書かれた量子プログラムはHaskellで専用のライブラリを用いて書かれている。例えば、次のコードはpreparation of a superpositionを実装する。

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

== 注釈 ==
{{Reflist|group="※"}}

== 出典 ==
{{Reflist}}

== 外部リンク ==
* [http://www.comlab.ox.ac.uk/people/bob.coecke/DCM_QPL_08.html 5th International Workshop on Quantum Physics and Logic]
* [http://www.mathstat.dal.ca/~selinger/qpl2006/ 4th International Workshop on Quantum Programming Languages]
* [http://www.mathstat.dal.ca/~selinger/qpl2005/ 3rd International Workshop on Quantum Programming Languages]
* [http://www.mathstat.dal.ca/~selinger/qpl2004/ 2nd International Workshop on Quantum Programming Languages]
* [http://www.dcs.gla.ac.uk/~simon/quantum/ Bibliography on Quantum Programming Languages] (updated in May 2007)
* [http://www.quantiki.org/wiki/index.php/Quantum_Programming_Language Quantum programming language] in [http://www.quantiki.org/ Quantiki]

{{量子コンピュータ}}
{{新技術|topics=yes|quantum=yes}}
{{デフォルトソート:りようしふろくらみんくけんこ}}
[[Category:量子プログラミング|*]]
[[Category:プログラミング言語の分類]]