Quipper: a quantum programming language

Quipper: a quantum programming language

[Peter Selinger]

Dear Category Theorists,

we are proud to announce the first public release of Quipper, an
embedded, scalable functional programming language for quantum
computing. The Quipper distribution is available here:

http://www.mathstat.dal.ca/~selinger/quipper/

and includes extensive documentation, as well as seven worked examples
of non-trivial quantum algorithms from the literature. Here are some
highlights:

* High-level circuit description language, including both gate-by-gate
   descriptions and powerful higher-order operators for assembling and
   manipulating circuits.

* A monadic semantics, allowing for a mixture of procedural and
   declarative programming styles.

* Built-in facilities for automatic synthesis of reversible quantum
   circuits, including from classical Haskell code.

* Support for hierarchical circuits.

* Extensible quantum data types.

* Programmable circuit transformers (that are essentially monoidal
   functors).

* Support for a dynamic lifting operation to allow circuit generation
   to depend on parameters generated at circuit execution time.

* Extensive libraries of quantum functions, including: libraries for
   quantum integer and fixed-point arithmetic; the Quantum Fourier
   transform; an efficient quantum random access memory implementation;
   libraries for simulation of pseudo-classical circuits, Stabilizer
   circuits, and arbitrary circuits; libraries for exact and
   approximate decomposition of circuits into specific gate sets.

Comments are welcome!

Alexander S. Green
Peter LeFanu Lumsdaine
Neil Julien Ross
Peter Selinger
Benoit Valiron


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

RE: Quipper: a quantum programming language

[Joyal, André]

Dear Peter,

I would like to ask you a naive question:

Is it runned on an actual quantum computer?


Best,
André





-----Original Message-----
From: Peter Selinger [mailto:selinger@mathstat.dal.ca]
Sent: Wed 6/19/2013 3:40 PM
To: Categories List
Subject: categories: Quipper: a quantum programming language
 
Dear Category Theorists,

we are proud to announce the first public release of Quipper, an
embedded, scalable functional programming language for quantum
computing. The Quipper distribution is available here:

http://www.mathstat.dal.ca/~selinger/quipper/

and includes extensive documentation, as well as seven worked examples
of non-trivial quantum algorithms from the literature. Here are some
highlights:

* High-level circuit description language, including both gate-by-gate
    descriptions and powerful higher-order operators for assembling and
    manipulating circuits.

* A monadic semantics, allowing for a mixture of procedural and
    declarative programming styles.

* Built-in facilities for automatic synthesis of reversible quantum
    circuits, including from classical Haskell code.

* Support for hierarchical circuits.

* Extensible quantum data types.

* Programmable circuit transformers (that are essentially monoidal
    functors).

* Support for a dynamic lifting operation to allow circuit generation
    to depend on parameters generated at circuit execution time.

* Extensive libraries of quantum functions, including: libraries for
    quantum integer and fixed-point arithmetic; the Quantum Fourier
    transform; an efficient quantum random access memory implementation;
    libraries for simulation of pseudo-classical circuits, Stabilizer
    circuits, and arbitrary circuits; libraries for exact and
    approximate decomposition of circuits into specific gate sets.

Comments are welcome!

Alexander S. Green
Peter LeFanu Lumsdaine
Neil Julien Ross
Peter Selinger
Benoit Valiron

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Quipper: a quantum programming language

[Peter Selinger]

Dear Andre,

the answer, unfortunately, is no. At least we don't think so. We
developed this programming language for IARPA, an agency of the
U.S. government, and effectively nobody knows whether they have a
quantum computer or not.

In any case, the language is designed so that it *could* run on a
quantum computer, if there was one. So now we are just standing by
until somebody builds the hardware :)

There is actually one kind of quantum computer that is already on the
market: the DWave quantum computer. Unfortunately, our language is not
compatible with it; the DWave machine uses a technology called
"adiabatic quantum computing", and people are still figuring out how
to program it. Our language would be compatible with quantum computers
based on the quantum circuit model.

Maybe the underlying point of your question is: why would anybody care
about a quantum programming language, when there is no quantum
computer?

One possible answer is: to help figure out how much it would actually
cost to build one. It is one thing for a quantum algorithm to appear
in a research paper. You will find a lot of statements like "it is
well-known that such-and-such can be done in O(n^2) operations", "by
applying such-and-such trick this problem can be reduced to another
problem with polynomial overhead", and so on. It is quite a different
thing to actually program the algorithm, and to worry about how to do
so efficiently. The difference between using 10^10 operations or 10^50
operations matters a lot in practice, but not in theory. Moreover, one
can then account for additional overhead that people don't usually
think about much, like the cost of adding many layers of error
correction, physical fail-safe mechanisms, and so on. By coding up
some algorithms for "realistic" problem sizes, we get a much better
idea of what kind of computing resources this would actually require.
("Realistic" can be defined as the problem size where a hypothetical
quantum computer would actually outperform a classical computer
running the best known classical algorithm for the problem).

Finally, there is some interesting theory that we can discover by
considering programming languages for quantum computing. To our
surprise, we even found a minor, yet satisfying, application of
identity types from type theory.

Best wishes, -- Peter

Joyal, Andr?? wrote:
>
> Dear Peter,
>
> I would like to ask you a naive question:
>
> Is it runned on an actual quantum computer?
>
>
> Best,
> Andr??
>

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

