Exact Synthesis of Clifford+T Gates

The qdecomp.utils.exact_synthesis subpackage provides a set of tools for the exact synthesis of Clifford+T gates in their corresponding sequences. Decomposable Clifford+T gates are represented as a matrix of the form:

\[\begin{split}U = \begin{bmatrix} z & -w^{\dagger}\omega^k \\ w & z^{\dagger} \omega^k \end{bmatrix},\end{split}\]

where \(z\) and \(w\) are elements in \(\mathbb{D}[\omega]\), \(\omega = e^{i \frac{\pi}{4}}\) and \(k \in \{ 0, ..., 7\}\).

Exact Synthesis Module

This module provides functionality for the exact synthesis of 2x2 unitary matrices with entries in \(\mathbb{D}[\omega]\) into sequences of H and T gates, up to a global phase. It also includes functions to characterize and generate sequences of H and T gates using the Domega class.

The algorithm is based on [Kliuchnikov et al., 2013].

This module contains the following functions:

  • exact_synthesis_alg(): Decomposes a unitary 2x2 matrix with elements in \(\mathbb{D}[\omega]\) into a sequence of H and T gates.

  • exact_synthesis_reduc(): Computes the sde reduction of a matrix with elements in \(\mathbb{D}[\omega]\) into a sequence of H and T gates and a matrix with sde \(\leq 3\).

  • s3_decomposition(): Finds the sequence of H and T gates up to a global phase to synthesize a matrix with elements in \(\mathbb{D}[\omega]\) by looking in the S3 table.

  • is_unitary_deomega(): Checks if a matrix with \(\mathbb{D}[\omega]\) elements is unitary.

  • apply_sequence(): Applies a sequence of W, H and T gates to a matrix.

  • domega_matrix_to_tuple(): Converts the first column of a 2x2 array of \(\mathbb{D}[\omega]\) elements to a tuple format.

  • get_omega_exponent(): Evaluates the phase difference between two complex numbers in terms of powers of \(\omega\)

Example:

>>> import numpy as np
>>> from qdecomp.utils.exact_synthesis import exact_synthesis_alg, ZERO_DOMEGA, ONE_DOMEGA
>>> from qdecomp.rings import Domega

# Define the X gate with 0 and 1 as Domega objects
>>> X = np.array([[ZERO_DOMEGA, ONE_DOMEGA], [ONE_DOMEGA, ZERO_DOMEGA]], dtype=Domega)

# Perform the exact synthesis
>>> sequence = exact_synthesis_alg(X)
>>> print(sequence)
HTTTTH
qdecomp.utils.exact_synthesis.exact_synthesis.exact_synthesis_alg(U: ndarray, insert_global_phase: bool = False) → str[source]

Decompose an unitary 2x2 matrix with elements in \(\mathbb{D}[\omega]\) into a sequence of H and T gates.

The algorithm is based on [Kliuchnikov et al., 2013].

Parameters:

  • U (np.ndarray) – Unitary 2x2 matrix to decompose, with elements in Domega

  • insert_global_phase (bool) – If True, insert the global phase gates (W) in the final sequence. Default is False

Returns:

Sequence of H and T (W if insert_global_phase is True) gates to decompose the matrix

Return type:

str

Raises:

  • TypeError – If matrix elements are not instances of the class Domega

  • TypeError – If the matrix is not 2x2

  • ValueError – If the matrix is not unitary

qdecomp.utils.exact_synthesis.exact_synthesis.optimize_sequence(sequence: str) → str[source]

Performs a basic optimization of a sequence of gates by removing redundant gates and combining consecutive gates.

Parameters:

sequence (str) – The input sequence of gates as a string.

Returns:

The optimized sequence of gates.

Return type:

str

Raises:

TypeError – If the input sequence is not a string.

S3 Table Generator Module

This module generates the S3 table of all Clifford+T gates with sde \(\leq 3\) and provides a utility function to help generate the table.

This module contains the following functions:

  • generate_sequences(): Generates all valid sequences of T and H gates with specific constraints (see function description).

  • generate_s3(): Generates the S3 table of Clifford+T gates with sde \(\leq 3\) and stores it in a JSON file.

qdecomp.utils.exact_synthesis.s3_generator.generate_sequences() → list[str][source]

Generate all valid sequences of T and H gates.

The sequences that are viable candidates in the S3 table are generated with the following constraints:

  • A maximum of 7 consecutive T gates.

  • A maximum of 3 H gates.

  • The sequence starts with an H gate.

Returns:

A list of strings containing the valid sequences of T and H gates.

Return type:

list[str]

qdecomp.utils.exact_synthesis.s3_generator.generate_s3() → None[source]

Generate the S3 table of all Clifford+T gates with sde \(\leq 3\) up to a global phase.

This function generates the first column of the matrix given by each string of the sequence produced by the generate_sequences() function. Each element from the matrix is stored as a tuple with eight integers required to initialize a Domega object. It stores the result in a JSON file named s3_table.json in the same directory as this script.

References

[KMM13] (1,2)

Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Fast and efficient exact synthesis of single qubit unitaries generated by clifford and t gates. Quantum Information & Computation, 2013. URL: https://arxiv.org/abs/1206.5236.