Safe Haskell	None

Quipper.Libraries.ClassicalOptim.Simplification

Contents

Auxiliary definitions
Small, simple optimizations
Compression of wire numbering
A useful data structure
Algebraic optimization method
Multi-pass optimization
Orphan instances

Description

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

Synopsis

trace :: String -> b -> b
moveWire :: Wire -> Wire -> Gate -> Gate
flipCtl :: Wire -> Gate -> Gate
moveWireFlip :: Wire -> Wire -> Gate -> Gate
suppress_garbage :: [Gate] -> IntSet -> [Gate]
suppressGarbageGates :: ([Gate], [Wire]) -> ([Gate], [Wire])
getAllWires :: [Gate] -> IntSet
getInitWires :: [Gate] -> IntSet
getInputWires :: [Gate] -> IntSet
compressWires :: [Wire] -> ([Gate], [Wire]) -> ([Gate], [Wire])
type GateId = Int
type GateIdSet = IntSet
type UsedWire = IntMap GateIdSet
gateIdFindMin :: GateIdSet -> Maybe GateId
gateIdFindMax :: GateIdSet -> Maybe GateId
pairUsedWire :: UsedWire -> Wire -> GateIdSet
firstUsedWire :: UsedWire -> Wire -> Maybe GateId
lastUsedWire :: UsedWire -> Wire -> GateId
nextUsedGate :: UsedWire -> GateId -> GateId -> Wire -> GateId
circuitControlWires :: GateId -> [Gate] -> UsedWire
circuitNotWires :: GateId -> [Gate] -> UsedWire
exp_length :: Exp -> Int
exp_list_and :: [Set Exp] -> Set Exp
expEvalCtl :: IntMap (Set (Exp, Int)) -> (Wire, Bool) -> Set Exp
expEvalGate :: IntMap (Set (Exp, Int)) -> Gate -> IntMap (Set (Exp, Int))
data ExpState = ExpState {
- gates_to_skip :: IntMap Gate
- allWiresInCirc :: IntSet
- gateId :: GateId
- usedControlWires :: UsedWire
- usedNotWires :: UsedWire
- future :: [Gate]
- past :: [Gate]
- expMap :: IntMap (Set (Exp, Int))
- freshVar :: Integer
- outWires :: [Wire]
- sizeCirc :: Int
}
initExpState :: IntSet -> [Wire] -> [Gate] -> ExpState
data EvalCirc a = EvalCirc (ExpState -> (ExpState, a))
runEvalCirc :: IntSet -> [Wire] -> [Gate] -> EvalCirc a -> ExpState
getExpState :: EvalCirc ExpState
setExpState :: ExpState -> EvalCirc ()
newFreshVar :: EvalCirc Integer
pullNewGate :: EvalCirc (Maybe Gate)
changeFuture :: [Gate] -> EvalCirc ()
updateFuture :: (Gate -> Gate) -> EvalCirc (IntSet, IntSet)
storeOldGate :: Gate -> EvalCirc ()
incrGateId :: EvalCirc ()
getAllWiresInCirc :: EvalCirc IntSet
setAllWiresInCirc :: IntSet -> EvalCirc ()
removeFromAllWiresInCirc :: Int -> EvalCirc ()
getExpMap :: EvalCirc (IntMap (Set (Exp, Int)))
setExpMap :: IntMap (Set (Exp, Int)) -> EvalCirc ()
updateUsedControlWires :: (UsedWire -> UsedWire) -> EvalCirc ()
updateUsedNotWires :: (UsedWire -> UsedWire) -> EvalCirc ()
updateOutWires :: ([Wire] -> [Wire]) -> EvalCirc ()
addToSkipGates :: GateId -> Gate -> EvalCirc ()
sendEndOfTime :: Gate -> EvalCirc ()
shiftGate :: Gate -> GateId -> EvalCirc ()
pairEqualExp :: IntMap [Exp] -> IntMap [Exp] -> [Wire] -> [(Wire, Wire)]
pruneListExp :: Int -> Set (Exp, Int) -> Set (Exp, Int)
stepEvalCirc :: EvalCirc Bool
stepSwapCirc :: EvalCirc Bool
stepSwapCirc_simple :: EvalCirc Bool
runWhile :: Monad m => (a -> Bool) -> m a -> m ()
stripNoOp :: [Gate] -> [Gate]
alg_simplify :: ([Gate], [Wire]) -> ([Gate], [Wire])
alg_swap :: ([Gate], [Wire]) -> ([Gate], [Wire])
alg_swap_simple :: ([Gate], [Wire]) -> ([Gate], [Wire])
is_equal_list :: Eq a => [a] -> [a] -> Int -> (Int, Bool)
get_list_init :: [Gate] -> [Wire]
simplRec' :: ([Gate], [Wire]) -> ([Gate], [Wire])
simplRec :: ([Gate], [Wire]) -> ([Gate], [Wire])

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 IDs.

type GateIdSet = IntSet Source #

A set of gate IDs.

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 IDs.

gateIdFindMax :: GateIdSet -> Maybe GateId Source #

Get the maximum of a set of gate IDs.

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

gates_to_skip :: IntMap Gate
For use with stepSwapCirc.
allWiresInCirc :: IntSet
All the wires in the circuit.
gateId :: GateId
ID of the first gate in the future (starts at 1).
usedControlWires :: UsedWire
Location of the controls.
usedNotWires :: UsedWire
Location 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 :: Integer
The next fresh wire.
outWires :: [Wire]
The output wires.
sizeCirc :: Int
Size of the circuit.

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 #
Instance details Defined in Quipper.Libraries.ClassicalOptim.Simplification Methods (>>=) :: EvalCirc a -> (a -> EvalCirc b) -> EvalCirc b # (>>) :: EvalCirc a -> EvalCirc b -> EvalCirc b # return :: a -> EvalCirc a # fail :: String -> EvalCirc a #
Functor EvalCirc #
Instance details Defined in Quipper.Libraries.ClassicalOptim.Simplification Methods fmap :: (a -> b) -> EvalCirc a -> EvalCirc b # (<$) :: a -> EvalCirc b -> EvalCirc a #
Applicative EvalCirc #
Instance details Defined in Quipper.Libraries.ClassicalOptim.Simplification Methods pure :: a -> EvalCirc a # (<>) :: EvalCirc (a -> b) -> EvalCirc a -> EvalCirc b # liftA2 :: (a -> b -> c) -> EvalCirc a -> EvalCirc b -> EvalCirc c # (>) :: 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.