\documentclass[10pt,twocolumn]{article}
\usepackage[margin=0.75in,top=0.9in,bottom=0.9in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{booktabs}
\usepackage{array}
\usepackage{microtype}
\usepackage{xcolor}
\usepackage[colorlinks=true,linkcolor=blue!60!black,urlcolor=blue!60!black,citecolor=blue!60!black]{hyperref}
\usepackage{graphicx}
\usepackage{fancyhdr}

\makeatletter
\renewcommand\section{\@startsection{section}{1}{\z@}%
  {8pt plus 2pt minus 1pt}{4pt}{\normalsize\bfseries\scshape}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
  {6pt plus 2pt minus 1pt}{3pt}{\small\bfseries}}
\makeatother

\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}
\fancyfoot[C]{\footnotesize\color{gray} Draft --- August 2026 \quad Page \thepage}

\newcommand{\Fp}{\mathbb{F}_{31}}
\newcommand{\DT}{D_T}
\newcommand{\xor}{\mathbin{\oplus}}
\setlength{\columnsep}{18pt}
\setlength{\emergencystretch}{1em}

\begin{document}

\twocolumn[{%
\centering
{\LARGE\bfseries Progressive Synthesis of a Reversible 5-Bit\\[2pt]
Elliptic-Curve Group-Law Oracle\par}
\vspace{10pt}
{\normalsize
\texttt{@jackylee0424},
\texttt{@gnuchev},
\texttt{@runeape-sats},
\texttt{@jieyilong},
\texttt{@edi3on}\par}
\vspace{12pt}
\begin{minipage}{0.88\textwidth}
\small
\textbf{Abstract.}
Shor's discrete-logarithm algorithm calls elliptic-curve point addition inside its main oracle.
Reversible arithmetic for that oracle dominates published fault-tolerant resource estimates.
Toffoli count and Toffoli depth price its non-Clifford work and critical path.
The cost proxy $q\sqrt{T\DT}$ combines those quantities with logical width.
Here, $q$ is the logical-qubit count, $T$ is the Toffoli count, and $\DT$ is Toffoli depth.
We synthesize the evolving design of a verified 5-bit oracle over $\Fp$.
The design moved from table-free arithmetic to a three-point scalar pebble.
Later work refined cleanup order, live ranges, controlled-add timing, and an inverse-case witness.
The current circuit uses 315 logical qubits and 4{,}724{,}217 Toffoli gates.
Its Toffoli depth is 3{,}523{,}665, giving a score of 1{,}285{,}206{,}102.9293.
The small instance exposes interactions between width, arithmetic, and scheduling under complete reversible cleanup.
\vspace{8pt}
\end{minipage}\par
}]

\section{Introduction}

The cost of elliptic-curve discrete logarithms depends on reversible group arithmetic.
Shor's algorithm supplies the polynomial-time quantum framework~\cite{shor}.
Its elliptic-curve realization repeatedly evaluates controlled point additions.
Those additions require finite-field arithmetic, exception handling, and clean uncomputation.

Existing estimates place this arithmetic at the center of fault-tolerant resource accounting.
Roetteler et al. quantified complete circuits for elliptic-curve discrete logarithms~\cite{roetteler}.
H\"aner et al. later reduced resources through improved reversible circuits~\cite{haner}.
Both works motivate studying the oracle below the algorithm level.

This work isolates a variable-base group-law oracle at a fully testable field size.
The curve is $y^2=x^3+7$ over $\Fp$.
Its group has order 21.
The oracle maps two scalars and two points to their linear combination.
It preserves every input and clears every ancillary qubit~\cite{contest}.

The cost model rewards joint control of space, work, and serialized non-Clifford work.
Its score is
\begin{equation}
  S=q\sqrt{T\DT}.
  \label{eq:score}
\end{equation}
Width enters linearly.
Toffoli count and depth enter through their geometric mean.
This form permits a width reduction to offset more arithmetic.

The current design reaches $S=1{,}285{,}206{,}102.9293$ under the fixed oracle contract.
It uses 315 logical qubits, 4{,}724{,}217 Toffoli gates, and depth 3{,}523{,}665.
The result emerged through a public, strict-improvement research process.
This paper presents that process as progressive synthesis rather than a ranking report.

\paragraph{Contributions.}
The authors contributed distinct phases of the frontier.
\texttt{@jackylee0424} maintained the effort and established the table-free baseline.
\texttt{@runeape-sats} introduced the width cut and several cleanup schedules.
\texttt{@edi3on} reduced cleanup work by changing the recycled power slot.
\texttt{@jieyilong} shortened live ranges through delayed scratch allocation.
\texttt{@gnuchev} combined early scheduling with a predicate-specific field witness.

