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 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 Bool, 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 QBit, 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
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.