Grid Problem Solver

The qdecomp.utils.grid_problem subpackage provides a set of tools for solving grid problems.

Grid Algorithms Module

The grid_algorithms module contains functions to solve 1D and 2D grid problems.

The module provides two main functions:

• solve_grid_problem_1d(): Given two real closed intervals A and B, solve_grid_problem_1d() finds all the solutions x in the ring of quadratic integers with radicand 2, \(\mathbb{Z}[\sqrt{2}]\), such that x is in A and the \(\sqrt{2}\)-conjugate of x is in B. This function is a sub-algorithm to solve 2D grid problems for upright rectangles.

• solve_grid_problem_2d(): Given two upright rectangles A and B in the complex plane, solve_grid_problem_2d() finds all the solutions x in the ring of cyclotomic integers with radicand 2, \(\mathbb{Z}[\omega]\), such that x is in A and the \(\sqrt{2}\)-conjugate of x is in B. The solutions are used as candidates for unitary matrix entries in the Clifford+T approximation of z-rotation gates.

For more information on solving 1D and 2D grid problems, see [Ross and Selinger, 2014].

qdecomp.utils.grid_problem.grid_algorithms.solve_grid_problem_1d(A: Sequence[Real] | ndarray[tuple[Any, ...], dtype[_ScalarT]], B: Sequence[Real] | ndarray[tuple[Any, ...], dtype[_ScalarT]]) → Generator[Zsqrt2]

Solve the 1-dimensional grid problem for two intervals and return the result.

Given two real closed sets A and B, this function finds all the solutions x in the ring \(\mathbb{Z}[\sqrt{2}]\) such that x is in A and the \(\sqrt{2}\)-conjugate of x is in B.

Parameters:

• A (Sequence[Real, Real]) – (A0, A1): Bounds of the first interval.

• B (Sequence[Real, Real]) – (B0, B1): Bounds of the second interval.

Returns:

A generator of all solutions to the grid problem. The solutions are given as Zsqrt2 objects.

Return type:

Generator[Zsqrt2]

Raises:

TypeError – If intervals A and B are not real sequences of length 2.

qdecomp.utils.grid_problem.grid_algorithms.solve_grid_problem_2d(A: Sequence[Sequence[Real]] | ndarray[tuple[Any, ...], dtype[_ScalarT]], B: Sequence[Sequence[Real]] | ndarray[tuple[Any, ...], dtype[_ScalarT]]) → Generator[Zomega]

Solve the 2-dimensional grid problem for two upright rectangles and return the result.

Given two real 2D closed sets A and B of the form [a, b] x [c, d], find all the solutions x in the ring \(\mathbb{Z}[\omega]\) such that x is in A and the \(\sqrt{2}\)-conjugate of x is in B.

Parameters:

• A (Sequence[Sequence[Real, Real]]) – [(A0, A1), (A2, A3)]: Bounds of the first upright rectangle. Rows correspond to the x and y axis respectively.

• B (Sequence[Sequence[Real, Real]]) – [(B0, B1), (B2, B3)]: Bounds of the second upright rectangle. Rows correspond to the x and y axis respectively.

Returns:

A generator of all solutions to the grid problem. The solutions are given as Zomega objects.

Return type:

Generator[Zomega]

Raises:

TypeError – If intervals A and B are not real 2 x 2 nested sequences.

Grid Operator Class

This module defines the GridOperator.

Grid operators are a central concept introduced in Section 5.3 of [Ross and Selinger, 2014]. However, this class is generalized to work with any matrix whose elements lie in the ring \(D[\sqrt{2}]\).

To efficiently solve a general 2D grid problem, it is necessary to find the upright bounding box of the regions of interest, since grid problems can only be solved on upright rectangular domains. It is important to asses how closely this upright rectangle conforms to the shape inside it. The uprightness of an arbitrary shape \(A\) is defined as follows:

\[Up(A) = \frac{\text{area}(A)}{\text{area}(BBox(A))}.\]

This is an important tool to evaluate how well a bounding box represents its corresponding shape.

Since the input error \(\varepsilon\) is small and the width of the slice \(\mathcal{R}_\epsilon\) is proportional to \(\epsilon^2\), solving the grid problem on the bounding box of this slice is extremely inefficient, because \(Up(\mathcal{R}_\varepsilon) \to 0\). To solve this issue, grid operators can be introduced.

