论文标题
通过自适应测量值的经典布尔功能的量子算法：时空资源的指数减少
Quantum algorithms for classical Boolean functions via adaptive measurements: Exponential reductions in space-time resources
论文作者
论文摘要
恒定深度量子电路的计算能力有限，可以通过根据中路测量结果调整未来的门来提高。我们使用群集状态资源和经典的辅助处理器制定了基于自适应测量的量子计算的框架中各种布尔函数的计算，该量子可以添加bits modulo 2，所谓的$ l2 $ -MBQC。我们的自适应方法克服了一个已知的挑战，即在非自适应环境中计算这些功能需要一个资源状态，该资源状态在计算输入的大小上呈指数级。特别是，我们基于量子信号处理技术构建自适应$ L2 $ -MBQC算法，该技术在时空资源（即QUBIT计数，量子计数，经典的内存大小，呼叫数量以及对副处理器的呼叫数量）中计算Mod-$ p $功能的功能。由于该主题是多元化的，并且历史悠久，因此该论文包括对几种先前构建的算法的评论，并使用群集状态资源将其作为自适应$ L2 $ -MBQC重新铸造。我们的结果构成了关于恒定深度量子电路的功率与恒定深度的古典电路之间的口径分离的旧定理的替代证明。
The limited computational power of constant-depth quantum circuits can be boosted by adapting future gates according to the outcomes of mid-circuit measurements. We formulate computation of a variety of Boolean functions in the framework of adaptive measurement-based quantum computation using a cluster state resource and a classical side-processor that can add bits modulo 2, so-called $l2$-MBQC. Our adaptive approach overcomes a known challenge that computing these functions in the nonadaptive setting requires a resource state that is exponentially large in the size of the computational input. In particular, we construct adaptive $l2$-MBQC algorithms based on the quantum signal processing technique that compute the mod-$p$ functions with the best known scaling in the space-time resources (i.e., qubit count, quantum circuit depth, classical memory size, and number of calls to the side-processor). As the subject is diverse and has a long history, the paper includes reviews of several previously constructed algorithms and recasts them as adaptive $l2$-MBQCs using cluster state resources. Our results constitute an alternative proof of an old theorem regarding an oracular separation between the power of constant-depth quantum circuits and constant-depth classical circuits with unbounded fan-in NAND and mod-$p$ gates for any prime $p$.
