8 Commutativity

8.1 Commutativity of the point measurements

Definition 8.1 Shared diagonal-line sample

✓

Sample a uniformly random ordered point pair $(u,v)$ and a uniformly random parameter $t \in \mathbb {F}_q$. Package this data as the diagonal line whose direction is $v-u$ and whose parametrization visits $u$ at $t$ and $v$ at $t+1$.

Theorem 8.2 Commutativity of the point measurements

✓

Let $(\psi ,A,B,L)$ be an $(\varepsilon ,\delta ,\gamma )$-good symmetric strategy for the $(m,q,d)$ low individual degree test. On average over independent and uniformly random $u,v \sim \mathbb {F}_q^m$,

\[ (A_a^u A_b^v) \otimes I \approx _{32\gamma m} (A_b^v A_a^u) \otimes I. \]

Proof ▶

By Definition 2.13, the strategy passes the $m$-restricted diagonal lines test with probability $1-\gamma m$. Hence

\[ A_a^u \otimes I \simeq _{\gamma m} I \otimes L^\ell _{[f(u)=a]} \]

on average over uniformly random $u \sim \mathbb {F}_q^m$ and a uniformly random line $\ell $ in $\mathbb {F}_q^m$ containing $u$. By 3.21,

\begin{equation} \label{eq:point-diagonal-line-approx} A_a^u \otimes I \approx _{2\gamma m} I \otimes L^\ell _{[f(u)=a]}. \end{equation}

Let $u$ and $v$ be independent uniformly random points in $\mathbb {F}_q^m$, and let $\ell $ be a uniformly random line containing both points. The marginal distribution on $(u,\ell )$ and on $(v,\ell )$ is the same as above, so

\begin{align*} (A_a^u A_b^v) \otimes I & \approx _{2\gamma m} A_a^u \otimes L^\ell _{[f(v)=b]} \tag {by \ref{eq:point-diagonal-line-approx}} \\ & \approx _{2\gamma m} I \otimes \bigl(L^\ell _{[f(v)=b]} L^\ell _{[f(u)=a]}\bigr) \tag {by \ref{eq:point-diagonal-line-approx}} \\ & = I \otimes \bigl(L^\ell _{[f(u)=a]} L^\ell _{[f(v)=b]}\bigr) \tag {because~ $L$ is projective} \\ & \approx _{2\gamma m} A_b^v \otimes L^\ell _{[f(u)=a]} \tag {by \ref{eq:point-diagonal-line-approx}} \\ & \approx _{2\gamma m} (A_b^v A_a^u) \otimes I. \tag {by \ref{eq:point-diagonal-line-approx}} \end{align*}

The theorem follows from 3.27.

8.2 Commutativity of $G$ after evaluation

Lemma 8.3 Commutativity of $G$ after evaluation

✓

Let $(\psi ,A,B,L)$ be an $(\varepsilon ,\delta ,\gamma )$-good symmetric strategy for the $(m+1,q,d)$ low individual degree test. Let $\{ G^x\} \in \mathrm{PolySub}(m,q,d)$ be a collection of projective sub-measurements indexed by $x \in \mathbb {F}_q$ with the following properties:

(Consistency with $A$) On average over $(u,x) \sim \mathbb {F}_q^{m+1}$,

\[ A_a^{u,x} \otimes I \simeq _\zeta I \otimes G^x_{[g(u)=a]}. \]
(Strong self-consistency) On average over $x \sim \mathbb {F}_q$,

\[ G_g^x \otimes I \approx _\zeta I \otimes G_g^x. \]
(Boundedness) There exists a positive-semidefinite matrix $Z^x$ for each $x \in \mathbb {F}_q$ such that

\[ \mathbb {E}_x \langle \psi \rvert (I-G^x) \otimes Z^x \lvert \psi \rangle \le \zeta \]

and for each $x \in \mathbb {F}_q$ and $g \in \mathcal{P}(m,q,d)$,

\[ Z^x \ge \left(\mathbb {E}_u A_{g(u)}^{u,x}\right). \]

Let

\[ \nu = 48m\bigl(\gamma ^{1/2}+\zeta ^{1/2}\bigr). \]

Then on average over independent and uniformly random $(u,x),(v,y) \sim \mathbb {F}_q^{m+1}$,

