Safe Haskell | None |
---|

This module provides a user-friendly interface to building quantum circuits out of classical functions on booleans. It is based on lower-level functionality provided by Libraries.Template.

Technically, the only functions to be used in this module are

, a specialized version of `decToCircMonad`

, and
`decToMonad`

. The only useful datatype here is `unpack`

.`BoolParam`

One should not have to directly use the other things: they are only for the internal use of Template Haskell to build quantum circuits out of classical computation on booleans.

Note: in the following, we write circuits in ASCII form. The following conventions are used. They are extended in obvious ways when applicable (e.g. when writing a ternary gate).

---- : wire 0 |-- : initialize an ancilla |0> --| 0 : terminate an ancilla, asserting it was |0> +--+ -| |- : a unary gate +--+ +--+ -| |- | | : a binary gate -| |- +--+ -- -- X : swap gate -- -- --x-- | : controlled-not, applying NOT on the bottom wire if the top one is |1> --N-- --o-- | : controlled-not, applying NOT on the bottom wire if the top one is |0> --N--

- data BoolParam
- newBool :: BoolParam -> Bool
- template_PFalse :: Circ BoolParam
- template_PTrue :: Circ BoolParam
- decToCircMonad :: Q [Dec] -> Q [Dec]
- template_newBool :: Circ (BoolParam -> Circ Qubit)
- template_False :: Circ Qubit
- template_True :: Circ Qubit
- template_not :: Circ (Qubit -> Circ Qubit)
- template_symb_ampersand_symb_ampersand_ :: Circ (Qubit -> Circ (Qubit -> Circ Qubit))
- template_symb_vbar_symb_vbar_ :: Circ (Qubit -> Circ (Qubit -> Circ Qubit))
- template_bool_xor :: Circ (Qubit -> Circ (Qubit -> Circ Qubit))
- template_if :: QData b => Circ Qubit -> Circ b -> Circ b -> Circ b
- template_symb_equal_symb_equal_ :: QEq qa => Circ (qa -> Circ (qa -> Circ Qubit))
- class CircLiftingUnpack packed unpacked | packed -> unpacked, unpacked -> packed where

# Overview

Using the tool

designed in Libraries.Template, we
can easily generate quantum circuits. Indeed, suppose that we are given the classical oracle `decToMonad`

toyOracle :: Bool -> Bool toyOracle a = f (g a) (h a)

for some `g,h :: Bool -> Bool`

and `f :: Bool -> Bool -> Bool`

. If
*g* and *h* are given by quantum circuits of the form

+-----+ input ---| |-- input wire, assumed to be not modified by the box | | 0 |-| |--- output (was ancilla wire) +-----+

and if *f* is given by

+-----+ input ---| |-- was input 1, assumed to be not modified | | input ---| |-- was input 2, assumed to be not modified | | 0 |--| |-- output (was ancilla wire), +-----+

we can compositionally generate a circuit `C`

for *toyOracle* as follows.

+---+ +---+ input ---| |-- -----------------| |-- (output of g) | g | X +---+ | | 0 |--| |-- --| |--- ------| f |-- (output of h) +---+ | h | X | | (I) 0 |------------| |--- - ----| |-- (output of f) +---+ X +---+ 0 |- ----------- (input of g)

Note that the resulting circuit is a classical, reversible circuit
(more precisely, the circuit defines a one-to-one function). In
order to obtain a reversible quantum circuit, one should then apply
the function

to get the following (we
keep the same convention of wires as in the definition of `classical_to_reversible`

`C`

):

+---+ +---+ input--| |-----| |-- still the input | | | | 0 |--| |-----| |--| 0 | C | | D | (II) 0 |--| |--x--| |--| 0 | | | | | 0 |--| |--|--| |--| 0 +---+ | +---+ | output wire---N--------------.

Here `D`

is the inverse of `C`

. We now have a circuit of the
canonical form, computing and then uncomputing its ancillas:

+-----------+ a --| |- a | toyOracle | z --| |- z + (f (g a) (h a)) +-----------+

# A type of boolean parameters

During the construction of a quantum circuit from
classical code, the type `Bool`

is mapped to the type
`Qubit`

. However, it is also sometimes useful to specify boolean
parameters to be used during circuit generation (for example, in
the BWT algorithm, the color is a parameter). For this purpose, we
provide a new type `BoolParam`

, which is identical to `Bool`

in
most respects, except that it is not mapped to `Qubit`

during
circuit generation.

A custom-design boolean type, not modified by circuit generation.

template_PFalse :: Circ BoolParam Source #

Lifted version of PFalse.

template_PTrue :: Circ BoolParam Source #

Lifted version of PTrue.

# Lifting classical functions to circuits

The main tool for transforming a classical computation into a
quantum circuit is the function

. It inputs the
syntax tree of a classical function, and outputs the syntax tree of
a corresponding quantum circuit. The type `decToCircMonad`

`Bool`

is mapped to
`Qubit`

; the type `BoolParam`

is unchanged; and each function *f* :
*a* → *b* is mapped to a function *f'* : *a'* → `Circ`

*b'*,
where *a'* and *b'* are the translations of the types *a* and *b*,
respectively.

Most of the work is done by the lower-level function

from the module Libraries.Template.
This lower-level function knows how to deal with many usual
constructs of the Haskell language, such as function applications,
lambda-abstractions, let-assignments, case-distinctions, and so
on. However, `decToMonad`

