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
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.
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