Definitions for Quantum CISC Compilation by Optimal Control and Scalable Assembly of Complex Instruction Sets beyond Two-Qubit Gates

QAlgorithms.Papers.Independent.Intakethird100.P39.BlockStep.matrix

For every natural number $n$, this assigns a complex matrix indexed by length-$n$ Boolean strings to each of four forms of step, whose parameters are arbitrary natural numbers: fourier $(o,w)$, phaseSwap $(o,h,j)$, swap $(o,h)$, and truncatedPhaseSwap $(o,h,j,c)$. The local matrix for a fourier step has row and column strings $v,u$ of length $w$ and entries

$$F_w(v,u)=\frac{\exp\!\left(2\pi\mathrm i\,V_w(v)V_w(u)/2^w\right)}{\sqrt{2^w}}, \qquad V_w(u)=\sum_{a=0}^{w-1}\mathbf1_{\{u_a=\mathrm{true}\}}2^{w-1-a}.$$

For the other three forms, the local strings have length $2h$; let $E_h(u)$ exchange their two halves, so $(E_h(u))_a=u_{h+a}$ for $a<h$ and $(E_h(u))_a=u_{a-h}$ for $h\le a<2h$, and put

$$A_h(u)=\sum_{a=0}^{h-1}\mathbf1_{\{u_a=\mathrm{true}\}}2^{h-1-a}, \qquad B_h(u)=\sum_{b=0}^{h-1}\mathbf1_{\{u_{h+b}=\mathrm{true}\}}2^{h-1-b}.$$

The local phaseSwap matrix has entry $\exp\!\left(2\pi\mathrm i\,A_h(u)B_h(u)/2^{(j+1)h}\right)$ when $v=E_h(u)$, and zero otherwise; the local swap matrix has entry $1$ when $v=E_h(u)$, and zero otherwise; the local truncatedPhaseSwap matrix has entry $\exp(\mathrm i\Phi(u))$ when $v=E_h(u)$, and zero otherwise, where, writing $d=\max(j-1,0)$,

$$\Phi(u)=\sum_{a=0}^{h-1}\sum_{b=0}^{h-1} \begin{cases} \displaystyle\frac{\pi}{2^{dh+1+a+b}}, &u_a=\mathrm{true},\ u_{h+b}=\mathrm{true},\ dh+1+a+b\le c,\\ 0,&\text{otherwise}. \end{cases}$$

To obtain the assigned matrix, take the local width $r=w$ for fourier and $r=2h$ for the other forms. If $o+r\le n$, its $(y,x)$ entry is the local matrix entry on the substrings $(y_o,\ldots,y_{o+r-1})$ and $(x_o,\ldots,x_{o+r-1})$, provided $y$ and $x$ agree at every position outside that interval, and is zero otherwise. If $o+r>n$, the assigned matrix is the identity. Empty sums are zero; width $w=0$ or half-width $h=0$ gives the identity matrix, and the truncated phase formula permits $j=0$ using $d=0$.

QAlgorithms.Papers.Independent.Intakethird100.P39.BlockStep

This defines a type whose elements have exactly four possible forms: a fourier value carrying natural numbers called offset and width; a phaseSwap value carrying natural numbers called offset, halfWidth, and phaseIndex; a truncatedPhaseSwap value carrying natural numbers called offset, halfWidth, phaseIndex, and cutoff; or a swap value carrying natural numbers called offset and halfWidth. All parameter values, including zero, are permitted, with no bounds or compatibility conditions. The four forms are distinct, two values of the same form are equal exactly when all corresponding parameters are equal, and equality of values of this type is decidable.

QAlgorithms.Papers.Independent.Intakethird100.P39.OneFactorQuotient

For arbitrary natural numbers $a,b$, let $S$ be the real vector space of complex matrices indexed by $\{0,\ldots,a-1\}\times\{0,\ldots,b-1\}$ satisfying $X^\ast=-X$ and $\operatorname{tr}(X)=0$, and let

$$L=\operatorname{span}_{\mathbb R} \{A\otimes I_b:A\in\mathbb C^{a\times a},\ A^\ast=-A,\ \operatorname{tr}(A)=0\}.$$

