Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Quantum Information Processing
Published in: Quantum Information Processing 1/2015

01-01-2015

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

Authors: Parshuram Budhathoki, Rainer Steinwandt

Published in: Quantum Information Processing | Issue 1/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

When designing quantum circuits for Shor’s algorithm to solve the discrete logarithm problem, implementing the group arithmetic is a cost-critical task. We introduce a software tool for the automatic generation of addition circuits for ordinary binary elliptic curves, a prominent platform group for digital signatures. The resulting circuits reduce the number of \(T\)-gates by a factor \(13/5\) compared to the best previous construction, without increasing the number of qubits or \(T\)-depth. The software also optimizes the (CNOT) depth for \({\mathbb F}_2\)-linear operations by means of suitable graph colorings.
previous article Binary construction of pure additive quantum codes with distance five or six
next article Local deterministic simulation of equatorial Von Neumann measurements on tripartite GHZ state

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
As is common, we do not distinguish between \(T\)- and \(T^\dagger \)-gates in statements on the number of \(T\)-gates or the \(T\)-depth.
 
2
As \((0,0)\not \in E_{a_2,a_6}(\mathbb {F}_{2^n})\), the neutral element \(\mathcal O\) can be represented as \((0,0)\).
 
Literature
1.
Al-Daoud, E., Mahmod, R., Rushdan, M., Kilicman, A.: A new addition formula for elliptic curves over GF\((2^n)\). IEEE Trans. Comput. 51(8), 972–975 (2002)CrossRefMathSciNet
2.
Amento, B., Rötteler, M., Steinwandt, R.: Efficient quantum circuits for binary elliptic curve arithmetic: reducing \(T\)-gate complexity. Quantum Inf. Comput. 13, 631–644 (2013)MathSciNet
3.
Amento, B., Rötteler, M., Steinwandt, R.: Quantum binary field inversion: improved circuit depth via choice of basis representation. Quantum Inf. Comput. 13, 116–134 (2013)MathSciNet
4.
Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. Comput. Aided Design Integr. Circuits Syst. 32(6), 818–830 (2013). For a preprint version see [5]
5.
Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. arXiv:​1206.​0758v3, January (2013)
6.
7.
8.
Bernstein, D.J., Lange, T., Farashahi, R.R.: Binary edwards curves. In: Oswald, E., Rohatgi, P. (eds.) Cryptographic Hardware and Embedded Systems—CHES 2008. Lecture Notes in Computer Science, vol. 5154, pp. 244–265. International Association for Cryptologic Research, Springer (2008)
9.
Cohen, H., Frey, G. (eds.): Handbook of Elliptic and Hyperelliptic Curve Cryptography: Discrete Mathematics and its Applications. Chapman & Hall/CRC, London (2006)
10.
11.
12.
13.
Higuchi, A., Takagi, N.: A fast addition algorithm for elliptic curve arithmetic using projective coordinates. Inf. Process. Lett. 76, 101–103 (2000)CrossRefMathSciNet
14.
15.
López, J., Dahab, R.: Improved algorithms for elliptic curve arithmetic in \(GF(2^n)\). In: Tavares, S., Meijer, H. (eds.) Selected Areas in Cryptography—SAC’98, volume 1556 of Lecture Notes in Computer Science, pp. 201–212. Springer, Berlin (1999)
16.
Maslov, D., Mathew, J., Cheung, D., Pradhan, D.K.: An \(O(m^2)\)-depth quantum algorithm for the elliptic curve discrete logarithm problem over GF\((2^m)\). Quantum Inf. Comput. 9(7), 610–621 (2009). For a preprint version see [17]MATHMathSciNet
17.
Maslov, D., Mathew, J., Cheung, D., Pradhan, D.K.: On the design and optimization of a quantum polynomial-time attack on elliptic curve cryptography. arXiv:​0710.​1093v2, February (2009)
18.
19.
20.
21.
Rodríguez-Henríquez, F., Morales-Luna, G., López, J.: Low-complexity bit-parallel square root computation over \(GF(2^m)\) for all trinomials. IEEE Trans. Comput. 57(4), 472–480 (2008). For a preprint version see [22]CrossRefMathSciNet
22.
Rodríguez-Henríquez, F., Morales-Luna, G., López-Hernández, J.: Low complexity bit-parallel square root computation over \(GF(2^m)\) for all trinomials. Cryptology ePrint Archive: Report 2006/133, April 2006. http://​eprint.​iacr.​org/​2006/​133
23.
Rötteler, M., Steinwandt, R.: A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O\((\log ^2 n)\). Quantum Inf. Comput. 14, 888–900 (2014)
24.
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)CrossRefMATHMathSciNet
25.
Solinas, J.A.: An improved algorithm for arithmetic on a family of elliptic curves. In: Kaliski Jr., B.S. (ed.) Advances in Cryptology—CRYPTO ’97, Volume 1294 of Lecture Notes in Computer Science, pp. 357–371. Springer, Berlin (1997)
Metadata
Title
Automatic synthesis of quantum circuits for point addition on ordinary binary elliptic curves
Authors
Parshuram Budhathoki
Rainer Steinwandt
Publication date
01-01-2015
Publisher
Springer US
Published in
Quantum Information Processing / Issue 1/2015
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-014-0851-6

Other articles of this Issue 1/2015

Quantum Information Processing 1/2015 Go to the issue

OriginalPaper

Distributing a multi-photon polarization-entangled state with unitary fidelity via arbitrary collective noise channels

OriginalPaper

A quantum algorithm for obtaining the lowest eigenstate of a Hamiltonian assisted with an ancillary qubit system

OriginalPaper

C-NOT three-gates performance by coherent cavity field and its optimized quantum applications

OriginalPaper

Effective Hamiltonian for two interacting double-dot exchange-only qubits and their controlled-NOT operations

OriginalPaper

Joint remote state preparation for two-qubit equatorial states

OriginalPaper

Variable entangling in a quantum prisoner’s dilemma cellular automaton