Automatic synthesis of quantum circuits for point addition on ordinary binary elliptic curves

DOI10.1007/S11128-014-0851-6MaRDI QIDQ2018146zbMATHOpenAlexFDO

Authors Parshuram Budhathoki, Rainer Steinwandt

Publication date 13 April 2015

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.2437

zbMATH Keywords

discrete logarithm problemquantum circuitShor's algorithm

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Factorization; primality (11A51)

Abstract: Implementing the group arithmetic is a cost-critical task when designing quantum circuits for Shor's algorithm to solve the discrete logarithm problem. We introduce a tool for the automatic generation of addition circuits for ordinary binary elliptic curves, a prominent platform group for digital signatures. Our Python software generates circuit descriptions that, without increasing the number of qubits or T-depth, involve less than 39% of the number of T-gates in the best previous construction. The software also optimizes the (CNOT) depth for GF(2)-linear operations by means of suitable graph colorings.

Recommendations

• Improved quantum circuits for elliptic curve discrete logarithms
• Quantum circuits for \(\mathbb F_{2^n}\)-multiplication with subquadratic gate count
• An \(O(m^2)\)-depth quantum algorithm for the elliptic curve discrete logarithm problem over \(\mathrm{GF}(2^m)^\alpha\)
• On the Design and Optimization of a Quantum Polynomial-Time Attack on Elliptic Curve Cryptography
• Quantum algorithm for solving hyperelliptic curve discrete logarithm problem

Cites work

• scientific article; zbMATH DE number 1304119 (Why is no real title available?)
• scientific article; zbMATH DE number 1088246 (Why is no real title available?)
• scientific article; zbMATH DE number 954401 (Why is no real title available?)
• A fast addition algorithm for elliptic curve arithmetic in \(\mathrm{GF}(2^{n})\) using projective coordinates
• A new addition formula for elliptic curves over GF(2/sup n/)
• An \(O(m^2)\)-depth quantum algorithm for the elliptic curve discrete logarithm problem over \(\mathrm{GF}(2^m)^\alpha\)
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Handbook of Elliptic and Hyperelliptic Curve Cryptography
• Low-Complexity Bit-Parallel Square Root Computation over GF(2^{m}) for All Trinomials
• On the Design and Optimization of a Quantum Polynomial-Time Attack on Elliptic Curve Cryptography
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Cited in

(3)

• Elliptic curves in continuous-variable quantum systems
• Quantum circuits for \(\mathbb F_{2^n}\)-multiplication with subquadratic gate count
• Improved quantum circuits for elliptic curve discrete logarithms

Describes a project that uses

Uses Software

• EFD
• QCViewer
• Python

This page was built for publication: Automatic synthesis of quantum circuits for point addition on ordinary binary elliptic curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2018146)