The abbreviation denotes the real vector space $S/(S\cap L)$: two elements of $S$ represent the same class exactly when their difference belongs to $L$. Here $\ast$ denotes conjugate transpose and $\otimes$ denotes the Kronecker product. Zero values of $a$ or $b$ are allowed and give the zero quotient space.

QAlgorithms.Papers.Independent.Intakethird100.P39.TwoFactorQuotient

For arbitrary natural numbers $a,b$, let $S$ be the real vector space of complex matrices indexed by $\{0,\ldots,a-1\}\times\{0,\ldots,b-1\}$ satisfying $X^\ast=-X$ and $\operatorname{tr}(X)=0$, and set

$$L=\operatorname{span}_{\mathbb R} \{A\otimes I_b:A\in\mathbb C^{a\times a},\ A^\ast=-A,\ \operatorname{tr}(A)=0\}, \qquad R=\operatorname{span}_{\mathbb R} \{I_a\otimes B:B\in\mathbb C^{b\times b},\ B^\ast=-B,\ \operatorname{tr}(B)=0\}.$$

The abbreviation denotes the real vector space $S/(S\cap(L+R))$: two elements of $S$ represent the same class exactly when their difference belongs to the sum of subspaces $L+R$. Here $\ast$ denotes conjugate transpose and $\otimes$ denotes the Kronecker product. Zero values of $a$ or $b$ are allowed and give the zero quotient space.

QAlgorithms.Papers.Independent.Intakethird100.P39.ascendingSweep

For every natural number $\ell$, including $0$, and every Boolean string $x=(x_0,\ldots,x_\ell)$, this defines a Boolean string by starting with $y=x$ and, successively for $i=0,1,\ldots,\ell-1$, replacing $y_{i+1}$ by $y_{i+1}\mathbin{\oplus}y_i$, leaving every other coordinate unchanged at that step. Here $\oplus$ is Boolean exclusive-or, and each step uses the current values of $y$, including changes made by previous steps. When $\ell=0$, there are no steps, and the result is $x$.

QAlgorithms.Papers.Independent.Intakethird100.P39.bitCnot

For every natural number $n$, every control index $c$ and target index $t$ in $\{0,\ldots,n-1\}$, and every bit string $x:\{0,\ldots,n-1\}\to\{\mathrm{false},\mathrm{true}\}$, this defines the bit string $y$ by

$$y_i= \begin{cases} x_i\mathbin{\oplus}x_c&i=t,\\ x_i&i\ne t, \end{cases}$$

where $\oplus$ is exclusive-or and the control bit is read from the original string $x$. The control and target need not be distinct: if $c=t$, the target becomes false. Although $n=0$ is permitted as a parameter, there are then no control or target indices with which to instantiate the definition.

QAlgorithms.Papers.Independent.Intakethird100.P39.blockCircuitMatrix

For every natural number $n$ and finite list $c=[s_0,\ldots,s_{L-1}]$ of block steps, this defines a complex matrix indexed by the length-$n$ bit strings as the reverse-ordered product $M_{L-1}\cdots M_0$, where $M_i$ is the matrix assigned to $s_i$; the empty list gives the identity matrix. The matrix assigned to a step places its local matrix on consecutive positions beginning at its offset, leaving all other bits unchanged; if the entire local block does not fit within the $n$ positions, the assigned matrix is instead the identity. More explicitly, a local matrix $A$ on $r$ bits, placed at offset $o$ with $o+r\le n$, has entry $A_{y|_{o,\ldots,o+r-1},\,x|_{o,\ldots,o+r-1}}$ when $y$ and $x$ agree outside that block, and entry zero otherwise. For a bit string $x$ of length $r$, write $v(x)=\sum_{a=0}^{r-1}x_a2^{r-1-a}$, interpreting bits as $0$ or $1$. A Fourier step of width $r$ uses the local matrix with entry

$$\frac{\exp(2\pi\mathrm{i}\,v(y)v(x)/2^r)}{\sqrt{2^r}}.$$

