Efficient and Error-Resilient Data Access Protocols for a Limited-Sized Quantum Random Access Memory

Zhaoyun Chen, Cheng Xue, Tai‐Ping Sun, Huanyu Liu, Xi‐Ning Zhuang, Menghan Dou, Tian-Rui Zou, Yuan Fang, Yu-Chun Wu, Guo‐Ping Guo, Guo, Guo-PingarXiv 2023 · DOI · arXiv

Abstract

Quantum Random Access Memory (QRAM) is a critical component for loading classical data into quantum computers. While constructing a practical QRAM presents several challenges, including the impracticality of an infinitely large QRAM size and a fully error-correction implementation, it is essential to consider a practical case where the QRAM has a limited size. In this work, we focus on the access of larger data sizes without keeping on increasing the size of the QRAM. Firstly, we address the challenge of word length, as real-world datasets typically have larger word lengths than the single-bit data that most previous studies have focused on. We propose a novel protocol for loading data with larger word lengths $k$ without increasing the number of QRAM levels $n$. By exploiting the parallelism in the data query process, our protocol achieves a time complexity of $O(n+k)$ and improves error scaling performance compared to existing approaches. Secondly, we provide a data-loading method for general-sized data access tasks when the number of data items exceeds $2^n$, which outperforms the existing hybrid QRAM+QROM architecture. Our method contributes to the development of time and error-optimized data access protocols for QRAM devices, reducing the qubit count and error requirements for QRAM implementation, and making it easier to construct practical QRAM devices with a limited number of physical qubits.

1. Introduction

For quantum algorithms to be useful in fields like machine learning or differential equation solving, they must efficiently load massive amounts of classical data. Quantum Random Access Memory (QRAM) serves as the theoretical "bridge" for this task, allowing a quantum computer to query classical data in superposition. However, current QRAM research often overlooks the complexities of real-world data, specifically the word length ($k$). Standard protocols either query bits sequentially, leading to slow performance, or require hardware expansion that is currently impractical. Furthermore, near-term quantum hardware is limited in size and prone to noise. This paper introduces a "Parallel Protocol" that utilizes pipelining to reduce time complexity from $O(nk)$ to $O(n+k)$ and drastically improves error resilience.

2. Methods: The Parallel Protocol

The proposed Parallel Protocol draws inspiration from classical CPU pipelining to optimize the "bucket-brigade" QRAM architecture.

2.1 Circuit-Level Parallelism and Bidirectional Routing

In a standard QRAM, a single bit travels from the root to the leaves and back before the next bit starts. The Parallel Protocol allows multiple bits to occupy the QRAM tree simultaneously. As soon as one bit moves to the next layer, the next bit enters the root. To prevent interference between simultaneous bits, the authors utilize bidirectional routing, allowing data bits to move up and down the tree independently.

Comparison of data access protocols: Parallel, Nonparallel, and High-bandwidth.

2.2 Hybrid-Parallel and High-Bandwidth Protocols

For datasets larger than the QRAM's capacity (i.e., more than $2^n$ entries), a hybrid method combining QRAM and QROM logic is introduced. Additionally, a high-bandwidth variant is proposed to further lower the overall cost by increasing the number of bits transferred at once without necessarily needing to increase the number of address levels.

3. Results and Performance

The protocols were evaluated using numerical simulations and noise models, applying damping and depolarizing error channels to each working qudit/qubit to test fidelity under realistic noisy conditions.

3.1 Time and Error Scaling

The shift from multiplicative to additive complexity—from $O(nk)$ to $O(n+k)$—is a significant improvement. For a 32-level QRAM loading 32-bit words, this reduces the time steps from 1024 to roughly 64. This parallelism also acts as an error buffer; because execution time is shorter, qubits have less time to decohere. For a typical case where $n=k=32$, error resilience is improved approximately 16-fold, with error scaling moving from $O(n^3)$ to $O(n^2)$.

Performance comparison of different QRAM protocols in terms of complexity and error scaling.

3.2 Cost Efficiency

The authors introduce a "Cost Factor" ($T \epsilon_t / n\epsilon$) to provide a standardized comparison of protocol quality. The Parallel Protocol's cost factor is $(n+k)^2$, which is significantly lower than the $k^2n^2$ cost of non-parallel approaches. Numerical simulations confirmed that the Parallel Protocol maintains significantly higher fidelity than the non-parallel protocol as address length increases.

4. Discussion and Conclusion

While the Parallel Protocol offers substantial theoretical advantages, its implementation requires hardware capable of bidirectional routing and layered operations. Future work will focus on applying these protocols to specific mid-term quantum algorithms, such as those in quantum chemistry or financial modeling, to evaluate real-world overhead reduction. By optimizing both time and error requirements, this work moves us closer to practical QRAM implementation on limited-sized physical hardware.

Summary updated

Abstract

Quantum Random Access Memory (QRAM) is a critical component for loading classical data into quantum computers. While constructing a practical QRAM presents several challenges, including the impracticality of an infinitely large QRAM size and a fully error-correction implementation, it is essential to consider a practical case where the QRAM has a limited size. In this work, we focus on the access of larger data sizes without keeping on increasing the size of the QRAM. Firstly, we address the challenge of word length, as real-world datasets typically have larger word lengths than the single-bit data that most previous studies have focused on. We propose a novel protocol for loading data with larger word lengths $k$ without increasing the number of QRAM levels $n$. By exploiting the parallelism in the data query process, our protocol achieves a time complexity of $O(n+k)$ and improves error scaling performance compared to existing approaches. Secondly, we provide a data-loading method for general-sized data access tasks when the number of data items exceeds $2^n$, which outperforms the existing hybrid QRAM+QROM architecture. Our method contributes to the development of time and error-optimized data access protocols for QRAM devices, reducing the qubit count and error requirements for QRAM implementation, and making it easier to construct practical QRAM devices with a limited number of physical qubits.
BibTeX
@misc{chen2023efficient,
  author = {Zhaoyun Chen and Cheng Xue and Tai‐Ping Sun and Huanyu Liu and Xi‐Ning Zhuang and Menghan Dou and Tian-Rui Zou and Yuan Fang and Yu-Chun Wu and Guo‐Ping Guo and Guo, Guo-Ping},
  title = {{Efficient and Error-Resilient Data Access Protocols for a Limited-Sized Quantum Random Access Memory}},
  year = {2023},
  eprint = {2303.05207},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.05207},
}
Figure