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

An index for a row or column of a matrix.

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.

Invert a TwoLevel operator.

Invert a list of TwoLevel operators.

Construct a two-level matrix with the given entries.

Construct a one-level matrix with the given entry.

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

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.

Replace the ith element of a list by x.

Apply a unary operator to element i of a list.

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

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

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

Multiply a scalar by ωⁿ.

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

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

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

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

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}.

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.

Row reduction: Given a unit column vector v, generate a sequence of two-level operators that reduces the ith standard basis vector e_i to v. Any rows that are already 0 in both vectors are guaranteed not to be touched.

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.

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.

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.

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 e_i 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.

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.