这篇说的是一个技术上不太传统的关于线路复杂性 (circuit complexity) 的结果 [1], 给出了一个问题使得, 量子计算机只需要常数深度量子线路 (constant-depth quantum circuit), 而经典计算机至少需要对数深度 (logarithmic-depth) 经典线路. 前者的构造非常简单, 并且有很漂亮的解释 (制备 graph state 并按某种方式测量); 后者是与前者问题中的图相关的下界. 这里的量子优越性的来源是量子非局域性 (non-locality), 换而言之, 对于任何常数深度量子线路, 求解这一问题意味着对应的 GHZ game 的量子策略最大获胜概率为 1 (而经典策略的最大获胜概率则小于 1).

第一稿写于 2018 年 4 月, 2018 年末这个工作 [1:1] 因为被 Science 接收还曾经引起了不小的关注度. 主要参考三位作者在不同场合的 Slides, 以及 David Gosset 2018 年在 UCSD Spring School 的 Slides [2]. 第二稿写于 2019 年 4 月, 当时有一系列后续工作扩展到了平均情形 (average-case) 和无限扇入 (unbounded fan-in) 的常数深度量子线路的计算优越性 [3][4][5]. 第三稿写于 2020 年 2 月, 增加了对[5:1] 的构造的简单介绍, 新的后续工作 [6] 扩展到了对数深度量子线路 (在线路复杂性假设下) 的计算优越性.

下面开始正文.

纠错编码之前的量子计算优越性

环境噪声与线路深度

众所周知, 环境噪声是量子计算的物理实现难以避免的问题之一. 那么如果不考虑任何形式的纠错编码的话, 满足关系 nd<1/ϵnd<1/\epsilon , 其中 nn 是量子线路的宽度 (量子比特的个数), dd 是量子线路的深度, ϵ\epsilon 是错误发生的几率.
在这里显然我们并不打算考虑任何形式的 trade-off, 那自然是线路的深度和宽度中选一个:

  • 更深的量子线路意味着更少的量子比特, 而这意味着(有效地)经典模拟的可行性; 有效意味着在(关于输入规模的)多项式时间内.
  • 足够浅的量子线路意味着足够多的量子比特, 我们知道它们可以发生纠缠, 从这个角度看, 似乎量子线路很可能有优越性.

量子计算优越性

自然, 为了显示量子计算的优越之处, 考虑后者自是合适的多. 事实上, 量子线路的计算能力也和线路深度密切相关:

  • 在线路深度足够浅 ( d≤2d\leq2 ) 时可以有效地用经典计算机模拟 [7];
  • 常数深度 (constant-depth) 则有可能的优越之处 (然而需要的量子比特的数量级在 10310^3 ), 如近似优化 (QAOA) 和"quantum (computational) supremacy" (诸如 IQP);
  • 如果深度是关于对数的多项式的话, 可以实现 Shor 算法用到的量子 Fourier 变换;
  • 增加到多项式深度 (假定线路本身可以在多项式时间内产生), 那么任何 BQP\mathsf{BQP} 里的问题的算法都适用.

如果读者熟悉矩阵乘积态 (matrix product state) 的话, 那么一个众所周知的结果是, 对数深度的量子线路可以用矩阵乘积态表示, 自然它是可以有效地经典模拟的. 需要说明的是, 矩阵乘积态的有效地经典模拟意味着 bond dimension 为多项式 poly(n)poly(n) , 此时由于收缩过程中张量的开指标个数仅有常数 cc (比如 ≤4\leq 4 )个, 那么对于有限长度 nn 的矩阵乘积态, 计算代价为 O(npoly(n)c)=O(poly(n))O(n poly(n)^c)=O(poly(n)) . 这里没有任何关于经典线路的线路深度的 lower bound. 但是直觉上, 相较之下量子线路的对数深度和经典线路的多项式深度, 似乎意味着量子计算的可能优势.

那么, 让我们回顾一些如何展示量子优越性:

  1. 第一类自然是诸如 Shor 算法等, 其量子算法的时间复杂度相对经典算法具有多项式/超多项式/指数加速. 但是问题在于, 我们并不能证明更好的经典算法并不存在.
  2. 第二类是采样问题, 说的是从对于经典计算机在难以高效地生成的分布 (distribution) 中采样, 比如 Boson Sampling. 这一类问题往往借助于某些猜想, 比如 PH\mathsf{PH} 不会 collapse.
  3. 第三类是和黑盒 (oracle) 相关的加速, 比如和查询复杂性 (query complexity) 相关的一些结果. 这一类的问题在于, 黑盒本身往往在真实世界中并不存在.

