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 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 $Mem$ is modeled (in terms of monads in computer science) by the state monad induced from the *cartesian* internal hom-adjunction

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

namely:

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

(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

- tensor product$\;$ $QMem \otimes (-) \;\;\dashv\;\; LinMaps(QMem, - )$ $\;$linear space-of-linear maps

and the corresponding monad is

$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 $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

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

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]

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

Further development:

- 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]

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