Hidden subgroup ยท Circuits
Elliptic-curve point addition
Theorem statement
Let $p>3$ be prime, $f=\lceil\log_2p\rceil$,
$h=\lceil\log_2(2f)\rceil$,
$E/\mathbb{F}_p:y^2=x^3+a x+b$ be an elliptic curve, and
$Q\in E(\mathbb{F}_p)$ be a fixed classical point other than
the identity $\mathcal{O}$. There exists a reversible quantum circuit
on $37f+27+3h$ qubits, using at most $35f+26+3h$ ancilla qubits
and $(22656h+247488)f^2+(23120h-41836)f+3550$ Toffoli gates,
whose action on computational basis states satisfies
$$
\mathtt{ECADD}_{Q}\ket{c}\ket{P}
=\ket{c}\ket{P+cQ}
$$
for every control bit $c\in\{0,1\}$ and every point
$P\in E(\mathbb{F}_p)$ distinct from $\mathcal{O}$, $Q$, and $-Q$.
- $$p$$
- Prime field characteristic.
- $$f$$
- Canonical binary width of one prime-field coordinate, equal to the ceiling of log base two of p.
- $$E$$
- Elliptic curve over the prime field.
- $$a$$
- Linear coefficient in the short Weierstrass curve equation.
- $$b$$
- Constant coefficient in the short Weierstrass curve equation.
- $$P$$
- Input elliptic-curve point encoded in the quantum register.
- $$Q$$
- Fixed classical nonidentity point added conditionally by the circuit.
- $$\mathcal{O}$$
- Identity point of the elliptic-curve group.
- $$\mathtt{ECADD}_{Q}$$
- Controlled fixed-addend elliptic-curve point-addition circuit.
- $$c$$
- Control bit selecting whether the fixed point is added.
- $$x$$
- Affine x-coordinate in the curve equation.
- $$y$$
- Affine y-coordinate in the curve equation.
Sources
- Quantum resource estimates for computing elliptic curve discrete logarithms
Martin Roetteler, Michael Naehrig, Krysta M. Svore, Kristin Lauter, 2017
- Shor's discrete logarithm quantum algorithm for elliptic curves
John Proos, Christof Zalka, 2003
Lean context
Copy a short prompt with the import, theorem name, citations, and public source link.