但是本文谈论的关于常数深度量子线路的优越性, 则不需要任何假设. 那么, 我们能用它做什么呢?

常数深度量子线路

考虑一个常数深度量子线路可以解决的问题, 如果我们要显示量子计算的优越之处的话, 选择有二:

  • 要么这个问题无法用多项式深度的经典线路解决. 这看起非常野心勃勃, 但是非常困难, 因为会导出 P⊂BQP⊆PSPACE\mathsf{P}\subset\mathsf{BQP}\subseteq\mathsf{PSPACE} .
  • 要么这个问题无法用对数深度的经典线路解决, 这正是我们要讨论的问题.

剩下唯一要做的就是找到一个合适的问题. 那么我们需要知道我们可以从常数深度 (constant-depth) 量子线路中得到什么.

第一个问题是如果我们从真空态 ∣0⟩⊗n|0\rangle^{\otimes n} 或者别的乘积态出发, 应用常数深度量子线路之后能够得到哪些量子态. 根据 Matt Hastings 的定义, 我们能够得到的态叫做 Trivial state, 因为这里没有长程纠缠 (long-range entanglement), 只有短程纠缠 (short-range entanglement). 这样定义的原因是, quantum phases 的等价性使用 local unitary operation 定义. 而产生长程纠缠需要至少对数深度量子线路, 比如 GHZ 态 (或猫态) 12(∣0⟩⊗n+∣1⟩⊗n)\frac{1}{\sqrt{2}}(|0\rangle^{\otimes n}+|1\rangle^{\otimes n}) .

第二个问题是如果我们试图在经典计算机上模拟这样的常数深度量子线路, 我们能够做得多好. 如果线路深度 d≤2d \leq 2 的话, 我们可以做到高效地经典模拟. 对于更一般的情况, 我们可以做的在超多项式 (super-poly) 时间内模拟.

隐含线性函数问题

这一节主要介绍用以体现常数深度线路上的量子优越性的隐含线性函数问题 (Hidden Linear Function Problem), 问题的名字看起来有点诡异, 但是如果我们理解来龙去脉的话看起来会好得多.

回顾: Bernstein-Vazirani 算法

Bernstein 和 Vazirani 在 1993 年提出了下述问题的量子算法:

给定黑盒 (oracle) 的量子线路实现 UU , 使得 U∣x⟩=(−1)z⋅x∣x⟩U|x\rangle = (-1)^{z\cdot x}|x\rangle , 即使用未知比特串 zz 的线性布尔函数 (linear Boolean function). 用最少的黑盒查询次数找到 z∈{0,1}nz\in \{0,1\}^n .

量子算法仅需要一次查询, 而经典算法则需要 nn 次查询. 经典算法的话, 考虑 nn 个线性无关的字符串 x∈{0,1}nx\in\{0,1\}^n , 根据结果求解关于 z1⋯znz_1\cdots z_n 的线性方程即可.

量子算法需要一些观察. 注意到一个关于 Hadamard 门的事实, 即 H⊗n∣0⟩⊗n=12n/2∑x∈{0,1}n∣x⟩=12n/2∑x∈{0,1}n(−1)0⋅x.∣x⟩H^{\otimes n}|0\rangle^{\otimes n} = \frac{1}{2^{n/2}}\sum_{x \in \{0,1\}^n} |x\rangle = \frac{1}{2^{n/2}}\sum_{x \in \{0,1\}^n} (-1)^{0\cdot x}. |x\rangle

类似地, 不难验证下述结论 (即这是离散 Fourier 变换),
H⊗n∣z⟩=12n/2(−1)z⋅x∣x⟩.H^{\otimes n} |z\rangle = \frac{1}{2^{n/2}} (-1)^{z\cdot x} |x\rangle. 从而我们可以利用上述变换的可逆性质, 进而得到 ∣z⟩=H⊗nUH⊗n∣0⟩⊗n|z\rangle = H^{\otimes n} UH^{\otimes n}|0\rangle^{\otimes n} . 毫无疑问这里体现了量子计算的优越之处, 但是这里使用了黑盒 (oracle), 并且把一个未知的线性函数藏在了黑盒里 – 所以我们需要的是设计一个同样需要找到未知线性函数的问题, 并且不需要任何假设.