A grid operator \(G\) is such that for \(u \in \mathbb{Z}[\omega]\), \(G(u) \in \mathbb{Z}[\omega]\). Moreover, if \(\det(G) = \pm 1\), then \(G\) is called a special grid operator. Grid operators are extremely useful for solving grid problems on arbitrary shapes, because if \(G\) is a special grid operator, then the problem

\[\text{Find } G(u) \in G(\mathcal{R}_\varepsilon) \text{ such that } (G(u))^\bullet \in G^\bullet (\bar{\mathcal{D}}),\]

is equivalent to the initial problem.

Furthermore, if we define \(E\) as the smallest ellipse that encapsulates \(\mathcal{R}_\varepsilon\), then there exists a special grid operator \(G\), such that:

\[Up(G(E)) \geq \frac{1}{6}, \quad Up(G^\bullet (\bar{\mathcal{D}})) \geq \frac{1}{6}.\]

This class defines grid operators, which will be useful in the grid problem algorithm as a whole.

For more information on the use of states, see Section 5.3 of [Ross and Selinger, 2014].

class qdecomp.utils.grid_problem.grid_operator.GridOperator(G: ndarray)

Bases: object

Class to represent a grid operator used in solving grid problems over the complex plane.

A grid operator is a linear (though not continuous) transformation of the complex plane that preserves the grid structure defined by the ring \(\mathbb{D}[\omega]\). These operators are instrumental in improving the efficiency of grid problem algorithms.

In particular, grid problems typically involve searching for solutions within narrow, non-rectangular regions of the complex plane. Since grid problems can only be solved efficiently over upright rectangular domains, applying a grid operator allows us to widen and reshape these regions into more tractable forms, thus enabling more effective enumeration of solutions.

Grid operators are discussed in detail in Section 5.3 of [Ross and Selinger, 2014].

Parameters:

G (np.ndarray) – ndarray form of the grid operator

__init__(G: ndarray) → None

Initialize the object with a 2x2 numpy array.

Parameters:

• G (list | np.ndarray) – A 4-element flat list, a 2x2 nested list, or a 2x2 numpy.ndarray

• Dsqrt2. (containing elements of type)

Raises:

• ValueError – If G is not a 4-element flat list, a 2x2 nested list, or a 2x2 array.

• TypeError – If elements of G are not of valid types.

• ValueError – If G is not 2x2 in size.

det() → int | D | Zsqrt2 | Dsqrt2

Compute the determinant of the grid operator.

Returns:

The determinant of the grid operator, depending on the types of its elements.

Return type:

int | D | Zsqrt2 | Dsqrt2

dag() → GridOperator

Compute the hermitian conjugate of the grid operator.

Returns:

A new grid operator that is the hermitian conjugate of the current one.

Return type:

GridOperator

conjugate()

Define the conjugation of the grid operator

inv() → GridOperator

Return the inverse of the grid operator.

The inversion is defined only for grid operators with determinant ±1.

Returns:

The inverse of the current grid operator.

Return type:

GridOperator

Raises:

ValueError – If the determinant is 0, or not equal to ±1.

as_float() → ndarray

Return a float-valued approximation of the grid operator matrix.

Returns:

A 2x2 NumPy array with float entries corresponding to the grid operator.

Return type:

np.ndarray

as_mpfloat() → ndarray

Return a high-precision float (mpmath) representation of the grid operator matrix.

Returns:

A 2x2 NumPy array with entries converted to mpmath floating-point values.

Return type:

np.ndarray

State Class

This file defines the State class, which is a key component in solving the grid problem. Specifically, it is used to ensure that the uprightness of the ellipse pair is augmented to at least 1/6.

For more information on the use of states, see appendix A of [Ross and Selinger, 2014].

class qdecomp.utils.grid_problem.state.State(A: ndarray, B: ndarray)

Bases: object

Class to initialize a state given a pair of 2×2 matrices.

A state is of the form \((A, B)\), where both \(A\) and \(B\) are 2×2 real matrices with determinant 1. These matrices correspond to ellipses, with the matrices encoding the dimensions and orientation of each ellipse.