\[ G^x_{[g(u)=a]} G^y_{[h(v)=b]} \otimes I \approx _\nu G^y_{[h(v)=b]} G^x_{[g(u)=a]} \otimes I. \]

Proof ▶

Write $G_a^{u,x}=G^x_{[g(u)=a]}$. Expanding the commutator square gives

\begin{align} & \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert \bigl(G_a^{u,x} G_b^{v,y} - G_b^{v,y} G_a^{u,x}\bigr)^\dagger \bigl(G_a^{u,x} G_b^{v,y} - G_b^{v,y} G_a^{u,x}\bigr) \otimes I \lvert \psi \rangle \nonumber \\ & = 2 \mathbb {E}_{u,v,x,y} \sum _{a,b} \Bigl(\langle \psi \rvert G_b^{v,y} G_a^{u,x} G_b^{v,y} \otimes I \lvert \psi \rangle - \langle \psi \rvert G_a^{u,x} G_b^{v,y} G_a^{u,x} G_b^{v,y} \otimes I \lvert \psi \rangle \Bigr), \label{eq:gcom8} \end{align}

using the projectivity of $G$. To compare the two quartic terms, first note that

\begin{equation} \label{eq:sum-of-gux} G^{u,x} = \sum _a G_a^{u,x} = \sum _a G^x_{[g(u)=a]} = G^x. \end{equation}

The identity 3 is exactly Proposition 3.13 for the evaluation map $g \mapsto g(u)$. By 1 and 3.31,

\begin{align} G_a^{u,x} \otimes I & \approx _{4\zeta } G^{u,x} \otimes A_a^{u,x}\nonumber \\ & = G^x \otimes A_a^{u,x}, \label{eq:add-an-a} \end{align}

where the last equality is 3. Applying 3.23 once to the second term in 2 gives

\begin{align} & \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} G_a^{u,x} G_b^{v,y} \otimes I \lvert \psi \rangle \nonumber \\ \approx _{2\sqrt{\zeta }} & \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} G_a^{u,x} G^y \otimes A_b^{v,y} \lvert \psi \rangle . \label{eq:apply-add-an-a-once} \end{align}

The first boundedness-driven stability step is

\begin{equation} \eqref{eq:apply-add-an-a-once} \approx _{\sqrt{\zeta }} \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} G_a^{u,x} \otimes A_b^{v,y} \lvert \psi \rangle , \label{eq:gcom9} \end{equation}

which is 8.4. Applying 4 once more and then 8.2, we obtain

\begin{align} \eqref{eq:gcom9} & \approx _{2\sqrt{\zeta }} \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} G^x \otimes A_a^{u,x} A_b^{v,y} \lvert \psi \rangle \nonumber \\ & \approx _{6\sqrt{\gamma (m+1)}} \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} G^x \otimes A_b^{v,y} A_a^{u,x} \lvert \psi \rangle . \label{eq:commuting-answer-swapped} \end{align}

The second boundedness-driven stability step is

\begin{equation} \eqref{eq:commuting-answer-swapped} \approx _{\sqrt{\zeta }+6\sqrt{\gamma (m+1)}} \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} \otimes A_a^{u,x} A_b^{v,y} \lvert \psi \rangle , \label{eq:gcom10} \end{equation}

which is 8.5. Using 4 twice more and 3.23,

\begin{align} \eqref{eq:gcom10} & \approx _{2\sqrt{\zeta }} \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} \otimes A_b^{v,y} \lvert \psi \rangle \nonumber \\ & \approx _{2\sqrt{\zeta }} \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} G_b^{v,y} \otimes I \lvert \psi \rangle . \label{eq:gonna-cite-this-in-just-a-bit} \end{align}

Next, 2 and the projectivity of $G$ imply via 3.36 and 3.37 that

\begin{equation} \label{eq:new-fact-that-i-derived} G_a^{u,x} \otimes I \approx _\zeta I \otimes G_a^{u,x}. \end{equation}

Applying 10 twice with 3.23 turns 9 into

\[ \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_b^{v,y} G_a^{u,x} G_b^{v,y} \otimes I \lvert \psi \rangle , \]

which is the first quartic term from 2. Collecting the ten approximation steps appearing between 2 and 10 yields the bound

\[ 48m\bigl(\gamma ^{1/2}+\zeta ^{1/2}\bigr), \]

