Definitions for Matchgates and classical simulation of quantum circuits

QAlgorithms.Papers.Independent.Intakethird100.P77.BasisDecisionFamily.Allowed

For a basis decision family $F$, with a width $w(s)$ and a finite gate list for every Boolean string $s$, and output wires $o(n)<w(\mathrm{true}^{\,n})$ with $n\le w(\mathrm{true}^{\,n})$, and for a natural number $r$, this property says that for every $n\in\mathbb N$, every gate $g$ in the list at $s=\mathrm{true}^{\,n}$ has two unitary Boolean-indexed complex $2\times2$ matrices $A_g,B_g$ and an injective wire assignment $v_g:\{0,1\}\hookrightarrow\{0,\ldots,w(s)-1\}$ satisfying both $|v_g(0)-v_g(1)|\le r$ and $\det A_g=\det B_g$. This quantifies over $n=0$ as well. Empty gate lists satisfy these conditions vacuously; when $r=0$, injectivity prevents any gate from satisfying the distance bound, so all lists at unary strings must be empty. The condition concerns the gate lists at unary strings only.

QAlgorithms.Papers.Independent.Intakethird100.P77.BasisDecisionFamily.Effective

For a basis decision family $F$, consisting of widths $w(s)$, lists of two-wire gates with unitary Boolean-indexed matrices $A_g,B_g$ and injective wire assignments $v_g$, and output wires $o(n)<w(\mathrm{true}^{\,n})$ satisfying $n\le w(\mathrm{true}^{\,n})$, this property requires three polynomial-time Boolean-string computations. Write $u(j)=\mathrm{true}^{\,j}$ and $T([a_1,\ldots,a_k])=\big\Vert_j(u(|a_j|)\,\mathrm{false}\,a_j)$. First, the function

$$s\longmapsto T\!\left([u(w(s)),u(\text{number of gates})]\mathbin{+\!\!+} [T([u(v_g(0)),u(v_g(1))]):g\text{ in list order}]\right)$$

must be polynomial-time computable. Second, form the complex-entry list by taking, for each gate in order, the four entries of $A_g$ and then those of $B_g$, each in order $(0,0),(0,1),(1,0),(1,1)$. There must be a polynomial-time function which, on $T([s,u(j),u(m),[b]])$, approximates entry $j$'s real part if $b=\mathrm{false}$, or imaginary part if $b=\mathrm{true}$, within $2^{-m}$, for every valid $j$, every $m\in\mathbb N$, and both $b$. Its output denotes the binary integer in its tail divided by $2^m$, negated when its first bit is true; empty or missing bits contribute zero. Third, $x\mapsto u(o(|x|))$ must be polynomial-time computable for every Boolean string $x$. Polynomial time means computability by a TM2 Turing machine using identity input and output encodings. These requirements include empty input strings and precision $m=0$.

QAlgorithms.Papers.Independent.Intakethird100.P77.BasisDecisionFamily.acceptance

For a basis decision family $F$, with widths $w(s)$, gate lists, and output wires $o(n)<w(\mathrm{true}^{\,n})$ satisfying $n\le w(\mathrm{true}^{\,n})$, and a finite Boolean string $x$, put $n=|x|$, $s=\mathrm{true}^{\,n}$, and $w=w(s)$. Each gate in the list at $s$ has unitary Boolean-indexed matrices $A_g,B_g$ and an injective ordered pair of wires; on those wires, its entry from $y\in\{0,1\}^2$ to $z\in\{0,1\}^2$ is zero if their parities differ, is $(A_g)_{z_0,y_0}$ if both parities are even, and is $(B_g)_{z_0,y_0}$ if both are odd, with every other wire unchanged. Let $U_s$ be the product of these embedded matrices in reverse list order, the empty product being the identity, and let $a\in\{0,1\}^w$ contain $x$ in its first $n$ positions and false in its remaining positions. The defined acceptance value is

$$\sum_{\substack{z\in\{0,1\}^{w}\\z_{o(n)}=\mathrm{true}}}|(U_s)_{z,a}|^2.$$

The definition includes the empty input $x$; even then the family supplies an output wire and therefore at least one wire.

QAlgorithms.Papers.Independent.Intakethird100.P77.BasisDecisionFamily

An object of this structure consists of a family assigning to every finite Boolean string $s$ a width $w(s)\in\mathbb N$ and a finite ordered list of gates, each carrying two unitary complex $2\times2$ matrices $A,B$, indexed by Boolean values, and an injection of its two wire positions into $\{0,\ldots,w(s)-1\}$; an output wire $o(n)\in\{0,\ldots,w(\mathrm{true}^{\,n})-1\}$ for every $n\in\mathbb N$; and a proof that $n\le w(\mathrm{true}^{\,n})$ for every $n$. The presence of an output wire also requires $w(\mathrm{true}^{\,n})>0$, including at $n=0$. The gate matrices are required here only to be unitary, and their wire assignments to be injective; the structure itself imposes no determinant-equality or wire-distance requirement.

QAlgorithms.Papers.Independent.Intakethird100.P77.CARPolynomial.DegreeLE

For any natural numbers $n,d$ and any finite list $P$ of complex-coefficient terms whose index lists are strictly increasing in $\{0,\ldots,2n-1\}$ and do not repeat, this predicate means that every stored term has an index list of length at most $d$. This requirement applies even to terms with coefficient zero. It holds vacuously for an empty list of terms. For $d=0$, every stored index list must be empty; for $n=0$, it holds for every $d$.

QAlgorithms.Papers.Independent.Intakethird100.P77.CARPolynomial.eval

For any natural number $n$, let $P$ be a finite list of terms $(l,a)$ with complex coefficients, where each index list $l$ is strictly increasing in $\{0,\ldots,2n-1\}$ and distinct terms have distinct index lists. For any arbitrary family $c_i$ of complex matrices indexed by $Q_n=\{0,1\}^n$, this defines

$$P(c)=\sum_{([i_1,\ldots,i_r],a)\,\text{in }P}a\,c_{i_1}\cdots c_{i_r}.$$

An empty index list contributes $aI$, while an empty list of terms evaluates to zero. No Hermiticity or anticommutation assumptions are imposed on $c_i$. When $n=0$, the result is zero or a scalar multiple of the identity.

QAlgorithms.Papers.Independent.Intakethird100.P77.CARPolynomial

For any natural number $n$, this structure consists of a finite list of pairs $(l,a)$, where $a\in\mathbb C$ and $l$ is a finite list of indices in $\{0,\ldots,2n-1\}$, together with the requirements that the indices in each stored list $l$ are strictly increasing and that no two entries have the same index list. There is no prescribed ordering of the terms themselves, and zero coefficients are allowed. Empty index lists are allowed, but at most one can occur. The list of terms may be empty; when $n=0$, it is either empty or consists of a single term with an empty index list.

QAlgorithms.Papers.Independent.Intakethird100.P77.EffectiveCode

For any function $\mathrm{code}$ from finite Boolean strings to finite Boolean strings, this predicate means that there exists a polynomial-time TM2 computation of $\mathrm{code}$ using the identity encoding for both input and output strings. It imposes no additional condition that the output be a valid encoding of any particular kind of object.

QAlgorithms.Papers.Independent.Intakethird100.P77.EffectiveNumbers

For any function $\mathrm{data}$ assigning a finite list of complex numbers to each finite Boolean string, this predicate means that there exists one function $f$ from Boolean strings to Boolean strings, computable in polynomial time by a TM2 machine with identity input and output encodings, such that for every string $s$, every index $0\le j<|\mathrm{data}(s)|$, every natural number $m$, and every Boolean $b$, the following approximation holds: form the four component strings $s$, $1^j$, $1^m$, and $[b]$, prefix each component $x$ by $1^{|x|}0$, concatenate them in that order, and apply $f$; interpret its output as a signed binary integer divided by $2^m$, with a first bit of true indicating a negative sign and the remaining bits giving the unsigned binary magnitude. This interpreted value differs by at most $2^{-m}$ from the imaginary part of the $j$th entry of $\mathrm{data}(s)$ if $b$ is true, and from its real part if $b$ is false. An empty output or an output of length one is interpreted as $0$. The case $m=0$ is included and requires error at most $1$; if $\mathrm{data}(s)$ is empty, there are no approximation requirements for that $s$.

