A Distillation-Teleportation Protocol for Fault-Tolerant QRAM

Dalzell, Alexander M. and Gilyén, András Pál and Hann, Connor T. and McArdle, Sam and Salton, Grant and Nguyen, Quynh T. and Kubica, Aleksander and Brandão, Fernando G.S.L. (2026) A Distillation-Teleportation Protocol for Fault-Tolerant QRAM. In: 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, Melbourne, pp. 38-74. ISBN 9798331571320

Preview

Text 2505.20265v1.pdf - Published Version Available under License Creative Commons Attribution Share Alike. Download (1MB) | Preview

Abstract

Wepresentaprotocolforfault-tolerantlyimplementingthelogicalquantumrandomaccessmemory (QRAM)operation,givenaccesstoaspecialized,noisyQRAMdevice.Forcoherentlyaccessingclassical memoriesofsize2n,ourprotocolconsumesonlypoly(n)fault-tolerantquantumresources(logicalgates, logicalqubits,quantumerrorcorrectioncycles,etc.),avoidingtheneedtoperformactiveerrorcorrection onallΩ(2n)componentsoftheQRAMdevice.Thisisthefirstrigorousconceptualdemonstrationthata specialized,noisyQRAMdevicecouldbeusefulforimplementingafault-tolerantquantumalgorithm. In fact,thefidelityofthedevicecanbeaslowas1/poly(n).TheprotocolqueriesthenoisyQRAMdevice poly(n) times toprepareasequenceofn-qubitQRAMresourcestates,whicharemovedtoageneralpurposepoly(n)-sizeprocessortobeencodedintoaQECcode,distilled,andfault-tolerantlyteleported intothecomputation.Toaidthisprotocol,wedevelopanewgate-efficientstreamingversionofquantum purityamplificationthatmatchestheoptimal samplecomplexityinawiderangeofparametersandis thereforeof independent interest. Theexponentialreductioninfault-tolerantquantumresourcescomesattheexpenseofanexponentialquantityofpurelyclassicalcomplexity—eachof theniterationsof theprotocol requiresadaptively updatingthe2n-sizeclassicaldatasetandprovidingthenoisyQRAMdevicewithaccesstotheupdated datasetatthenextiteration.WhileourprotocoldemonstratesthatQRAMismorecompatiblewithfaulttolerantquantumcomputationthanpreviouslythought, theneedforsignificantclassicalcomputational complexityexposespotentially fundamental limitations torealizingatrulypoly(n)-cost fault-tolerant QRAM.

Actions (login required)

Edit Item