\section{Related Work}

Shor established polynomial-time quantum algorithms for discrete logarithms~\cite{shor}.
The algorithm prepares a periodic quantum state and extracts its period information.
For elliptic curves, the period function evaluates scalar combinations of points.
That evaluation turns the group law into an inner reversible computation.

Roetteler et al. connected this algorithm to concrete elliptic-curve resource estimates~\cite{roetteler}.
Their analysis accounted for logical qubits and quantum gates at cryptographic sizes.
It showed how field inversion and point addition shape the total circuit.
The present work studies those mechanisms in a smaller verified setting.

H\"aner et al. developed lower-resource circuits for elliptic-curve discrete logarithms~\cite{haner}.
Their work demonstrates that representation and arithmetic choices change full-algorithm costs.
Our metric adds explicit pressure on Toffoli depth.
It also exposes scratch lifetime through the factor $q$.

The eventual real-world target includes curves such as secp256k1.
SEC~2 specifies that curve and its domain parameters~\cite{sec2}.
The 5-bit curve here is not a resource estimate for secp256k1.
It is an exact test bed for reversible design choices.

The contest repository defines the executable contract and ongoing research record~\cite{contest}.
This paper uses that record for metrics and lineage.
It does not reproduce implementation artifacts or validation logs.

\section{The Oracle and Its Cost Model}

The target operation preserves four inputs and writes one output point.
It is
\begin{equation}
\begin{split}
|a\rangle|b\rangle|P\rangle|Q\rangle|0\rangle\longmapsto{}&
|a\rangle|b\rangle|P\rangle|Q\rangle\\
&|aP+bQ\rangle .
\end{split}
\label{eq:oracle}
\end{equation}
Both 5-bit scalars are interpreted modulo 21.
The points are variable inputs rather than compile-time constants.

Each point uses affine coordinates plus an infinity flag.
Table~\ref{tab:registers} gives the public register layout.
Each coordinate occupies five qubits.
The flag distinguishes the point at infinity from finite coordinate encodings.
The output begins in the all-zero state.

\begin{table}[t]
\centering
\small
\setlength{\tabcolsep}{5pt}
\begin{tabular}{@{}lll@{}}
\toprule
Register & Width & Meaning\\
\midrule
$a,b$ & 5 each & scalars modulo 21\\
$p_x,p_y,p_{\rm inf}$ & $5,5,1$ & input point $P$\\
$q_x,q_y,q_{\rm inf}$ & $5,5,1$ & input point $Q$\\
$r_x,r_y,r_{\rm inf}$ & $5,5,1$ & output point $R$\\
\bottomrule
\end{tabular}
\caption{Public registers for the oracle in Eq.~\eqref{eq:oracle}.}
\label{tab:registers}
\end{table}

The arithmetic contract is reversible and in place.
Its field facade provides addition, subtraction, multiplication, inversion, comparison, zero testing, and multiplexing.
The scalar facade permits point doubling and controlled affine addition.
Scratch may be reused only after it has been returned to zero.

The score in Eq.~\eqref{eq:score} measures a compiled logical circuit.
The logical width $q$ includes public registers and live workspace.
The count $T$ measures all Toffoli gates.
The depth $\DT$ measures Toffoli layers along the critical path.
Clifford gates and total operations remain reported diagnostics.

The frontier gate requires a strictly lower score and complete verification.
A candidate with unchanged width may win through count or depth.
A narrower candidate may win even when both Toffoli measures rise.
This rule made space-time tradeoffs observable throughout the lineage.

Verification uses 9{,}024 deterministic Fiat--Shamir shots.
The first check establishes oracle correctness.
The second checks in-place $\Fp$ arithmetic composition.
The third enforces the restricted scalar strategy interface.
The remaining checks cover input preservation, phase cleanliness, and ancilla cleanup.
All six conditions must hold for the score to enter the frontier~\cite{contest}.

\section{Progressive Synthesis of the Frontier}

The frontier evolved through one width cut and then intertwined arithmetic and scheduling refinements.
Methodologically, the work separates into baseline, width, field arithmetic, and scalar scheduling.
Chronologically, scheduling refinements preceded the final field specialization.
Table~\ref{tab:eras} records representative frontier states in their actual order.