二次型和隐含线性函数

让我们考虑有限域 F2n\mathbb{F}_2^n 上的对称矩阵 AA . 这是一个线性变换, 所以我们可以考虑它的 kerA={x:Ax=0 (mod 2)}ker{A} = \{x:Ax = 0\text{ (mod }2)\} , 并且可以在稍大的有限域 Z4\mathbb{Z}_4 上定义一个二次型 q(x)=xTAx (mod 4)q(x)=x^T Ax\text{ (mod 4)} .

如果我们限制 x∈kerAx\in ker{A} 的话, 那么二次型 q:F2n→Z4q: \mathbb{F}_2^n \rightarrow \mathbb{Z}_4 是一个线性布尔函数, 并且 q(x)=2zTxq(x) = 2z^Tx . 证明如下,

  • 定义集合 Lq={x∈F2n:q(x⊕y)=q(x)⊕q(y) ∀y∈F2n}\mathcal{L}_q = \{x\in\mathbb{F_2^n}: q(x\oplus y)=q(x)\oplus q(y) ~\forall y\in\mathbb{F_2^n}\} , 那么不难验证 Lq\mathcal{L}_q 是 F2n\mathbb{F}_2^n 的线性子空间.
  • 并且 ∀x∈Lq,q(x)∈{0,2}\forall x\in\mathcal{L}_q, q(x) \in\{0,2\} , 因为 0=q(0)=q(x⊕x)=2q(x) ∀x∈Lq0=q(0)=q(x\oplus x)=2q(x)~\forall x\in\mathcal{L}_q , 从而得到 q(x)∈{0,2}q(x) \in \{0,2\} .
  • 最后考虑 l(x)∈{0,1}l(x)\in\{0,1\} , 满足 l(x⊕y)=l(x)⊕l(y) ∀x,y∈Lql(x\oplus y)=l(x)\oplus l(y)~\forall x,y\in\mathcal{L}_q 和 q(x)=2⇔l(x)=1q(x)=2 \Leftrightarrow l(x)=1 , 那么 l(x)=zTx (mod 2)l(x) = z^Tx~(\text{mod }2) , 即 q(x)=2zTx (mod 4)q(x)=2z^Tx~(\text{mod }4) .

于是我们最终定义隐含线性函数问题 (Hidden Linear Function Problem, HLFP):

给定二次型 q:F2n→Z4q: \mathbb{F_2^n}\rightarrow \mathbb{Z}_4 的矩阵表示 A∈Mn(Z2n)A\in M_n(\mathbb{Z}_2^n) . 找到 z∈Z2nz\in\mathbb{Z}_2^n , 满足 q(x)=2zTx (mod4)q(x)=2z^T x~(\mathrm{mod} 4) , 其中 ∀x∈ker(A)\forall x \in ker(A) .

注意到在隐含线性函数问题中, AA 可以看做有图的邻接矩阵. 便宜起见, 我们把图 G=(V,E)G=(V,E) 限制在 n×n\sqrt{n}\times\sqrt{n} 正方形网格上. 即对角元 AvvA_{vv} 表示二维正方形网格中对应格点 (v,v)(v,v) 是否存在; 而非对角元 AvwA_{vw} 则表示二维正方形网格中, 格点 vv 和 ww 之间的边是否存在. 于是我们得到下述二维隐含线性函数问题 (2D HLFP):

给定 n×n\sqrt{n}\times\sqrt{n} 格点上的图 G=(V,E)G=(V,E) . 考虑二次型 q:F2n→Z4q: \mathbb{F_2^n}\rightarrow \mathbb{Z}_4 的矩阵表示 A∈Mn(Z2n)A\in M_n(\mathbb{Z}_2^n) . 找到 z∈Z2nz\in\mathbb{Z}_2^n , 满足 q(x)=2zTx (mod4)q(x)=2z^T x~(\mathrm{mod} 4) , 其中 ∀x∈ker(A)\forall x \in ker(A) .

2D HLFP 的量子算法

