Bounds on the speedup in quantum signaling

Given a classical, reversible dynamics over a line of discrete systems, we can define a quantum evolution, which acts on basis states like the classical one but is linearly extended to allow for quantum superpositions. It is a curious fact that in the quantum regime, the speed of propagation of information can sometimes be much greater than in the classical regime. Here we provide optimal bounds on this quantum speedup. In particular we show that over a run of many steps, the quantum propagation neighborhood can only increase by a constant fringe, so that there is no asymptotic increase in speed.

Figure 1

$(x,y)\in \mathcal{N}\left(f\right)$ means that, in at least one case, knowing $c_x$ is essential to determining $f{\left(c\right)}_y$. In other words, it means that there exists an antecedent configuration $c$ such that changing the cell $x$ will change the cell $y$ of the image configuration $f\left(c\right)$.

Figure 2

$\mathcal{BN}\left(f\right)\left(y\right)$ is the smallest $Z\subseteq X$ such that $f$ can be decomposed in such a way, with $g$ and $h$ bijective. Note that $X$ and $Z$ denote neither antecedents nor images of $f$; they are sets of cells. For instance, the left-hand side reads “the image of a configuration on $X$ by $f$ is a configuration on $X$” and not “$f\left(X\right)=X$”.

Figure 3

Let $A$ act on $y$. Intuitively $Q_f\left(A\right)$ is ${U_f}^{†}A{U}_f$, but this is not always local. However if $\mathcal{BN}\left(f\right)\left(y\right)$ is finite, $U_f$ decomposes into $U_g$ and $U_h$, and ${U_f}^{†}A{U}_f$ yields the left picture. The $U_h$ cancel out (middle), and the remainder ${U_g}^{†}A{U}_g$ makes for a good, local definition of $Q_f\left(A\right)$.

Figure 4

Illustration of the combined upper bounds (1) and (5). In order to be able to send a signal from $x$ to $y$ in the quantum regime, it is necessary that there exist $x^{\prime }$, $x^{″}$, $y^{\prime }$, and $y^{″}$, forming such a pattern (points on each side need not be distinct).

Figure 5

The Toffoli CA. Each cell is made of two bits. The leftmost bit at the next time step is just the rightmost bit of the left neighbor at the previous time step ($b$). The rightmost bit at the next time step is the leftmost bit at the previous time step ($c$), inverted if both $b$ and the rightmost bit ($d$) were set to one, i.e., $c\oplus b·d$.

Figure 6

For the Toffoli CA, the quantum neighborhood $\mathcal{N}\left(Q_f\right)$ contains $-2$. Indeed, focus on the middle Toffoli gate, and forget about its left wire for a second. We are left with a cnot gate, apparently controlled by its right wire. But it is a well-known (albeit curious) fact that switching to the $|\pm \rangle$ basis flips who controls whom. So, this cnot gate, if activated, will effectively toggle the right wire. Now, recalling that this cnot gate is in fact part of a Toffoli gate and thus activated by the left wire, we see that changing the left toggles the right.

Figure 7

The quantum neighborhood of the iterated Toffoli CA does not grow very fast. The bottom-left cell can spread its influence only through the black gates (left). In the first step, because it touches the left wire of a Toffoli gate, it can signal at speed two. But it only reaches the leftmost bit of the third cell, so that in the second step, because the top-right Toffoli gates commute (right), there is no way it can signal at speed two again.

Figure 8

Illustration of Corollary t3 when $n=3$.

Figure 9

Typical asymptotics for iterated dynamics.