We study the robustness of the bucket brigade quantum random access memory model introduced by Giovannetti et al (2008 Phys. Rev. Lett. 100 160501 ). Due to a result of Regev and Schiff (ICALP '08 733), 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 (where is the size of the memory) whenever the memory is used as an 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. By contrast, for algorithms such as matrix inversion Harrow et al (2009 Phys. Rev. Lett. 103 150502 ) or quantum machine learning Rebentrost et al (2014 Phys. Rev. Lett. 113 130503 ) that only require a polynomial number of queries, the error rate only needs to be polynomially small and quantum error correction may not be required. 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.
We study the robustness of the bucket brigade quantum random access memory model introduced by Giovannetti et al (2008 Phys. Rev. Lett. 100 160501 ). Due to a result of Regev and Schiff (ICALP '08 733), 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 (where is the size of the memory) whenever the memory is used as an 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. By contrast, for algorithms such as matrix inversion Harrow et al (2009 Phys. Rev. Lett. 103 150502 ) or quantum machine learning Rebentrost et al (2014 Phys. Rev. Lett. 113 130503 ) that only require a polynomial number of queries, the error rate only needs to be polynomially small and quantum error correction may not be required. 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.
We study the robustness of the bucket brigade quantum random access memory model introduced by Giovannetti, Lloyd, and Maccone [Phys. Rev. Lett., 2008]. Due to a result of Regev and Schiff [ICALP, 2008], 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 an 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.
Quantum random access memory (QRAM)—memory which stores classical data but allows queries to be performed in superposition—is required for the implementation of numerous quantum algorithms. While naive implementations of QRAM are highly susceptible to decoherence and hence not scalable, it has been argued that the bucket-brigade QRAM architecture [Giovannetti et al., Phys. Rev. Lett. 100, 160501 (2008)] is highly resilient to noise, with the infidelity of a query scaling only logarithmically with the memory size. In prior analyses, however, this favorable scaling followed directly from the use of contrived noise models, thus leaving open the question of whether experimental implementations would actually enjoy the purported scaling advantage. In this work, we study the effects of decoherence on QRAM in full generality. Our main result is a proof that this favorable infidelity scaling holds for arbitrary error channels (including, e.g., depolarizing noise and coherent errors). Our proof identifies the origin of this noise resilience as the limited entanglement among the memory’s components, and it also reveals that significant architectural simplifications can be made while preserving the noise resilience. We verify these results numerically using a novel classical algorithm for the efficient simulation of noisy QRAM circuits. Our findings indicate that QRAM can be implemented with existing hardware in realistically noisy devices, and that high-fidelity queries are possible without quantum error correction. Furthermore, we also prove that the benefits of the bucket-brigade architecture persist when quantum error correction is used, in which case the scheme offers improved hardware efficiency and resilience to logical errors.
Quantum random access memory (QRAM)-memory which stores classical data but allows queries to be performed in superposition-is required for the implementation of numerous quantum algorithms.While naive implementations of QRAM are highly susceptible to decoherence and hence not scalable, it has been argued that the bucket-brigade QRAM architecture [Giovannetti et al., Phys. Rev. Lett. 100, 160501 (2008)] is highly resilient to noise, with the infidelity of a query scaling only logarithmically with the memory size.In prior analyses, however, this favorable scaling followed directly from the use of contrived noise models, thus leaving open the question of whether experimental implementations would actually enjoy the purported scaling advantage.In this work, we study the effects of decoherence on QRAM in full generality.Our main result is a proof that this favorable infidelity scaling holds for arbitrary error channels (including, e.g., depolarizing noise and coherent errors).Our proof identifies the origin of this noise resilience as the limited entanglement among the memory's components, and it also reveals that significant architectural simplifications can be made while preserving the noise resilience.We verify these results numerically using a novel classical algorithm for the efficient simulation of noisy QRAM circuits.Our findings indicate that QRAM can be implemented with existing hardware in realistically noisy devices, and that high-fidelity queries are possible without quantum error correction.Furthermore, we also prove that the benefits of the bucket-brigade architecture persist when quantum error correction is used, in which case the scheme offers improved hardware efficiency and resilience to logical errors.
Quantum algorithms often use quantum random access memory (QRAM) for accessing information stored in a databaselike manner. QRAM has to be fast, resource efficient, and fault tolerant. The latter is often influenced by access speeds, because shorter times introduce less exposure of the stored information to noise. The total execution time of an algorithm depends on the QRAM access time which includes (i) address translation time and (ii) effective query time. The bucket-brigade QRAM was proposed to achieve faster addressing at the cost of exponentially many ancillas. We illustrate a systematic method to significantly reduce the effective query time by using Clifford+T gate parallelism. The method does not introduce any ancilla qubits. Our parallelization method is compatible with the surface code quantum error correction. We show that parallelization is a result of advantageous Toffoli gate decomposition in terms of Clifford+T gates, and after addresses have been translated, we achieve theoretical O(1) parallelism for the effective queries. We conclude that, in theory, (i) fault-tolerant bucket-brigade quantum RAM queries can be performed approximately with the speed of classical RAM, and (ii) the exponentially many ancillas from the bucket-brigade addressing scheme are a tradeoff cost for achieving exponential query speedup compared to quantum read-only memories whose queries are sequential by design. The methods used to compile, parallelize, and analyze the presented QRAM circuits have been implemented in software which is available online.
Quantum random access memory (QRAM) enables efficient classical data access for quantum computers -- a prerequisite for many quantum algorithms to achieve quantum speedup. Despite various proposals, the experimental realization of QRAM remains largely unexplored. Here, we experimentally investigate the circuit-based bucket-brigade QRAM with a superconducting quantum processor. To facilitate the experimental implementation, we introduce a hardware-efficient gate decomposition scheme for quantum routers, which effectively reduces the depth of the QRAM circuit by more than 30% compared to the conventional controlled-SWAP-based implementation. We further propose an error mitigation method to boost the QRAM query fidelity. With these techniques, we are able to experimentally implement the QRAM architectures with two and three layers, achieving query fidelities up to 0.800 ± 0.026 and 0.604$\pm$0.005, respectively. Additionally, we study the error propagation mechanism and the scalability of our QRAM implementation, providing experimental evidence for the noise resilience nature of the bucket-brigade QRAM architecture. Our results highlight the potential of superconducting quantum processors for realizing a scalable QRAM architecture.
A ``bucket brigade'' architecture for a quantum random memory of N=2n memory cells needs n(n+5)/2 times of quantum manipulation on control circuit nodes per memory call. Here we propose a scheme in which only on average n/2 times manipulations are required to accomplish a memory call. This scheme may significantly decrease the time spent on a memory call and the average overall error rate per memory call. A physical implementation scheme is discussed for storing an arbitrary state in a selected memory cell followed by reading it out.