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
Erschienen in:
An Introduction to Quantum Computing and Its Application Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Variational Quantum Factoring

verfasst von : Eric Anschuetz, Jonathan Olson, Alán Aspuru-Guzik, Yudong Cao

Erschienen in: Quantum Technology and Optimization Problems

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Integer factorization has been one of the cornerstone applications of the field of quantum computing since the discovery of an efficient algorithm for factoring by Peter Shor. Unfortunately, factoring via Shor’s algorithm is well beyond the capabilities of today’s noisy intermediate-scale quantum (NISQ) devices. In this work, we revisit the problem of factoring, developing an alternative to Shor’s algorithm, which employs established techniques to map the factoring problem to the ground state of an Ising Hamiltonian. The proposed variational quantum factoring (VQF) algorithm starts by simplifying equations over Boolean variables in a preprocessing step to reduce the number of qubits needed for the Hamiltonian. Then, it seeks an approximate ground state of the resulting Ising Hamiltonian by training variational circuits using the quantum approximate optimization algorithm (QAOA). We benchmark the VQF algorithm on various instances of factoring and present numerical results on its performance.

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
Vorheriges Kapitel A Quantum Algorithm for Minimising the Effective Graph Resistance upon Edge Addition
Nächstes Kapitel Function Maximization with Dynamic Quantum Search
Fußnoten
1
The term ansatz means a trial solution of a specific form with some parameter(s) that need to be specified for the particular problem at hand.
 
2
To lower the needed qubits for our numerical simulations, we assumed prior knowledge of \(n_p\) and \(n_q\).
 
3
We note that other simple relations exist that can be used for preprocessing—the simplified clauses for \(m=56153,291311\) as used in our numerical simulations were given by [3] who utilized a different preprocessing scheme.
 
4
The simulation of noisy quantum circuits was performed using QuTiP [13]. To access the data generated for all instances considered in this study, including those which produced Figs. 2, 3, 4, 5, and 6, please refer to our Github repository at https://​github.​com/​zapatacomputing/​VQFData.
 
Literatur
1.
Beauregard, S.: Circuit for Shor’s algorithm using 2n+3 qubits. Quant. Inf. Comput. 3(2), 175–185 (2003)MathSciNetMATH
2.
Burges, C.J.C.: Factoring as Optimization. Microsoft Research, MSR-TR-200 (2002)
3.
4.
Dridi, R., Alghassi, H.: Prime factorization using quantum annealing and computational algebraic geometry. Sci. Rep. 7(1), 43048 (2017)CrossRef
5.
Ekerå, M.: Modifying Shor’s algorithm to compute short discrete logarithms. IACR Cryptology ePrint Archive (2016)
6.
7.
Farhi, E., Harrow, A.W.: Quantum supremacy through the quantum approximate optimization algorithm, arXiv:​1602.​07674 [quant-ph] (2016)
8.
Fletcher, R.: Practical Methods of Optimization, 2nd edn. Wiley, New York (2000)CrossRef
9.
Fowler, A.G., Devitt, S.J., Hollenberg, L.C.L.: Implementation of Shor’s Algorithm on a Linear Nearest Neighbour Qubit Array. Quantum Information & Computation 4, 237–251 (2004)MathSciNetMATH
10.
Fried, E.S., Sawaya, N.P.D., Cao, Y., Kivlichan, I.D., Romero, J., Aspuru-Guzik, A.: qTorch: The quantum tensor contraction handler, arXiv:​1709.​03636 [quant-ph] (2017)
11.
Geller, M.R., Zhou, Z.: Factoring 51 and 85 with 8 qubits. Sci. Rep. 3(3), 1–5 (2013)
12.
13.
Johansson, J., Nation, P., Nori, F.: QuTiP: an open-source Python framework for the dynamics of open quantum systems. Comput. Phys. Commun. 183(8), 1760–1772 (2012)CrossRef
14.
Jones, N.C., et al.: Layered architecture for quantum computing. Phys. Rev. X 2(3), 1–27 (2012)
15.
16.
Lin, C.Y.-Y., Zhu, Y.: Performance of QAOA on typical instances of constraint satisfaction problems with bounded degree, arXiv:​1601.​01744 [quant-ph] (2016)
17.
Martín-López, E., Laing, A., Lawson, T., Alvarez, R., Zhou, X.Q., O’brien, J.L.: Experimental realization of Shor’s quantum factoring algorithm using qubit recycling. Nat. Photonics 6(11), 773–776 (2012)
18.
Nannicini, G.: Performance of hybrid quantum/classical variational heuristics for combinatorial optimization, arXiv:​1805.​12037 [quant-ph] (2018)
19.
Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information, 10th Anniversary edn. Cambridge University Press, Cambridge (2010)
20.
Peruzzo, A., et al.: A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5(May), 4213 (2014)CrossRef
21.
Politi, A., Matthews, J.C.F., O’Brien, J.L.: Shor’s quantum factoring algorithm on a photonic chip. Science 325(5945), 1221–1221 (2009)MathSciNetCrossRef
22.
Romero, J., Olson, J., Aspuru-Guzik, A.: Quantum autoencoders for efficient compression of quantum data. Quant. Sci. Technol. 2(4), 045001 (2017)CrossRef
23.
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)MathSciNetCrossRef
24.
Metadaten
Titel
Variational Quantum Factoring
verfasst von
Eric Anschuetz
Jonathan Olson
Alán Aspuru-Guzik
Yudong Cao
Copyright-Jahr
2019
Buch
Quantum Technology and Optimization Problems

Print ISBN: 978-3-030-14081-6

Electronic ISBN: 978-3-030-14082-3

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-030-14082-3_7