We see a future where we efficiently utilize quantum properties for machine learning and pattern recognition, anticipating quantum computers to revolutionize the field of artificial intelligence. However, most of these quantum algorithms are devised assuming that we already have a quantum equivalent of classical RAM, which, in reality, still has not been constructed yet. In this article, we will dive into what quantum RAM is, how it contrasts with its classical counterpart, and why we need it. Moreover, we will explore a proposed model of quantum RAM along with its limitations.
What is Quantum RAM?
For computation not entirely based on the current input, we need an easily accessible memory device. This memory device should be readable (data can be fetched from the storage base) and writable (we can assign and reset values as per necessity). It acts as a relay between processor and data-store. For classical computers this job is carried out by Random Access Memory: aka. "RAM." RAM consists of three main components: input register, output register and memory cells. The input register is often termed an address register. A memory cell is the fundamental unit of computer memory and multiple memory cells form the memory. The input and output registers take entry and read out the corresponding data retrieved from the memory array, respectively.
As for quantum computers, we need a quantum mechanical version of RAM that would retrieve the data from the storage base not as bit-strings but as states. Thus, the input and output register in Quantum-RAM is qubits instead of bits. These qubits fetch a superposition of data ready to be used in quantum algorithms. The memory array can either be quantum or classical in nature depending on the application.
In general, there are two types of algorithms that require quantum RAM: the data is classical in nature and for the other, the data is inherently quantum in nature (for example: quantum chemistry simulation).
Why do we need a qRAM?
The algorithmic speed-up that is achieved exclusively in quantum algorithms is the implication of entanglement and superposition of qubits. So, quantum devices compute by operating on states of qubits rather than bits of either 0s or 1s. When we want to work with data, whether classical or quantum in nature, they need to be encoded in the form of states of qubits. This allows them to be processed in a quantum machine,. For instance, for analyzing data in quantum machine learning, the data needs to be pre-processed and mapped to any quantum property. Then, by a RAM-call, the superposition of data is retrieved for operation. In technical terms, the data register (output) will return a superposition of memory cells in the address register (input). And thus instead of bits, the data register and address register in qRAMs need to be qubits. The following theoretical framework provides a conceptual architecture for constructing a quantum RAM:
Bucket-Brigade Architecture
Suppose, we have N=2^n memory cells arranged at the end of the following bifurcation graph, where n is the number of levels:
The value of the address register can be interpreted as the route to follow throughout the whole graph that leads to a unique memory cell. N different routes corresponds to 2^n memory cells. The binary address register is a bit-string of n bits where for '0' left path must be followed and right for '1'. For instance, for an address register of '010', the left path will be followed at first level, right and again left for second and third level respectively. A quantum scheme of the architecture would have quantum control lines where n qubits in the address register coherently controls an entire level. There are switches (logic gates) that shunt to left or right for states |0> or |1> respectively. The connected superposition of the address is entangled with a set of switches that find a superposition of routes through the graph. A signal, Quantum Bus, is sent from the root node and it follows the superposition of routes line quantum particles. The state of the Bus is changed according to the quantum information of the memory cells with an n qubit operation of CNOT gate. The bus then comes back following the same route and according to the RAM call, it fetches the superposition quantum information as output.
This model was first introduced by Vittorio Giovannetti, et al. in the year 2007.
Implications of Bucket-Brigade Scheme in quantum RAM
For constructing a qRAM based on this scheme, the number of transistors needed for logic operation grows exponentially for each level. However, if O(N) logic gates are replaced with a three level memory unit (e.g, a qutrit) with three possible quantum states: |left>, |right> and |wait>, the number of active gates reduces exponentially- from O(N) to O(log^2(N)). Because, all of the switches will be initialized to "wait" state and only the corresponding transistor of the address register will be active. This computational advantage in theory, however, is not enough to construct an experimental quantum RAM. Here each gate is entangled and thus has a high decoherence rate, whereas, search algorithms like Grover's search will not be possible without an error free quantum RAM making it extremely hard to materialize. Again, which hardware framework would be the most suitable is an open question.
Quantum RAM is vital for advanced algorithms to solve harder problems. There are a few theories with no physical implementation. All these make qRAM an active field of research. Two practical frameworks have been recently proposed: Josephson arrays and Optical Lattices, but had not yet been devised. Some experts are optimistic about a hybrid model of superconducting and spin qubit.
