Quantum programming language

From Wikipedia, the free encyclopedia

You have new messages (last change).

Quantum Programming Languages are programming languages that can be used to write programs for quantum computers. Generally, such languages attempt to provide high-level constructs for expressing quantum algorithms.

Contents

[edit] Imperative quantum programming

[edit] Quantum pseudocode

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

[edit] Quantum computing language

QCL (Quantum Computer Language) is one of the first implemented quantum programming languages. Its syntax resembles syntax of the C programming language and classical data types are similar to data types in C.

The basic built-in quantum data type in QCL is qreg (quantum register). It can be interpreted as an array of qubits (quantum bits).

   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

Since qcl interpreter uses qlib simulation library, it is possible to observe internal state of the quantum machine during execution of the quantum programme.

   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>

Note that dump operation is different from measurement, since it does not influence the state of the quantum machine and can be realised only using simulator.

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.

But 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 to define algorithms on higher level of abstraction and extend library of function available for programmer.

[edit] Q language

Q Language is the second implemented imperative quantum programming language.

Q Language was implemented as an extension of C++ programming language. It provides classes for basic quantum operations like QHadamard, QFourier, QNot, QSwap 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

Computation process is executed using provided simulator. Noisy environment can be simulated using parameters of the simulator.

[edit] 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 programmes specification.

[edit] Functional quantum programming

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.

[edit] 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.

[edit] QML

QML is a Haskell-like quantum programming language by Altenkirch and Grattage[1][2]. 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 |\phi\rangle to |\phi\rangle\otimes|\phi\rangle, and is not to be confused with the impossible operation of cloning.

It is planned to be implemented in Haskell (in an inefficient way).

[edit] Quantum lambda calculi

Quantum lambda calculi are extensions of the 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. 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[3].

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

[edit] References

Simon Gay's Quantum Programming Languages Survey has more information on the current state of research and a comprehensive bibliography of resources. [4]

  • Quantum Lambda Calculus [4]
    • A. van Tonder, A Lambda Calculus for Quantum Computation, SIAM J. Comput. 33, 1109-1135, 2004. Also arXiv:quant-ph/0307150
    • A. van Tonder, Quantum Computation, Categorical Semantics and Linear Logic. arXiv:quant-ph/0312174
    • P. Maymin, Extending the Lambda Calculus to Express Randomized and Quantumized Algorithms, 1996. arXiv:quant-ph/9612052
    • P. Maymin, The lambda-q calculus can efficiently simulate quantum computers, 1997. arXiv:quant-ph/9702057
    • P. Selinger, B. Valiron, A lambda calculus for quantum computation with classical control. Mathematical Structures in Computer Science 16(30:527-552, 2006. Also arXiv:LO/0404056 cs. LO/0404056
  • Semantics
    • E. D'Hondt and P. Panangaden, Quantum weakest preconditions. Mathematical Structures in Computer Science, 16(3):429-451, 2006. Also arXiv:quant-ph/0501157
    • Y. Feng, R. Duan, Z. Ji, M. Ying, Semantics of a purely quantum programming language, 2005. arXiv:PL/0507043 cs. PL/0507043

[edit] See also

[edit] External links

Retrieved from "http://en.wikipedia.org../../../q/u/a/Quantum_programming_language.html"
In other languages