Definitions for Reversible quantum cellular automata

QAlgorithms.Papers.Independent.Intakethird100.P96.IsWatrous

For every natural number $extra$, put $L=extra+5$ and let $\mathcal C$ be the set of Boolean functions on $\mathbb Z/L\mathbb Z$, identified with positions $0,\ldots,L-1$. For any complex matrix $W$ whose rows and columns are indexed by $\mathcal C$, this defines the property that there exists a function $u:\{\mathrm{false},\mathrm{true}\}\times\mathcal C\to\mathbb C$ such that

$$W_{a,b}=\prod_{x\in\mathbb Z/L\mathbb Z} u\!\left(a_x,\ (b_{x+k})_{k\in\mathbb Z/L\mathbb Z}\right) \quad\text{for every }a,b\in\mathcal C.$$

All additions of positions are modulo $L$. The same function $u$ is used at every position and may depend on the entire shifted configuration; no normalization or unitarity condition is part of this definition. The case $extra=0$, hence $L=5$, is included.

QAlgorithms.Papers.Independent.Intakethird100.P96.RingConfiguration

For every natural number $extra$, this defines a ring configuration to be an arbitrary function from $\{0,\ldots,extra+4\}$ to the Boolean values $\{\mathrm{false},\mathrm{true}\}$. Thus it is a Boolean assignment to $extra+5$ indexed positions; $extra=0$ gives five positions.

QAlgorithms.Papers.Independent.Intakethird100.P96.coefficientLeft

For the ambient complex vector spaces $B_1,B_2$ and every subset $M\subseteq B_1\otimes_{\mathbb C}B_2$, this defines a complex linear subspace of $B_1$: the span of all contractions $(\operatorname{id}_{B_1}\otimes f)(a)$, where $a\in M$ and $f:B_2\to\mathbb C$ ranges over all complex linear functionals, with $B_1\otimes_{\mathbb C}\mathbb C$ identified with $B_1$. Explicitly, if $a=\sum_r x_r\otimes y_r$, its contraction is $\sum_r f(y_r)x_r$. The span consists of finite complex linear combinations of these contractions; when $M$ is empty, it is $\{0\}$.

QAlgorithms.Papers.Independent.Intakethird100.P96.coefficientRight

For the ambient complex vector spaces $B_1,B_2$ and every subset $M\subseteq B_1\otimes_{\mathbb C}B_2$, this defines a complex linear subspace of $B_2$: the span of all contractions $(f\otimes\operatorname{id}_{B_2})(a)$, where $a\in M$ and $f:B_1\to\mathbb C$ ranges over all complex linear functionals, with $\mathbb C\otimes_{\mathbb C}B_2$ identified with $B_2$. Explicitly, if $a=\sum_r x_r\otimes y_r$, its contraction is $\sum_r f(x_r)y_r$. The span consists of finite complex linear combinations of these contractions; when $M$ is empty, it is $\{0\}$.

QAlgorithms.Papers.Independent.Intakethird100.P96.contractLeft

For the ambient complex vector spaces $B_1,B_2$ and every complex linear functional $f:B_2\to\mathbb C$, this defines the complex linear map $C_f:B_1\otimes_{\mathbb C}B_2\to B_1$ obtained by applying the identity to the first factor, applying $f$ to the second factor, and identifying $B_1\otimes_{\mathbb C}\mathbb C$ with $B_1$. Thus $C_f(x\otimes y)=f(y)x$, and on any finite tensor sum it gives $C_f(\sum_r x_r\otimes y_r)=\sum_r f(y_r)x_r$.

QAlgorithms.Papers.Independent.Intakethird100.P96.contractRight

For the ambient complex vector spaces $B_1,B_2$ and every complex linear functional $f:B_1\to\mathbb C$, this defines the complex linear map $D_f:B_1\otimes_{\mathbb C}B_2\to B_2$ obtained by applying $f$ to the first factor, applying the identity to the second factor, and identifying $\mathbb C\otimes_{\mathbb C}B_2$ with $B_2$. Thus $D_f(x\otimes y)=f(x)y$, and on any finite tensor sum it gives $D_f(\sum_r x_r\otimes y_r)=\sum_r f(x_r)y_r$.

QAlgorithms.Papers.Independent.Intakethird100.P96.coordinateProjection

For every natural number $d$ and every index $i\in\{0,\ldots,d-1\}$, this defines the complex $d\times d$ matrix $E_i$ whose $(j,k)$-entry is $1$ when $j=k=i$ and $0$ otherwise. The parameter $d=0$ is allowed, but then there is no index $i$ to supply.

QAlgorithms.Papers.Independent.Intakethird100.P96.jointAction

For arbitrary natural numbers $aCount,bCount$, natural-valued families $n_i,m_j,r_{ij}$, and complex matrices $a_i\in M_{n_i}(\mathbb C)$, $b_j\in M_{m_j}(\mathbb C)$, this defines a complex matrix indexed by the tagged tuples $(i,j,((s,t),h))$, where $i<aCount$, $j<bCount$, $s<n_i$, $t<m_j$, and $h<r_{ij}$, as the block diagonal matrix

