本文探讨了元胞自动机的量子力学扩展，即量子元胞自动机。作者将经典元胞自动机中的布尔值细胞扩展到量子态，并使用幺正算符描述其时间演化。文章的核心问题在于，是否存在本质上不同于可逆经典元胞自动机的量子元胞自动机。作者目前理解，任何量子元胞自动机都可以通过选择八个复数二维向量来描述，这些向量表示给定邻域下细胞下一个状态的概率幅。为了满足幺正性，这些向量的内积需要满足特定的条件。作者试图通过枚举所有可能的输入和输出状态，并使用Z3求解器寻找满足这些条件的向量，但尚未得出明确结论。文章的核心问题在于，量子元胞自动机是否能够展现出超越经典元胞自动机的有趣行为。

🤔 **量子元胞自动机的定义:** 将经典元胞自动机扩展到量子领域，每个细胞的状态由量子态描述，时间演化由幺正算符U决定，其矩阵元素由函数f决定，该函数将细胞的当前状态及其邻域映射到复数。

🔍 **幺正性条件:** 为了保证量子元胞自动机的演化是物理合理的，幺正算符U需要满足⟨Ux|Uy⟩=⟨x|y⟩，即内积保持不变。这导致了对函数f的约束，使得其对应的向量内积满足特定的条件。

🤔 **经典元胞自动机与量子元胞自动机关系:** 作者推测，所有的量子元胞自动机都可能等价于可逆的经典元胞自动机，但尚未得到确切证明。通过分析函数f及其对应的向量，作者试图找出量子元胞自动机是否能展现出超越经典元胞自动机的独特行为。

🤔 **Z3求解器尝试:** 作者使用Z3求解器枚举所有可能的输入和输出状态，并尝试找到满足幺正性条件的向量，但目前尚未得出结论，也可能存在Z3使用上的问题。

💰 **悬赏问题:** 作者悬赏100美元，希望有人能帮助他更深入地理解为什么所有量子元胞自动机都可能等价于经典元胞自动机，或者证明他的推测是错误的，即量子元胞自动机存在有趣的非经典行为。

Published on November 26, 2024 12:11 AM GMT

You know elementary cellular automata, where each of the boolean-valued cells evolves according to 

$$x_{t+1}^{\left(k\right)}=f(x_t^{(k-1)},x_t^{\left(k\right)},x_t^{(k+1)})$$

where $f:\{0,1{\}}^3\to \{0,1\}$.

I think the natural quantum-mechanical extension of this is:

there are $2^{\text{(N := tape size)}}$ basis states: $|00\cdots 00⟩$ through $|11\cdots 11⟩$its time-evolution is given, of course, by a unitary operator $U$, which, expressed in that basis, is:

$$⟨y|U|x⟩=\prod _{k}f(x^{(k-1)},x^{\left(k\right)},x^{(k+1)},y^{\left(k\right)})$$

...where $f:\{0,1{\}}^4\to C$.

You can take any elementary cellular automaton and quantum-ize it: just choose $f_{quantum}(a,b,c,z)=\left(\text{if}{f}_{classical}(a,b,c)=z\text{then 1 else 0}\right)$; then that product is 1 exactly when $y$ is the classical evolution of $x$. (Not every $f_{classical}$ gives rise to a unitary $U$, though; only the reversible ones.)

But... are there other unitary operators of this form, which aren't basically equivalent to reversible classical CAs? I think not, disappointingly, but I'm not sure, and I don't understand why not.

Bounty: $100 if you make me feel like I have a significantly deeper understanding of why all quantum elementary CAs are basically equivalent to classical elementary CAs (or show me I'm wrong and there actually is interesting behavior here). Partial payouts for partial successes.

---

My current understanding (the thing you have to enhance or beat) is:

Any choice of $f$ is equivalent to a choice of eight complex two-vectors ${\overrightarrow{\lambda }}_{000},\cdots ,{\overrightarrow{\lambda }}_{111}$, each describing roughly "how (0/1)ish the next state of a cell should be given its current neighborhood."For unitarity, we want $⟨Ux|Uy⟩=⟨x|y⟩$ for all $x,y$. If you bang through some math, I think this inner product turns out to equal the product of all 64 possible inner products of the ${\overrightarrow{\lambda }}_{abc}$ s, raised to various powers: 

$$⟨Ux|Uy⟩=({\overrightarrow{\lambda }}_{000}\cdot {\overrightarrow{\lambda }}_{111}{)}^{N_{000,111}}\cdots ({\overrightarrow{\lambda }}_{000}\cdot {\overrightarrow{\lambda }}_{111}{)}^{N_{000,111}}$$

...where $N_{000,111}$ is the number of locations where the neighborhood on tape $x$ is 000 and the neighborhood on tape $y$ is 111. For $x=y$, we want this product to be 1; for $x\ne y$, we want this product to be 0, meaning at least one of the inner products with a nonzero $N$ must be zero.

(Sanity check: if $x=y$, then $N_{abc,abc}=1$ and all the other $N$s are 0. The inner products raised to power 0 disappear; the remaining ones are ${\overrightarrow{\lambda }}_{abc}\cdot {\overrightarrow{\lambda }}_{abc}$, which is 1 as long as the $\overrightarrow{\lambda }$s are normalized, so we get $⟨Ux|Ux⟩=1$ practically for free. Great.)

(Note that not all the $N$s can be chosen independently: for example, if $N_{001,000}>0$, then evidently tape $x$ has some stretch of 0s ending in a 1; I'm imagining that the tape wraps around, so there must be a 1 on the left side of the stretch of 0s too; so some $N_{100,abc}$ must be positive too.)
It feels like there must be some clever geometrical insight, here, but I can't find it. Instead, I just enumerated all possible $x,y$ for a small (4-cell) automaton, computed which $N$s were nonzero, and asked Z3 to find $\overrightarrow{\lambda }$s satisfying the huge pile of constraints (the AND of a bunch of ORs of clauses like "A dot B is zero") and "some $\overrightarrow{\lambda }$ is not parallel to ${\overrightarrow{\lambda }}_{000}$ or ${\overrightarrow{\lambda }}_{111}$". (I think that if there are just two mutually-perpendicular families of $\overrightarrow{\lambda }$, that's basically equivalent to a classical CA.)It... well, it didn't print "unsat," but it did hang, whereas, if I left out the interestingness constraint, it promptly spit out a satisfactory output. Shrug. This is my first time with Z3, so it might be a newbie mistake.

Discuss