考虑 AA 对应的 nn-qubit 量子态 ∣A⟩|A\rangle , 以及作为 ancilla 的 ∣0⟩⊗n|0\rangle^{\otimes n} . 类似上一节提到的 Bernstein-Vazirani 算法, 我们可以得到下述量子算法:

  1. 产生所有 nn 位比特串的叠加态 (量子 Fourier 变换): (I⊗H⊗n)∣A⟩⊗∣0⟩⊗n=∣A⟩⊗(12n/2∑x∈{0,1}n∣x⟩).(I\otimes H^{\otimes n})|A\rangle\otimes |0\rangle^{\otimes n} = |A\rangle \otimes \left( \frac{1}{2^{n/2}}\sum_{x\in \{0,1\}^n} |x\rangle \right).
  2. 制备图态 (graph state) 中边的部分: CZ(A)(∣A⟩⊗12n/2∑x∈{0,1}n∣x⟩)=(∏1≤i<j≤nCZijAij)(∣A⟩⊗12n/2∑x∈{0,1}n∣x⟩).\begin{aligned} CZ(A) \left(|A\rangle \otimes \frac{1}{2^{n/2}}\sum_{x\in\{0,1\}^n} |x\rangle \right) &= \left( \prod_{1\leq i<j\leq n} CZ_{ij}^{A_{ij}} \right) \left(|A\rangle \otimes \frac{1}{2^{n/2}}\sum_{x\in\{0,1\}^n} |x\rangle \right).\\ \end{aligned}
  3. 制备图态 (graph state) 中点的部分: S(A)CZ(A)(∣A⟩⊗12n/2∑x∈{0,1}n∣x⟩)=(⊗i=1nSjAjj)CZ(A)(∣A⟩⊗12n/2∑x∈{0,1}n∣x⟩).S(A)CZ(A) \left(|A\rangle \otimes \frac{1}{2^{n/2}}\sum_{x\in \{0,1\}^n} |x\rangle \right) = \left(\otimes_{i=1}^nS_j^{A_{jj}}\right) CZ(A) \left(|A\rangle \otimes \frac{1}{2^{n/2}}\sum_{x\in \{0,1\}^n} |x\rangle \right).
  4. 再次进行量子 Fourier 变换, 并测量 ancilla 部分的量子比特: H⊗nS(A)CZ(A)(I⊗H⊗n)∣A⟩⊗∣0⟩⊗n=∣A⟩⊗∣z⟩.H^{\otimes n} S(A)CZ(A) (I\otimes H^{\otimes n})|A\rangle\otimes |0\rangle^{\otimes n} = |A\rangle\otimes |z\rangle.

不难验证, 记这两步的操作为 Uq=S(A)CZ(A)U_q = S(A)CZ(A) 的话 (只考虑在 ancilla 上的部分), 我们有 Uq∣x⟩=iq(x)∣x⟩, x∈{0,1}nU_q|x\rangle = i^{q(x)} |x\rangle,~x\in\{0,1\}^n . 此外, 上述量子算法需要的量子线路深度为常数, 时间复杂度为线性. 时间复杂度的来源是输入宽度为 O(n)O(n) , 经典地模拟上述量子线路可以使用 Gottesman-Knill 定理, 需要的时间复杂度是 O(n2)O(n^2) – 于是另一个有趣的问题是, 我们能否证明这一问题的经典算法的时间复杂度无法 (或者在某些假设下, 比如 fine-grained complexity) 进一步改进?

计算优越性和量子非局域性

2D HLFP 的量子优越性

Bravyi, Gosset 和 Konig 在 2017 年证明了, 求解 HLFP 的经典概率线路 (classical probabilistic circuit) 的线路深度至少为对数深度 (log-depth), 即下述定理:

任何由 fan-in ≤K\leq K 的经典概率线路 (classical probabilistic circuit), 以超过 7/87/8 的概率求解 2D HLFP 问题, 需要的线路深度至少为 log⁡(n)8log⁡(K)\frac{\log(n)}{8\log(K)} .

这一问题的量子优越性的来源是, 量子力学中的非局域性 (non-locality) 和经典线路的局域性. 展开来说, 经典概率线路的输入有 AA 和随机输入 rr , 经过深度为 Ω(log⁡(n))\Omega(\log(n)) 的经典线路后, 输出 zz 的概率大于 7/87/8 .

优越性的来源

刻画上述计算优越性, 实际上在比较两件事:

  • 浅层经典线路生成的局部隐变量模型 (local Hidden-Variable model).
  • 常数深度量子线路上的量子非局域性 (non-locality).

