The power of constant-depth quantum circuits of unbounded size

技术摘要：无限制规模常数深度量子电路的力量

问题陈述
本文研究了在移除对电路规模和辅助空间限制时，量子电路的计算能力。在经典复杂度理论中，$AC^0$ 类（具有无限制扇入 AND/OR 门的常数深度电路）无法计算奇偶校验（parity）。然而，如果取消多项式规模的限制，通过析取范式（DNF）构造，每个布尔函数都可以在常数深度内被计算。作者提出了这样一个疑问：对于由任意单比特门和广义 Toffoli 门构建的量子电路（即 $QAC^0$），是否也能实现类似的现象？具体而言，如果电路规模和辅助量子比特的数量不受限制，是否可以精确实现任何幺正变换（unitary operation）？

作者通过四个日益通用的任务来界定这一探究：

1. 计算任何集合 $L \subseteq \{0, 1\}^n$ 的成员资格。
2. 实现任何计算基态的置换（permutation）。
3. 制备任何纯量子态。
4. 在每个输入态上实现任何任意幺正变换。

方法论
作者结合了可逆经典电路构造、适配于量子领域的概率性经典技术以及量子隐形传态协议。

• 可逆经典构造： 作者首先确定了任意比特串的置换可以通过 Toffoli 门和扇出（fanout）门在常数深度内实现。这是通过一种“指示器编码”（indicator encoding）方案实现的：将输入映射到一个 $2^n$ 维的指示向量（其中恰好有一个条目为 1），对其进行操作，然后解码回原始字符串。这允许并行评估所有可能的输入字符串。
• 从概率到量子的适配： 为了制备任意概率分布和纯量子态，作者适配了一种经典的概率性构造。该方法涉及通过独立采样比特来编码一个基于第一个“1”位置的分布。在量子设定下，通过对第一个“1”之后的量子比特应用逆旋转，使其回到 $|0\rangle$ 状态而不破坏叠加态，从而使该过程变为相干的。
• 门集扩展： 虽然主要的门集包括单比特门和广义 Toffoli 门，但作者将扇出门作为一个概念性工具进行利用。他们引用了 Grier, Morris, 和 Wu [GMW26] 以及 Rosenthal [Ros20] 的结果，证明扇出可以仅使用主要门集精确地在常数深度内实现，尽管这可能会导致电路规模增加到双指数界限。
• 幺正变换的归约： 对于实现任意幺正变换，作者并未提供直接的构造。相反，他们提供了几种等价的形式化表达和归约方式。这些包括将幺正变换的实现归约为：
  • 克隆指定正交规范基的向量。
  • 置换基向量列表。
  • 解码基标签。
  • 实现具有单位行和列和的幺正矩阵（通过 Idel-Wolf 标准型）。
  • 实现无迹幺正对合（使用一个额外的干净量子比特）。
• 基于端口的隐形传态 (PBT)： 为了在不依赖于特定门的条件下实现任意幺正变换，作者利用了基于端口的隐形传传态（PBT）。他们构造了一个利用最大纠缠态（或目标幺正矩阵的 Choi 态）和联合测量，随后进行端口选择的幺正电路来执行 PBT。

核心贡献与结果

1. 针对特定任务的精确常数深度构造：

   • 置换： 任意计算基态的置换可以使用 $O(n2^n)$ 个门和辅助量子比特在常数深度（深度 $\le 20$）内实现。
   • 对角幺正变换： 任意对角幺正变换可以通过计算指示器、并行应用相位并进行逆计算，在常数深度（深度 7）内实现。
   • 态制备： 任意纯量子态可以使用 $O(4^n)$ 个量子比特和 $O(n2^n)$ 个门在常数深度（深度 $\le 37$）内制备。所有辅助量子比特均返回到零状态。
   • 扇出实现： 扇出可以仅使用单比特门和广义 Toffoli 门在常数深度内精确实现，尽管这可能需要双指数级的规模。

2. 任意幺正变换的归约：
   论文证明了在常数深度内实现任意幺正变换，等价于实现若干特定操作（例如，克隆基向量、解码标签或实现无迹对合）。这为实现任意幺正变换这一开放问题重新定义为一系列等价的结构性挑战。

3. 自适应测量与门隐形传态：
   作者展示了如果允许自适应中间测量，Clifford 层级中第 $\ell$ 层的任何门都可以在深度 $O(\ell)$ 内实现。此外，在自适应模型下，任意幺正变换的实现归约为实现无迹幺正对合。

4. 基于端口的隐形传态近似：
   作者构造了一个用于输入维度为 $d$ 且端口数 $M \ge d^2 - 1$ 的基于端口的隐形传态（PBT）幺正电路。

   • 深度： 该电路深度为 $O(\sqrt{d})$，且与端口数 $M$ 无关。
   • 保真度： 纠缠保真度受限于 $F_e \ge (1 - \frac{d^2-1}{2M})^2$。
   • 精度与深度的关系： 对于任何固定的输入维度 $d$，可以通过增加 $M$ 来使近似变得任意精确，而不会增加电路深度。然而，其对输入维度 $d$ 的依赖性仍然存在；是否可以实现与 $d$ 无关的深度界限仍是一个开放问题。
   • 实现： 该电路仅使用单比特门和广义 Toffoli 门，且不需要中间测量。

意义与主张

本文确立了通过移除规模和辅助空间限制，常数深度量子电路可以执行那些在多项式规模常数深度模型中通常无法完成的任务，例如任意态制备和基态置换。这建立了量子态制备与可逆经典计算及概率分布制备之间的直接联系。

然而，对于实现任意幺正变换，本文保持了审慎的态度。虽然作者为置换、对角幺正变换和态制备提供了精确的常数深度构造，但实现一般的幺正变换仍然是一个开放问题。作者提供了该问题的几种等价特征，但并未解决它。

关于一般幺正变换的主要贡献在于 PBT 构造。作者证明了对于任何固定的输入维度，可以通过增加端口数来以任意精度近似实现任意幺正变换，而不会增加电路深度。然而，该构造的深度随输入维度 $d$ 呈 $O(\sqrt{d})$ 缩放。作者明确指出，是否可以消除这种对 $d$ 的依赖（即实现一个独立于 $d$ 的深度界限）仍然是一个开放问题。该工作强调，在常数深度实现一般幺正变换的根本困难不在于从一个固定的输入产生任意输出，而在于如何在保持幺正性的同时，对每一个输入态同时规定其作用。