The Quipper System

Safe HaskellNone

QuipperLib.ClassicalOptim.Simplification

Contents

Description

This module contains the core of the classical circuit optimization algorithm.

Synopsis

Auxiliary definitions

trace :: String -> b -> b Source #

Internal definition of a trace, for debugging purposes. This is a no-op, but can be replaced to turn on debugging.

moveWire :: Wire -> Wire -> Gate -> Gate Source #

Change a wire ID in a gate. The first two arguments are the old and the new wire ID.

flipCtl :: Wire -> Gate -> Gate Source #

Flip the control on the given wire (from positive to negative or vice versa).

moveWireFlip :: Wire -> Wire -> Gate -> Gate Source #

Change a wire ID in a gate and flip the potential control.

Small, simple optimizations

suppress_garbage :: [Gate] -> IntSet -> [Gate] Source #

Suppress gates acting on garbage wires, i.e., wires that are not in the input set.

suppressGarbageGates :: ([Gate], [Wire]) -> ([Gate], [Wire]) Source #

Like suppress_garbage, but packaged in a manner that is friendly for composition.

Compression of wire numbering

As the optimization process goes on, many init gates will end up being discarded. The function compressWires compacts the wire numbering scheme to make a smaller circuit.

getAllWires :: [Gate] -> IntSet Source #

Get the set of all wires used by the circuit.

getInitWires :: [Gate] -> IntSet Source #

Get the set of wires initialized by the circuit.

getInputWires :: [Gate] -> IntSet Source #

Get the set of input wires, i.e., the ones that are used but not initialized.

compressWires :: [Wire] -> ([Gate], [Wire]) -> ([Gate], [Wire]) Source #

Compress the wire numbering.

A useful data structure

When considering a particular point in a circuit (i.e., in a list of gates), to decide whether a given wire is used or controlled before or after, we keep a data-structure UsedWire.

type GateId = Int Source #

The type of gate ID's.

type GateIdSet = IntSet Source #

A set of gate ID's.

type UsedWire = IntMap GateIdSet Source #

A map from wires to pairs of GateIds. The left member gives the ID of the first gate using the wire, and the right member gives the ID of the last gate using the wire.

gateIdFindMin :: GateIdSet -> Maybe GateId Source #

Get the minimum of a set of gate ID's.

gateIdFindMax :: GateIdSet -> Maybe GateId Source #

Get the maximum of a set of gate ID's.

pairUsedWire :: UsedWire -> Wire -> GateIdSet Source #

Get the pair corresponding to the given wire.

firstUsedWire :: UsedWire -> Wire -> Maybe GateId Source #

Get the first gate using the wire in the future.

lastUsedWire :: UsedWire -> Wire -> GateId Source #

Get the last gate using the wire in the past. Return 0 if none.

nextUsedGate :: UsedWire -> GateId -> GateId -> Wire -> GateId Source #

nextUsedGate ws g g' w: Look for the next gate in ws corresponding to wire w, starting from g. Return g' if none.

circuitControlWires :: GateId -> [Gate] -> UsedWire Source #

For each wire, find the set of gates placing a control on it.

circuitNotWires :: GateId -> [Gate] -> UsedWire Source #

For each wire, find the set of gates acting on it with NOT.

Algebraic optimization method

To each wire in a circuit, we attach a set of formulas. At each iteration, the wire that gets modified is updated with its new value, using all the possible values, possibly together with a fresh variable. At each iteration, we also strip away the expressions that get too large. Here, the size of an algebraic expression is measured by the exp_length function.

exp_length :: Exp -> Int Source #

Calculate the size of an algebraic expression.

exp_list_and :: [Set Exp] -> Set Exp Source #

Given a list of sets of expressions, form the conjunction of every possible choice of one expression from each set. For example.

exp_list_and [{a,b}, {c,d}, {e,f}] = 
    [a∧c∧e, a∧c∧f, a∧d∧e, a∧d∧f, b∧c∧e, b∧c∧f, b∧d∧e, b∧d∧f].

expEvalCtl :: IntMap (Set (Exp, Int)) -> (Wire, Bool) -> Set Exp Source #

Evaluate a control with respect to a state.

expEvalGate :: IntMap (Set (Exp, Int)) -> Gate -> IntMap (Set (Exp, Int)) Source #

Evaluate a gate with respect to a state.

State of the optimization automaton

data ExpState Source #

The state of the automaton. This contains in particular the current state, the past and future gates, and a fresh variable.

Constructors

ExpState 

Fields

initExpState :: IntSet -> [Wire] -> [Gate] -> ExpState Source #

The initial state for a given set of parameters.

The state monad

data EvalCirc a Source #

The state monad corresponding to ExpState.

Constructors

EvalCirc (ExpState -> (ExpState, a)) 

Instances

Monad EvalCirc # 

Methods

(>>=) :: EvalCirc a -> (a -> EvalCirc b) -> EvalCirc b #

(>>) :: EvalCirc a -> EvalCirc b -> EvalCirc b #

return :: a -> EvalCirc a #

fail :: String -> EvalCirc a #

Functor EvalCirc # 

Methods

fmap :: (a -> b) -> EvalCirc a -> EvalCirc b #

(<$) :: a -> EvalCirc b -> EvalCirc a #

Applicative EvalCirc # 