\begin{table*}[t]
\centering
\small
\setlength{\tabcolsep}{6pt}
\resizebox{\textwidth}{!}{%
\begin{tabular}{@{}p{2.25cm}p{3.2cm}lrrrr@{}}
\toprule
Frontier phase & Main method & Contributors & $q$ & $T$ & $\DT$ & Score\\
\midrule
Table-free baseline & Dynamic powers and reversible $\Fp$ kernels
& \texttt{@jackylee0424} & 326 & 4{,}624{,}825 & 3{,}477{,}469 & 1{,}307{,}365{,}094.9206\\
Width reduction & Three-point scalar pebble
& \texttt{@runeape-sats} & 315 & 4{,}791{,}417 & 3{,}579{,}733 & 1{,}304{,}571{,}408.6103\\
Scalar refinement & Recycled slot, cleanup order, and retiming
& \texttt{@edi3on}, \texttt{@runeape-sats}, \texttt{@jieyilong}
& 315 & 4{,}734{,}423 & 3{,}529{,}327 & 1{,}287{,}626{,}872.9591\\
Field--schedule co-design & Complement witness and bit-order retiming
& \texttt{@gnuchev} & 315 & 4{,}724{,}217 & 3{,}523{,}665 & 1{,}285{,}206{,}102.9293\\
\bottomrule
\end{tabular}
}
\caption{Era-level progression. Each row is a representative accepted frontier state.}
\label{tab:eras}
\end{table*}

\subsection{Table-Free Baseline}

The baseline established an arithmetic-first oracle without field or point lookup tables.
The field layer used reversible Boolean kernels over $\Fp$.
Multiplication used controlled cyclic shifts for the modulus $2^5-1$.
Inversion used a Fermat exponentiation chain.

The baseline also specialized repeated field operations.
Multiplication by 3 became addition to a one-bit cyclic rotation.
The first product term was copied without an add from zero.
Reduced bits and the all-ones reduction flag were materialized once.

The first scalar strategy stored a full dynamic power chain.
It computed $2P$, $4P$, $8P$, and $16P$.
It applied the same process to $Q$.
Each chain was reversed after its controlled additions.

\subsection{Width Reduction}

The width phase replaced four live powers with a three-point pebble.
One scratch point first held $2P$ and was later reused for $16P$.
The other two scratch points retained $4P$ and $8P$.
The schedule accepted two extra doublings to enable reuse.

This exchange reduced width from 326 to 315 logical qubits.
Toffoli count rose from 4{,}624{,}825 to 4{,}791{,}417.
Toffoli depth rose from 3{,}477{,}469 to 3{,}579{,}733.
The linear width gain still lowered the score by 2{,}793{,}686.3103.

\subsection{In-Place Field Arithmetic}

Field refinement specialized a value that served only as a predicate.
The inverse-point branch needs to know whether two finite $y$ coordinates sum to zero.
It does not need the sum after that test.
A reversible witness can therefore replace a full modular addition.

The witness uses complementation in five-bit encodings modulo 31.
For a nonzero field encoding, negation is its bitwise complement.
The kernel writes
\begin{equation}
 w=y_{\rm left}\xor y_{\rm right}\xor 11111_2.
 \label{eq:witness}
\end{equation}
The zero test on $w$ preserves the inverse-case decision.

The first witness reduced both Toffoli count and depth at width 315.
It lowered $T$ by 10{,}206 and $\DT$ by 5{,}502.
Writing witness bits in order $3,0,1,2,4$ then removed 160 depth layers.
That permutation left every recorded gate count unchanged.

\subsection{Scalar-Strategy Scheduling}

Scalar scheduling reduced work and depth within the three-point budget.
\texttt{@edi3on} kept $2P$ live and recycled the $4P$ slot for $16P$.
Cleanup then recreated $4P$ from $2P$ before clearing $8P$.
This change cut both Toffoli count and depth.

Cleanup-pebble ordering exposed further depth-only improvements.
\texttt{@runeape-sats} converted the $16P$ slot into a valid $2P$ cleanup value.
The temporary $16P\xor2P$ pattern was never used as a point.
Later controlled additions were placed near each power's last use.

Live-range control shortened the critical path without changing work.
\texttt{@jieyilong} delayed allocation of the third scratch point.
The schedule then added $16P$, $8P$, $4P$, $2P$, and $P$.
It cleaned power slots near their last use.

Early-staircase retiming completed the accepted scalar schedule.
\texttt{@runeape-sats} moved low controlled additions toward power creation.
\texttt{@gnuchev} retained that staircase beside the field witness.
The final schedule keeps three 11-qubit scratch points.

\section{The Leading Method in Depth}