QAlgorithms.Papers.Independent.Intakethird100.P77.EffectivePermutations

For a function $w$ assigning a natural number to every finite Boolean string $s$, and a permutation $p_s$ of $\{0,\ldots,w(s)-1\}$ for every $s$, this property says that the following Boolean-string function is computable in polynomial time by a TM2 Turing machine, with identity input and output encodings: list the numbers $p_s(0),\ldots,p_s(w(s)-1)$ in order, encode each number $j$ as $j$ copies of true, and prefix each resulting string by its length encoded as that many copies of true followed by false; concatenate these prefixed strings. Thus the output is $\big\Vert_{i=0}^{w(s)-1}(\mathrm{true}^{\,p_s(i)}\,\mathrm{false}\,\mathrm{true}^{\,p_s(i)})$, where $\Vert$ denotes concatenation. Width zero is permitted, in which case the permutation is the unique permutation of the empty set and the output is the empty string.

QAlgorithms.Papers.Independent.Intakethird100.P77.GaussianFamily.Effective

For a Gaussian family $F$, this property is the conjunction of polynomial-time computability of its structural encoding and polynomial-time approximability of its numerical data. More precisely, let $1^j$ denote $j$ true bits and let $\mathcal T(w_1,\ldots,w_q)$ concatenate the strings $1^{|w_r|}0w_r$ in order. At input $s$, the structural encoding is $\mathcal T(1^n,1^L,O_0,\ldots,O_{n-1})$, where $n$ is the width, $L$ is the gate-list length, and $O_k$ encodes the observable’s ordered index-word list by applying $\mathcal T$ to the encodings $\mathcal T(1^{i_1},\ldots,1^{i_p})$ of its words. The numerical list $D_s$ consists, in order, of all four entries of every generator factor matrix, ordered by generator, wire, row and column; all real gate-matrix entries embedded into $\mathbb C$, ordered by gate, row and column; and all observable coefficients, ordered by wire and term. The structural encoding, as a function of $s$, must have a polynomial-time Turing-machine realization with identity string encodings. There must also exist a polynomial-time Boolean-string function $f$ such that, for every $s$, valid index $0\le j<|D_s|$, natural precision $m$, and Boolean $b$,

$$\left|\operatorname{dyad}_m\!\left(f\bigl(\mathcal T(s,1^j,1^m,[b])\bigr)\right) -\begin{cases}\operatorname{Im}(D_s[j]),&b=\mathrm{true},\\ \operatorname{Re}(D_s[j]),&b=\mathrm{false}\end{cases}\right|\le 2^{-m}.$$

Here $\operatorname{dyad}_m(w)$ interprets the first bit as a sign, negative when true, interprets the remaining bits as a binary natural number with the most significant bit first, and divides the signed result by $2^m$; an empty string represents zero. Precision zero is included, and an empty numerical list imposes no numerical approximation conditions.

QAlgorithms.Papers.Independent.Intakethird100.P77.GaussianFamily.code

For any Gaussian family $F$ and finite Boolean string $s$, let $n$ be its width, $L$ the length of its ordered list of real skew-symmetric gate matrices, $q<n$ its measured-wire index, and $w_1,\ldots,w_K$ the generator-index words in its observable’s term list, in their stored order. Its code is the Boolean string

$$\operatorname{tuple}\!\left[ 1^n,\ 1^L,\ 1^q,\ \operatorname{tuple}\!\left[ \operatorname{tuple}[1^{i}:i\text{ occurs in }w_1],\ldots, \operatorname{tuple}[1^{i}:i\text{ occurs in }w_K] \right]\right].$$

Here $1^a$ is $a$ true bits, and $\operatorname{tuple}$ concatenates each constituent string after prefixing it with its length in unary followed by a false bit. Generator indices are their natural values in $\{0,\ldots,2n-1\}$. The words have strictly increasing indices and are distinct. An empty list has empty tuple encoding, and an empty word is encoded by the empty inner tuple. This code records the width, gate count, measured index, and ordered words; matrix entries and observable coefficients do not occur in it.

QAlgorithms.Papers.Independent.Intakethird100.P77.GaussianFamily.data

For any Gaussian family $F$ and finite Boolean string $s$, write $n$ for its width, $F_{i,k}$ for the complex $2\times2$ factor of generator $i<2n$ on wire $k<n$, $h_1,\ldots,h_L$ for its ordered list of real skew-symmetric $2n\times2n$ gate matrices, and $(w_1,\alpha_1),\ldots,(w_K,\alpha_K)$ for its observable terms. Its data is a single list of complex numbers formed by concatenating three lists: first, for increasing $i$ and then increasing $k$, the four entries

$$(F_{i,k})_{\mathrm{false},\mathrm{false}},\ (F_{i,k})_{\mathrm{false},\mathrm{true}},\ (F_{i,k})_{\mathrm{true},\mathrm{false}},\ (F_{i,k})_{\mathrm{true},\mathrm{true}};$$

second, for gates in their stored order, all entries $(h_\ell)_{ij}$, embedded from $\mathbb R$ into $\mathbb C$, with $i$ increasing first as the outer index and $j$ increasing as the inner index; and third, the coefficients $\alpha_1,\ldots,\alpha_K$ in stored term order. Empty gate or term lists contribute no entries.

QAlgorithms.Papers.Independent.Intakethird100.P77.GaussianFamily

A Gaussian family consists of the following data and identities for every finite Boolean string $s$. It has a natural width $n=n(s)$, with basis labels $\{0,1\}^n$, and $2n$ complex matrices $c_0,\ldots,c_{2n-1}$ on this basis satisfying

$$c_i^\dagger=c_i,\qquad c_ic_j+c_jc_i=2\delta_{ij}I.$$

For each generator $i$ and wire $k<n$, it supplies a complex $2\times2$ matrix $F_{i,k}$, with the required factorization

$$(c_i)_{x,y}=\prod_{k<n}(F_{i,k})_{x_k,y_k} \quad(x,y\in\{0,1\}^n).$$

It also supplies a finite ordered list of real $2n\times2n$ matrices $h$, each satisfying $h_{ij}=-h_{ji}$, a measured wire $q<n$, and a finite list of pairs $(w,\alpha)$, where $\alpha\in\mathbb C$ and $w$ is a list of generator indices. Each word has strictly increasing indices, and no word occurs twice in this list. These pairs must satisfy

$$\sum_{(w,\alpha)}\alpha\,c_{w_1}\cdots c_{w_{|w|}} =Z_q,\qquad (Z_q)_{x,y}=\prod_{k<n} \begin{cases} Z_{x_k,y_k},&k=q,\\ \delta_{x_k,y_k},&k\ne q, \end{cases}$$

where $Z=\operatorname{diag}(1,-1)$, with false preceding true. Empty words contribute the identity, zero coefficients are allowed, and the gate list may be empty. There is no degree or effectiveness requirement in this structure. The measured-wire field requires $n(s)>0$ for every $s$.

QAlgorithms.Papers.Independent.Intakethird100.P77.InBoundedMatchgate