Methods

pure :: a -> EvalCirc a #

(<*>) :: EvalCirc (a -> b) -> EvalCirc a -> EvalCirc b #

(*>) :: EvalCirc a -> EvalCirc b -> EvalCirc b #

(<*) :: EvalCirc a -> EvalCirc b -> EvalCirc a #

Low-level access functions

runEvalCirc :: IntSet -> [Wire] -> [Gate] -> EvalCirc a -> ExpState Source #

Construct an ExpState out of an EvalCirc.

getExpState :: EvalCirc ExpState Source #

Retrieve the state.

setExpState :: ExpState -> EvalCirc () Source #

Set the state.

Higher-level access functions

newFreshVar :: EvalCirc Integer Source #

Create a fresh variable

pullNewGate :: EvalCirc (Maybe Gate) Source #

Pull a new gate to be analyzed out of the future.

changeFuture :: [Gate] -> EvalCirc () Source #

Modify the future gates.

updateFuture :: (Gate -> Gate) -> EvalCirc (IntSet, IntSet) Source #

Update the future using the given parameter function. Return two sets of gateIds that got modified: the first set concerns the controls, the second set the NOT gates.

storeOldGate :: Gate -> EvalCirc () Source #

Store a gate in the past.

incrGateId :: EvalCirc () Source #

Increase the '@gateId@' (i.e., go forward).

getAllWiresInCirc :: EvalCirc IntSet Source #

Get the set of all wires.

setAllWiresInCirc :: IntSet -> EvalCirc () Source #

Set the set of all wires.

removeFromAllWiresInCirc :: Int -> EvalCirc () Source #

Remove a gate from the set of all wires.

getExpMap :: EvalCirc (IntMap (Set (Exp, Int))) Source #

Get the algebraic representation of the set of wires.

setExpMap :: IntMap (Set (Exp, Int)) -> EvalCirc () Source #

Set the algebraic representation of the state of wires.

updateUsedControlWires :: (UsedWire -> UsedWire) -> EvalCirc () Source #

Update the database recording the controlled wires.

updateUsedNotWires :: (UsedWire -> UsedWire) -> EvalCirc () Source #

Update the database recording the NOT gates.

updateOutWires :: ([Wire] -> [Wire]) -> EvalCirc () Source #

Update the list of output wires.

addToSkipGates :: GateId -> Gate -> EvalCirc () Source #

Add a gate ID to the list of gates to skip.

sendEndOfTime :: Gate -> EvalCirc () Source #

Send a gate to the end of the future.

shiftGate :: Gate -> GateId -> EvalCirc () Source #

Place a gate at the given gate ID in the future.

Auxiliary functions

pairEqualExp :: IntMap [Exp] -> IntMap [Exp] -> [Wire] -> [(Wire, Wire)] Source #

pairEqualExp m1 m2 ws: returns a list of pairs of wires (x,y) such that m2 x = m1 x = m1 y.

pruneListExp :: Int -> Set (Exp, Int) -> Set (Exp, Int) Source #

From a set of expressions (annotated with sizes), prune the ones whose size is larger than n.

The algebraic optimization automaton

stepEvalCirc :: EvalCirc Bool Source #

Perform a set of filters acting on one gate at a time, looking for:

  • gates having no effect;
  • orphan NOT-gates (i.e. NOT gates negating an out-wire) ;
  • simple copy-cats (both positive and negative) ;
  • hidden copy-cats.

Return False when the end of the circuit is reached, True otherwise.

stepSwapCirc :: EvalCirc Bool Source #

Shuffle the circuit by sending the CNOT gates as far as possible (i.e., until they hit a control, or to the end). Return False when the end of the circuit is reached, True otherwise.

stepSwapCirc_simple :: EvalCirc Bool Source #

A more elementary version of stepSwapCirc: shuffle the circuit by sending to the end all the NOT gates that can be sent there. Return False when the end of the circuit is reached, True otherwise.

Some wrappers

runWhile :: Monad m => (a -> Bool) -> m a -> m () Source #

Run the monad until False occurs.

stripNoOp :: [Gate] -> [Gate] Source #

Strip the NoOp gates from a list of gates.

alg_simplify :: ([Gate], [Wire]) -> ([Gate], [Wire]) Source #

Wrapper around stepEvalCirc.

alg_swap :: ([Gate], [Wire]) -> ([Gate], [Wire]) Source #

Wrapper around stepSwapCirc.

alg_swap_simple :: ([Gate], [Wire]) -> ([Gate], [Wire]) Source #

Wrapper around stepSwapCirc_simple.

Multi-pass optimization

is_equal_list :: Eq a => [a] -> [a] -> Int -> (Int, Bool) Source #

Auxiliary function. Simultaneously compute the maximum of the lengths of two lists, and their point-wise equality.

get_list_init :: [Gate] -> [Wire] Source #

Get the list of initialized wires from a circuit.

simplRec' :: ([Gate], [Wire]) -> ([Gate], [Wire]) Source #

Do several passes of alg_simplify until it reaches a fixed point.

simplRec :: ([Gate], [Wire]) -> ([Gate], [Wire]) Source #

Do several passed of alg_swap followed with simplRec until it reaches a fixed point.

Orphan instances

NFData Gate # 

Methods

rnf :: Gate -> ()