Quipper.Internal.CircLifting

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 Quipper.Utils.Template.

Technically, the only functions to be used in this module are decToCircMonad, a specialized version of decToMonad, and unpack. The only useful datatype here is 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-- 

Overview

Using the tool decToMonad designed in Quipper.Utils.Template, we can easily generate quantum circuits. Indeed, suppose that we are given the classical oracle

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 classical_to_reversible to get the following (we keep the same convention of wires as in the definition of 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.

data BoolParam

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

Constructors

PTrue

PFalse

Instances

Eq BoolParam

Defined in Quipper.Internal.CircLifting

Methods

(==) :: BoolParam -> BoolParam -> Bool

(/=) :: BoolParam -> BoolParam -> Bool

Show BoolParam

Defined in Quipper.Internal.CircLifting

Methods

showsPrec :: Int -> BoolParam -> ShowS

show :: BoolParam -> String

showList :: [BoolParam] -> ShowS

newBool :: BoolParam -> Bool

Type-cast from BoolParam to Bool

template_PFalse :: Circ BoolParam

Lifted version of PFalse.

template_PTrue :: Circ BoolParam

Lifted version of PTrue.

Lifting classical functions to circuits

The main tool for transforming a classical computation into a quantum circuit is the function decToCircMonad. It inputs the syntax tree of a classical function, and outputs the syntax tree of a corresponding quantum circuit. The type 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 decToMonad from the module Quipper.Utils.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 &&, ||, 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 decToCircMonad is a version of decToMonad that knows about these liftings.

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

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 decToCircMonad function.

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)

Lifted version of newBool:

newBool :: BoolParam -> Bool.

Depending on the boolean parameter, the circuit is either

0 |--

or

1 |--

Boolean constants

template_False :: Circ Qubit

Lifted version of False:

False :: Bool.

The circuit is

0 |--   output: quantum bit in state |0>

template_True :: Circ Qubit

Lifted version of True:

True :: Bool.

The circuit is

1 |--   output: quantum bit in state |1>

Unary boolean operations

template_not :: Circ (Qubit -> Circ Qubit)

Lifted version of not:

not :: Bool -> Bool.

The circuit is

a -----x--
       |
  1 |--N------- output: not a.

Binary boolean operations

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

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

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

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 template_if, a term describing the if-then-else construct as a circuit.

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

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

Lifted version of the == operator:

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

Generic unpacking

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

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, Circ (qa -> Circ (qb -> Circ qd)) unpacks into the type 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.

Methods

unpack :: packed -> unpacked

pack :: unpacked -> packed

Instances

CircLiftingUnpack (Circ [a]) (Circ [a])

Defined in Quipper.Internal.CircLifting

Methods

unpack :: Circ [a] -> Circ [a]

pack :: Circ [a] -> Circ [a]

CircLiftingUnpack (Circ ()) (Circ ())

Defined in Quipper.Internal.CircLifting

Methods

unpack :: Circ () -> Circ ()

pack :: Circ () -> Circ ()

CircLiftingUnpack (Circ (a, b)) (Circ (a, b))

Defined in Quipper.Internal.CircLifting

Methods

unpack :: Circ (a, b) -> Circ (a, b)

pack :: Circ (a, b) -> Circ (a, b)

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

Defined in Quipper.Internal.CircLifting

Methods

unpack :: Circ (a, b, c) -> Circ (a, b, c)

pack :: Circ (a, b, c) -> Circ (a, b, c)

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

Defined in Quipper.Internal.CircLifting

Methods

unpack :: Circ (a, b, c, d) -> Circ (a, b, c, d)

pack :: Circ (a, b, c, d) -> Circ (a, b, c, d)

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

Defined in Quipper.Internal.CircLifting

Methods

unpack :: Circ (a, b, c, d, e) -> Circ (a, b, c, d, e)

pack :: 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))

Defined in Quipper.Internal.CircLifting

Methods

unpack :: Circ (a, b, c, d, e, f) -> Circ (a, b, c, d, e, f)

pack :: 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))

Defined in Quipper.Internal.CircLifting

Methods

unpack :: Circ (a, b, c, d, e, f, g) -> Circ (a, b, c, d, e, f, g)

pack :: Circ (a, b, c, d, e, f, g) -> Circ (a, b, c, d, e, f, g)

CircLiftingUnpack (Circ Qubit) (Circ Qubit)

Defined in Quipper.Internal.CircLifting

Methods

unpack :: Circ Qubit -> Circ Qubit

pack :: Circ Qubit -> Circ Qubit

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

Defined in Quipper.Internal.CircLifting

Methods

unpack :: Circ (a -> Circ b) -> a -> b'

pack :: (a -> b') -> Circ (a -> Circ b)