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:2609.34935

Classical simulation of amplitude-damped bucket-brigade quantum random access memories via predictable branch evolution

Zhao-Yun Chen, Ming-Yang Tan, Sheng Zhang, Peng Wang, Yun-Jie Wang, Guo-Ping Guo

quant-phSubmitted Sep 28, 2026• Announced Sep 29, 2026• 0 citations
arXivHTMLPDF

Abstract

Classical simulation of quantum random access memory (QRAM) under noise can be accelerated dramatically by branch pruning: noise histories are sampled as trajectory ensembles, and good branches, whose routing paths avoid every sampled fault, need not be evolved because their final states are analytically predictable. Under amplitude damping this predictability is not automatic, because the no-jump operator $K_0$ acts on every branch at every time slice. Here we give a complete account of damping-channel predictability in bucket-brigade QRAM simulation, for both qutrit and qubit encodings. For the qutrit encoding, $K_0$ is diagonal in the node basis, and the wait state $|W\rangle$ is its fixed point, so a good branch follows the noiseless orbit up to a scalar attenuation. In the qubit encoding, phase-kickback memory fetching between two Hadamard walls makes $K_0$ no longer diagonal, yet the resulting structure is exactly solvable in closed form. Conditional on no jump, the in-branch infidelity of a good branch is second order in the damping rate $γ$, with coherent leakage $\sim n^2γ^2/4$ per data qubit, and the closed form captures it without approximation. We also revise the pruning criterion for the qubit encoding. The resulting algorithm evolves only the bad branches plus one reference branch and shares every other cost with the full evolution it replaces. It is validated by end-to-end benchmarks with pruned-over-full speedups up to $285\times$ and by trajectory-level tests confirming every closed form to machine precision.

AI Summary

The paper asks when branch pruning remains exact for classical trajectory simulation of noisy bucket-brigade QRAM under amplitude damping. Pruning replaces branches unaffected by sampled faults with analytic predictions, but the no-jump operator acts everywhere, and qubit-encoded fetching transports data between Hadamard walls. For qutrit encoding, diagonal no-jump damping preserves each good branch’s basis-state orbit and contributes a schedule-computable scalar attenuation. For qubit encoding, the paper derives an exact wall-to-wall map: each data qubit experiences $2n$ damping layers and has ideal-output and flipped-output amplitudes $[1\pm(1-\gamma)^n]/2$. The multi-qubit output factors, giving conditional no-jump infidelity $n^2\gamma^2/4+O(\gamma^3)$ per data qubit. It also revises fault marking to account for excitations migrating through idle qubit routers, yielding an expected bad-branch count $O(n^3p)D$, and proves an exact joint Kraus-outcome sampler. The simulator evolves bad branches plus one reference branch. Benchmarks through $n=12$, with three data qubits, report up to $285\times$ speedup at zero noise and $10$–$21\times$ at $\varepsilon=\gamma=10^{-5}$; gains approach unity at $10^{-3}$. Validation includes 1,000 paired full/pruned trajectories, 644 single-fault injections, closed-form checks to floating-point precision, and a nine-qubit density-matrix cross-check. The established input class allows coherent address superpositions with one computational-basis bus-input column per address, not general coherent superpositions across bus columns. No general multi-fault theorem is claimed for the marking rule. Tree-wide noise sampling, classical-memory storage, and output costs remain shared with full simulation.

Some signs of AI-generated textIncrementalStrong assumptionsOverclaims

Central claim may not hold: The abstract omits that exact simulation is established only for inputs containing one computational-basis bus word per address, not general coherent QRAM inputs. The good-branch theorem uses routing-path avoidance where its shared-tree conclusion requires exclusion from the larger family-divergence bad-address union. The reported fidelity and verification scans include coherent multi-column inputs whose damping statistics are not reproduced by the simulator's explicitly incoherent input-column bookkeeping.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
16 pages, 6 figures, 5 tables

Related papers

Efficient Quantum State Preparation with Bucket Brigade QRAM

