nLab QRAM

Contents

Context

Quantum systems

quantum logic


quantum physics


quantum probability theoryobservables and states


quantum information


quantum computation

quantum algorithms:

Computation

Contents

Idea

In quantum computing and quantum information theory, the notion of quantum random access memory (QRAM, due to Giovanettiy, 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 (original and followup) references on QRAM are somewhat vague on the precise intended operational definition. But 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,A)LinMaps(QMem,QMemA) QRAM(Mem,A) \;\coloneqq\; LinMaps \big( QMem ,\, QMem \otimes A \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

but it could be argued (?) that the notion is implicit already in Knill (1996).

Further development:

Created on October 29, 2022 at 15:25:04. See the history of this page for a list of all contributions to it.