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 7/2017

01.07.2017

Boosting quantum annealer performance via sample persistence

verfasst von: Hamed Karimi, Gili Rosenberg

Erschienen in: Quantum Information Processing | Ausgabe 7/2017

Einloggen

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

search-config
loading …

Abstract

We propose a novel method for reducing the number of variables in quadratic unconstrained binary optimization problems, using a quantum annealer (or any sampler) to fix the value of a large portion of the variables to values that have a high probability of being optimal. The resulting problems are usually much easier for the quantum annealer to solve, due to their being smaller and consisting of disconnected components. This approach significantly increases the success rate and number of observations of the best known energy value in samples obtained from the quantum annealer, when compared with calling the quantum annealer without using it, even when using fewer annealing cycles. Use of the method results in a considerable improvement in success metrics even for problems with high-precision couplers and biases, which are more challenging for the quantum annealer to solve. The results are further enhanced by applying the method iteratively and combining it with classical pre-processing. We present results for both Chimera graph-structured problems and embedded problems from a real-world application.
Vorheriger Artikel Simulations of Shor’s algorithm using matrix product states
Nächster Artikel Steady states of continuous-time open quantum walks

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
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
The chip at our disposal had 1100 active qubits, a working temperature of 26 ± 5 mK, and a minimum annealing time of 20 \(\upmu \)s.
 
2
A gauge, in this context, implies multiplying each spin operator by \(\pm 1\).
 
3
We used the function fix_variables in D-Wave Systems’ SAPI 2.3.1, which is the solver API used to access the quantum annealer [9].
 
4
The value zero was excluded for the couplers but not for the biases, and we use this convention throughout the paper.
 
5
The reduced problems often consist of multiple connected components (see Sect. 3.4). We took advantage of this fact when evaluating the energy values for the states in each sample.
 