For a phase-swap step of half-width $w$ and phase index $j$, write the input as $x=(a,b)$, with each half of length $w$; its only nonzero entry in column $x$ is at row $(b,a)$, and equals $\exp(2\pi\mathrm{i}\,v(a)v(b)/2^{(j+1)w})$. A swap step has the same row position and entry $1$. A truncated phase-swap step with half-width $w$, phase index $j$, and cutoff $C$ has the same row position and entry

$$\exp\!\left(\mathrm{i}\sum_{p=0}^{w-1}\sum_{q=0}^{w-1} \begin{cases} \pi/2^{(j-1)w+1+p+q}, & a_p=b_q=1\ \text{and }(j-1)w+1+p+q\le C,\\ 0,&\text{otherwise}. \end{cases}\right).$$

Here $j-1$ uses natural-number subtraction, so it is zero when $j=0$. All offsets, widths, phase indices, and cutoffs may be zero; a zero-width block has one empty bit string, empty sums are zero, and $n=0$ is included.

QAlgorithms.Papers.Independent.Intakethird100.P39.blockQuality

For arbitrary real numbers $F_q,T,T_R$, an arbitrary function $F_c:\mathbb N\to\mathbb R$, and any finite list $c$ of block steps, this defines

$$\operatorname{blockQuality}(F_q,F_c,T,T_R,c) =\left(\prod_{s\text{ in }c}w(s)\right)e^{-T/T_R}, \qquad w(s)= \begin{cases} F_q & s\text{ is a Fourier step},\\ F_c(j) & s\text{ is a phase-swap step with phase index }j,\\ F_c(j) & s\text{ is a truncated phase-swap step with phase index }j,\\ F_c(3) & s\text{ is a swap step}. \end{cases}$$

The offsets, widths, and truncation cutoffs do not affect these weights. The product counts every occurrence in the list; an empty list has product $1$. There are no sign, size, or positivity restrictions on the real parameters or weights. In particular, $T_R=0$ is allowed, and real division by zero is defined to be zero, making the exponential factor $1$ in that case.

QAlgorithms.Papers.Independent.Intakethird100.P39.blockSwap

For every natural number $m$, this defines a complex matrix indexed by Boolean strings $y,x$ of length $2m$, with entry $1$ if

$$y_i= \begin{cases} x_{m+i},&0\le i<m,\\ x_{i-m},&m\le i<2m, \end{cases}$$

and entry $0$ otherwise. Thus each column has its $1$ at the row obtained by exchanging the two length-$m$ halves of the column string. For $m=0$, the row and column index sets each contain only the empty string, and the matrix has the single entry $1$.

QAlgorithms.Papers.Independent.Intakethird100.P39.cpSwap

For all natural numbers $m,j$, this defines a complex matrix $C_{m,j}$ whose rows and columns are indexed by Boolean strings of length $2m$. For such a string $x$, let

$$A(x)=\sum_{a=0}^{m-1}\mathbf1_{\{x_a=\mathrm{true}\}}\,2^{m-1-a}, \qquad B(x)=\sum_{b=0}^{m-1}\mathbf1_{\{x_{m+b}=\mathrm{true}\}}\,2^{m-1-b},$$

so these are the natural numbers encoded by the first and second halves, with their first coordinates having the largest binary weights. Let $E_m(x)$ be the string with coordinates $x_{m+i}$ for $i<m$ and $x_{i-m}$ for $m\le i<2m$. Then, for every row $y$ and column $x$,

$$(C_{m,j})_{y,x}= \begin{cases} \displaystyle \exp\!\left(\frac{2\pi\mathrm i\,A(x)B(x)}{2^{(j+1)m}}\right), &y=E_m(x),\\ 0,&y\ne E_m(x). \end{cases}$$

There are no positivity assumptions on $m$ or $j$; the denominator is always nonzero. When $m=0$, the sums are empty and the resulting matrix is the $1\times1$ matrix with entry $1$.

QAlgorithms.Papers.Independent.Intakethird100.P39.descendingSweep

