Skip to content

Quantum random access memory

Rough overview (in words)

Quantum random access memory (QRAM) is a construction that enables coherent access to classical data, such that multiple different elements in a classical database can be read in superposition. The ability to rapidly access large, unstructured classical data sets in this way is crucial to the speedups of certain quantum algorithms (for example, quantum machine learning based on quantum linear algebra). QRAM is commonly invoked in such cases as a way to circumvent data-input bottlenecks [1], i.e. situations where loading input data could limit the end-to-end runtime of an algorithm. It remains an open question, however, whether a large-scale QRAM will ever be practical, casting doubt on quantum speedups that rely on QRAM. Note that, while here we focus on the more common use case of loading classical data with QRAM, certain QRAM architectures can be adapted to also load quantum data.

Rough overview (in math)

Consider a length-\(N\), unstructured classical data vector \(x\), and denote the \(i^\mathrm{th}\) entry as \(x_i\). Let the number of bits of \(x_i\) be denoted by \(d\) and let \(D = 2^d\). Given an input quantum state \(\ket{\psi} = \sum_{i =0}^{N-1}\sum_{j=0}^{D-1}\alpha_{ij} \ket{i}_A \ket{j}_B\), QRAM is defined [2] as a unitary operation \(Q\) with the action,

\[\begin{equation} Q\ket{\psi} = Q\sum_{i =0}^{N-1}\sum_{j=0}^{D-1}\alpha_{ij} \ket{i}_A \ket{j}_B = \sum_{i =0}^{N-1}\sum_{j=0}^{D-1}\alpha_{ij} \ket{i}_A \ket{j \oplus x_i}_B. \label{eq:QRAM_definition} \end{equation}\]

Here, \(A\) is a \(\log_2(N)\)-qubit register, and \(B\) is a \(d\)-qubit register. Note that the unitary \(Q\) can also be understood as an oracle (or black box) providing access to \(x\), as \(Q(\sum_i \alpha_i \ket{i}\ket{0}) = \sum_i \alpha_i \ket{i}\ket{x_i}\).

Let \(T_Q\) denote the time it takes to implement the operation \(Q\), where \(T_Q\) can be measured in circuit depth, total gate cost, \(T\)-gate cost, etc., depending on the context. Algorithms that rely on QRAM to claim exponential speedups over their classical counterparts frequently assume that \(T_Q = \mathrm{polylog} (N)\).

Dominant resource cost (gates/qubits)

