Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2002.09340 · Physical Review A

Parallelizing the queries in a bucket-brigade quantum random access memory

Alexandru Paler, Oumarou Oumarou, Robert Basmadjian

Published Sep 8, 2020• 36 citations
arXivHTMLPDF

Abstract

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 $\mathrm{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 $\mathrm{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.

DOI
10.1103/physreva.102.032608

Related papers

Experimental realization of the bucket-brigade quantum random access memory

Shen, Fanhao, Ji, Yujie, Xiang, Debin +20 more

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 $\pm$ 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.

arXiv:2506.16682•Jun 20, 2025•0 citations

Reduction of Resources for a Fault-tolerant qRAM using Pieceable Bucket-Brigade Schemes

Bernard Ousmane Sane, Praveen Balaji, Michal Hajdušek +2 more

Quantum random access memory (qRAM) is valuable for applying quantum computers to a broad range of problems and for successfully implementing large-scale quantum computation systems. Despite its importance, its adoption may be restricted by the fact that the decomposition of the qRAM function contains non-transversal gates, which cannot be executed transversally on any quantum error correction (QEC) code. To overcome these limitations, existing works employ techniques like magic state distillation. However, distillation is time-and qubit-intensive. This paper presents a fault-tolerant, resource-efficient implementation of qRAM based on pieceable fault tolerance. By breaking the logical CSWAP and Toffoli gate into simpler, easier-to-execute but non-transversal components, we first show that bucket-brigade qRAM can be implemented in polynomial depth without the need for ancillary magic states, further gate decomposition, or other gates. Afterward, we demonstrate the resource efficiency of this method of attaining fault tolerance in quantum operations. Based on resource estimation results, fault-tolerant bucket brigades using the pieceable technique perform better than fault-tolerant bucket brigades using magic state distillation with respect to the number of physical qubits, time, and cost.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•0 citations

A quantum random access memory (QRAM) using a polynomial encoding of binary strings

Priyanka Mukhopadhyay

Quantum algorithms claim significant speedup over their classical counterparts for solving many problems. An important aspect of many of these algorithms is the existence of a quantum oracle, which needs to be implemented efficiently in order to realize the claimed advantages in practice. A quantum random access memory (QRAM) is a promising architecture for realizing these oracles. In this paper we develop a new design for QRAM and implement it with Clifford+T circuit. We focus on optimizing the T-count and T-depth since non-Clifford gates are the most expensive to implement fault-tolerantly in most error correction schemes. Integral to our design is a polynomial encoding of bit strings and so we refer to this design as [Formula: see text]. Compared to the previous state-of-the-art bucket brigade architecture for QRAM, we achieve an exponential improvement in T-depth, while reducing T-count and keeping the qubit-count same. Specifically, if N is the number of memory locations to be queried, then [Formula: see text] has T-depth [Formula: see text], T-count [Formula: see text] and uses O(N) logical qubits, while the bucket brigade circuit has T-depth [Formula: see text], T-count O(N) and uses O(N) qubits. Combining two [Formula: see text] we design a quantum look-up-table, [Formula: see text], that has T-depth [Formula: see text], T-count [Formula: see text] and qubit count [Formula: see text]. A quantum look-up table (qLUT) or quantum read-only memory (QROM) has restricted functionality than a QRAM. For example, it cannot write into a memory location and the circuit needs to be compiled each time the contents of the memory change. The previous state-of-the-art CSWAP architecture has T-depth [Formula: see text], T-count [Formula: see text] and qubit count [Formula: see text]. Thus we achieve a double exponential improvement in T-depth while keeping the T-count and qubit-count asymptotically same. Additionally, with our polynomial encoding of bit strings, we develop a method to optimize the Toffoli-count of circuits, specially those consisting of multi-controlled-NOT gates.

arXiv:2408.16794•Scientific Reports•Mar 31, 2025•4 citations

Resilience of Quantum Random Access Memory to Generic Noise

Connor T. Hann, Gideon Lee, S. M. Girvin +1 more

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.

arXiv:2012.05340•PRX Quantum•Apr 29, 2021•69 citations

Resilience of Quantum Random Access Memory to Generic Noise

Connor T. Hann, Gideon Lee, S. M. Girvin +1 more

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.

•Apr 29, 2021•56 citations

Error-Corrected QRAM Queries with One-Fault-Tolerant \texttt{CSWAP} Gates

Shifan Xu, Connor T. Hann, Nathan Wiebe +2 more

Quantum random-access memory (QRAM) enables coherent queries to classical data. However, the \(O(N)\) qubits required for a memory with \(N=2^n\) addresses make QRAM appear vulnerable to noise. Though bucket-brigade routing provides intrinsic noise resilience to reduce the error in QRAM, improving the fidelity of QRAM queries is still an important and challenging problem. We introduce a low-overhead protection framework for bucket-brigade QRAM with two complementary components. First, we propose a one-fault-tolerant repeat-until-success logical controlled-SWAP gate using the \([[4,2,2]]\) code under erasure noise channel. Interleaved erasure checks and local recovery correct every single erasure, so the leading logical failure probability is second order in the physical erasure error rates. Second, we exploit validity constraints of bucket-brigade routing to define local parity checks directly on the router states, without adding extra data qubits to create code redundancy. Under bit-flip noise, minimum-weight perfect matching with noiseless syndrome measurements corrects single interior faults, while open spatial boundaries retain a first-order contribution in the residual bit-flip rate. Monte Carlo simulations confirm quadratic suppression for the protected controlled-SWAP and improved depth scaling for decoded QRAM router-state snapshots. The two codes admit a concatenated realization in which the inner code supplies erasure protection and the outer code optionally corrects interior logical bit flips. Together, these results show how routing constraints and a protected non-Clifford routing gate can improve QRAM reliability under biased and erasure-dominant noise.

quant-pharXiv:2610.17185•Oct 13, 2026•0 citations
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\mathrm{Clifford}+TClifford+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\mathrm{Clifford}+TClifford+T gates, and after addresses have been translated, we achieve theoretical O(1)O(1)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 ±\pm± 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.
Quantum random access memory (qRAM) is valuable for applying quantum computers to a broad range of problems and for successfully implementing large-scale quantum computation systems. Despite its importance, its adoption may be restricted by the fact that the decomposition of the qRAM function contains non-transversal gates, which cannot be executed transversally on any quantum error correction (QEC) code. To overcome these limitations, existing works employ techniques like magic state distillation. However, distillation is time-and qubit-intensive. This paper presents a fault-tolerant, resource-efficient implementation of qRAM based on pieceable fault tolerance. By breaking the logical CSWAP and Toffoli gate into simpler, easier-to-execute but non-transversal components, we first show that bucket-brigade qRAM can be implemented in polynomial depth without the need for ancillary magic states, further gate decomposition, or other gates. Afterward, we demonstrate the resource efficiency of this method of attaining fault tolerance in quantum operations. Based on resource estimation results, fault-tolerant bucket brigades using the pieceable technique perform better than fault-tolerant bucket brigades using magic state distillation with respect to the number of physical qubits, time, and cost.
Quantum algorithms claim significant speedup over their classical counterparts for solving many problems. An important aspect of many of these algorithms is the existence of a quantum oracle, which needs to be implemented efficiently in order to realize the claimed advantages in practice. A quantum random access memory (QRAM) is a promising architecture for realizing these oracles. In this paper we develop a new design for QRAM and implement it with Clifford+T circuit. We focus on optimizing the T-count and T-depth since non-Clifford gates are the most expensive to implement fault-tolerantly in most error correction schemes. Integral to our design is a polynomial encoding of bit strings and so we refer to this design as [Formula: see text]. Compared to the previous state-of-the-art bucket brigade architecture for QRAM, we achieve an exponential improvement in T-depth, while reducing T-count and keeping the qubit-count same. Specifically, if N is the number of memory locations to be queried, then [Formula: see text] has T-depth [Formula: see text], T-count [Formula: see text] and uses O(N) logical qubits, while the bucket brigade circuit has T-depth [Formula: see text], T-count O(N) and uses O(N) qubits. Combining two [Formula: see text] we design a quantum look-up-table, [Formula: see text], that has T-depth [Formula: see text], T-count [Formula: see text] and qubit count [Formula: see text]. A quantum look-up table (qLUT) or quantum read-only memory (QROM) has restricted functionality than a QRAM. For example, it cannot write into a memory location and the circuit needs to be compiled each time the contents of the memory change. The previous state-of-the-art CSWAP architecture has T-depth [Formula: see text], T-count [Formula: see text] and qubit count [Formula: see text]. Thus we achieve a double exponential improvement in T-depth while keeping the T-count and qubit-count asymptotically same. Additionally, with our polynomial encoding of bit strings, we develop a method to optimize the Toffoli-count of circuits, specially those consisting of multi-controlled-NOT gates.
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 random-access memory (QRAM) enables coherent queries to classical data. However, the O(N)O(N)O(N) qubits required for a memory with N=2nN=2^nN=2n addresses make QRAM appear vulnerable to noise. Though bucket-brigade routing provides intrinsic noise resilience to reduce the error in QRAM, improving the fidelity of QRAM queries is still an important and challenging problem. We introduce a low-overhead protection framework for bucket-brigade QRAM with two complementary components. First, we propose a one-fault-tolerant repeat-until-success logical controlled-SWAP gate using the [[4,2,2]][[4,2,2]][[4,2,2]] code under erasure noise channel. Interleaved erasure checks and local recovery correct every single erasure, so the leading logical failure probability is second order in the physical erasure error rates. Second, we exploit validity constraints of bucket-brigade routing to define local parity checks directly on the router states, without adding extra data qubits to create code redundancy. Under bit-flip noise, minimum-weight perfect matching with noiseless syndrome measurements corrects single interior faults, while open spatial boundaries retain a first-order contribution in the residual bit-flip rate. Monte Carlo simulations confirm quadratic suppression for the protected controlled-SWAP and improved depth scaling for decoded QRAM router-state snapshots. The two codes admit a concatenated realization in which the inner code supplies erasure protection and the outer code optionally corrects interior logical bit flips. Together, these results show how routing constraints and a protected non-Clifford routing gate can improve QRAM reliability under biased and erasure-dominant noise.