Definitions for Universal Quantum Emulator

QAlgorithms.Papers.Independent.Intakethird100.P67.BinaryEmulatorFamily

This abbreviates the type of all families $B$ that, for every pair of natural numbers $n,k$, every anchor $a\in\{0,\ldots,k-1\}$, every three natural numbers $q,T,m$, and every history $h:\{0,\ldots,T-1\}\to\{0,\ldots,k-1\}$, return a sample circuit on $n$-qubit registers with sample labels in $\mathrm{Bool}\times\{0,\ldots,k-1\}$. Such a circuit consists of a natural number $N$ of physical qubits, a natural number $s$ of sample copies, an injective map placing the $n$ input wires and the $sn$ sample wires into the $N$ physical wires, a Boolean-and-index label for each sample copy, a fixed Boolean value for every physical wire, and a list of elementary gates. An elementary gate is either an arbitrary one-qubit unitary or a gate on four distinct wires that swaps the last two wires exactly when the first two are both true. Given input and sample matrices, initialization places them on their respective ports and puts all remaining wires in their designated computational-basis states; the output applies the gates in list order and traces out every wire except the input ports. This abbreviation imposes no resource, correctness, or computability condition. All natural parameters may be zero; when $k=0$, there is no anchor argument to supply.

QAlgorithms.Papers.Independent.Intakethird100.P67.ElementaryGate

For every natural number $N$, an elementary gate on $N$ wires is one of two kinds: a choice of a wire $q\in\{0,\ldots,N-1\}$ together with a unitary complex matrix $U$ indexed by the two Boolean values, or an injective assignment $w:\{0,1,2,3\}\hookrightarrow\{0,\ldots,N-1\}$ of four distinct wires. The second kind carries no additional matrix parameter. The definition permits $N=0$, when there are no elementary gates; the four-wire kind is available only when $N\ge4$.

QAlgorithms.Papers.Independent.Intakethird100.P67.EmulatorFamily

An emulator family is a function that, for every pair of natural numbers $n,k$, every anchor $a\in\{0,\ldots,k-1\}$, every pair of natural numbers $T,m$, and every sequence $h:\{0,\ldots,T-1\}\to\{0,\ldots,k-1\}$, returns a sample circuit on $n$-wire registers whose labels belong to $\{0,\ldots,k-1\}$. Such a circuit specifies its own physical wire count, number of record registers, injective allocation of the input and record ports, Boolean-label pairs for its records, auxiliary Boolean assignment, and finite list of one-wire unitary or four-wire controlled-swap gates. There are no resource bounds or correctness conditions and no required relationship between $T,m,h$ and the returned circuit. The case $T=0$ uses the unique empty sequence; $n=0$ and $m=0$ are allowed. When $k=0$, there is no anchor argument, so no circuit is required for that value of $k$.

QAlgorithms.Papers.Independent.Intakethird100.P67.Generates

For a finite index type $I$ with decidable equality, a finite label type $K$, and arbitrary complex $I\times I$ matrices $S_k$, let $\mathcal A_S$ be the complex linear span of all nonempty finite ordered products of the $S_k$, allowing repeated labels, and let $\Pi_S=f(\sum_k S_k)$ in real continuous functional calculus, with $f(0)=0$ and $f(x)=1$ for $x\neq0$. This defines the assertion that, for every complex $I\times I$ matrix $X$, $X\in\mathcal A_S$ if and only if $\Pi_S X\Pi_S=X$. For a Hermitian sum, $\Pi_S$ projects onto its nonzero eigenspaces; for a non-Hermitian sum it is zero, so the assertion then requires $\mathcal A_S=\{0\}$. An empty label type satisfies this assertion.

QAlgorithms.Papers.Independent.Intakethird100.P67.InSampleSupport

For a finite index type $I$ with decidable equality, a finite label type $K$, arbitrary complex $I\times I$ matrices $S_k$, and an arbitrary complex $I\times I$ matrix $\rho$, this defines the assertion $\Pi_S\rho\Pi_S=\rho$, where $\Pi_S=f(\sum_kS_k)$ in real continuous functional calculus, with $f(0)=0$ and $f(x)=1$ for nonzero real $x$. If the sum is Hermitian, $\Pi_S$ projects onto its nonzero eigenspaces; if it is not Hermitian, $\Pi_S=0$. No positivity or trace condition is imposed on $\rho$. In particular, when $K$ is empty or the sum is non-Hermitian, the assertion is equivalent to $\rho=0$.

QAlgorithms.Papers.Independent.Intakethird100.P67.ProjectiveFamily

For finite index types $I,A$, with decidable equality on $I$, and any family $P:A\to\mathbb C^{I\times I}$, this predicate means that every $P_a$ is Hermitian and satisfies $P_a^2=P_a$, every two distinct labels $a,b\in A$ satisfy $P_aP_b=0$, and

$$\sum_{a\in A}P_a=\mathrm{Id}.$$

Zero projectors are allowed. If $A$ is empty, the individual and pairwise conditions are vacuous and the final condition is $0=\mathrm{Id}$, which holds precisely when $I$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P67.SampleCircuit.initial

For any natural number $n$, label type $K$, sample circuit $C$ with $N$ physical wires and $c$ additional registers, arbitrary matrices $\rho$ and $R_{b,k}$ on $n$-bit strings, this definition constructs a matrix on $N$-bit strings as follows. Write $x_{\mathrm{in}}$ for the restriction of $x$ to the distinguished input ports and $x_r$ for its restriction to additional register $r$, and similarly for $y$; write $u$ for the circuit’s specified auxiliary Boolean assignment. Then

$$C_{\mathrm{initial}}(x,y) =\rho(x_{\mathrm{in}},y_{\mathrm{in}}) \prod_{r<c}R_{C.\mathrm{labels}(r)}(x_r,y_r) \begin{cases} 1,&x_q=u_q\ \text{and}\ y_q=u_q \text{ for every wire }q\text{ outside all ports},\\ 0,&\text{otherwise}. \end{cases}$$

No positivity or trace assumptions are imposed on the supplied matrices. The auxiliary assignment on port wires does not enter this expression, and when $c=0$ the product is $1$; when $n=0$, the supplied register matrices are $1\times1$ matrices.

QAlgorithms.Papers.Independent.Intakethird100.P67.SampleCircuit

For a natural number $n$ and an arbitrary label type $K$, a sample circuit consists of natural numbers $N$ and $c$, an injection from the disjoint union $\{0,\ldots,n-1\}\sqcup(\{0,\ldots,c-1\}\times\{0,\ldots,n-1\})$ into the $N$ physical wires, a label $(b_r,k_r)\in\{\mathrm{false},\mathrm{true}\}\times K$ for each $r<c$, a Boolean assignment to all $N$ wires, and a finite ordered list of elementary gates on those wires. The injection allocates mutually distinct wires to one distinguished $n$-wire register and to each of the $c$ additional $n$-wire registers, so $(c+1)n\le N$. Labels may repeat. Zero values of $n$, $N$, or $c$, and an empty gate list, are allowed whenever the specified injection and labels exist; no normalization or correctness conditions are included.

QAlgorithms.Papers.Independent.Intakethird100.P67.SampleCircuit.output

For any natural number $n$, label type $K$, sample circuit $C$, arbitrary record matrices $R_{b,k}$, and arbitrary input matrix $\rho$, let $G_1,\ldots,G_s$ be the matrices of its elementary gates in list order: a one-wire gate applies its specified unitary on that wire and preserves every other bit, while a four-wire gate swaps its last two specified wires exactly when its first two specified bits are true. Set $V=G_s\cdots G_1$, with $V=1$ for an empty list, and set $X=VAV^\dagger$, where

$$A(x,y)=\rho(x_{\mathrm{in}},y_{\mathrm{in}}) \prod_{r<C.\mathrm{copies}} R_{C.\mathrm{labels}(r)}(x_r,y_r)$$

when both $x$ and $y$ equal the prescribed auxiliary assignment outside all ports, and $A(x,y)=0$ otherwise. Here the restrictions refer to the distinguished input ports and the additional register ports of $C$. The output entry at $n$-bit strings $i,j$ is