For a natural number $r$ and a language $L$ of finite Boolean strings, this property asserts the existence of widths $w(s)$, finite gate lists at every string $s$, and output wires $o(n)<w(\mathrm{true}^{\,n})$, with $n\le w(\mathrm{true}^{\,n})$ for all $n\in\mathbb N$, satisfying the following requirements. Each gate has two unitary Boolean-indexed complex $2\times2$ matrices $A_g,B_g$ and an injective wire assignment $v_g$. Put $u(j)=\mathrm{true}^{\,j}$ and $T([a_1,\ldots,a_k])=\big\Vert_j(u(|a_j|)\,\mathrm{false}\,a_j)$. The functions encoding each family member as $T([u(w(s)),u(\text{gate count})]\mathbin{+\!\!+}[T([u(v_g(0)),u(v_g(1))]):g\text{ in order}])$, and sending $x$ to $u(o(|x|))$, must be polynomial-time computable. There must also be a polynomial-time function which, queried on $T([s,u(j),u(m),[b]])$, approximates the real or imaginary part, selected respectively by $b=\mathrm{false}$ or true, of entry $j$ of the gate-data list within $2^{-m}$, for every valid $j$ and every $m\in\mathbb N$; that list contains $A_g$ then $B_g$ for each gate, with entries ordered $(0,0),(0,1),(1,0),(1,1)$, and a returned string denotes its binary tail divided by $2^m$, negated if its first bit is true, with missing bits zero. All polynomial-time computations use TM2 machines with identity encodings. At every unary string $\mathrm{true}^{\,n}$, each gate must satisfy $\det A_g=\det B_g$ and $|v_g(0)-v_g(1)|\le r$. Its two-wire matrix uses $A_g$ on even-parity rows and columns, $B_g$ on odd-parity rows and columns, and zero between different parities, indexing each block by the first wire's bit; it leaves all other wires unchanged. Let $U_n$ be the reverse-order product of the embedded gate list at $\mathrm{true}^{\,n}$, with the empty product the identity, and let $a_x$ be $x$ followed by false bits to width $w(\mathrm{true}^{\,|x|})$. For every string $x$, including the empty string, the quantity

$$a(x)=\sum_{z:\,z_{o(|x|)}=\mathrm{true}}|(U_{|x|})_{z,a_x}|^2$$

must satisfy $a(x)\ge2/3$ if $x\in L$, and $a(x)\le1/3$ if $x\notin L$. When $r=0$, the injectivity and distance requirements force all gate lists at unary strings to be empty.

QAlgorithms.Papers.Independent.Intakethird100.P77.InP

For a set $L$ of finite Boolean strings, this property says that there exists a function $f$ from finite Boolean strings to finite Boolean strings which is computable in polynomial time by a TM2 Turing machine, using identity input and output encodings, and which returns exactly the one-bit string [true] on every $x\in L$, and exactly [false] on every $x\notin L$. This requirement applies to every input string, including the empty string.

QAlgorithms.Papers.Independent.Intakethird100.P77.InPQPMatchgate

For a natural number $r$ and a language $L$ of finite Boolean strings, this property asserts the existence of widths $w(s)$, finite gate lists for every string $s$, output wires $o(n)<w(\mathrm{true}^{\,n})$ with $n\le w(\mathrm{true}^{\,n})$, and a polynomial $p$ with natural-number coefficients such that $p(n)\ge2$ for every $n\in\mathbb N$. Each gate carries unitary Boolean-indexed complex $2\times2$ matrices $A_g,B_g$ and an injective ordered pair of wires $v_g$. Write $u(j)=\mathrm{true}^{\,j}$ and $T([a_1,\ldots,a_k])=\big\Vert_j(u(|a_j|)\,\mathrm{false}\,a_j)$. The encoding $s\mapsto T([u(w(s)),u(\text{gate count})]\mathbin{+\!\!+}[T([u(v_g(0)),u(v_g(1))]):g\text{ in order}])$ and the function $x\mapsto u(o(|x|))$ must be polynomial-time computable. The gate-data list, consisting of $A_g$ then $B_g$ for each gate and entries in order $(0,0),(0,1),(1,0),(1,1)$, must admit a polynomial-time approximation function: at input $T([s,u(j),u(m),[b]])$, it approximates entry $j$'s real part for $b=\mathrm{false}$, or imaginary part for $b=\mathrm{true}$, within $2^{-m}$, for all valid $j$ and all $m\in\mathbb N$. The returned string represents its binary tail divided by $2^m$, with a negative sign exactly when the first bit is true, and missing bits zero. Polynomial time uses TM2 machines with identity encodings. At each unary string $\mathrm{true}^{\,n}$, all gates must satisfy $\det A_g=\det B_g$ and $|v_g(0)-v_g(1)|\le r$. The local gate matrix has entries from $A_g$ on the even-parity block, from $B_g$ on the odd-parity block, each indexed by the first bit, and zero between blocks; other wires are unchanged. Let $U_n$ be the reverse-order product of these embedded gates, and let $a_x$ be $x$ padded with false to the width at $\mathrm{true}^{\,|x|}$. Then for every string $x$,

$$\begin{aligned} x\in L&\ \Longrightarrow\ \frac12+2^{-p(|x|)} \le \sum_{z:\,z_{o(|x|)}=\mathrm{true}}|(U_{|x|})_{z,a_x}|^2,\\ x\notin L&\ \Longrightarrow\ \sum_{z:\,z_{o(|x|)}=\mathrm{true}}|(U_{|x|})_{z,a_x}|^2 \le\frac12-2^{-p(|x|)}. \end{aligned}$$

The conditions include length zero; output-wire existence requires positive width there. Empty gate lists are allowed, and $r=0$ forces all unary-indexed gate lists to be empty.

QAlgorithms.Papers.Independent.Intakethird100.P77.IntertwinedFamily.Effective

For an intertwined family $F$, this predicate requires two polynomial-time computability properties. To state them explicitly, let $u(r)$ be $r$ true bits, and let $\tau([v_1,\ldots,v_\ell])$ concatenate $u(|v_j|)$, a false bit, and $v_j$ for every $j$. At parameter string $s$, write $n_s$ for the base width, $L_s$ for the number of base skew-symmetric real gate matrices, and $\ell_{s,k,j}$ for the ordered index word of term $j$ in the observable at wire $k$; these words are strictly increasing and distinct within each observable. The first requirement is that a polynomial-time function compute exactly

$$\tau\!\left( [\tau([u(n_s),u(L_s)])] \mathbin{+\!\!+} \left[ \tau\!\left([\tau([u(i):i\in\ell_{s,k,j}]):j\text{ in term order}]\right) :k=0,\ldots,n_s-1 \right]\right)$$

from $s$. The second requirement concerns the numerical list $D_s$ obtained by concatenating the gate matrices’ entries in gate, row, and column order, then the four entries $(00,01,10,11)$ of each supplied generator factor in generator and wire order, and then the observable coefficients in wire and term order. The supplied factors give the tensor factorizations of $T_s^\dagger c_iT_s$, and the observable words evaluated on these matrices give the single-wire $Z$ operators. There must exist a polynomial-time function $f$ such that, for every $s$, every $j<|D_s|$, every $r\in\mathbb N$, and every Boolean $b$, interpreting $f(\tau([s,u(j),u(r),[b]]))$ as a signed binary integer divided by $2^r$ gives an approximation within $2^{-r}$ of $\operatorname{Re}(D_s)_j$ if $b$ is false and $\operatorname{Im}(D_s)_j$ if $b$ is true. The output’s first bit specifies the sign, true meaning negative, and its tail is the binary magnitude; missing bits are false. Precision $r=0$, empty parameter strings, zero widths, and empty numerical lists are included; entry-approximation requirements are vacuous when the numerical list is empty.

QAlgorithms.Papers.Independent.Intakethird100.P77.IntertwinedFamily.code

For any intertwined family $F$ and finite Boolean string $s$, let $n$ be its base width, $L$ its base gate-list length, $q<n$ its measured-wire index, and $w_1,\ldots,w_K$ the distinct, strictly increasing generator-index words in its observable’s stored term list. Its code is

$$\operatorname{tuple}\!\left[ \operatorname{tuple}[1^n,1^L],\ 1^q,\ \operatorname{tuple}\!\left[ \operatorname{tuple}[1^i:i\text{ occurs in }w_1],\ldots, \operatorname{tuple}[1^i:i\text{ occurs in }w_K] \right]\right].$$

Here $1^a$ denotes $a$ true bits, and tuple encoding concatenates each constituent string after prefixing it with its length in unary followed by a false bit. The inner $\operatorname{tuple}[1^n,1^L]$ is the base-family code. Generator indices are their natural values below $2n$. Empty lists have empty tuple encodings, including empty observable words. This encoding contains the structural indices and counts displayed above; it contains neither matrix entries nor observable coefficients.

QAlgorithms.Papers.Independent.Intakethird100.P77.IntertwinedFamily.data

