论文标题
量子随机访问存储的机器
Quantum Random Access Stored-Program Machines
论文作者
论文摘要
随机访问机（RAM）和随机访问存储的程序机（RASP）是计算模型，与图灵机（TMS）（TMS）相比，它更接近现实世界计算机的体系结构。它们在算法的复杂性分析中也很方便。 RAM，RASP和TMS之间的关系经过了充分研究。但是，文献中仍然缺少其量子对应物之间的明确关系。我们通过正式定义量子随机访问机（QRAM）和量子随机访问存储机器（QRASPS）的模型来填补这一空白，并阐明QRAM，QRASPS和量子图灵机（QTMS）之间的关系。 In particular, we show that $\textbf{P} \subseteq \textbf{EQRAMP} \subseteq \textbf{EQP} \subseteq \textbf{BQP} = \textbf{BQRAMP}$, where $\textbf{EQRAMP}$ and $ \ textbf {bqramp} $代表分别由多项式时间QRAM确定和有界错误解决的问题集。我们证明的核心是具有扩展的停止方案的QTM的标准化，这是独立的。
Random access machines (RAMs) and random access stored-program machines (RASPs) are models of computing that are closer to the architecture of real-world computers than Turing machines (TMs). They are also convenient in complexity analysis of algorithms. The relationships between RAMs, RASPs and TMs are well-studied. However, clear relationships between their quantum counterparts are still missing in the literature. We fill in this gap by formally defining the models of quantum random access machines (QRAMs) and quantum random access stored-program machines (QRASPs) and clarifying the relationships between QRAMs, QRASPs and quantum Turing machines (QTMs). In particular, we show that $\textbf{P} \subseteq \textbf{EQRAMP} \subseteq \textbf{EQP} \subseteq \textbf{BQP} = \textbf{BQRAMP}$, where $\textbf{EQRAMP}$ and $\textbf{BQRAMP}$ stand for the sets of problems that can be solved by polynomial-time QRAMs with certainty and bounded-error, respectively. At the heart of our proof, is a standardisation of QTM with an extended halting scheme, which is of independent interest.
