Quantum.Synthesis.MultiQubitSynthesis

This module provides functions for the representation and exact synthesis of multi-qubit Clifford+T operators.

The multi-qubit Clifford+T exact synthesis algorithm is described in the paper:

• Brett Giles, Peter Selinger. Exact synthesis of multiqubit Clifford+T circuits. Physical Review A 87, 032332 (7 pages), 2013. Available from http://arxiv.org/abs/1212.0506.

It generalizes the single-qubit exact synthesis algorithm of Kliuchnikov, Maslov, and Mosca.

Residues

class Residue a b | a -> b where

A type class for things that have residues. In a typical instance, a is a ring whose elements are expressed with coefficients in ℤ, and b is a corresponding ring whose elements are expressed with coefficients in ℤ₂.

Minimal complete definition

residue

Methods

residue :: a -> b

Return the residue of something.

Instances

Residue Integer Z2

Methods

residue :: Integer -> Z2

Residue () ()

Methods

residue :: () -> ()

Residue a b => Residue [a] [b]

Methods

residue :: [a] -> [b]

Residue a b => Residue (Omega a) (Omega b)

Methods

residue :: Omega a -> Omega b

Residue a b => Residue (Cplx a) (Cplx b)

Methods

residue :: Cplx a -> Cplx b

Residue a b => Residue (RootTwo a) (RootTwo b)

Methods

residue :: RootTwo a -> RootTwo b

(Residue a a', Residue b b') => Residue (a, b) (a', b')

Methods

residue :: (a, b) -> (a', b')

Residue a b => Residue (Vector n a) (Vector n b)

Methods

residue :: Vector n a -> Vector n b

Residue a b => Residue (Matrix m n a) (Matrix m n b)

Methods

residue :: Matrix m n a -> Matrix m n b

One- and two-level operators

Symbolic representation

type Index = Int

An index for a row or column of a matrix.

data TwoLevel

Symbolic representation of one- and two-level operators. Note that the power k in the TL_T and TL_omega constructors can be positive or negative, and should be regarded modulo 8.

Note: when we use a list of TwoLevel operators to express a sequence of operators, the operators are meant to be applied right-to-left, i.e., as in the mathematical notation for matrix multiplication. This is the opposite of the quantum circuit notation.

Constructors

TL_X Index Index

X_i,j.

TL_H Index Index

H_i,j.

TL_T Int Index Index

(T_i,j)^k.

TL_omega Int Index

(ω_i)^k.

Instances

Eq TwoLevel

Methods

(==) :: TwoLevel -> TwoLevel -> Bool

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

Show TwoLevel

Methods

showsPrec :: Int -> TwoLevel -> ShowS

show :: TwoLevel -> String

showList :: [TwoLevel] -> ShowS

ToGates TwoLevel

Methods

to_gates :: TwoLevel -> [Gate]

ShowLaTeX TwoLevel

Methods

showlatex :: TwoLevel -> String

showlatex_p :: Int -> TwoLevel -> ShowS

ShowLaTeX [TwoLevel]

Methods

showlatex :: [TwoLevel] -> String

showlatex_p :: Int -> [TwoLevel] -> ShowS

invert_twolevel :: TwoLevel -> TwoLevel

Invert a TwoLevel operator.

invert_twolevels :: [TwoLevel] -> [TwoLevel]

Invert a list of TwoLevel operators.

Constructors for two-level matrices

twolevel_matrix :: (Ring a, Nat n) => (a, a) -> (a, a) -> Index -> Index -> Matrix n n a

Construct a two-level matrix with the given entries.

onelevel_matrix :: (Ring a, Nat n) => a -> Index -> Matrix n n a

Construct a one-level matrix with the given entry.

matrix_of_twolevel :: (ComplexRing a, RootHalfRing a, Nat n) => TwoLevel -> Matrix n n a

Convert a symbolic one- or two-level operator into a matrix.

matrix_of_twolevels :: (ComplexRing a, RootHalfRing a, Nat n) => [TwoLevel] -> Matrix n n a

Convert a list of symbolic one- or two-level operators into a matrix. Note that the operators are to be applied right-to-left, exactly as in mathematical notation.

Auxiliary list functions

list_insert :: Index -> a -> [a] -> [a]

Replace the ith element of a list by x.

transform_at :: (a -> a) -> Index -> [a] -> [a]

Apply a unary operator to element i of a list.

transform_at2 :: ((a, a) -> (a, a)) -> Index -> Index -> [a] -> [a]

Apply a binary operator to elements i and j of a list.

list_pairs :: [a] -> ([(a, a)], Maybe a)

Split a list into pairs. Return a list of pairs, and a final element if the length of the list was odd.

Functions on ℤ[ω]

log_omega :: ZOmega -> Maybe Int

Given an element of the form ω^m, return m ∈ {0,…,7}, or Nothing if not of that form.

omega_power :: OmegaRing a => Int -> a -> a

Multiply a scalar by ωⁿ.

reduce_ZOmega :: ZOmega -> ZOmega

Divide an element of ZOmega by √2, or throw an error if it is not divisible.

opX_zomega :: (ZOmega, ZOmega) -> (ZOmega, ZOmega)

Apply the X operator to a 2-dimensional vector over ZOmega.

opH_zomega :: (ZOmega, ZOmega) -> (ZOmega, ZOmega)

Apply the H operator to a 2-dimensional vector over ZOmega. This throws an error if the result is not well-defined over ZOmega.

apply_twolevel_zomega :: TwoLevel -> [ZOmega] -> [ZOmega]

Apply a TwoLevel operator to a ZOmega-vector, represented as a list. Throws an error if any operation produces a scalar that is not in ZOmega.