Alessandro Berti, Francesco Ghisoni

The preparation of data in quantum states is a critical component in the design of quantum algorithms. The cost of this step can significantly limit the realization of quantum advantage in domains such as machine learning, finance, and chemistry. One of the main approaches to achieve efficient state preparation is through the use of Quantum Random Access Memory (QRAM), a theoretical device for coherent data access with several proposed hardware implementations. In this work, we present a framework that integrates the hardware model of the Bucket Brigade QRAM (BBQRAM) with the classical data structure of the Segment Tree to achieve efficient state preparation. We introduce a memory layout that embeds a segment tree within BBQRAM memory cells by preserving the segment tree's hierarchy and supporting data retrieval in logarithmic time via specialized access primitives. We demonstrate that our method encodes a matrix $A \in \mathbb{R}^{M \times N}$ in a quantum register of $Θ(\log_2(MN))$ qubits in $\mathcal{O}(\log_2^2(MN))$ time, {requiring a constant number of working qubits (under fixed precision) and $\mathcal{O}(MN)$ memory cells within the BBQRAM architecture.} We further illustrate the method through a numerical example. This framework provides theoretical support for quantum algorithms that assume negligible data loading overhead and establishes a foundation for designing classical-to-quantum encoding algorithms that are aware of the underlying hardware QRAM architecture.

arXiv:2510.16149•Oct 17, 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.

•Apr 29, 2021•57 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•95 citations

Efficient Complex-Valued State Preparation on Bucket Brigade QRAM

Alessandro Berti, Francesco Ghisoni

Efficient quantum state preparation is a critical component in quantum algorithms that process large classical data, and it is fundamental to realizing quantum advantage in domains such as machine learning, quantum linear algebra, and quantum finance. Building on the framework of~\cite{berti2025efficient}, which integrates Bucket Brigade QRAM (BBQRAM) with a segment tree to achieve amplitude encoding in polylogarithmic query time, we present two improvements within the same architecture-aware framework. First, we remove the $U_{2\mathrm{CR}}$ subroutine by classically precomputing the rotation angles determined by the segment tree and storing these angles directly in the BBQRAM cells. The tradeoff is that the classically loaded QRAM stores precomputed fixed-point angles rather than raw subtree weights. Second, we extend the construction to complex-valued matrices $A \in \mathbb{C}^{M \times N}$ by storing a leaf phase alongside each precomputed rotation angle and using a two-step magnitude-then-phase procedure; the real signed case is naturally subsumed as a one-bit phase specialization. At unchanged $\mathcal{O}(\log_2^2(MN))$ BBQRAM query complexity, the QPU procedure reduces to BBQRAM retrievals and controlled-rotation cascades, with $\mathcal{O}(MN)$ memory cells per matrix and no reversible arithmetic on the QPU.

quant-pharXiv:2604.25644•Apr 29, 2026•0 citations

Refined criteria for quantum random-access memory error suppression via an efficient large-scale simulator

Yun-Jie Wang, Tai‐Ping Sun, Xi‐Ning Zhuang +6 more

Quantum random access memory (QRAM) is a critical primitive for quantum algorithms that require data lookup in superposition, but its lack of fault tolerance poses a major obstacle to practical deployment. Error filtration (EF) has been proposed as a hardware-efficient alternative to error correction, capable of suppressing incoherent noise without encoding overhead. However, its performance in realistic QRAM systems with moderate fidelity has remained unclear, as existing analyses rely on asymptotic approximations and numerical simulations have been limited to small sizes. We address this gap using a new simulator for bucket-brigade (BB) QRAM that combines sparse state encoding with a noise-aware pruning algorithm. This framework provides full quantum state access and scales efficiently, enabling us to probe EF performance in size and noise regimes far beyond previous studies. Our simulations reveal suppression anomalies at high noise levels or large address sizes, where post-selection probability fundamentally constrains EF scaling. Incorporating this effect, we refine EF theory into near-deterministic criteria linking base infidelity to achievable suppression, thereby delineating the regime in which EF yields progressive improvement. Beyond refining EF, we quantitatively characterize the runtime and memory costs of our noisy BB QRAM simulator, achieving simulations of systems with 20 layers using less than 1 GB of memory. This efficiency is what enables us to probe parameter regimes beyond previous work and to establish the simulator as a practical, ``fine-print'' analysis tool for assessing QRAM as a quantum resource.

