Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Quantum Information Processing
Erschienen in: Quantum Information Processing 4/2021

01.04.2021

Using small-scale quantum devices to solve algebraic equations

verfasst von: Hongshu Li, Zhi Ma, Hong Wang, Qianheng Duan, Yangyang Fei, Xiangdong Meng

Erschienen in: Quantum Information Processing | Ausgabe 4/2021

Einloggen

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

search-config
loading …

Abstract

Solving algebraic equations over GF(2) is a problem which has a wide range of applications, including NP-Hard problems and problems related to cryptography. The existing mature algorithms are difficult to solve large-scale problems. Inspired by Schöning’s algorithm and its quantum version, we apply related methods to solve algebraic equations over GF (2). The new algorithm we proposed has a significant improvement of solving efficiency in large-scale and sparse algebraic equations. As a hybrid algorithm, the new algorithm can not only run on a classic computer alone, but also use small-scale quantum devices to assist acceleration. And the new algorithm can be seen as an example of solving a large-scale problem on a small-scale quantum device.
Vorheriger Artikel Engineering distributed atomic NOON states via single-photon detection
Nächster Artikel Hierarchy of quantum correlations under non-Markovian dynamics

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
Literatur
1.
Armknecht, F.: Improving fast algebraic attacks. Lect. Notes Comput. Sci. 3017, 65–82 (2004)CrossRefMATH
2.
Bard, G.V.: Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis (2007)
3.
Bard, G.V., Courtois, N., Jefferson, C.: Efficient methods for conversion and solution of sparse systems of low-degree multivariate polynomials over gf(2) via sat-solvers. System 2007, (2007)
4.
Bardet, M., Faugre, J.C., Salvy, B., Spaenlehauer, P.J.: On the complexity of solving quadratic boolean systems. J. Complex. (2013)
5.
Courtois, N., Bard, G.V.: Algebraic cryptanalysis of the data encryption standard. In: Proceedings of 11th IMA International Conference Cryptography and Coding, Cirencester, UK (2006)
6.
Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: International Conference on Advances in Cryptology-eurocrypt (2000)
7.
Cox, D.A., John, L., Donal, O.: Using algebraic geometry (2005)
8.
Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Sch?Ning, U.: A deterministic (22/(k+1))n algorithm for k-sat based on local search. Theoret. Comput. 289(1), 69–83 (2002)
9.
Dunjko, V., Ge, Y., Cirac, J.I.: Computational speedups using small quantum devices. Phys. Rev. Lett. 121(25), 250501 (2018)ADSCrossRef
10.
Ge, Y., Dunjko, V.: A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles. J. Math. Phys. 61(1), 012201 (2020)ADSMathSciNetCrossRefMATH
11.
Herbort, S., Ratz, D.: Improving the efficiency of a nonlinear-system-solver using a componentwise newton method. Institut Fr Angewandte Mathematik Universitt Karlsruhe (1997)
12.
Hochba, D.S.: Approximation algorithms for np-hard problems. ACM Sigact News 28(2), 40–52 (1997)
13.
Kannan, R., Karpinski, M., Prmel, H.J.: Approximation algorithms for np-hard problems
14.
Litman, M.F.: On covering problems of codes. Theory Comput. Syst. (1997)
15.
LIYao-hui, LIUBao-Jun: Survey of finding real roots of nonlinear equations(in chinese). J.f Wuhan Univ. Sci. Technol. 03, 326–330 (2004)
16.
Miura, H., Hashimoto, Y., Takagi, T.: Extended algorithm for solving underdefined multivariate quadratic equations. In: International Workshop on Post-Quantum Cryptography (2013)
17.
Moser, R.A., Scheder, D.: A full derandomization of schöning’s k-sat algorithm. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, p. 245252. Association for Computing Machinery, New York (2011). https://​doi.​org/​10.​1145/​1993636.​1993670
18.
Rennela, M., Laarman, A., Dunjko, V.: Hybrid divide-and-conquer approach for tree search algorithms (2020)
19.
Schoning, T.: A probabilistic algorithm for k-sat and constraint satisfaction problems. In: 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pp. 410–414. IEEE (1999)
20.
Yang, B.Y., Chen, J.M.: Theoretical analysis of xl over small fields. In: Information Security Privacy: Australasian Conference (2004)
Metadaten
Titel
Using small-scale quantum devices to solve algebraic equations
verfasst von
Hongshu Li
Zhi Ma
Hong Wang
Qianheng Duan
Yangyang Fei
Xiangdong Meng
Publikationsdatum
01.04.2021
Verlag
Springer US
Erschienen in
Quantum Information Processing / Ausgabe 4/2021
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-021-03064-6

Weitere Artikel der Ausgabe 4/2021

Quantum Information Processing 4/2021 Zur Ausgabe

OriginalPaper

Entanglement-based quantum key distribution with untrusted third party

OriginalPaper

Entanglement-assisted Reed–Solomon codes over qudits: theory and architecture

OriginalPaper

Quantum k-means algorithm based on trusted server in quantum cloud computing

OriginalPaper

Novel methods to construct nonlocal sets of orthogonal product states in an arbitrary bipartite high-dimensional system

OriginalPaper

Quantum forgery attacks on COPA, AES-COPA and marble authenticated encryption algorithms

OriginalPaper

Three-party semi-quantum protocol for deterministic secure quantum dialogue based on GHZ states

Neuer Inhalt

    Bildnachweise