The QRAM operation \(Q\) can be implemented as a quantum circuit that uses \(\mathcal{O}\left( N \right)\) ancillary qubits and \(\mathcal{O}\left( N \right)\) gates. Assuming gates acting on disjoint qubits can be parallelized, the depth of the circuit is only \(T_Q = \mathcal{O}\left( \log(N) \right)\). Explicit circuits can be found in, e.g., [3, 4]. The number of ancillary qubits can be reduced at the price of increased circuit depth; circuits implementing \(Q\) can be constructed using \(\mathcal{O}\left( N/M \right)\) ancillary qubits and depth \(\mathcal{O}\left( M\log(N) \right)\), where \(M \in [1, N]\), see examples in [5, 6, 3, 4] (the setting of \(M=N/\log(N)\) is sometimes referred to as "QROM\"—see terminology caveats below—and its fault-tolerant cost of implementation is well established [7]).

Note that the above resource costs neglect the dependence on \(d\) for simplicity, since different constructions yield different \(d\) dependence. For example, the \(d\) bits of a data element can be queried in series, requiring \(\mathcal{O}\left( N \right)\) ancillary qubits with \(T_Q = \mathcal{O}\left( d\log(N) \right)\) (improvement to \(T_Q = \mathcal{O}\left( d+\log(N) \right)\) is possible for certain QRAM architectures [8]). Alternatively, the \(d\) bits can be accessed in parallel, with \(T_Q = \mathcal{O}\left( \log(N) \right)\), but at the price of \(\mathcal{O}\left( Nd \right)\) ancillary qubits.

Caveats

The main concern for QRAM's practicality is the large hardware overhead that is necessary to realize fast queries \(T_Q = \mathcal{O}\left( \log(N) \right)\). This cost is likely to be prohibitive for big-data applications where \(N\) can be millions or billions. This cost will be magnified by additional overhead associated with error correction and fault tolerance [3], especially given that circuits implementing \(Q\) are composed of \(\mathcal{O}\left( N \right)\) non-Clifford gates. Indeed, the fact that \(\mathcal{O}\left( N \right)\) non-Clifford gates are required, together with the assumption that magic state distillation is expensive to run in a massively parallel fashion, has led some to argue that \(T_Q = \mathcal{O}\left( \log(N) \right)\) is not realistic in a fault-tolerant setting. It is possible that alternative approaches to fault tolerance tailored to QRAM could help alleviate this large hardware overhead.

The fault-tolerance overhead may be reduced for the so-called bucket-brigade QRAM (BBQRAM) [2, 9, 4]. BBQRAM can be understood as a family of circuits implementing \(Q\) that are intrinsically resilient to noise. More precisely, [4] shows that if \(\epsilon\) is the per-gate error rate, BBQRAM circuits can implement \(Q\) with leading-order fidelity \(F \sim 1- \epsilon\, \mathrm{polylog}(N)\), while generic circuits implementing \(Q\) have leading-order fidelity \(F \sim 1- \epsilon\, \mathcal{O}\left( N \right)\). Nevertheless, some amount of error correction will almost certainly be required even for BBQRAM circuits.

Some terminology caveats:

  • The unitary \(Q\) is referred to by some as Quantum Read-Only Memory (QROM) [7], reflecting the fact that \(Q\) corresponds only to reading data. Some algorithms also require the ability to write to the vector \(x\) duration a computation, but the writing of classical data need not be implemented via a quantum circuit.
  • The term QRAM is used by different authors to refer to the unitary \(Q\), families of circuits that implement \(Q\), or quantum hardware that runs said circuits.
  • Some use the term QRAM to refer exclusively to the case \(N\gg 1\) and \(T_Q = \mathrm{polylog} (N)\), where the implementation challenges for QRAM are most pronounced.
  • The terms QRAM and QROM are sometimes synonymous with the cases of \(T_Q = \mathrm{polylog}(N)\) and \(T_Q = \mathrm{poly}(N)\), respectively, even though \(T_Q\) is unrelated to the distinction between reading and writing. The term QROAM has also been used to describe intermediate circuits that trade off depth and width [6].

Elsewhere in this document, we follow the convention described in the final two bullet points above: usage of the term QRAM, unless specified otherwise, refers to the ability to implement \(Q\) at cost \(\mathrm{polylog}(N)\).

Example use cases

  • Quantum linear algebra. QRAM can be used as an oracle implementation for linear algebra algorithms operating on unstructured data (e.g., by acting as a subroutine in a block-encoding), with applications in machine learning, finance, etc. For example, the quantum recommendation systems algorithm [10] (now dequantized) uses QRAM as a subroutine to efficiently encode rows of an input data matrix in the amplitudes of quantum states (see Appendix A of [10] for details).
  • Hamiltonian simulation, quantum chemistry, condensed matter physics. In the linear combination of unitaries query model, QRAM can be used as a subroutine for "PREPARE" oracles that encode coefficients of the simulated Hamiltonian into the amplitudes of quantum states [7]. These use cases typically consider the hybrid QROM/QRAM constructions with \(\mathcal{O}\left( K \log(N) \right)\) ancillary qubits and depth \(\mathcal{O}\left( N/K \right)\) (with \(K\) a parameter to be optimized), because the amount of data (and thus the size of \(N\)) scales only polynomially with the system size.
  • Grover's search. QRAM can be used as an oracle implementation for Grover's oracle in the context of an unstructured database search, see Chapter 4 of [11]. This sort of Grover's search appears for example in quantum algorithms that utilize dynamic programming to give polynomial speedups for combinatorial optimization problems like the traveling salesman problem [12]. However, it has been argued that a quantum computer running Grover's algorithm with a QRAM oracle would not provide a speedup over a classical computer with comparable hardware resources [13].
  • Topological data analysis (TDA). A small QRAM (i.e., not exponentially larger than the main quantum data register) is used in some quantum algorithms for TDA [14, 15] in order to load the positions of the data points for computing whether simplices are present in the complex at a given length scale.

Further reading

  • Reference [16] focuses on various fundamental and practical concerns for large-scale QRAM, while also providing a comprehensive survey of the field.
  • Reference [17] provides an overview of practical concerns facing QRAM in the context of big-data applications (though the discussions of noise resilience there and in [9] are somewhat outdated, cf. [4]).

Bibliography

  1. Scott Aaronson. Read the fine print. Nature Physics, 11(4):291–293, 2015. URL: https://scottaaronson.com/papers/qml.pdf, doi:10.1038/nphys3272.

  2. Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical Review Letters, 100(16):160501, 2008. arXiv: https://arxiv.org/abs/0708.1879. doi:10.1103/PhysRevLett.100.160501.

  3. Olivia Di Matteo, Vlad Gheorghiu, and Michele Mosca. Fault-tolerant resource estimation of quantum random-access memories. IEEE Transactions on Quantum Engineering, 1:1–13, 2020. arXiv: https://arxiv.org/abs/1902.01329. doi:10.1109/TQE.2020.2965803.

  4. Connor T. Hann, Gideon Lee, S.M. Girvin, and Liang Jiang. Resilience of quantum random access memory to generic noise. PRX Quantum, 2:020311, 4 2021. arXiv: https://arxiv.org/abs/2012.05340. URL: https://link.aps.org/doi/10.1103/PRXQuantum.2.020311, doi:10.1103/PRXQuantum.2.020311.

  5. Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer. Trading t-gates for dirty qubits in state preparation and unitary synthesis. arXiv: https://arxiv.org/abs/1812.00954, 2018.

  6. Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush. Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization. Quantum, 3:208, 12 2019. arXiv: https://arxiv.org/abs/1902.02134. URL: https://doi.org/10.22331/q-2019-12-02-208, doi:10.22331/q-2019-12-02-208.

  7. Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear t complexity. Physical Review X, 8(4):041015, 2018. arXiv: https://arxiv.org/abs/1805.03662. doi:10.1103/PhysRevX.8.041015.

  8. Zhao-Yun Chen, Cheng Xue, Tai-Ping Sun, Huan-Yu Liu, Xi-Ning Zhuang, Meng-Han Dou, Tian-Rui Zou, Yuan Fang, Yu-Chun Wu, and Guo-Ping Guo. An efficient and error-resilient protocol for quantum random access memory with generalized data size. arXiv: https://arxiv.org/abs/2303.05207, 2023.

  9. Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O'Connor, Michele Mosca, and Priyaa Varshinee Srinivasan. On the robustness of bucket brigade quantum ram. New Journal of Physics, 17(12):123010, 2015. arXiv: https://arxiv.org/abs/1502.03450. doi:10.1088/1367-2630/17/12/123010.

  10. Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), 49:1–49:21. 2017. arXiv: https://arxiv.org/abs/1603.08675. doi:10.4230/LIPIcs.ITCS.2017.49.

  11. Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000. doi:10.1017/CBO9780511976667.

  12. Andris Ambainis, Kaspars Balodis, Jānis Iraids, Martins Kokainis, Krišjānis Prūsis, and Jevgēnijs Vihrovs. Quantum speedups for exponential-time dynamic programming algorithms. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1783–1793. SIAM, 2019. arXiv: https://arxiv.org/abs/2104.14384. doi:10.1137/1.9781611975482.107.

  13. Damian S Steiger and Matthias Troyer. Racing in parallel: quantum versus classical. In APS March Meeting Abstracts, volume 2016, H44–010. 2016. See related talk video.

  14. Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. Quantum algorithms for topological and geometric analysis of data. Nature Communications, 7(1):1–7, 2016. arXiv: https://arxiv.org/abs/1408.3106. doi:https://doi.org/10.1038/ncomms10138.

  15. Sam McArdle, András Gilyén, and Mario Berta. A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits. arXiv: https://arxiv.org/abs/2209.12887, 2022.

  16. Samuel Jaques and Arthur G Rattew. Qram: a survey and critique. arXiv: https://arxiv.org/abs/2305.10310, 2023.

  17. Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig. Quantum machine learning: a classical perspective. Proceedings of the Royal Society A, 474(2209):20170551, 2018. arXiv: https://arxiv.org/abs/1707.08561. doi:https://doi.org/10.1098/rspa.2017.0551.