nach oben

Quantum Information Processing

Erschienen in:

01.07.2015

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

verfasst von: Shane Kepley, Rainer Steinwandt

Erschienen in: Quantum Information Processing | Ausgabe 7/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

One of the most cost-critical operations when applying Shor’s algorithm to binary elliptic curves is the underlying field arithmetic. Here, we consider binary fields \({\mathbb {F}}_{2^n}\) in polynomial basis representation, targeting especially field sizes as used in elliptic curve cryptography. Building on Karatsuba’s algorithm, our software implementation automatically synthesizes a multiplication circuit with the number of \(T\)-gates being bounded by \(7\cdot n^{\log _2(3)}\) for any given reduction polynomial of degree \(n=2^N\). If an irreducible trinomial of degree \(n\) exists, then a multiplication circuit with a total gate count of \({\mathcal {O}}(n^{\log _2(3)})\) is available.

Vorheriger Artikel One-dimensional quantum walks subject to next-nearest-neighbour hopping decoherence

Nächster Artikel Enhanced refractive index without absorption in semiconductor quantum dots

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

As usual, by a \(T\) -gate we mean the matrix \(\left( \begin{array}{cc}1&{}0\\ 0&{}\hbox {e}^{i\pi /4}\end{array}\right) \), and for the resource analysis we do not distinguish between \(T\)- and \(T^\dagger \)-gates.

The somewhat unusual indexing will become clear in a moment.

Performing the same multiplication with constant \(T\)-depth would be possible, the trade-off being additional wires—our Sage implementation can be adapted to optimize the number of qubits for a given constraint on the \(T\)-depth.

The processing of \(X\) and \(Y\) is identical up to relabeling, so the length of \(L\) is half of the total number of CNOT gates.

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

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

Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on 32(6), 818–830 (2013). For a preprint version see [4]CrossRef

Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits arXiv:quant-ph/1206.0758v3, (January 2013). Available at http://arxiv.org/abs/1206.0758v3

Budhathoki, P., Steinwandt, R.: Automatic synthesis of quantum circuits for point addition on ordinary binary elliptic curves. Quantum Information Processing, (accepted, to appear). Preprint http://lanl.arxiv.org/abs/1401.2437v1

Burns, M.: QCViewer. GitHub repository, June 2013. Available at https://github.com/aparent/QCViewer

Childs, A.M., van Dam, W.: Quantum algorithms for algebraic problems. Rev. Mod. Phys. 82(1), 1–52 (2010)MATHADSCrossRef

Fan, H., Hasan, A.: Alternative to the Karatsuba algorithm for software implementations of \(GF(2^n)\) multiplications. IET Inf. Secur. 3(2), 60–65 (2009)CrossRef

von zur Gathen, J., Gerhard, J.: Polynomial factorization over \({\mathbb{F}}_{2}\). Math. Comput. 71(240), 1677–1698 (2002)MATHADSCrossRef

10.

Karatsuba, A.A.: The complexity of computations. In: Proceedings of the Steklov Institute of Mathematics, 211:169–183, 1995. Available at http://www.ccas.ru/personal/karatsuba/divcen.pdf. Translated from Trudy Matematicheskogo Instituta imeni V.A. Steklova, Vol. 211, (1995) pp. 186–202

11.

Kowada, L.A.B., Portugal, R., de Figueiredo, C.H.M.: Reversible Karatsuba’s algorithm. J. Univ. Comput. Sci. 12(5), 499–511 (2006)MathSciNet

12.

Maslov, D.: Reversible Logic Synthesis Benchmarks Page. http://webhome.cs.uvic.ca/~dmaslov/, (2011)

13.

Maslov, D., Falconer, S.M., Mosca, M.: Quantum circuit placement: optimizing qubit-to-qubit interactions through mapping quantum circuits into a physical experiment. In: Proceedings of the 44th Design Automation Conference—DAC 2007, pp. 962–965. ACM, (2007)

14.

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 [15]MATHMathSciNet

15.

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, (2009). Available at http://arxiv.org/abs/0710.1093v2

16.

Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, (2001). Sample chapters http://cacr.uwaterloo.ca/hac/

17.

National Institute of Standards and Technology, Gaithersburg, MD 20899–8900. FIPS PUB 186–4. Federal Information Processing Standard Publication. Digital Signature Standard (DSS), (July 2013). Available at http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

18.

Offermann, S., Wille, R., Dueck, G.W., Drechsler, R.: Synthesizing multiplier in reversible logic. In: 13th IEEE Symposium on Design and Diagnostics of Electronic Circuits and Systems—DDECS 2010, pp. 335–340. IEEE Computer Society, (2010)

19.

Parent, A.: Quantum Arithmetic Circuit Generator. GitHub Repository, (2012). Avalable at https://github.com/aparent/qacg

20.

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(9–10), 888–900 (2014). http://dl.acm.org/citation.cfm?id=2638681

21.

Shor, Peter W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MATHMathSciNetCrossRef

22.

Stein, W.A. et al.: Sage Mathematics Software (Version 5.4). The Sage Development Team, (2012). http://www.sagemath.org

Titel: Quantum circuits for -multiplication with subquadratic gate count
verfasst von: Shane Kepley
Rainer Steinwandt
Publikationsdatum: 01.07.2015
Verlag: Springer US
Erschienen in: Quantum Information Processing / Ausgabe 7/2015
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI: https://doi.org/10.1007/s11128-015-0993-1

Neuer Inhalt

Bildnachweise

VDI-Icon, Profil Icon, inhalt2, Springer Professional Modul/© Springer Fachmedien Wiesbaden GmbH, Zukunftswerkstatt Sales Excellence_ieS/© Springer Fachmedien Wiesbaden GmbH, Search Icon, Banner Hanser, Strompreise/© vejaa / stock.adobe.com, Bunte Männchen, die Kunden darstelle, werden von einem riesigen Magneten angezogen. /© Oleksiy Mark, Dr. Daniel Schneider/© Fraunhofer IESE, Zeitschrift Wissensmanagement Cover, PatentFit-Logo/© Springer Fachmedien Wiesbaden GmbH, Zukunftswerkstatt Sales Excellence 2024/© AndreyPopov / Getty Images / iStock, 2023_Antrieb/© supervisuell, ATZ-Webinar: Prototypenfreie Entwicklung durch Offline- und Driver-in-the-Loop-HiL-Tests /© (c) VI-grade

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 7/2015

An improved control mode for the ping-pong protocol operation in imperfect quantum channels

Witnessing the boundary between Markovian and non-Markovian quantum dynamics: a Green’s function approach

A quantum algorithm for Viterbi decoding of classical convolutional codes

Applications of quantum cryptographic switch: various tasks related to controlled quantum communication can be performed using Bell states and permutation of particles

One-dimensional quantum walks subject to next-nearest-neighbour hopping decoherence

Enhanced refractive index without absorption in semiconductor quantum dots

Neuer Inhalt

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.