Mukhopadhyay Priyanka
Department of Computer Science, University of Toronto, Toronto, ON, Canada.
Sci Rep. 2025 Mar 31;15(1):11002. doi: 10.1038/s41598-025-95283-5.
Quantum algorithms claim significant speedup over their classical counterparts for solving many problems. An important aspect of many of these algorithms is the existence of a quantum oracle, which needs to be implemented efficiently in order to realize the claimed advantages in practice. A quantum random access memory (QRAM) is a promising architecture for realizing these oracles. In this paper we develop a new design for QRAM and implement it with Clifford+T circuit. We focus on optimizing the T-count and T-depth since non-Clifford gates are the most expensive to implement fault-tolerantly in most error correction schemes. Integral to our design is a polynomial encoding of bit strings and so we refer to this design as [Formula: see text]. Compared to the previous state-of-the-art bucket brigade architecture for QRAM, we achieve an exponential improvement in T-depth, while reducing T-count and keeping the qubit-count same. Specifically, if N is the number of memory locations to be queried, then [Formula: see text] has T-depth [Formula: see text], T-count [Formula: see text] and uses O(N) logical qubits, while the bucket brigade circuit has T-depth [Formula: see text], T-count O(N) and uses O(N) qubits. Combining two [Formula: see text] we design a quantum look-up-table, [Formula: see text], that has T-depth [Formula: see text], T-count [Formula: see text] and qubit count [Formula: see text]. A quantum look-up table (qLUT) or quantum read-only memory (QROM) has restricted functionality than a QRAM. For example, it cannot write into a memory location and the circuit needs to be compiled each time the contents of the memory change. The previous state-of-the-art CSWAP architecture has T-depth [Formula: see text], T-count [Formula: see text] and qubit count [Formula: see text]. Thus we achieve a double exponential improvement in T-depth while keeping the T-count and qubit-count asymptotically same. Additionally, with our polynomial encoding of bit strings, we develop a method to optimize the Toffoli-count of circuits, specially those consisting of multi-controlled-NOT gates.
量子算法在解决许多问题时，相较于其经典对应算法有着显著的加速效果。这些算法中的许多算法的一个重要方面是存在量子预言机，为了在实践中实现所宣称的优势，需要高效地实现它。量子随机存取存储器（QRAM）是实现这些预言机的一种很有前景的架构。在本文中，我们开发了一种QRAM的新设计，并使用Clifford+T电路来实现它。我们专注于优化T门数量和T门深度，因为在大多数纠错方案中，非Clifford门是容错实现中最昂贵的。我们设计的一个重要组成部分是比特串的多项式编码，所以我们将这种设计称为[公式：见原文]。与之前用于QRAM的最先进的桶形队列架构相比，我们在T门深度上实现了指数级的改进，同时减少了T门数量并保持量子比特数不变。具体来说，如果N是要查询的存储位置的数量，那么[公式：见原文]的T门深度为[公式：见原文]，T门数量为[公式：见原文]，并使用O(N)个逻辑量子比特，而桶形队列电路的T门深度为[公式：见原文]，T门数量为O(N)，并使用O(N)个量子比特。结合两个[公式：见原文]，我们设计了一个量子查找表，[公式：见原文]，其T门深度为[公式：见原文]，T门数量为[公式：见原文]，量子比特数为[公式：见原文]。量子查找表（qLUT）或量子只读存储器（QROM）的功能比QRAM受到更多限制。例如，它不能写入存储位置，并且每次存储器内容改变时都需要编译电路。之前最先进的CSWAP架构的T门深度为[公式：见原文]，T门数量为[公式：见原文]，量子比特数为[公式：见原文]。因此，我们在T门深度上实现了双指数级的改进，同时使T门数量和量子比特数渐近相同。此外，通过我们对比特串的多项式编码，我们开发了一种优化电路的托佛利门数量的方法，特别是那些由多控制非门组成的电路。
