A quantum random access memory (QRAM) using a polynomial encoding of binary strings

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. 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. Integral to our design is a polynomial encoding of bit strings and so we refer to this design as QRAMpoly. 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, then QRAMpoly has T-depth O(loglog N), T-count O(N-log N) and qubit count $O(N)$, while the bucket brigade circuit has T-depth O(log N), T-count $O(N)$ and qubit count $O(N)$. Combining two QRAMpoly we design a quantum look-up-table, qLUTpoly, that has T-depth O(loglog N), T-count O(√N) and qubit count O(√N). A qLUT or quantum read-only memory (QROM) has restricted functionality than a QRAM and needs to be compiled each time the contents of the memory change. The previous state-of-the-art CSWAP architecture has T-depth O(√N), T-count O(√N) and qubit count O(√N). 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.