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 \(\text {QRAM}_{poly}\) . 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 \(\text {QRAM}_{poly}\) has T-depth \(O(\log \log N)\) , T-count \(O(N-\log N)\) and uses O(N) logical qubits, while the bucket brigade circuit has T-depth \(O(\log N)\) , T-count O(N) and uses O(N) qubits. Combining two \(\text {QRAM}_{poly}\) we design a quantum look-up-table, \(\text {qLUT}_{poly}\) , that has T-depth \(O(\log \log N)\) , T-count \(O(\sqrt{N})\) and qubit count \(O(\sqrt{N})\) . 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 \(O(\sqrt{N})\) , T-count \(O(\sqrt{N})\) and qubit count \(O(\sqrt{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.
