Quantum.Synthesis.CliffordT

This module provides a representation of the single-qubit Clifford+T operators, Matsumoto-Amano normal forms, and functions for the exact synthesis of single-qubit Clifford+T operators.

Matsumoto-Amano normal forms and the Matsumoto-Amano exact synthesis algorithm are described in the paper:

• Ken Matsumoto, Kazuyuki Amano. Representation of Quantum Circuits with Clifford and π/8 Gates. http://arxiv.org/abs/0806.3834.

Clifford+T interchange format

It is convenient to have a simple but exact "interchange format" for operators in the single-qubit Clifford+T group. Different operator representations can be converted to and from this format.

Our format is simply a list of gates from X, Y, Z, H, S, T, and E = HS³ω³, with the obvious interpretation as a matrix product. We also include the global phase gate W = ω = e^iπ/4. The W gate is ignored when converting to or from representations that cannot represent global phase (such as the Bloch sphere representation).

data Gate

An enumeration type to represent symbolic basic gates (X, Y, Z, H, S, T, W, E).

Note: when we use a list of Gates 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

X

Y

Z

H

S

T

E

W

Instances

Eq Gate

Show Gate

ToGates Gate

FromGates [Gate]

ShowLaTeX [Gate]

class ToGates a where

A type class for all things that can be exactly converted to a list of gates. These are the exact representations of the single-qubit Clifford+T group.

Methods

to_gates :: a -> [Gate]

Convert any suitable thing to a list of gates.

Instances

ToGates Char

ToGates Integer

ToGates Axis

ToGates Clifford

ToGates TwoLevel

ToGates Syllables

ToGates NormalForm

ToGates Gate

ToGates a => ToGates [a]

ToQOmega a => ToGates (SO3 a)

ToQOmega a => ToGates (U2 a)

class FromGates a where

A type class for all things that a list of gates can be converted to. For example, a list of gates can be converted to an element of U(2) or an element of SO(3), using various (exact or approximate) representations of the matrix entries.

Methods

from_gates :: [Gate] -> a

Convert a list of gates to any suitable type.

Instances

FromGates Integer

FromGates String

FromGates NormalForm

FromGates [Gate]

RootHalfRing a => FromGates (SO3 a)

(RootHalfRing a, ComplexRing a) => FromGates (U2 a)

invert_gates :: [Gate] -> [Gate]

Invert a gate list.

convert :: (ToGates a, FromGates b) => a -> b

Convert any precise format to any format.

Matrices in U(2) and SO(3)

Matrices in U(2)

u2_X :: Ring a => U2 a

The Pauli X operator.

u2_Y :: ComplexRing a => U2 a

The Pauli Y operator.

u2_Z :: Ring a => U2 a

The Pauli Z operator.

u2_H :: RootHalfRing a => U2 a

The Hadamard operator.

u2_S :: ComplexRing a => U2 a

The S operator.

u2_T :: OmegaRing a => U2 a

The T operator.

u2_E :: (OmegaRing a, RootHalfRing a) => U2 a

The E operator.

u2_W :: OmegaRing a => U2 a

The W = e^iπ/4 global phase operator.

u2_of_gate :: (RootHalfRing a, ComplexRing a) => Gate -> U2 a

Convert a symbolic gate to the corresponding operator.

Matrices in SO(3)

This is the Bloch sphere representation of single qubit operators.

so3_X :: Ring a => SO3 a

The Pauli X operator.

so3_Y :: Ring a => SO3 a

The Pauli Y operator.

so3_Z :: Ring a => SO3 a

The Pauli Z operator.

so3_H :: Ring a => SO3 a

The Hadamard operator.

so3_S :: Ring a => SO3 a

The operator S.

so3_E :: Ring a => SO3 a

The operator E.

so3_T :: RootHalfRing a => SO3 a

The T operator.

so3_of_gate :: RootHalfRing a => Gate -> SO3 a

Convert a symbolic gate to the corresponding Bloch sphere operator.

Conversions

so3_of_u2 :: (Adjoint a, ComplexRing a, RealPart a b, HalfRing b) => U2 a -> SO3 b

Conversion from U(2) to SO(3).

so3_of_clifford :: (ToClifford a, Ring b) => a -> SO3 b

Convert a Clifford operator to a matrix in SO(3).

clifford_of_so3 :: (Ring a, Eq a, Adjoint a) => SO3 a -> Clifford

Convert a matrix in SO(3) to a Clifford gate. Throw an error if the matrix isn't Clifford.

Matsumoto-Amano normal forms

A Matsumoto-Amano normal form is a sequence of Clifford+T operators that is of the form

• (ε | T) (HT | SHT)^* C.

Here, ε is the empty sequence, C is any Clifford operator, and the meanings of "|" and "*" are as for regular expressions. Every single-qubit Clifford+T operator has a unique Matsumoto-Amano normal form.

Representation of normal forms

data NormalForm

A representation of normal forms, optimized for right multiplication.

Constructors

NormalForm Syllables Clifford

Instances

Eq NormalForm

Show NormalForm

FromGates NormalForm

ToGates NormalForm

data Syllables

Syllables is a circuit of the form (ε|T) (HT|SHT)^*.

Constructors

S_I

The empty sequence ε.

S_T

The sequence T.

SApp_HT Syllables

A sequence of the form …HT.

SApp_SHT Syllables