Literatur
1.
Battaglia, D.A., Santoro, G.E., Tosatti, E.: Optimization by quantum annealing: lessons from hard satisfiability problems. Phys. Rev. E 71(6), 066,707 (2005)CrossRef
2.
Boixo, S., Rønnow, T.F., Isakov, S.V., Wang, Z., Wecker, D., Lidar, D.A., Martinis, J.M., Troyer, M.: Evidence for quantum annealing with more than one hundred qubits. Nat. Phys. 10(3), 218–224 (2014)CrossRef
3.
Boixo, S., Smelyanskiy, V.N., Shabani, A., Isakov, S.V., Dykman, M., Denchev, V.S., Amin, M.H., Smirnov, A.Y., Mohseni, M., Neven, H.: Computational multiqubit tunnelling in programmable quantum annealers. Nat. Commun. 7, 10327 (2016). doi:10.​1038/​ncomms10327
4.
Boros, E., Hammer, P.L., Tavares, G.: Preprocessing of unconstrained quadratic binary optimization. Rutcor research report (2006)
5.
Bunyk, P.I., Hoskinson, E.M., Johnson, M.W., Tolkacheva, E., Altomare, F., Berkley, A.J., Harris, R., Hilton, J.P., Lanting, T., Przybysz, A.J., et al.: Architectural considerations in the design of a superconducting quantum annealing processor. IEEE Trans. Appl. Supercond. 24(4), 1–10 (2014)CrossRef
6.
Chardaire, P., Lutton, J.L., Sutter, A.: Thermostatistical persistency: a powerful improving concept for simulated annealing algorithms. Eur. J. Oper. Res. 86(3), 565–579 (1995)CrossRefMATH
7.
Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7(5), 193–209 (2008)MathSciNetCrossRefMATH
8.
Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10(3), 343–353 (2011)MathSciNetCrossRefMATH
9.
D-Wave Systems: Private communication (2016)
10.
D-Wave Systems: SAPI 2.3.1 documentation (2016)
11.
Denchev, V.S., Boixo, S., Isakov, S.V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., Neven, H.: What is the computational value of finite-range tunneling? Phys. Rev. X 6, 031,015 (2016). doi:10.​1103/​PhysRevX.​6.​031015
12.
Finnila, A., Gomez, M., Sebenik, C., Stenson, C., Doll, J.: Quantum annealing: a new method for minimizing multidimensional functions. Chem. Phys. Lett. 219(5), 343–348 (1994)ADSCrossRef
13.
14.
15.
Hammer, P.L., Hansen, P., Simeone, B.: Roof duality, complementation and persistency in quadratic 0–1 optimization. Math. Program. 28(2), 121–155 (1984)MathSciNetCrossRefMATH
16.
Hamze, F., de Freitas, N.: From fields to trees. In: Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, pp. 243–250. AUAI Press (2004)
17.
Heim, B., Rønnow, T.F., Isakov, S.V., Troyer, M.: Quantum versus classical annealing of ising spin glasses. Science 348(6231), 215–217 (2015)ADSMathSciNetCrossRefMATH
18.
Hen, I., Job, J., Albash, T., Rønnow, T.F., Troyer, M., Lidar, D.A.: Probing for quantum speedup in spin-glass problems with planted solutions. Phys. Rev. A 92(4), 042,325 (2015)CrossRef
19.
Jiang, H., Xuan, J.: Backbone guided local search for the weighted maximum satisfiability problem. INTECH Open Access Publisher (2009)
20.
Johnson, M., Amin, M., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A., Johansson, J., Bunyk, P., et al.: Quantum annealing with manufactured spins. Nature 473(7346), 194–198 (2011)ADSCrossRef
21.
Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Phys. Rev. E 58(5), 5355 (1998)ADSCrossRef
22.
Katzgraber, H.G., Hamze, F., Andrist, R.S.: Glassy Chimeras could be blind to quantum speedup: designing better benchmarks for quantum annealing machines. Phys. Rev. X 4(2), 021,008 (2014)
23.
Katzgraber, H.G., Hamze, F., Zhu, Z., Ochoa, A.J., Munoz-Bauza, H.: Seeking quantum speedup through spin glasses: the good, the bad, and the ugly. Phys. Rev. X 5(3), 031,026 (2015)
24.
King, A.D.: Performance of a quantum annealer on range-limited constraint satisfaction problems. arXiv preprint arXiv:​1502.​02098 (2015)
25.
King, J., Yarkoni, S., Nevisi, M.M., Hilton, J.P., McGeoch, C.C.: Benchmarking a quantum annealing processor with the time-to-target metric. arXiv preprint arXiv:​1508.​05087 (2015)
26.
Lanting, T., Przybysz, A., Smirnov, A.Y., Spedalieri, F., Amin, M., Berkley, A., Harris, R., Altomare, F., Boixo, S., Bunyk, P., et al.: Entanglement in a quantum annealing processor. Phys. Rev. X 4(2), 021041 (2014)
27.
Lechner, W., Hauke, P., Zoller, P.: A quantum annealing architecture with all-to-all connectivity from local interactions. Sci. Adv. 1(9), e1500,0838 (2015)CrossRef
28.
29.
Mandrà, S., Zhu, Z., Wang, W., Perdomo-Ortiz, A., Katzgraber, H.G.: Strengths and weaknesses of weak-strong cluster problems: a detailed overview of state-of-the-art classical heuristics versus quantum approaches. Phys. Rev. A 94, 022,337 (2016). doi:10.​1103/​PhysRevA.​94.​022337 CrossRef
30.
McGeoch, C.C., Wang, C.: Experimental evaluation of an adiabiatic quantum system for combinatorial optimization. In: Proceedings of the ACM International Conference on Computing Frontiers, p. 23. ACM (2013)
31.
Mishra, A., Albash, T., Lidar, D.A.: Performance of two different quantum annealing correction codes. Quantum Inf. Process. 15(2), 609–636 (2016)ADSMathSciNetCrossRefMATH
32.
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic ‘phase transitions’. Nature 400(6740), 133–137 (1999)ADSMathSciNetCrossRefMATH
33.
Muthukrishnan, S., Albash, T., Lidar, D.A.: Tunneling and speedup in quantum optimization for permutation-symmetric problems. Phys. Rev. X 6, 031,010 (2016). doi:10.​1103/​PhysRevX.​6.​031010
34.
35.
Perdomo-Ortiz, A., Fluegemann, J., Biswas, R., Smelyanskiy, V.N.: A performance estimator for quantum annealers: Gauge selection and parameter setting. arXiv preprint arXiv:​1503.​01083 (2015)
36.
Perdomo-Ortiz, A., O’Gorman, B., Fluegemann, J., Biswas, R., Smelyanskiy, V.N.: Determination and correction of persistent biases in quantum annealers. Sci. Rep. 6, 18,628 (2016)CrossRef
37.
Pudenz, K.L., Albash, T., Lidar, D.A.: Error-corrected quantum annealing with hundreds of qubits. Nat. Commun. 5, 3243 (2014). doi:10.​1038/​ncomms4243
38.
Pudenz, K.L., Albash, T., Lidar, D.A.: Quantum annealing correction for random Ising problems. Phys. Rev. A 91(4), 042,302 (2015)CrossRef
39.
Ray, P., Chakrabarti, B., Chakrabarti, A.: Sherrington-Kirkpatrick model in a transverse field: absence of replica symmetry breaking due to quantum fluctuations. Phys. Rev. B 39(16), 11,828 (1989)CrossRef
40.
Romá, F., Risau-Gusman, S.: Backbone structure of the Edwards–Anderson spin-glass model. Phys. Rev. E 88(4), 042,105 (2013)CrossRef
41.
42.
Rosenberg, G., Haghnegahdar, P., Goddard, P., Carr, P., Wu, K., de Prado, M.L.: Solving the optimal trading trajectory problem using a quantum annealer. IEEE J. Sel. Top. Signal. Process. 10(6), 1053–1060 (2016)
43.
Rosenberg, G., Vazifeh, M., Woods, B., Haber, E.: Building an iterative heuristic solver for a quantum annealer. Comput. Optim. Appl. 65(13), 845–869 (2015)
44.
Santoro, G.E., Martoňák, R., Tosatti, E., Car, R.: Theory of quantum annealing of an Ising spin glass. Science 295(5564), 2427–2430 (2002)ADSCrossRef
45.
46.
47.
Tavares, G.: New algorithms for Quadratic Unconstrained Binary Optimization (QUBO) with applications in engineering and social sciences. Ph.D. thesis, Rutgers University, Graduate School—New Brunswick (2008). doi:10.​7282/​T3XK8FS2
48.
Tran, T.T., Do, M., Rieffel, E.G., Frank, J., Wang, Z., O’Gorman, B., Venturelli, D., Beck, J.C.: A hybrid quantum-classical approach to solving scheduling problems. In: Ninth Annual Symposium on Combinatorial Search (2016)
49.
Vinci, W., Albash, T., Paz-Silva, G., Hen, I., Lidar, D.A.: Quantum annealing correction with minor embedding. Phys. Rev. A 92(4), 042310 (2015)ADSCrossRef
50.
Wang, Y., Lü, Z., Glover, F., Hao, J.K.: Effective variable fixing and scoring strategies for binary quadratic programming. In: Evolutionary Computation in Combinatorial Optimization, pp. 72–83. Springer (2011)
51.
Wang, Y., Lü, Z., Glover, F., Hao, J.K.: Backbone guided tabu search for solving the UBQP problem. J. Heuristics 19(4), 679–695 (2013)
52.
Zaribafiyan, A., Marchand, D.J.J., Changiz Rezaei, S.S.: Systematic and deterministic graph-minor embedding for Cartesian products of graphs. Quantum Inf. Process. 16(5), 136 (2017). doi:10.​1007/​s11128-017-1569-z
53.
Zhang, W.: Configuration landscape analysis and backbone guided local search. Part I: satisfiability and maximum satisfiability. Artif. Intell. 158(1), 1–26 (2004)MathSciNetCrossRefMATH
54.
Zintchenko, I., Hastings, M.B., Troyer, M.: From local to global ground states in Ising spin glasses. Phys. Rev. B 91(2), 024,201 (2015)CrossRef
Metadaten
Titel
Boosting quantum annealer performance via sample persistence
verfasst von
Hamed Karimi
Gili Rosenberg
Publikationsdatum
01.07.2017
Verlag
Springer US
Erschienen in
Quantum Information Processing / Ausgabe 7/2017
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-017-1615-x

Weitere Artikel der Ausgabe 7/2017

Quantum Information Processing 7/2017 Zur Ausgabe

OriginalPaper

Entanglement-assisted quantum feedback control

OriginalPaper

SLOCC orbit of rank-deficient two-qubit states: quantum entanglement, quantum discord and EPR steering

OriginalPaper

Quantum algorithm to solve function inversion with time–space trade-off

OriginalPaper

Quantum sealed-bid auction using a modified scheme for multiparty circular quantum key agreement

OriginalPaper

Quantum private comparison employing single-photon interference

OriginalPaper

Variance-based uncertainty relation for incompatible observers

Neuer Inhalt

    Bildnachweise