This entry is about QRAM in the sense of Giovanetti et al. 2008. For the other sense of classically controlled quantum computation see there.
quantum algorithms:
constructive mathematics, realizability, computability
propositions as types, proofs as programs, computational trinitarianism
In quantum computing and quantum information theory, the notion of quantum random access memory (QRAM, due to Giovanetti, Lloyd & Maccone 2008) is meant to be the quantum-analog of the classical notion of random access memory; the key point being that QRAM may be addressed by quantum superpositions of address values and then reads/writes the corresponding quantum superposition of quantum data (GLM08, (1)).
The circuit model for QRAM essentially identifies a quantum program
of nominal type $\mathscr{H} \longrightarrow \mathscr{H}$
but with access to a QRAM space $QMem$
with a a quantum circuit of type
In the existing literature this is typically stated in terms of concrete examples rather than in abstract generality, see for instance [Arunachalam et al 2015, Fig. 9] or [Park, Petruccione & Rhee 2019, Fig 1] with review in [Phalak, Chatterjee & Ghosh 2023, Fig 4]. A nicely transparent example is given in by quantumcomputinguk.org:
(Here the block “Memory Cells” is our “$QMem$”, the rest is our $\mathscr{H}$.)
This quantum circuit is such that (assuming $q_2 =\cdots = q_6 = 0$)
if the Read/Write flag is 0 then
it keeps all qbits (except for “Routing” and) except that the “Readout QBit” is set to one of the four “Memory values” depending on the four possible values of the “Addressing QBits”
if the Read/Write flag is 1 then
it keeps all qbits (except for “Routing” and) except that the “Memory QBit” addressed by the value of the “Addressing QBits” is set to the value of $q_{10}$.
for a superposition of these inputs it yields the corresponding superposition of outputs.
Recall that a classical random access memory of data type $Mem$ is modeled (in terms of monads in computer science) by the state monad induced from the cartesian internal hom-adjunction
namely:
(Notice that in concrete applications people often insist that $Mem =$ Bool${}^{\times^n}$, but the conceptual nature of RAM is indifferent to this choice.)
Now, with classical data types (such as bits) replaced by quantum data types (such as qbits), namely by linear types, the analogous internal hom-adjunction is
and the corresponding monad is
and it seems clear that this does correspond to the intended behaviour of QRAM (where we are free to set $QMem \coloneqq$ QBit${}^{\otimes^n}$, if desired, which is typically the case in the literature).
In particular, the intended equivalence between the “QRAM model” and the “quantum circuit-model” of quantum computation is just the hom-isomorphism of the linear internal hom-adjunction
The terminology “quantum random access memory” is due to
Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone, Quantum random access memory, Phys. Rev. Lett. 100 160501 (2008) [doi:10.1103/PhysRevLett.100.160501, arXiv:0708.1879]
Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone, Architectures for a quantum random access memory, Phys. Rev. A 78 052310 (2008) [doi:10.1103/PhysRevA.78.052310, arXiv:0807.4994]
but it could be argued (?) that the notion is implicit already in Knill (1996).
Further development:
S. Arunachalam et al., On the robustness of bucket brigade quantum RAM, New Journal of Physics, 17 12 (2015) 123010 [arXiv:1502.03450, doi:10.1088/1367-2630/17/12/123010]
Park, Petruccione, Rhee, Circuit-Based Quantum Random Access Memory for Classical Data, Scientific Reports 9 3949 (2019) [doi:10.1038/s41598-019-40439-3]
Review:
Alessandro Luongo, The QRAM, §3.1.1. in: Quantum algorithms for data analysis
Koustubh Phalak, Avimita Chatterjee, Swaroop Ghosh, Quantum Random Access Memory For Dummies [arXiv:2305.01178]
Samuel Jaques, Arthur G. Rattew, QRAM: A Survey and Critique [arXiv:2305.10310]
With Qiskit:
Last revised on August 16, 2023 at 12:48:48. See the history of this page for a list of all contributions to it.