so the commutator norm is at most $\nu $.

Lemma 8.4

✓

This claim is made under the same standing hypotheses used in the commutativity-of-$G$ theorem above. The linked SliceBoundednessInput declarations are precisely the two displayed parts of item 3: the averaged $(I-G^y)\otimes Z^y$ residual bound and the domination $Z^y\ge \mathbb {E}_u A^{u,y}_{g(u)}$.

\begin{align} & \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} G_a^{u,x} G^y \otimes A_b^{v,y} \lvert \psi \rangle \label{eq:g-comm-stab1} \\ \approx _{\sqrt{\zeta }} & \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} G_a^{u,x} \otimes A_b^{v,y} \lvert \psi \rangle . \nonumber \end{align}

Proof ▶

For each $y \in \mathbb {F}_q$ and $g \in \mathcal{P}(m,q,d)$, define

\[ R_g^y = \mathbb {E}_{u,x} \sum _a G_a^{u,x} G_g^y G_a^{u,x}. \]

Since $G$ is a sub-measurement, $R^y=\{ R_g^y\} $ is also a sub-measurement. The difference between the two sides of the lemma is

\begin{align} & \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} G_a^{u,x} (I-G^y) \otimes A_b^{v,y} \lvert \psi \rangle \nonumber \\ & = \mathbb {E}_{v,y} \sum _g \langle \psi \rvert R_g^y (I-G^y) \otimes A_{g(v)}^{v,y} \lvert \psi \rangle . \label{eq:bound-this-right-now!} \end{align}

Apply Cauchy–Schwarz to 12. The first factor is at most $1$ because $R^y$ is a sub-measurement. For the second factor, average over $v$ and use 3 to replace $\mathbb {E}_v A_{g(v)}^{v,y}$ by $Z^y$; the resulting quantity is at most

\[ \mathbb {E}_y \langle \psi \rvert (I-G^y) \otimes Z^y \lvert \psi \rangle \le \zeta . \]

Hence the difference has magnitude at most $\sqrt{\zeta }$.

Lemma 8.5

✓

This claim is made under the same standing hypotheses used in the commutativity-of-$G$ theorem above, in particular the boundedness item 3. The linked SliceBoundednessInput declarations expose those boundedness hypotheses in Lean; they are not auxiliary assumptions added to the paper statement.

\begin{align*} & \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} G^x \otimes A_a^{u,x} A_b^{v,y} \lvert \psi \rangle \\ \approx _{\sqrt{\zeta }+6\sqrt{\gamma (m+1)}} & \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} \otimes A_a^{u,x} A_b^{v,y} \lvert \psi \rangle . \end{align*}

Proof ▶

The difference between the two sides is

\begin{align} & \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} (I-G^x) \otimes A_a^{u,x} A_b^{v,y} \lvert \psi \rangle \nonumber \\ \approx _{6\sqrt{\gamma (m+1)}} & \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G_a^{u,x} G_b^{v,y} (I-G^x) \otimes A_b^{v,y} A_a^{u,x} \lvert \psi \rangle , \label{eq:just-got-commuted} \end{align}

where 8.2 commutes the point measurements on the right register. Expanding $G_a^{u,x}=\sum _{g:g(u)=a} G_g^x$, we rewrite

\begin{align} \eqref{eq:just-got-commuted} & = \mathbb {E}_{u,v,x,y} \sum _{g,b} \langle \psi \rvert G_g^x G_b^{v,y} (I-G^x) \otimes A_b^{v,y} A_{g(u)}^{u,x} \lvert \psi \rangle . \label{eq:g-comm-stab7} \end{align}

Apply Cauchy–Schwarz to 14. The first factor is at most $1$ because both $G$ and $A$ are sub-measurements. In the second factor, average over $u$ and use 3 to replace $\mathbb {E}_u A_{g(u)}^{u,x}$ by $Z^x$; then sum over $g$ and $b$ using the sub-measurement property. This leaves

\[ \mathbb {E}_x \langle \psi \rvert (I-G^x) \otimes Z^x \lvert \psi \rangle \le \zeta . \]

Hence 14 has magnitude at most $\sqrt{\zeta }$, and the total loss is $\sqrt{\zeta }+6\sqrt{\gamma (m+1)}$.

8.3 Commutativity of $G$

