newsynth-0.2: Exact and approximate synthesis of quantum circuits

Safe HaskellNone

Quantum.Synthesis.MultiQubitSynthesis

Contents

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.

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 ℤ[ω]

log_omega :: ZOmega -> Maybe IntSource

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.

reduce_ZOmega :: ZOmega -> ZOmegaSource

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

data ResidueType Source

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

Constructors

RT_0000 
RT_0001 
RT_1010 

residue_type :: Omega Z2 -> ResidueTypeSource

Return the residue's ResidueType.

residue_shift :: Omega Z2 -> IntSource

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

Return the residue's ResidueType and the shift.

residue_offset :: Omega Z2 -> Omega Z2 -> IntSource

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 -> BoolSource

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.

data TwoLevelAlt Source

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

(Tm(iH)Tm)i,j.

TL_W Int Index Index

Wmi,j.

TL_omega_alt Int Index

i)m.

twolevels_of_twolevelalts :: [TwoLevelAlt] -> [TwoLevel]Source

Convert from the alternate generators to the original generators.

invert_twolevels_alt :: [TwoLevelAlt] -> [TwoLevel]Source

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.

reduce_column_alt :: Nat n => Matrix n One DOmega -> Index -> [TwoLevelAlt]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, 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.