$$\sum_{\substack{x,y\text{ on the physical wires}\\ x_{\mathrm{in}}=i,\ y_{\mathrm{in}}=j\\ x_q=y_q\text{ on every non-input wire}}}X(x,y).$$

Thus the definition traces out every physical wire outside the distinguished input register, including the record registers. It requires no positivity or normalization of the supplied matrices and includes zero-sized registers and empty gate lists.

QAlgorithms.Papers.Independent.Intakethird100.P67.addressedReflection

For an index type $I$ with decidable equality, any vector $\phi\in\mathbb C^I$, and natural numbers $q,t$, put $N=2^q$. This defines a matrix on $I\times\{0,\ldots,N-1\}$ with zero entries between different address values; its block at address $r$ is $I_I-2\phi\phi^\ast$ if $r=t$, and $I_I$ otherwise, where $(\phi\phi^\ast)_{ij}=\phi_i\overline{\phi_j}$. No normalization of $\phi$ is required. If $t\ge N$, the whole matrix is the identity; for $q=0$, its sole address block is $I_I-2\phi\phi^\ast$ when $t=0$, and the identity otherwise.

QAlgorithms.Papers.Independent.Intakethird100.P67.basisPhase

For a finite index type $I$ with decidable equality, a natural number $d$, and any family $\theta_k\in\mathbb C^I$ indexed by $0\le k<d$, put $H_{ij}=\sum_{k=0}^{d-1}k\,(\theta_k)_i\overline{(\theta_k)_j}$. This defines the matrix on $I\times\{0,\ldots,d-1\}$ whose entry at row $(i,r)$ and column $(j,s)$ is $[\exp(\mathrm{i}(2\pi r/d)H)]_{ij}$ when $r=s$, and zero otherwise, where the exponential is the matrix exponential. No normalization or orthogonality of the $\theta_k$ is assumed. When $d=0$, the matrix has an empty index set.

QAlgorithms.Papers.Independent.Intakethird100.P67.binaryHistory

For a finite index type $I$ with decidable equality, an index type $K$, natural numbers $T,q$, any family $\phi_k\in\mathbb C^I$, an anchor $a\in K$, and a sequence $h_0,\ldots,h_{T-1}\in K$, put $N=2^q$, $P=\phi_a\phi_a^\ast$, and let $C$ be the address shift with entries $C_{rs}=\mathbf1_{\{r=(s+1)\bmod N\}}$. Set $B=P\otimes I_N+(I_I-P)\otimes C$, and let $R_j$ be block diagonal in the address, with block $I_I-2\phi_{h_j}\phi_{h_j}^\ast$ at address $j+1$ and identity blocks elsewhere. This defines $(R_{T-1}B)\cdots(R_0B)$, with the empty product equal to the identity when $T=0$. No vectors are required to be normalized, and no relation between $T$ and $2^q$ is imposed: when $j+1\ge2^q$, $R_j$ is the identity while the factor $B$ remains.

QAlgorithms.Papers.Independent.Intakethird100.P67.binaryMeasure

For an index type $I$ with decidable equality, any vector $\phi\in\mathbb C^I$, and any natural number $q$, put $N=2^q$ and $P_{ij}=\phi_i\overline{\phi_j}$. This defines the complex matrix on $I\times\{0,\ldots,N-1\}$ with entry $P_{ij}\delta_{rs}+(\delta_{ij}-P_{ij})\mathbf1_{\{r=(s+1)\bmod N\}}$ at row $(i,r)$ and column $(j,s)$, where $\delta$ is the Kronecker delta. No normalization of $\phi$ is assumed. When $q=0$, this matrix is the identity.

QAlgorithms.Papers.Independent.Intakethird100.P67.bridgeSamples

For index types $K$ and $I$, any family of complex matrices $S_k$ indexed by $I\times I$, any vector $\phi\in\mathbb C^I$, and any $\alpha,\beta\in\mathbb C$, this defines a matrix-valued function on an optional pair consisting of a Boolean and an element of $K$. Put $c_{\mathrm{false}}=\alpha$ and $c_{\mathrm{true}}=\beta$. At the absent value, its entry from column $(j,c)$ to row $(i,b)$ is $\phi_i c_b\,\overline{\phi_j c_c}$. At a present value $(b_0,k)$, that entry is $(S_k)_{ij}$ if $b=c=b_0$, and zero otherwise. No normalization of $\phi,\alpha,\beta$, or positivity or trace condition on $S_k$, is required.

QAlgorithms.Papers.Independent.Intakethird100.P67.coherentErasureChannel

For finite index types $I$ and $L$, arbitrary real weights $p_\ell$, arbitrary complex matrices $W_\ell$ indexed by $I\times\{\mathrm{false},\mathrm{true}\}$, and an arbitrary complex matrix $\rho$ indexed by $I$, this defines

$$\sum_{\ell\in L}p_\ell\, \operatorname{Tr}_{\mathrm{bit}}\!\left[ W_\ell\bigl(\rho\otimes mm^\dagger\bigr)W_\ell^\dagger \right], \qquad m_{\mathrm{false}}=\frac1{\sqrt2}, \quad m_{\mathrm{true}}=-\frac1{\sqrt2},$$

where $\dagger$ denotes conjugate transpose and the partial trace means $(\operatorname{Tr}_{\mathrm{bit}}X)_{i,i'}=\sum_bX_{(i,b),(i',b)}$. The real weights are regarded as complex scalars in this matrix sum. No normalization or positivity of $p$ or $\rho$, and no unitarity of $W_\ell$, is required. If $L$ is empty, the result is the zero matrix.

QAlgorithms.Papers.Independent.Intakethird100.P67.compressedReflection

For finite index types $I,K$, with decidable equality on $I$, an arbitrary family $\phi_k\in\mathbb C^I$, and elements $a,k\in K$, this defines

$$Q\bigl(\mathbf1-2\phi_k\phi_k^\dagger\bigr)Q, \qquad Q=\Pi-\phi_a\phi_a^\dagger, \qquad \Pi=f\!\left(\sum_{r\in K}\phi_r\phi_r^\dagger\right), \quad f(t)= \begin{cases} 0,&t=0,\\ 1,&t\ne0. \end{cases}$$

Here $(vv^\dagger)_{i,i'}=v_i\overline{v_{i'}}$, and $f$ is applied to the matrix by the real continuous functional calculus, so $\Pi$ is the spectral projection onto the nonzero eigenspaces of the positive semidefinite sum. The vectors need not be normalized or linearly independent, and $a$ and $k$ may coincide. If every $\phi_r$ is zero, the defined matrix is zero.

QAlgorithms.Papers.Independent.Intakethird100.P67.compressedReflectionChannel

For finite index types $I,K$ with decidable equality, any family $\phi:K\to\mathbb C^I$, an anchor $a\in K$, and any complex matrix $\rho$ indexed by $I$, define $D_k$ by $(D_k)_{ij}=\phi_k(i)\overline{\phi_k(j)}$, and let $\Pi=f(\sum_{k\in K}D_k)$, using matrix functional calculus with $f(0)=0$ and $f(x)=1$ for $x\ne0$. Put $Q=\Pi-D_a$, $C_k=Q(\mathrm{Id}-2D_k)Q$, and $p_a(k)=0$ when $k=a$, otherwise $p_a(k)=1/(|K|-1)$. The definition returns

$$\sum_{k\in K}p_a(k)\,C_k\rho C_k.$$

The vectors need not be normalized, and $\rho$ need not be a density matrix. The anchor makes $K$ nonempty; if $K$ has one element, the result is zero. The subtraction in $|K|-1$ is natural-number subtraction, and division uses the convention $1/0=0$.

QAlgorithms.Papers.Independent.Intakethird100.P67.conjugateBasis

For an index type $I$, a natural number $d$, any family $\theta_0,\ldots,\theta_{d-1}\in\mathbb C^I$, and an index $0\le j<d$, this defines the vector $\sum_{k=0}^{d-1}(\sqrt d)^{-1}\exp(2\pi\mathrm{i}kj/d)\,\theta_k$. The vectors $\theta_k$ are not required to be normalized, orthogonal, or a basis. The parameter $d=0$ is included, but then there is no index $j$ at which to evaluate this definition.