RE: Quipper: a quantum programming language

[Joyal, André]

Dear Peter,

I thank you for your answer.

Is it possible to "simulate" quantum 
computing on ordinary computers?
Operator algebra is matrix algebra.
Surely, there will be a loss of efficiency.
But it might help understanding
the nature of quantum computations.

Best wishes,
-André


-----Original Message-----
From: Peter Selinger [mailto:selinger@mathstat.dal.ca]
Sent: Thu 6/20/2013 3:36 PM
To: Joyal, André
Cc: Categories List
Subject: Re: categories: Quipper: a quantum programming language
 
Dear Andre,

the answer, unfortunately, is no. At least we don't think so. We
developed this programming language for IARPA, an agency of the
U.S. government, and effectively nobody knows whether they have a
quantum computer or not.

In any case, the language is designed so that it *could* run on a
quantum computer, if there was one. So now we are just standing by
until somebody builds the hardware :)

There is actually one kind of quantum computer that is already on the
market: the DWave quantum computer. Unfortunately, our language is not
compatible with it; the DWave machine uses a technology called
"adiabatic quantum computing", and people are still figuring out how
to program it. Our language would be compatible with quantum computers
based on the quantum circuit model.

Maybe the underlying point of your question is: why would anybody care
about a quantum programming language, when there is no quantum
computer?

One possible answer is: to help figure out how much it would actually
cost to build one. It is one thing for a quantum algorithm to appear
in a research paper. You will find a lot of statements like "it is
well-known that such-and-such can be done in O(n^2) operations", "by
applying such-and-such trick this problem can be reduced to another
problem with polynomial overhead", and so on. It is quite a different
thing to actually program the algorithm, and to worry about how to do
so efficiently. The difference between using 10^10 operations or 10^50
operations matters a lot in practice, but not in theory. Moreover, one
can then account for additional overhead that people don't usually
think about much, like the cost of adding many layers of error
correction, physical fail-safe mechanisms, and so on. By coding up
some algorithms for "realistic" problem sizes, we get a much better
idea of what kind of computing resources this would actually require.
("Realistic" can be defined as the problem size where a hypothetical
quantum computer would actually outperform a classical computer
running the best known classical algorithm for the problem).

Finally, there is some interesting theory that we can discover by
considering programming languages for quantum computing. To our
surprise, we even found a minor, yet satisfying, application of
identity types from type theory.

Best wishes, -- Peter


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

RE: Quipper: a quantum programming language

[Peter Selinger]

Dear Andre,

yes, you are right. Quantum computers can be simulated on classical
computers, but not efficiently. The simulation can be done in
exponential time (or more specifically, polynomial space). Quipper
includes such a simulator (but it is only intended for testing small
components, not to actually run whole programs).

It is an interesting fact that there are subclasses of quantum
computing that *can* be efficiently simulated. Consider the monoidal
category U of finite dimensional Hilbert spaces and unitary maps.
Consider a 2-dimensional Hilbert space V, and consider the full
subcategory U' with objects {1, V, V*V, V*V*V, ...}; here "*" denotes
tensor product.  It is this monoidal category in which quantum
computation usually "takes place". More precisely, one usually
considers a set of generators, for example, some finite set of maps
A,B,C :: V -> V and another finite set of maps D,E,F :: V*V -> V*V.
Let U'' be the smallest monoidal subcategory of U' that contains these
given maps.  For almost all choices of A...F, U'' will be dense in U'.
In the setting of quantum computing, the generators A...F are called
"gates"; the morphisms of the free monoidal category generated by
A...F are called "circuits", and each circuit of course defines a
morphism of U''. Somehow quantum computing is concerned with how to
write certain interesting unitary maps in terms of the given
generators.

This is quite analogous to classical (boolean) circuits, where
"programming" means to decompose a given boolean function of interest
into elementary gates (usually and, or, not, and a fanout gate). From
the point of view, the difference between classical and quantum
computation is that boolean circuit form a cartesian, rather than
monoidal, category.

To get back to the issue of simulation: Consider the generators
X,Y,Z,H,S and CNOT, where X,Y,Z are the Pauli matrices, H is the
Hadamard gate, S is the phase gate, and CNOT :: V*V -> V*V is the
controlled not gate. Their matrices are:

X      Y       Z       H       S
0 1    0 -i    1  0    s  s    1 0
1 0    i  0    0 -1    s -s    0 i

CNOT
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0

where s = 1 / sqrt(2). The monoidal category U'' spanned by these
generators is the so-called Clifford groupoid. Interestingly, U'' is
not at all dense in U'; moreover, it is a (non-trivial) theorem that
quantum computations using only gates from the Clifford groupoid can
be efficiently simulated on a classical computer. It follows, as a
corollary, that any interesting quantum computation must use at least
one non-Clifford gate.

Sorry, this was probably a much longer answer than you asked for.
I'm indulging myself because I think, as a category theorist, this way
of looking at quantum computation is appealing.

Best, -- Peter

Joyal, Andr?? wrote:
>
> Dear Peter,
>
> I thank you for your answer.
>
> Is it possible to "simulate" quantum
> computing on ordinary computers?
> Operator algebra is matrix algebra.
> Surely, there will be a loss of efficiency.
> But it might help understanding
> the nature of quantum computations.
>
> Best wishes,
> -Andr??
>

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]