For any intertwined family $F$ and finite Boolean string $s$, let $n$ be its base width, $h_1,\ldots,h_L$ its ordered list of real skew-symmetric $2n\times2n$ base gate matrices, $F_{i,k}$ its complex $2\times2$ factors satisfying $(T_s^\dagger c_iT_s)_{x,y}=\prod_{k<n}(F_{i,k})_{x_k,y_k}$, and $(w_1,\alpha_1),\ldots,(w_K,\alpha_K)$ its observable terms. Its data is the concatenation of: all entries of $h_1,\ldots,h_L$, embedded into $\mathbb C$, in gate order and then increasing row and column order; all factor entries, for increasing generator index $i<2n$, then increasing wire $k<n$, in the order

$$(F_{i,k})_{\mathrm{false},\mathrm{false}},\ (F_{i,k})_{\mathrm{false},\mathrm{true}},\ (F_{i,k})_{\mathrm{true},\mathrm{false}},\ (F_{i,k})_{\mathrm{true},\mathrm{true}};$$

and finally the coefficients $\alpha_1,\ldots,\alpha_K$ in stored term order. The $c_i$ are the tensor products with preceding $Z$ factors, an $X$ or $Y$ factor at wire $\lfloor i/2\rfloor$ according to the parity of $i$, and identity afterward. Empty gate and term lists contribute no entries.

QAlgorithms.Papers.Independent.Intakethird100.P77.IntertwinedFamily

An intertwined family consists of a base family indexed by finite Boolean strings $s$, giving a natural width $n=n(s)$ and an ordered finite list of real $2n\times2n$ matrices $h$ satisfying $h_{ij}=-h_{ji}$, together with the following additional data and requirements. For each $s$, it supplies a unitary matrix $T_s$ on the basis $\{0,1\}^n$ which normalizes the subgroup generated by all matrices

$$\mathrm i^a\bigotimes_{k<n}P_k,\qquad a\in\{0,1,2,3\},\quad P_k\in\{I,X,Y,Z\},$$

where $X=\begin{pmatrix}0&1\\1&0\end{pmatrix}$, $Y=\begin{pmatrix}0&-\mathrm i\\\mathrm i&0\end{pmatrix}$, and $Z=\operatorname{diag}(1,-1)$. Thus conjugation by $T_s$ preserves that subgroup. Define the matrices $c_i$, $i<2n$, as tensor products with $Z$ on wires $k<\lfloor i/2\rfloor$, with $X$ at wire $\lfloor i/2\rfloor$ when $i$ is even and $Y$ there when $i$ is odd, and identity on later wires. The family supplies complex $2\times2$ matrices $F_{i,k}$ satisfying

$$(T_s^\dagger c_iT_s)_{x,y}=\prod_{k<n}(F_{i,k})_{x_k,y_k}.$$

It also supplies a measured wire $q<n$ and a finite list of pairs $(w,\alpha)$, with $\alpha\in\mathbb C$, whose words $w$ have strictly increasing indices in $\{0,\ldots,2n-1\}$ and do not repeat. These must represent the measured $Z$ matrix:

$$\sum_{(w,\alpha)}\alpha (T_s^\dagger c_{w_1}T_s)\cdots(T_s^\dagger c_{w_{|w|}}T_s)=Z_q,$$

where $Z_q$ is $Z$ on wire $q$ and identity on all other wires. Empty words mean identity, zero coefficients and empty gate lists are allowed, and no degree or effectiveness condition is imposed here. The measured-wire field requires every width to be positive.

QAlgorithms.Papers.Independent.Intakethird100.P77.IsMajoranaRotation

For any natural number $n$ and any real $2n\times2n$ matrix $R$, this predicate means

$$R^{\mathsf T}R=I_{2n}\quad\text{and}\quad\det R=1.$$

When $n=0$, the unique empty matrix satisfies both conditions, with empty determinant equal to $1$.

QAlgorithms.Papers.Independent.Intakethird100.P77.JWFamily.Effective

For a JW family $F$, assigning each finite Boolean string $s$ a natural width $n_s$ and an ordered list of $L_s$ real skew-symmetric $2n_s\times2n_s$ matrices, this property requires both of the following. First, the string function $s\mapsto\mathcal T(1^{n_s},1^{L_s})$ has a polynomial-time Turing-machine realization with identity string encodings, where $1^j$ denotes $j$ true bits and $\mathcal T(w_1,\ldots,w_q)$ concatenates $1^{|w_r|}0w_r$. Second, if $D_s$ is the list of gate entries embedded into $\mathbb C$, in gate order and then increasing row and column order, there exists a polynomial-time Boolean-string function $f$ satisfying, for every $s$, valid index $j<|D_s|$, natural $m$, and Boolean $b$,

$$\left|\operatorname{dyad}_m\!\left(f(\mathcal T(s,1^j,1^m,[b]))\right) -\begin{cases}\operatorname{Im}(D_s[j]),&b=\mathrm{true},\\ \operatorname{Re}(D_s[j]),&b=\mathrm{false}\end{cases}\right|\le 2^{-m}.$$

Here $\operatorname{dyad}_m$ takes a Boolean string’s first bit as a negative sign when true, reads the remaining bits as a most-significant-bit-first binary natural number, and divides the signed value by $2^m$; the empty string represents zero. Precision zero is included, and the numerical condition is vacuous whenever $D_s$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P77.JWFamily.code

For every JW family $F$, which assigns each finite Boolean string $s$ a width $n_s$ and a finite ordered list of real skew-symmetric $2n_s\times2n_s$ matrices, the definition returns $\mathcal T(1^{n_s},1^{L_s})$, where $L_s$ is the gate-list length, $1^j$ is the string of $j$ true bits, and $\mathcal T(w_1,\ldots,w_q)$ concatenates $1^{|w_r|}$, one false bit and $w_r$ for each argument in order. Thus the returned string is $1^{n_s}0\,1^{n_s}1^{L_s}0\,1^{L_s}$. Zero widths and empty gate lists are included; when both numbers are zero the result consists of two false bits.

QAlgorithms.Papers.Independent.Intakethird100.P77.JWFamily.data

For every JW family $F$ and finite Boolean string $s$, let $n_s$ be its width and let $h_0,\ldots,h_{L_s-1}$ be its ordered list of real skew-symmetric $2n_s\times2n_s$ matrices. The definition returns the complex-number list of all entries of $h_0$, then all entries of $h_1$, and so on, with each matrix traversed in increasing row-index order and then increasing column-index order, and with each real entry embedded into $\mathbb C$. It retains zero and repeated entries and has length $L_s(2n_s)^2$. It is empty if the gate list is empty or the width is zero.

QAlgorithms.Papers.Independent.Intakethird100.P77.JWFamily

A JW family consists of a natural-number width $n_s$ for every finite Boolean string $s$, together with a finite ordered list of real $2n_s\times2n_s$ matrices for each $s$, and a requirement that every matrix $h$ appearing in that list satisfies $h_{ij}=-h_{ji}$ for all indices $i,j<2n_s$. Width zero, empty input strings and empty gate lists are allowed; at width zero the matrix indices are empty and skew-symmetry is vacuous. No computability condition or bound on widths, gate-list lengths or matrix entries is part of this structure.

QAlgorithms.Papers.Independent.Intakethird100.P77.ParityApp.Allowable

For every natural number $n$ and every application $g$ consisting of two Boolean-indexed complex unitary matrices $A_g,B_g$ and an injection of two ordered wires into $n$ wires, this predicate means exactly $\det A_g=\det B_g$. It adds no condition on the wire positions beyond their already required distinctness. For $n=0$ or $n=1$, there is no such application $g$.

QAlgorithms.Papers.Independent.Intakethird100.P77.ParityApp

For each natural number $n$, an object of this structure consists of two complex unitary matrices $A$ and $B$, each with Boolean row and column indices, together with an injective map $w:\{0,1\}\to\{0,\ldots,n-1\}$ specifying two ordered, distinct wires. No equality of $\det A$ and $\det B$ is required by the structure. Such an object cannot exist when $n=0$ or $n=1$, because the required injection then cannot exist.

QAlgorithms.Papers.Independent.Intakethird100.P77.ParityApp.toGateApp