The leading method combines predicate-specific field arithmetic with an early scalar staircase.
The field change removes work that the point adder never observes.
The scalar change controls the lifetime and dependency order of point powers.
Both retain compute--copy--uncompute cleanup.

\subsection{Arithmetic Scheme}

The arithmetic scheme implements field operations as reversible transformations.
Addition and subtraction reduce their results modulo 31.
Multiplication accumulates controlled cyclic shifts.
Inversion applies a Fermat exponentiation chain.
Comparison, zero testing, and multiplexing support exceptional group-law branches.

The inverse-case witness is narrower in purpose than modular addition.
Equation~\eqref{eq:witness} is used only for a zero predicate.
Its bits can be written in an order chosen for downstream depth.
The selected order is $3,0,1,2,4$.

The witness remains reversible because it is later uncomputed.
The point adder first computes $w$ into zeroed scratch.
It copies the zero-test decision into the branch logic.
It then reverses the witness construction.
No residual witness remains in the final state.

\subsection{Scalar Strategy}

The scalar strategy builds each multiple only while it supports additions or cleanup.
Successive doublings provide $2P$, $4P$, $8P$, and $16P$.
Controlled additions consume scalar bits as their powers become available.
The same construction forms the contribution from $Q$.

Three scratch points form the live pebble budget.
The first slot is cleared and reused for $8P$.
The final power slot later becomes a valid $2P$ cleanup pebble.
This state supports reversing the earlier doublings.

The transient XOR pattern is an output state, not a point value.
During cleanup, a slot may briefly contain $16P\xor2P$.
No doubling or controlled addition consumes that pattern.
The next inverse operation recovers a valid cleanup point.

The schedule contains ten doubling calls and five controlled additions.
It performs controlled additions in an early staircase.
Low powers enter the accumulator soon after they exist.
Cleanup then reverses every remaining power dependency.

\subsection{Correctness Invariants}

Correctness follows from four invariants maintained across every reversible segment.
First, the public inputs $a$, $b$, $P$, and $Q$ never change.
Second, every consumed point source is a valid affine-plus-flag encoding.
Third, the output accumulates exactly the selected powers.
Fourth, every scratch qubit returns to zero.

The infinity flag makes the point representation total for the group law.
Finite points use their two affine coordinates.
The flag represents the identity without assigning it finite coordinates.
Point operations preserve this encoding convention.

The scalar invariant ties the binary schedule to the group expression.
Each controlled addition contributes one selected power of its input point.
The dynamic chain supplies all five scalar positions.
Combining the two held products yields $aP+bQ$.

The witness invariant concerns only the inverse-point predicate.
For its stated nonzero field inputs, complementation realizes modular negation.
Thus $w=0$ exactly when the two encoded $y$ values are inverses.
Uncomputing $w$ restores its scratch register.

The validation conditions test the observable consequences of these invariants.
Oracle correctness checks the final group element.
Input preservation checks the public registers.
Phase and ancilla checks detect reversible garbage.
Field composition and scalar-interface checks constrain the implementation boundary.

\subsection{Where the Budget Goes}

The remaining budget is bounded by repeated point operations and their field kernels.
The source papers identify inversion and multiplication as the main arithmetic targets.
Each dynamic point power invokes those kernels through doubling.
Each controlled affine addition adds another dependency chain.

The final arithmetic optimization affects a small but repeated decision path.
It removes 10{,}206 Toffoli gates compared with the preceding scheduled design.
Its bit permutation removes another 160 Toffoli layers.
Width stays fixed because the witness reuses existing scratch.

The scalar schedule now offers less depth-only headroom than earlier phases.
Several refinements changed only $\DT$ while holding all counts fixed.
Their reductions were 1{,}216, 2{,}282, 116, and 34 layers.
The sequence shows diminishing gains from dependency-tail retiming.

\section{Results}

The final circuit improves the score through width, arithmetic, and critical-path control.
Table~\ref{tab:final} reports the complete recorded metrics.
The circuit preserves the 315-qubit width reached in the second frontier phase.
It then reduces both Toffoli measures relative to that width milestone.

\begin{table}[t]
\centering
\small
\begin{tabular}{@{}lr@{}}
\toprule
Metric & Final value\\
\midrule
Logical qubits & 315\\
Toffoli count & 4{,}724{,}217\\
Toffoli depth & 3{,}523{,}665\\
Clifford count & 14{,}182{,}788\\
Total operations & 26{,}076{,}249\\
$q\sqrt{T\DT}$ & 1{,}285{,}206{,}102.9293\\
\bottomrule
\end{tabular}
\caption{Final compiled circuit metrics.}
\label{tab:final}
\end{table}

