Are bucket-brigate (q)RAM architectures also advantageous in the classical case?

Question

One of the main ideas introduced in Giovannetti et al. 2007 (0708.1879) is the so-called bucket-brigade (q)RAM architecture.

The authors state (first paragraph, second column, first page, in v2) that this new (at the time) (q)RAM architecture reduces the number of switches that must be thrown during a RAM call, quantum or classical, from $O(N^{1/d})$ to $O(\log N)$, where $N=2^n$ is the number of memory slots in the RAM and $d$ is the dimension of the lattice that, according to the authors, conventional RAM architectures use for memory retrieval.

The conventional architecture they have in mind essentially consists in retrieving the information using a tree structure, like the one they present in their Fig. 1 (here reproduced):

They say that this scheme requires to throw $O(N)$ switches for each memory call, but I don't understand why is this the case. From the above, it would seem that one just needs to throw $O(\log_2(N))$ switches, one per bifurcation, to get from the top to the bottom.

I understand that in the quantum case, with this protocol, we would end up with a state correlated with all of the $N$ switches, but they seem to be stating that even in the classical case one needs to activate them all.

In other words, is the advantage of the bucket-brigade approach only in the higher error resilience in the quantum case, or would it also be classically advantageous, compared with the conventional approaches?

Answer 1

They say that this scheme requires to throw $O(N)$ switches for each memory call, but I don't understand why is this the case. From the above, it would seem that one just needs to throw $O(\log_2(N))$ switches, one per bifurcation, to get from the top to the bottom.

It seems to me that $n= \log_2 N$ is the length of the address register: the number of times that you have to say left or right to reach a given node.

The number of 'switches' is the amount of hardware required to realize the full graph. For the classical case, this means transistors. From the paper:

An electronic implementation requires placing one transistor in each of the two paths following each node in the graph. Each address bit controls all the transistors in one of the graph levels: it activates all the transistors in the left paths if it has value 0, or all the transistors in the right paths if it has value 1

The number of transistors required for the bottom level of the graph is $O(N)$. This then decreases exponentially as you go up the graph. So the total number is also $O(N)$. All are active, since each address bit activates all the transistors in a given level.

In other words, is the advantage of the bucket-brigade approach only in the higher error resilience in the quantum case, or would it also be classically advantageous, compared with the conventional approaches?

I think that it would indeed work in classical RAM, but the hardware constraints didn't supply the 'evolutionary pressure' required for it to be develiped and implemented. The quantum need to hide from errors is the main motivation.

Answer 2

An answer to this question seems to have been given by the same authors, in a different follow-up paper which I hadn't seen before.

In [1], the authors write (emphasis mine):

A classical RAM that uses the bucket-brigade addressing schemes need only activate $O(n)$ transistors in the course of a memory call, in contrast with a conventional RAM that activates $O(2^n)$ transistors. As a result, a RAM that uses our design might operate with less dissipation and power consumption than a conventional RAM. Note, however, that energy costs in the memory addressing are not sufficiently high in current RAM chips to justify an immediate adoption of the bucket-brigade. Other sources of inefficiencies and dissipations are currently predominant (mostly in the memory cells themselves). However, new promising memory cell technologies are being developed (e.g. the “memristor” cells [15]), which would drastically cut back cell dissipation, so that cutting back dissipation in the addressing may become important in the future.

It would therefore seem that, at least according to the authors, the bucket-brigade scheme would be also advantageous for classical architectures, in terms of energy consumption.

[1]: Giovannetti, Lloyd, and Maccone. "Architectures for a quantum random access memory." Physical Review A 78.5 (2008): 052310.