For every natural number $\ell$, including $0$, and every Boolean string $x=(x_0,\ldots,x_\ell)$, this defines a Boolean string by starting with $y=x$ and performing the updates $y_{i+1}\leftarrow y_{i+1}\mathbin{\oplus}y_i$ in decreasing order of $i$, from $\ell-1$ down to $0$, leaving every other coordinate unchanged at each step. Here $\oplus$ is Boolean exclusive-or, and each step uses the current values of $y$. When $\ell=0$, there are no steps, and the result is $x$.

QAlgorithms.Papers.Independent.Intakethird100.P39.endpointCnot

For every natural number $\ell$, including $0$, and every Boolean string $x=(x_0,\ldots,x_\ell)$, this defines the Boolean string $y$ by $y_\ell=x_\ell\mathbin{\oplus}x_0$ and $y_i=x_i$ for every $i\ne\ell$, where $\oplus$ denotes Boolean exclusive-or. In particular, when $\ell=0$, the control and target coordinates coincide, so the sole output bit is $x_0\mathbin{\oplus}x_0=\mathrm{false}$.

QAlgorithms.Papers.Independent.Intakethird100.P39.endpointMatrix

For every natural number $\ell$, this defines an $(\ell+1)\times(\ell+1)$ matrix over $\mathbb Z/2\mathbb Z$, indexed by $0,\ldots,\ell$, as the identity matrix plus the matrix having entry $1$ at row $\ell$, column $0$, and entry $0$ elsewhere:

$$E_{ij}=\mathbf 1_{\{i=j\}}+\mathbf 1_{\{i=\ell,\ j=0\}},$$

with addition taken modulo $2$. When $\ell=0$, the two contributions coincide, so the resulting one-entry matrix is $[0]$.

QAlgorithms.Papers.Independent.Intakethird100.P39.exchangeHalves

For every natural number $m$ and every Boolean string $x$ of length $2m$, this defines a Boolean string $E_m(x)$ of the same length by

$$(E_m(x))_i= \begin{cases} x_{m+i},&0\le i<m,\\ x_{i-m},&m\le i<2m. \end{cases}$$

Thus the last $m$ coordinates become the first $m$ coordinates, and the first $m$ become the last $m$. The subtraction in the second case is natural-number subtraction, and its branch condition ensures that $i\ge m$. For $m=0$, the function sends the unique empty string to itself.

QAlgorithms.Papers.Independent.Intakethird100.P39.firstHalf

For every natural number $m$ and every Boolean string $x$ indexed by $0,\ldots,2m-1$, this defines a Boolean string of length $m$ whose coordinate at each $0\le i<m$ is $x_i$. Thus its coordinates are $(x_0,\ldots,x_{m-1})$. When $m=0$, both the input and output are the unique empty Boolean string.

QAlgorithms.Papers.Independent.Intakethird100.P39.fittedInteriorCost

For any natural numbers $k,m$, this defines the real number

$$C(k,m) =(13k-8)\left((m+2)\frac{215}{100}-\frac{448}{100}\right) +\begin{cases}0&m=1,\\1&m\ne1\end{cases} (13k+3)\left(m\frac{69}{100}+\frac{6}{100}\right).$$

Here $k$ and $m$ are converted to real numbers before the displayed arithmetic is performed, so the subtractions are ordinary real subtractions. Both arguments may be zero; the second summand is suppressed exactly when $m=1$, including no suppression when $m=0$.

QAlgorithms.Papers.Independent.Intakethird100.P39.fourierCount

For every finite list $c$ of block-step records, this defines a natural number equal to the number of occurrences of Fourier-step records in $c$, irrespective of their offsets or widths. Phase-swap, truncated phase-swap, and swap records contribute zero. Repeated occurrences are counted separately, zero-width Fourier steps are counted, and the empty list has count zero.

QAlgorithms.Papers.Independent.Intakethird100.P39.halfBlockExpansion

For every block-step record $s$, this defines a list as follows: if $s$ is a phase-swap record with offset $o$, half-width $w$, and phase index $j$, put $h=\lfloor w/2\rfloor$ and return, in the displayed order, the four phase-swap records

$$(o+h,h,2j),\qquad (o,h,2j-1),\qquad (o+2h,h,2j+1),\qquad (o+h,h,2j),$$