apply_twolevels_zomega :: [TwoLevel] -> [ZOmega] -> [ZOmega]

Apply a list of TwoLevel operators to a ZOmega-vector, represented as a list. Throws an error if any operation produces a scalar that is not in ZOmega.

Functions on residues

data ResidueType

The residue type of t ∈ ℤ[ω] is the residue of t^†t. It is 0000, 0001, or 1010.

Constructors

RT_0000

RT_0001

RT_1010

Instances

Eq ResidueType

Methods

(==) :: ResidueType -> ResidueType -> Bool

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

Ord ResidueType

Methods

compare :: ResidueType -> ResidueType -> Ordering

(<) :: ResidueType -> ResidueType -> Bool

(<=) :: ResidueType -> ResidueType -> Bool

(>) :: ResidueType -> ResidueType -> Bool

(>=) :: ResidueType -> ResidueType -> Bool

max :: ResidueType -> ResidueType -> ResidueType

min :: ResidueType -> ResidueType -> ResidueType

residue_type :: Omega Z2 -> ResidueType

Return the residue's ResidueType.

residue_shift :: Omega Z2 -> Int

Return the residue's shift.

The shift is defined so that:

• 0001, 1110, 0011 have shift 0,
• 0010, 1101, 0110 have shift 1,
• 0100, 1011, 1100 have shift 2, and
• 1000, 0111, 1001 have shift 3.

Residues of type RT_0000 have shift 0.

residue_type_shift :: Omega Z2 -> (ResidueType, Int)

Return the residue's ResidueType and the shift.

residue_offset :: Omega Z2 -> Omega Z2 -> Int

Given two irreducible residues a and b of the same type, find an index m such that a + ω^mb = 0000. If no such index exists, find an index m such that a + ω^mb = 1111.

reducible :: Omega Z2 -> Bool

Check whether a residue is reducible. A residue r is called reducible if it is of the form r = √2 ⋅ r', i.e., r ∈ {0000, 0101, 1010, 1111}.

Exact synthesis

row_step :: ((Index, Omega Z2, ZOmega), (Index, Omega Z2, ZOmega)) -> [TwoLevel]

Perform a single row operation as in Lemma 4, applied to rows i and j. The entries at rows i and j are x and y, respectively, with respective residues a and b. A precondition is that x and y are of the same residue type. Returns a list of two-level operations that decreases the denominator exponent.

reduce_column :: Nat n => Matrix n One DOmega -> Index -> [TwoLevel]

Row reduction: Given a unit column vector v, generate a sequence of two-level operators that reduces the ith standard basis vector e_i to v. Any rows that are already 0 in both vectors are guaranteed not to be touched.

synthesis_nqubit :: Nat n => Matrix n n DOmega -> [TwoLevel]

Input an exact n×n unitary operator with coefficients in D[ω], and output an equivalent sequence of two-level operators. This is the algorithm from the Giles-Selinger paper. It has superexponential complexity.

Note: the list of TwoLevel operators will be returned in right-to-left order, i.e., as in the mathematical notation for matrix multiplication. This is the opposite of the quantum circuit notation.

Alternative algorithm

Section 6 of the Giles-Selinger paper mentions an alternate version of the decomposition algorithm. It requires no ancillas, provided that the determinant of the operator permits this.

data TwoLevelAlt

Symbolic representation of one- and two-level operators, with an alternate set of generators.

Note: when we use a list of TwoLevel operators to express a sequence of operators, the operators are meant to be applied right-to-left, i.e., as in the mathematical notation for matrix multiplication. This is the opposite of the quantum circuit notation.

Constructors

TL_iX Index Index

iX_i,j.

TL_TiHT Int Index Index

(Tsuper −/m/T^m)_i,j.

TL_W Int Index Index

W^m_i,j.

TL_omega_alt Int Index

(ω_i)^m.

Instances

Eq TwoLevelAlt

Methods

(==) :: TwoLevelAlt -> TwoLevelAlt -> Bool

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

Show TwoLevelAlt

Methods

showsPrec :: Int -> TwoLevelAlt -> ShowS

show :: TwoLevelAlt -> String

showList :: [TwoLevelAlt] -> ShowS

twolevels_of_twolevelalts :: [TwoLevelAlt] -> [TwoLevel]

Convert from the alternate generators to the original generators.

invert_twolevels_alt :: [TwoLevelAlt] -> [TwoLevel]

Invert a list of TwoLevelAlt operators, and convert the output to a list of TwoLevel operators.

row_step_alt :: ((Index, Omega Z2, ZOmega), (Index, Omega Z2, ZOmega)) -> [TwoLevelAlt]

Perform a single row operation as in Lemma 4, applied to rows i and j, using the generators of Section 6. The entries at rows i and j are x and y, respectively, with respective residues a and b. A precondition is that x and y are of the same residue type. Returns a list of two-level operations that decreases the denominator exponent.

reduce_column_alt :: Nat n => Matrix n One DOmega -> Index -> [TwoLevelAlt]

Row reduction: Given a unit column vector v, generate a sequence of two-level operators that reduces the ith standard basis vector e_i to v. Any rows that are already 0 in both vectors are guaranteed not to be touched, except possibly row i+1 may be multiplied by a scalar.

synthesis_nqubit_alt :: Nat n => Matrix n n DOmega -> [TwoLevelAlt]

Input an exact n×n unitary operator with coefficients in D[ω], and output an equivalent sequence of two-level operators (in the alternative generators, where all but at most one of the generators has determinant 1). This is the algorithm from the Giles-Selinger paper, Section 6. It has superexponential complexity.

Note: the list of TwoLevelAlt operators will be returned in right-to-left order, i.e., as in the mathematical notation for matrix multiplication. This is the opposite of the quantum circuit notation.