1 Introduction↩︎

Elliptic curve cryptography (ECC), first proposed in the mid-1980s as an alternative framework for public-key cryptography [1], [2], has become one of the foundational primitives in modern cryptographic systems. The security of ECC-based cryptosystems relies on the computational difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP). Specifically, given an elliptic curve defined over a finite field, a base point \(P\) on that curve, and another point \(Q\) resulting from scalar multiplication of \(P\) by an unknown integer \(m\), the ECDLP asks for the recovery of the scalar \(m\) from the two points. Despite decades of research, no classical algorithm is known that solves the ECDLP in polynomial time of bit length; the best generic attacks, such as Pollard’s rho method, require \(\Theta(\sqrt{p})\) group operations, where \(p\) denotes the field size of the curve which is exponentially large [3].

Compared to classical public-key systems such as RSA [4] and finite-field Diffie-Hellman [5], ECC offers equivalent security with substantially smaller key sizes. For example, according to NIST recommendations [6], a 256-bit elliptic curve provides a security level of 128 bits, which is comparable to that of RSA with a 3072-bit modulus. This efficiency advantage has led to the widespread adoption of ECC in both theoretical cryptographic constructions and real-world applications. Specifically, ECC is used for key exchange [5] and digital signature schemes [7], [8] in widely deployed protocols, including transport layer security [9], secure shell [10], as well as cryptocurrencies such as Bitcoin [11], [12].

In contrast to the computational hardness of ECDLP on classical computers, the security landscape changes fundamentally in the presence of large-scale quantum computers. In 1994, Shor gave polynomial-time quantum algorithms for integer factorization and discrete logarithms [13]. Because the ECDLP is a discrete-logarithm problem in a cyclic subgroup of an elliptic-curve group, it can be efficiently solved quantumly by Shor’s algorithm whenever the elliptic-curve group operation can be implemented efficiently. Proos and Zalka subsequently developed an implementation with resource analysis for prime-field elliptic curves [14]. Thus, sufficiently large fault-tolerant quantum computers would break conventional ECC based on the hardness of the ECDLP. At the same time, the practical implementation of quantum algorithms for cryptography problems remains severely constrained by the limitations of near-term quantum hardware. For instance, implementing Shor’s algorithm at cryptographically relevant scales requires a fault-tolerant quantum computer with a large number of logical qubits and circuits, as well as sufficiently low physical error rates (or equivalently, achievable logical error rates after error correction) [15], [16].

Motivated by these challenges, a substantial body of work has focused on reducing the quantum resource requirements of Shor’s algorithm for integer factorization [17]–[20] and the ECDLP [21]–[27]. In recent studies, three primary resource metrics have received the most attention: (i) space, measured by the number of logical qubits; (ii) quantum gate complexity; and (iii) circuit depth. These resources are strongly coupled, and optimizing one metric often leads to increased costs in others [21], [22], [26], [27]. For each single metric, the state-of-the-art results are:

• In terms of space complexity, Chevignard, Fouque, and Schrottenloher [25] proposed a low-space variant of Shor’s ECDLP algorithm based on residue-number-system arithmetic and compressed projective-coordinate outputs. Their construction achieves the state-of-the-art asymptotic qubit complexity among existing implementations, requiring only \(3.12n+O(\sqrt n)\) logical qubits for an \(n\)-bit prime field. However, this reduction in space comes at the cost of a sufficiently larger gate count of \(\widetilde{O}(n^4)\).

• In terms of gate complexity, Babbush et al. [26] reported substantially improved resource estimates for solving ECDLP of the curve secp256k1 using \(1191\) logical qubits and \(2^{26.27}\) Toffoli gates in the space-optimized setting, or \(1441\) logical qubits and \(2^{25.94}\) Toffoli gates in the gate-optimized setting. However, their circuit-level details are not publicly disclosed. Schrottenloher [27] subsequently gave an explicit and reproducible point addition architecture with comparable performance and slightly smaller Toffoli counts for secp256k1.

• In terms of circuit depth, Kim et al. [24] developed depth-optimized point-addition circuits based on QCSA-based Montgomery multiplication and low-depth binary-EEA inversion. They achieved the lowest circuit depth with adequate ancilla qubits. In terms of the product of qubit count and full depth, their qubit-optimized version achieves a 37%–40% improvement compared to the previous result by Häner et al. [22].

In this work, we study the space complexity of ECDLP. In particular, our focus is the modular inversion subroutine, which is the dominant source of workspace in affine-coordinate point addition. Our goal is to answer the following question:

1.1 Contributions↩︎

The idea of reducing the space complexity of quantum ECDLP algorithms can be traced back to Proos and Zalka [14], who introduced a register-sharing strategy and obtained an asymptotic space bound of \(5n+O(\sqrt n)\) for solving the ECDLP over an \(n\)-bit prime field. However, their analysis was given at a high level of abstraction and did not provide explicit reversible circuit constructions or detailed resource estimates; in particular, issues such as reversible implementation and ancilla management were not fully addressed, and the approximate treatment of modular inversion introduces a fidelity loss of \(O(n^{-1})\).

Our main contribution is to turn this low-space strategy into an exact and fully explicit circuit-level construction. Since modular inversion is the dominant contributor to the overall space, we focus on designing a more space-efficient reversible implementation of this component. Building on the algorithmic framework and register-sharing idea of Proos and Zalka, we refine the representation of the EEA state, introduce length registers and location-controlled arithmetic, and provide explicit circuit constructions with detailed resource estimates. As summarized in Table 1, our construction achieves the best asymptotic logical-qubit complexity reported so far for ECDLP in the standard quantum circuit model.

Second, we provide resource estimates for our quantum circuit implementation. Specifically, we show that a modular inversion circuit can be implemented using at most \(195n^2 + O(n\log_2 n)\) Toffoli gates and \(247n^2 + O(n\log_2 n)\) CNOT gates. By integrating this modular inversion circuit into an affine point addition circuit with mid-circuit measurement (Figures 18 and 17), we obtain a complexity of \(914n^2 + O(n\log_2 n)\) Toffoli gates per point addition. Furthermore, incorporating the point addition circuit into the complete quantum algorithm for solving the ECDLP using the signed-window technique [22] yields a total Toffoli-gate complexity of \(919n^3/\log_2 n + O(n^2)\).

We complement the asymptotic comparison with numerical gate-count estimates and concrete secp256k1 resource estimates. Figure 1 reports the Toffoli and CNOT counts of our modular-inversion and point-addition circuits as functions of the field size \(n\) and Table 2 compares the resulting secp256k1 estimates with recent quantum ECDLP implementations. For secp256k1, our construction uses 835 logical qubits, saving more than 250 logical qubits compared to 1098 qubits in the previous best space-optimized estimate of Chevignard et al. [20]. Furthermore, our Toffoli count is two orders of magnitude lower than [20].

1.2 Overview↩︎

We present an overview of our quantum circuit for solving ECDLP. The standard implementation of Shor’s algorithm consists of \(2n+2\) controlled elliptic-curve point additions followed by a quantum Fourier transform (QFT), as illustrated in Figure 2. Replacing the QFT with its semiclassical variant reduces the logical-qubit requirement without altering the algorithmic functionality, as shown in Figure 3.

Each elliptic-curve point addition is decomposed into reversible modular arithmetic operations, including modular addition, multiplication, squaring, and division, etc. Among these, modular division is the dominant contributor to the logical-qubit cost. Figure 17 illustrates the structure of our point-addition circuit, where these operations are encapsulated as modular arithmetic blocks. In particular, the in-place modular division block is realized by the circuit shown in Figure 18, which consists of a forward execution of the extended Euclidean algorithm (EEA) for modular inversion, followed by its uncomputation.

We present each component from a top-down perspective as follows.

1.2.0.1 Space-efficient reversible algorithm for modular inversion (Section 3).

Our modular inversion procedure, based on the EEA, is designed to implement the following quantum transformation: \[\begin{align} |x \rangle_X|0 \rangle_A|0 \rangle_S \longmapsto |x^{-1}\bmod p \rangle_X|0 \rangle_A|\Gamma(x) \rangle_S, \qquad x\in\mathbb{F}_p^\times, \label{eq:inv95api} \end{align}\tag{1}\] where \(A\) is an \(n\)-qubit workspace register, \(S\) denotes the remaining ancillary registers, and \(|\Gamma(x) \rangle\) is the forward EEA state retained for later uncomputation.

We first revisit the four-phase framework of Proos and Zalka [14] (see Section 3.1), which is well suited for quantum implementation because the number of iterations (which we refer to as steps) is linear in \(n\). Rather than relying on the (inaccurate) \(4.5n\) upper bound stated in [14], we establish a rigorous bound showing that a complete execution of the EEA requires at most \(4\lceil cn\rceil\) steps for every input \(x\), where \(c = 1 / \log_2\!\left(\frac{\sqrt{5} + 1}{2}\right)\).

Section 3.2 then develops an explicit and refined register-sharing strategy at the algorithmic level. In the original construction of [14], a uniform register allocation is used to accommodate all inputs \(x \in \mathbb{F}_p\) in superposition. This worst-case allocation incurs an \(O(\sqrt{n})\) space overhead and necessitates truncating rare outlier cases, introducing an \(O(n^{-2})\) fidelity loss. In contrast, we present an exact allocation scheme that guarantees a deterministic register bound for all inputs \(x \in \mathbb{F}_p\). This reduces the additional space overhead to \(O(\log n)\) while preserving exact correctness.

Finally, starting from a baseline reversible realization of this space-efficient EEA, we introduce a sequence of algorithmic optimizations in Section 3.3 that reorganize the update rules and eliminate redundant arithmetic operations. We provide complete pseudocode (Algorithm 7) together with representative classical execution traces (Table 4), which illustrate the reversibility and correctness of each step and clarify how the procedure can be translated into a quantum circuit.

1.2.0.2 Explicit quantum circuit construction for modular inversion (Section 4).

To show that our modular inversion algorithm admits an explicit quantum circuit implementation, we present a detailed construction based on Algorithm 7. We begin with the overall circuit architecture (Figures 8 and 9 in Section 4.1), where location-controlled operations arise as key non-standard components.

Before giving their explicit implementations, we establish the necessary tools. In Section 4.2, we introduce step-dependent active windows, which restrict the relevant index range at each step and thereby reduce gate complexity. We then introduce unary iteration (Section 4.3) as a primitive for implementing controlled indexed operations, which enables the realization of these location-controlled components.

Finally, in Section 4.4, we present explicit constructions of the location-controlled circuit blocks, including swap, addition/subtraction, and length-update operations (Figures 12, 13, 15, and 16). In addition to the circuit diagrams, we provide detailed explanations of the underlying techniques and design rationale.

1.2.0.3 Affine point addition with mid-circuit measurements (Section 5).

We further show that affine point addition can be implemented using our EEA inversion circuit with only \(3n+O(\log n)\) logical qubits by allowing mid-circuit measurements and classical feed-forward operations. The main issue is the in-place division step \[|x \rangle_X|y \rangle_Y|0 \rangle_A \longmapsto |x \rangle_X|y/x \rangle_Y|0 \rangle_A .\] To perform this map, the EEA inversion circuit in Equation 1 is first applied to \(x\). This requires one clean \(n\)-qubit register \(A\) and leaves the forward EEA state \(\Gamma(x)\) to be cleared later. After the quotient \(y/x\) has been written into \(A\), however, the register \(A\) is no longer clean, so the inverse EEA circuit has no available \(n\)-qubit workspace.

As shown in Figure 18, we resolve this problem by measuring the register containing the old value \(y\) in the Hadamard basis and resetting it to zero. This makes the register \(Y\) available as the clean workspace for the inverse EEA circuit, which recovers \(x\) and clears \(\Gamma(x)\). This measurement is valid because, after \(y/x\) has been written into \(A\), the old value \(y\) is redundant and can be recovered from \(x\) and \(y/x\). Measuring \(|y \rangle\) in the Hadamard basis gives a uniformly random outcome \(b\in\{0,1\}^n\), and the only effect on the remaining registers is the phase \((-1)^{b\cdot y}\). Thus measuring the register \(Y\) does not destroy coherence. The phase is removed by recomputing \(y\) from \(x\) and \(y/x\), applying the corresponding Pauli \(Z\) corrections, and uncomputing the recomputation. The same measurement and correction procedure gives an in-place multiplication circuit. Consequently, affine point addition can be implemented using three \(n\)-qubit registers \(X\), \(Y\), and \(A\), together with the \(O(\log n)\) auxiliary qubits required by the EEA circuit.

