QRAM

Theory

Qram binary tree or a bifurcation graph.

The direct implementation of classical binary tree (using transistors) is rather impractical, as the exponential number of transistors is needed.

Bucket Brigade implementation.

The address and output registers of QRAM are composed of qubits instead of bits, though the memory array can be either quantum or classical.

Address register $a$: superposition $\sum _{i}\alpha _{i}|i\rangle _{a}$.

Data register $d$ with $D_{i}$ being the content of $i$th memory cell. QRAM is the operation $\sum _{i}\alpha _{i}|i\rangle _{a}\to \sum _{i}\alpha _{i}|i\rangle _{a}|D_{i}\rangle _{d}$.

Example

Store the data array $[1,2,5,7]=[1,10,101,111]_{2}$ into a Qram addresses $[0,1]$. Address register is $\sum _{i=0}^{1}\alpha _{i}|i\rangle _{a}=\alpha _{0}|0\rangle _{a}+\alpha _{1}|1\rangle _{a}$.

References

https://arxiv.org/pdf/0708.1879.pdf

https://arxiv.org/pdf/2006.11761.pdf

https://github.com/qsharp-community/qram Nice animation.

https://www.cs.umd.edu/class/fall2019/cmsc657/projects/group_11.pdf