The Quipper System

QuipperLib.ClassicalOptim.Simplification

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.

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

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.

A set of gate ID's.

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.

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

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

Get the pair corresponding to the given wire.

Get the first gate using the wire in the future.

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

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

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.

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&#8743;c&#8743;e, a&#8743;c&#8743;f, a&#8743;d&#8743;e, a&#8743;d&#8743;f, b&#8743;c&#8743;e, b&#8743;c&#8743;f, b&#8743;d&#8743;e, b&#8743;d&#8743;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 Fieldsgates_to_skip :: IntMap GateFor use with stepSwapCirc.allWiresInCirc :: IntSetAll the wires in the circuit.gateId :: GateIdID of the first gate in the future (starts at 1).usedControlWires :: UsedWireLocation of the controls.usedNotWires :: UsedWireLocation of the NOT gates.future :: [Gate]Gates left to explore.past :: [Gate]Gates already explored.expMap :: IntMap (Set (Exp, Int))Algebraic state of the wires. Also contains the size of the expression, so we don't have to recompute it each time.freshVar :: IntegerThe next fresh wire.outWires :: [Wire]The output wires.sizeCirc :: IntSize of the circuit.

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

The initial state for a given set of parameters.

data EvalCirc a Source #

The state monad corresponding to ExpState.

Constructors

 EvalCirc (ExpState -> (ExpState, a))

Instances

 # Methods(>>=) :: EvalCirc a -> (a -> EvalCirc b) -> EvalCirc b #(>>) :: EvalCirc a -> EvalCirc b -> EvalCirc b #return :: a -> EvalCirc a #fail :: String -> EvalCirc a # # Methodsfmap :: (a -> b) -> EvalCirc a -> EvalCirc b #(<\$) :: a -> EvalCirc b -> EvalCirc a # # Methodspure :: 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.

Retrieve the state.

Set the state.

Higher-level access functions

Create a fresh variable

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.

Store a gate in the past.

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

Get the set of all wires.

Set the set of all wires.

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.

Update the database recording the controlled wires.

Update the database recording the NOT gates.

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

Update the list of output wires.

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

Send a gate to the end of the future.

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

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.

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.

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 # Methodsrnf :: Gate -> ()