We note that mid-circuit measurements have previously been used to reduce either the qubit count or the \(T\)-gate cost of quantum arithmetic circuits [28]–[31]. In particular, the lowest-qubit quantum algorithm currently known for the elliptic-curve discrete logarithm problem also makes extensive use of measurements to reduce the number of qubits [25]. That work does not keep the full elliptic-curve point, nor does it reduce the index registers using a semiclassical Fourier transform. Instead of computing the full point, it computes a one-bit Legendre symbol from the projective coordinates of that point using residue-number-system arithmetic. Its measurements are used to release intermediate nodes in a spooky pebbling strategy for a binary tree [28], [29]. In contrast, we keep the standard affine point-addition structure and use measurements only inside the in-place division and multiplication blocks, where they recycle a register needed as workspace for running the inverse EEA circuit.

1.2.0.4 Resource estimations (Section 6).

Putting everything together, we quantify the space complexity and gate costs of the complete construction of Shor’s ECDLP circuit. We first show in Section 6.1 that the modular inversion circuit requires \(2n + 6\lfloor \log_2 n \rfloor + 19\) logical qubits, and that the affine point addition circuit of Section 5 can therefore be implemented using \(3n + 6\lfloor \log_2 n \rfloor + 19\) logical qubits. Section 6.2 then combines the per-block gate costs (Section 4.4) with the step-dependent active-window bounds (Section 4.2), to obtain an upper bound of \(195n^2 + O(n\log_2 n)\) Toffoli gates and \(247n^2 + O(n\log_2 n)\) CNOT gates for modular inversion, as well as an upper bound of \(914n^2 + O(n\log_2 n)\) Toffoli gates for one affine point addition.

We complement these asymptotic bounds with concrete circuit generation and blockwise compilation using Qiskit in Section 6.3, reporting numerical Toffoli and CNOT gate counts for prime-field sizes ranging from \(64\) to \(512\) bits. Finally, in Section 6.4, we incorporate signed-window scalar multiplication and the associated table look-ups into the complete Shor’s ECDLP circuit. This yields an overall Toffoli complexity of \(919n^3/\log_2 n + O(n^2).\) For the secp256k1 curve, our construction requires \(835\) logical qubits and \(2^{30.63}\) Toffoli gates.

1.3 Open questions↩︎

Our work leaves several open questions for future investigation:

• Gate-count optimization. Our construction prioritizes logical-qubit efficiency and gives explicit reversible circuits for all arithmetic components. However, several building blocks, especially location-controlled arithmetic, length-register updates, and controlled modular operations, may still admit substantial improvements of their gate counts.

• Depth analysis and space-depth trade-offs. This paper focuses primarily on the number of logical qubits and Toffoli/CNOT gate counts, and does not provide a detailed analysis of circuit depth. A natural next step is to study the depth of our modular inversion and point-addition circuits, identify which parts of the computation can be parallelized, and quantify the resulting trade-offs between space, gate count, and depth.

• Applications beyond elliptic-curve discrete logarithms. We note that modular inversion is a general-purpose arithmetic primitive, not only restricted to ECDLP. It would be useful to investigate whether the space-efficient reversible EEA and register-sharing techniques developed here can improve other quantum algorithms that require modular division or inversion, such as Decoded Quantum Interferometry (DQI) [32].

• AI-assisted discovery of quantum arithmetic circuits. An important open question is whether AI systems can enable the automated design of quantum arithmetic circuits, supporting both the discovery of new resource-efficient circuits and the optimization of existing ones. One possible approach is to encode techniques such as windowing, unary iteration, register sharing and mid-circuit measurement as composable modules, and to develop AI-assisted evolutionary frameworks, inspired by systems such as AlphaEvolve [33], that iteratively explore their replacement and composition under automated correctness verification and resource-aware evaluation.

2 Preliminaries↩︎

This section provides a very brief discussion of the basic concepts used in this work. We assume that readers have basic knowledge of quantum computation. For a general survey of quantum algorithms for algebraic problems, we recommend the survey written by Childs and van Dam [34].

2.1 Quantum computing and the Toffoli counts↩︎

We write basis quantum states as \(|x \rangle\), where \(x\) is a bit string, and we model a quantum algorithm as a circuit composed of elementary gates applied to one or more qubits. A key feature is that circuits can create and transform superpositions of basis states, enabling interference effects that are exploited by quantum algorithms.

At the fault-tolerant logical level, it is common to express circuits over a universal gate set such as Clifford+\(T\) [35]. In many architectures the \(T\) gate is substantially more expensive than Clifford operations, so circuit cost is frequently summarized by \(T\)-count, \(T\)-depth, or related metrics [36]. For design and validation, however, it is often convenient to use a purely reversible gate basis.

Accordingly, we express the main reversible components as Toffoli networks. The Toffoli gate maps \[|x,y,z \rangle\;\longmapsto\;|x,y, z \oplus (x y) \rangle,\] and it forms a universal primitive for classical reversible computation [35]. A practical benefit of working at the Toffoli-network level is that such networks admit exact realizations over Clifford+\(T\) [37], avoiding approximation overhead associated with synthesizing arbitrary unitaries. Moreover, Toffoli-based reversible circuits can be efficiently simulated on classical inputs at scales far beyond what is possible for general quantum-state simulation, which makes testing and debugging large arithmetic circuits significantly more tractable [38]. For these reasons, we specify the core arithmetic and elliptic-curve routines using Toffoli and CNOT gates.

2.2 Elliptic curves and the ECDLP↩︎

Let \(p\) be a large prime and let \(\mathbb{F}_p\) denote the finite field with \(p\) elements. An elliptic curve \(E/\mathbb{F}_p\) (in short Weierstrass form) is the set of affine solutions \((x,y)\in \mathbb{F}_p^2\) to an equation \(y^2 = x^3 + ax + b\), together with a distinguished point \(\mathcal{O}\) at infinity. The set of \(\mathbb{F}_p\)-rational points, together with \(\mathcal{O}\), is denoted by \(E(\mathbb{F}_p)\).

The points on \(E(\mathbb{F}_p)\) form an abelian group under the elliptic-curve addition law, with identity element \(\mathcal{O}\). For affine points \(P_1=(x_1,y_1)\) and \(P_2=(x_2,y_2)\) that are not inverse to each other, the sum \(P_3=P_1+P_2\) can be computed via a slope parameter \(\lambda\): \[x_3 = \lambda^2 - x_1 - x_2, \qquad y_3 = \lambda(x_1 - x_3) - y_1,\] where \(\lambda\) equals the chord slope \(\frac{y_2 - y_1}{x_2 - x_1}\) when \(P_1\neq P_2\), and the tangent slope \(\frac{3x_1^2 + a}{2y_1}\) when \(P_1 = P_2\). Exceptional cases (e.g., \(P_i = \mathcal{O}\) or \(P_2 = -P_1\)) are handled according to the standard group properties.

For an integer \(m\ge 1\), the notation \([m]P\) denotes the \(m\)-fold sum of a point \(P\) with itself, i.e. \([m]P = P + P + \cdots + P\), where \(P\) occurs \(m\) times. This \(m\)-fold sum can be extended to all \(m\in \mathbb{Z}\) by defining \([0]P = \mathcal{O}\) and \([-m]P = [m](-P)\) for \(m \ge 1\). The operation \(m\mapsto [m]P\) is called scalar multiplication and is the core primitive used in elliptic-curve cryptography.

Let \(P\in E(\mathbb{F}_p)\) generates a cyclic subgroup \(\langle P\rangle\) of order \(r\), and let \(Q\in\langle P\rangle\). The elliptic-curve discrete logarithm problem (ECDLP) is to recover the unique \(m\in\{0,1,\ldots,r-1\}\) such that \[Q = [m]P.\] In classical settings, the best generic algorithms require on the order of \(\Theta(\sqrt{p})\) group operations [3], which is exponential in the bit length \(\log_2 p\).

2.3 Shor’s quantum algorithm for ECDLP↩︎

Shor’s discrete-logarithm algorithm for solving ECDLP applies to elliptic curve over any finite abelian group and therefore to \(E(\mathbb{F}_p)\). Let \(n = \lfloor\log_2 p\rfloor + 1\) be the bit-length of \(p\). The quantum procedure uses two exponent registers and one register storing an elliptic curve point.

Firstly, initialize two \((n+1)\)-qubit registers⁵ to be \(|0^{n+1}, 0^{n+1} \rangle\), and apply Hadamard gate to all the qubits to obtain a uniform superposition over pairs \((k, \ell)\in \{0, 1, \ldots, 2^{n+1} - 1\}^2\). Next, coherently compute the elliptic curve group action into an accumulator as \[\label{eqn:shor} \sum_{k, \ell = 0}^{2^{n+1} - 1} |k, \ell \rangle|\mathcal{O} \rangle \;\longmapsto\; \sum_{k, \ell = 0}^{2^{n+1} - 1} |k, \ell \rangle|[k]P + [\ell]Q \rangle.\tag{2}\] After this step, apply Quantum Fourier Transform \(\mathsf{QFT}_{2^{n+1}}\) to both exponent registers and then measure them. Finally, a classical post-processing procedure uses the measurement outcomes to reconstruct the discrete logarithm \(m\) with high probability, as shown in [13].

In terms of resource, the dominant cost arises from the coherent group evaluation, i.e., the double-scalar multiplication on elliptic curve points. To reduce the qubit cost associated with QFT, its full circuit on the exponent registers can be replaced by a semiclassical variant [40]. This semiclassical Fourier transform performs measurements during the computation, reusing qubits and applying conditional phase rotations based on previously observed outcomes. The overall quantum circuits of Shor’s algorithm for ECDLP using QFT (resp. semiclassical QFT) are shown in Figure 2 (resp. Figure 3).

3 Space-Efficient Extended Euclidean Algorithm↩︎

As discussed in previous sections, the dominant cost in designing quantum circuits for solving ECDLP via Shor’s algorithm arises from coherent group additions on elliptic curve points. Among these operations, modular inversion is the most resource-consuming component. In this section, we present a space-efficient and reversible algorithm for modular inversion based on the Extended Euclidean Algorithm. This design is suitable for further translation into a quantum circuit, as detailed in Section 4.

Suppose that \(p > x\) are two positive integers. The well-known Euclidean algorithm can be used to compute the greatest common divisor (GCD) of \(p\) and \(x\). The algorithm initializes \(r_0 := p\) and \(r_1 := x\), and for iterations \(i = 1, 2, \ldots\), it repeatedly divides \(r_{i-1}\) by \(r_i\) to obtain the quotient \(q_i = \lfloor r_{i-1} / r_i \rfloor\) and the remainder \(r_{i+1} = r_{i-1} - q_i r_i\). The process terminates when \(r_{k+1} = 0\), at which point the greatest common divisor of \(p\) and \(x\) equals \(r_k\).

The Extended Euclidean Algorithm (EEA) not only computes the GCD of \(p\) and \(x\), but also outputs the modular inverse \(x^{-1} \bmod p\) when \(p\) and \(x\) are coprime. In addition to computing the sequence \(r_i\), it also initializes \(t_0 := 0\) and \(t_1 := 1\), and for each iteration \(i = 1, 2, \ldots\), updates \(t_{i+1} = t_{i-1} + q_i t_i\) after obtaining \(q_i = \lfloor r_{i-1} / r_i \rfloor\). When the algorithm first encounters \(r_k = 1\), the modular inverse is given by \((-1)^{k-1} t_k \bmod p\).

When realizing the Extended Euclidean algorithm on a quantum computer to compute the modular inverse of \(x\) with a prime modulus \(p\) of \(n\) binary digits, the primary challenge lies in handling superpositions of \(x\). The number of iterations required varies from \(1\) to \(O(n)\) depending on the input, implying that a straightforward implementation would require \(O(n)\) iterations. Each iteration involves divisions and multiplications on \(n\)-digit numbers, leading to an overall gate complexity of \(O(n^3)\).

In what follows, we describe the dedicated four-phase algorithm framework first proposed in [14], followed by our own algorithmic optimizations and the details of our optimized circuit implementation.

3.1 The four-phase algorithm framework↩︎