For every natural number $n$ and every application $g$ consisting of Boolean-indexed complex unitary matrices $A_g,B_g$ and an injective two-wire map $w_g$, this function constructs an application of a gate from the set of all gates on the same $n$ wires. The constructed gate has arity $2$ and matrix entries indexed by two-bit strings $x,y$: the entry is $0$ when their exclusive-or parities differ, $A_g(x_0,y_0)$ when both parities are false, and $B_g(x_0,y_0)$ when both are true. Its wire map is exactly $w_g$. No hypothesis $\det A_g=\det B_g$ is imposed; for $n<2$ there is no input application $g$.

QAlgorithms.Papers.Independent.Intakethird100.P77.ParityFamily.Effective

For every family $F$ of finite lists of two-wire applications indexed by finite Boolean strings, this predicate requires both an exact polynomial-time computation of its structural encoding and polynomial-time approximations to its matrix entries. More precisely, let $u(k)$ be $k$ true bits, and let $T$ encode a list of strings by prefixing each constituent string $x$ with $u(|x|)$ followed by a false bit. If $F$ has width $w$ and $L$ applications at $s$, with ordered wires $(i_j,j_j)$, there must be a polynomial-time computable string function returning exactly $T([u(w),u(L),T([u(i_1),u(j_1)]),\ldots,T([u(i_L),u(j_L)])])$. Separately, form $d(s)$ by listing, for each application in order, the entries $00,01,10,11$ of its first unitary matrix and then those of its second. There must be a polynomial-time computable string function $f$ such that, for every $s$, index $0\le j<|d(s)|$, natural number $m$, and Boolean $b$, the string $f(T([s,u(j),u(m),[b]]))$, interpreted as a signed binary integer divided by $2^m$, differs by at most $2^{-m}$ from $\operatorname{Re}d(s)_j$ when $b$ is false and from $\operatorname{Im}d(s)_j$ when $b$ is true. In this interpretation, the first output bit is the sign, true meaning negative, and the remaining bits give the binary magnitude from most significant to least significant; missing bits contribute zero. Precision $m=0$ is included, and an empty data list imposes no entry-approximation conditions.

QAlgorithms.Papers.Independent.Intakethird100.P77.ParityFamily.code

For every family $F$ assigning a width $w(s)$ and a list of two-wire applications to each finite Boolean string $s$, this function returns the following Boolean string. Write $u(k)$ for $k$ consecutive true bits, and define $T([x_1,\ldots,x_\ell])$ by concatenating $u(|x_j|)$, one false bit, and $x_j$, for each $j$ in order. If the application list at $s$ is $[g_1,\ldots,g_L]$, with ordered wire indices $i_j,j_j$, the returned string is

$$T\bigl([u(w(s)),u(L),T([u(i_1),u(j_1)]),\ldots,T([u(i_L),u(j_L)])]\bigr).$$

Each application also contains two unitary $2\times2$ complex matrices, but their entries do not occur in this string. Empty application lists and width zero are included.

QAlgorithms.Papers.Independent.Intakethird100.P77.ParityFamily.data

For every family $F$ assigning a width and a finite ordered list of two-wire applications to each finite Boolean string $s$, this function returns a list of complex numbers obtained by traversing the applications in order. For each application, whose two unitary $2\times2$ matrices are $A$ and $B$, it appends

$$[A_{00},A_{01},A_{10},A_{11},B_{00},B_{01},B_{10},B_{11}],$$

where $0$ means false and $1$ means true. Thus a list of $L$ applications gives $8L$ entries, and an empty application list gives an empty data list.

QAlgorithms.Papers.Independent.Intakethird100.P77.ParityFamily

A value of this structure consists of a function assigning a natural number $w(s)$ to every finite Boolean string $s$, and, for each such $s$, a finite ordered list of applications on $w(s)$ wires. Each application contains two unitary complex matrices indexed by $\{\mathrm{false},\mathrm{true}\}$, together with an injection from $\{0,1\}$ into $\{0,\ldots,w(s)-1\}$, specifying two distinct ordered wires. The structure imposes no determinant equality, distance bound, or computability requirement. Width zero is allowed; at widths zero and one the application list must be empty.

QAlgorithms.Papers.Independent.Intakethird100.P77.ProductInputs.data

For any width function $w$ on finite Boolean strings, any assignment $I$ of unit-norm complex two-component vectors $\phi_{s,i}$ for $0\le i<w(s)$, and any string $s$, this function returns the complex list

$$[\phi_{s,0}(\mathrm{false}),\phi_{s,0}(\mathrm{true}),\ldots, \phi_{s,w(s)-1}(\mathrm{false}),\phi_{s,w(s)-1}(\mathrm{true})].$$

The factors are listed in increasing wire order, with the false component before the true component. The list has length $2w(s)$ and is empty when $w(s)=0$.

QAlgorithms.Papers.Independent.Intakethird100.P77.ProductInputs

For any function $w$ from finite Boolean strings to natural numbers, a value of this structure assigns to every string $s$ and every index $i\in\{0,\ldots,w(s)-1\}$ a complex vector $\phi_{s,i}$ indexed by the two Boolean values, and includes the requirement

$$|\phi_{s,i}(\mathrm{false})|^2+|\phi_{s,i}(\mathrm{true})|^2=1.$$

There is no computability requirement. Width zero is allowed, in which case there are no factors or normalization conditions at that string.

QAlgorithms.Papers.Independent.Intakethird100.P77.RangeBound

For every natural number $n$, natural number $r$, and finite list $c$ of gate applications on $n$ wires, each application consisting of two unitary $2\times2$ complex matrices and an ordered pair of distinct wire indices, this predicate means that every application $g$ in $c$ has wire indices $i_g,j_g\in\{0,\ldots,n-1\}$ satisfying $|i_g-j_g|\le r$. The condition holds vacuously for an empty list; because the two indices are distinct, $r=0$ permits only an empty list.

QAlgorithms.Papers.Independent.Intakethird100.P77.SelectedStrongSimulation

For any function $p$ assigning a real number $p(s,b)$ to each finite Boolean string $s$ and each Boolean $b$, this property means that there exists a polynomial-time computable function $f$ from finite Boolean strings to finite Boolean strings such that, for every $s$, every natural number $m$, and both values of $b$,

$$\left|\operatorname{dyad}_m\!\left(f\!\left(\operatorname{tuple}[s,1^m,[b]]\right)\right)-p(s,b)\right|\le 2^{-m}.$$

Here $1^m$ is the string of $m$ true bits; $\operatorname{tuple}[w_1,\ldots,w_k]$ concatenates, for each $w_i$, the string $1^{|w_i|}$, a false bit, and then $w_i$ itself. To obtain $\operatorname{dyad}_m(w)$, interpret the tail of $w$ as a binary natural number, reading from left to right by the update $a\mapsto 2a+b$, negate this number exactly when the first bit is true, and divide by $2^m$. An empty string has default first bit false and binary value zero. Polynomial-time computability uses the identity encodings of input and output Boolean strings. The quantifiers include the empty input string and $m=0$, where the permitted error is $1$; no probability or range restriction on $p$ is imposed.

QAlgorithms.Papers.Independent.Intakethird100.P77.Skew

For any natural number $n$ and any real matrix $h$ indexed by $\{0,\ldots,2n-1\}$, this predicate means

$$h_{ij}=-h_{ji}\qquad\text{for every }0\le i,j<2n.$$

In particular, every diagonal entry must be zero. When $n=0$, there are no indices and the condition holds vacuously.

QAlgorithms.Papers.Independent.Intakethird100.P77.SourceFamily.Effective

