[Submitted on 31 Aug 2026 (this version), latest revision 31 Aug 2026 (v5)]
Title:Verification and Repair of a Space-Efficient Quantum ECDLP Construction
Abstract: Luo et al. propose an 835-logical-qubit circuit for the elliptic-curve discrete-logarithm problem over secp256k1. Version 2 replaces the fixed Euclidean schedule argument in version 1 with a finite polyhedral antinorm certificate. A machine-checked reconstruction proves the new quotient-weight bound of 405 and the resulting 1,620-step schedule. The published inverter still fails on valid inputs: its coefficient endpoint truncates a reachable operand, its active window omits a required secp256k1 position, its final remainder-length endpoint exceeds the work register, and terminal padding moves the inverse away from the stated output slice. A later companion revision changes each mechanism. Finite executions and formal reconstructions support those changes, while a circuit-level theorem for the complete measurement-enabled generator remains absent. A separately verified repair computes inversion for every nonzero reduced secp256k1 input, preserves the input, and clears its workspace. It uses 858 logical wires and has syntax-derived upper bounds of 2,209,345,754 reversible gates, 1,140,152,658 Toffoli gates, and 2,185,828,088 CNOT gates. The published affine point-addition schedule is correct only when its divisor and an internal multiplication operand are nonzero. Its coherent caller includes excluded group cases, so the published circuit does not establish total group translation. The paper's asymptotic arithmetic is conditionally reproducible, but the current companion cannot reproduce its numerical rows, and the complete ECDLP width lacks a peak-live register allocation.
| Comments: | 9 pages, 4 tables |
| Subjects: | Logic in Computer Science (cs.LO); Computational Complexity (cs.CC) |
| Cite as: | marXiv:2608.00055 [cs.LO] (or marXiv:2608.00055v1 [cs.LO] for this version) |
Submission history
[v1] Mon, 31 Aug 2026 18:41:34 UTC (373 KB)
[v2] Mon, 31 Aug 2026 19:08:03 UTC (371 KB)
[v3] Mon, 31 Aug 2026 19:40:32 UTC (429 KB)
[v4] Mon, 31 Aug 2026 19:56:55 UTC (406 KB)
[v5] Mon, 31 Aug 2026 20:08:27 UTC (406 KB)