where each triple specifies offset, half-width, and phase index. Subtraction is natural-number subtraction, so $2j-1=0$ when $j=0$. There is no requirement that $w$ be even or positive: odd widths are divided with rounding down, and $w=0$ or $w=1$ gives $h=0$ while still returning all four records. If $s$ is a Fourier, swap, or truncated phase-swap record, the result is the singleton list containing $s$ unchanged.

QAlgorithms.Papers.Independent.Intakethird100.P39.jordanMatrix

For any type $R$ equipped with a designated element $0_R$ and a designated element $1_R$, and any natural number $\ell$, this defines an $(\ell+1)\times(\ell+1)$ matrix with entries in $R$, whose rows and columns are indexed by $0,\ldots,\ell$, by

$$J_{ij}= \begin{cases} 1_R&i=j\ \text{or }i=j+1,\\ 0_R&\text{otherwise}. \end{cases}$$

Thus the main diagonal and the immediately lower diagonal receive $1_R$. No algebraic laws or distinction between $0_R$ and $1_R$ are assumed. The case $\ell=0$ is included and gives the one-entry matrix $[1_R]$.

QAlgorithms.Papers.Independent.Intakethird100.P39.marginalDemand

For arbitrary natural numbers $n,m$, define the real number

$$\operatorname{marginalDemand}(n,m) = 4^n+1-2\cdot4^{\,m-\lfloor m/2\rfloor} -\left\lfloor\frac nm\right\rfloor(4^m-1).$$

The quotient $n/m$ is computed in the natural numbers before being converted to a real number, and $m-\lfloor m/2\rfloor$ is natural-number subtraction, truncated at zero. Natural-number division by zero is zero, so the definition includes $m=0$ and gives $\operatorname{marginalDemand}(n,0)=4^n-1$. The additions and subtractions outside exponents are real arithmetic, and the value need not be nonnegative.

QAlgorithms.Papers.Independent.Intakethird100.P39.marginalGateBound

For every pair of natural numbers $n,m$, this defines an integer $G(n,m)$ by

$$G(n,m)= \left\lceil \frac{4^n+1-2\cdot4^{m-h}-q(4^m-1)} {4^m-4^h-4^{m-h}+1} \right\rceil+q, \qquad h=\left\lfloor\frac m2\right\rfloor,$$

where $q$ is natural-number division $n/m$: it equals $\lfloor n/m\rfloor$ when $m>0$, and equals $0$ when $m=0$. The fraction is evaluated in $\mathbb R$, and the ceiling is the least integer greater than or equal to that real number. Division by zero in this formula is defined to give zero. There are no positivity or divisibility assumptions on $n,m$; in particular, $G(n,0)=0$ and $G(n,1)=n$, since the denominator is zero in both cases.

QAlgorithms.Papers.Independent.Intakethird100.P39.marginalIncrement

For every natural number $m$, define the real number

$$\operatorname{marginalIncrement}(m) = 4^m-4^{\lfloor m/2\rfloor} -4^{\,m-\lfloor m/2\rfloor}+1.$$

Here $m/2$ is natural-number division, and the subtraction in the exponent is natural-number subtraction truncated at zero; the other subtractions are real arithmetic. The definition includes $m=0$ and $m=1$, for both of which its value is zero.

QAlgorithms.Papers.Independent.Intakethird100.P39.marginalSlotBound

For every pair of natural numbers $n,m$, this defines an integer $S(n,m)$ by

$$S(n,m)=1+ \left\lceil \frac{4^n+1-2\cdot4^{m-h}-q(4^m-1)} {q\bigl(4^m-4^h-4^{m-h}+1\bigr)} \right\rceil, \qquad h=\left\lfloor\frac m2\right\rfloor,$$

where $q$ is natural-number division $n/m$, with $q=0$ when $m=0$. The fraction is evaluated in $\mathbb R$, division by zero gives zero, and the ceiling takes its value in $\mathbb Z$. All natural $n,m$, including zero, are allowed. In particular, the value is $1$ whenever $q=0$ or $m\in\{0,1\}$, so it is $1$ when $n<m$ and when $n=0$.

QAlgorithms.Papers.Independent.Intakethird100.P39.panelA