This class is based on Appendix A of [Ross and Selinger, 2014], and is used in the context of achieving at least 1/6 uprightness for both ellipses associated with a state.

Parameters:

• A (np.ndarray) – First matrix of the state.

• B (np.ndarray) – Second matrix of the state.

• z (float) – Exponent of \(\lambda\) in A.

• zeta (float) – Exponent of \(\lambda\) in B.

• e (float) – Diagonal component of A.

• epsilon (float) – Diagonal component of B.

• b (float) – Antidiagonal component of A.

• beta (float) – Antidiagonal component of B.

__init__(A: ndarray, B: ndarray) → None

Initialize the state class.

Parameters:

• A (np.ndarray) – First matrix of the class.

• B (np.ndarray) – Second matrix of the class.

Raises:

• TypeError – If A or B cannot be converted to a numpy array.

• TypeError – If the elements of A or B are not mp.mpf.

• ValueError – If A or B are not 2x2 matrices.

• ValueError – If A or B are not symmetric matrices.

property z: float

Exponent of \(\lambda\) and \(\lambda^{-1}\) for the first matrix of the state.

Returns:

The exponent \(z\) computed from the diagonal entries of matrix \(A\).

Return type:

float

property zeta: float

Exponent of \(\lambda\) and \(\lambda^{-1}\) for the second matrix of the state.

Returns:

The exponent \(z\) computed from the diagonal entries of matrix \(B\).

Return type:

float

property e: float

Diagonal elements of the first matrix of the state.

Returns:

The diagonal component \(e\) of matrix \(A\).

Return type:

float

property epsilon: float

Diagonal elements of the second matrix of the state.

Returns:

The diagonal component \(\epsilon\) of matrix \(B\).

Return type:

float

property b: float

Anti-diagonal elements of the first matrix of the state.

Returns:

The anti-diagonal component \(b\) of matrix \(A\).

Return type:

float

property beta: float

Anti-diagonal elements of the second matrix of the state.

Returns:

The anti-diagonal component \(\beta\) of matrix \(B\).

Return type:

float

property skew: float

Compute the skew of the state.

The skew measures how upright the ellipses of the state are. A higher skew indicates lower uprightness.

Returns:

The skew value \(b^2 + \beta^2\).

Return type:

float

property bias: float

Compute the bias of the state.

The bias measures how difficult it is to reduce the skew. To reduce the skew in a quantifiable manner, the bias must be between -1 and 1.

Returns:

The bias value \(\zeta - z\).

Return type:

float

transform(G: GridOperator) → State

Apply a grid operator to the state.

This computes the transformation of both ellipses in the state under the action of a given grid operator \(G\). The operator acts on the first matrix \(A\) and its conjugate acts on the second matrix \(B\).

Parameters:

G (GridOperator) – The grid operator to apply to the state.

Returns:

The transformed state after applying the grid operator.

Return type:

State

shift(k: int) → State

Apply the shift operation by an integer \(k\) to the state.

This operation adjusts the bias of the state while preserving its skew. It is used to bring the bias into a desired range (e.g., between -1 and 1) without affecting how upright the ellipses are.

Parameters:

k (int) – The shift amount. A positive value increases the bias, while a negative value decreases it.

Returns:

The shifted state with the same skew and adjusted bias.

Return type:

State

Raises:

ValueError – If k is not an integer.

Grid Problem Solver Module

This module provides the function find_points() to find the three points that define the slice \(\mathcal{R}_\varepsilon\) as described in Section 7.2 of [Ross and Selinger, 2014]. It also includes the find_grid_operator() function to find the grid operator that reduces the skew of a state to less than 15, as well as the find_special_grid_operator() function to find the special grid operator that reduces the skew by at least 10%. The functions utilize the mpmath library for high precision arithmetic and the numpy library for numerical operations.

The procedure to reduce the skew of a state is based on the algorithm described in Annexes A and B of [Ross and Selinger, 2014].

For more information on the use of states, see Annex A and B of [Ross and Selinger, 2014].

qdecomp.utils.grid_problem.grid_problem.find_points(theta: float, epsilon: float) → tuple[ndarray, ndarray, ndarray]

