Quantum resource estimates for computing binary elliptic curve discrete logarithms
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916924234924032 |
|---|---|
| author | Garn, Michael Kan, Angus |
| author_facet | Garn, Michael Kan, Angus |
| contents | We perform logical and physical resource estimation for computing binary elliptic curve discrete logarithms using Shor's algorithm on fault-tolerant quantum computers. We adopt a windowed approach to design our circuit implementation of the algorithm, which comprises repeated applications of elliptic curve point addition operations and table look-ups. Unlike previous work, the point addition operation is implemented exactly, including all exceptional cases. We provide exact logical gate and qubit counts of our algorithm for cryptographically relevant binary field sizes. Furthermore, we estimate the hardware footprint and runtime of our algorithm executed on surface-code matter-based quantum computers with a baseline architecture, where logical qubits have nearest-neighbor connectivity, and on a surface-code photonic fusion-based quantum computer with an active-volume architecture, which enjoys a logarithmic number of non-local connections between logical qubits. At 10$\%$ threshold and compared to a baseline device with a $1μs$ code cycle, our algorithm runs $\gtrsim$ 2-20 times faster, depending on the operating regime of the hardware and over all considered field sizes, on a photonic active-volume device. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02984 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum resource estimates for computing binary elliptic curve discrete logarithms Garn, Michael Kan, Angus Quantum Physics We perform logical and physical resource estimation for computing binary elliptic curve discrete logarithms using Shor's algorithm on fault-tolerant quantum computers. We adopt a windowed approach to design our circuit implementation of the algorithm, which comprises repeated applications of elliptic curve point addition operations and table look-ups. Unlike previous work, the point addition operation is implemented exactly, including all exceptional cases. We provide exact logical gate and qubit counts of our algorithm for cryptographically relevant binary field sizes. Furthermore, we estimate the hardware footprint and runtime of our algorithm executed on surface-code matter-based quantum computers with a baseline architecture, where logical qubits have nearest-neighbor connectivity, and on a surface-code photonic fusion-based quantum computer with an active-volume architecture, which enjoys a logarithmic number of non-local connections between logical qubits. At 10$\%$ threshold and compared to a baseline device with a $1μs$ code cycle, our algorithm runs $\gtrsim$ 2-20 times faster, depending on the operating regime of the hardware and over all considered field sizes, on a photonic active-volume device. |
| title | Quantum resource estimates for computing binary elliptic curve discrete logarithms |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2503.02984 |