For a family $F$ assigning a width and an instruction list to each finite Boolean string $s$, this property is the conjunction of two requirements. Define $u(k)$ to be $k$ true bits and define $\operatorname{tuple}(x_1,\ldots,x_r)$ by concatenating $|x_j|$ true bits, one false bit, and $x_j$ for each component in order. First, the function sending $s$ to $\operatorname{tuple}(u(F.\mathrm{width}(s)),u(|F.\mathrm{gates}(s)|),\text{instruction records})$ is computable by a polynomial-time Turing machine on Boolean strings with identity input and output encodings; a one-wire instruction on $k$ has record $\operatorname{tuple}([\mathrm{false}],u(k))$, and an adjacent controlled-$Z$ instruction on $w(0),w(1)$ has record $\operatorname{tuple}([\mathrm{true}],u(w(0)),u(w(1)))$. Second, there exists a polynomial-time computable Boolean-string function $f$ such that, for every $s$, every index $j$ of the list $d(s)$ obtained by concatenating the four entries of each one-wire unitary in row order false, true while omitting controlled-$Z$ instructions, every natural precision $m$, and every Boolean $b$, the string $v=f(\operatorname{tuple}(s,u(j),u(m),[b]))$ satisfies $\left|\operatorname{dyad}_m(v)-(\operatorname{Im}d(s)_j\text{ if }b=\mathrm{true},\text{ otherwise }\operatorname{Re}d(s)_j)\right|\le2^{-m}$. Here $\operatorname{dyad}_m(v)$ reads the first bit as a sign, negative for true and positive for false, interprets the remaining bits as an unsigned binary integer in most-significant-first order, and divides that signed integer by $2^m$; missing bits default to false, so the empty string represents zero. Precision $m=0$ is included, and when $d(s)$ is empty there are no entry-index requirements for that $s$.

QAlgorithms.Papers.Independent.Intakethird100.P77.SourceFamily.code

For every family $F$ assigning a width and a finite instruction list to each finite Boolean string, and every input string $s$, this definition produces the following Boolean encoding. Let $u(k)$ be the string of $k$ true bits, and let $\operatorname{tuple}(x_1,\ldots,x_r)$ concatenate, for each $x_j$ in order, $|x_j|$ true bits, one false bit, and then $x_j$ itself. The result is $\operatorname{tuple}$ applied to the list beginning with $u(F.\mathrm{width}(s))$ and $u(|F.\mathrm{gates}(s)|)$, followed by one record for each instruction in its list order. A one-wire instruction on wire $k$ contributes $\operatorname{tuple}([\mathrm{false}],u(k))$, while a controlled-$Z$ instruction on ordered adjacent wires $w(0),w(1)$ contributes $\operatorname{tuple}([\mathrm{true}],u(w(0)),u(w(1)))$. The one-wire unitary matrices are not included in this encoding.

QAlgorithms.Papers.Independent.Intakethird100.P77.SourceFamily.data

For every family $F$ assigning a width and a finite instruction list to each finite Boolean string, and every input string $s$, this definition forms a list of complex numbers by traversing $F.\mathrm{gates}(s)$ in order and concatenating the contributions of its instructions. A one-wire instruction with unitary matrix $A$ contributes the four entries $[A_{\mathrm{false},\mathrm{false}},A_{\mathrm{false},\mathrm{true}},A_{\mathrm{true},\mathrm{false}},A_{\mathrm{true},\mathrm{true}}]$ in exactly that order; a controlled-$Z$ instruction contributes the empty list. Consequently, the resulting list is empty if there are no one-wire instructions.

QAlgorithms.Papers.Independent.Intakethird100.P77.SourceFamily

This structure consists of a function assigning a natural-number width to every finite Boolean string $s$, together with a finite list of instructions on that many wires for each $s$. Each instruction is either an arbitrary unitary $2\times2$ complex matrix on one specified wire or a controlled-$Z$ instruction on an injectively selected ordered pair $w(0),w(1)$ satisfying $w(1)=w(0)+1$. No computability or size condition is part of this structure; a string assigned width zero necessarily has an empty instruction list.

QAlgorithms.Papers.Independent.Intakethird100.P77.SourceStep

For each natural number $n$, this defines a type of instructions with two constructors: a one-wire instruction specified by an arbitrary Boolean-indexed unitary $2\times2$ complex matrix $A$ and a wire $k\in\{0,\ldots,n-1\}$; or a controlled-$Z$ instruction specified by an injection $w:\{0,1\}\hookrightarrow\{0,\ldots,n-1\}$ together with the condition $w(1)=w(0)+1$. There are no instructions when $n=0$, and the second constructor is unavailable when $n<2$.

QAlgorithms.Papers.Independent.Intakethird100.P77.SourceStep.toGateApp

For every natural number $n$, this maps an instruction on $n$ wires to a gate application whose allowed gate set consists of all gates. A one-wire instruction with unitary matrix $A$ and wire $k$ becomes an arity-one gate with matrix entry $A_{x_0,y_0}$ for one-bit strings $x,y$, applied through the injection sending its sole wire to $k$. A controlled-$Z$ instruction with injection $w$ becomes an arity-two gate applied through $w$, whose matrix entry on two-bit strings $x,y$ is $-1$ if $x=y$ and both bits are true, $1$ if $x=y$ and they are not both true, and $0$ if $x\ne y$. The adjacency proof carried by the controlled-$Z$ instruction does not contribute any additional data to the resulting gate application.

QAlgorithms.Papers.Independent.Intakethird100.P77.StrongSimulation

For any function $\mathrm{width}$ from finite Boolean strings to natural numbers and any family of real numbers $p(s,k,b)$ indexed by a string $s$, an integer $0\le k<\mathrm{width}(s)$, and a Boolean $b$, this predicate means that there exists one function $f$ from Boolean strings to Boolean strings, computable in polynomial time by a TM2 machine with identity input and output encodings, satisfying the following requirement for every $s$, every natural number $m$, every such $k$, and both values of $b$: prefix each of the four strings $s$, $1^m$, $1^k$, and $[b]$ by its unary length followed by false, concatenate them in that order, and apply $f$; the output, interpreted as a signed binary integer divided by $2^m$, differs from $p(s,k,b)$ by at most $2^{-m}$. The output’s first bit supplies the sign, with true meaning negative, and its remaining bits supply the binary magnitude; empty outputs and outputs of length one represent $0$. Precision $m=0$ is included. When $\mathrm{width}(s)=0$, there are no requirements for that $s$. No probability bounds or normalization conditions on $p$, and no computability condition on $\mathrm{width}$ itself, are part of this predicate.

QAlgorithms.Papers.Independent.Intakethird100.P77.SupportedOnPair

For every natural number $n$, every injection $w:\{0,1\}\hookrightarrow\{0,\ldots,n-1\}$, and every real matrix $h$ indexed in both coordinates by $\{0,\ldots,2n-1\}$, this property means that, for all indices $i,j<2n$,

$$\left(\left\lfloor\frac i2\right\rfloor\notin\{w(0),w(1)\} \ \text{or}\ \left\lfloor\frac j2\right\rfloor\notin\{w(0),w(1)\}\right) \ \Longrightarrow\ h_{ij}=0.$$

Equivalently, entries may be nonzero only when both indices belong to $\{2w(0),2w(0)+1,2w(1),2w(1)+1\}$. There is no additional restriction on entries within that submatrix, and skew-symmetry is not required by this property. The injection requires two distinct wires, so no such $w$ exists when $n<2$.

QAlgorithms.Papers.Independent.Intakethird100.P77.basisInput

For every natural number $n$ and finite Boolean string $x$, this defines the vector in $\mathbb C^{\{0,1\}^n}$ whose amplitude is one at the bit string $z$ given by $z_i=x_i$ when position $i$ exists in $x$, and $z_i=\mathrm{false}$ otherwise, and whose other amplitudes are zero. Consequently, positions of $x$ beyond the first $n$ are unused, and missing positions among the first $n$ are filled with false. When $n=0$, the vector has amplitude one at the unique empty bit string, for every $x$.

QAlgorithms.Papers.Independent.Intakethird100.P77.binaryNat

For every finite Boolean string $w=[b_1,\ldots,b_r]$, this function returns the natural number obtained by starting at $a=0$ and, reading the string from left to right, replacing $a$ by $2a+1$ when the next bit is true and by $2a$ when it is false. Equivalently, identifying false with $0$ and true with $1$, its value is $\sum_{i=1}^r b_i2^{r-i}$. The empty string has value $0$, and leading false bits are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P77.circuitRotation

