论文标题
空间有限的计算的量子优势
Quantum advantage for computations with limited space
论文作者
论文摘要
量子计算有能力解决经典环境中难以理解的问题。限制所考虑的计算类型通常可以通过量子计算来建立可证明的理论优势，然后通过实验证明它。在本文中，我们考虑了限制空间的计算，其中输入是仅读取的内存，并且只能计算一个（qu）位。我们表明，可以通过使用$ o（n^2）$ gates将量子信号处理作为有限的空间量子计算来精确实现$ n $ bit对称的布尔函数，但是其中有些只能通过类似地定义的典型的概率（n/\ sqrt {2}^n）$ 1/2 + o（N/\ sqrt {2}^n）$ 1/2 + O（通过类似地定义）进行评估。我们通过实验表明计算$ 3 $ - ，$ 4 $ - ，$ 5 $ - 和$ 6 $ - 位对称的布尔函数通过量子电路进行，利用自定义的两金门，其算法成功概率超过了最佳的经典。这建立并在实验上验证了另一种量子优势 - 量子废料空间比类似的古典空间更有价值 - 并要求对量子电路中的时空折衷进行深入探索。
Quantum computations promise the ability to solve problems intractable in the classical setting. Restricting the types of computations considered often allows to establish a provable theoretical advantage by quantum computations, and later demonstrate it experimentally. In this paper, we consider space-restricted computations, where input is a read-only memory and only one (qu)bit can be computed on. We show that $n$-bit symmetric Boolean functions can be implemented exactly through the use of quantum signal processing as restricted space quantum computations using $O(n^2)$ gates, but some of them may only be evaluated with probability $1/2 + O(n/\sqrt{2}^n)$ by analogously defined classical computations. We experimentally demonstrate computations of $3$-, $4$-, $5$-, and $6$-bit symmetric Boolean functions by quantum circuits, leveraging custom two-qubit gates, with algorithmic success probability exceeding the best possible classically. This establishes and experimentally verifies a different kind of quantum advantage -- one where quantum scrap space is more valuable than analogous classical space -- and calls for an in-depth exploration of space-time tradeoffs in quantum circuits.
