Automatic synthesis of quantum circuits for point addition on ordinary binary elliptic curves
From MaRDI portal
Publication:2018146
DOI10.1007/S11128-014-0851-6zbMATH Open1311.81075OpenAlexW2100626924MaRDI QIDQ2018146FDOQ2018146
Authors: Parshuram Budhathoki, Rainer Steinwandt 
Publication date: 13 April 2015
Published in: Quantum Information Processing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1401.2437
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
Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Factorization; primality (11A51)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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)
Uses Software
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)