QAlgorithms.Papers.Independent.Intakethird100.P67.coordinateExpansion

For a finite index type $I$ with decidable equality, an index type $K$, any natural number $T$, family $\phi:K\to\mathbb C^I$, anchor $a\in K$, history $h:\{0,\ldots,T-1\}\to K$, and vector $\psi\in\mathbb C^I$, define $(D_k)_{ij}=\phi_k(i)\overline{\phi_k(j)}$, $r_0=\psi$, and $r_{t+1}=(\mathrm{Id}-2D_{h(t)})(\mathrm{Id}-D_a)r_t$. Let $u_{T,t}$ be the length-$T$ Boolean word whose bit $j$ is true exactly when $j<t$. The definition returns the vector $E$ indexed by pairs $(i,z)$, with $i\in I$ and $z$ a length-$T$ Boolean word, given by

$$E(i,z)= \sum_{t=0}^{T-1} \left(\sum_{j\in I}\overline{\phi_a(j)}\,r_t(j)\right) \phi_a(i)\,\mathbf1_{\{z=u_{T,t}\}} +r_T(i)\,\mathbf1_{\{z=u_{T,T}\}}.$$

Here $\mathbf1$ is the indicated equality indicator. No vectors are required to be normalized. For $T=0$, the sum is empty and $E(i,z)=\psi(i)$ for the unique empty word $z$.

QAlgorithms.Papers.Independent.Intakethird100.P67.densityConjugation

For a finite index type $I$ and arbitrary complex matrices $V,\rho$ indexed by $I\times I$, this defines their density conjugation to be $V\rho V^\dagger$, where $V^\dagger$ is the conjugate transpose. Neither unitarity of $V$ nor positivity or normalization of $\rho$ is assumed; the definition also applies when $I$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P67.doubleControlledSwap

For an index type $I$ with decidable equality, this defines a complex matrix indexed by $(I\times I)\times(\{\mathrm{false},\mathrm{true}\}\times\{\mathrm{false},\mathrm{true}\})$. Its entry at row $((i,j),(b,c))$ and column $((k,\ell),(b',c'))$ is zero unless $(b,c)=(b',c')$; when the Boolean pairs agree, the entry is $\mathbf1_{\{i=\ell,\ j=k\}}$ if both $b$ and $c$ are true, and $\mathbf1_{\{i=k,\ j=\ell\}}$ otherwise. Thus the two $I$-registers are swapped exactly in the block where both Boolean values are true. If $I$ is empty, the matrix is empty.

QAlgorithms.Papers.Independent.Intakethird100.P67.effectiveHamiltonian

For a coordinate index type $I$, any vector $\phi\in\mathbb C^I$, natural number $n$, and real coupling $c$, this defines the complex matrix

$$c(n+1)\phi\phi^\dagger, \qquad \bigl(c(n+1)\phi\phi^\dagger\bigr)_{ij} =c(n+1)\phi_i\overline{\phi_j}.$$

No normalization of $\phi$ or sign restriction on $c$ is imposed. In particular, $n=0$ gives $c\phi\phi^\dagger$, and $\phi=0$ gives the zero matrix.

QAlgorithms.Papers.Independent.Intakethird100.P67.elementaryMatrix

For every natural number $N$, this definition assigns a complex matrix, with rows and columns indexed by Boolean strings $x,y:\{0,\ldots,N-1\}\to\{\mathrm{false},\mathrm{true}\}$, to each elementary gate on $N$ wires. For a one-wire gate specified by $q$ and a unitary $2\times2$ matrix $U$, its entry is $U_{x_q,y_q}$ if $x_\ell=y_\ell$ for every $\ell\ne q$, and is zero otherwise. For a four-wire gate specified by an injection $w$, its entry is $1$ precisely when $x$ is obtained from $y$ by swapping the values on wires $w(2)$ and $w(3)$ if both $y_{w(0)}$ and $y_{w(1)}$ are true, and by leaving $y$ unchanged otherwise; every other entry is zero. In the swap case, the two replacement values are both taken from the original string $y$.

QAlgorithms.Papers.Independent.Intakethird100.P67.emulate

For finite index types $I,K$ with decidable equality, an arbitrary vector family $\phi_k\in\mathbb C^I$, an anchor $a\in K$, a complex matrix $U$ on $I$, a natural number $T$, and a matrix $\rho$ on $I$, this defines the matrix

$$\operatorname{Tr}_{\mathrm{anc}} \sum_{b\in\{\mathrm{false},\mathrm{true}\}} \sum_{h:\{0,\ldots,T-1\}\to K} \left(\prod_{j=0}^{T-1}p_{h(j)}\right) H_{\mathrm{out}}(h)^\dagger \left[ (U\phi_a)(U\phi_a)^\dagger\otimes \operatorname{Tr}_I\!\left( (P_b\otimes\mathbf1)H_{\mathrm{in}}(h) (\rho\otimes m_Tm_T^\dagger) H_{\mathrm{in}}(h)^\dagger(P_b^\dagger\otimes\mathbf1) \right) \right]H_{\mathrm{out}}(h).$$