This defines a list of $25$ phase-swap steps. In order, take $b=0,1,2,3,4$, and for each fixed $b$, take $a=4,3,2,1,0$; append the phase-swap step whose offset is $a+b$, whose half-width is $1$, and whose phase index is $1+a+b$. These are ordered list entries, so repeated offsets or phase indices remain separate occurrences.

QAlgorithms.Papers.Independent.Intakethird100.P39.panelB

This defines a list of $25$ block steps, ordered by $b=0,1,2,3,4$ and, within each fixed $b$, by $a=4,3,2,1,0$. The entry for $(a,b)$ is a phase-swap step of offset $a+b$, half-width $1$, and phase index $6+a+b$ if $6+a+b\le10$, equivalently $a+b\le4$; otherwise it is a swap step of offset $a+b$ and half-width $1$. Thus the equality case $a+b=4$ selects a phase-swap step, and every occurrence is retained in the specified order.

QAlgorithms.Papers.Independent.Intakethird100.P39.panelC

This defines a list of $25$ swap steps. In order, take $b=0,1,2,3,4$, and for each fixed $b$, take $a=4,3,2,1,0$; append the swap step with offset $a+b$ and half-width $1$. Repeated offsets are retained as separate list entries.

QAlgorithms.Papers.Independent.Intakethird100.P39.panelStep

For any natural numbers $o,p,c$, representing an offset, angle power, and cutoff, respectively, this defines a block-step record: it is a phase-swap step with offset $o$, half-width $1$, and phase index $p$ when $p\le c$, and a swap step with offset $o$ and half-width $1$ when $p>c$. Equality with the cutoff therefore selects the phase-swap branch. All three arguments may be zero, and the definition imposes no condition that the step fit within any particular register.

QAlgorithms.Papers.Independent.Intakethird100.P39.phaseCount

For every natural number $j$ and finite list $c$ of block-step records, this defines the number of occurrences in $c$ of phase-swap records whose phase index equals $j$, irrespective of their offsets or half-widths. Fourier, swap, and truncated phase-swap records contribute zero, including truncated phase-swap records whose phase index is $j$. Repeated occurrences are counted separately; $j=0$ and zero half-widths are allowed, and the empty list has count zero.

QAlgorithms.Papers.Independent.Intakethird100.P39.phaseTotal

For every finite list $c$ of block-step records, this defines the number of occurrences of phase-swap records in $c$, regardless of their offsets, half-widths, or phase indices. Fourier, swap, and truncated phase-swap records contribute zero. Repeated occurrences and phase-swap records with zero half-width or zero phase index are counted, and the empty list has count zero.

QAlgorithms.Papers.Independent.Intakethird100.P39.placeBlock

For every natural number $r$, every complex matrix $A$ indexed by Boolean strings of length $r$, and all natural numbers $n,o$, this defines a complex matrix $P$ indexed by Boolean strings of length $n$. If $o+r\le n$, define $x^{[o,r]}_i=x_{o+i}$ for $0\le i<r$; then

$$P_{y,x}= \begin{cases} A_{y^{[o,r]},x^{[o,r]}}, &y_a=x_a\text{ for every }a\in\{0,\ldots,n-1\} \setminus\{o,\ldots,o+r-1\},\\ 0,&\text{otherwise}. \end{cases}$$

If $o+r>n$, then $P$ is the identity matrix, with entry $1$ when $y=x$ and $0$ otherwise. No unitarity assumption is imposed on $A$. Zero sizes are allowed: when $r=0$ and $o\le n$, the result is the identity matrix multiplied by the sole entry of $A$; when $r=0$ and $o>n$, it is the identity regardless of that entry.

QAlgorithms.Papers.Independent.Intakethird100.P39.qftAssembly

For any natural numbers $m$ and $k$, this defines the list obtained by concatenating, in increasing order of $t=0,1,\ldots,k-1$, the following lists: phase-swap steps with offset $sm$, half-width $m$, and phase index $s+1$, in decreasing order $s=t-1,\ldots,0$, followed by a Fourier step with offset $0$ and width $m$. For $t=0$, that constituent list contains just the Fourier step. When $k=0$, the entire list is empty; when $k=1$, it contains just one Fourier step. Zero is also allowed for $m$, producing zero offsets and widths without removing any records.