does not by default know how to deal
with the base cases, i.e., how to extract quantum circuits from
specific term constants such as `decToMonad`

, `&&`

, etc.`||`

The purpose of the remainder of this module is to do just that. For
every constant or function `XXX`

that one may want to use in a
classical program, we provide an implementation `template_XXX`

as a
quantum circuit. We refer to `template_XXX`

as the "lifted"
version of `XXX`

. The function

is a version of
`decToCircMonad`

that knows about these liftings.`decToMonad`

decToCircMonad :: Q [Dec] -> Q [Dec] Source #

Input the syntax tree of a classical function, and output the
syntax tree of a corresponding quantum function. The type `Bool`

is
mapped to `Qubit`

; the type `BoolParam`

is unchanged; and and each
function *f* : *a* → *b* is mapped to a function *f'* : *a'* →
`Circ`

*b'*, where *a'* and *b'* are the translations of the types
*a* and *b*, respectively. The function `decToCircMonad`

knows
about many built-in operations such as

and `&&`

, whose
circuit translations are defined below.`||`

# Syntactic sugar

Quipper comes equipped with syntactic sugar to ease
the use of the

function.`decToCircMonad`

Although the code

$( decToCircMonad [d| f x = ... |] )

is valid, it is possible to use the special keyword
`build_circuit`

, as follows:

build_circuit f x = ...

This code is equivalent to

f x = ... $( decToCircMonad [d| f x = ... |] )

In other words, it generates both a function `f`

of type `a -> ...`

and an object `template_f`

of type `Circ (a -> Circ ...)`

.

The following spellings are recognized:

build_circuit f x y z = ...

build_circuit f x y z = ...

build_circuit f :: a -> ... f x y z = ...

# Circuits for specific operations

## Boolean parameters

template_newBool :: Circ (BoolParam -> Circ Qubit) Source #

Lifted version of `newBool`

:

newBool :: BoolParam -> Bool.

Depending on the boolean parameter, the circuit is either

0 |--

or

1 |--

## Boolean constants

## Unary boolean operations

## Binary boolean operations

template_symb_ampersand_symb_ampersand_ :: Circ (Qubit -> Circ (Qubit -> Circ Qubit)) Source #

Lifted version of `&&`

:

(&&) :: Bool -> Bool -> Bool.

The circuit is

a -----x--- | b -----x--- | 0 |--N------- output: a and b.

template_symb_vbar_symb_vbar_ :: Circ (Qubit -> Circ (Qubit -> Circ Qubit)) Source #

Lifted version of `||`

:

(||) :: Bool -> Bool -> Bool.

The circuit is

a -----o--- | b -----o--- | 1 |--N------- output: a or b.

template_bool_xor :: Circ (Qubit -> Circ (Qubit -> Circ Qubit)) Source #

Lifted version of `bool_xor`

:

bool_xor :: Bool -> Bool -> Bool.

The circuit is

a -----x------- | b -----|---x--- | | 0 |--N---N------ output: a xor b.

## The if-then-else operation

The last term we need to build is

, a term
describing the if-then-else construct as a circuit.`template_if`

template_if :: QData b => Circ Qubit -> Circ b -> Circ b -> Circ b Source #

Lifted version of the `if-then-else`

construction:

if-then-else :: Bool -> b -> b -> b

We only allow first-order terms in the "then" and "else" clauses. The circuit is:

q -----x---o--- | | a -----x---|--- | | b -----|---x--- | | 0 |--N---N-------- wire output of the function.

## Equality test

template_symb_equal_symb_equal_ :: QEq qa => Circ (qa -> Circ (qa -> Circ Qubit)) Source #

Lifted version of the `==`

operator:

(==) :: Eq a => a -> a -> Bool

# Generic unpacking

class CircLiftingUnpack packed unpacked | packed -> unpacked, unpacked -> packed where Source #

The `decToCircMonad`

function produces (and also requires)
functions with somewhat unwieldy types. The `CircLiftingUnpack`

class defines generic functions for unpacking these types into a
more useable format, and for packing them back.

For example,

unpacks into
the type `Circ`

(qa -> `Circ`

(qb -> `Circ`

qd))`qa -> qb -> `

.`Circ`

qd

Note that `pack`

and `unpack`

do not in general form an
isomorphism, just a retraction of the packed type onto the unpacked
type.

CircLiftingUnpack (Circ [a]) (Circ [a]) # | |

CircLiftingUnpack (Circ ()) (Circ ()) # | |

CircLiftingUnpack (Circ (a, b)) (Circ (a, b)) # | |

CircLiftingUnpack (Circ (a, b, c)) (Circ (a, b, c)) # | |

CircLiftingUnpack (Circ (a, b, c, d)) (Circ (a, b, c, d)) # | |

CircLiftingUnpack (Circ (a, b, c, d, e)) (Circ (a, b, c, d, e)) # | |

CircLiftingUnpack (Circ (a, b, c, d, e, f)) (Circ (a, b, c, d, e, f)) # | |

CircLiftingUnpack (Circ (a, b, c, d, e, f, g)) (Circ (a, b, c, d, e, f, g)) # | |

CircLiftingUnpack (Circ Qubit) (Circ Qubit) # | |

CircLiftingUnpack (Circ b) b' => CircLiftingUnpack (Circ (a -> Circ b)) (a -> b') # | |