论文标题
带有量子随机访问门的内存压缩
Memory Compression with Quantum Random-Access Gates
论文作者
论文摘要
在经典RAM中，我们具有以下有用的属性。如果我们在执行过程中使用$ M $存储器单元使用$ M $内存单元，并且在某种意义上，在任何时间点，$ m $单元中的$ m $只有$ m $的零件将是非零的，那么我们可以将其“压缩”到另一种算法中，仅使用$ m \ log M $内存，并且在几乎同一时间运行。我们可以通过使用哈希表或自平衡树模拟内存来做到这一点。 我们显示了配备量子随机访问门的量子算法的类似结果。如果我们有一种量子算法，该算法在时间$ t $中运行并使用$ m $ Qubits，以便在任何时间步骤中，在最多$ m $的锤击量计算中支持了内存状态，那么它可以由仅使用$ o（m \ log m）$ o（m \ log m）$ o（$ o o o o o（$ o）$ o（$ o o（$ o（ 我们展示如何以黑盒方式使用该定理来简化几篇论文中的演示文稿。从广义上讲，当需要使用独立于历史的量子数据结构时，通常可以构建一个空间内置，但稀疏的量子数据结构，然后对我们的主要定理提出上诉。这导致更简单，更短的论点。
In the classical RAM, we have the following useful property. If we have an algorithm that uses $M$ memory cells throughout its execution, and in addition is sparse, in the sense that, at any point in time, only $m$ out of $M$ cells will be non-zero, then we may "compress" it into another algorithm which uses only $m \log M$ memory and runs in almost the same time. We may do so by simulating the memory using either a hash table, or a self-balancing tree. We show an analogous result for quantum algorithms equipped with quantum random-access gates. If we have a quantum algorithm that runs in time $T$ and uses $M$ qubits, such that the state of the memory, at any time step, is supported on computational-basis vectors of Hamming weight at most $m$, then it can be simulated by another algorithm which uses only $O(m \log M)$ memory, and runs in time $\tilde O(T)$. We show how this theorem can be used, in a black-box way, to simplify the presentation in several papers. Broadly speaking, when there exists a need for a space-efficient history-independent quantum data-structure, it is often possible to construct a space-inefficient, yet sparse, quantum data structure, and then appeal to our main theorem. This results in simpler and shorter arguments.