A sequence of the form …SHT.

Instances

Eq Syllables

Show Syllables

ToGates Syllables

normalform_append :: NormalForm -> Gate -> NormalForm

Right-multiply the given normal form by a gate.

Group operations on normal forms

nf_id :: NormalForm

The identity as a normal form.

nf_mult :: ToGates b => NormalForm -> b -> NormalForm

Multiply two normal forms. The right factor can be any ToGates.

nf_inv :: ToGates a => a -> NormalForm

Invert a normal form. The input can be any ToGates.

Conversion to normal form

normalize :: ToGates a => a -> NormalForm

Convert any ToGates list to a NormalForm, thereby normalizing it.

Exact synthesis

Synthesis from SO(3)

synthesis_bloch :: SO3 DRootTwo -> [Gate]

Input an exact matrix in SO(3), and output the corresponding Clifford+T normal form. It is an error if the given matrix is not an element of SO(3), i.e., orthogonal with determinant 1.

This implementation uses the Matsumoto-Amano algorithm.

Note: the list of gates 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.

Synthesis from U(2)

synthesis_u2 :: U2 DOmega -> [Gate]

Input an exact matrix in U(2), and output the corresponding Clifford+T normal form. The behavior is undefined if the given matrix is not an element of U(2), i.e., unitary with determinant 1.

We use a variant of the Kliuchnikov-Maslov-Mosca algorithm, as implemented in Quantum.Synthesis.MultiQubitSynthesis.

Note: the list of gates 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.

Compact representation of normal forms

It is sometimes useful to store Clifford+T operators in a file; for this purpose, we provide a very succinct encoding of Clifford+T operators as bit strings, which are in turns represented as integers.

Our bitwise encoding is as follows. The first regular expression represents the set of Matsumoto-Amano normal forms (with a particular presentation of the rightmost Clifford operator). The second regular expression, which has the same form, defines the corresponding bit string encoding.

• (ε|T) (HT|SHT)^* (ε|H|SH) (ε|X) (ε|S²) (ε|S) (ε|ω⁴) (ε|ω²) (ε|ω)
• (10|11) (0|1)^* (00|01|10) (0|1) (0|1) (0|1) (0|1) (0|1) (0|1)

As a special case, the leading bits 10 are omitted in case the encoded operator is a Clifford operator. This ensures that the encoding of a Clifford operator is an integer from 0 to 191.

This format has the property that the encoded Clifford+T operator can, in principle, be read off directly from the hexadecimal representation of the bit string, with the following decoding:

Leftmost one or two hexadecimal digits:

  0 = n/a             4 = HT              8 = HTHT            c = THTHT
  1 = see below       5 = SHT             9 = HTSHT           d = THTSHT
  2 = ε               6 = THT             a = SHTHT           e = TSHTHT
  3 = T               7 = TSHT            b = SHTSHT          f = TSHTSHT

  10 = HTHTHT         14 = SHTHTHT        18 = THTHTHT        1c = TSHTHTHT
  11 = HTHTSHT        15 = SHTHTSHT       19 = THTHTSHT       1d = TSHTHTSHT
  12 = HTSHTHT        16 = SHTSHTHT       1a = THTSHTHT       1e = TSHTSHTHT
  13 = HTSHTSHT       17 = SHTSHTSHT      1b = THTSHTSHT      1f = TSHTSHTSHT

Central hexadecimal digit:

  0 = HTHTHTHT        4 = HTSHTHTHT       8 = SHTHTHTHT       c = SHTSHTHTHT
  1 = HTHTHTSHT       5 = HTSHTHTSHT      9 = SHTHTHTSHT      d = SHTSHTHTSHT
  2 = HTHTSHTHT       6 = HTSHTSHTHT      a = SHTHTSHTHT      e = SHTSHTSHTHT
  3 = HTHTSHTSHT      7 = HTSHTSHTSHT     b = SHTHTSHTSHT     f = SHTSHTSHTSHT

Second-to-rightmost hexadecimal digit:

  0 = ε               4 = H               8 = SH              c = n/a
  1 = SS              5 = HSS             9 = SHSS            d = n/a
  2 = X               6 = HX              a = SHX             e = n/a
  3 = XSS             7 = HXSS            b = SHXSS           f = n/a

Rightmost hexadecimal digit:

  0 = ε               4 = ω⁴              8 = S               c = Sω⁴
  1 = ω               5 = ω⁵              9 = Sω              d = Sω⁵
  2 = ω²              6 = ω⁶              a = Sω²             e = Sω⁶
  3 = ω³              7 = ω⁷              b = Sω³             f = Sω⁷

For example, the hexadecimal integer

 6bf723e31

encodes the Clifford+T operator

 THT SHTHTSHTSHT SHTSHTSHTSHT HTSHTSHTSHT HTHTSHTHT HTHTSHTSHT SHTSHTSHTHT XSS ω.

normalform_pack :: NormalForm -> Integer

Compactly encode a NormalForm as an Integer.

normalform_unpack :: Integer -> NormalForm

Decode a NormalForm from its Integer encoding. This is the inverse of normalform_pack.

clifford_pack :: Clifford -> Integer

Encode a Clifford operator as an integer in the range 0−191.

clifford_unpack :: Integer -> Clifford

Decode a Clifford operator from its integer encoding. This is the inverse of clifford_pack