newsynth-0.2: Exact and approximate synthesis of quantum circuits

Quantum.Synthesis.MultiQubitSynthesis

Description

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.

Synopsis

# Residues

class Residue a b | a -> b whereSource

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 ℤ2.

Methods

residue :: a -> bSource

Return the residue of something.

Instances

 Residue Integer Z2 Residue () () Residue a b => Residue [a] [b] Residue a b => Residue (Omega a) (Omega b) Residue a b => Residue (Cplx a) (Cplx b) Residue a b => Residue (RootTwo a) (RootTwo b) (Residue a a', Residue b b') => Residue (a, b) (a', b') Residue a b => Residue (Vector n a) (Vector n b) Residue a b => Residue (Matrix m n a) (Matrix m n b)

# One- and two-level operators

## Symbolic representation

type Index = IntSource

An index for a row or column of a matrix.

data TwoLevel Source

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 Xi,j. TL_H Index Index Hi,j. TL_T Int Index Index (Ti,j)k. TL_omega Int Index (ωi)k.

Instances

 Eq TwoLevel Show TwoLevel ToGates TwoLevel ShowLaTeX TwoLevel ShowLaTeX [TwoLevel]

Invert a `TwoLevel` operator.

invert_twolevels :: [TwoLevel] -> [TwoLevel]Source

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 aSource

Construct a two-level matrix with the given entries.

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

Construct a one-level matrix with the given entry.

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

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

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

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]Source

Replace the ith element of a list by x.

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

Apply a unary operator to element i of a list.

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

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

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

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

# Functions on ℤ[ω]

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

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

Multiply a scalar by ωn.

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

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

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

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

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]Source

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]Source

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

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

Constructors

 RT_0000 RT_0001 RT_1010

Instances

 Eq ResidueType Ord ResidueType

Return the residue's `ResidueType`.

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.

Return the residue's `ResidueType` and the shift.

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.

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]Source

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]Source

Row reduction: Given a unit column vector v, generate a sequence of two-level operators that reduces the ith standard basis vector ei 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]Source

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.

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 iXi,j. TL_TiHT Int Index Index (T−m(iH)Tm)i,j. TL_W Int Index Index Wmi,j. TL_omega_alt Int Index (ωi)m.

Instances

 Eq TwoLevelAlt Show TwoLevelAlt

Convert from the alternate generators to the original generators.

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]Source

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.

Row reduction: Given a unit column vector v, generate a sequence of two-level operators that reduces the ith standard basis vector ei 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]Source

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.