For any natural number $n$ and any finite list $[h_1,\ldots,h_r]$ of arbitrary real $2n\times2n$ matrices, this defines the real matrix

$$\exp(-4h_r)\cdots\exp(-4h_1).$$

The exponentials are matrix exponentials, and the factors occur in reverse list order. There is no skew-symmetry assumption on the matrices in the list. An empty list gives $I_{2n}$; when $n=0$, the result is the unique empty identity matrix.

QAlgorithms.Papers.Independent.Intakethird100.P77.conjugatedGenerators

For any natural number $n$, any unitary matrix $T$ indexed by length-$n$ bit strings, any family $c_0,\ldots,c_{2n-1}$ of complex matrices indexed by those strings, and any index $i\in\{0,\ldots,2n-1\}$, this defines the matrix

$$T^\dagger c_iT,$$

where $T^\dagger$ is the conjugate transpose. No algebraic relations on the matrices $c_i$ are assumed. The parameter $n=0$ is permitted, but there is then no index $i$ at which to evaluate this family.

QAlgorithms.Papers.Independent.Intakethird100.P77.dyadic

For every finite Boolean string $w$ and every natural number $m$, this function returns $(-1)^bN/2^m$, where $b$ is the first bit of $w$, interpreted as $0$ for false and $1$ for true, and $N$ is the natural number represented in binary by the remaining bits, read from left to right with the most significant bit first. If $w$ is empty, the first bit defaults to false and the remaining string is empty, whose binary value is $0$. Consequently, empty strings and strings of length one both give $0$. The parameter $m$ may be $0$, in which case the denominator is $1$; no relationship between $m$ and the length of $w$ is required.

QAlgorithms.Papers.Independent.Intakethird100.P77.encodeFourBits

For every natural number $n$ and every Boolean string $x$ indexed by $\{0,\ldots,n-1\}$, this definition produces a Boolean string of length $4n$ by replacing each input bit $x_k$ with the four-bit block $(x_k,\mathrm{false},\mathrm{false},x_k)$. Equivalently, its bit at index $i<4n$ is $x_{\lfloor i/4\rfloor}$ when $i\bmod4$ is $0$ or $3$, and is false otherwise. For $n=0$, it returns the unique empty indexed Boolean string.

QAlgorithms.Papers.Independent.Intakethird100.P77.encodeState

For any natural numbers $n,m$, any function $e$ from length-$n$ bit strings to length-$m$ bit strings, and any complex Euclidean vector $\psi$ indexed by length-$n$ bit strings, this defines the vector

$$\sum_{x\in\{0,1\}^n}\psi_x\,|e(x)\rangle,$$

where $|y\rangle$ has coordinate $1$ at $y$ and $0$ elsewhere. Equivalently, its coordinate at $y$ is $\sum_{x:e(x)=y}\psi_x$. No injectivity assumption on $e$ or normalization assumption on $\psi$ is imposed: amplitudes with the same image are added, and a coordinate with no preimage is zero. Both $n=0$ and $m=0$ are included; a zero-length bit-string space has one element.

QAlgorithms.Papers.Independent.Intakethird100.P77.encodeTwoBits

For every natural number $n$ and every bit string $x:\{0,\ldots,n-1\}\to\{\mathrm{false},\mathrm{true}\}$, this defines a bit string of length $2n$ whose coordinate $i$ is $x_{\lfloor i/2\rfloor}$. Thus each input bit appears twice, consecutively:

$$(x_0,x_1,\ldots,x_{n-1})\longmapsto(x_0,x_0,x_1,x_1,\ldots,x_{n-1},x_{n-1}).$$

The definition includes $n=0$, when both strings are empty.

QAlgorithms.Papers.Independent.Intakethird100.P77.entries

For every complex matrix $A$ whose rows and columns are indexed by the two Boolean values, this function returns the four-entry list $[A_{\mathrm{false},\mathrm{false}},A_{\mathrm{false},\mathrm{true}},A_{\mathrm{true},\mathrm{false}},A_{\mathrm{true},\mathrm{true}}]$. There are no assumptions on $A$, such as unitarity or Hermitian symmetry.

QAlgorithms.Papers.Independent.Intakethird100.P77.expandedWord

For any natural number $n$, any arbitrary family $c_i$, $0\le i<2n$, of complex matrices indexed by $Q_n=\{0,1\}^n$, any arbitrary real $2n\times2n$ matrix $R$, and any finite index list $l=[i_1,\ldots,i_r]$, this defines

$$\sum_{j_1,\ldots,j_r\in\{0,\ldots,2n-1\}} \left(\prod_{a=1}^{r}R_{i_a j_a}\right)c_{j_1}\cdots c_{j_r},$$

with the real coefficient regarded as a complex scalar. The summation ranges over all choices of indices, including repeated choices, and the matrix factors retain their position order. No ordering condition on $l$, relations among the $c_i$, or orthogonality condition on $R$ are imposed. For an empty list, there is one empty choice of indices, the scalar product is $1$, and the result is the identity matrix; this also covers the only possible list when $n=0$.

QAlgorithms.Papers.Independent.Intakethird100.P77.gaussianCircuit

For any natural number $n$, any arbitrary family $c_i$, $0\le i<2n$, of complex matrices indexed by $Q_n=\{0,1\}^n$, and any finite list $[h_1,\ldots,h_r]$ of real $2n\times2n$ matrices, this defines

$$G(c,h_r)\cdots G(c,h_1), \qquad G(c,h)=\exp\!\left(-\sum_{\substack{0\le i,j<2n\\i\ne j}}h_{ij}c_i c_j\right).$$

Thus the factors occur in reverse list order. Neither skew-symmetry of the matrices $h_k$ nor any relations among the matrices $c_i$ are required. An empty list gives the identity matrix; when $n=0$, every factor and hence the resulting product is the identity.

QAlgorithms.Papers.Independent.Intakethird100.P77.gaussianOperation

For any natural number $n$, any family $c_i$ of complex matrices indexed by $Q_n=\{0,1\}^n$, with $0\le i<2n$, and any real $2n\times2n$ matrix $h$, this defines

$$G(c,h)=\exp\!\left(\mathrm{i}\left[\mathrm{i}\sum_{\substack{0\le i,j<2n\\i\ne j}}h_{ij}c_i c_j\right]\right) =\exp\!\left(-\sum_{\substack{0\le i,j<2n\\i\ne j}}h_{ij}c_i c_j\right),$$

where $\exp$ is the matrix exponential and multiplication inside the sum is matrix multiplication. No relations on the matrices $c_i$ or skew-symmetry of $h$ are required. When $n=0$, this is the identity matrix.

QAlgorithms.Papers.Independent.Intakethird100.P77.jordanWigner

For every natural number $n$ and every index $i\in\{0,\ldots,2n-1\}$, write $q=\lfloor i/2\rfloor$. The definition gives the complex matrix on Boolean strings $x,y$ of length $n$ whose entry is

$$\prod_{k=0}^{n-1}M_k(x_k,y_k),\qquad M_k=\begin{cases} Z,&k<q,\\ X,&k=q\text{ and }i\text{ is even},\\ Y,&k=q\text{ and }i\text{ is odd},\\ I,&k>q, \end{cases}$$

where, in the Boolean order $(\mathrm{false},\mathrm{true})$,

$$X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad Y=\begin{pmatrix}0&-\mathrm i\\\mathrm i&0\end{pmatrix},\qquad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}.$$

The case $n=0$ is included in the natural-number parameter, but then there is no permissible index $i$.

QAlgorithms.Papers.Independent.Intakethird100.P77.majoranaWord

For any natural number $n$, any family $c_i$, $0\le i<2n$, of arbitrary complex matrices indexed by $Q_n=\{0,1\}^n$, and any finite list $l=[i_1,\ldots,i_r]$ of these indices, this defines the ordered matrix product

$$c_{i_1}c_{i_2}\cdots c_{i_r}.$$

Repeated indices and arbitrary index order are allowed, and no relations among the matrices are assumed. The empty list gives the identity matrix; when $n=0$, the empty list is the only possible list.

QAlgorithms.Papers.Independent.Intakethird100.P77.modifiedSwap

