Parallel Spooky Pebbling Makes Regev Factoring More Practical
Pith reviewed 2026-05-18 09:03 UTC · model grok-4.3
The pith
Parallel spooky pebbling reduces Regev factoring to multiplication depth 193 for 4096-bit integers.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
By combining parallelism and spooky measurements, a line graph of length ℓ can be pebbled in depth exactly 2ℓ with space bounded by 2.47 log ℓ; an A* search further improves concrete small cases. When these pebbling schedules are substituted into the arithmetic of Regev's factoring algorithm, 4096-bit integers N can be factored with multiplication depth 193.
What carries the argument
The parallel spooky pebble game on a line graph, which permits simultaneous pebble moves and Hadamard-basis measurements that leave temporary phase ghosts, thereby trading space for depth in a controlled way.
If this is right
- Regev's algorithm factors 4096-bit N at multiplication depth 193 instead of 680.
- The new depth is lower than the 444 reported for Shor's algorithm, although Shor still requires far less space.
- The same pebbling techniques extend to other arithmetic circuits that appear in quantum cryptanalysis.
- Regev variants become more attractive on hardware platforms where depth is scarcer than space.
Where Pith is reading between the lines
- If error-correction overhead scales with depth rather than space, the reduced depth could make Regev competitive on certain fault-tolerant architectures despite its larger qubit count.
- The A* search procedure used for small instances could be adapted to search over non-line graphs that arise in other quantum algorithms.
- Combining the reported schedules with known techniques for reversible modular multiplication might yield still lower total depth.
Load-bearing premise
The abstract costs of the pebble game translate directly into quantum-circuit depth and space with only negligible overhead from decomposing spooky measurements into gates, realizing parallelism on hardware, or paying error-correction costs.
What would settle it
A gate-level simulation of the reported pebbling schedule for a small concrete ℓ that measures the actual two-qubit gate count and total depth and shows whether they match the predicted pebble-derived figures.
read the original abstract
"Pebble games," an abstraction from classical reversible computing, have found use in the design of quantum circuits for inherently sequential tasks. Gidney showed that allowing Hadamard basis measurements during pebble games can dramatically improve costs -- an extension termed "spooky pebble games" because the measurements leave temporary phase errors called ghosts. Separately, previous work by Blocki et al. studied the benefits of parallelism in pebble games. In this work we define and study parallel spooky pebble games, showing that parallelism and spookiness can yield impressive gains when used together. First, we show by construction that a line graph of length $\ell$ can be pebbled in depth $2\ell$ (exactly optimal) using space $\leq 2.47\log \ell$. Then, to explore pebbling schemes using even less space, we use a highly optimized $A^*$ search implemented in Julia to find the lowest-depth parallel spooky pebbling possible for a range of concrete line graph lengths $\ell$ given a constant number of pebbles $s$. We then show that these techniques can significantly reduce the cost of the arithmetic in Regev's factoring algorithm. For example, we find that 4096-bit integers $N$ can be factored in multiplication depth 193, which outperforms the 680 required of previous variants of Regev and the 444 reported by Eker{\aa} and G\"artner for Shor's algorithm. While the space required for Shor's algorithm is considerably less than any variant of Regev's algorithm including ours, and thus Shor likely remains the best candidate for the first quantum factorization of large integers, our results show that implementations of Regev's algorithm are far from fully optimized, and Regev's algorithm may have practical importance in the future. We also believe our pebbling techniques are applicable in quantum cryptanalysis beyond integer factorization, and in quantum circuit compilation more broadly.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript defines parallel spooky pebble games by combining parallelism with spooky (Hadamard-basis) measurements in classical pebble games for quantum circuit design. It gives an explicit construction proving that a line graph of length ℓ can be pebbled in depth exactly 2ℓ (optimal) using space ≤ 2.47 log ℓ. An optimized A* search in Julia is used to find minimal-depth pebbling strategies for concrete ℓ values under fixed pebble counts. These techniques are applied to the arithmetic circuit of Regev's factoring algorithm, yielding a claimed multiplication depth of 193 for 4096-bit N (improving on 680 for prior Regev variants and 444 for Shor's algorithm).
Significance. The explicit construction for the depth-2ℓ bound and the independent A* search results constitute concrete, falsifiable contributions that strengthen the work. If the reported pebble-game depths translate directly into quantum-circuit multiplication depth with only negligible overhead, the results demonstrate that Regev's algorithm remains substantially under-optimized and could become practically relevant in future fault-tolerant regimes, even while acknowledging that Shor's algorithm retains a space advantage.
major comments (1)
- [Abstract] Abstract: The headline claim that 4096-bit N can be factored with multiplication depth 193 rests on equating the parallel spooky pebbling depth (2ℓ) to the multiplication depth of the Regev arithmetic circuit. The manuscript supplies the pebbling construction and search results but contains no explicit gate-level decomposition, ghost-correction cost accounting, or parallelism overhead analysis that would confirm the mapping incurs no substantial extra depth from Clifford/Pauli updates or routing.
minor comments (1)
- [Abstract] The abstract states the space bound ≤ 2.47 log ℓ but does not indicate in which section the constant is derived from the construction; a forward reference would improve readability.
Simulated Author's Rebuttal
We thank the referee for their careful reading and for recognizing the concrete contributions of the explicit construction and A* search results. We address the major comment below, clarifying the relationship between pebbling depth and circuit depth while acknowledging where additional discussion can strengthen the presentation.
read point-by-point responses
-
Referee: [Abstract] Abstract: The headline claim that 4096-bit N can be factored with multiplication depth 193 rests on equating the parallel spooky pebbling depth (2ℓ) to the multiplication depth of the Regev arithmetic circuit. The manuscript supplies the pebbling construction and search results but contains no explicit gate-level decomposition, ghost-correction cost accounting, or parallelism overhead analysis that would confirm the mapping incurs no substantial extra depth from Clifford/Pauli updates or routing.
Authors: The parallel spooky pebble game is introduced precisely as an abstraction for quantum-circuit depth in sequential arithmetic tasks. By definition, the depth of a valid pebbling strategy on the line graph of length ℓ equals the multiplication depth of the corresponding Regev circuit under the spooky measurement model; the ghost-correction rules are already encoded in the allowed moves, and the reported depth 2ℓ (or the A*-optimized depths) is therefore the depth in that model. Parallelism is incorporated by permitting simultaneous pebble placements consistent with the quantum circuit's ability to execute independent operations. We do not supply a full gate-level Clifford/Pauli decomposition or routing analysis because the paper focuses on the high-level pebbling optimization; such overheads are largely independent of the chosen pebbling schedule and can be bounded separately using standard compilation techniques. The relative improvement over prior Regev variants therefore remains valid. To address the referee's concern we will add a short clarifying paragraph in Section 4 (or a new subsection) that explicitly states the modeling assumptions and cites the foundational spooky-pebbling literature establishing the depth correspondence. revision: partial
Circularity Check
No significant circularity: results rest on explicit construction and independent A* search
full rationale
The paper's core claims derive from an explicit construction showing a line graph of length ℓ can be pebbled in depth exactly 2ℓ with space ≤2.47 log ℓ, plus a separate A* search (implemented in Julia) to find minimal-depth schemes for fixed pebble count s. These steps are not self-definitional, do not rename fitted parameters as predictions, and do not rely on load-bearing self-citations or imported uniqueness theorems. The mapping to Regev multiplication depth (e.g., 193 for 4096-bit N) is presented as a direct application of the pebbling costs rather than a tautological reduction to the input data or assumptions. Prior work is cited from external authors (Gidney, Blocki et al.), not as a self-referential chain. The derivation chain is therefore self-contained and does not reduce to its inputs by construction.
Axiom & Free-Parameter Ledger
free parameters (1)
- 2.47
axioms (1)
- domain assumption Pebble games on line graphs accurately model the reversible arithmetic costs inside Regev's quantum factoring circuit.
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
we show by construction that a line graph of length ℓ can be pebbled in depth 2ℓ (exactly optimal) using space ≤ 2.47 log ℓ
-
IndisputableMonolith/Foundation/DimensionForcing.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
α≈1.32 solution to α³−α−1=0; A_k = A_{k-2}+A_{k-3}
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.