Lemma 8.6 Normalization condition for a sandwiched family

✓

Let $P=\{ P_a\} $ be a sub-measurement and $Q=\{ Q_b\} $ be a projective sub-measurement. Define $C_{a,b}=Q_b P_a Q_b$. Then

\[ \sum _a \left(\sum _b C_{a,b}\right)^\dagger \left(\sum _b C_{a,b}\right) = \sum _a \left(\sum _b C_{a,b}\right)\left(\sum _b C_{a,b}\right)^\dagger \le I. \]

Proof ▶

Expand the square, use the orthogonality $Q_b Q_{b'}=0$ for $b \neq b'$, and then sum over the sub-measurement $P$.

Theorem 8.7 Commutativity of $G$

✓

Let $(\psi ,A,B,L)$ be an $(\varepsilon ,\delta ,\gamma )$-good symmetric strategy for the $(m+1,q,d)$ low individual degree test. Let $\{ G^x\} _{x \in \mathbb {F}_q}$ denote a set of projective sub-measurements in $\mathrm{PolySub}(m,q,d)$ with the following properties:

(Consistency with $A$) On average over $(u,x) \sim \mathbb {F}_q^{m+1}$,

\[ A_a^{u,x} \otimes I \simeq _\zeta I \otimes G^x_{[g(u)=a]}. \]
(Strong self-consistency) On average over $x \sim \mathbb {F}_q$,

\[ G_g^x \otimes I \approx _\zeta I \otimes G_g^x. \]
(Boundedness) There exists a positive-semidefinite matrix $Z^x$ for each $x \in \mathbb {F}_q$ such that

\[ \mathbb {E}_x \langle \psi \rvert (I-G^x) \otimes Z^x \lvert \psi \rangle \le \zeta \]

and for each $x \in \mathbb {F}_q$ and $g \in \mathcal{P}(m,q,d)$,

\[ Z^x \ge \left(\mathbb {E}_u A_{g(u)}^{u,x}\right). \]

Let

\[ \nu = 30m\left(\gamma ^{1/4}+\zeta ^{1/4}+(d/q)^{1/4}\right). \]

Then on average over independent and uniformly random $(u,x),(v,y) \sim \mathbb {F}_q^{m+1}$,

\[ G_g^x G_h^y \otimes I \approx _\nu G_h^y G_g^x \otimes I. \]

Proof ▶

If at least one of $\gamma $, $\zeta $, or $d/q$ is at least $1$, then $\nu \ge 30$ and the estimate is trivial from 3.26. We therefore assume $\gamma ,\zeta ,d/q \le 1$.

Expanding the commutator square gives

\begin{align} & \mathbb {E}_{x,y} \sum _{g,h} \langle \psi \rvert \bigl(G_g^x G_h^y - G_h^y G_g^x\bigr)^\dagger \bigl(G_g^x G_h^y - G_h^y G_g^x\bigr) \otimes I \lvert \psi \rangle \nonumber \\ & = 2 \mathbb {E}_{x,y} \sum _{g,h} \langle \psi \rvert G_g^x G_h^y G_g^x \otimes I \lvert \psi \rangle - 2 \mathbb {E}_{x,y} \sum _{g,h} \langle \psi \rvert G_g^x G_h^y G_g^x G_h^y \otimes I \lvert \psi \rangle . \label{eq:gcomterms} \end{align}

The first term is close to $\langle \psi \rvert G \otimes G \lvert \psi \rangle $, where $G=\mathbb {E}_x G^x$, by 3.32 and 2. For the second term, 3.23 and 8.6 yield

\begin{equation} \mathbb {E}_{x,y} \sum _{g,h} \langle \psi \rvert G_g^x G_h^y G_g^x G_h^y \otimes I \lvert \psi \rangle \approx _{\sqrt{\zeta }} \mathbb {E}_{x,y} \sum _{g,h} \langle \psi \rvert G_h^y G_g^x G_h^y \otimes G_g^x \lvert \psi \rangle . \label{eq:gcom4} \end{equation}

The first Schwartz–Zippel reduction evaluates the left factor at a random point:

\begin{align} \eqref{eq:gcom4} & = \mathbb {E}_{x,y} \sum _{g,h} \langle \psi \rvert G_h^y G_g^x G_h^y \otimes G_g^x \lvert \psi \rangle \nonumber \\ & \approx _{\frac{dm}{q}} \mathbb {E}_{u,x,y} \sum _{a,h} \langle \psi \rvert G_h^y G^x_{[g(u)=a]} G_h^y \otimes G^x_{[g(u)=a]} \lvert \psi \rangle . \label{eq:evaluate-gcom-at-points} \end{align}

Indeed, the difference is

\begin{equation} \label{eq:gcom4-diff} \mathbb {E}_{u,x,y} \sum _{g \neq g',h} \mathbf{1}\! \left[[\right]g(u)=g'(u)] \langle \psi \rvert G_h^y G_g^x G_h^y \otimes G_{g'}^x \lvert \psi \rangle , \end{equation}

and 3.7 bounds this by $dm/q$.

Next, apply 3.23 twice:

\begin{align} \eqref{eq:evaluate-gcom-at-points} & = \mathbb {E}_{u,x,y} \sum _{a,h} \langle \psi \rvert G_h^y G^x_{[g(u)=a]} G_h^y \otimes G^x_{[g(u)=a]} \lvert \psi \rangle \nonumber \\ & \approx _{\sqrt{\zeta }} \mathbb {E}_{u,x,y} \sum _{a,h} \langle \psi \rvert G^x_{[g(u)=a]} G_h^y G^x_{[g(u)=a]} G_h^y \otimes I \lvert \psi \rangle \nonumber \\ & \approx _{\sqrt{\zeta }} \mathbb {E}_{u,x,y} \sum _{a,h} \langle \psi \rvert G^x_{[g(u)=a]} G_h^y G^x_{[g(u)=a]} \otimes G_h^y \lvert \psi \rangle . \label{eq:don't-understand-the-numbering-system} \end{align}

A second Schwartz–Zippel reduction evaluates the right factor at an independent point:

\begin{align} \eqref{eq:don't-understand-the-numbering-system} & = \mathbb {E}_{u,x,y} \sum _{a,h} \langle \psi \rvert G^x_{[g(u)=a]} G_h^y G^x_{[g(u)=a]} \otimes G_h^y \lvert \psi \rangle \nonumber \\ & \approx _{\frac{dm}{q}} \mathbb {E}_{u,v,x,y} \sum _{a,b} \langle \psi \rvert G^x_{[g(u)=a]} G^y_{[h(v)=b]} G^x_{[g(u)=a]} \otimes G^y_{[h(v)=b]} \lvert \psi \rangle . \label{eq:evaluate-gcom-at-points-part-dos} \end{align}

The difference is

\begin{equation} \label{eq:numbering-system-diff} \mathbb {E}_{u,v,x,y} \sum _{a,h \neq h'} \mathbf{1}\! \left[[\right]h(v)=h'(v)] \langle \psi \rvert G^x_{[g(u)=a]} G_h^y G^x_{[g(u)=a]} \otimes G_{h'}^y \lvert \psi \rangle , \end{equation}

and the same Schwartz–Zippel estimate again gives the loss $dm/q$.

Now set

\[ \nu _{\mathrm{evaluation}} = 48m\bigl(\gamma ^{1/2}+\zeta ^{1/2}\bigr), \]

the error from 8.3. Apply 8.3 to commute the evaluated families in 20; after one more use of 3.23 with 2, the resulting quantity is $\langle \psi \rvert G \otimes G \lvert \psi \rangle $. Thus the second term in 15 is also close to $\langle \psi \rvert G \otimes G \lvert \psi \rangle $.

Combining the first-term estimate, 16, the two Schwartz–Zippel losses, the two intermediate $\sqrt{\zeta }$ losses, and the evaluated commutation error $\nu _{\mathrm{evaluation}}^{1/2}$ gives

\[ 30m\left(\gamma ^{1/4}+\zeta ^{1/4}+(d/q)^{1/4}\right), \]

where the constant $30m$ accounts for the $10m$ Schwartz–Zippel evaluation losses plus $20m$ from the $\approx $-chain in the first and second terms. This proves 8.7.

Blueprint for arXiv:2009.12982
Quantum Soundness of the Classical Low Individual Degree Test

8 Commutativity

8.1 Commutativity of the point measurements

8.2 Commutativity of \(G\) after evaluation

8.3 Commutativity of \(G\)