For every natural number $n$, every family $c_0,\ldots,c_{2n-1}$ of arbitrary complex matrices indexed by $n$-bit strings, and every injection $w:\{0,1\}\hookrightarrow\{0,\ldots,n-1\}$, write $c_{a,b}=c_{2w(a)+b}$ for $a,b\in\{0,1\}$. This definition is the matrix $\exp\!\left(-\frac{\pi}{4}\left[-c_{0,0}c_{1,1}+c_{0,1}c_{1,0}+c_{0,0}c_{0,1}+c_{1,0}c_{1,1}\right]\right)$, where products are matrix products in the displayed order. The matrices $c_j$ need not satisfy any anticommutation or Hermiticity conditions, and the two selected wires need not be adjacent; their injection requires $n\ge2$.

QAlgorithms.Papers.Independent.Intakethird100.P77.outputExpectation

For every natural number $n$, arbitrary complex matrices $U,A$ indexed by Boolean strings of length $n$, and arbitrary complex vector $\psi$ on those strings, this function returns the complex number

$$\langle U\psi,A(U\psi)\rangle =\sum_{x\in\{0,1\}^n} \overline{(U\psi)_x}\sum_{y\in\{0,1\}^n}A_{xy}(U\psi)_y, \qquad (U\psi)_x=\sum_yU_{xy}\psi_y.$$

No unitarity, normalization, or Hermitian assumptions are imposed, and the result is not required to be real. The definition includes $n=0$, where the indexing set contains the single empty string.

QAlgorithms.Papers.Independent.Intakethird100.P77.pairMajor

For every natural number $n$, every injection $w:\{0,1\}\hookrightarrow\{0,\ldots,n-1\}$, every $a\in\{0,1\}$, and every Boolean $b$, this definition returns the index $2w(a)+b$ in $\{0,\ldots,2n-1\}$, interpreting false as $0$ and true as $1$. Thus it selects the even or odd index associated with the chosen wire. The injection requires $n\ge2$; no adjacency condition is imposed.

QAlgorithms.Papers.Independent.Intakethird100.P77.parityCircuit

For every natural number $n$ and every finite list $c$ of applications, each consisting of two Boolean-indexed complex unitary matrices $A,B$ and an injection specifying two ordered, distinct wires among $n$ wires, this function returns a circuit over the set of all gates by replacing each application, in the same list order, with the arity-$2$ gate on those wires whose $(x,y)$ entry is $0$ for differing two-bit exclusive-or parities, $A(x_0,y_0)$ for common parity false, and $B(x_0,y_0)$ for common parity true. The resulting circuit is a list of the same length as $c$; no determinant-equality or wire-distance condition is required. An empty input list gives an empty circuit, and when $n<2$ the input list must be empty.

QAlgorithms.Papers.Independent.Intakethird100.P77.parityGate

For any two complex matrices $A$ and $B$ indexed by Boolean rows and columns, this function defines a matrix indexed by two-bit strings $x=(x_0,x_1)$ and $y=(y_0,y_1)$. Its $(x,y)$ entry is $0$ if $x_0\mathbin{\oplus}x_1\ne y_0\mathbin{\oplus}y_1$, is $A_{x_0,y_0}$ if both parities are false, and is $B_{x_0,y_0}$ if both parities are true, where $\oplus$ is exclusive-or. Thus, in the order $00,01,10,11$, the resulting matrix is

$$\begin{pmatrix} A_{00}&0&0&A_{01}\\ 0&B_{00}&B_{01}&0\\ 0&B_{10}&B_{11}&0\\ A_{10}&0&0&A_{11} \end{pmatrix}.$$

Here the subscripts $0,1$ on $A$ and $B$ denote false,true; no assumptions on either matrix are required.

QAlgorithms.Papers.Independent.Intakethird100.P77.permutationOperator

For every natural number $n$ and every permutation $p$ of the indices $\{0,\ldots,n-1\}$, this defines the complex matrix indexed by length-$n$ bit strings whose entry in row $x$ and column $y$ is

$$(P_p)_{x,y}= \begin{cases} 1,&x_i=y_{p(i)}\text{ for every }i,\\ 0,&\text{otherwise}. \end{cases}$$

Thus it sends the coordinate vector $|y\rangle$ to $|y\circ p\rangle$. The case $n=0$ is included, giving the $1\times1$ matrix with entry $1$.

QAlgorithms.Papers.Independent.Intakethird100.P77.productOperator

For every natural number $n$ and every family $P_0,\ldots,P_{n-1}$ of arbitrary complex matrices indexed by the Boolean values, this function defines a matrix on Boolean strings of length $n$ by

$$\bigl(\operatorname{productOperator}(P)\bigr)_{xy} =\prod_{i=0}^{n-1}(P_i)_{x_i y_i}.$$

No normalization, Hermitian, or unitarity conditions are imposed. When $n=0$, the empty product is $1$, giving the $1\times1$ matrix with entry $1$.

QAlgorithms.Papers.Independent.Intakethird100.P77.quadraticHamiltonian

For any natural number $n$, let $Q_n=\{0,1\}^n$, let $c_0,\ldots,c_{2n-1}$ be arbitrary complex matrices indexed by $Q_n$, and let $h$ be an arbitrary real $2n\times2n$ matrix. This defines the complex matrix

$$H(c,h)=\mathrm{i}\sum_{\substack{0\le i,j<2n\\i\ne j}}h_{ij}c_i c_j.$$

The sum includes all ordered pairs of distinct indices and ignores every diagonal entry of $h$. No Hermiticity, anticommutation, or skew-symmetry assumption is imposed. When $n=0$, the sum is empty and the result is the zero matrix on the singleton set $Q_0$.

QAlgorithms.Papers.Independent.Intakethird100.P77.singleWireProbability

For every natural number $n$, arbitrary complex matrix $U$ indexed by Boolean strings of length $n$, arbitrary complex vector $\psi$ on those strings, wire $k\in\{0,\ldots,n-1\}$, and Boolean $b$, this function returns

$$\sum_{\substack{x\in\{0,1\}^n\\x_k=b}} \left|\sum_{y\in\{0,1\}^n}U_{xy}\psi_y\right|^2.$$

No unitarity of $U$ or normalization of $\psi$ is assumed, so the definition itself does not require this number to lie in $[0,1]$. Although $n$ ranges over all natural numbers, supplying $k$ is impossible when $n=0$.

QAlgorithms.Papers.Independent.Intakethird100.P77.sourceCircuit

For every natural number $n$ and every finite list $c$ of instructions on $n$ wires, this definition produces a circuit over the set of all gates by replacing each instruction, in the same list order, with its gate application: a unitary one-wire instruction becomes the corresponding arity-one gate on its specified wire, and a controlled-$Z$ instruction becomes the arity-two diagonal gate with diagonal entries $1,1,1,-1$ on its specified ordered adjacent pair. A circuit here is simply a list of such gate applications, so the empty instruction list produces the empty circuit.

QAlgorithms.Papers.Independent.Intakethird100.P77.tupleCode

For every finite list $[x_1,\ldots,x_r]$ of finite Boolean strings, this function returns the concatenation $(1^{|x_1|}0)x_1\cdots(1^{|x_r|}0)x_r$, where $1^k$ denotes $k$ copies of true, $0$ denotes false, and $|x_i|$ is the length of $x_i$. Thus each string is preceded by its length in unary followed by false; there is no separate prefix specifying the number of strings. The empty list produces the empty string, and an empty component contributes just one false.

QAlgorithms.Papers.Independent.Intakethird100.P77.zOperator

For every natural number $n$ and wire $k\in\{0,\ldots,n-1\}$, this function defines the matrix on Boolean strings of length $n$ obtained by taking the product of single-wire matrix entries, using $\operatorname{diag}(1,-1)$ on wire $k$ and the identity on every other wire. Equivalently, its entries are

$$(Z_k)_{xy}= \begin{cases} 1,&x=y\text{ and }x_k=\mathrm{false},\\ -1,&x=y\text{ and }x_k=\mathrm{true},\\ 0,&x\ne y. \end{cases}$$

There is no possible wire argument when $n=0$.