QAlgorithms.Papers.Independent.Intakethird100.P39.qftAssemblyII

For any natural numbers $m,k$, put $h=\lfloor m/2\rfloor$. This defines a list by taking $t=0,\ldots,k-1$ in increasing order and, for each $t$, taking $s=t-1,\ldots,0$ in decreasing order, appending the four phase-swap records

$$(sm+h,h,2s+2),\qquad (sm,h,2s+1),\qquad (sm+2h,h,2s+3),\qquad (sm+h,h,2s+2)$$

for each such $s$, and then appending one Fourier record with offset $0$ and width $m$. Each phase-swap triple specifies offset, half-width, and phase index. When $t=0$, only the Fourier record is appended. No positivity or evenness assumption is imposed on $m$: its division by two rounds down, and $m=0$ or $m=1$ gives zero half-widths for all generated phase-swap records. When $k=0$, the list is empty; when $k=1$, it consists solely of the Fourier record.

QAlgorithms.Papers.Independent.Intakethird100.P39.qftInsertion

For any natural numbers $m$ and $t$, this defines a list of block-step records consisting, in order, of a phase-swap step with offset $sm$, half-width $m$, and phase index $s+1$ for each $s=t-1,t-2,\ldots,0$, followed by one Fourier step with offset $0$ and width $m$. When $t=0$, there are no phase-swap steps and the list consists solely of that Fourier step. The value $m=0$ is allowed: all offsets and widths are then zero, while the phase indices remain $t,t-1,\ldots,1$.

QAlgorithms.Papers.Independent.Intakethird100.P39.quality

For arbitrary real numbers $F,T,T_R$, define

$$\operatorname{quality}(F,T,T_R)=F\exp\!\left(\frac{-T}{T_R}\right).$$

There are no sign or nonzero assumptions on these arguments. Division is total, with division by zero equal to zero, so $\operatorname{quality}(F,T,0)=F$ for every $F,T$.

QAlgorithms.Papers.Independent.Intakethird100.P39.secondHalf

For every natural number $m$ and every Boolean string $x$ indexed by $0,\ldots,2m-1$, this defines a Boolean string of length $m$ whose coordinate at each $0\le i<m$ is $x_{m+i}$. Thus its coordinates are $(x_m,\ldots,x_{2m-1})$. When $m=0$, both the input and output are the unique empty Boolean string.

QAlgorithms.Papers.Independent.Intakethird100.P39.specialUnitaryTangent

For every type $\iota$ equipped with a finite enumeration, define the real vector subspace of complex matrices indexed by $\iota$ to be

$$\left\{A\in\mathbb C^{\iota\times\iota}:A^\ast=-A\ \text{and}\ \operatorname{tr}(A)=0\right\},$$

where $A^\ast$ is the conjugate transpose. Thus membership requires both skew-Hermitian symmetry and zero complex trace, and scalar multiplication in this subspace is by real numbers. The index type may be empty; then the matrix space and this subspace each contain only the zero matrix.

QAlgorithms.Papers.Independent.Intakethird100.P39.tensorLeftTangent

For arbitrary natural numbers $a,b$, define a real vector subspace of complex matrices indexed by $\{0,\ldots,a-1\}\times\{0,\ldots,b-1\}$ as

$$\operatorname{span}_{\mathbb R} \left\{A\otimes I_b: A\in\mathbb C^{a\times a},\ A^\ast=-A,\ \operatorname{tr}(A)=0\right\}.$$

Here $I_b$ is the $b\times b$ identity matrix, $\otimes$ is the Kronecker product, and the real span consists of finite real linear combinations of the displayed matrices. Either $a$ or $b$ may be zero; in either case the product index set is empty and the resulting subspace contains only the zero matrix.

QAlgorithms.Papers.Independent.Intakethird100.P39.tensorRightTangent

For arbitrary natural numbers $a,b$, define a real vector subspace of complex matrices indexed by $\{0,\ldots,a-1\}\times\{0,\ldots,b-1\}$ as

