.png){kind=icon}
Return
A quantum random access memory (QRAM) using a polynomial encoding of binary strings
.png){kind=icon}
OA
AI
DOI：10.1038/s41598-025-95283-5.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 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 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 QRAM(poly) we design a quantum look-up-table, qLUT(poly), that has T-depth O(log log N), T-countO root(N) and qubit count O root(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 root(N), T-count O root(N) and qubit count O root(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.
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.9
Papers:
28.0W
Citations:
83.5W
Organization
Cited Papers
No cited papers available