The last frontier step isolates a pure depth improvement.
Logical width, Toffoli count, Clifford count, and total operations were unchanged.
Toffoli depth fell by 160 layers.
The score fell by 29{,}178.5176 through the $\sqrt{\DT}$ factor.

The score decomposition now favors structural changes over small retimings.
For proportional changes, width has full weight in Eq.~\eqref{eq:score}.
Count and depth each have half weight.
A tenfold score cut from width alone requires a tenfold width cut.
A cut from one Toffoli factor alone requires a hundredfold reduction.

The 9{,}024-shot gate found no failures for the final circuit.
All six required checks passed.
This result supports correctness under the defined deterministic test suite.
It is not a proof for larger fields or another oracle contract.

\section{Discussion and Future Work}

The remaining headroom lies in field kernels, a smaller live set, or both.
Depth-only scheduling still helps, but its latest gains are narrow.
Inversion and multiplication repeat across doublings and additions.
Reducing them can affect both $T$ and $\DT$.

A lower-width scalar strategy must account for recomputation costs.
The first width cut saved 11 qubits but added two doublings.
Equation~\eqref{eq:score} accepted that trade at this size.
A further cut must preserve clean reversal and the restricted interface.

The 5-bit result does not directly extrapolate to cryptographic curves.
Field registers, multiplication circuits, and inversion chains grow with the modulus.
Their relative costs can change with arithmetic architecture.
The secp256k1 domain is therefore a separate compilation target~\cite{sec2}.

Several design principles do transfer beyond this instance.
Predicate-specific computation avoids producing unused values.
Pebbling makes width and recomputation explicit.
Live-range ordering exposes depth without changing gate totals.
Compute--copy--uncompute gives local cleanup obligations.

The contest format contributes a reproducible method for circuit synthesis.
A fixed interface prevents improvements from changing the mathematical task.
A scalar score makes space-time exchanges visible.
Deterministic verification keeps each accepted frontier state comparable.
The ongoing record can therefore support further collective refinement~\cite{contest}.

\section*{Acknowledgments}

We thank the \href{https://ecdsa.fail}{ecdsa.fail} community~\cite{ecdsafail} for pioneering this effort; resource estimates and mitigations for 256-bit curves are surveyed in~\cite{googleecc}.

The contributions were assisted by GPT-5, GPT-5.5, and Claude Sonnet model families.
The draft was auto-assembled from the contest record and contestant-derived papers.
It has not been peer reviewed.

\begin{thebibliography}{9}\small

\bibitem{shor}
P.~W.~Shor,
``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,''
\emph{SIAM Journal on Computing}, vol.~26, no.~5, pp.~1484--1509, 1997.
arXiv:\href{https://arxiv.org/abs/quant-ph/9508027}{quant-ph/9508027}.

\bibitem{roetteler}
M.~Roetteler, M.~Naehrig, K.~M.~Svore, and K.~Lauter,
``Quantum resource estimates for computing elliptic curve discrete logarithms,''
ASIACRYPT, 2017.
arXiv:\href{https://arxiv.org/abs/1706.06752}{1706.06752}.

\bibitem{haner}
T.~H\"aner, S.~Jaques, M.~Naehrig, M.~Roetteler, and M.~Soeken,
``Improved quantum circuits for elliptic curve discrete logarithms,''
PQCrypto, 2020.
arXiv:\href{https://arxiv.org/abs/2001.09580}{2001.09580}.

\bibitem{sec2}
Certicom Research,
``SEC 2: Recommended Elliptic Curve Domain Parameters,''
version 2, 2010.

\bibitem{contest}
5-bit Shor ECDLP Contest,
``In-place $\Fp$ field arithmetic and scalar strategy oracle.''
\href{https://github.com/ecdlp-contest/ecdlp-5-bit}{github.com/ecdlp-contest/ecdlp-5-bit}.

\bibitem{ecdsafail}
The ECDSA.fail community (an Eigen Labs project),
quantum circuit construction challenge against ECDSA.
\href{https://ecdsa.fail}{ecdsa.fail}.

\bibitem{googleecc}
R.~Babbush, A.~Zalcman, C.~Gidney, M.~Broughton, T.~Khattar, H.~Neven,
T.~Bergamaschi, J.~Drake, and D.~Boneh,
``Securing elliptic curve cryptocurrencies against quantum vulnerabilities: resource estimates and mitigations,''
2026.
arXiv:\href{https://arxiv.org/abs/2603.28846}{2603.28846}.

\end{thebibliography}

\end{document}