举例来说, 我们知道 GHZ 态 (或者说猫态) 12(∣0⟩⊗n+∣1⟩⊗n)\frac{1}{\sqrt{2}}\left(|0\rangle^{\otimes n}+|1\rangle^{\otimes n}\right) 具有长程纠缠 (long-range entanglement). 不妨考虑下述问题, 给定输入 b1,b2,b3∈{0,1}b_1,b_2,b_3\in\{0,1\} , 可以使用随机比特 rr , 在一系列运算后得到 z1,z2,z3∈{−1,1}z_1,z_2,z_3\in\{-1,1\} , 其中 zi=Fi(bi,r)z_i=F_i(b_i,r) 即 FiF_i 为对应部分的线路. 那么我们能否设法选择 rr , 使得 z1z2z3=1⇔b1=b2=b3=0z_1z_2z_3=1 \Leftrightarrow b_1=b_2=b_3=0 , 且 z1z2z3=−1⇔b1=b2=b3=1z_1z_2z_3=-1 \Leftrightarrow b_1=b_2=b_3=1 呢?

对于经典线路我们无法做到, 而对于量子线路, 把 rr 换成 ∣GHZ⟩|GHZ\rangle 即可. 看起来这里的优越性的来源是量子力学的非局域性, 也即量子纠缠 – 我们知道 CHSH game (或者说 Bell 不等式)中量子优势的来源同样是非局域性 (non-locality), 那么这一工作是否和 non-local games 有关系呢?