Here $p_a=0$ and $p_k=1/(|K|-1)$ for $k\ne a$, with natural-number subtraction and reciprocal zero equal to zero; $P_{\mathrm{false}}=\phi_a\phi_a^\dagger$, $P_{\mathrm{true}}=\mathbf1-\phi_a\phi_a^\dagger$, and $m_T(z)=2^{-T/2}(-1)^{|\{j:z_j=\mathrm{true}\}|}$. Outer products have entries $v_i\overline{v_{i'}}$. To specify the history matrices, put $R_k=\mathbf1-2\phi_k\phi_k^\dagger$ and let $C(R)$ have entry $R_{i,i'}$ when both Boolean indices are true, $\delta_{i,i'}$ when both are false, and zero when they differ; set

$$E_k=C(R_k)(\mathbf1\otimes H)C(R_a), \qquad E'_k=(U\otimes\mathbf1_2)E_k(U\otimes\mathbf1_2)^\dagger, \qquad H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}.$$

Then $H_{\mathrm{in}}(h)$ and $H_{\mathrm{out}}(h)$ are the reverse-order products of $E_{h(j)}$ and $E'_{h(j)}$, respectively, each embedded on the system and bit $j$ by retaining its entries when all other bits agree and using zero otherwise. The inner partial trace sums equal $I$ indices, and the outer partial trace sums equal length-$T$ ancillary bitstrings. At $T=0$ the history products and weight are identities and $1$, respectively. If $K$ is a singleton and $T>0$, all history weights vanish. No normalization of $\phi_k$ or $\rho$, positivity of $\rho$, or unitarity of $U$ is assumed.

QAlgorithms.Papers.Independent.Intakethird100.P67.encodeUnary

For an index type $I$, natural numbers $q,T$, and any vector $v$ indexed by $I\times\{\mathrm{false},\mathrm{true}\}^T$, define $u_t$ to be the length-$T$ bit string whose coordinate $j$ is true exactly when $j<t$. This defines a vector $w$ indexed by $I\times\{0,\ldots,2^q-1\}$ by $w(i,r)=\sum_{t=0}^{T}\mathbf1_{\{r=t\}}v(i,u_t)$; equivalently, $w(i,r)=v(i,u_r)$ if $r\le T$, and zero otherwise. No condition $T<2^q$ is required: values associated with $t\ge2^q$ have no output address, and values of $v$ on bit strings other than the $u_t$ are unused. When $T=0$, only address zero can have a nonzero coordinate.

QAlgorithms.Papers.Independent.Intakethird100.P67.eraseProbability

For finite index types $I,L$, arbitrary real weights $p_\ell$, complex matrices $W_\ell$ on $I\times\{\mathrm{false},\mathrm{true}\}$, a vector $\phi\in\mathbb C^I$, a natural number $T$, and a matrix $\rho$ on $I$, this defines

$$\operatorname{Re}\operatorname{tr}\!\left(\phi\phi^\dagger\,\mathcal C^{\,T}(\rho)\right), \qquad \mathcal C(X)= \sum_{\ell\in L}p_\ell\, \operatorname{Tr}_{\mathrm{bit}}\!\left[ W_\ell(X\otimes mm^\dagger)W_\ell^\dagger \right].$$

Here $(vv^\dagger)_{i,i'}=v_i\overline{v_{i'}}$, $m=(1,-1)/\sqrt2$ in Boolean order $(\mathrm{false},\mathrm{true})$, and the partial trace has entries $\sum_bY_{(i,b),(i',b)}$. The exponent on $\mathcal C$ means $T$ successive applications of this function, with $\mathcal C^0$ the identity function. Thus at $T=0$ the value is $\operatorname{Re}\operatorname{tr}(\phi\phi^\dagger\rho)$. No hypotheses ensure that this real number is a probability: the weights, vector, matrices, and input are unrestricted.

QAlgorithms.Papers.Independent.Intakethird100.P67.erasureGate

For a finite index type $I$ with decidable equality, an arbitrary label type $K$, a family $\phi_k\in\mathbb C^I$, and labels $a,k\in K$, this defines the matrix $C(R_{\phi_k})(I_I\otimes H)C(R_{\phi_a})$ on $I\times\{\mathrm{false},\mathrm{true}\}$. Here $R_\phi=I_I-2\phi\phi^\dagger$, with $(\phi\phi^\dagger)_{ij}=\phi(i)\overline{\phi(j)}$; $C(V)$ preserves the Boolean coordinate and acts by $V$ on its true block and by the identity on its false block; and, in Boolean order $(\mathrm{false},\mathrm{true})$, $H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$. The rightmost factor acts first. The labels may coincide, and no normalization of the vectors is assumed.

QAlgorithms.Papers.Independent.Intakethird100.P67.gentleChannel

For finite index types $I,L,A$, with decidable equality on $I$, any real-valued function $p:L\to\mathbb R$, complex matrix families $V:L\to\mathbb C^{I\times I}$ and $P:A\to\mathbb C^{I\times I}$, and complex matrix $\rho$ indexed by $I$, set $B_{\ell,a}=V_\ell^\dagger P_aV_\ell$. The definition returns

$$\sum_{\ell\in L}p(\ell)\sum_{a\in A} B_{\ell,a}\rho B_{\ell,a}^\dagger.$$

Real weights are regarded as complex scalars. The definition imposes no positivity or normalization on $p$, no unitarity on $V$, no projector conditions on $P$, and no density-matrix conditions on $\rho$. If either summation index type is empty, the result is zero.

QAlgorithms.Papers.Independent.Intakethird100.P67.gentleProbability

For finite index types $I,L$, with decidable equality on $I$, an index type $A$, any function $p:L\to\mathbb R$, complex matrix families $V:L\to\mathbb C^{I\times I}$ and $P:A\to\mathbb C^{I\times I}$, complex matrix $\rho$ indexed by $I$, and selected label $a\in A$, the definition returns the real number

$$\sum_{\ell\in L}p(\ell)\, \operatorname{Re}\operatorname{tr} \left(P_aV_\ell\rho V_\ell^\dagger\right).$$

There are no distribution, unitarity, effect, projector, or density-matrix hypotheses on these arguments, so the definition itself does not require this number to lie in $[0,1]$. If $L$ is empty, it is zero.

QAlgorithms.Papers.Independent.Intakethird100.P67.historyUnitary

For a finite system index type $I$ with decidable equality, a label type $L$, a natural number $T$, a family of complex matrices $W_\ell$ indexed by $I\times\{\mathrm{false},\mathrm{true}\}$, and a history $h:\{0,\ldots,T-1\}\to L$, this defines the matrix

$$E_{T-1}\cdots E_1E_0, \qquad (E_j)_{(i,z),(i',z')}= \begin{cases} (W_{h(j)})_{(i,z_j),(i',z'_j)},&z_\ell=z'_\ell\text{ for every }\ell\ne j,\\ 0,&\text{otherwise}, \end{cases}$$

where $z,z'$ are bitstrings of length $T$. Thus the factor with index $0$ acts first under matrix multiplication on column vectors. For $T=0$, the result is the identity matrix. No unitarity assumption is imposed on the matrices $W_\ell$.

QAlgorithms.Papers.Independent.Intakethird100.P67.historyWeight

For a label type $L$, a natural number $T$, an arbitrary real-valued function $p:L\to\mathbb R$, and a history $h:\{0,\ldots,T-1\}\to L$, this defines the real number

$$\prod_{j=0}^{T-1}p(h(j)).$$

The function $p$ need not be nonnegative or sum to one. For $T=0$, the product is $1$, including when $L$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P67.increment

For every natural number $q$, put $N=2^q$. This defines the $N\times N$ complex matrix whose entry at row $x$ and column $y$ is one if $x=(y+1)\bmod N$, and zero otherwise, for $0\le x,y<N$. Thus it shifts each coordinate basis vector forward by one modulo $N$. In particular, $q=0$ gives the $1\times1$ identity matrix.

QAlgorithms.Papers.Independent.Intakethird100.P67.inputOutputRecords

For a label type $K$, a finite coordinate type $I$, any family of complex vectors $\phi_k\in\mathbb C^I$, and any complex matrix $U$ on $I$, this definition assigns to each Boolean-label pair $(b,k)$ the matrix

$$R_{b,k}= \begin{cases} U\,|\phi_k\rangle\langle\phi_k|\,U^\dagger,&b=\mathrm{true},\\ |\phi_k\rangle\langle\phi_k|,&b=\mathrm{false}, \end{cases} \qquad (|\phi_k\rangle\langle\phi_k|)_{ij} =\phi_k(i)\overline{\phi_k(j)}.$$

Neither normalization of the vectors nor unitarity of $U$ is assumed; an empty label type or empty coordinate type is allowed.

QAlgorithms.Papers.Independent.Intakethird100.P67.jointBranch

For finite index types $I,J,L$, with decidable equality on the system indices, arbitrary weights $p:L\to\mathbb R$, matrix families $W^{\mathrm{in}}_\ell$ on $I\times\{\mathrm{false},\mathrm{true}\}$ and $W^{\mathrm{out}}_\ell$ on $J\times\{\mathrm{false},\mathrm{true}\}$, vectors $\phi\in\mathbb C^I$ and $\phi_{\mathrm{out}}\in\mathbb C^J$, a natural number $T$, a Boolean $b$, and a matrix $\rho$ on $I$, this defines

$$\sum_{h:\{0,\ldots,T-1\}\to L} \left(\prod_{j=0}^{T-1}p(h(j))\right) H_{\mathrm{out}}(h)^\dagger \left[ \phi_{\mathrm{out}}\phi_{\mathrm{out}}^\dagger\otimes \operatorname{Tr}_I\!\left( (P_b\otimes\mathbf1)H_{\mathrm{in}}(h) (\rho\otimes m_Tm_T^\dagger) H_{\mathrm{in}}(h)^\dagger(P_b^\dagger\otimes\mathbf1) \right) \right]H_{\mathrm{out}}(h).$$

Here $P_{\mathrm{false}}=\phi\phi^\dagger$, $P_{\mathrm{true}}=\mathbf1-\phi\phi^\dagger$, outer products have entries $v_i\overline{v_{i'}}$, and $m_T(z)=2^{-T/2}(-1)^{|\{j:z_j=\mathrm{true}\}|}$. Each $H_{\mathrm{in/out}}(h)$ is $E_{T-1}\cdots E_0$, with $(E_j)_{(i,z),(i',z')}=(W^{\mathrm{in/out}}_{h(j)})_{(i,z_j),(i',z'_j)}$ if the bitstrings agree outside $j$, and zero otherwise; $\operatorname{Tr}_I$ sums equal system indices. No positivity, normalization, or unitarity hypotheses are imposed. At $T=0$ there is one empty history of weight $1$, even if $L$ is empty, and both history products are identities; if $L$ is empty and $T>0$, the sum is zero.

QAlgorithms.Papers.Independent.Intakethird100.P67.jointBranchHistory

For finite system index types $I,J$ with decidable equality, a label type $L$, a natural number $T$, arbitrary matrix families $W^{\mathrm{in}}_\ell$ on $I\times\{\mathrm{false},\mathrm{true}\}$ and $W^{\mathrm{out}}_\ell$ on $J\times\{\mathrm{false},\mathrm{true}\}$, vectors $\phi\in\mathbb C^I$ and $\phi_{\mathrm{out}}\in\mathbb C^J$, a history $h:\{0,\ldots,T-1\}\to L$, a Boolean $b$, and an arbitrary matrix $\rho$ on $I$, this defines

$$H_{\mathrm{out}}^\dagger \left[ \phi_{\mathrm{out}}\phi_{\mathrm{out}}^\dagger\otimes \operatorname{Tr}_I\!\left( (P_b\otimes\mathbf1)H_{\mathrm{in}} (\rho\otimes m_Tm_T^\dagger) H_{\mathrm{in}}^\dagger(P_b^\dagger\otimes\mathbf1) \right) \right]H_{\mathrm{out}}.$$

Here $P_{\mathrm{false}}=\phi\phi^\dagger$, $P_{\mathrm{true}}=\mathbf1-\phi\phi^\dagger$, $(vv^\dagger)_{i,i'}=v_i\overline{v_{i'}}$, and $m_T(z)=2^{-T/2}(-1)^{|\{j:z_j=\mathrm{true}\}|}$ for each length-$T$ bitstring $z$. Each $H_{\mathrm{in/out}}$ is the product $E_{T-1}\cdots E_0$, where $E_j$ has entry $(W^{\mathrm{in/out}}_{h(j)})_{(i,z_j),(i',z'_j)}$ when $z,z'$ agree outside $j$, and zero otherwise. The partial trace is $(\operatorname{Tr}_IX)_{z,z'}=\sum_iX_{(i,z),(i,z')}$. For $T=0$, both history products are identities and the ancillary space has one coordinate with $m_0=1$. No vector normalization, matrix positivity, or unitarity is assumed.

QAlgorithms.Papers.Independent.Intakethird100.P67.jointEmulator

For finite index types $I,J,L$, with decidable equality on the system indices, arbitrary real weights $p_\ell$, matrix families $W^{\mathrm{in}}_\ell$ on $I\times\{\mathrm{false},\mathrm{true}\}$ and $W^{\mathrm{out}}_\ell$ on $J\times\{\mathrm{false},\mathrm{true}\}$, vectors $\phi\in\mathbb C^I$ and $\phi_{\mathrm{out}}\in\mathbb C^J$, a natural number $T$, and a matrix $\rho$ on $I$, this defines

$$\sum_{b\in\{\mathrm{false},\mathrm{true}\}} \sum_{h:\{0,\ldots,T-1\}\to L} \left(\prod_{j=0}^{T-1}p(h(j))\right) H_{\mathrm{out}}(h)^\dagger \left[ \phi_{\mathrm{out}}\phi_{\mathrm{out}}^\dagger\otimes \operatorname{Tr}_I\!\left( (P_b\otimes\mathbf1)H_{\mathrm{in}}(h) (\rho\otimes m_Tm_T^\dagger) H_{\mathrm{in}}(h)^\dagger(P_b^\dagger\otimes\mathbf1) \right) \right]H_{\mathrm{out}}(h).$$

Here $P_{\mathrm{false}}=\phi\phi^\dagger$, $P_{\mathrm{true}}=\mathbf1-\phi\phi^\dagger$, $(vv^\dagger)_{i,i'}=v_i\overline{v_{i'}}$, and $m_T(z)=2^{-T/2}(-1)^{|\{j:z_j=\mathrm{true}\}|}$. Each $H_{\mathrm{in/out}}(h)=E_{T-1}\cdots E_0$, where $E_j$ acts through $W^{\mathrm{in/out}}_{h(j)}$ on the system and bit $j$: its entry is $(W^{\mathrm{in/out}}_{h(j)})_{(i,z_j),(i',z'_j)}$ when all other bits agree, and zero otherwise. The partial trace sums equal system indices. No normalization, positivity, or unitarity is required. For $T=0$, the sole history has weight $1$ and identity history matrices; for empty $L$ and positive $T$, the result is zero.

QAlgorithms.Papers.Independent.Intakethird100.P67.lambdaPerp

For finite index types $I,K$ with decidable equality, any family $\phi:K\to\mathbb C^I$, and an anchor $a\in K$, set $(D_k)_{ij}=\phi_k(i)\overline{\phi_k(j)}$, $\Pi=f(\sum_kD_k)$ by matrix functional calculus with $f(0)=0$ and $f(x)=1$ for $x\ne0$, and $C_k=(\Pi-D_a)(\mathrm{Id}-2D_k)(\Pi-D_a)$. With $p_a(a)=0$ and $p_a(k)=1/(|K|-1)$ for $k\ne a$, the definition returns the Euclidean operator norm

$$\left\|\sum_{k\in K}p_a(k)\,C_k\otimes\overline{C_k}\right\|_{2\to2},$$

where the bar means entrywise complex conjugation and $\otimes$ is the Kronecker product. No normalization of the vectors is required. If $K$ consists only of $a$, this value is zero; the reciprocal convention is $1/0=0$.

QAlgorithms.Papers.Independent.Intakethird100.P67.meanSampleDensity

For any index type $I$, finite index type $K$, and family $\phi:K\to\mathbb C^I$, the definition returns the complex matrix

$$M_{ij}=\frac1{|K|}\sum_{k\in K}\phi_k(i)\overline{\phi_k(j)}.$$

The vectors are arbitrary and need not have norm one. If $K$ is empty, the sum and the resulting matrix are zero, with the reciprocal of zero interpreted as zero.

QAlgorithms.Papers.Independent.Intakethird100.P67.minusRegister

For every natural number $T$, including $T=0$, this defines a complex vector indexed by Boolean strings $z:\{0,\ldots,T-1\}\to\{\mathrm{false},\mathrm{true}\}$, with coordinate $\prod_{j=0}^{T-1}c(z_j)$, where $c(\mathrm{false})=1/\sqrt2$ and $c(\mathrm{true})=-1/\sqrt2$. Equivalently, its coordinate is $2^{-T/2}(-1)^{|\{j:z_j=\mathrm{true}\}|}$. When $T=0$, there is one empty string and its coordinate is the empty product $1$.

QAlgorithms.Papers.Independent.Intakethird100.P67.minusVector

This defines the complex vector indexed by the two Boolean values whose false coordinate is $1/\sqrt2$ and whose true coordinate is $-1/\sqrt2$, namely $(1/\sqrt2,-1/\sqrt2)$ in Boolean order $(\mathrm{false},\mathrm{true})$.

QAlgorithms.Papers.Independent.Intakethird100.P67.mixedEmulate

For finite index types $I,K$, any family $S:K\to\operatorname{Mat}_I(\mathbb C)$, anchor $a\in K$, vector $\phi\in\mathbb C^I$, arbitrary matrices $U,\rho\in\operatorname{Mat}_I(\mathbb C)$, and natural number $T$, this defines the matrix whose entries are

$$|K|^{-T}\sum_{h:\{0,\ldots,T-1\}\to K} \int_{[0,1]^T} \left[ \operatorname{Tr}_{\mathrm{anc}} \left( V_{\mathrm{out}}^\dagger \left((U\phi)(U\phi)^\dagger\otimes\operatorname{Tr}_{I}X\right) V_{\mathrm{out}} \right) \right]_{ij}\,d\mathbf t.$$

For each history and parameter tuple, $V_{\mathrm{in}}=A_{T-1}\cdots A_0$, where $A_j$ acts on the system and Boolean register $j$ by $C(e^{-it_jS_{h_j}})(1\otimes H)C(e^{-i\pi S_a})$ and preserves the other registers; $C(M)$ applies $1$ in the false sector and $M$ in the true sector, and $H=2^{-1/2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$. Further,

$$m_T(z)=\prod_{j<T}\frac{(-1)^{z_j}}{\sqrt2},\qquad X=V_{\mathrm{in}}(\rho\otimes m_Tm_T^\dagger)V_{\mathrm{in}}^\dagger,\qquad V_{\mathrm{out}}=(U\otimes1)V_{\mathrm{in}}(U^\dagger\otimes1).$$

The partial traces sum matching indices of the indicated register, and the integral is entrywise with respect to product Lebesgue measure. The histories include occurrences of the anchor. No normalization, positivity, Hermitian, or unitarity hypotheses are imposed. The anchor requires $K\ne\varnothing$; $T=0$ is allowed, with one empty history, normalization factor $1$, and integration over the singleton empty tuple.

QAlgorithms.Papers.Independent.Intakethird100.P67.mixedGate

For a finite coordinate index type $I$, any family $S:K\to\operatorname{Mat}_I(\mathbb C)$, indices $a,k\in K$, and real number $t$, this defines

$$C\!\left(e^{-itS_k}\right)(1\otimes H) C\!\left(e^{-i\pi S_a}\right), \qquad H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},$$

on the system and a Boolean register ordered false, true. Here $C(M)$ preserves the Boolean register, applies the identity to the system when that register is false, and applies $M$ when it is true; the rightmost factor acts first. The matrices $S_k$ need not be Hermitian, and $t$ is unrestricted, so unitarity is not an input hypothesis.

QAlgorithms.Papers.Independent.Intakethird100.P67.mixedHistory

For a finite coordinate index type $I$, any index type $K$, family $S:K\to\operatorname{Mat}_I(\mathbb C)$, anchor $a\in K$, natural number $T$, history $h:\{0,\ldots,T-1\}\to K$, and real parameters $(t_j)_{j<T}$, this defines

$$A_{T-1}\cdots A_1A_0,$$

where $A_j$ acts on the system and Boolean register $j$ by

$$G_j=C(e^{-it_jS_{h_j}})(1\otimes H)C(e^{-i\pi S_a}), \qquad H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},$$

and preserves all other Boolean registers. Explicitly, $(A_j)_{(i,z),(i',z')}=(G_j)_{(i,z_j),(i',z'_j)}$ when $z_\ell=z'_\ell$ for every $\ell\ne j$, and is zero otherwise; $C(M)$ applies $1$ in the false sector and $M$ in the true sector. No Hermitian assumptions or bounds on the real parameters are imposed. For $T=0$, the product is the identity.

QAlgorithms.Papers.Independent.Intakethird100.P67.mixedHistoryOutput

For a finite coordinate index type $I$, any index type $K$, family $S:K\to\operatorname{Mat}_I(\mathbb C)$, anchor $a\in K$, vector $\phi\in\mathbb C^I$, arbitrary matrices $U,\rho\in\operatorname{Mat}_I(\mathbb C)$, natural number $T$, history $h:\{0,\ldots,T-1\}\to K$, and real parameters $(t_j)_{j<T}$, let $V_{\mathrm{in}}=A_{T-1}\cdots A_0$, where $A_j$ acts on the system and Boolean register $j$ by $C(e^{-it_jS_{h_j}})(1\otimes H)C(e^{-i\pi S_a})$ and preserves the other registers; here $C(M)$ applies $1$ in the false sector and $M$ in the true sector, and $H=2^{-1/2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$. With

$$m_T(z)=\prod_{j=0}^{T-1}\frac{(-1)^{z_j}}{\sqrt2},\qquad X=V_{\mathrm{in}}(\rho\otimes m_Tm_T^\dagger)V_{\mathrm{in}}^\dagger,\qquad V_{\mathrm{out}}=(U\otimes1)V_{\mathrm{in}}(U^\dagger\otimes1),$$

the definition returns

$$\operatorname{Tr}_{\mathrm{anc}} \left[ V_{\mathrm{out}}^\dagger \left((U\phi)(U\phi)^\dagger\otimes\operatorname{Tr}_{I}X\right) V_{\mathrm{out}} \right].$$

The partial traces sum matching indices of the indicated register. No normalization, positivity, Hermitian, or unitarity hypotheses are imposed. The case $T=0$ is included: $m_T=1$, $V_{\mathrm{in}}=1$, and $V_{\mathrm{out}}=UU^\dagger$ under the empty-register identification.

QAlgorithms.Papers.Independent.Intakethird100.P67.mixedSampleErasureChannel

For finite index types $I,K$, any family $S:K\to\operatorname{Mat}_I(\mathbb C)$, anchor $a\in K$, and arbitrary matrix $\rho\in\operatorname{Mat}_I(\mathbb C)$, this defines the matrix with entries

$$\frac1{|K|}\sum_{k\in K}\int_{[0,1]} \left[ \operatorname{Tr}_{\mathrm{Bool}} \left(G_{a,k}(t)(\rho\otimes mm^\dagger)G_{a,k}(t)^\dagger\right) \right]_{ij}\,dt,$$

where $m_{\mathrm{false}}=1/\sqrt2$, $m_{\mathrm{true}}=-1/\sqrt2$, and

$$G_{a,k}(t)=C(e^{-itS_k})(1\otimes H)C(e^{-i\pi S_a}), \qquad H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}.$$

The controlled matrix $C(M)$ applies $1$ on the false Boolean sector and $M$ on the true sector, and the partial trace sums the two matching Boolean indices. The integral is taken entry by entry with respect to Lebesgue measure. The sum includes $k=a$; the existence of $a$ requires $K$ to be nonempty. No Hermitian condition on $S_k$ or density-matrix condition on $\rho$ is imposed.

QAlgorithms.Papers.Independent.Intakethird100.P67.negativeFourier

For every natural number $d$, this defines the complex matrix with rows and columns indexed by $0,\ldots,d-1$ and entries $F_{jk}=(\sqrt d)^{-1}\exp(-2\pi\mathrm{i}jk/d)$. For $d=0$, this is the empty matrix, so there are no entries at which the division by $d$ is evaluated.

QAlgorithms.Papers.Independent.Intakethird100.P67.nonanchorProbability

For a finite type $K$ with decidable equality and elements $a,k\in K$, this defines

$$\begin{cases} 0,&k=a,\\ \displaystyle\frac1{\max(|K|-1,0)},&k\ne a, \end{cases}$$

where the subtraction is performed in the natural numbers before conversion to a real number, and the reciprocal of zero is defined to be zero. In particular, when $|K|=1$, the function is identically zero. If $K$ is empty, there are no elements $a,k$ to which the definition can be applied.

QAlgorithms.Papers.Independent.Intakethird100.P67.onAncilla

For an index type $I$, a natural number $T$, a complex matrix $V$ indexed by $I\times\{\mathrm{false},\mathrm{true}\}$, and an index $j\in\{0,\ldots,T-1\}$, this defines a matrix indexed by $I\times\{\mathrm{false},\mathrm{true}\}^T$. For system indices $i,i'\in I$ and bitstrings $z,z'$ of length $T$, its entry is

$$\begin{cases} V_{(i,z_j),(i',z'_j)},&z_\ell=z'_\ell\text{ for every }\ell\ne j,\\ 0,&\text{otherwise}. \end{cases}$$

There is no assumption that $V$ is unitary. When $T=0$, there is no admissible index $j$.

QAlgorithms.Papers.Independent.Intakethird100.P67.positivePhaseEvolution

For a finite index type $I$ with decidable equality, any complex matrix $H$ indexed by $I$, and any real number $\theta$, the definition returns the matrix exponential

$$\exp(i\theta H)=\sum_{m=0}^{\infty}\frac{(i\theta H)^m}{m!}.$$

There is no Hermitian hypothesis on $H$ or restriction on $\theta$; in particular, $\theta=0$ returns the identity matrix.

QAlgorithms.Papers.Independent.Intakethird100.P67.precisionRounds

For every natural number $d$, including $0$, and arbitrary real numbers $\lambda,\varepsilon$, this defines the natural number

$$\operatorname{precisionRounds}(d,\lambda,\varepsilon)= \begin{cases} 0,&d\le1,\\[2mm] \displaystyle \max\!\left\{1,\ \left\lceil \frac{\log\!\left(8(\varepsilon^{-1})^2(d-1)\right)} {1-\lambda} \right\rceil_{\mathbb N}\right\},&d>1. \end{cases}$$

Here $d-1$ inside the logarithm is real subtraction, and $\lceil x\rceil_{\mathbb N}$ is the least natural number at least $x$, giving $0$ for $x\le0$. There are no restrictions on $\lambda$ or $\varepsilon$: inverses and division are total, with $0^{-1}=0$ and division by zero equal to zero, while the real logarithm has $\log0=0$ and $\log(-x)=\log x$. Consequently, for $d>1$, either $\varepsilon=0$ or $\lambda=1$ gives the value $1$.

QAlgorithms.Papers.Independent.Intakethird100.P67.projectionBranch

For finite index types $I,K$ with decidable equality, any family $\phi:K\to\mathbb C^I$, natural number $T$, Boolean $b$, and complex matrix $\rho$ indexed by $I$, put $(D_k)_{ij}=\phi_k(i)\overline{\phi_k(j)}$ and $R_k=\mathrm{Id}-2D_k$. Let $m_T$ be the vector on length-$T$ Boolean words with $m_T(z)=2^{-T/2}(-1)^{|\{j:z_j=\mathrm{true}\}|}$, and set $P=\mathrm{Id}\otimes m_Tm_T^\dagger$. For each history $h:\{0,\ldots,T-1\}\to K$, let $G_{h,j}$ apply $R_{h(j)}$ to the system when ancilla bit $j$ is true and apply the identity when it is false, leaving every other ancilla bit unchanged, and set $V_h=G_{h,T-1}\cdots G_{h,0}$, with the empty product equal to the identity. Taking $Q_b=P$ if $b$ is true and $Q_b=\mathrm{Id}-P$ otherwise, the definition returns

$$(|K|^T)^{-1}\sum_h \operatorname{Tr}_{\mathrm{anc}} \left[ V_h^\dagger Q_bV_h (\rho\otimes m_Tm_T^\dagger) V_h^\dagger Q_b^\dagger V_h \right],$$

where $(\operatorname{Tr}_{\mathrm{anc}}X)_{ij}=\sum_zX_{(i,z),(j,z)}$. No normalization, positivity, or unitarity hypotheses are imposed on $\phi,\rho$, or the resulting matrices $V_h$. For $T=0$, the true branch returns $\rho$ and the false branch returns zero; if $K$ is empty and $T>0$, both return zero. Reciprocals use $0^{-1}=0$, and $0^0=1$.

QAlgorithms.Papers.Independent.Intakethird100.P67.projectionChannel

For finite index types $I,K$ with decidable equality, any family $\phi:K\to\mathbb C^I$, natural number $T$, and complex matrix $\rho$ indexed by $I$, define $D_k$ by $(D_k)_{ij}=\phi_k(i)\overline{\phi_k(j)}$, let $m_T(z)=2^{-T/2}(-1)^{|\{j:z_j=\mathrm{true}\}|}$ on length-$T$ Boolean words, and put $P=\mathrm{Id}\otimes m_Tm_T^\dagger$. For each history $h:\{0,\ldots,T-1\}\to K$, form $V_h=G_{h,T-1}\cdots G_{h,0}$, where $G_{h,j}$ applies $\mathrm{Id}-2D_{h(j)}$ to the system conditional on ancilla bit $j$ being true and leaves the other ancillas unchanged. The definition returns

$$(|K|^T)^{-1}\sum_h\sum_{Q\in\{\mathrm{Id}-P,P\}} \operatorname{Tr}_{\mathrm{anc}} \left[ V_h^\dagger QV_h(\rho\otimes m_Tm_T^\dagger) V_h^\dagger Q^\dagger V_h \right],$$

where the inner sum means the two displayed choices, and partial trace sums equal ancilla indices. There are no normalization or positivity assumptions on the inputs. For $T=0$ it returns $\rho$; for empty $K$ and $T>0$ it returns zero, using $0^{-1}=0$ and $0^0=1$.

QAlgorithms.Papers.Independent.Intakethird100.P67.pureFisherInformation

For a coordinate index type $I$, a function $v:\mathbb R\to\mathbb C^I$ in complex Euclidean space, and any $\alpha\in\mathbb R$, this defines the real number

$$4\left(\|v'(\alpha)\|^2-\left|\langle v(\alpha),v'(\alpha)\rangle_{\mathbb C}\right|^2\right).$$

The complex inner product conjugates its first argument. No normalization or differentiability hypothesis is imposed on $v$; the derivative is the total derivative operation, which returns zero when $v$ is not differentiable at $\alpha$.

QAlgorithms.Papers.Independent.Intakethird100.P67.pureSamples

For arbitrary index and label types $I,K$ and a family of complex vectors $\phi_k\in\mathbb C^I$, this defines the matrix family $S_k$ by $S_k(i,j)=\phi_k(i)\overline{\phi_k(j)}$. No normalization or nonzero condition is imposed on the vectors; in particular, a zero vector gives the zero matrix.

QAlgorithms.Papers.Independent.Intakethird100.P67.referenceVector

For any coordinate index type $I$, vector $\phi\in\mathbb C^I$, and natural number $n$, this defines a vector indexed by functions $x:\{0,\ldots,n-1\}\to I$, whose coordinate at $x$ is

$$\prod_{j=0}^{n-1}\phi(x_j).$$

No normalization is required of $\phi$. The case $n=0$ is included: there is one empty indexing function, and its coordinate is the empty product $1$.

QAlgorithms.Papers.Independent.Intakethird100.P67.registerSwap

For an index type $I$ with decidable equality, this defines the complex matrix on $I\times I$ whose entry at row $(i,j)$ and column $(k,\ell)$ is one exactly when $i=\ell$ and $j=k$, and zero otherwise. Thus it sends the coordinate basis vector indexed by $(k,\ell)$ to that indexed by $(\ell,k)$. The type $I$ is not required to be nonempty; if it is empty, the matrix is empty.

QAlgorithms.Papers.Independent.Intakethird100.P67.residual

For a finite index type $I$ with decidable equality, an index type $K$, any family $\phi:K\to\mathbb C^I$, anchor $a\in K$, vector $\psi\in\mathbb C^I$, and finite list $h=[k_0,\ldots,k_{m-1}]$ of elements of $K$, let $(D_k)_{ij}=\phi_k(i)\overline{\phi_k(j)}$. Starting with $r_0=\psi$, successively form

$$r_{s+1}=(\mathrm{Id}-2D_{k_s})(\mathrm{Id}-D_a)r_s \qquad(0\le s<m).$$

The definition returns $r_m$, with matrix action given by ordinary matrix-vector multiplication. An empty list returns $\psi$; repeated labels and unnormalized vectors are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P67.sampleAlgebra

For a finite index type $I$ with decidable equality, an arbitrary label type $K$, and a family $S=(S_k)_{k\in K}$ of complex $I\times I$ matrices, this defines the complex linear subspace spanned by all products $S_{k_1}\cdots S_{k_r}$ with $r\geq1$. Labels may repeat, and the factors retain their listed order. Thus its elements are finite complex linear combinations of nonempty products; the empty product is excluded from the generating set. If $K$ is empty, this subspace is $\{0\}$.

QAlgorithms.Papers.Independent.Intakethird100.P67.sampleDimension

For a finite index type $I$ with decidable equality, a finite label type $K$, and arbitrary complex $I\times I$ matrices $S_k$, this defines the natural number $\dim_{\mathbb C}\operatorname{range}(\Pi_S)$, viewing $\Pi_S$ as a complex linear map on $\mathbb C^I$. Here $\Pi_S=f(\sum_kS_k)$ is obtained by real continuous functional calculus with $f(0)=0$ and $f(x)=1$ for nonzero real $x$. For a Hermitian sum, this counts its nonzero eigenvalues with multiplicity; for a non-Hermitian sum, it is zero. It is also zero when $K$ or $I$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P67.samplePi

For a finite index type $I$ with decidable equality, a finite label type $K$, and arbitrary complex $I\times I$ matrices $S_k$, put $A=\sum_{k\in K}S_k$. This defines $\Pi_S=f(A)$ using real continuous functional calculus, where $f(0)=0$ and $f(x)=1$ for every nonzero real $x$. When $A$ is Hermitian, $\Pi_S$ is the orthogonal projection onto the sum of its nonzero eigenspaces, including eigenspaces with negative eigenvalues. When $A$ is not Hermitian, the totalized real functional calculus returns the zero matrix. No positivity assumption is imposed on the samples or their sum; an empty label type gives $\Pi_S=0$.

QAlgorithms.Papers.Independent.Intakethird100.P67.sampleReflection

For an index type $I$ with decidable equality and an arbitrary complex vector $\phi\in\mathbb C^I$, this defines the matrix $R_\phi=I_I-2\phi\phi^\dagger$, whose $(i,j)$-entry is $\delta_{ij}-2\phi(i)\overline{\phi(j)}$. No normalization is assumed. In particular, $\phi=0$ gives the identity matrix.

QAlgorithms.Papers.Independent.Intakethird100.P67.slowFactor

For every natural number $d$, every real $\varepsilon$, and every natural number $r$, this defines

$$\operatorname{slowFactor}(d,\varepsilon,r) =\left(1+\log(d+1)+\log(1+\varepsilon^{-1})\right)^r,$$

where the additions involving $d$ are real arithmetic. No positivity or nonzero assumption is imposed on $\varepsilon$; the inverse is total with $0^{-1}=0$, and the real logarithm is total with $\log0=0$ and $\log(-x)=\log x$. In particular, $\varepsilon=0$ gives $(1+\log(d+1))^r$, and $r=0$ gives $1$, including when the base is zero.

QAlgorithms.Papers.Independent.Intakethird100.P67.swapHamiltonian

For a coordinate index type $I$, any natural number $n$, and any real coupling $c$, this defines the complex matrix

$$H_{n,c}=c\sum_{j=0}^{n-1}S_j$$

on indices $(i,r)\in I\times I^{\{0,\ldots,n-1\}}$, where $S_j$ has entry $1$ from column $(i',r')$ to row $(i,r)$ exactly when $i=r'_j$ and $r$ equals $r'$ with coordinate $j$ replaced by $i'$, and has entry $0$ otherwise. The coupling may be negative or zero. For $n=0$, the sum is empty and $H_{0,c}=0$.

QAlgorithms.Papers.Independent.Intakethird100.P67.swapJoint

For a finite coordinate index type $I$, any vector $\phi\in\mathbb C^I$, natural number $n$, real numbers $c,t$, and arbitrary complex matrix $\rho$ indexed by $I$, this defines

$$V\bigl(\rho\otimes rr^\dagger\bigr)V^\dagger, \qquad V=\exp(-itH),\qquad H=c\sum_{j=0}^{n-1}S_j,\qquad r(x)=\prod_{j=0}^{n-1}\phi(x_j),$$

where $S_j$ exchanges the distinguished $I$-coordinate with reference coordinate $j$, and $rr^\dagger$ has entries $r(x)\overline{r(y)}$. No normalization of $\phi$, positivity or trace condition on $\rho$, or sign restriction on $c,t$ is imposed. The case $n=0$ uses the one-dimensional empty reference register, $r=1$, and $H=0$, so the resulting matrix has entries $\rho_{ij}$ under the natural identification with the distinguished register.

QAlgorithms.Papers.Independent.Intakethird100.P67.swapReference

For a coordinate index type $I$, a natural number $n$, and an index $j\in\{0,\ldots,n-1\}$, this defines a complex matrix indexed by pairs $(i,r)$, where $i\in I$ and $r:\{0,\ldots,n-1\}\to I$. Its entry in row $(i,r)$ and column $(i',r')$ is $1$ exactly when $i=r'_j$ and $r$ is obtained from $r'$ by replacing its $j$-th coordinate with $i'$; otherwise the entry is $0$. Thus its action exchanges the distinguished coordinate with reference coordinate $j$. When $n=0$, there is no admissible choice of $j$.

QAlgorithms.Papers.Independent.Intakethird100.P67.systemControlled

For an index type $I$ with decidable equality and an arbitrary complex $I\times I$ matrix $V$, this defines a matrix $C(V)$ indexed by $I\times\{\mathrm{false},\mathrm{true}\}$. Its entry from $(j,c)$ to $(i,b)$ is zero when $b\neq c$, is $V_{ij}$ when $b=c=\mathrm{true}$, and is $\delta_{ij}$ when $b=c=\mathrm{false}$. Thus the Boolean coordinate controls whether $V$ or the identity acts on the $I$-coordinate. No unitarity assumption is imposed on $V$.

QAlgorithms.Papers.Independent.Intakethird100.P67.transportedGate

For a finite system index type $I$, a label type $L$, an arbitrary complex matrix $U$ on $I$, and an arbitrary family of complex matrices $W_\ell$ on $I\times\{\mathrm{false},\mathrm{true}\}$, this defines the family

$$\ell\longmapsto (U\otimes\mathbf1_2)\,W_\ell\,(U\otimes\mathbf1_2)^\dagger,$$

where $\mathbf1_2$ is the identity matrix on the Boolean index and $\dagger$ denotes conjugate transpose. Neither $U$ nor the matrices $W_\ell$ are assumed unitary.

QAlgorithms.Papers.Independent.Intakethird100.P67.unaryWord

For all natural numbers $T,t$, the definition returns the Boolean word $u_{T,t}$ of length $T$ whose bit at position $j\in\{0,\ldots,T-1\}$ is true exactly when $j<t$. Thus its first $\min(t,T)$ bits are true and its remaining bits are false. In particular, $t=0$ gives the all-false word, $t\ge T$ gives the all-true word, and $T=0$ gives the unique empty word.

QAlgorithms.Papers.Independent.Intakethird100.P67.uniformAddress

For every natural number $d$, this defines the vector in $\mathbb C^{\{0,\ldots,d-1\}}$ whose every coordinate equals $(\sqrt d)^{-1}$. When $d=0$, the coordinate set is empty and the result is the unique vector in the zero-dimensional space; the real inverse of zero is defined to be zero.

QAlgorithms.Papers.Independent.Intakethird100.P67.wireBranch

For finite index types $I,K$, any family $(\phi_k)_{k\in K}$ of vectors in $\mathbb C^I$, anchor $a\in K$, arbitrary complex matrices $U,\rho$ indexed by $I$, natural number $T$, and Boolean $b$, this defines the following matrix. Write $P_k=\phi_k\phi_k^\dagger$, $R_k=1-2P_k$, $p_a(k)=0$ if $k=a$ and $p_a(k)=(|K|-1)^{-1}$ otherwise, where the subtraction is natural-number subtraction and the real inverse of zero is zero. For any system matrix $M$, let $C(M)$ preserve a Boolean register and apply $1$ when that register is false and $M$ when it is true; let $H=2^{-1/2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ in the order false, true, and put $E_k=C(R_k)(1\otimes H)C(R_a)$. For a history $h:\{0,\ldots,T-1\}\to K$, let $V_h$ apply $E_{h_j}$ to the system and Boolean register $j$, in increasing order of $j$, and let $\widetilde V_h$ be the corresponding product with each $E_k$ replaced by $(U\otimes1)E_k(U^\dagger\otimes1)$. Set

$$w_h=\prod_{j=0}^{T-1}p_a(h_j),\qquad m_T(z)=\prod_{j=0}^{T-1}\frac{(-1)^{z_j}}{\sqrt2},\qquad X_h=V_h(\rho\otimes m_Tm_T^\dagger)V_h^\dagger.$$

If $b$ is true, the result is

$$\sum_h w_h\,\operatorname{Tr}_{\mathrm{anc}} \!\left[((1-P_a)\otimes1)X_h((1-P_a)\otimes1)^\dagger\right].$$

If $b$ is false, the result is

$$\sum_h w_h\,\operatorname{Tr}_{\mathrm{anc}} \!\left[ \widetilde V_h^\dagger \left((U\phi_a)(U\phi_a)^\dagger\otimes \operatorname{Tr}_{I}\!\left[(P_a\otimes1)X_h(P_a\otimes1)^\dagger\right]\right) \widetilde V_h \right].$$

Here each partial trace sums matching row and column indices of the indicated register. No normalization, positivity, or unitarity hypotheses are imposed on the inputs. For $T=0$, there is one empty history, its weight is $1$, and both history products are identities; if $K$ is a singleton and $T>0$, all history weights are zero.