$$\operatorname{span}_{\mathbb R} \left\{I_a\otimes B: B\in\mathbb C^{b\times b},\ B^\ast=-B,\ \operatorname{tr}(B)=0\right\}.$$

Here $I_a$ is the $a\times a$ identity matrix, $\otimes$ is the Kronecker product, and the real span consists of finite real linear combinations of the displayed matrices. Either $a$ or $b$ may be zero; in either case the product index set is empty and the resulting subspace contains only the zero matrix.

QAlgorithms.Papers.Independent.Intakethird100.P39.traceFidelity

For every natural number $n$ and arbitrary complex matrices $U,V$ indexed by the set $Q_n=\{0,1\}^n$ of length-$n$ bit strings, define

$$\operatorname{traceFidelity}(U,V)=\frac{\operatorname{Re}\operatorname{tr}(V^\ast U)}{2^n},$$

where $V^\ast$ is the conjugate transpose of $V$. No unitarity assumption is imposed. The definition includes $n=0$, when $Q_0$ contains one empty bit string and the matrices are $1\times1$.

QAlgorithms.Papers.Independent.Intakethird100.P39.truncateBlockStep

For every natural-number cutoff $C$ and block-step record $s$, this defines a new record as follows: if $s$ is a phase-swap record with offset $o$, half-width $w$, and phase index $j$, it becomes a swap record with offset $o$ and half-width $w$ when $C<(j-1)w+1$, and otherwise becomes a truncated phase-swap record with offset $o$, half-width $w$, phase index $j$, and cutoff $C$. The subtraction $j-1$ is natural-number subtraction, so the threshold is $1$ when $j=0$; it is also $1$ whenever $w=0$. In particular, cutoff zero turns every phase-swap record into a swap record. Fourier, swap, and already truncated phase-swap records are returned unchanged, including their existing parameters.

QAlgorithms.Papers.Independent.Intakethird100.P39.truncatedCpSwap

For all natural numbers $m,j,c$, where $c$ is the cutoff, this defines a complex matrix $T_{m,j,c}$ indexed by Boolean strings of length $2m$. Write $d=\max(j-1,0)$, reflecting natural-number subtraction, and for $0\le a,b<m$ set $e_{a,b}=dm+1+a+b$. For a column string $x$, define the real number

$$\Phi_{m,j,c}(x)= \sum_{a=0}^{m-1}\sum_{b=0}^{m-1} \begin{cases} \displaystyle\frac{\pi}{2^{e_{a,b}}}, &x_a=\mathrm{true},\ x_{m+b}=\mathrm{true},\ e_{a,b}\le c,\\ 0,&\text{otherwise}. \end{cases}$$

Let $E_m(x)$ have coordinates $x_{m+i}$ for $i<m$ and $x_{i-m}$ for $m\le i<2m$. The matrix entries are

$$(T_{m,j,c})_{y,x}= \begin{cases} \exp\!\bigl(\mathrm i\,\Phi_{m,j,c}(x)\bigr),&y=E_m(x),\\ 0,&y\ne E_m(x). \end{cases}$$

All natural values are allowed, including $j=0$, for which $d=0$. For $c=0$, every phase summand vanishes, so the entries are $1$ exactly when $y=E_m(x)$. For $m=0$, the matrix is the $1\times1$ matrix with entry $1$.

QAlgorithms.Papers.Independent.Intakethird100.P39.truncatedQftAssembly

For any natural numbers $m,k,C$, this defines a list by taking $t=0,\ldots,k-1$ in increasing order and, within each $t$, taking $s=t-1,\ldots,0$ in decreasing order: at each such $s$, append a swap record with offset $sm$ and half-width $m$ if $C<sm+1$, and otherwise append a truncated phase-swap record with offset $sm$, half-width $m$, phase index $s+1$, and cutoff $C$; after these records for each $t$, append a Fourier record with offset $0$ and width $m$. For $t=0$, only the Fourier record is appended. When $k=0$, the list is empty; when $k=1$, it consists solely of the Fourier record. Cutoff zero selects the swap case at every phase position. The value $m=0$ is also allowed: all offsets and widths are then zero, and every phase position selects the swap case for $C=0$ and the truncated phase-swap case for $C\ge1$.