Coudron, Stark, Vidick [3:1] 进一步注意到, 对于任何常数深度量子线路, 总是能够求解 2D HLFP 意味着对应的 GHZ game 的最大获胜概率为 1. GHZ game 是 non-local games 的一种 (更多介绍见 量子 PCP 猜想浅说 (二): 量子纠缠的交互式证明验证, 并且它的量子策略的最大获胜概率为 1 (同时任何经典策略的最大获胜概率都小于 1). 和 non-local games 的关联从另一个角度印证了我们在上一段的直觉, 而从这里出发, 我们还可以建立常数深度量子线路和其他问题的联系, 比如可验证的随机性 (certifiable randomness).

无限扇入经典线路和平均情形优越性

我们能把 [1:2] 中的量子计算优越性, 即存在常数深度量子线路 (QNC0\mathsf{QNC^0}) 能解决, 但经典线路至少需要对数深度的问题, 扩展到平均情形 (average-case) 吗? 除此之外, [1:3] 中线路是有限 (bounded) 扇入 (NC0\mathsf{NC}^0) 的, 我们能把这一结果扩展到无限 (unbounded) 扇入 (AC0\mathsf{AC}^0) 吗? 扇入 (fan-in) 就是逻辑门的输入的个数, 比如说 nn 个变量的 AND 函数, 只需要一个扇入-nn (无限意味着扇入可能和输入规模一样多) 的 AND 门就可以了, 但是用有限扇入经典线路则需要对数深度, 因而看起来无限扇入经典线路会更强一些.

需要说明的是, 这里使用的 NC0\mathsf{NC^0} 和 AC0\mathsf{AC^0} 的定义和标准对应略有不同, 因为这里考虑的是关系问题 (relation problem), 而不是判定问题 (decision problem), 关系问题意味着我们需要考虑满足某个"关系"的 (输入, 输出) 配对.

为什么[1:4] 有可能被扩展到无限扇入经典线路和平均情形呢? 注意到 [1:5] 中并没有使用任何经典线路复杂性 (circuit complexity) 中的结果 (如著名的 switching lemma, 即无限扇入经典线路在一些情况下有极高的概率可以用有限扇入经典线路来模拟), 用的是在哈密顿量复杂性里的很常见的 light-cone argument (即某一部分对其他部分的影响局限在光锥之内), 因而看起来这样的结果是可能的. 另外, 在 [1:6] 中使用非局域性的 GHZ 态有很多很强的性质, 比如说有长程纠缠, 另外这样的量子态也不能被常数深度量子线路制备. 那么是否其中只有一部分性质, 对于量子计算优越性来说, 是必须的呢?

Watts, Kothari, Schaeffer 和 Tal [5:2] 证明了这样的无条件量子计算优越性即使在平均情形和无限扇入下仍然是成立的. 他们考虑了 generalized GHZ game, 对应的是一个这样的问题:

Parity Halving Problem. 给定一个偶数 Hamming 权的字符串 xx, 找到另一个字符串 yy 使得 yy 的 Hamming 权和 xx 的 Hamming 权的一半的奇偶性相同. 在给定 GHZ 态的情形下, 可以被很简单的常数深度解决.

但在另一方面, 通过分析这一 game 的经典策略, 可以证明这样的问题不能被常数深度的有限扇入的经典线路求解, 即求解的概率几乎和 1/21/2 一样. 进而, 我们用 switching lemma 证明, 无限扇入的经典线路的求解这一问题概率几乎还是一样糟糕.

但即使这样, 看起来我们依然不能绕开 GHZ 态 ∣GHZ±⟩:=12(∣0n⟩±∣1n⟩)|GHZ^{\pm}\rangle := \frac{1}{\sqrt{2}}(|0^n\rangle\pm|1^n\rangle), 而且这样的态也不能被常数深度量子线路制备. 幸运的是, [5:3] 中证明了∣GHZ~±⟩:=12(∣z⟩±∣zˉ⟩)|\tilde{GHZ}^{\pm}\rangle := \frac{1}{\sqrt{2}}(|z\rangle\pm|\bar{z}\rangle), 其中 z∈{0,1}nz\in\{0,1\}^n 是均匀随机选择的比特串, 可以得到同样的量子计算优越性. 注意到 ∣GHZ~±⟩|\tilde{GHZ}^{\pm}\rangle 并没有全局约束 (比如说都是 00 或者 11), 这样的态其实是可以用常数深度量子线路制备的! 具体来说, 它可以看成图态 (graph state) 的特例 (这在基于测量的量子计算, 即 measurement-based quantum computation, 的上下文里很常见), 而制备图态的线路深度和图的顶点度的最大值 Δmax\Delta_{max} (max degree), 以及直径 dd (diameter, 即图上两个连通顶点的最长距离) 有关 – ∣GHZ±⟩|GHZ^{\pm}\rangle 对应的 Δmax=n−1\Delta_{max}=n-1, 而 ∣GHZ~±⟩|\tilde{GHZ}^{\pm}\rangle 对应的是 nn 个顶点的平衡二叉树, 满足 Δmax=3\Delta_{max}=3 和 d=Θ(log⁡n)d=\Theta(\log n).

因此, 在组合了 light-cone argument, 常数深度制备的图态的条件, 线路复杂性理论中的 switching lemma, 以及 generalized GHZ game 的刻画之后, 就可以把 QNC0̸⊆NC0\mathsf{QNC^0} \not\subseteq \mathsf{NC^0} 扩展到 QNC0̸⊆AC0\mathsf{QNC^0} \not\subseteq \mathsf{AC^0}, 并且这样的结果甚至在平均情形下也成立. [6:1] 进一步把这一结果扩展到对数深度经典线路, 但是就不可避免地需要使用一些线路复杂性中的假设.

参考文献

  1. Sergey Bravyi, David Gosset, and Robert Koenig. "Quantum advantage with shallow circuits."Science 362.6412 (2018): 308-311. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

  2. UCSD Spring School on Quantum Computation http://cseweb.ucsd.edu/~slovett/workshops/quantum-computation-2018/ ↩︎

  3. Coudron, Matthew, Jalex Stark, and Thomas Vidick. “Trading locality for time: certifiable randomness from low-depth circuits.” arXiv preprint arXiv:1810.04233 (2018). ↩︎ ↩︎

  4. Le Gall, François. “Average-case quantum advantage with shallow circuits.” In 34th Computational Complexity Conference (CCC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. ↩︎

  5. Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. "Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits."Proceedings of the 51th Annual ACM SIGACT Symposium on Theory of Computing. ACM, 2019. ↩︎ ↩︎ ↩︎ ↩︎

  6. Grier, Daniel, and Luke Schaeffer. “Interactive shallow Clifford circuits: quantum advantage against NC 1^ 1 and beyond.” arXiv preprint arXiv:1911.02555 (2019). ↩︎ ↩︎

  7. Green, Frederic, Steven Homer, Cristopher Moore, and Christopher Pollett. “Counting, fanout and the complexity of quantum ACC.”_Quantum Information & Computation_2, no. 1 (2002): 35-65. ↩︎