nLab QRAM

Contents

This entry is about QRAM in the sense of Giovanetti et al. 2008. For the other sense of classically controlled quantum computation see there.


Context

Quantum systems

quantum logic


quantum physics


quantum probability theoryobservables and states


quantum information


quantum computation

qbit

quantum algorithms:


quantum sensing


quantum communication

Computation

Contents

Idea

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)).

Circuit model

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 QMemQMem

with a a quantum circuit of type

QMemQMem. QMem \otimes \mathscr{H} \longrightarrow QMem \otimes \mathscr{H} \,.

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 “QMemQMem”, the rest is our \mathscr{H}.)

This quantum circuit is such that (assuming q 2==q 6=0q_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 10q_{10}.

  • for a superposition of these inputs it yields the corresponding superposition of outputs.

Via linear state-effects

Recall that a classical random access memory of data type MemMem is modeled (in terms of monads in computer science) by the state monad induced from the cartesian internal hom-adjunction

  • product\; Mem×()Maps(Mem,)Mem \times (-) \;\;\dashv\;\; Maps(Mem, -) \;function set

namely:

RAM(Mem,A)Maps(Mem,Mem×A). RAM(Mem,A) \;\coloneqq\; Maps \big( Mem ,\, Mem \times A \big) \,.

(Notice that in concrete applications people often insist that Mem=Mem = Bool × n{}^{\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

QRAM(Mem,)LinMaps(QMem,QMem) QRAM(Mem, \mathscr{H}) \;\coloneqq\; LinMaps \big( QMem ,\, QMem \otimes \mathscr{H} \big)

and it seems clear that this does correspond to the intended behaviour of QRAM (where we are free to set QMemQMem \coloneqq QBit n{}^{\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

{InLinMaps(QMem,QMemOut)}{InQMemOutQMem}. \Big\{ In \longrightarrow LinMaps \big( QMem ,\, QMem \otimes Out \big) \Big\} \;\;\;\;\;\;\; \leftrightarrow \;\;\;\;\;\;\; \Big\{ In \otimes QMem \longrightarrow Out \otimes QMem \Big\} \,.

References

The terminology “quantum random access memory” is due to

Further development:

Review:

With emhasis on laboratory realization:

  • Chenxu Liu, et al., III.C (pp. 18) of: Quantum Memory: A Missing Piece in Quantum Computing Units [arXiv:2309.14432]

  • Samuel Jaques, Arthur G. Rattew, QRAM: A Survey and Critique [arXiv:2305.10310]

With Qiskit:

Last revised on May 27, 2024 at 12:45:08. See the history of this page for a list of all contributions to it.