On the robustness of bucket brigade quantum RAM

We study the robustness of the bucket brigade quantum random access memory model introduced by Giovannetti, Lloyd, and Maccone [Phys. Rev. Lett. 100, 160501 (2008)]. Due to a result of Regev and Schiff [ICALP \'08 pp. 773], we show that for a class of error models the error rate per gate in the bucket brigade quantum memory has to be of order O(2^n/2) (where N=2^n is the size of the memory) whenever the memory is used as a oracle for the quantum searching problem. We conjecture that this is the case for any realistic error model that will be encountered in practice, and that for algorithms with super-polynomially many oracle queries the error rate must be super-polynomially small, which further motivates the need for quantum error correction. We introduce a circuit model for the quantum bucket brigade architecture and argue that quantum error correction for the circuit causes the quantum bucket brigade architecture to lose its primary advantage of a small number of \"active\" gates, since all components have to be actively error corrected.