arXiv:2503.13832•Physical Review Applied•Mar 24, 2026•3 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
Classical simulation of quantum random access memory (QRAM) under noise can be accelerated dramatically by branch pruning: noise histories are sampled as trajectory ensembles, and good branches, whose routing paths avoid every sampled fault, need not be evolved because their final states are analytically predictable. Under amplitude damping this predictability is not automatic, because the no-jump operator K0K_0K0​ acts on every branch at every time slice. Here we give a complete account of damping-channel predictability in bucket-brigade QRAM simulation, for both qutrit and qubit encodings. For the qutrit encoding, K0K_0K0​ is diagonal in the node basis, and the wait state ∣W⟩|W\rangle∣W⟩ is its fixed point, so a good branch follows the noiseless orbit up to a scalar attenuation. In the qubit encoding, phase-kickback memory fetching between two Hadamard walls makes K0K_0K0​ no longer diagonal, yet the resulting structure is exactly solvable in closed form. Conditional on no jump, the in-branch infidelity of a good branch is second order in the damping rate γγγ, with coherent leakage ∼n2γ2/4\sim n^2γ^2/4∼n2γ2/4 per data qubit, and the closed form captures it without approximation. We also revise the pruning criterion for the qubit encoding. The resulting algorithm evolves only the bad branches plus one reference branch and shares every other cost with the full evolution it replaces. It is validated by end-to-end benchmarks with pruned-over-full speedups up to 285×285\times285× and by trajectory-level tests confirming every closed form to machine precision.
The paper asks when branch pruning remains exact for classical trajectory simulation of noisy bucket-brigade QRAM under amplitude damping. Pruning replaces branches unaffected by sampled faults with analytic predictions, but the no-jump operator acts everywhere, and qubit-encoded fetching transports data between Hadamard walls.
For qutrit encoding, diagonal no-jump damping preserves each good branch’s basis-state orbit and contributes a schedule-computable scalar attenuation. For qubit encoding, the paper derives an exact wall-to-wall map: each data qubit experiences 2n2n2n damping layers and has ideal-output and flipped-output amplitudes [1±(1−γ)n]/2[1\pm(1-\gamma)^n]/2[1±(1−γ)n]/2. The multi-qubit output factors, giving conditional no-jump infidelity n2γ2/4+O(γ3)n^2\gamma^2/4+O(\gamma^3)n2γ2/4+O(γ3) per data qubit. It also revises fault marking to account for excitations migrating through idle qubit routers, yielding an expected bad-branch count O(n3p)DO(n^3p)DO(n3p)D, and proves an exact joint Kraus-outcome sampler.
The simulator evolves bad branches plus one reference branch. Benchmarks through n=12n=12n=12, with three data qubits, report up to 285×285\times285× speedup at zero noise and 101010–21×21\times21× at ε=γ=10−5\varepsilon=\gamma=10^{-5}ε=γ=10−5; gains approach unity at 10−310^{-3}10−3. Validation includes 1,000 paired full/pruned trajectories, 644 single-fault injections, closed-form checks to floating-point precision, and a nine-qubit density-matrix cross-check.
The established input class allows coherent address superpositions with one computational-basis bus-input column per address, not general coherent superpositions across bus columns. No general multi-fault theorem is claimed for the marking rule. Tree-wide noise sampling, classical-memory storage, and output costs remain shared with full simulation.
The preparation of data in quantum states is a critical component in the design of quantum algorithms. The cost of this step can significantly limit the realization of quantum advantage in domains such as machine learning, finance, and chemistry. One of the main approaches to achieve efficient state preparation is through the use of Quantum Random Access Memory (QRAM), a theoretical device for coherent data access with several proposed hardware implementations. In this work, we present a framework that integrates the hardware model of the Bucket Brigade QRAM (BBQRAM) with the classical data structure of the Segment Tree to achieve efficient state preparation. We introduce a memory layout that embeds a segment tree within BBQRAM memory cells by preserving the segment tree's hierarchy and supporting data retrieval in logarithmic time via specialized access primitives. We demonstrate that our method encodes a matrix A∈RM×NA \in \mathbb{R}^{M \times N}A∈RM×N in a quantum register of Θ(log⁡2(MN))Θ(\log_2(MN))Θ(log2​(MN)) qubits in O(log⁡22(MN))\mathcal{O}(\log_2^2(MN))O(log22​(MN)) time, {requiring a constant number of working qubits (under fixed precision) and O(MN)\mathcal{O}(MN)O(MN) memory cells within the BBQRAM architecture.} We further illustrate the method through a numerical example. This framework provides theoretical support for quantum algorithms that assume negligible data loading overhead and establishes a foundation for designing classical-to-quantum encoding algorithms that are aware of the underlying hardware QRAM architecture.
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.
Efficient quantum state preparation is a critical component in quantum algorithms that process large classical data, and it is fundamental to realizing quantum advantage in domains such as machine learning, quantum linear algebra, and quantum finance. Building on the framework of~\cite{berti2025efficient}, which integrates Bucket Brigade QRAM (BBQRAM) with a segment tree to achieve amplitude encoding in polylogarithmic query time, we present two improvements within the same architecture-aware framework. First, we remove the U2CRU_{2\mathrm{CR}}U2CR​ subroutine by classically precomputing the rotation angles determined by the segment tree and storing these angles directly in the BBQRAM cells. The tradeoff is that the classically loaded QRAM stores precomputed fixed-point angles rather than raw subtree weights. Second, we extend the construction to complex-valued matrices A∈CM×NA \in \mathbb{C}^{M \times N}A∈CM×N by storing a leaf phase alongside each precomputed rotation angle and using a two-step magnitude-then-phase procedure; the real signed case is naturally subsumed as a one-bit phase specialization. At unchanged O(log⁡22(MN))\mathcal{O}(\log_2^2(MN))O(log22​(MN)) BBQRAM query complexity, the QPU procedure reduces to BBQRAM retrievals and controlled-rotation cascades, with O(MN)\mathcal{O}(MN)O(MN) memory cells per matrix and no reversible arithmetic on the QPU.
Quantum random access memory (QRAM) is a critical primitive for quantum algorithms that require data lookup in superposition, but its lack of fault tolerance poses a major obstacle to practical deployment. Error filtration (EF) has been proposed as a hardware-efficient alternative to error correction, capable of suppressing incoherent noise without encoding overhead. However, its performance in realistic QRAM systems with moderate fidelity has remained unclear, as existing analyses rely on asymptotic approximations and numerical simulations have been limited to small sizes. We address this gap using a new simulator for bucket-brigade (BB) QRAM that combines sparse state encoding with a noise-aware pruning algorithm. This framework provides full quantum state access and scales efficiently, enabling us to probe EF performance in size and noise regimes far beyond previous studies. Our simulations reveal suppression anomalies at high noise levels or large address sizes, where post-selection probability fundamentally constrains EF scaling. Incorporating this effect, we refine EF theory into near-deterministic criteria linking base infidelity to achievable suppression, thereby delineating the regime in which EF yields progressive improvement. Beyond refining EF, we quantitatively characterize the runtime and memory costs of our noisy BB QRAM simulator, achieving simulations of systems with 20 layers using less than 1 GB of memory. This efficiency is what enables us to probe parameter regimes beyond previous work and to establish the simulator as a practical, ``fine-print'' analysis tool for assessing QRAM as a quantum resource.
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.