$$J_r(a,b)=\bigoplus_{i<aCount}\ \bigoplus_{j<bCount} \left(a_i\otimes b_j\otimes I_{r_{ij}}\right).$$

Explicitly, its entry between $(i,j,((s,t),h))$ and $(i',j',((s',t'),h'))$ is zero unless $i=i'$ and $j=j'$; when those equalities hold, it is $(a_i)_{ss'}(b_j)_{tt'}\delta_{hh'}$. Here $\otimes$ is the Kronecker product and $I_r$ is the $r\times r$ identity matrix. All dimensions and multiplicities may be zero, in which case the corresponding blocks have no indices.

QAlgorithms.Papers.Independent.Intakethird100.P96.jointBlockIndex

For arbitrary natural numbers $aCount,bCount$, families of natural numbers $(n_i)_{i<aCount}$ and $(m_j)_{j<bCount}$, and natural numbers $r_{ij}$ for every such pair $(i,j)$, this defines the index set

$$\bigsqcup_{i<aCount}\ \bigsqcup_{j<bCount} \bigl((\{0,\ldots,n_i-1\}\times\{0,\ldots,m_j-1\}) \times\{0,\ldots,r_{ij}-1\}\bigr).$$

Its elements are tagged tuples $(i,j,((s,t),h))$ with $s<n_i$, $t<m_j$, and $h<r_{ij}$. No positivity assumptions are imposed: a pair contributes no indices if any of $n_i,m_j,r_{ij}$ is zero, and the entire set is empty if either outer index set is empty.

QAlgorithms.Papers.Independent.Intakethird100.P96.ringHadamard

For every natural number $extra$, put $L=extra+5$. This defines a complex matrix $H$, indexed by Boolean configurations $a,b$ on the $L$ positions, by

$$H_{a,b} =\prod_{x=0}^{L-1} \frac{\begin{cases} -1,&a_x=\mathrm{true}\ \text{and }b_x=\mathrm{true},\\ 1,&\text{otherwise} \end{cases}}{\sqrt2}.$$

Equivalently, $H_{a,b}=2^{-L/2}(-1)^{|\{x:a_x=b_x=\mathrm{true}\}|}$. The definition includes $extra=0$, giving a matrix on configurations of five positions.

QAlgorithms.Papers.Independent.Intakethird100.P96.ringPhase

For every natural number $extra$, put $L=extra+5$. This defines a diagonal complex matrix $R$, indexed by Boolean configurations on positions $0,\ldots,L-1$, whose diagonal entry at configuration $b$ is

$$R_{b,b} =\prod_{x=0}^{L-1} \begin{cases} -1,&b_x=\mathrm{true}\ \text{and }b_{x+1}=\mathrm{true},\\ 1,&\text{otherwise}. \end{cases}$$

All off-diagonal entries are zero, and $x+1$ is taken modulo $L$, so the product includes the pair of positions $L-1$ and $0$. The definition includes $extra=0$, hence $L=5$.

QAlgorithms.Papers.Independent.Intakethird100.P96.supportLeft

For the ambient complex algebras $B_1,B_2$ with their given involutions and every subset $M\subseteq B_1\otimes_{\mathbb C}B_2$, this defines the smallest nonunital complex star subalgebra of $B_1$ containing the complex linear span of all left contractions of elements of $M$. A left contraction sends a finite tensor expression $\sum_r x_r\otimes y_r$ to $\sum_r f(y_r)x_r$ for an arbitrary complex linear functional $f:B_2\to\mathbb C$. The resulting subalgebra is closed under addition, complex scalar multiplication, multiplication, and involution; no identity element is required to belong to it. For $M=\varnothing$, it is $\{0\}$.

QAlgorithms.Papers.Independent.Intakethird100.P96.supportRight

For the ambient complex algebras $B_1,B_2$ with their given involutions and every subset $M\subseteq B_1\otimes_{\mathbb C}B_2$, this defines the smallest nonunital complex star subalgebra of $B_2$ containing the complex linear span of all right contractions of elements of $M$. A right contraction sends a finite tensor expression $\sum_r x_r\otimes y_r$ to $\sum_r f(x_r)y_r$ for an arbitrary complex linear functional $f:B_1\to\mathbb C$. The resulting subalgebra is closed under addition, complex scalar multiplication, multiplication, and involution; no identity element is required to belong to it. For $M=\varnothing$, it is $\{0\}$.

QAlgorithms.Papers.Independent.Intakethird100.P96.tensorSpan

For the ambient complex vector spaces $B_1,B_2$ and complex linear subspaces $P\subseteq B_1$, $Q\subseteq B_2$, this defines the complex linear subspace of $B_1\otimes_{\mathbb C}B_2$ spanned by all elementary tensors $x\otimes y$ with $x\in P$ and $y\in Q$. Its elements are finite complex linear combinations of such tensors, including the empty sum $0$; if either $P=\{0\}$ or $Q=\{0\}$, this subspace is $\{0\}$.