[Submitted on 9 Sep 2026 (v1), revised 9 Sep 2026 (this version, v3), latest revision 9 Sep 2026 (v4)]
Title:Toffoli Reductions and Single-Run Recovery for an 833-Qubit secp256k1 ECDLP Program
Abstract: We verify an 833-logical-qubit secp256k1 discrete-logarithm program that recovers every valid nonzero private scalar with probability greater than 99 percent in one execution and uses at most 36,591,123,006 Toffoli-class operations on every path and in expectation. Starting from the previously reported bound of 588,551,462,912 operations per execution, we derive reductions from shared Euclidean endpoint comparisons, scalar windows, output-side recognition of exceptional point additions, and an initial public-point lookup. An analytic Fourier-tail bound supports a bounded classical decoder and replaces the earlier 26-execution recovery guarantee. The smallest proved Toffoli bound in the resulting lookup family uses a 26-bit prefix, a 4 GiB packed public table, and at most 34,493,956,094 lookup CNOTs. Smaller prefixes reduce these classical-storage and CNOT costs. Lean proofs connect the generated operations, restored workspace, exact branch amplitudes, recovery probability, and logical resources. Structural count lemmas and symbolic scalar and measurement-history decompositions reduce the finite computations required in those proofs.
| Subjects: | Logic in Computer Science (cs.LO); Computational Complexity (cs.CC) |
| Cite as: | marXiv:2609.00003 [cs.LO] (or marXiv:2609.00003v3 [cs.LO] for this version) |
Submission history
[v1] Wed, 9 Sep 2026 13:43:24 UTC (297 KB)
[v2] Wed, 9 Sep 2026 13:48:30 UTC (298 KB)
[v3] Wed, 9 Sep 2026 13:56:48 UTC (299 KB)
[v4] Wed, 9 Sep 2026 14:02:07 UTC (299 KB)
Related work
- marXiv:2609.00002
- Extends the 833-qubit construction with shared endpoint comparisons, scalar windows, initial lookup, and analytic one-run recovery.
Named by
- marXiv:2609.00013
- This stand-alone report gives the completed 833-qubit algorithm, extending the intermediate optimization report.
- marXiv:2609.00004
- Extends the 36,591,123,006-Toffoli result with verified arithmetic reductions to 18,467,700,570 at the same 833-qubit allocation and one-run recovery guarantee.