{"id":"50b6bb8d-1d30-4338-95d0-2d023c036487","arxiv_id":"2411.15612","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Faulty QRAM routers can be bypassed with very few flag qubits, recovering a smaller but functioning QRAM.","lead":"This paper presents algorithms for salvaging a working quantum random access memory (QRAM) from a larger QRAM where some routers failed during fabrication. A smart generalist should care because it addresses a practical manufacturing-yield obstacle to building QRAM, a key component for many quantum algorithms.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"IterativeRepair depends at every layer on copying classical data at interior QRAM nodes; if the cited hardware does not support mid-tree data access, the central repair claim is conditional at best.","rationale":"The paper is internally coherent: the faulty-address statistics in Sec. III agree with simulation, the RelabelRepair and IterativeRepair algorithms are clearly specified, the greedy FlagQubitMinimization is explicitly acknowledged to exceed its own ceiling in rare cases, and the code is released. The reader's conditional verdict is appropriate. The single most load-bearing concern is the interior-data-access assumption. It is stated in the paper and supported only by the authors' own Ref. [7], so the broad claim 'a faulty n-bit QRAM with at least 2^(n-1) accessible addresses can be repaired' is not yet established for architectures that store data only at the bottom leaves. This concern does not invalidate the algorithmic contribution; it narrows its claimed scope or requires an additional hardware capability whose cost is not counted. A concrete hardware check or a modified simulation with leaf-only data access would settle whether the resource estimate survives in standard QRAM implementations. I therefore leave the reader's CONDITIONAL verdict unchanged.","tokens_in":19236,"tokens_out":15264,"duration_ms":140542,"concrete_test":"Check the hardware proposal of Ref. [7] (and, if claimed, the other cited QRAM platforms) for mid-tree classical data access: can a bus qubit be routed to an interior router node and have classical data copied into it while that node continues to function as a router? If not, rerun the IterativeRepair simulation with the flag-lookup QRAM restricted to leaf-level data registers or to an externally supplied classical lookup, and measure the resulting hardware or depth overhead; if the overhead changes the asymptotic resource estimate from O(n^2) to O(N) or requires a separate QRAM, the central claim does not generalize to standard leaf-only QRAM architectures.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires a functioning smaller QRAM to compute the flag-qubit rerouting patterns. In IterativeRepair (Sec. IV-B), this smaller QRAM is embedded in the upper levels of the same physical tree, so its leaves are interior nodes of the full n-bit tree. The paper explicitly states: \"this strategy assumes that we can access classical data even in the interior of the QRAM tree, and not just at the leaves. This functionality is supported by QRAM hardware proposals, such as those in Ref. [7].\" This assumption is load-bearing because every repair layer sends flag qubits as bus qubits into the currently functioning k-bit QRAM. If interior data access is unavailable, the flag-qubit lookup cannot be performed on the device, and the repair algorithm reduces to a statement about architectures with mid-tree data registers, not about QRAMs generally. RelabelRepair alone does not require interior access, but IterativeRepair is introduced precisely for cases where RelabelRepair fails, so the headline resource estimate depends on this architectural feature. Ref. [7] is the authors' own hardware proposal, and no independent or hardware-agnostic argument is provided that the other cited QRAM platforms [5], [8], [9], [10] support mid-tree data copy. This is not an internal inconsistency; it is an externally imposed condition that should be verified or explicitly priced into the resource claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper addresses fabrication defects in binary-tree quantum random access memory (QRAM). Assuming a faulty-router table is available and at least 2^(n-1) addresses remain accessible, the authors propose two classical repair strategies: RelabelRepair, which relabels addresses and fixes some routers as one-way streets, and IterativeRepair, which repairs the tree layer by layer using ancilla flag qubits to reroute queries from faulty routers to available spare routers. The paper derives analytic expressions for the expected number of faulty addresses (Eqs. (4) and (7)) and for the unrepairable fraction (Eq. (11)), and validates them with Monte Carlo simulations. For n=13 and a router failure rate of 1%, the headline claim is that on average about 430 addresses need repair while only about 1.5 ancilla flag qubits are required on average. Pseudocode for all algorithms is provided, and the simulation code is released at a public repository.","tokens_in":19424,"tokens_out":22062,"duration_ms":201155,"significance":"If the results hold, this is a useful contribution to the practical problem of improving QRAM fabrication yield. The paper's strengths include a clean analytic faulty-address count based on a Galton-Watson recursion, a semi-analytic unrepairability estimate that agrees well with numerical sampling, explicit pseudocode for all proposed algorithms, Monte Carlo simulations with stated numbers of instances, and a public code release. The result that a small number of flag qubits can reroute many faulty addresses is striking and potentially important for hardware proposals. The main caveats are that the headline flag-qubit numbers are produced by a greedy, not optimal, assignment heuristic, and that IterativeRepair relies on interior-tree classical-data access that is explicitly documented only for the authors' own hardware proposal.","major_comments":[{"comment":"The text states that for n=13 and epsilon=0.01, '857 faulty addresses, thus 429 faulty routers' and that '214 routers need repair.' This inference is not justified by Eq. (7), which counts inaccessible bottom addresses, not faulty routers. A router at depth k renders 2^(n-k+1) addresses inaccessible, so the expected number of faulty routers is not F*_n(epsilon)/2. Moreover, in IterativeRepair, a faulty router whose parent is faulty is never reached and is removed in Algorithm 2, so the number of routers that actually require assignment is the number of 'first' faulty routers on accessible paths, which is substantially smaller than F*_n(epsilon)/2. Please report the actually simulated number of router assignments and correct the abstract and Sec. VI.B accordingly.","section":"VI.B and Eq. (7)"},{"comment":"The IterativeRepair algorithm requires the flag-qubit lookup to access classical data at interior nodes of the QRAM tree, as stated in Sec. IV-B: 'this strategy assumes that we can access classical data even in the interior of the QRAM tree, and not just at the leaves.' The only cited support for this functionality is Ref. [7], the authors' own hardware proposal. Because IterativeRepair is exactly the algorithm used when RelabelRepair fails, the central resource claim is conditional on this architectural feature. Please either provide independent evidence that the other QRAM platforms cited in Sec. II-C support mid-tree data access, or explicitly scope the claims to architectures with interior data registers and explain how the flag-qubit lookup would be performed otherwise.","section":"IV-B"},{"comment":"FlagQubitMinimization is a greedy heuristic, and the paper acknowledges that it can require up to n-1 flag qubits even in cases where n-3 suffice (Sec. VI.B and Fig. 10). The abstract's statement 'we require only 1.5 ancilla flag qubits on average' should therefore be phrased as the number used by the greedy heuristic, not as the minimum required. If the minimal number is intended, please provide an optimality check, for example by comparing the greedy result with an exact integer-programming solution for small instances.","section":"V-B and VI.B"}],"minor_comments":[{"comment":"The description of FlagQubitMinimization says the algorithm chooses the bit-flip pattern that 'assigns the most unique faulty routers to the most unique available routers'; this wording is ambiguous, and the tie-breaking rule should be specified.","section":"Algorithm 3"},{"comment":"The exponent '2n-1-2' in Eq. (11) should be typeset as 2^{n-1}-2 to avoid ambiguity with the text-based rendering.","section":"Eq. (11)"},{"comment":"Fig. 9 shows average flag-qubit counts without error bars; please state whether error bars are omitted for readability or are too small to display.","section":"Fig. 9"},{"comment":"The term 'faulty routers' is used both for physical defective routers and for bottom-layer address pairs that are inaccessible as a consequence of higher-level faults, especially in Sec. VI.B. Please unify this terminology throughout the paper.","section":"General terminology"},{"comment":"Reference [20] lists 'S. Heng' twice; please verify the author list.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The statistical discrepancy in Sec. VI.B should be resolved before publication: the relationship between Eq. (7), the number of faulty routers, and the number of repair assignments in IterativeRepair is not as stated in the text. The interior-data-access assumption also makes the headline claim more architecture-specific than the abstract suggests; the authors should either broaden the evidence or narrow the claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid engineering paper with a genuinely new repair scheme for faulty interior routers in bucket-brigade QRAM. The headline claim—1.5 ancilla flag qubits on average to reroute around ~214 faulty routers at 1% failure rate and depth 13—comes from real Monte Carlo simulation backed by analytic faulty-address counts and released code. The analytics and numerics agree well. The main limitation is not internal: IterativeRepair requires the ability to access classical data at interior nodes of the tree, which the authors state plainly and support only by reference to their own 3D-cavity architecture. If your hardware cannot do mid-tree data access, IterativeRepair won't run, and you're left with RelabelRepair, which fails exponentially often as depth grows. That makes the universal claim conditional, but the paper is honest about it.\n\nWhat's new: prior work by Kim et al. treated faulty memory cells at the leaves; interior router faults are a different and more consequential failure mode. The RelabelRepair one-way-street idea and the flag-qubit bit-flip-pattern minimization are both new. The paper distinguishes the mask strategy from the optimized generating-set strategy and shows the greedy algorithm occasionally overshoots the n-3 ceiling, then fixes it with a linear-independent spanning set. That is careful.\n\nSoft spots: no error bars on the Monte Carlo points, and the O(N^2) observed runtime vs O(N^3 log N) bound is left with a hand-wave about finite-size effects. Both are minor. The larger caveat is the interior data-access assumption, and the paper's own discussion of future hybrid architectures suggests the authors know it is restrictive.\n\nWho it's for: people designing QRAM hardware and systems architects. A serious referee should engage with it. I'd recommend conditional acceptance: the algorithms and resource estimates are valuable; the authors should either supply a hardware-agnostic argument for interior data access or explicitly price its cost in the resource counts.","headline":"A genuinely useful repair scheme for faulty interior QRAM routers, with honest accounting of the assumptions; the headline resource numbers hold up under conditional acceptance.","tokens_in":20035,"tokens_out":1778,"would_cite":true,"duration_ms":16850,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"A defective QRAM can be repaired by rerouting around its broken routers, yielding a working memory of half size with only a handful of extra qubits.","keywords":["quantum random access memory","QRAM","faulty routers","fabrication defects","bucket-brigade architecture","ancilla flag qubits","rerouting","repair algorithm"],"falsifier":"Randomly generate depth-13 trees with 1% per-router failure conditioned on the top three routers being good and on at least $2^{12}$ reachable leaves, run IterativeRepair, and count flag qubits per layer; the central claim is false if a nontrivial fraction of such repairable instances fail to yield a 12-bit QRAM, or if the maximum per-layer flag-qubit count systematically exceeds $n-3$.","tokens_in":18970,"feed_emoji":"🔧","tokens_out":7163,"duration_ms":61852,"temperature":0.7,"pith_summary":"Quantum random access memory (QRAM) is a binary-tree network of routers that lets a quantum computer read classical data at addresses in superposition; a single broken router cuts off every address beneath it. This paper asks whether a chip with fabrication defects can still be used, and answers yes: if the top three routers survive and at least half of the $2^n$ addresses remain reachable, the defective $n$-bit tree can be converted into a working $(n-1)$-bit QRAM by relabelling addresses or by rerouting queries around dead routers layer by layer. The repair uses ancilla flag qubits that detect an incoming query aimed at a faulty router and flip the address qubits to redirect it to a spare working router. The headline quantitative result is that for $n=13$ and a router failure rate of $\\epsilon=1\\%$, the average of about 214 faulty routers on the repairable side can be handled with roughly 1.5 flag qubits. If correct, this means fabrication defects need not be fatal for solid-state QRAM: a partly failed chip can still deliver most of its intended memory with modest overhead and only polylogarithmic query slowdown.","feed_headline":"1.5 repair qubits fix a 13-bit QRAM with 1% bad routers","feed_subtitle":"Layer-by-layer rerouting turns a defective 13-bit tree into a working 12-bit quantum memory.","key_machinery":"The load-bearing objects are the router-based bucket-brigade QRAM tree and the faulty-router table obtained by local quantum process tomography, which immediately implies the faulty-address table. On top of these sit three algorithmic devices: one-way-street relabelling; layer-by-layer self-repair in which the already-repaired upper QRAM routes flag qubits to detect and redirect queries aimed at faulty routers; and a generating-set construction in which each flag qubit applies one address bit-flip pattern and combinations of patterns cover all assignments, drastically reducing the ancilla count. The statistical treatment uses a Galton-Watson branching-process recursion giving the expected faulty-address count $F_n(\\epsilon)=2^n(1-(1-\\epsilon)^n)$ and an exact recursion for the probability that an instance is repairable.","core_discovery":"The paper's central claim is that a repairable faulty QRAM—one with at least $2^{n-1}$ accessible leaves and healthy routers at the top two levels—can be turned into a functioning $(n-1)$-bit QRAM. It establishes this constructively with two algorithms. RelabelRepair treats some routers as one-way streets and relabels surviving addresses as the addresses of a reduced QRAM; when that fails, IterativeRepair grows the working QRAM one layer at a time: at each layer it classically assigns each faulty router on the repairable side to an available router on the spare side, then uses the already-working smaller QRAM to activate ancilla flag qubits that encode the required rerouting, unloads the address qubits, applies the corresponding CNOTs, and reloads them one layer deeper before uncomputing. The flag qubits are reused across layers. A greedy classical algorithm, FlagQubitMinimization, chooses which address bit-flip pattern each flag qubit encodes so that the fewest generating patterns cover all needed reroutings; simulation shows about 1.5 flag qubits suffice on average for the depth-13, 1%-defect case, versus 13 for the naive mask technique.","pith_inferences":["Beyond the paper, the layer-by-layer repair strategy transfers to any binary-tree routing fabric with known bad nodes, such as classical memory repair or photonic and atomic routing networks where a fault table is available.","Because the repair mapping is classical and reused across queries, the per-query cost is dominated by recomputing the flag-qubit CNOT patterns; one could cache assignments and update only when the fault table changes, a dynamic-fault regime the paper does not analyze.","The authors divide the tree into just repairable and spare halves; subdividing into quarters or using more spare partitions is an obvious generalization that should improve the repairable fraction and likely reduce flag-qubit counts further."],"forward_implications":["A fabricated QRAM with a few percent router loss need not be discarded; it can be commissioned as a next-smaller memory with all of its addresses working.","The per-query time of the repaired memory grows from $\\mathcal{O}(n)$ to $\\mathcal{O}(n^2)$, which is still polylogarithmic in the memory size $N=2^n$.","The flag-qubit cost is far below the naive one-flag-per-address-qubit count: for $\\epsilon=1\\%$ and $n=13$, about 1.5 flag qubits on average instead of 13.","Interior router faults, not just bottom-cell faults, are covered; a faulty router deep in the tree can be routed around, unlike prior redundancy schemes that only repaired bottom memory cells."],"supporting_citations":[{"why":"Supplies the superconducting-cavity QRAM hardware in which classical data is readable at interior tree nodes, an assumption IterativeRepair relies on.","marker":"[7]"},{"why":"Establishes the bucket-brigade, router-based QRAM query model and its noise resilience, the architecture the repair algorithms modify.","marker":"[13]"},{"why":"Introduces the bucket-brigade QRAM scheme whose binary-tree routers and query procedure the paper reuses.","marker":"[12]"},{"why":"Prior work repairing faulty bucket-brigade QRAM memory cells with redundancy, the comparison point for router-level repair.","marker":"[20]"},{"why":"Supplies the Galton-Watson branching-process theory behind the expected faulty-address counts and repairability statistics.","marker":"[35]"},{"why":"Gives the pipelined $O(j+b)$ query-timing model used to derive the $O(n^2)$ repaired-query overhead.","marker":"[36]"}],"fun_headline_variants":["1.5 ancillas revive a faulty QRAM","QRAM repairs with 1.5 qubits on average","IterativeRepair: 1.5 flags fix defective QRAM","Defective routers, minimal flags: QRAM survives","Recovering QRAM with 1.5 ancilla qubits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole procedure starts only if the top three routers (a functioning 2-bit QRAM) are defect-free and at least half the addresses remain reachable; if a router among the top levels is dead, the recursive repair cannot get off the ground.","fun_headline_variants_meta":{"raw":{"variants":["1.5 ancillas revive a faulty QRAM","QRAM repairs with 1.5 qubits on average","IterativeRepair: 1.5 flags fix defective QRAM","Defective routers, minimal flags: QRAM survives","Recovering QRAM with 1.5 ancilla qubits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000314,"raw_usage":{"total_tokens":1809,"prompt_tokens":1000,"completion_tokens":809,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":616,"completion_tokens_details":{"reasoning_tokens":723}},"tokens_in":616,"tokens_out":809,"duration_ms":7260,"temperature":1.0,"reasoning_tokens":723,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:05:22.562408+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Randomly generate depth-13 trees with 1% per-router failure conditioned on the top three routers being good and on at least $2^{12}$ reachable leaves, run IterativeRepair, and count flag qubits per layer; the central claim is false if a nontrivial fraction of such repairable instances fail to yield a 12-bit QRAM, or if the maximum per-layer flag-qubit count systematically exceeds $n-3$.","supporting_citations":[{"cited_title":"Maximizing the yield of bucket brigade quantum random access memory using redundancy repair,","cited_arxiv_id":null,"evidence_quote":"Prior work repairing faulty bucket-brigade QRAM memory cells with redundancy, the comparison point for router-level repair."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Galton-Watson branching-process theory behind the expected faulty-address counts and repairability statistics."}],"review_version":1}