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

DOI10.1007/S11128-014-0851-6zbMATH Open1311.81075arXiv1401.2437OpenAlexW2100626924MaRDI 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

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)

Cites Work

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

Cited In (1)

• Quantum circuits for \(\mathbb F_{2^n}\)-multiplication with subquadratic gate count

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)