论文标题
并行在铲斗旅量子RAM中查询
Parallelising the Queries in Bucket Brigade Quantum RAM
论文作者
论文摘要
量子算法通常使用量子公羊（QRAM）来访问以数据库方式存储的信息。 QRAM必须快速，资源效率和耐故障。后者通常会受到访问速度的影响，因为较短的时间将存储信息的暴露量较小。算法的总执行时间取决于QRAM访问时间，其中包括：1）地址翻译时间和2）有效的查询时间。提出了铲斗旅的QRAMS，以更快地解决以指数为代价的替代。我们说明了一种系统的方法，可通过使用Clifford+T Gate并行性显着减少有效的查询时间。该方法不会引入任何Ancillae Qubits。我们的并行方法与表面代码量子误差校正兼容。我们表明并行化是在Clifford+T门方面有利的Toffoli Gate分解的结果，并且在翻译地址后，我们实现了理论$ \ Mathcal {O}（1）$并行的有效查询。我们得出的结论是，从理论上讲：1）易于使用经典RAM的速度进行大约进行易耐断层的桶式量子量子RAM查询； 2）与仅量子读取的记忆相比，从铲斗大队寻址方案中的许多杂物是实现指数查询速度的折衷成本，这些记忆的查询是按设计顺序进行的。可以在网上获得的软件中实现了编译，并行和分析所提供的QRAM电路的方法。
Quantum algorithms often use quantum RAMs (QRAM) for accessing information stored in a database-like manner. QRAMs have to be fast, resource efficient and fault-tolerant. The latter is often influenced by access speeds, because shorter times introduce less exposure of the stored information to noise. The total execution time of an algorithm depends on the QRAM access time which includes: 1) address translation time, and 2) effective query time. The bucket brigade QRAMs were proposed to achieve faster addressing at the cost of exponentially many ancillae. We illustrate a systematic method to significantly reduce the effective query time by using Clifford+T gate parallelism. The method does not introduce any ancillae qubits. Our parallelisation method is compatible with the surface code quantum error correction. We show that parallelisation is a result of advantageous Toffoli gate decomposition in terms of Clifford+T gates, and after addresses have been translated, we achieve theoretical $\mathcal{O}(1)$ parallelism for the effective queries. We conclude that, in theory: 1) fault-tolerant bucket brigade quantum RAM queries can be performed approximately with the speed of classical RAM; 2) the exponentially many ancillae from the bucket brigade addressing scheme are a trade-off cost for achieving exponential query speedup compared to quantum read-only memories whose queries are sequential by design. The methods to compile, parallelise and analyse the presented QRAM circuits were implemented in software which is available online.