The four-phase algorithm framework was originally introduced in [14]. It operates on six quantum registers, denoted as \(r_{i-1}\), \(r_i\), \(t_{i-1}\), \(t_i\), \(q_i\), and \(\ell\), where the first five registers correspond to the variables used in the \(i\)-th iteration of EEA. To compute the quotient \(q_i = \lfloor r_{i-1} / r_i \rfloor\), the algorithm performs a binary long-division procedure consisting solely of bit shifts and long additions or subtractions. The algorithm proceeds through the following four phases:

• Phase 1. The register containing \(r_i\) is repeatedly shifted left by one bit, while the shift counter \(\ell\) is incremented at each step. This continues until the inequality \(2^\ell r_i > r_{i-1}\) holds. Conceptually, this phase determines the largest power of two by which \(r_i\) can be multiplied without exceeding \(r_{i-1}\). Equivalently, after the loop terminates, \(\ell_0 := \ell - 1\) gives the highest bit position in the binary representation of \(q_i\).

• Phase 2. The register containing \(r_i\) is then shifted right by one bit per step, with \(\ell\) decremented accordingly. At each step, the registers corresponding to \(r_{i-1}\) and \(q_i\) are updated as \[(r_{i-1} - q' r_i, q') \to \left(r_{i-1} - (q' + 2^\ell q_{i, \ell}) r_i, q' + 2^\ell q_{i, \ell}\right),\] depending on whether \(r_{i-1} - q' r_i\) is at least \(2^{\ell} r_i\). Here \(q'\) denotes the current partial quotient, given by \(q' = 2^{\ell_0} q_{i, \ell_0} + 2^{\ell_0 - 1} q_{i, \ell_0 - 1} + \cdots + 2^{\ell + 1} q_{i, \ell + 1}\), representing the most significant bits accumulated so far in the binary expansion \[q_i = 2^{\ell_0} q_{i, \ell_0} + 2^{\ell_0 - 1} q_{i, \ell_0 - 1} + \cdots + q_{i, 0}.\] This iterative process ultimately yields the transformation \[(r_{i-1}, 0) \to (r_{i-1} - q_i r_i, q_i),\] completing the computation of \(q_i\).

• Phase 3. The register containing \(t_i\) is shifted left by one bit per step, and \(\ell\) is incremented correspondingly. The registers associated with \(t_{i-1}\) and \(q_i\) are updated as \[(t_{i-1} + q'' t_i, q') \to \left(t_{i-1} + (q'' + 2^\ell q_{i, \ell}) t_i, q'\right),\] where the update depends on the bit value \(q_{i, \ell}\) of \(q_i\). After each step, \(q_{i, \ell}\) is reset to \(0\), depending on whether \(t_{i-1} + (q'' + 2^\ell q_{i, \ell}) t_i > 2^{\ell} t_i\). Here \(q'\) and \(q''\) represent the most and least significant portions of the quotient, respectively: \[q' = 2^{\ell_0} q_{i, \ell_0} + 2^{\ell_0 - 1} q_{i, \ell_0 - 1} + \cdots + 2^{\ell} q_{i, \ell}, \quad q'' = 2^{\ell - 1} q_{i, \ell - 1} + 2^{\ell - 2} q_{i, \ell - 2} + \cdots + q_{i, 0}.\] After completing all steps, the registers corresponding to \(t_{i-1}\) and \(q_i\) are updated as \[(t_{i-1}, q_i) \to (t_{i-1} + q_i t_i, 0).\]

• Phase 4. Finally, the register containing \(t_i\) is repeatedly shifted right by one bit, and \(\ell\) is decremented at each step. The process terminates once \(\ell = 0\).

Upon completion of all four phases, SWAP operations are applied between the register pairs corresponding to \((r_{i-1}, r_i)\) (which is currently \((r_{i+1}, r_i)\)) and the register pairs corresponding to \((t_{i-1}, t_i)\) (which is currently \((t_{i+1}, t_i)\)), respectively. This completes one full iteration of the EEA implementation.

We emphasize that, during the execution of this four-phase algorithm, the correspondence between the iteration index in EEA and the phase number may vary depending on the input value \(x\). In other words, the algorithm’s internal progression through iterations and phases is input-dependent. To avoid ambiguity in the subsequent descriptions, we use “step” to represent any sub-iteration occurring within any phase of an EEA iteration. The example in Table 3 illustrates how the step status evolves for different input values under this four-phase framework.

Although the sequence of step statuses differs for each input \(x\), the total number of steps required to reach an index \(k\) such that \(r_{k-1} = 1, r_k = 0\) can be bounded within the interval \([4n, 4\lceil cn\rceil]\) with \(c = 1 / \log_2\left(\frac{\sqrt{5} + 1}{2}\right)\), as formally proven in Appendix 7.1. This bounded-step property is crucial for quantum implementation: it implies that a quantum circuit corresponding to one “step” can be repeated at most \(4\lceil cn\rceil \approx 5.76n\) times to definitely obtain the modular inverse of any input \(x\) in superposition. Since each step involves arithmetic operations such as shifts, additions, and subtractions, which require \(O(n)\) quantum gates, the overall gate complexity of the algorithm is reduced to \(O(n^2)\).

Keeping the above discussion in mind, the forward space-efficient EEA subroutine for computing the modular inverse \(x^{-1} \bmod p\), where \(p\) is a prime represented with \(n\) binary digits and \(x \in \{1, 2, \ldots, p - 1\}\), is summarized in Algorithm 4. In this context: (i) the register allocation strategy is described in Section 3.2; (ii) Algorithm 7 provides the optimized stepwise iteration designed to minimize gate complexity and ensure quantum reversibility, as further discussed in Sections 3.2 and 3.3; (iii) when \(x > p/2\), we run the EEA on \(p-x\) instead of \(x\) and record this choice in the iteration-parity qubit.

3.2 Space-efficient algorithm by register sharing↩︎

In [14], the authors introduced the concept of register sharing. The central idea of register sharing is that, during the execution of the EEA, the sequence \(\{r_i\}\) is monotonically decreasing while the sequence \(\{t_i\}\) is monotonically increasing. This complementary behavior allows both values to occupy the same quantum register at different stages of computation, thereby reducing the overall space requirement. The identity \[r_{i-1}t_i + r_it_{i-1} = p\] implies that two quantum registers, each consisting of \((n + 2)\) qubits, are sufficient: one to store the pair \((r_{i-1}, t_i)\) and the other to store \((r_i, t_{i-1})\).

We extend this register-sharing idea further. Specifically, we observe that a single quantum register of \((n + 2)\) qubits can be used to store the triple \((r_{i-1}, t_i, q_i)\) simultaneously, including the intermediate states that arise during phases 2 and 3 of the algorithm. These phases are responsible for computing \(q_i = \lfloor r_{i-1} / r_i \rfloor\) and updating the variables \[r_{i-1} \leftarrow r_{i-1} - q_i r_i, t_{i-1} \leftarrow t_{i-1} + q_i t_i.\] The detailed allocation of quantum registers is described as follows, and illustrated in Figure 5.

• Work1 register (of \((n + 3)\) qubits). The left-most \(\ell_t + 1\) qubits encode the value \(t := t_i\) in little-endian order (here we append a zero to the rightmost position of \(t\) in order to simplify the circuit implementation). The following \(\ell_q\) qubits store the intermediate quotient value \(q := q'\) (only the effective most significant bits) in phases 2 and 3, in big-endian order. The remaining qubits hold the value \(r := r_{i-1}\) (or its updated form \(r := r_{i-1} - q'r_i\)) in big-endian order.

• Work2 register (of \((n + 3)\) qubits). The right-most \(\ell_{r'}\) qubits store \(r' := r_i\) in big-endian order, while the remaining qubits store the value \(t' := t_{i-1}\) (and its intermediate update \(t' := t_{i-1} + q''t_i\)) in little-endian order. During phases 2 and 3, this register may be circularly shifted left by \(\ell_s\) positions. In such cases, the value \(t'\) may span both ends of the register, effectively splitting into two contiguous parts.

• Length registers. Four auxiliary registers are used to manage variable-length storage. Each of them contains \(\lfloor \log_2 n\rfloor + 1\) qubits. They store the length indicators \(\ell_t, \ell_q, \ell_{r'}\), and the shift counter \(\ell_s\) respectively. These Length registers mark the logical boundaries within the Work1 and Work2 registers and enable coherent manipulation of superposed inputs of varying lengths.

• Control registers. Two single-qubit Phase registers indicate the current phase of the four-phase algorithmic framework, and one single-qubit Iter register that records the parity of the current EEA iteration number. Additionally, there are two auxiliary single-qubit registers, Sign and Ctrl, used for intermediate flag and control operations.

We next describe the behavior of the system when performing comparison, addition, and subtraction operations on the register pairs \((r, r')\) and \((t, t')\). The arithmetic between \(r\) and \(r'\) is relatively straightforward: a left shift by \(\ell_s\) positions corresponds to multiplying \(r'\) by \(2^{\ell_s}\). In contrast, the arithmetic involving \(t\) and \(t'\) requires a more careful interpretation. A convenient way to view this operation is that a left shift of \(\ell_s\) positions can be regarded as dividing \(t'\) by \(2^{\ell_s}\), where the integer part is placed in the left-most portion of Work2, and the fractional part occupies the right-most portion. When \(t\) is added to the integer part of \(t'\) (which is properly aligned), the arithmetic relation can be expressed as \(2^{-\ell_s}t' + t = 2^{-\ell_s}(t' + 2^{\ell_s}t)\). Thus, the expression \(t' + 2^{\ell_s}t\) represents the desired result, corresponding to a left shift by \(\ell_s\) positions.

With this register allocation, one step of our space-efficient EEA proceeds as in Algorithm 6. To illustrate how the proposed space-efficient EEA operates in practice, we also provide a concrete execution example for \(p = 37\) and \(x = 13\), shown in Table 4.

For each step, Table 4 shows how the contents of the two Work registers evolve and how different variables are mapped onto Work1 and Work2 under the register-sharing strategy. In particular, the variable \(t'\) stored in Work2 is divided into two parts that occupy the left-most and right-most portions of the register. The division symbols are not explicitly implemented in the quantum circuit; they are all illustrative and inferred from the corresponding Length registers, used to visualize the register allocation. In the actual quantum implementation, all registers are in superposition, and the location of these division symbols may vary across different input values.

3.3 Algorithmic optimizations↩︎

The baseline implementation of one step, as described in the previous subsection, was constructed to be fully reversible, ensuring that every state transformation can be realized as a unitary operation on a quantum computer. However, this direct implementation contains multiple redundant operations that unnecessarily increase both the circuit depth and gate count. In this subsection, we present a series of algorithmic optimizations applied to the baseline design in order to reduce the quantum circuit depth and overall gate complexity.

3.3.0.1 Removing redundant arithmetic and shift operations.

In the baseline version, several arithmetic and shift operations between different phases are functionally redundant. Specifically, we have: \[\begin{align} \text{In phases 1 and 2:} \quad & \text{comparison, addition, subtraction between } (r, 2^{\ell_s}r'); \\ \text{In phases 3 and 4:} \quad & \text{comparison, addition, subtraction between } (t', 2^{\ell_s}t); \\ \text{In phases 1 and 3:} \quad & \text{a one-position left shift on } \texttt{Work2}; \\ \text{In phases 2 and 4:} \quad & \text{a one-position right shift on } \texttt{Work2}. \\ \end{align}\] By combining the control conditions of these operations (or equivalently, the corresponding quantum control wires), we can eliminate redundant operations from the circuit. This optimization results in a total of two groups of location-controlled addition/subtraction operations and two location-controlled swaps in one step. Here, location-control refers to arithmetic operations applied conditionally on specific positions of the two Work registers, with the active positions indicated by the Length registers.

3.3.0.2 Merging location-controlled swaps.

To further decrease the circuit depth and gate count, we observe that the two location-controlled swaps appearing in phases 2 and 3 act on the same qubit position of Work1. We merge them into a single swap controlled by \(\texttt{Phase1}\oplus\texttt{Phase2}\). The required update of \(\ell_q\) depends on the phase: \(\ell_q\) is increased in phase 2 and decreased in phase 3.

3.3.0.3 Algorithm pseudocode and overall complexity.

After applying the above optimizations, the overall asymptotic quantum resource estimation per step is summarized as follows:

• Five location-controlled arithmetic operations, including one swap, two additions, and two subtractions; along with four length updates at the termination step of an EEA iteration. Each of these operations costs \(O(n)\) gates in the implementation presented in Section 4.

• Four position shifts and one \((n + 3)\)-qubit SWAP, each requiring \(O(n)\) quantum gates.

With these optimizations, one step of our space-efficient EEA proceeds as in Algorithm 7.

4 Quantum Circuit Implementation of Modular Inversion↩︎

In this section, we present the explicit quantum circuit implementation of a single step of the space-efficient EEA with register sharing, as described in Algorithm 7. Throughout the section, we use the same quantum register notation as in the algorithm.

The full circuit construction is, however, too complex to be depicted within a small number of circuit diagrams. This difficulty is mainly due to the presence of location-controlled arithmetic operations, which are highly non-standard. To present the construction in a relatively more explicit manner, we first describe the overall circuit structure in Section 4.1, where the location-controlled arithmetic operations are treated as circuit blocks; we then provide a detailed implementation of these operations in Section 4.4. In all circuit diagrams, the black triangle denotes the output wire that carries the result of the corresponding circuit block; and we denote \(\ell = \lfloor \log_2 n \rfloor\) for convenience.

4.1 Overall circuit implementation of one step↩︎

According to Algorithm 7, the overall circuit implementation of a single iteration of our space-efficient EEA is shown in Figures 8 and 9, presented in a continuous layout. Both circuit diagrams are divided into several algorithmic components, indicated by dashed boxes. Each component corresponds exactly to one arithmetic block specified in Algorithm 7.

In both circuit diagrams, \(\mathsf{Shift}\) denotes a position shift of the workspace: a positive value represents a left shift, while a negative value represents a right shift. The circuit blocks \(\mathsf{Add}\), \(\mathsf{Sub}\), and \(\mathsf{Swap}\) denote location-controlled addition, subtraction, and swap operations, respectively. At the end of each EEA iteration, the circuit block labeled \(\mathsf{SWAP}\) represents a full SWAP operation applied to all qubits in the registers Work1 and Work2; this block is distinct from the \(\mathsf{Swap}\) block to avoid ambiguity. Finally, the \(\mathsf{Len}\) block denotes the update operations on the length registers.

4.2 Step-dependent active windows↩︎

To reduce the quantum gate complexity for implementing our space-efficient EEA, we introduce step-dependent active windows for each location-controlled operation. As illustrated in the figures of the previous subsection, we define \(k\) and \(K\) as known bounds on the active indices of the Work registers.

For instance, at step \(T\), a location-controlled Swap circuit acts on the \((\ell_t + \ell_q + 1)\)-th qubit of the Work1 register. Over all possible inputs \(x\) used to compute the modular inverse \(x^{-1} \bmod p\), the quantity \(\ell_t + \ell_q + 1\) is bounded below by \(k := k(T)\) and above by \(K := K(T)\). Therefore, applying location-controlled operations to qubits in the Work1 register with indices outside the interval \([k, K]\) is unnecessary. We refer to this interval as the active window.

We next specify the step-dependent active windows for each type of location-controlled operation. All bounds are taken over all possible inputs \(x\), namely, those inputs \(x\) for which the location-controlled circuits are activated by the outer control qubits. The constant \(c\) equals to \(1 / \log_2\left(\frac{\sqrt{5} + 1}{2}\right)\). We defer the proofs to Appendix 7.2.

• Location-controlled addition/subtraction on \(r\)’s. These operations act on qubits indexed from \((\ell_t + \ell_q + 2)\) to \((n + 3 - \ell_s)\). The upper bound \(K_1 = K_1(T) = n + 3\); the lower bound \(k_1 = k_1(T)\) is defined by \[\ell_t + \ell_q + 2 \ge k_1(T) := \max\left\{ \left\lceil \frac{T - n - 2}{4c - 1} \right\rceil, 1 \right\} + 2.\]

• Location-controlled swap. These operations act on the \((\ell_t + \ell_q + 1)\)-th qubit. The two-sided bounds are defined by \[\begin{align} \ell_t + \ell_q + 1 & \ge k_2(T) := \max\left\{\left\lceil \frac{T - 3(n + 2)}{4c - 3} \right\rceil, 1\right\} + 1, \\ \ell_t + \ell_q + 1 & \le K_2(T) := \min\left\{\left\lfloor T/2 \right\rfloor + 2, n + 2\right\}. \end{align}\]

• Location-controlled addition/subtraction on \(t\)’s. These operations act on the first \((\ell_t + 1)\) qubits. This is a one-sided controlled operation, the upper bound \(K_3(T)\) is defined by \[\ell_t + 1 \le K_3(T) := \min\left\{\left\lceil T/4 \right\rceil + 1, n + 1\right\}.\]

• Length-update circuit for updating \(\ell_t\). We execute the length-update circuit only at step indices \(T\) that are multiples of four. This circuit acts on qubits indexed from \(\ell_t\) to \((n + 3 - \ell_{r'})\), and the corresponding two-sided active window is defined by \[\begin{align} \ell_t & \ge k_4(T) := \max\left\{\left\lceil \frac{T - 4(n + 2)}{4c - 4} \right\rceil, 1\right\}, \\ n + 3 - \ell_{r'} & \le K_4(T) := \min\left\{T/4 + 3, n + 3\right\}. \end{align}\]

• Length-update circuit for updating \(\ell_{r'}\). Let \(\ell_{t}^*, \ell_{r'}^*\) denote the updated value of \(\ell_t, \ell_{r'}\) after the length update. This circuit acts on qubits indexed from \(\ell_t^* + 2\) to \((n + 4 - \ell_{r'}^*)\), and the corresponding two-sided active window is defined by \[\begin{align} \ell_t^* + 2 & \ge k_5(T) := \left\lceil T/(4c) \right\rceil, \\ n + 4 - \ell_{r'}^* & \le K_5(T) := \min\left\{T/4 + 4, n + 3\right\}. \end{align}\]

4.3 Unary iteration↩︎

We will use unary iteration [41] to implement location-controlled operations on a known interval of the two Work registers. Let \(\mathsf{L}\) be a Length register promised to store a value \(a\in\{k,k+1,\ldots,K\}\), let \(\mathsf{W}\) be a Work register, and let \(c\) be an optional external control qubit. The operation has the form \[\begin{align} \mathcal{U}_{[k,K]} &= |0 \rangle\!\langle 0|_{c}\otimes I + |1 \rangle\!\langle 1|_{c}\otimes \sum_{j=k}^{K} |j \rangle\!\langle j|_{\mathsf{L}}\otimes U_j , \end{align}\] where \(U_j\) is a unitary operation on \(\mathsf{W}\) selected by the value \(j\). Equivalently, the operation performs \(|c \rangle|a \rangle|\psi \rangle \mapsto |c \rangle|a \rangle U_a^{\,c}|\psi \rangle\) for all \(a\in [k, K]\).

The main primitive used by unary iteration is a reversible AND. The compute and uncompute forms of this gate are shown in Figure 10. In the Toffoli/CNOT counting convention used here, computing an AND costs one Toffoli gate, while uncomputing an AND using measurement costs one CNOT gate with no Toffoli gates.

For a general interval, unary iteration can be viewed as a binary tree whose leaves are the labels \(k,k+1,\ldots,K\). Each internal node stores a subset of labels. If the current node has control bit \(g\), we choose the most significant bit position \(b\) that is not constant on its labels, thereby separating them into two nonempty subsets according to the value of \(A_b\). For an increasing-order traversal, we first compute \(h=g(1-A_b)\) with one reversible AND, use \(h\) as the control for the \(A_b=0\) child, then switch the same temporary bit by a CNOT, \(h\gets h\oplus g\), so that \(h=gA_b\) controls the \(A_b=1\) child. After the second child is processed, \(h\) is uncomputed. At a leaf \(j\), the current control bit is exactly \[\begin{align} e_j=c[a=j], \end{align}\] and the circuit applies \(U_j\) controlled on \(e_j\). For a decreasing-order traversal, the two children are visited in the opposite order. Figure 11 illustrates this construction for the interval \(\{5,6,7,8\}\).

If \(M=K-k+1\), the tree has \(M\) leaves and \(M-1\) internal nodes. Thus the selection logic contributes \(M-1=K-k\) Toffoli gates, while the leaf operations contribute the cost of the controlled \(U_j\) gates themselves. For \(M\ge2\), the recursion depth, and hence the number of temporary control qubits, is at most \(\left\lceil \log_2(M-1)\right\rceil+1\). For the trivial case \(M=1\), no temporary control qubit is needed. This replaces independent equality tests for all \(j\), which would cost \(O(M\log_2 n)\) Toffoli gates for an \(O(\log_2 n)\)-bit index register, by a linear-size selection circuit using only \(O(\log_2 M)\) temporary control qubits.

4.4 Location-controlled operations↩︎

In this subsection, the two Work registers are indexed, from left to right, by \(u_1, u_2, \ldots, u_{n+3}\) and \(v_1, v_2, \ldots, v_{n+3}\), respectively.

4.4.0.1 Location-controlled \(\mathsf{Swap}\) circuit.

We first consider the location-controlled swap operation appearing in Figure 8. The goal is to swap the Sign qubit with the \((\ell_t+\ell_q+1)\)-th qubit of Work1, while the whole operation is controlled by an external qubit Ctrl. Let \(J = \ell_t+\ell_q+1\), where \(k\) and \(K\) are known constants such that \(k\le J\le K\). After temporarily storing \(J\) in the \(\ell_q\) register, the location-controlled swap can be written as \[\begin{align} \mathsf{Swap}_{[k,K]} &= |0 \rangle\!\langle 0|_{\texttt{Ctrl}}\otimes I + |1 \rangle\!\langle 1|_{\texttt{Ctrl}} \otimes \sum_{j=k}^{K} |j \rangle\!\langle j|_{\ell_q} \otimes \mathsf{SWAP}\!\left(\texttt{Sign},u_j\right), \end{align}\] where the subscript \(\ell_q\) denotes the temporary register storing \(J\).

This operation can be implemented directly using unary iteration. We first reversibly transform the \(\ell_q\) register as \(|\ell_t \rangle|\ell_q \rangle \longmapsto |\ell_t \rangle|\ell_t+\ell_q+1 \rangle\). Using Ctrl as the global control, pruned unary iteration over the labels \(k,k+1,\ldots,K\) then produces, one value at a time, the control bit \(e_j=\texttt{Ctrl}\land [J=j]\). When this unary control is active, we swap Sign and \(u_j\). After it finishes we restore the \(\ell_q\) register to its original value. Figure 12 illustrates this construction for the example \(k=5\) and \(K=8\).

The unary iterator contributes \(K-k+O(1)\) Toffoli gates and \(2(K-k)+O(1)\) CNOT gates, the controlled swaps contribute \(K-k+O(1)\) Toffoli gates and \(2(K-k)+O(1)\) CNOT gates. The reversible transformations of the \(\ell_q\) register contribute \(O(\log_2 n)\) Toffoli/CNOT gates. Thus the location-controlled \(\mathsf{Swap}\) circuit uses \(2(K-k)+O(\log_2 n)\) Toffoli gates and \(4(K-k)+O(\log_2 n)\) CNOT gates.

4.4.0.2 Location-controlled \(\mathsf{Add, Sub}\) circuit.

We next describe the location-controlled addition and subtraction circuits. As a representative example, consider the operation \[\begin{align} (\texttt{Sign},r)\gets (\texttt{Sign},r)-2^{\ell_s}r', \label{eq:lc95sub95example} \end{align}\tag{3}\] where Sign records the sign of the subtraction result. In terms of physical positions in the two Work registers, this operation acts only on the interval \[\begin{align} L &= \ell_t+\ell_q+2, & R &= n+3-\ell_s . \end{align}\] That is, the relevant qubits are \(u_L,\ldots,u_R\) in Work1 and \(v_L,\ldots,v_R\) in Work2; outside this interval all qubits are left unchanged. The shift by \(\ell_s\) is already reflected in the endpoint \(R=n+3-\ell_s\), so the aligned bits \(v_L,\ldots,v_R\) represent the contribution of \(2^{\ell_s}r'\) to the subtraction. For a known active window \([k,K]\), we promise that \(k\le L\le R\le K\).

If the endpoints \(L\) and \(R\) were fixed, the subtraction could be implemented by a ripple-carry subtractor on the qubit pairs \((u_j,v_j)\) for \(j\in[L,R]\) with a dedicated carry qubit \(c\) initialized to \(|0 \rangle\). For the subtraction in Equation 3 , we first apply the \(\mathsf{UMA}^{\dagger}\) cells from high to low, update Sign from the carry qubit, and then apply the \(\mathsf{MAJ}^{\dagger}\) cells from low to high to uncompute the carry.

It remains to coherently select the interval \([L,R]\). The endpoint registers storing \(L\) and \(R\) are obtained from the length registers by reversible affine transformations, which are undone after the arithmetic block. The circuit uses one accumulator bit \(s\), initialized to \(|0 \rangle\). In the \(\mathsf{UMA}^{\dagger}\) pass, the circuit scans the physical positions from high to low, namely \(j=K,K-1,\ldots,k\). For each scanned position \(j\), pruned unary iteration on the endpoint registers coherently produces the two local controls \[\begin{align} \lambda_j &= \texttt{Ctrl}\land [R=j], & \mu_j &= \texttt{Ctrl}\land [L=j]. \end{align}\]

The circuit first updates the accumulator by \(s \gets s\oplus \lambda_j\). If the updated value of \(s\) is \(1\), the circuit applies \(\mathsf{UMA}^{\dagger}(c,u_j,v_j)\); otherwise it does nothing on \((c,u_j,v_j)\). After this controlled arithmetic cell, the circuit updates the accumulator by \(s \gets s\oplus \mu_j\). Therefore, when the scan reaches \(j=R\), the bit \(\lambda_j\) flips \(s\) from \(0\) to \(1\) before the arithmetic cell, so the \(\mathsf{UMA}^{\dagger}\) cell at \(j=R\) is applied. For positions strictly inside the interval, the accumulator remains equal to \(1\), so the corresponding arithmetic cells are also applied. When the scan reaches \(j=L\), the \(\mathsf{UMA}^{\dagger}\) cell is still applied, and then \(\mu_j\) flips \(s\) back to \(0\). The same update rule is used for every scanned position \(j\in[k,K]\). Before the active interval is reached, all arithmetic cells are disabled, so the carry qubit \(c\) remains equal to \(0\) at the interval entrance.

After the \(\mathsf{UMA}^{\dagger}\) pass, \(c\) stores the carry bit of the selected subtraction. We update Sign by \[\begin{align} \texttt{Sign}\gets \texttt{Sign}\oplus c. \end{align}\]

The \(\mathsf{MAJ}^{\dagger}\) pass visits \(j=k,k+1,\ldots,K\). At each position, the accumulator is first updated by \(s \gets s\oplus \mu_j\). If the updated value of \(s\) is \(1\), the circuit applies \(\mathsf{MAJ}^{\dagger}(c,u_j,v_j)\). It then updates the accumulator by \(s \gets s\oplus \lambda_j\). Therefore the \(\mathsf{MAJ}^{\dagger}\) cells are applied exactly for \(j\in[L,R]\), and \(s\) and \(c\) are restored to \(|0 \rangle\) at the end.

Figure 13 illustrates the complete pattern for the example \(k=5\) and \(K=7\).

Finally, we explain how the controlled \(\mathsf{MAJ}\) and \(\mathsf{UMA}\) cells used above are implemented. We do not add the location-control bit to every gate in the cell; only the Toffoli gate that updates the carry qubit is controlled. Figure 14 shows the corresponding controlled cells.

The gate count consists of the following contributions:

• Generating \([L=j]\) and \([R=j]\) during both scans requires four applications of unary iteration. They use \(4(K-k)+O(1)\) Toffoli gates and \(8(K-k)+O(1)\) CNOT gates in total.

• Applying one controlled \(\mathsf{UMA}^{\dagger}\) cell at each position in the high-to-low scan uses \(4(K-k)+O(1)\) Toffoli gates and \(2(K-k)+O(1)\) CNOT gates.

• Applying one controlled \(\mathsf{MAJ}^{\dagger}\) cell at each position in the low-to-high scan uses \(3(K-k)+O(1)\) Toffoli gates and \(2(K-k)+O(1)\) CNOT gates.

• Computing \(L\) and \(R\) from \(\ell_q\) and \(\ell_s\), and subsequently restoring these registers, uses \(O(\log_2 n)\) Toffoli and CNOT gates.

Adding these terms, the location-controlled \(\mathsf{Sub}\) circuit implementing Equation 3 uses \(11(K-k)+O(\log_2 n)\) Toffoli gates and \(12(K-k)+O(\log_2 n)\) CNOT gates.

4.4.0.3 Location-controlled length-update circuit.

Finally, we describe the length-update circuit. We focus on updating \(\ell_t\); the circuit for updating \(\ell_{r'}\) is analogous. At the end of one EEA iteration, after the full swap of Work1 and Work2, the left part of Work1 stores the current value of \(t\), while the left part of Work2 stores the current value of \(t'\). Let \(L_{\mathrm{new}} = \operatorname{len}(t), L_{\mathrm{old}} = \operatorname{len}(t')\). Since the value stored in \(\ell_t\) before the update is \(L_{\mathrm{old}}\), it suffices to implement \[\begin{align} \ell_t \gets \ell_t\oplus L_{\mathrm{old}}\oplus L_{\mathrm{new}} . \end{align}\] Thus the length update is reduced to two serial constant-XOR writes: first XOR the old length, and then XOR the new length.

We first describe the subroutine for XORing \(L_{\mathrm{new}}\) into \(\ell_t\). This subroutine finds the highest valid nonzero position among the qubits \(u_k,\ldots,u_K\). Only positions in the left region not occupied by \(r'\) should be inspected. Let \(J=n+3-\ell_{r'}\) be the right boundary of this valid region with the promise \(k\le \ell_t \le J\le K\) from the active window under consideration. For each \(j\in[k,K]\), define the masked bit \[\begin{align} a_j=\texttt{Ctrl}\land [j\le J]\land u_j . \end{align}\] Also define bits \[\begin{align} z_j=\bigwedge_{h=j}^{K}\neg a_h . \end{align}\] Thus \(z_j=1\) means that no valid nonzero bit occurs among positions \(j,j+1,\ldots,K\). If the highest valid nonzero position is \(m\), then \[\begin{align} z_K=\cdots=z_{m+1}=1, \qquad z_m=\cdots=z_k=0 . \end{align}\] If no valid nonzero bit exists in the window, then all \(z_j\) are equal to \(1\).

The highest position can be written using a telescoping XOR. We first XOR the classical constant \(K\) into the length register. Then, for \(j=K,K-1,\ldots,k+1\), whenever \(z_j=1\), we change the current candidate from \(j\) to \(j-1\) by XORing the classical constant \(j\oplus(j-1)\). Finally, if \(z_k=1\), then the entire window contains no valid nonzero bit, and we clear the remaining candidate \(k\) by XORing \(k\). Equivalently, the value written by the subroutine is \[\begin{align} L_{\mathrm{new}} = K \oplus \bigoplus_{j=k+1}^{K} z_j\cdot \bigl(j\oplus(j-1)\bigr) \oplus z_k\cdot k , \end{align}\] where a term such as \(z_j\cdot C\) means that the classical bit string \(C\) is XORed into the length register controlled on \(z_j\). If the highest valid nonzero position is \(m\), the expression telescopes to \(m\). If no such position exists, it telescopes to zero.

It remains to implement the constant writes controlled by the bits \(z_j\) without storing all of them in clean ancillae. Borrow dirty qubits \(g_k,\ldots,g_K\), which will be restored at the end. For \(j>k\), let \(V_j\) denote the Clifford operation that XORs the classical constant \(j\oplus(j-1)\) into the length register, and let \(V_k\) denote the operation that XORs \(k\). Since each \(V_j\) is a product of CNOT gates, \(V_j^2=I\). Assume for the moment that we can perform the transformation \[\begin{align} g_j\gets g_j\oplus z_j \qquad (j=k,\ldots,K). \end{align}\] Then the desired controlled write is implemented by placing this transformation between two uses of \(V_j\) controlled by the borrowed qubit: \[\begin{align} V_j^{g_j},\qquad g_j\gets g_j\oplus z_j,\qquad V_j^{g_j}. \end{align}\] Indeed, if the initial value of the borrowed qubit is \(G_j\), then the two controlled writes are \[\begin{align} V_j^{G_j}V_j^{G_j\oplus z_j}=V_j^{z_j}, \end{align}\] so the unknown initial value cancels. After all constant writes are completed, we perform the same transformation again to restore every \(g_j\) to its original value. Figure 15 illustrates this method for the example \(k=5\) and \(K=7\).

We now explain how to implement the transformation \(g_j\gets g_j\oplus z_j\) for all \(j\). The recurrence is \[\begin{align} z_K &= \neg a_K, & z_j &= \neg a_j\, z_{j+1} \qquad (j<K). \end{align}\] To implement this transformation, first apply, for \(j=k,k+1,\ldots,K-1\), the Toffoli gates \(g_j\gets g_j\oplus (\neg a_j)g_{j+1}\). Then apply the base CNOT gate \(g_K\gets g_K\oplus \neg a_K\). Finally apply the same Toffoli gates in reverse order, for \(j=K-1,K-2,\ldots,k\). For a fixed \(j<K\), the two Toffoli gates acting on \(g_j\) are separated by the transformation \(g_{j+1}\gets g_{j+1}\oplus z_{j+1}\). Therefore their combined action on \(g_j\) is \[\begin{align} g_j &\gets g_j \oplus (\neg a_j)g_{j+1} \oplus (\neg a_j)(g_{j+1}\oplus z_{j+1}) \notag\\ &= g_j\oplus (\neg a_j)z_{j+1} = g_j\oplus z_j . \end{align}\] The bit \(a_j\) is produced only locally when the corresponding gate is applied. During a scan of the window, unary iteration on the boundary register supplies the temporary range control \[\begin{align} b_j=\texttt{Ctrl}\land [j\le J]. \end{align}\] The circuit then computes \(a_j=b_j\land u_j\) into one clean temporary qubit, uses it as the negative control in the corresponding Toffoli or CNOT, and immediately uncomputes it. The required range controls are supplied by one scan in the order \(k,k+1,\ldots,K\) and one scan in the reverse order \(K,K-1,\ldots,k\).

Figure 16 shows this transformation for the example \(k=5\) and \(K=7\). The boundary value is computed in place on the \(\ell_{r'}\) register, and the temporary bit \(a\) is created only when the corresponding update gate is applied.

To update \(\ell_t\), we invoke this subroutine twice. First we use the analogous construction with \(v_j\) in place of \(u_j\) and borrow the qubits \(u_j\) as the dirty register \(g_j\), which XORs \(L_{\mathrm{old}}\) into \(\ell_t\). Then we use the construction described above and borrow the qubits \(v_j\) as the dirty register \(g_j\), which XORs \(L_{\mathrm{new}}\) into \(\ell_t\). The two calls are serial, and the borrowed dirty qubits are restored after each call.

We now give the explicit resource count. First consider one application of \(g_j\gets g_j\oplus z_j\) for all \(j\in[k,K]\). Its gate count has three contributions:

• The forward and reverse unary iterations use \(2(K-k)+O(1)\) Toffoli gates and \(4(K-k)+O(1)\) CNOT gates.

• The forward and reverse applications of \(g_j\gets g_j\oplus(\neg a_j)g_{j+1}\) contribute \(2(K-k)\) Toffoli gates in total, while the update at \(j=K\) contributes one CNOT gate.

• The temporary bit \(a_j=b_j\land u_j\) is computed once in each direction and uncomputed immediately after use. Over both directions, this uses \(2(K-k)+O(1)\) Toffoli gates and \(2(K-k)+O(1)\) CNOT gates.

Thus one application of \(g_j\gets g_j\oplus z_j\) uses \(6(K-k)+O(\log_2n)\) Toffoli gates and \(6(K-k)+O(\log_2n)\) CNOT gates.

To XOR either \(L_{\mathrm{old}}\) or \(L_{\mathrm{new}}\) into \(\ell_t\), the transformation \(g_j\gets g_j\oplus z_j\) is first applied between the two sets of controlled constant XORs and is then applied again to restore the qubits \(g_j\). These two applications use \(12(K-k)+O(\log_2n)\) Toffoli gates and \(12(K-k)+O(\log_2n)\) CNOT gates. Each set of controlled constant XORs uses \(2(K-k)+O(\log_2 n)\) CNOT gates and no Toffoli gates. Therefore, XORing one of the two lengths into \(\ell_t\) uses \(12(K-k)+O(\log_2n)\) Toffoli gates and \(16(K-k)+O(\log_2n)\) CNOT gates.

The complete length update performs this procedure once for \(L_{\mathrm{old}}\) and once for \(L_{\mathrm{new}}\). Its total cost is \(24(K-k)+O(\log_2n)\) Toffoli gates and \(32(K-k)+O(\log_2n)\) CNOT gates.

The construction uses exactly \(K-k+1\) dirty auxiliary qubits, all of which are restored to their initial states. The same clean auxiliary qubits can be reused throughout the circuit: one stores \(a_j\), one stores \(b_j\), and unary iteration requires at most \(\lceil\log_2(K-k)\rceil+1\) additional clean qubits for \(K-k\ge 1\). Thus the construction uses at most \(\lceil\log_2(K-k)\rceil+3\) clean auxiliary qubits.

5 Affine Point Addition with Mid-Circuit Measurement↩︎

In the previous sections, we constructed a space-efficient modular inversion circuit based on the extended Euclidean algorithm. The inversion circuit uses two \(n\)-qubit field registers together with \(O(\log_2 n)\) auxiliary qubits. In this section, we explain how to incorporate this component into an affine point-addition circuit. By allowing mid-circuit measurements and classical feed-forward operations, the affine point-addition block can be implemented using only three \(n\)-qubit field registers, plus the \(O(\log_2 n)\) auxiliary qubits required by the EEA inversion subroutine.

The overall circuit is shown in Figure 17. The three main quantum registers are denoted by \(X\), \(Y\), and \(A\), each storing an element of \(\mathbb{F}_p\). The remaining \(O(\log_2 n)\) EEA ancilla qubits are not shown explicitly in the figure.

The constant additions, subtractions, negations, and squarings in Figure 17 are standard in-place modular operations. The only non-standard components are the in-place division and multiplication subroutines. They have the following abstract interfaces: \[\begin{align} \operatorname{IDiv}:\quad |x \rangle_X|y \rangle_Y|0 \rangle_A &\longmapsto |x \rangle_X|y/x \rangle_Y|0 \rangle_A, \qquad x\ne 0, \tag{4} \\ \operatorname{IMul}:\quad |x \rangle_X|y \rangle_Y|0 \rangle_A &\longmapsto |x \rangle_X|xy \rangle_Y|0 \rangle_A, \qquad x\ne 0. \tag{5} \end{align}\]

It remains to explain how the in-place maps in Equations 4 and 5 can be implemented with only three field registers. The constructions are similar, so we describe the in-place division subroutine in detail. Let \(S\) denote the \(O(\log_2 n)\) auxiliary register used by the EEA inversion circuit. The goal is to implement \[\begin{align} |x \rangle_X|y \rangle_Y|0 \rangle_A|0 \rangle_S \longmapsto |x \rangle_X|y/x \rangle_Y|0 \rangle_A|0 \rangle_S, \qquad x\ne 0. \end{align}\]

First, run the forward EEA inversion circuit on \(X\), using \(A\) as the large clean workspace and \(S\) as the small auxiliary register: \[\begin{align} |x \rangle_X|y \rangle_Y|0 \rangle_A|0 \rangle_S \longmapsto |x^{-1} \rangle_X|y \rangle_Y|0 \rangle_A|\Gamma(x) \rangle_S. \end{align}\] Here \(|\Gamma(x) \rangle_S\) denotes the intermediate EEA state that is kept until the inverse EEA circuit is applied. Next, use a standard modular multiplication to write the quotient into \(A\): \[\begin{align} |x^{-1} \rangle_X|y \rangle_Y|0 \rangle_A \longmapsto |x^{-1} \rangle_X|y \rangle_Y|y/x \rangle_A. \end{align}\] At this point \(A\) is no longer clean, and therefore cannot be used as the large workspace for the inverse EEA circuit. Instead, we recycle the register \(Y\) by measurement. Apply \(H^{\otimes n}\) to \(Y\) and measure it in the computational basis. If the classical outcome is \(b\in\{0,1\}^n\), the remaining quantum state acquires the phase \((-1)^{b\cdot y}\), where the dot product is over \(\mathbb{F}_2\). The measured register \(Y\) is then reset to \(|0 \rangle\).

Now \(Y\) is a clean \(n\)-qubit register, so it can be used as the large workspace for the inverse EEA circuit. Applying the inverse EEA circuit gives \[\begin{align} (-1)^{b\cdot y} |x^{-1} \rangle_X|0 \rangle_Y|y/x \rangle_A|\Gamma(x) \rangle_S \longmapsto (-1)^{b\cdot y} |x \rangle_X|0 \rangle_Y|y/x \rangle_A|0 \rangle_S. \label{eq:idiv95step95inverse95eea} \end{align}\tag{6}\] The phase in Equation 6 is removed by recomputing the measured value \(y\) from \(x\) and \(y/x\). Specifically, apply the modular multiplication \[\begin{align} |x \rangle_X|0 \rangle_Y|y/x \rangle_A \longmapsto |x \rangle_X|y \rangle_Y|y/x \rangle_A, \label{eq:idiv95step95recompute95y} \end{align}\tag{7}\] then apply the classically controlled Pauli correction \[\begin{align} Z^b = Z^{b_0}\otimes Z^{b_1}\otimes\cdots\otimes Z^{b_{n-1}} \end{align}\] to the register \(Y\). This contributes another factor \((-1)^{b\cdot y}\) and therefore cancels the measurement phase. Finally, reverse the multiplication in Equation 7 , obtaining \[\begin{align} |x \rangle_X|0 \rangle_Y|y/x \rangle_A. \end{align}\] Swapping \(Y\) and \(A\) completes the in-place division: \[\begin{align} |x \rangle_X|y/x \rangle_Y|0 \rangle_A. \end{align}\] The corresponding circuit is shown in Figure 18.

The in-place multiplication subroutine is implemented by the same mechanism. One first computes \(xy\) into the clean register \(A\), measures and resets the old \(Y=y\) register, uses the remaining registers to recompute \(y\) for the \(Z^b\) phase correction, uncomputes this recomputation, and finally swaps \(Y\) with \(A\). Thus both \(\operatorname{IDiv}\) and \(\operatorname{IMul}\) require only the three field registers \(X,Y,A\), together with the \(O(\log_2 n)\) EEA auxiliary register \(S\). Therefore the affine point-addition circuit in Figure 17 uses \(3n+O(\log_2 n)\) logical qubits.

6 Resource Estimation and the ECDLP↩︎

We adopt the resource-estimation methodology introduced by Roetteler et al. [21]. In Shor’s algorithm for the ECDLP, the dominant quantum cost arises from the sequence of controlled elliptic-curve point additions performed in superposition. We consider the point additions in affine coordinates over the finite field \(\mathbb{F}_p\), where \(p\) is an \(n\)-bit prime. At this level, point addition reduces to a fixed sequence of modular additions, subtractions, multiplications, squarings, and inversions. Among these operations, modular inversion typically dominates both the space complexity and the Toffoli gate count.

6.1 Space complexity improvements↩︎

In this work, we focus exclusively on reducing the space complexity required for modular inversion, rather than exploring trade-offs among Toffoli count, circuit depth, and space complexity as previous works [21], [22], [26], [27]. Specifically, we present an exact, space-efficient, in-place reversible quantum circuit for modular inversion that implements Equation 1 . The circuit is based on the register-sharing technique originally proposed by Proos and Zalka [14]. This approach reduces the nunmber of qubits required for modular inversion to \[2n + 6\left\lfloor \log_2 n \right\rfloor + 19.\] Of this total, \(2n + 4\left\lfloor \log_2 n \right\rfloor + 15\) qubits correspond to the base circuit shown in Figures 8 and 9, while the remaining \(2\left\lfloor \log_2 n \right\rfloor + 4\) qubits are required for the unary iteration described in Section 4.3.

For elliptic curve point addition shown in Figure 17, the overall space complexity is then \[3n + 6\left\lfloor \log_2 n \right\rfloor + 19.\]

6.2 Asymptotic gate counts↩︎

6.2.0.1 Modular inversion.

We first derive the asymptotic Toffoli and CNOT gate counts of the proposed modular inversion circuit. Since the circuit consists of several types of location-controlled operations, we first recall (in Section 4.4) the gate cost incurred by each circuit block at algorithmic step \(T\). These per-step costs are summarized in Table 5. We then combine them with the active-window analysis developed in Section 4.2 to obtain the overall asymptotic gate complexity.

• Location-controlled addition/subtraction on \(r\)’s. These operations cost \[2\sum_{T=1}^{4\left\lceil cn \right\rceil} 11\bigl(K_1(T) - k_1(T)\bigr) + O(n\log_2 n) = (44c + 11)n^2 + O(n\log_2 n)\] Toffoli gates, and \((48c + 12)n^2 + O(n\log_2 n)\) CNOT gates.

• Location-controlled swap. These operations cost \[\sum_{T=1}^{4\left\lceil cn \right\rceil} 2\bigl(K_2(T) - k_2(T)\bigr) + O(n\log_2 n) = (4c + 1)n^2 + O(n\log_2 n)\] Toffoli gates, and \((8c + 2)n^2 + O(n\log_2 n)\) CNOT gates.

• Location-controlled addition/subtraction on \(t\)’s. These operations cost \[2\sum_{T=1}^{4\left\lceil cn \right\rceil} 9\bigl(K_3(T) - k_3(T)\bigr) + O(n\log_2 n) = (72c - 36)n^2 + O(n\log_2 n)\] Toffoli gates, and \((80c - 40)n^2 + O(n\log_2 n)\) CNOT gates.

• Length-update circuit for updating \(\ell_t\). We execute the length-update circuit only at step indices \(T\) that are multiples of four. These operations cost \[\sum_{T'=1}^{\left\lceil cn \right\rceil} 24\bigl(K_4(4T') - k_4(4T')\bigr) + O(n\log_2 n) = 12c n^2 + O(n\log_2 n).\] Toffoli gates, and \(16cn^2 + O(n\log_2 n)\) CNOT gates.

• Length-update circuit for updating \(\ell_{r'}\). We execute the length-update circuit only at step indices \(T\) that are multiples of four. These operations cost \[\sum_{T'=1}^{\left\lceil cn \right\rceil} 24\bigl(K_4(4T') - k_4(4T')\bigr) + O(n\log_2 n) = (12c - 12) n^2 + O(n\log_2 n).\] Toffoli gates, and \((16c - 16) n^2 + O(n\log_2 n)\) CNOT gates.

In addition to the circuit blocks analyzed above, the modular inversion circuit (illustrated in Figures 8 and 9) contains four controlled \(\mathrm{Shift}\) circuits. Each \(\mathrm{Shift}\) circuit consists of \(n+O(1)\) Toffoli gates and \(2n+O(1)\) CNOT gates. Therefore, these four \(\mathrm{Shift}\) circuits contribute an additional \(16cn^2+O(n)\) Toffoli gates and \(32cn^2+O(n)\) CNOT gates.

Combining all contributions, the total number of Toffoli gates required by our (one-sided without reversion) modular inversion circuit grows asymptotically as \[(160c - 36)n^2 + O(n\log_2 n) \approx 194.47 n^2 + O(n\log_2 n).\] The asymptotic bound of CNOT gates required is \[(200c - 42)n^2 + O(n\log_2 n) \approx 246.09 n^2 + O(n\log_2 n).\]

6.2.0.2 Point addition.

As discussed in Section 5, we count one affine point addition with mid-circuit measurement as consisting of 1 in-place division, 1 in-place multiplication, 2 modular squarings, and a constant number of modular additions/subtractions/negations. The corresponding circuit is shown schematically in Figure 17. Among these modular arithmetic operations, the modular additions/subtractions/negations contribute only \(O(n\log_2 n)\) Toffoli gates in total and are therefore absorbed into the lower-order term. The in-place division, as well as the in-place multiplication, consists of 2 modular divisions and 3 modular multiplications as shown in Figure 18.

We use an improved modular multiplication/squaring circuit described in Appendix 8, which costs \(17n^2 + O(n\log_2 n)\) Toffoli gates. Therefore, a single affine point addition with mid-circuit measurement can be implemented by at most \[(4\cdot 194.47 + 6\cdot 17 + 2\cdot 17)n^2 + O(n\log_2 n) < 914n^2 + O(n\log_2 n)\] Toffoli gates.

6.3 Numerical experiments↩︎

All resource-estimation experiments were conducted on a Linux server equipped with an AMD EPYC 7302 processor (up to 3.0 GHz). Circuit generation, compilation and optimization were performed using IBM Qiskit. The constructed circuits were transpiled into a gate basis consisting of CCX, CX, and X gates, in order to obtain accurate Toffoli-gate and CNOT-gate counts.

The implementation follows the explicit circuit constructions in Sections 4 and 5. Since modular inversion is the most involved subroutine and a main contributor to the point-addition cost, we report its implementation separately.

• Modular-inversion subroutine. We implement the one-step EEA circuit as a collection of Qiskit modules. These modules include the pre-shift and post-shift blocks, the location-controlled arithmetic and swap blocks, the phase-update logic, and the length-update circuits. A full inversion instance is generated by following the step schedule of Algorithm 7. Each step instantiates only its active window. The step circuits are counted in chunks and are then combined with the shared-register EEA wrapper.

• Point-addition circuit. We implement the point-addition circuit blockwise. Figure 17 specifies the top level affine point addition schedule, including the constant coordinate updates, the in-place division and multiplication calls, the square-minus block, and the final corrections. The point coordinates \(x_2\) and \(y_2\) are treated as classically precomputed constants. The in-place division and multiplication blocks are assembled according to Figure 18, from the shared-register EEA circuit, modular multiplication blocks, inverse multiplication blocks, and the explicit mid-circuit measurements and feed-forward phase corrections shown in the figure.

To obtain the compiled gate counts of these implemented circuits, we use a layered blockwise counting pipeline. This is necessary because directly expanding the full point-addition circuit into a single Qiskit circuit over elementary operations is impractical. We first recursively decompose and count reusable Qiskit subblocks, including constant-coordinate updates, controlled modular additions and subtractions, modular doubling and halving, and the shared-register EEA wrapper. We then assemble larger arithmetic blocks from these counted components with their exact multiplicities. For example, a modular multiplication block contains \(n\) controlled modular additions and \(n-1\) modular doublings, while its inverse contains \(n\) controlled modular subtractions and \(n-1\) modular halvings. The squaring block reuses the same multiplication count and adds the explicit CNOT cost for copy and uncompute. This yields a complete compiled gate count for the point-addition circuit while preserving the block multiplicities.

In addition to compiling and counting the reusable subblocks, we apply a local template-based optimization before each subblock count is stored and reused. The optimizer performs local cancellation and Qiskit template replacement on small reversible segments. To make the template identities directly applicable, we restrict these segments to the gate library \(\{X,\mathrm{CX},\mathrm{CCX}\}\). A rewritten segment is accepted only if its gate count does not increase.

To improve efficiency and preserve the circuit structure, we apply the optimization segment by segment. We scan each decomposed subblock linearly and collect consecutive \(X\), \(\mathrm{CX}\), and \(\mathrm{CCX}\) gates into one reversible segment. When the scan reaches any other instruction, the current segment is optimized, the out-of-library instruction is counted directly, and a new segment is started. Thus, in circuits with measurements and feed-forward phase corrections, these operations are not rewritten. They simply separate the neighboring reversible segments. If a segment exceeds the runtime limits, it is counted unchanged.

To validate the implementation, we developed test suites for both the modular-inversion and point-addition circuits. The tests include representative examples over prime fields with \(p\) ranging from small values such as \(p=3\) to 512-bit primes, and with circuit widths \(n\) ranging up to \(512\). They additionally verify register layouts, circuit schedules, arithmetic sub-blocks, and compiled block assembly.

The corresponding circuit implementation is included in our open-source codebase. ⁶

For each problem size \(n\), we generated the full circuit instance up to the theoretical upper bound on the number of cycles derived in this work, transpiled it into the CCX, CX, and X basis, and recorded the resulting gate counts. We report results for \(n \in \{64,128,160,192,224,256,384,512\}\). The numerical values are listed in Table 6.

6.4 Resource estimates for Shor’s ECDLP circuit↩︎

For the full ECDLP attack, we do not repeat the controlled point-addition circuit bit-by-bit for all \(2n\) control bits. Instead, we follow the signed-window technique of [22]. Namely, we partition the \(2n\) control bits arising in the double-scalar multiplication into windows of size \(w\), and implement each window by one signed windowed point addition.

In the signed-window construction, one of the \(w\) bits is used as a sign bit, while the remaining \(w-1\) bits address a precomputed table of point multiples. As shown schematically in Fig. 10 of [22], one such windowed point addition uses the arithmetic core of an affine Weierstrass point addition. The coordinates of the selected precomputed point are obtained through three table queries, and its sign is handled by one modular negation. In our space-optimized circuit, these three queries are implemented by five sequential table look-ups.⁷ Since the dominant \(n^2\) term in our Toffoli accounting comes from modular divisions, multiplications and squaring, replacing the classically known addend by an addend obtained from the look-up table does not change the asymptotic scaling.

To obtain a clean asymptotic bound, we choose window size \(w = 2\log_2 n\). The five sequential table look-ups contribute \(5\cdot 2^w\) Toffoli gates to each windowed point addition. The full double-scalar multiplication uses approximately \(2n/w\) windows, so its dominant Toffoli count becomes \[\frac{2n}{w}\left(914n^2 + 5\cdot 2^w + O(n\log_2n)\right) = 919\frac{n^3}{\log_2n} + O(n^2).\]

For \(n=256\), following the analysis in [26], the Toffoli count of the complete Shor ECDLP circuit is estimated as \[28 \cdot \left(5 \cdot 2^{16} + Q_A\right).\] Here, \(Q_A\) denotes the Toffoli count of a single controlled affine point-addition circuit. For a window size of \(w=16\), the number of signed-window point additions is \(\frac{2n}{w}-4=28\). The five sequential table look-ups described above incur an additional \(5\cdot 2^w\) Toffoli gates per window, which becomes \(5\cdot 2^{16}\) when \(w=16\). Substituting our concrete value of \(Q_A(256)\) shows that our algorithm requires \(2^{30.63}\) Toffoli gates for the curve secp256k1.

Finally, we note that compression techniques and multi-run tradeoffs [42] could potentially yield further improvements to the constant factors in our overall resource estimates.

Acknowledgments↩︎

This work was supported by the Innovation Program for Quantum Science and Technology (Grant Number 2024ZD0300500). ZY, ZW, YS and TL are supported by the National Natural Science Foundation of China (Grant Numbers 62372006 and 92365117).

7 Proof Details↩︎

7.1 Bounds on the total number of steps↩︎

Suppose that after \(k\) iterations of the Extended Euclidean Algorithm, we obtain \(r_{k-1} = 1\) and \(r_k = 0\), with intermediate quotients \(q_1, q_2, \ldots, q_{k-1}\), where \(q_i = \lfloor r_{i-1} / r_i \rfloor\) for \(i = 1, 2, \ldots, k-1\). Then the total number of steps required in our four-phase algorithm can be expressed as \[N = 4\sum_{i=1}^{k-1} \left(\lfloor \log_2 q_i \rfloor + 1\right).\]

The lower bound of \(N\) can be derived directly. Since \(r_{i-1} = q_i r_i + r_{i+1} < (q_i + 1)r_i\), it follows that \[N \ge 4\sum_{i=1}^{k-1}\log_2(q_i + 1) > 4\sum_{i=1}^{k-1}\log_2\frac{r_{i-1}}{r_i} = 4\log_2 p \ge 4(n - 1).\] Because \(N\) must be a multiple of \(4\), we conclude that \(N \ge 4n\).

To derive the upper bound of \(N\), we take a complementary viewpoint. Instead of fixing \(p\) and computing \(N\), we fix \(N\) and seek the smallest possible value of \(p\) as \(k\) and the quotient sequence \(\{q_i\}_{i=1}^{k-1}\) vary. Note that \(p = r_0\) can be reconstructed recursively from the sequence defined by \(r_k = 0\), \(r_{k-1} = 1\), and \(r_{i-1} = r_{i+1} + q_i r_i, \quad i = k-1, k-2, \cdots, 1\). To minimize \(p\) under this recurrence, we apply the following sequence of adjustment steps, keeping \(N = 4\sum_{i=1}^{k-1}(b_i + 1)\) fixed:

• We first adjust all quotients to powers of two, i.e., \(q_i = 2^{b_i}\) with \(b_i = \lfloor \log_2 q_i \rfloor\). This modification is justified because reducing any quotient strictly decreases the corresponding sequence \(r_{i-1}, \ldots, r_0\).

• For any \(i = 1, 2, \ldots, k-2\), if \(b_i \ge 2\) for \(i = 1\) and \(b_i \ge 1\) for \(i > 1\), we can split the EEA iteration with quotient \(q_i = 2^{b_i}\) into two successive iterations with quotients \(q_{i,1} = 1\) and \(q_{i,2} = 2^{b_i - 1}\). The updated value of \(r_{i-1}\) is then \[r_{i-1}' = r_i + q_{i,1}(r_{i+1} + q_{i,2}r_i) = r_{i+1} + (2^{b_i-1} + 1)r_i \le r_{i+1} + 2^{b_i}r_i = r_{i-1},\] implying that the modified sequence yields a smaller \(p\). The condition \(b_1 \ge 2\) when \(i = 1\) is required since the algorithm assumes \(x < p/2\).

• If \(b_{k-1} \ge 2\), we further refine the final iteration with \(q_{k-1} = 2^{b_{k-1}}\) by splitting it into two iterations with quotients \(q_{k-1,1} = 2\) and \(q_{k-1,2} = 2^{b_{k-1}-2}\). This adjustment differs from the previous one because \(r_{k-2}\) must remain greater than \(1\). The updated value of \(r_{k-2}\) becomes \[r_{k-2}' = 1 + q_{k-1,1} \cdot q_{k-1,2} = 1 + 2^{b_{k-1}-1} < 2^{b_{k-1}} = r_{k-2},\] showing once again that the adjustment leads to a smaller \(p\) for the same total number of steps.

After applying all possible adjustments, we obtain a quotient sequence of form \(\{q_i\} = \{2, 1, 1, \ldots, 1, 2\}\) with length \(k - 1 = N/4 - 2\). The corresponding sequence of \(r_i\) satisfies \[r_{k-1} = 1, \quad r_{k-2} = 2, \quad r_{i-1} = r_{i+1} + r_i \text{ for } i = k-2, \ldots, 2, \quad \text{and } r_0 = r_2 + 2r_1.\] This recurrence defines a Fibonacci sequence with \(r_{k-i} = F_{i+1}\) for \(i = 1, 2, \cdots, k-1\), and the minimal possible value of \(p\) is thus \(p = r_0 = F_{k-1} + 2F_k = F_{k+2} = F_{N/4+1}\). Together with the condition \(2^{n-1} \le p < 2^n\), we obtain \[\frac{1}{\sqrt{5}}\left(\frac{\sqrt{5} + 1}{2}\right)^{N/4+1} \le F_{N/4+1} + 1 \le p + 1 \le 2^n.\] Hence, \[N \le 4\left\lfloor c\left(n + \log_2 \sqrt{5}\right) - 1 \right\rfloor \le 4\left\lceil c n \right\rceil,\] where \(c = 1 / \log_2\left(\frac{\sqrt{5} + 1}{2}\right)\).

7.2 Step-dependent active windows↩︎

Fix an input \(x\), let \((q_1, \ldots, q_{k-1})\) denote the quotient sequence produced by EEA, and define \(b_i := \left\lfloor \log_2 q_i \right\rfloor\) for each iteration \(i\). Under the four-phase schedule, each EEA iteration \(i\) is expanded into \(4(b_i + 1)\) steps. The total number of steps is \(N = 4\sum_{i=1}^{k-1} (b_i + 1) \le N_{\max} := 4\left\lceil cn \right\rceil\), where \(c = 1/\log_2\left(\frac{\sqrt{5}+1}{2}\right)\) (see Appendix 7.1).

For a global step index \(T \in \{1, 2, \ldots, N_{\max}\}\), let \(j = j(x, T)\) denote the index of the EEA iteration that contains step \(T\), and let \(u = u(x, T)\) denote the position of \(T\) within that iteration. More precisely, the pair \((j(x,T), u(x,T))\) is uniquely determined by the conditions \[\sum_{i=1}^{j-1} 4(b_i + 1) < T \le \sum_{i=1}^{j} 4(b_i + 1), \quad u = T - \sum_{i=1}^{j-1} 4(b_i + 1).\] The bit-length of the current quotient \(\ell_q(x, T)\) depends deterministically on indices \((j, u)\): \[\label{eqn:phase95decompose} \begin{align} \ell_q(x, T) & = \begin{cases} 0 & u(x, T)\in (0, b_j + 1] \cup (3(b_j + 1), 4(b_j + 1)],\\ u(x, T) - (b_j + 1) & u(x, T)\in (b_j + 1, 2(b_j + 1)],\\ 3(b_j + 1) - u & u(x, T)\in (2(b_j + 1), 3(b_j + 1)]. \end{cases} \end{align}\tag{8}\]

We next state a lemma that characterizes the minimal possible value of \(t_j\), conditioned on the total number of steps \(N_j\) taken before reaching the \(j\)-th iteration of EEA. The proof follows exactly the same adjustment argument as in Appendix 7.1, and is therefore omitted.

We then provide the detailed proofs of the bounds stated in Section 4.2 in the remainder of this subsection. Recall that \(c = 1 / \log_2\left(\frac{\sqrt{5}+1}{2}\right)\).

7.2.0.1 Location-controlled addition/subtraction on \(r\)’s.

First, observe that \(t_j q_j < t_{j+1} < p\), which implies \(\ell_t + b_j \le n + 1\). Since a location-controlled addition/subtraction on \(r\)’s is only activated in Phase 1 and 2, i.e. \(0 < u\le 2(b_j + 1)\), we then analyze the claimed bound by considering two cases.

• Case 1. Suppose that \(u \le b_j + 1\). In this case, we have \(\ell_q = 0\). By Lemma 1, it follows that \[\ell_t \ge \log_2\left(\frac{\sqrt{5}+1}{2}\right)\cdot\frac{T - u}{4} \ge \log_2\left(\frac{\sqrt{5}+1}{2}\right)\cdot\frac{T - (n + 2 - \ell_t)}{4},\] hence \(\ell_t + \ell_q = \ell_t \ge \dfrac{T - n - 2}{4c - 1}\).

• Case 2. Suppose that \(b_j + 1 < u \le 2(b_j + 1)\). Then \(\ell_q = u - (b_j + 1)\), and we obtain that \[\ell_t + \ell_q \ge \log_2\left(\frac{\sqrt{5}+1}{2}\right)\cdot\frac{T - u}{4} + (u - b_j - 1).\] The right-hand side is minimized when \(u = b_j + 1\), in which case the expression reduces to that of Case 1.

Combining the two cases, we conclude that \(\ell_t + \ell_q + 2 \ge \max\left\{\left\lceil \dfrac{T - n - 2}{4c - 1} \right\rceil, 1\right\} + 2\).

7.2.0.2 Location-controlled swaps.

For the lower bound, a location-controlled swap is only activated in Phase 2 and 3, i.e. \(b_j + 1 < u\le 3(b_j + 1)\), we then analyze the claimed lower bound by considering two cases.

• Case 1. Suppose that \(b_j + 1 < u \le 2(b_j + 1)\). In this case, we also have \(\ell_t + \ell_q \ge \dfrac{T - n - 2}{4c - 1}\).

• Case 2. Suppose that \(2(b_j + 1) < u \le 3(b_j + 1)\). In this case, we have \(\ell_q = 3(b_j + 1) - u\). By Lemma 1, it follows that \[\ell_t \ge \log_2\left(\frac{\sqrt{5}+1}{2}\right)\cdot\frac{T - u}{4} \ge \log_2\left(\frac{\sqrt{5}+1}{2}\right)\cdot\frac{T - 3(n + 2 - \ell_t)}{4},\] hence \(\ell_t + \ell_q \ge \ell_t \ge \dfrac{T - 3(n + 2)}{4c - 3}\).

Combining the two cases, we conclude that \(\ell_t + \ell_q + 1 \ge \max\left\{\left\lceil \dfrac{T - 3(n + 2)}{4c - 3} \right\rceil, 1\right\} + 1\).

For the upper bound, recall the recurrence relation of the EEA on the \(t\)-sequence, that is \(t_{i+1} = t_{i-1} + q_i t_i < (q_i + 1)t_i \le 2^{b_i + 1} t_i\). By iterating this inequality, we obtain that \[t = t_j \le \prod_{i=1}^{j-1} 2^{b_i + 1} = 2^{(T - u)/4}, \quad \text{and then} \quad \ell_t \le (T - u) / 4 + 1.\] By Equation 8 , we know that \(\ell_q \le u/2\). Hence, \[\ell_t + \ell_q + 1 \le \left\lfloor (T - u)/4 + u/2 + 2 \right\rfloor = \left\lfloor (T + u)/4 \right\rfloor + 2 \le \left\lfloor T/2 \right\rfloor + 2.\] Finally, since the Work1 register stores a value \(r \ge 1\), we conclude that \(\ell_t + \ell_q + 1 \le n + 2\).

7.2.0.3 Location-controlled addition/subtraction on \(t\)’s.

As shown above, we have that \(\ell_t + 1 \le \left\lfloor (T - u)/4 \right\rfloor + 2\le \left\lceil T/4 \right\rceil + 1\). Under the constraint that \(t\le p < 2^n\), we also obtain that \(\ell_t + 1\le n + 1\).

7.2.0.4 Length-update circuit.

For the lower bound \(k_4(T)\), the length-update circuit is activated only at the end of an EEA iteration, namely when \(u = 4(b_j + 1)\). By Lemma 1, we have \[\ell_t \ge \log_2\left(\frac{\sqrt{5}+1}{2}\right)\cdot\frac{T - u}{4} \ge \log_2\left(\frac{\sqrt{5}+1}{2}\right)\cdot\frac{T - 4(n + 2 - \ell_t)}{4},\] which implies \(\ell_t \ge \dfrac{T - 4(n + 2)}{4c - 4}\).

For the lower bound \(k_5(T)\), Lemma 1 directly yields \[\ell_t^* \ge \log_2\left(\frac{\sqrt{5}+1}{2}\right)\cdot \frac{T}{4} = \frac{T}{4c}.\]

For the upper bound \(K_5(T)\), recall the recurrence relation of the EEA on the \(r\)-sequence, \(r_{i-1} = r_{i+1} + q_i r_i < (q_i + 1)r_i \le 2^{b_i + 1} r_i\). By iterating this inequality, we obtain \[p / r_{j+1} \le \prod_{i=1}^{j} 2^{b_i + 1} = 2^{T/4}.\] It follows that \(n + 4 - \ell_{r'}^* < n + 4 - \log_2 r_{j+1} \le T/4 + n + 4 - \log_2 p \le T/4 + 5\), and hence \(n + 4 - \ell_{r'}^* \le T/4 + 4\).

For the upper bound \(K_4(T)\), we similarly have \(n + 3 - \ell_{r'}\le n + 3 - \ell_{r'}^* \le T/4 + 3\).

8 Improved Modular Multiplication Circuit↩︎

Our modular multiplier used in in-place division/multiplication implements \[\mathrm{Mul}_{p}: |x \rangle|y \rangle|0 \rangle \longmapsto |x \rangle|y \rangle|xy \bmod p \rangle,\] based on the usual Horner double-and-add scan as the low-space multiplier of [21]. The circuit contains \(n\) controlled modular additions and \(n-1\) modular doublings.

• Controlled modular additions. The controlled modular addition \[|c \rangle|A \rangle|B \rangle|0 \rangle_{f} \longmapsto |c \rangle|A \rangle|B+cA\bmod p \rangle|0 \rangle_{f},\] is implemented by first doing the controlled addition \(B\leftarrow B+cA \pmod {2^n}\), while XORing the overflow carry into a flag \(f\). We use a specialized controlled quantum–quantum ripple-carry adder for this step, rather than controlling every gate of an ordinary adder from [43]. Let \(\gamma_i\) denote the carry into bit \(i\), with \(\gamma_0=0\), and \(\gamma_{i+1}=\operatorname{maj}(A_i,B_i,\gamma_i)\).

  During the forward sweep, the circuit computes the carry chain. At bit \(i\), the addend and accumulator wires are temporarily transformed to \(A_i\oplus \gamma_i\) and \(B_i\oplus \gamma_i\), while the carry wire is advanced to \(\gamma_{i+1}\). In the reverse sweep, we first undo the carry Toffoli, so the carry wire again contains \(\gamma_i\). A CNOT from this carry wire to the accumulator wire restores \(B_i\oplus \gamma_i \longmapsto B_i\). At this point the addend wire still contains \(A_i\oplus \gamma_i\). We then apply the controlled sum-writing Toffoli \[\operatorname{CCX}\bigl(c,\; A_i\oplus \gamma_i;\; B_i\bigr).\] Thus, if \(c=0\), the accumulator bit remains \(B_i\); if \(c=1\), it becomes \(B_i\oplus A_i\oplus \gamma_i\), which is exactly the \(i\)-th sum bit. Finally, a CNOT from the carry wire to the addend wire restores \(A_i\oplus \gamma_i \longmapsto A_i\). Therefore, the controlled writing of the \(n\) sum bits contributes precisely \(n\) additional Toffoli gates. In addition, after the forward sweep the final carry \(\gamma_n\) is copied into the overflow flag only when \(c=1\), using one more CCX gate, \[f \longleftarrow f\oplus c\gamma_n.\] Hence this controlled variant of ripple-carry adder costs \(3n+O(1)\) Toffoli gates.

  Let \(S=B+cA\), then after the first step the accumulator contains \[\widetilde{B}=S\bmod 2^n,\] and the overflow bit \[h=\lfloor S/2^n\rfloor\] has been XORed into the flag. Since \(A,B_{\rm old}<p<2^n\), we have \(S\le 2p-2<2^{n+1}\), so \(h\in\{0,1\}\). The true reduction condition is \(S\ge p\). If \(h=0\), then \(\widetilde{B}=S\), so this condition is exactly \([\widetilde{B}\ge p]\). If \(h=1\), then reduction is certainly needed, while \(\widetilde{B}=S-2^n<p\), so \([\widetilde{B}\ge p]=0\). Hence the reduction bit is \[r=h\oplus[\widetilde{B}\ge p].\] We therefore update the flag by XORing in the fixed-modulus comparison \([\widetilde{B}\ge p]\), which is evaluated by the classical-quantum comparator from [44]. Here we use the dirty-assisted adder which costs \(3n+O(1)\) Toffoli gates by borrowing the non-target register \(A\) as dirty workspace. Controlled on this flag, we subtract the fixed modulus \(p\) from \(B\), again using the same Gidney-style controlled classical–quantum subtractor, with cost \(3n+O(1)\). Finally, after the correction, the flag can be uncomputed by one Toffoli gate applying \[f\leftarrow f\oplus c\,[B_{\rm final}<A].\] \([B_{\rm final}<A]\) can be evaluated using the high-bit-only Cuccaro quantum comparator, derived from the Cuccaro ripple-carry adder [43], costing \(2n+O(1)\) Toffoli gates. All clean and borrowed dirty workspace, including the flag \(f\), is restored at the end of the block.

  Therefore, one controlled modular addition costs \[\begin{align} T_{\mathrm{add}}(n)=(3n+O(1))+(3n+O(1))+(3n+O(1))+(2n+O(1))=11n+O(1) \end{align}\] Toffoli gates.

• Modular doublings. For modular doubling, we follow the implementation from [21]. The binary doubling itself is implemented by Clifford shift/CNOT operations. Since \(p\) is odd, the reduction flag can be cleared from the least significant output bit. The only parts that require Toffoli gates are one fixed comparison with \(p\) and one conditional fixed subtraction, which can be implemented by the same classical-quantum adder from [44].

  Therefore, one modular doubling costs \[T_{\mathrm{dbl}}(n) =(3n+O(1))+(3n+O(1)) =6n+O(1)\] Toffoli gates.

Consequently, the total number of Toffoli gates required by our modular multiplication circuit grows asymptotically as \[\begin{align} T(n) &= n\,T_{\mathrm{add}}(n) +(n-1)\,T_{\mathrm{dbl}}(n) = 17n^2+O(n). \end{align}\] The modular squaring circuit is same to the modular multiplication, but with the addend equal to the input register itself. Therefore, it also costs at most \(17n^2+O(n)\) Toffoli gates.

References↩︎