!5p      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w xyz{|}~Safe)newsynth'We provide a replacement for Haskell's %, because the latter depends on the ( class, which limits its applicability.SafeMnewsynthA axis is either I, H, or SH. newsynthrA type class for things that can be exactly converted to a Clifford operator. One particular instance of this is 3, so that Clifford operators can be denoted, e.g., to_clifford "-iX"5The valid characters for such string conversions are  "XYZHSEIWi-". newsynth2Convert any suitable thing to a Clifford operator. newsynth4A type representing single-qubit Clifford operators. newsynth The Pauli X-gate as a Clifford operator. newsynth The Pauli Y-gate as a Clifford operator.newsynth The Pauli Z-gate as a Clifford operator.newsynth)The Hadamard gate as a Clifford operator.newsynthThe Clifford operator S.newsynthThe Clifford operator SH.newsynthThe Clifford operator E = HSI[sup 3][sup 3]. This operator is uniquely determined by the properties E = I, EXE { = Y, EYE { = Z, and EZE { = X. [image E.png]newsynthThe Clifford operator  = [exp i/4].newsynthGiven a Clifford operator U , return (a, b, c, d ) such thatU = E[sup a]X[sup b]S[sup c][sup d],a " {0, 1, 2}, b " {0, 1}, c " {0, &, 3}, and d " {0, &, 7}.Here, E = HSup 3][sup 3]. Note that E, X, Sy, and  have order 3, 2, 4, and 8, respectively. Moreover, each Clifford operator can be uniquely represented as above.newsynthGiven a Clifford operator U , return (K, b, c, d ) such thatU = KX[sup b]S[sup c][sup d],K " {I, H, SH}, b " {0, 1}, c " {0, &, 3}, and d " {0, &, 7}.newsynthThe identity Clifford operator.newsynthClifford multiplication.newsynthClifford inverse.newsynthGiven a Clifford gate C, return an axis K " {I, H, SH} and a Clifford gate C' such thatCT = KTC'. newsynth  c b returns (c', d ') such thatS[sup c]X[sup b] = X[sup b]S[sup c'][sup d']. newsynth  b c a returns (a', b', c', d ') such thatX[sup b]S[sup c]E[sup a] = E[sup a']X[sup b']S[sup c'][sup d']. newsynth  a b c returns (a', b', c', d ') such that(E[sup a]X[sup b]S[sup c]) { = E[sup a']X[sup b']S[sup c'][sup d']. newsynth  a b returns (K, c, d ) such thatE[sup a]X[sup b]T = KTX[sup b]S[sup c][sup d].   None ,=?@ACM>N#newsynth)A type class for things that have parity.$newsynthReturn the parity of something.%newsynth>A type class for things that can be exactly converted to ![].&newsynthConversion to 1.'newsynthA type class for things from which a common power of 1/"2 (a least denominator exponent) can be factored out. Typical instances are @, 9;, as well as tuples, lists, vectors, and matrices thereof.(newsynth)Calculate the least denominator exponent k of a. Returns the smallest k "e0 such that a = b/"2[sup k] for some integral b.)newsynth Factor out a kth power of 1/"2 from a. In other words, calculate a"2[sup k].*newsynth_A type class for rings that have a distinguished subring "of integers". A typical instance is a = @ , which has b = A as its ring of integers.+newsynth;The embedding of the ring of integers into the larger ring.,newsynthThe inverse of +O. Throws an error if the given element is not actually an integer in the ring.-newsynthLA type class for rings that have a "real" component. A typical instance is a = 9 with b = @..newsynthTake the real part./newsynthEA type class relating "rational" types to their dyadic counterparts.0newsynthgConvert a "rational" value to a "dyadic" value, if the denominator is a power of 2. Otherwise, return  .1newsynthThe field ![] of cyclotomic rationals of degree 8.2newsynthThe ring [bold D][]. Here [bold D]=!$[] is the ring of dyadic fractions. In fact, [bold D][] is isomorphic to the ring [bold D]["2, i], but they have different  instances.3newsynthThe ring !$[] of cyclotomic integers of degree 8. Such rings were first studied by Kummer around 1840, and used in his proof of special cases of Fermat's Last Theorem. See also: Rhttp://fermatslasttheorem.blogspot.com/2006/05/basic-properties-of-cyclotomic.html Ghttp://fermatslasttheorem.blogspot.com/2006/02/cyclotomic-integers.html_Harold M. Edwards, "Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory".4newsynth The ring R [], where RE is any ring, and  = [exp i/4] is an 8th root of unity. The value 4 a b c d represents a [sup 3]+b [sup 2]+c+d.6newsynth0Single precision complex floating point numbers.7newsynth0Double precision complex floating point numbers.8newsynthThe field !["2, i].9newsynthThe ring [bold D]["2, i ] = !$[1/"2, i].:newsynth The ring ![i] of Gaussian rationals.;newsynthThe ring [bold D][i ] = !$[, i] of Gaussian dyadic fractions.<newsynth The ring !$[i] of Gaussian integers.=newsynth The ring R[i ], where R, is any ring. The reason we do not use the  a` type from the standard Haskell libraries is that it assumes too much, for example, it assumes a is a member of the 8 class. Also, this allows us to define a more sensible  instance.?newsynthThe field !["2].@newsynth!The ring [bold D]["2] = !$[1/"2]. AnewsynthThe ring !$["2].Bnewsynth The ring R ["2], where R is any ring. The value B a b represents a + b "2.Dnewsynth[We define our own variant of the rational numbers, which is an identical copy of the type H from the standard Haskell library, except that it has a more sensible  instance.Gnewsynth}A dyadic fraction is a rational number whose denominator is a power of 2. We denote the dyadic fractions by [bold D] = !$[].*We internally represent a dyadic fraction a/2[sup n] as a pair (a,n). Note that this representation is not unique. When it is necessary to choose a canonical representative, we choose the least possible n"e0.Inewsynth"The ring !$ of integers modulo 2. LnewsynthThe  and  functions provided by the standard Haskell libraries are predicated on many unnecessary assumptions. This type class provides an alternative.Minimal complete definition: M or N.MnewsynthCompute the floor of x, i.e., the greatest integer n such that n "d x.NnewsynthCompute the ceiling of x, i.e., the least integer n such that x "d n.OnewsynthA (number-theoretic) norm on a ring R is a function N : R ! !$ such that N(rs) = N(r)N(s ), for all r, s " R. The norm also satisfies N(r ) = 0 iff r = 0, and N(r ) = 1 iff r is a unit of the ring.QnewsynthXA type class for rings with a "2-conjugation, i.e., an automorphism mapping "2 to ""2. TWhen instances of this type class are vectors or matrices, the "2-conjugation does not( exchange the roles of rows and columns.WFor rings that have no "2, the conjugation can be defined to be the identity function.RnewsynthCompute the adjoint, mapping a + b"2 to a "b"2.SnewsynthPA type class for rings with complex conjugation, i.e., an automorphism mapping i to "i. When instances of this type class are vectors or matrices, the conjugation also exchanges the roles of rows and columns (in other words, it is the adjoint).\For rings that are not complex, the conjugation can be defined to be the identity function.Tnewsynth2Compute the adjoint (complex conjugate transpose).Unewsynth5A type class for rings that contain a square root of i(, or equivalently, a fourth root of "1.VnewsynthThe square root of i.Wnewsynth8A type class for rings that contain a square root of -1.XnewsynthThe complex unit.Ynewsynth)A type class for rings that contain 1/"2.Minimal complete definition: Z. The default definition of [ uses the expression  x+roottwo*yl. However, this can give potentially bad round-off errors for fixed-precision types, where the expression  roottwo*y can be vastly inaccurate if yC is large. For such rings, one should provide a custom definition.ZnewsynthThe square root of .[newsynthThe unique ring homomorphism from [bold D]["2] to any ring containing 1/"2. This exists because [bold D]["2] = !$[1/"2] is the free such ring.\newsynth'A type class for rings that contain "2.Minimal complete definition: ]. The default definition of ^ uses the expression  x+roottwo*yl. However, this can give potentially bad round-off errors for fixed-precision types, where the expression  roottwo*y can be vastly inaccurate if yC is large. For such rings, one should provide a custom definition.]newsynthThe square root of 2.^newsynthtThe unique ring homomorphism from !$["2] to any ring containing "2. This exists because !$["2] is the free such ring._newsynth&A type class for rings that contain .Minimal complete definition: `. The default definition of a uses the expression a*half^nk. However, this can give potentially bad round-off errors for fixed-precision types where the expression half^n^ can underflow. For such rings, one should provide a custom definition, for example by using a/2^n instead.`newsynth The value .anewsynth.The unique ring homomorphism from !$[] to any _(. This exists because !$[] is the free _.bnewsynth&A type class to denote rings. We make b a synonym of Haskell's 4 type class, so that we can use the usual notation , , I for the ring operations. This is not a perfect fit, because Haskell's . class also contains two non-ring operations  and j. By convention, for rings where these notions don't make sense (or are inconvenient to define), we set  x = x and  x = 1.cnewsynthGiven a dyadic fraction r , return (a,n ) such that r = a/2[sup n ], where n""e0 is chosen as small as possible.dnewsynthGiven a dyadic fraction r and an integer k"e0, such that a = r2[sup k] is an integer, return a. If a/ is not an integer, the behavior is undefined.enewsynthpAn auxiliary function for printing rational numbers, using correct precedences, and omitting denominators of 1.fnewsynthConversion from D to any  type.gnewsynthTReturn a square root of an element of !$["2], if such a square root exists, or else  .hnewsynthThe unique ring homomorphism from !["2] to any ring containing the rational numbers and "2. This exists because !["2] is the free such ring.inewsynth$The unique ring homomorphism from !$[i] to any ring containing i. This exists because !$[i] is the free such ring.jnewsynth+The unique ring homomorphism from [bold D][i ] to any ring containing and i. This exists because [bold D][i] is the free such ring.knewsynth$The unique ring homomorphism from ![i3] to any ring containing the rational numbers and i. This exists because ![i] is the free such ring.lnewsynth/The unique ring homomorphism from [bold D]["2, i#] to any ring containing 1/"2 and i#. This exists because [bold D]["2, i ] = !$[1/"2, i] is the free such ring.mnewsynth(The unique ring homomorphism from !["2, i8] to any ring containing the rational numbers, "2, and i. This exists because !["2, i] is the free such ring.nnewsynthAn inverse to the embedding R ! R=[]: return the "real rational" part. In other words, map a [sup 3]+b [sup 2]+c+d to d.onewsynthqThe unique ring homomorphism from !$[] to any ring containing . This exists because !$[] is the free such ring.pnewsynthInverse of the embedding !$["2] ! !$[]. Note that !$["2] = !$[] ") !. This function takes an element of !$[] that is real, and converts it to an element of !$["2]. It throws an error if the input is not real.qnewsynthThe unique ring homomorphism from [bold D][] to any ring containing  and 1/2. This exists because [bold D][] is the free such ring.rnewsynthThe unique ring homomorphism from ![] to any ring containing the rational numbers and . This exists because ![] is the free such ring.snewsynthoConvert a "rational" value to a "dyadic" value, if the denominator is a power of 2. Otherwise, throw an error.tnewsynth8Calculate and factor out the least denominator exponent k of a . Return (b,k ), where a = b /("2)[sup k] and k"e0.unewsynthGeneric =-like method that factors out a common denominator exponent.vnewsynth^Return the position of the rightmost "1" bit of an Integer, or -1 if none. Do this in time O(n log n ), where n) is the size of the integer (in digits).wnewsynthIf n is of the form 2[sup k ], return k. Otherwise, return  .xnewsynthCReturn 1 + the position of the leftmost "1" bit of a non-negative . Do this in time O(n log n ), where n) is the size of the integer (in digits).ynewsynthFor n- "e 0, return the floor of the square root of nJ. This is done using integer arithmetic, so there are no rounding errors.W#$%&')(*,+-./0123456789:;<=>?@ABCDEFGHIKJLNMOPQRSTUVWXY[Z\^]_a`bcdefghijklmnopqrstuvwxyWb_a`\^]Y[ZWXUVSTQROPLNMIKJGHcdDEFefBCAg@?h=><i;j:k9l8m7645n3op2q1r/0s-.*,+')(tu%&#$vwxyNone&'=>?@AHUVXjSnewsynth7A convenient abbreviation for the type of 33-matrices.newsynth7A convenient abbreviation for the type of 22-matrices.newsynthAn mn-matrix is a list of n& columns, each of which is a list of mU scalars. The type of square matrices of any fixed dimension is an instance of the b3 class, and therefore the usual symbols, such as "" and "G" can be used on them. However, the non-square matrices, the symbols """ and ")" must be used.newsynthVector n a is the type of lists of length n with elements from a. We call this a "vector" rather than a tuple or list for two reasons: the vectors are homogeneous (all elements have the same type), and they are strict: if any one component is undefined, the whole vector is undefined.newsynth-Multiplication of type-level natural numbers.newsynth'Addition of type-level natural numbers.newsynth^A type class for the natural numbers. The members are exactly the type-level natural numbers.newsynthTReturn a term-level natural number corresponding to this type-level natural number.newsynthReturn a term-level integer corresponding to this type-level natural number. The argument is just a dummy argument and is not evaluated.newsynth6A data type for the natural numbers. Specifically, if n& is a type-level natural number, then NNat n7is a singleton type containing only the natural number n.newsynth]The 10th successor of a natural number type. For example, the natural number 18 as a type is  Ten_and Eightnewsynth The natural number 10 as a type.newsynthThe natural number 9 as a type.newsynthThe natural number 8 as a type.newsynthThe natural number 7 as a type.newsynthThe natural number 6 as a type.newsynthThe natural number 5 as a type.newsynthThe natural number 4 as a type. newsynthThe natural number 3 as a type. newsynthThe natural number 2 as a type. newsynthThe natural number 1 as a type. newsynth'Type-level representation of successor. newsynth"Type-level representation of zero.newsynth Convert an  to an .newsynthConstruct a vector of length 1.newsynthReturn the length of a vector. Since this information is contained in the type, the vector argument is never evaluated and can be a dummy (undefined) argument.newsynth0Convert a fixed-length list to an ordinary list.newsynthZip two equal length lists.newsynth(Map a function over a fixed-length list.newsynthCreate the vector (0, 1, &, n-1).newsynthCreate the vector (f(0), f(1), &, f(n-1)).newsynthConstruct a vector from a list. Note: since the length of the vector is a type-level integer, it cannot be inferred from the length of the input list; instead, it must be specified explicitly in the type. It is an error to apply this function to a list of the wrong length.newsynth Return the i`th element of the vector. Counting starts from 0. Throws an error if the index is out of range.newsynthTReturn a fixed-length list consisting of a repetition of the given element. Unlike , no count is needed, because this information is already contained in the type. However, the type must of course be inferable from the context.newsynth+Turn a list of columns into a list of rows.newsynth*Left strict fold over a fixed-length list.newsynth$Right fold over a fixed-length list.newsynthaReturn the tail of a fixed-length list. Note that the type system ensures that this never fails.newsynthaReturn the head of a fixed-length list. Note that the type system ensures that this never fails.newsynthAppend two fixed-length lists.newsynth Version of  for fixed-length lists. newsynth*Decompose a matrix into a list of columns.!newsynthReturn the size (m, n) of a matrix, where m is the number of rows, and n is the number of columns. Since this information is contained in the type, the matrix argument is not evaluated and can be a dummy (undefined) argument."newsynth Addition of mn,-matrices. We use a special symbol because mn#-matrices do not form a ring; only nn9-matrices form a ring (in which case the normal symbol "" also works).#newsynthSubtraction of mn,-matrices. We use a special symbol because mn#-matrices do not form a ring; only nn9-matrices form a ring (in which case the normal symbol "" also works).$newsynth1Map some function over every element of a matrix.%newsynthCreate the matrix whose i,j -entry is (i,j). Here i and j0 are 0-based, i.e., the top left entry is (0,0).&newsynthCreate the matrix whose i,j -entry is f i j. Here i and j* are 0-based, i.e., the top left entry is f 0 0.'newsynth"Multiplication of a scalar and an mn-matrix.(newsynthDivision of an mn-matrix by a scalar.)newsynthMultiplication of mn,-matrices. We use a special symbol because mn#-matrices do not form a ring; only nn9-matrices form a ring (in which case the normal symbol "" also works).*newsynth+Return the 0 matrix of the given dimension.+newsynthTake the transpose of an mn-matrix.,newsynthTake the adjoint of an mn-matrix. Unlike T., this can be applied to non-square matrices.-newsynthReturn the element in the i th row and jtth column of the matrix. Counting of rows and columns starts from 0. Throws an error if the index is out of range..newsynthSReturn a list of all the entries of a matrix, in some fixed but unspecified order./newsynth Version of  for matrices.0newsynth$Return the trace of a square matrix.1newsynth5Return the square of the Hilbert-Schmidt norm of an mn-matrix, defined by M  = tr M[sup ]M.2newsynthStack matrices vertically.3newsynthStack matrices horizontally.4newsynth@Repeat a matrix vertically, according to some vector of scalars.5newsynth,Vertically concatenate a vector of matrices.6newsynthBRepeat a matrix horizontally, according to some vector of scalars.7newsynth.Horizontally concatenate a vector of matrices.8newsynth!Kronecker tensor of two matrices.9newsynthForm a diagonal block matrix.:newsynthForm a controlled gate.;newsynthOA convenience constructor for matrices: turn a list of columns into a matrix. Note: since the dimensions of the matrix are type-level integers, they cannot be inferred from the dimensions of the input; instead, they must be specified explicitly in the type. It is an error to apply this function to a list of the wrong dimension.<newsynthKA convenience constructor for matrices: turn a list of rows into a matrix.Note: since the dimensions of the matrix are type-level integers, they cannot be inferred from the dimensions of the input; instead, they must be specified explicitly in the type. It is an error to apply this function to a list of the wrong dimension.=newsynthA synonym for <.>newsynth%Turn a matrix into a list of columns.?newsynth"Turn a matrix into a list of rows.@newsynthGA convenience constructor for 22-matrices. The arguments are by rows.AnewsynthAA convenience destructor for 22-matrices. The result is by rows.BnewsynthGA convenience constructor for 33-matrices. The arguments are by rows.CnewsynthGA convenience constructor for 44-matrices. The arguments are by rows.Dnewsynth;A convenience constructor for 3-dimensional column vectors.EnewsynthSA convenience destructor for 3-dimensional column vectors. This is the inverse of D.FnewsynthDA convenience constructor for turning a vector into a column matrix.GnewsynthControlled-not gate.Hnewsynth Swap gate.InewsynthA z-rotation gate, R sub /z/ = [exp "iZ/2].X      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIX      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHI5"6#6'7(7)7None&'@AC^,bnewsynth^Symbolic representation of one- and two-level operators, with an alternate set of generators.Note: when we use a list of k 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.cnewsynthiX[sub i,j].dnewsynth(T iH super "/m/T[super m])[sub i,j].enewsynthW[super m][sub i,j].fnewsynth([sub i ])[super m].gnewsynthThe  residue type of t " !$[] is the residue of t[sup ]t. It is 0000, 0001, or 1010.knewsynthNSymbolic representation of one- and two-level operators. Note that the power k in the n and oL constructors can be positive or negative, and should be regarded modulo 8.Note: when we use a list of k 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.lnewsynthX[sub i,j].mnewsynthH[sub i,j].nnewsynth(T[sub i,j ])[super k].onewsynth([sub i ])[super k].pnewsynth)An index for a row or column of a matrix.qnewsynthDA type class for things that have residues. In a typical instance, aE is a ring whose elements are expressed with coefficients in !$, and bU is a corresponding ring whose elements are expressed with coefficients in !$[sub 2].rnewsynth Return the residue of something.snewsynth Invert a k operator.tnewsynthInvert a list of k operators.unewsynth4Construct a two-level matrix with the given entries.vnewsynth2Construct a one-level matrix with the given entry.wnewsynth<Convert a symbolic one- or two-level operator into a matrix.xnewsynthConvert 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.ynewsynth Replace the ith element of a list by x.znewsynth"Apply a unary operator to element i of a list.{newsynth$Apply a binary operator to elements i and j of a list.|newsynthhSplit a list into pairs. Return a list of pairs, and a final element if the length of the list was odd.}newsynth#Given an element of the form [sup m ], return m " {0, &,7}, or   if not of that form.~newsynthMultiply a scalar by [sup n].newsynthDivide an element of 32 by "2, or throw an error if it is not divisible.newsynth Apply the X) operator to a 2-dimensional vector over 3.newsynth Apply the H* operator to a 2-dimensional vector over 3?. This throws an error if the result is not well-defined over 3.newsynthApply a k operator to a 3d-vector, represented as a list. Throws an error if any operation produces a scalar that is not in 3.newsynthApply a list of k operators to a 3d-vector, represented as a list. Throws an error if any operation produces a scalar that is not in 3.newsynthReturn the residue's g.newsynthReturn 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, and1000, 0111, 1001 have shift 3.Residues of type h have shift 0.newsynthReturn the residue's g and the shift.newsynthGiven two irreducible residues a and b" of the same type, find an index m such that a + [sup m]b1 = 0000. If no such index exists, find an index m such that a + [sup m]b = 1111.newsynth0Check 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}.newsynth>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 yo are of the same residue type. Returns a list of two-level operations that decreases the denominator exponent.newsynth*Row reduction: Given a unit column vector v?, generate a sequence of two-level operators that reduces the ith standard basis vector e[sub i] to vP. Any rows that are already 0 in both vectors are guaranteed not to be touched.newsynthInput an exact nn unitary operator with coefficients in [bold 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 k 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.newsynthAConvert from the alternate generators to the original generators.newsynthInvert a list of b1 operators, and convert the output to a list of k operators.newsynth>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 yp are of the same residue type. Returns a list of two-level operations that decreases the denominator exponent.newsynth*Row reduction: Given a unit column vector v?, generate a sequence of two-level operators that reduces the ith standard basis vector e[sub i] to vf. 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.newsynthInput an exact nn6 unitary operator with coefficients in [bold 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 b 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./bfedcgjihkonmlpqrstuvwxyz{|}~/qrpkonmlstuvwxyz{|}~gjihbfedcNone҃newsynthDecompose a unitary operator UC into Euler angles (, , , ). These angles are computed so thatU = [exp i ] R[sub z ]() R[sub x ]() R[sub z]().newsynthCompute the operatorU = [exp i ] R[sub z ]() R[sub x ]() R[sub z]().from the given Euler angles.None=?newsynthzA type class for Euclidean domains. A Euclidean domain is a ring with a Euclidean function and a division with remainder.newsynthEThe Euclidean function for the Euclidean domain. This is a function rank : R\{0} ! ! such that:for all nonzero a, b " R, rank(a) "d rank(ab);if b "` 0 and (q,r) = a  b, then either r = 0 or rank(r) < rank(b).newsynthGiven a and b5"`0, return a quotient and remainder for division of a by b. Specifically, return (q,r ) such that a = qb + r, and such that r = 0 or rank(r) < rank(b).newsynth,Calculate the remainder for the division of x by y. Assumes that y "` 0.newsynth+Calculate the quotient for the division of x by y, ignoring the remainder, if any. This is typically, but not always, used in situations where the remainder is known to be 0 ahead of time. Assumes that y "` 0.newsynth>Calculate the greatest common divisor in any Euclidean domain.newsynth4Perform the extended Euclidean algorithm. On inputs x and y, this returns (a,b,s,t,d ) such that:d = gcd(x,y),ax + by = d,sx + ty = 0,at - bs = 1.newsynth^Find the inverse of a unit in a Euclidean domain. If the given element is not a unit, return  .newsynth=Determine whether an element of a Euclidean domain is a unit.newsynthCompute the inverse of a in R /(p), where R3 is a Euclidean domain. Note: this works whenever a and p are relatively prime. If a and p" are not relatively prime, return  .newsynthCheck whether a is a divisor of b.newsynthCheck whether a and b@ are associates, i.e., differ at most by a multiplicative unit.newsynthGiven elements x and y* of a Euclidean domain, find the largest k such that x can be written as y[sup k]z. Return the pair (k, z).If x=0 or y is a unit, return (0, x).newsynthFor y "` 0, find the integer q closest to x / y$. This works regardless of whether x and/or y* are positive or negative. The distance q " x / y% is guaranteed to be in (-1/2, 1/2].777None=?,,newsynth&Syllables is a circuit of the form (|T) (HT|SHT )[sup *].newsynthThe empty sequence .newsynth The sequence T.newsynthA sequence of the form &HT.newsynthA sequence of the form &SHT.newsynthFA representation of normal forms, optimized for right multiplication.newsynthA 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 SOQ(3), using various (exact or approximate) representations of the matrix entries.newsynth-Convert a list of gates to any suitable type.newsynthA 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.newsynth.Convert any suitable thing to a list of gates.newsynth7An enumeration type to represent symbolic basic gates (X, Y, Z, H, S, T, W, E).Note: when we use a list of s 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.newsynthInvert a gate list.newsynth)Convert any precise format to any format.newsynth The Pauli X operator.newsynth The Pauli Y operator.newsynth The Pauli Z operator.newsynthThe Hadamard operator.newsynthThe S operator.newsynthThe T operator.newsynthThe E operator.newsynthThe W = [exp i/4] global phase operator.newsynth6Convert a symbolic gate to the corresponding operator.newsynth The Pauli X operator.newsynth The Pauli Y operator.newsynth The Pauli Z operator.newsynthThe Hadamard operator.newsynth The operator S.newsynth The operator E.newsynthThe T operator.newsynthDConvert a symbolic gate to the corresponding Bloch sphere operator.newsynthConversion from U(2) to SO(3).newsynth+Convert a Clifford operator to a matrix in SO(3).newsynthConvert a matrix in SOE(3) to a Clifford gate. Throw an error if the matrix isn't Clifford.newsynth/Right-multiply the given normal form by a gate.newsynthThe identity as a normal form.newsynth8Multiply two normal forms. The right factor can be any .newsynth+Invert a normal form. The input can be any .newsynth Convert any  list to a , thereby normalizing it.newsynthInput an exact matrix in SO,(3), and output the corresponding Clifford+TG normal form. It is an error if the given matrix is not an element of SO)(3), i.e., orthogonal with determinant 1.7This 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.newsynthInput an exact matrix in U,(2), and output the corresponding Clifford+TR normal form. The behavior is undefined if the given matrix is not an element of U'(2), i.e., unitary with determinant 1.OWe 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.newsynthCompactly encode a  as an .newsynth Decode a  from its # encoding. This is the inverse of .newsynth<Encode a Clifford operator as an integer in the range 0"191.newsynthNDecode a Clifford operator from its integer encoding. This is the inverse of 55 None. NoneI[ newsynth,An elementary rotation is either a combined x- and z-rotation, applied at indices j and k&, or a phase change applied at index j.   j k represents the operator R sub /z/R sub /x/, applied to levels j and k.[image ERot_zx.png]   j represents the operator [exp i] applied to level j.[image ERot_phase.png]Note: when we use a list of s 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. newsynth<Convert a symbolic elementary rotation to a concrete matrix. newsynth1Convert a sequence of elementary rotations to an nn-matrix. newsynth Convert an nn.-matrix to a sequence of elementary rotations.Note: the list of elementary rotations 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. newsynthConstruct a two-level nn--matrix from a given 22-matrix and indices j and k.newsynthExtract the phase of the j'th diagonal entry of the given matrix.newsynth&Perform a two-level operation on rows j and k of a matrix U2, such that the resulting matrix has a 0 in the (j,k`)-position. Return the inverse of the two-level operation used, as well as the updated matrix.newsynthReturn a "random" unitary nn|-matrix. These matrices will not quite be uniformly distributed; this function is primarily meant to generate test cases. newsynthaGenerate a random matrix, decompose it, and then re-calculate the matrix from the decomposition.             SafeinewsynthA step computation can be run for a specified number of steps, stopped, continued, and interleaved. Such a computation produces "ticks" at user-defined intervals, which must be consumed by the environment for the computation to continue.newsynthTerminate with a result.newsynth/Produce a "tick", then resume the computation.newsynthIssue a single tick.newsynth&Run the step computation for one step.newsynthFast-forward a computation by n1 steps. This is essentially equivalent to doing n  operations.newsynth.Check whether a step computation is completed.newsynth8Retrieve the result of a completed step computation (or   if it is incomplete).newsynth'Run a subsidiary computation for up to nL steps, translated into an equal number of steps of the parent computation.newsynth-Run a subtask, speeding it up by a factor of n= "e 1. Every 1 tick of the calling task corresponds to up to n ticks of the subtask.newsynth<Run two step computations in parallel, until one branch terminates. Tick allocation is associative: each tick of the parent function translates into one tick for each subcomputation. Therefore, when running, e.g., three subcomputations in parallel, they will each receive an approximately equal number of ticks.newsynthRWrap a step computation to return the number of steps, in addition to the result.newsynth)Run a step computation until it finishes. newsynthXRun a step computation until it finishes, and also return the number of steps it took. !newsynth#Run a step computation for at most n steps."newsynthDo nothing, forever.#newsynthhRun two step computations in parallel. The first one to complete becomes the result of the computation.$newsynthFRun two step computations in parallel. If either computation returns   , return  ). Otherwise, return the pair of results.%newsynthIRun a list of step computations in parallel. If any computation returns   , return  ). Otherwise, return the list of results. !"#$% !"#$% None*newsynthGiven  " !$["2], find t " !$[] such that t[sup ]t = , if such t exists, or return   otherwise.+newsynth(Given an element  " [bold D]["2], find t " [bold D][] such that t[sup ]t = , if such t exists, or return   otherwise.,newsynthGiven  " !$["2], find t " !$[] such that t[sup ]t ~ , if such t exists, or   otherwise. Unlike *Q, the equation is only solved up to associates, i.e., up to a unit of the ring.-newsynth#Given a positive composite integer n , find a non-trivial factor of n@ using a simple Pollard-rho method. The expected runtime is O("p ), where p0 is the size of the smallest prime factor. If n is not composite (i.e., if n) is prime or 1), this function diverges..newsynthGiven a factorization n = ab@ of some element of a Euclidean domain, find a factorization of n into relatively prime factors,[center n = u c [sub 1][sup k[sub 1]] " & " c[sub m][sup k[sub m]],]where m "e 2, u is a unit, and c [sub 1], &, c[sub m!] are pairwise relatively prime.1While this is not quite a prime factorization of n, it can be a useful intermediate step for computations that proceed by recursion on relatively prime factors (such as Euler's -function, the solution of Diophantine equations, etc.)./newsynth@Modular exponentiation, using the method of repeated squaring. / a k n computes a[sup k] (mod n).0newsynthCompute a root of "1 in !$[sub n ], where n > 0. If n! is a positive prime satisfying nc "a 1 (mod 4), this succeeds within an expected number of 2 ticks. Otherwise, it probably diverges.1As a special case, if this function notices that nC is not prime, then it diverges without doing any additional work.1newsynthCompute a root of a in !$[sub n ], where n > 0. If n is an odd prime and a is a non-zero square in !$[sub nZ], then this succeeds in an expected number of 2 ticks. Otherwise, it probably diverges.newsynthGiven an integer n " !$, attempt to find t " !$[] such that t[sup ]t ~ n , or return   if no such t exists.-This function is optimized for the case when nL is prime, and succeeds in an expected number of 2 ticks in this case. If n0 is not prime, this function probably diverges.newsynthGiven an integer n " !$, find t " !$[] such that t[sup ]t ~ n , if such t exists, or return   if no such t exists.  This function alternately calls  and attempts to factor ne. Therefore, it will eventually succeed; however, the runtime depends on how hard it is to factor . newsynthGiven a factorization n = q [sub 1][sup k [sub 1]]" &"q[sub m][sup k[sub m]] of an integer n, where q [sub 1], &, q[sub m&] are pairwise relatively prime, find t " !$[] such that t[sup ]t ~ n , if such t exists, or return   if no such t exists.!newsynthGiven a pair of integers (n, k), find t " !$[] such that t[sup ]t ~ n[sup k ], if such t exists, or return   if no such t exists."newsynth-Given  " !$["2] such that  ~ [sup "], find t " !$[] such that t[sup ]t ~ , if such t exists, or return   if no such t exists.#newsynthAGiven  " !$["2] such that gcd(, [sup "]) = 1, attempt to find t " !$[] such that t[sup ]t ~ , or return   if no such t exists. This function is optimized for the case when  is a prime in the ring !$["2]. In this case, it succeeds quickly, in an expected number of 2 ticks. If  is not prime, this function probably diverges.$newsynth5Given  " !$["2] such that gcd(, [sup "]) = 1, find t " !$[] such that t[sup ]t ~ , if such t exists, or return   if no such t exists. This function alternately calls  and attempts to factor . Therefore, it will eventually succeed. However, the runtime depends on how hard it is to factor .%newsynthGiven a factorization  = q [sub 1][sup k [sub 1]]" &"q[sub m][sup k[sub m]] of some  " !$["2], where q [sub 1], &, q[sub m&] are pairwise relatively prime, find t " !$[] such that t[sup ]t ~ , if such t exists, or return  # if it can be proven not to exist.&newsynthGiven a pair (, k), with  " !$["2] and k "e 0, find t " !$[] such that t[sup ]t ~ [sup k ], if such t exists, or return   if no such t exists.*+,-./01*+,-./01 Safe=?SX72newsynthWA type class for things that can be converted to a real number at arbitrary precision.4newsynth:A type to represent symbolic expressions for real numbers.Caution: equality 'b at this type denotes symbolic equality of expressions, not equality of the defined real numbers.5newsynthAn integer constant.6newsynthJA decimal constant. This has a rational value and a string representation.7newsynthx + y.8newsynthx " y.9newsynthx * y.:newsynthx / y.;newsynth"x.<newsynth|x|.=newsynthsignum(x).>newsynth1/x.?newsynth.@newsynthe.Anewsynth[exp x].Bnewsynth"x.Cnewsynthlog x.Dnewsynthx[sup y].Enewsynthsin x.Fnewsynthcos x.Gnewsynthcos x.Hnewsynthasin x.Inewsynthatan x.Jnewsynthacos x.Knewsynthsinh x.Lnewsynthtanh x.Mnewsynthcosh x.Nnewsynthasinh x.Onewsynthatanh x.Pnewsynthacosh x.Qnewsyntharctan2 x y.RnewsynthIt would be useful to have a function for converting a symbolic real number to a fixed-precision real number with a chosen precision, such that the precision e depends on a parameter d: Pto_fixedprec :: (ToReal r) => Integer -> r -> FixedPrec e to_fixedprec d x = ...However, since e is a type, dP is a term, and Haskell is not dependently typed, this cannot be done directly. The function R9 is the closest thing we have to a workaround. The call dynamic_fixedprec d f x calls f(x '), where x' is the value x converted to d/ digits of precision. In other words, we have /dynamic_fixedprec d f x = f (to_fixedprec d x),(with the restriction that the precision e, cannot occur freely in the result type of f.SnewsynthLike RK, but take two real number arguments. In terms of the fictitious function  to_fixedprec , we have: Edynamic_fixedprec2 d f x y = f (to_fixedprec d x) (to_fixedprec d y).Tnewsynthinteger ::= digit digit*.Unewsynthfloat ::= digit* "." digit*.KThere must be at least one digit, either before or after the decimal point.Vnewsynthconst_pi ::= "pi".Wnewsynthconst_e ::= "e".Xnewsynthnegative ::= """.Ynewsynthpositive ::= "+".Znewsynth plus_term ::= "+" exp7.[newsynth minus_term ::= """ exp7.\newsynth times_term ::= "*" exp8.]newsynthdiv_term ::= "/" exp8.^newsynth power_term ::= exp10 "**" | exp10 "^"._newsynth unary_fun ::= unary_op exp10.`newsynthunary_op ::= "abs" | "signum" | ...anewsynth binary_fun ::=  binary_op exp10 exp10.bnewsynth binary_op ::= "abs" | "signum" | ...cnewsynthexp6 ::= (negative | positive)? exp7 (  plus_term |  minus_term )*.qAn expression whose top-level operator has precedence 6 or above. The operators of precedence 6 are "+" and """.dnewsynthexp7 ::= exp8 (  times_term | div_term )*.qAn expression whose top-level operator has precedence 7 or above. The operators of precedence 6 are "*" and "/".enewsynthexp8 ::= (  power_term )* exp10rAn expression whose top-level operator has precedence 8 or above. The operators of precedence 6 are "**" and "^".fnewsynthexp10 ::=  parenthesized | const_pi | const_e | integer | float |  unary_fun |  binary_fun.An expression whose top-level operator has precedence 10 or above. Such expressions are constants, applications of unary operators (except unary """ and "+"), and parenthesized expressions.gnewsynth parenthesized ::= "(" exp6 ")".hnewsynth expression ::= exp6  end-of-line.This is a top-level expression.inewsynthQParse a symbolic real number expression. Typical strings that can be parsed are "1.0", "pi/128", "(1+sin(pi/3))^2"3, etc. If the expression cannot be parsed, return  .8234PONMLKJIHGFEDCB@?>=<;8697Q5A:RSTUVWXYZ[\]^_`abcdefghi84PONMLKJIHGFEDCB@?>=<;8697Q5A:23RSTUVWXYZ[\]^_`abcdefghiNoneNone&'=?}newsynth=A type class for things that can be printed to LaTeX format. Minimal complete definition: ~ or .~newsynthPrint to LaTeX format.newsynth5Print to LaTeX format, with precedence. Analogous to (.newsynthNGeneric showlatex-like method that factors out a common denominator exponent.}~}~Safe=?SX\newsynthWA type class for things that can be converted to a real number at arbitrary precision.newsynthIt would be useful to have a function for converting a symbolic real number to a fixed-precision real number with a chosen precision, such that the precision e depends on a parameter d: Pto_fixedprec :: (ToReal r) => Integer -> r -> FixedPrec e to_fixedprec d x = ...However, since e is a type, dP is a term, and Haskell is not dependently typed, this cannot be done directly. The function 9 is the closest thing we have to a workaround. The call dynamic_fixedprec d f x calls f(x '), where x' is the value x converted to d/ digits of precision. In other words, we have /dynamic_fixedprec d f x = f (to_fixedprec d x),(with the restriction that the precision e, cannot occur freely in the result type of f.newsynthLike K, but take two real number arguments. In terms of the fictitious function  to_fixedprec , we have: Edynamic_fixedprec2 d f x y = f (to_fixedprec d x) (to_fixedprec d y).None=?@AnewsynthThis type class provides a primitive method for solving quadratic equations. For many floating-point or fixed-precision representations of real numbers, using the usual "quadratic formula" results in a significant loss of precision. Instances of the H class should provide an efficient high-precision method when possible.newsynth a b c : solve the quadratic equation ax + bx + c$ = 0. Return the pair of solutions (x , x ) with x "d x , or  4 if no solution exists. Note that the coefficients a, b, and cq can be taken to be of an exact type; therefore instances have the opportunity to work with infinite precision.)newsynthGiven b, c* " !["2], consider the quadratic function f(t) = t + bt + c.If f(t$) = 0 has no real solutions, return  .If f(t) = 0 has real solutions t "d t , return t' , t' " !$ such that t' "d t , t "d t ' , and |t' - t |, |t' - t | "d 1.*newsynthGiven a, b, c " !["2] with a' > 0, consider the quadratic function f(t) = at + bt + c.If f(t$) = 0 has no real solutions, return  .If f(t) = 0 has real solutions t "d t , return (t' , t' ) such that t' "d t , t "d t ' , and |t' - t |, |t' - t | "d 10[sup -d ], where d7 is the precision of the fixed-point real number type.None>MnewsynthA state is a pair (DY, ) of real positive definite matrices of determinant 1. It encodes a pair of ellipses.newsynthhA compact convex set is given by a bounding ellipse, a characteristic function, and a line intersector.newsynthA line intersector& knows about some compact convex set A. Given a straight line L7, it computes an approximation of the intersection of L and A.More specifically, L# is given as a parametric equation p(t) = v + tw, where v and w "` 0 are vectors. Given v and w6, the line intersector returns (an approximation of) t and t such that p(t) " A iff t " [t , t ].newsynthThe characteristic function of a set A inputs a point p, and outputs + if p " A and , otherwise. The point ph is given of an exact type, so characteristic functions have the opportunity to use infinite precision.newsynthAn ellipse is given by an operator D and a center p; the ellipse in this case isA = { v | (v-p )[sup ] D (v-p) "d 1}.newsynth!An operator is a real 22-matrix.newsynthA point in the plane.newsynthGiven two intervals A = [x , x ] and B = [y , y[ ] of real numbers, output all solutions  " !$["2] of the 1-dimensional grid problem for A and BH. The list is produced lazily, and is sorted in order of increasing . newsynthLike , but only produce solutions a + b "2 where a* has the same parity as the given integer.newsynthGiven two intervals A = [x , x ] and B = [y , y{ ] of real numbers, and a source of randomness, output a random solution  " !$["2] of the 1-dimensional grid problem for A and B.Note: the randomness is not uniform. To ensure that the set of solutions is non-empty, we must have xy "e (1 + "2), where x = x " x "e 0 and y = y " y? "e 0. If there are no solutions at all, the function returns  .newsynthLike , but only produce solutions a + b "2 where a* has the same parity as the given integer.newsynthGiven intervals A = [x , x ] and B = [y , y ], and an integer k. "e 0, output all solutions  " !$["2] / "2[sup k0] of the scaled 1-dimensional grid problem for A, B, and kF. The list is produced lazily, and is sorted in order of increasing .newsynthLike  , but assume k7 "e 1, take an additional parameter  " !$["2] / "2[sup k=], and return only those  such that  "  " !$["2] / "2[sup k-1].newsynth$Convert a point with coordinates in @% to a point with coordinates in any Y.newsynthThe closed unit disk.newsynthA closed disk of radius "s!, centered at the origin. Assume s > 0.newsynth-A closed rectangle with the given dimensions.newsynthGiven bounded convex sets A and B, enumerate all solutions u. " !$[] of the 2-dimensional grid problem for A and B.newsynthGiven bounded convex sets A and B&, return a function that can input a kM and enumerate all solutions of the two-dimensional scaled grid problem for A, B, and k.;Note: a large amount of precomputation is done on the sets A and B, so it is beneficial to call this function only once for a given pair of sets, and then possibly call the result many times for different kR. In other words, for optimal performance, the function should be used like this: alet solver = gridpoints2_scaled setA setB let solutions0 = solver 0 let solutions1 = solver 1 ...jNote: the gridpoints are computed in some deterministic (but unspecified) order. They are not randomized.newsynthLike , except that instead of performing a precomputation, we input the desired grid operator. It must make the two given sets upright.newsynthGiven bounded convex sets A and BN, enumerate all solutions of the two-dimensional scaled grid problem for all kg "e 0. Each solution is only enumerated once, and the solutions are enumerated in order of increasing k&. The results are returned in the form #[ (0, l0), (1, l1), (2, l2), ... ],where l0 is a list of solutions for k=0, l1 is a list of solutions for k=1, and so on.newsynthLike , except that instead of performing a precomputation, we input the desired grid operator. It must make the two given sets upright.newsynth Similar to  , except:  Assume that x0 and y0v are not too far from the origin (say, between -10 and 10). This is to avoid problems with numeric instability when x0 and y0 are much larger than dx and dy, respectively.]The function potentially returns some non-solutions, so the caller should test for accuracy.newsynth Construct a 22-matrix, by rows.newsynth-Extract the entries of a 22-matrix, by rows.newsynth$Convert an operator with entries in @% to an operator with entries in any Y.newsynthThe (b,z=)-representation of a positive operator with determinant 1 is[image bz.png]where b, z " ! and e > 0 with e = b0 + 1. Create such an operator from parameters b and z.newsynth^Conversely, given a positive definite real operator of determinant 1, return the parameters (b, z). This is the inverse of ). For efficiency reasons, the parameter z(, which is a logarithm, is modeled as a -.newsynth A version of  that returns (b , [sup 2z]) instead of (b, z{). This is a critical optimization, as this function is called often, and logarithms are relatively expensive to compute.newsynth The determinant of a 22-matrix.newsynthJCompute the skew of a positive operator of determinant 1. We define the skew& of a positive definite real operator D to be[image skew.png]newsynth/Compute the uprightness of a positive operator D. The  uprightness of D* is the ratio of the area of the ellipse E = {v | v[sup ]Dv' "d 1} to the area of its bounding box R. It is given by[image area.png][image ellipse-rectangle.png]newsynthThe skew: of a state is the sum of the skews of the two operators.newsynthThe bias of a state is  - z.newsynthThe special grid operator R: a clockwise rotation by 45.[image gridop-R.png]newsynthThe special grid operator A7: a clockwise shearing with offset 2, parallel to the x-axis.[image gridop-A.png]newsynthThe special grid operator A@ {: a counterclockwise shearing with offset 2, parallel to the x-axis.[image gridop-Ai.png]newsynth The operator A[sup k].newsynthThe special grid operator B8: a clockwise shearing with offset "2, parallel to the x-axis.[image gridop-B.png]newsynthThe special grid operator BA {: a counterclockwise shearing with offset "2, parallel to the x-axis.[image gridop-Bi.png]newsynth The operator B[sup k].newsynthThe special grid operator K.[image gridop-K.png]newsynth The Pauli X& operator is a special grid operator. [image gridop-X.png]newsynthThe Pauli operator Z is a special grid operator.[image gridop-Z.png]newsynthThe special grid operator S : a scaling by  = 1+"2 in the x&-direction, and by  { = -1+"2 in the y -direction.[image gridop-S.png] The operator Sw is not used in the paper, but we use it here for a more efficient implementation of large shifts. The point is that S is a grid operator, but shifts in increments of 4, whereas the Shift Lemma uses non-grid operators but shifts in increments of 2.newsynthThe special grid operator S {, the inverse of .[image gridop-Si.png]newsynthReturn S[sup k].newsynth,Compute the right action of a grid operator G on a state (D, ). This is defined as:(D, ) " G := (G[sup ]DG, G [sup "T]G [sup "]).newsynthGiven an operator D, compute [sup k]D[sup k].newsynth#Given an operator , compute [sup k][sup k].newsynth Compute the k-shift of a state (D,).newsynthAn implementation of the A-Lemma. Given z and , compute the integer m such that the operator A[sup m] reduces the skew.newsynthAn implementation of the B-Lemma. Given z and , compute the integer m such that the operator B[sup m] reduces the skew.newsynth A version of  that inputs [sup 2z ] instead of z3 and [sup 2] instead of . Compute the constant m such that the operator A[sup m] reduces the skew.newsynth A version of  that inputs [sup 2z ] instead of z3 and [sup 2] instead of . Compute the constant m such that the operator B[sup m] reduces the skew.newsynth4An implementation of the Step Lemma. Input a state (DV,). If the skew is > 15, produce a special grid operator whose action reduces Skew(D,) by at least 5%. If the skew is "d 15 and  "e 0 and z +  "e 0, do nothing. Otherwise, produce a special grid operator that ensures  "e 0 and z +  "e 0.newsynthRRepeatedly apply the Step Lemma to the given state, until the skew is 15 or less.newsynth1Given a pair of ellipses, return a grid operator Gb such that the uprightness of each ellipse is greater than 1/6. This is essentially the same as G, except we do not assume that the input operators have determinant 1.newsynth4Given a pair of convex sets, return a grid operator G making both sets upright.newsynthApply a linear transformation G to a point p.newsynth&Apply a special linear transformation G to an ellipse A#. This results in the new ellipse G(A) = { G(z) | z " A }.newsynthApply a special grid operator G to a characteristic function.newsynth&Apply a special linear transformation GM to a line intersector. If the input line intersector was for a convex set A2, then the output line intersector is for the set G(A) = { G(z) | z " A }.newsynth&Apply a special linear transformation G to a convex set A%. This results in the new convex set G(A) = { G(z) | z " A }.newsynth*Calculate the bounding box for an ellipse.newsynth5Calculate a bounding box for a convex set. Returns ((x , x ), (y , y )).newsynth We write x `within` (a,b) for a "d x "d b, or equivalently, x " [a, b].newsynth0Given an interval, return a slightly bigger one.newsynthThe constant  = 1 + "2.newsynthThe constant  { = "2 - 1.newsynth Return [sup k ], where k " !$. This works in any \.Note that we can't use ., because it requires k "e 0, nor /, because it requires the 0 class.newsynthReturn (-1)[sup k ], where k " !$.newsynthGiven positive numbers b and x , return (n, r ) such thatx = r b[sup n ] and 1 "d r < b#. In other words, let n = # log[sub b] x# and r = x b[sup "n#]. This can be more efficient than  (1 b xJ) depending on the type; moreover, it also works for exact types such as  and ?.newsynth2A version of the natural logarithm that returns a -8. The logarithm of just about any value can fit into a -a; so if not a lot of precision is required in the mantissa, this function is often faster than 2.newsynth The inner product of two points.newsynthSubtract two points.newsynthCalculute the inverse of an operator of determinant 1. Note: this does not work correctly for operators whose determinant is not 1.OONone>X newsynthMInformation about the status of an attempt to solve a Diophantine equation. - means the Diophantine equation was solved; 7 means that it was proved that there was no solution; C means that the question was not decided within the allotted time.newsynth*Output a unitary operator in the Clifford+T group that approximates R sub /z/ = [exp "iZd/2] to within  in the operator norm. This operator can then be converted to a list of gates with .The parameters are:a source of randomness g; the angle ;the precision b# "e 0 in bits, such that  = 2[sup -b];an integer that determines the amount of "effort" to put into factoring. A larger number means more time spent on factoring. A good default for this is 25.Note: the argument theta is given as a symbolic real number. It will automatically be expanded to as many digits as are necessary for the internal calculation. In this way, the caller can specify, e.g., an angle of pi/128 :: 4A, without having to worry about how many digits of  to specify.newsynth A version of 3 that returns a list of gates instead of a matrix.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.newsynth A version of X that also returns some statistics: log[sub 0.5] of the actual approximation error (or  U if the error is 0), and a data structure with information on the candidates tried.newsynth A version of $ that returns the optimal operator up to a global phaseE. (The default behavior is to return the optimal operator exactly).newsynthThe -regionO for given  and  is a convex subset of the closed unit disk, given by [nobr u " z "e 1 - /2], where [nobr z = [exp "iB/2]], and "  denotes the dot product of ! (identified with !).[center [image Re.png]]newsynthThe -region%, scaled by an additional factor of "s , where s* > 0. The center of scaling is the origin.newsynth}The internal implementation of the ellipse-based approximate synthesis algorithm. The parameters are a source of randomness g, the angle , the precision b? "e 0 in bits, and an amount of "effort" to put into factoring.3The outputs are a unitary operator in the Clifford+T group that approximates R sub /z/I to within  in the operator norm; log[sub 0.5] of the actual error, or  8 if the error is 0; and the number of candidates tried.Note: the parameter  must be of a real number type that has enough precision to perform intermediate calculations; this typically requires precision O([sup 2]). A more user-friendly function that selects the required precision automatically is .newsynthThe internal implementation of the ellipse-based approximate synthesis algorithm, up to a phase. The parameters are the same as for .newsynthMerge the elements of two lists in increasing order, assuming that each of the lists is already sorted. The first argument is a comparison function for elements.newsynth'Return the first component of a triple.NonetnewsynthZBackward compatible interface to the approximate synthesis algorithm. The parameters are:an angle , to implement a R sub /z/ = [exp "iZ /2] gate; a precision b# "e 0 in bits, such that  = 2[sup -b];a source of randomness g.*Output a unitary operator in the Clifford+T group that approximates R sub /z/a to within  in the operator norm. This operator can then be converted to a list of gates with .Note: the argument theta is given as a symbolic real number. It will automatically be expanded to as many digits as are necessary for the internal calculation. In this way, the caller can specify, e.g., an angle of 3/128 :: 4A, without having to worry about how many digits of  to specify.newsynth A version of X that also returns some statistics: log[sub 0.1] of the actual approximation error (or  9 if the error is 0), and the number of candidates tried.newsynth A version of S that returns a list of gates instead of a matrix. The inputs are the same as for .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.4 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIIJKLMNOPQQRSTUUVWXYYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                        ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C  D  E F G H I J K L M N O P Q R S T U V W X Y Z [  \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~   ?@\]z{|}~      !"#$%&' ( ) * + , - . / 012345617817917:;<=>?@A'newsynth-0.4.1.0-Gwbf18n6TxuEQXpQQA11yjQuantum.Synthesis.ArcTan2Quantum.Synthesis.CliffordQuantum.Synthesis.RingQuantum.Synthesis.Matrix%Quantum.Synthesis.MultiQubitSynthesisQuantum.Synthesis.EulerAngles!Quantum.Synthesis.EuclideanDomainQuantum.Synthesis.CliffordT Quantum.Synthesis.Ring.FixedPrec'Quantum.Synthesis.RotationDecompositionQuantum.Synthesis.StepCompQuantum.Synthesis.DiophantineQuantum.Synthesis.SymRealQuantum.Synthesis.Ring.SymRealQuantum.Synthesis.LaTeXQuantum.Synthesis.ToReal#Quantum.Synthesis.QuadraticEquationQuantum.Synthesis.GridProblemsQuantum.Synthesis.GridSynthQuantum.Synthesis.NewsynthArcTan2arctan2$fArcTan2FixedPrec$fArcTan2Float$fArcTan2DoubleAxisAxis_IAxis_HAxis_SH ToClifford to_cliffordClifford clifford_X clifford_Y clifford_Z clifford_H clifford_S clifford_SH clifford_E clifford_Wclifford_decomposeclifford_decompose_coset clifford_id clifford_mult clifford_invclifford_tconj$fShowClifford$fToClifford[]$fToCliffordChar$fToCliffordClifford$fToCliffordAxis $fEqClifford $fOrdClifford$fEqAxis $fShowAxisParityparityToQOmegatoQOmegaDenomExpdenomexpdenomexp_factor WholePart from_wholeto_wholeRealPartrealToDyadic maybe_dyadicQOmegaDOmegaZOmegaOmegaCFloatCDouble QRComplex DRComplexQComplexDComplexZComplexCplxQRootTwoDRootTwoZRootTwoRootTwo Rationals ToRationals unRationalsDyadicZ2EvenOddFloorfloor_of ceiling_of NormedRingnormAdjoint2adj2Adjointadj OmegaRingomega ComplexRingi RootHalfRingroothalf fromDRootTwo RootTwoRingroottwo fromZRootTwoHalfRinghalf fromDyadicRingdecompose_dyadicinteger_of_dyadicshowsPrec_rational fromRationals zroottwo_root fromQRootTwo fromZComplex fromDComplex fromQComplex fromDRComplex fromQRComplex omega_real fromZOmegazroottwo_of_zomega fromDOmega fromQOmega to_dyadicdenomexp_decomposeshowsPrec_DenomExplobitlog2hibitintsqrt$fComplexRingComplex$fAdjointComplex$fAdjointRatio$fAdjointFloat$fAdjointDouble $fAdjointInt$fAdjointInteger$fAdjoint2Ratio $fAdjoint2Int$fAdjoint2Integer$fNormedRingInteger $fFloorDouble $fFloorFloat $fFloorRatio$fFloorInteger $fAdjoint2Z2 $fAdjointZ2$fNumZ2$fShowZ2$fAdjoint2Dyadic$fAdjointDyadic $fNumDyadic $fOrdDyadic $fEqDyadic $fShowDyadic $fRealDyadic$fHalfRingDyadic$fHalfRingComplex$fHalfRingRatio$fHalfRingFloat$fHalfRingDouble$fNormedRingRootTwo$fAdjoint2RootTwo$fAdjointRootTwo$fComplexRingRootTwo$fHalfRingRootTwo$fFractionalRootTwo $fShowRootTwo $fOrdRootTwo $fNumRootTwo$fRootTwoRingRootTwo$fRootTwoRingComplex$fRootTwoRingFloat$fRootTwoRingDouble$fOmegaRingRootTwo$fRootHalfRingRootTwo$fOmegaRingComplex$fRootHalfRingComplex$fRootHalfRingFloat$fRootHalfRingDouble$fNormedRingCplx$fAdjoint2Cplx $fAdjointCplx$fRootTwoRingCplx$fRootHalfRingCplx$fHalfRingCplx$fOmegaRingCplx$fComplexRingCplx$fFractionalCplx $fNumCplx $fShowCplx $fShowCplx0$fOmegaRingOmega$fNormedRingOmega$fAdjoint2Omega$fAdjointOmega$fComplexRingOmega$fRootTwoRingOmega$fRootHalfRingOmega$fHalfRingOmega$fFractionalOmega $fNumOmega $fShowOmega $fShowOmega0$fToDyadicOmegaOmega$fToDyadicCplxCplx$fToDyadicRootTwoRootTwo$fToDyadicRatioDyadic$fToDyadicDyadicDyadic$fRealPartOmegaRootTwo$fRealPartCplxa$fWholePartCplxCplx$fWholePart[][]$fWholePart()()$fWholePart(,)(,)$fWholePartOmegaOmega$fWholePartRootTwoRootTwo$fWholePartDyadicInteger$fDenomExpCplx $fDenomExp[] $fDenomExp() $fDenomExp(,)$fDenomExpOmega$fDenomExpRootTwo$fToQOmegaOmega$fToQOmegaCplx$fToQOmegaDyadic$fToQOmegaRootTwo$fToQOmegaRatio$fToQOmegaInteger$fToDyadicRationalsDyadic$fShowRationals$fFloorRootTwo$fParityRootTwo $fParitya$fEqZ2 $fEqRootTwo$fEqCplx $fEqOmega$fNumRationals $fEqRationals$fOrdRationals$fFractionalRationals$fRealRationals$fRealFracRationals$fHalfRingRationals$fAdjointRationals$fAdjoint2Rationals$fToQOmegaRationals$fFloorRationalsSO3U2MatrixVectorNilConsTimesPlusNatnnatnatNNatZeroSuccTen_andTenNineEightSevenSixFiveFourThreeTwoOnefromNNatvector_singleton vector_lengthlist_of_vectorvector_zipwith vector_map vector_enumvector_of_functionvector vector_index vector_repeatvector_transpose vector_foldl vector_foldr vector_tail vector_head vector_appendvector_sequenceunMatrix matrix_size.+..-. matrix_map matrix_enummatrix_of_function scalarmult scalardiv.*. null_matrixmatrix_transposeadjoint matrix_indexmatrix_entriesmatrix_sequencetr hs_sqnormstack_verticalstack_horizontaltensor_verticalconcat_verticaltensor_horizontalconcat_horizontaltensoroplusmatrix_controlledmatrix_of_columnsmatrix_of_rowsmatrixcolumns_of_matrixrows_of_matrix matrix2x2from_matrix2x2 matrix3x3 matrix4x4column3 from_column3 column_matrixcnotswapzrot $fNatSucc $fNatZero $fShowNNat$fDenomExpVector$fWholePartVectorVector$fToDyadicVectorVector $fShowVector $fEqVector$fOmegaRingMatrix$fComplexRingMatrix$fRootTwoRingMatrix$fRootHalfRingMatrix$fHalfRingMatrix$fAdjoint2Matrix$fAdjointMatrix $fNumMatrix$fDenomExpMatrix$fWholePartMatrixMatrix$fToDyadicMatrixMatrix $fShowMatrix $fShowMatrix0 $fShowMatrix1 $fShowMatrix2 $fEqMatrix TwoLevelAltTL_iXTL_TiHTTL_W TL_omega_alt ResidueTypeRT_0000RT_0001RT_1010TwoLevelTL_XTL_HTL_TTL_omegaIndexResidueresidueinvert_twolevelinvert_twolevelstwolevel_matrixonelevel_matrixmatrix_of_twolevelmatrix_of_twolevels list_insert transform_at transform_at2 list_pairs log_omega omega_power reduce_ZOmega opX_zomega opH_zomegaapply_twolevel_zomegaapply_twolevels_zomega residue_type residue_shiftresidue_type_shiftresidue_offset reduciblerow_step reduce_columnsynthesis_nqubittwolevels_of_twolevelaltsinvert_twolevels_alt row_step_altreduce_column_altsynthesis_nqubit_alt$fResidueMatrixMatrix$fResidueVectorVector$fResidueCplxCplx $fResidue[][] $fResidue()()$fResidue(,)(,)$fResidueRootTwoRootTwo$fResidueOmegaOmega$fResidueIntegerZ2$fShowTwoLevel $fEqTwoLevel$fEqResidueType$fOrdResidueType$fShowTwoLevelAlt$fEqTwoLevelAlt euler_anglesmatrix_of_euler_anglesEuclideanDomainrankdivmod euclid_mod euclid_div euclid_gcdextended_euclideuclid_inverseis_unitinv_modeuclid_divideseuclid_associateseuclid_extract_powerrounddiv$fEuclideanDomainOmega$fEuclideanDomainRootTwo$fEuclideanDomainCplx$fEuclideanDomainInteger SyllablesS_IS_TSApp_HTSApp_SHT NormalForm FromGates from_gatesToGatesto_gatesGateXYZHSTEW invert_gatesconvertu2_Xu2_Yu2_Zu2_Hu2_Su2_Tu2_Eu2_W u2_of_gateso3_Xso3_Yso3_Zso3_Hso3_Sso3_Eso3_T so3_of_gate so3_of_u2so3_of_cliffordclifford_of_so3normalform_appendnf_idnf_multnf_inv normalizesynthesis_bloch synthesis_u2normalform_packnormalform_unpack clifford_packclifford_unpack$fToCliffordMatrix$fToGatesInteger$fToGatesMatrix$fToGatesTwoLevel$fToGatesMatrix0$fToGatesClifford $fToGatesAxis $fToGatesChar $fToGates[] $fToGatesGate$fFromGatesInteger$fFromGatesMatrix$fFromGatesMatrix0 $fFromGates[]$fFromGates[]0$fToGatesSyllables$fFromGatesNormalForm$fShowNormalForm$fToGatesNormalForm $fShowGate$fEqGate $fEqSyllables$fShowSyllables$fEqNormalForm$fFloorFixedPrec$fAdjoint2FixedPrec$fAdjointFixedPrec$fHalfRingFixedPrec$fRootTwoRingFixedPrec$fRootHalfRingFixedPrec ElementaryRotERot_zx ERot_phasematrix_of_elementarymatrix_of_elementariesrotation_decompositiontwolevel_matrix_of_matrix get_phaserowoprandom_unitarytest$fShowElementaryRotStepCompDoneTicktickuntickforwardis_done get_resultsubtaskspeedupparallel with_counterrunrun_with_steps run_boundeddivergeparallel_firstparallel_maybeparallel_list_maybe$fShowStepComp$fFunctorStepComp$fApplicativeStepComp$fMonadStepComp diophantinediophantine_dyadicdiophantine_associate find_factorrelatively_prime_factors power_modroot_of_negative_oneroot_modToRealto_realSymRealConstDecimalMinusDivNegateAbsSignumRecipPiEulerExpSqrtLogPowerSinTanCosASinATanACosSinhTanhCoshASinhATanhACoshdynamic_fixedprecdynamic_fixedprec2integerfloatconst_piconst_enegativepositive plus_term minus_term times_termdiv_term power_term unary_fununary_op binary_fun binary_opexp6exp7exp8exp10 parenthesized expression parse_SymReal$fArcTan2SymReal$fFloatingSymReal$fFractionalSymReal $fNumSymReal $fShowSymReal $fToReal[]$fToRealFixedPrec $fToRealFloat$fToRealDouble $fToRealInt$fToRealInteger $fToRealRatio$fToRealSymReal $fEqSymReal$fAdjoint2SymReal$fAdjointSymReal$fHalfRingSymReal$fRootTwoRingSymReal$fRootHalfRingSymReal ShowLaTeX showlatex showlatex_pshowlatex_denomexp_p$fShowLaTeXSymReal $fShowLaTeX[]$fShowLaTeXMatrix$fShowLaTeXMatrix0$fShowLaTeXOmega$fShowLaTeXDouble$fShowLaTeXCplx$fShowLaTeXOmega0$fShowLaTeXRootTwo$fShowLaTeXDyadic$fShowLaTeXRatio$fShowLaTeXMatrix1$fShowLaTeXOmega1$fShowLaTeXInteger$fShowLaTeX[]0$fShowLaTeXTwoLevel Quadratic quadratic$fQuadratictDouble$fQuadratictFixedPrec OperatorPair ConvexSetLineIntersectorCharFunEllipseOperatorPoint gridpointsgridpoints_paritygridpoint_randomgridpoint_random_paritygridpoints_scaledgridpoints_scaled_paritypoint_fromDRootTwounitdiskdisk rectangle gridpoints2gridpoints2_scaledgridpoints2_scaled_with_gridopgridpoints2_increasing"gridpoints2_increasing_with_gridopgridpoints_internal toOperator fromOperatorop_fromDRootTwooperator_from_bzoperator_to_bzoperator_to_bl2zdet operator_skew uprightnessskewbiasopRopAopA_inv opA_poweropBopB_inv opB_poweropKopXopZopSopS_inv opS_poweraction shift_sigma shift_tau shift_statelemma_Alemma_B lemma_A_l2 lemma_B_l2 step_lemma reduction to_uprightto_upright_setspoint_transformellipse_transformcharfun_transformlineintersector_transformconvex_transformboundingbox_ellipse boundingboxwithinfatten_intervallambda lambda_inv lambdapower signpowerfloorloglogBase_doubleiprod point_subspecial_inverse$fShowConvexSet $fShowEllipsePhasePhase0Phase1DStatusSuccessFailTimeout gridsynthgridsynth_gatesgridsynth_statsgridsynth_phase_statsepsilon_regionepsilon_region_scaledgridsynth_internalgridsynth_phase_internalmergeByfirst $fEqDStatus $fShowDStatusnewsynthnewsynth_statsnewsynth_gatesbase GHC.Floatatan2 RealFloatGHC.BaseStringconj2conj3cinvtconj GHC.MaybeNothingGHC.ShowShow Data.ComplexComplexGHC.RealRationalfloorceilingGHC.NumNum+-*abssignum Fractionalshow integer-gmpGHC.Integer.TypeIntegerGHC.List replicateData.Traversablesequencedioph_int_assoc_primedioph_int_assocdioph_int_assoc_powersdioph_int_assoc_powerdioph_zroottwo_selfassociatedioph_zroottwo_assoc_primedioph_zroottwo_assocdioph_zroottwo_assoc_powersdioph_zroottwo_assoc_powerghc-prim GHC.Classes== showsPrec int_quadraticquadratic_fixedprec GHC.TypesTrueFalseDouble^**FloatinglogBaselogpi