Find the three points which define the slice \(\mathcal{R}_\varepsilon\) as shown in Section 7.2 of [Ross and Selinger, 2014].

Parameters:

• theta (float) – The angle \(\theta\) such that \(0 \leq \theta < 4\pi\) corresponding to the \(R_z\) gate.

• epsilon (float) – The error \(\varepsilon\) of the approximation of \(R_z\).

Returns:

A tuple containing three points \((p_1, p_2, p_3)\), where:

• p1 (np.ndarray): The origin point \([\cos(\theta / 2), \sin(\theta / 2)]\).

• p2 (np.ndarray): The first computed point on the slice.

• p3 (np.ndarray): The second computed point on the slice.

Return type:

tuple

Raises:

• ValueError – If \(\theta \notin [0, 4\pi]\).

• ValueError – If \(\varepsilon \geq 0.5\).

• TypeError – If either \(\theta\) or \(\varepsilon\) cannot be converted to floats.

qdecomp.utils.grid_problem.grid_problem.find_grid_operator(A: ndarray, B: ndarray) → tuple[GridOperator, GridOperator]

Find the grid operator which reduces the skew of a state to less than 15.

Parameters:

• A (np.ndarray) – The 2x2 matrix defining the first ellipse.

• B (np.ndarray) – The 2x2 matrix defining the second ellipse.

Returns:

The resulting grid operator that satisfies the initial criteria.

Return type:

grid_op (GridOperator)

Raises:

• TypeError – If A or B are not of type np.ndarray or convertable to it.

• ValueError – If A or B are not 2x2 matrices or are incompatible with the State class.

qdecomp.utils.grid_problem.grid_problem.find_special_grid_operator(state: State) → GridOperator

Find the special grid operator which reduces the skew of a state by at least 10%.

Parameters:

state (State) – The state defined by a pair of ellipses.

Returns:

The resulting special grid operator that satisfies the initial criteria.

Return type:

special_grid_operator (GridOperator)

Raises:

ValueError – If the algorithm encountered unaccounted-for values of z and zeta

Z-Rotational Approximation Module

This file runs the entire z-rotational approximation algorithm to find the associated sequence.

It contains the initialization() function, which is only to visually lighten the code and the z_rotational_approximation() function which is the main function of this file. Given an angle and an error, it finds an approximation of the associated z-rotation by solving for potential values of u, and then checking if there exists a valid associated value for t using the Diophantine equation module. When u and t are found, it returns the Clifford+T approximation of the z-rotation.

qdecomp.utils.grid_problem.rz_approx.initialization(theta: float, epsilon: float) → tuple[ndarray, ndarray]

Initializes important parameters necessary to find the appropriate Rz approximation.

This function calculates points based on the angle and the error provided, finds the necessary ellipse, and determines grid operators and bounding boxes for further computations.

Parameters:

• theta (float) – Angle of the z-rotational gate.

• epsilon (float) – Maximum allowable error.

Returns:

A tuple containing:

• bbox_1 (tuple): Bounding box coordinates for the transformed ellipse.

• bbox_2 (tuple): Bounding box coordinates for the transformed unit disk.

Return type:

tuple

qdecomp.utils.grid_problem.rz_approx.z_rotational_approximation(theta: float, epsilon: float) → ndarray

Finds the z-rotational approximation up to an error \(\varepsilon\).

This function finds an approximation of a z-rotational inside the Clifford+T group.

Parameters:

• theta (float) – Angle \(\theta\) of the z-rotational gate.

• epsilon (float) – Maximum allowable error \(\varepsilon\).

Returns:

Approximation \(M\) of a z-rotational inside the Clifford+T subset.

Return type:

np.ndarray

Raises:

• ValueError – If \(\theta\) is not in the range \([0, 4\pi]\).

• ValueError – If \(\varepsilon \geq 0.5\).

• ValueError – If \(\theta\) or \(\varepsilon\) cannot be converted to floats.

References

[RS14] (1,2,3,4,5,6,7,8,9,10)

N. J. Ross and P. Selinger. Optimal ancilla-free clifford+t approximation of z-rotations. Quantum Information & Computation, 2014. URL: https://arxiv.org/abs/1403.2975.