Unraveling Quantum Annealers using Classical Hardness
| dc.contributor.author | Martín Mayor, Víctor | |
| dc.contributor.author | Hen, Itay | |
| dc.date.accessioned | 2023-06-18T06:48:30Z | |
| dc.date.available | 2023-06-18T06:48:30Z | |
| dc.date.issued | 2015-10-20 | |
| dc.description | © Nature Publishing Group. We thank Luis Antonio Fernández and David Yllanes for providing us with their analysis program for the PT correlation function. We also thank Marco Baity-Jesi for helping us to prepare the figures. We are indebted to Mohammad Amin, Luis Antonio Fernández, Enzo Marinari, Denis Navarro, Giorgio Parisi, Federico Ricci-Tersenghi and Juan Jesús Ruiz-Lorenzo for discussions. We thank Luis Antonio Fernández, Daniel Lidar, Felipe LLanes-Estrada, David Yllanes and Peter Young for their reading of a preliminary version of the manuscript. We thank D-Wave Systems Inc. for granting us access to the chip. We acknowledge the use of algorithms and source code for a classic solver, devised and written by Alex Selby, available for public usage at https://github.com/alex1770/QUBO-Chimera. Our simulated annealing runs were carried out on the Picasso supercomputer. The authors thankfully acknowledge the computer resources, technical expertise and assistance provided by the staff at the Red Española de Supercomputación. IH acknowledges support by ARO grant number W911NF-12-1-0523. VMM was supported by MINECO (Spain) through research contract No FIS2012-35719-C02. | |
| dc.description.abstract | Recent advances in quantum technology have led to the development and manufacturing of experimental programmable quantum annealing optimizers that contain hundreds of quantum bits. These optimizers, commonly referred to as 'D-Wave' chips, promise to solve practical optimization problems potentially faster than conventional 'classical' computers. Attempts to quantify the quantum nature of these chips have been met with both excitement and skepticism but have also brought up numerous fundamental questions pertaining to the distinguishability of experimental quantum annealers from their classical thermal counterparts. Inspired by recent results in spinglass theory that recognize 'temperature chaos' as the underlying mechanism responsible for the computational intractability of hard optimization problems, we devise a general method to quantify the performance of quantum annealers on optimization problems suffering from varying degrees of temperature chaos: A superior performance of quantum annealers over classical algorithms on these may allude to the role that quantum effects play in providing speedup. We utilize our method to experimentally study the D-Wave Two chip on different temperature-chaotic problems and find, surprisingly, that its performance scales unfavorably as compared to several analogous classical algorithms. We detect, quantify and discuss several purely classical effects that possibly mask the quantum behavior of the chip. | |
| dc.description.department | Depto. de Física Teórica | |
| dc.description.faculty | Fac. de Ciencias Físicas | |
| dc.description.refereed | TRUE | |
| dc.description.sponsorship | Army Research Office, EE.UU. | |
| dc.description.sponsorship | United States Goverment | |
| dc.description.sponsorship | Ministerio de Economía y Competitividad (MINECO), España | |
| dc.description.status | pub | |
| dc.eprint.id | https://eprints.ucm.es/id/eprint/34802 | |
| dc.identifier.doi | 10.1038/srep15324 | |
| dc.identifier.issn | 2045-2322 | |
| dc.identifier.officialurl | http://dx.doi.org/10.1038/srep15324 | |
| dc.identifier.relatedurl | http://www.nature.com/ | |
| dc.identifier.uri | https://hdl.handle.net/20.500.14352/24258 | |
| dc.journal.title | Scientific reports | |
| dc.language.iso | eng | |
| dc.publisher | Nature Publishing Group | |
| dc.relation.projectID | W911NF-12-1-0523 | |
| dc.relation.projectID | FIS2012-35719-C02 | |
| dc.rights | Atribución 3.0 España | |
| dc.rights.accessRights | open access | |
| dc.rights.uri | https://creativecommons.org/licenses/by/3.0/es/ | |
| dc.subject.cdu | 53 | |
| dc.subject.keyword | Ising spin-glasses | |
| dc.subject.keyword | Renormalization-group | |
| dc.subject.keyword | Temperature chaos | |
| dc.subject.keyword | Mean-field | |
| dc.subject.keyword | Computer | |
| dc.subject.keyword | Simulations | |
| dc.subject.keyword | Mechanics | |
| dc.subject.keyword | Systems | |
| dc.subject.keyword | Driven | |
| dc.subject.keyword | Models | |
| dc.subject.ucm | Física (Física) | |
| dc.subject.unesco | 22 Física | |
| dc.title | Unraveling Quantum Annealers using Classical Hardness | |
| dc.type | journal article | |
| dc.volume.number | 5 | |
| dcterms.references | 1. Shor, P. W. Polynomial time-algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comp. 26, 1484–1509 (1997). 2. Grover, L. K. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325–328 (1997). 3. Schlosshauer, M. Decoherence, the measurement problem, and interpretations of quantum mechanics. Rev. Mod. Phys. 76, 1267–1305 (2004). 4. Johnson, M. W. et al. Quantum annealing with manufactured spins. Nature 473, 194–198 (2011). 5. Albash, T., Boixo, S., Lidar, D. A. & Zanardi, P. Quantum adiabatic markovian master equations. New Journal of Physics 14, 123016 (2012). 6. Lanting, T. et al. Entanglement in a quantum annealing processor. Phys. Rev. X 4, 021041 (2014). 7. Albash, T., Hen, I., Spedalieri, F. M. & Lidar, D. A. Reexamination of the evidence for entanglement in the D-Wave processor. arXiv:1506.03539 (2015). 8. Smolin, J. A. & Smith, G. Classical signature of quantum annealing. arXiv:1305.4904 (2013). 9. Shin, S. W., Smith, G., Smolin, J. A. & Vazirani, U. How “quantum” is the D-Wave machine? arXiv:1401.7087 (2014). 10. I. Hen et al. Probing for quantum speedup in spin glass problems with planted solutions. arXiv:1502.01663 (2015). 11. Ronnow, T. F. et al. Defining and detecting quantum speedup. Science 345, 420–424 (2014). 12. Boixo, S. et al. Evidence for quantum annealing with more than one hundred qubits. Nat Phys 10, 218–224 (2014). 13. Young, A. P. Spin Glasses and Random Fields (World Scientific. Singapore, 1998). 14. Belletti, F. et al. (Janus Collaboration). Simulating spin systems on IANUS, an FPGA-based computer. Comp. Phys. Comm. 178, 208–216 (2008). 15. Belletti, F. et al. (Janus Collaboration). Janus: An FPGA-based system for high-performance scientific computing. Computing in Science and Engineering 11, 48–58 (2009). 16. Baity-Jesi, M. et al. (Janus Collaboration). Janus II: a new generation application-driven computer for spin-system simulations. Comp. Phys. Comm 185, 550–559 (2014). 17. Hukushima, K. & Nemoto, K. Exchange monte carlo method and application to spin glass simulations. J. Phys. Soc. Japan 65, 1604–1608 (1996). 18. Marinari, E. In Advances in Computer Simulation (eds. Kertész, J. & Kondor, I.), 50–81 (Springer-Verlag, 1998). 19. Kirkpatrick, S., Gelatt Jr., C. D. & Vecchi, M. P. Optimization by simulated annealing. Science 220, 671–680 (1983). 20. Sokal, A. In Functional Integration: Basics and Applications (eds. DeWitt-Morette, C., Cartier, P. & Folacci, A.), 131–192 (Plenum, 1997). 21. Fernandez, L. A. et al. Phase transition in the three dimensional Heisenberg spin glass: Finite-size scaling analysis. Phys. Rev. B 80, 024422 (2009). 22. Alvarez Baños, R. et al. (Janus Collaboration). Nature of the spin-glass phase at experimental length scales. J. Stat. Mech. 2010, P06026 (2010). 23. Fernandez, L. A., Martin-Mayor, V., Parisi, G. & Seoane, B. Temperature chaos in 3d Ising spin glasses is driven by rare events. EPL 103, 67003 (2013). 24. McKay, S. R., Berker, A. N. & Kirkpatrick, S. Spin-glass behavior in frustrated Ising models with chaotic renormalization-group trajectories. Phys. Rev. Lett. 48, 767–770 (1982). 25. Bray, A. J. & Moore, M. A. Chaotic nature of the spin-glass phase. Phys. Rev. Lett. 58, 57–60 (1987). 26. Banavar, J. R. & Bray, A. J. Chaos in spin glasses: A renormalization-group study. Phys. Rev. B 35, 8888–8890 (1987). 27. Kondor, I. On chaos in spin glasses. J. Phys. A 22, L163–L168 (1989). 28. Kondor, I. & Végsö, A. Sensitivity of spin-glass order to temperature changes. J. Phys. A 26, L641–L646 (1993). 29. Billoire, A. & Marinari, E. Evidence against temperature chaos in mean-field and realistic spin glasses. J. Phys. A 33, L265–L272 (2000). 30. Rizzo, T. Against chaos in temperature in mean-field spin-glass models. J. Phys. 34, 5531–5549 (2001). 31. Mulet, R., Pagnani, A. & Parisi, G. Against temperature chaos in naive thouless-anderson-palmer equations. Phys. Rev. B 63, 184438 (2001). 32. Billoire, A. & Marinari, E. Overlap among states at different temperatures in the sk model. Europhys. Lett. 60, 775–781 (2002). 33. Krzakala, F. & Martin, O. C. Chaotic temperature dependence in a model of spin glasses. Eur. Phys. J. 28, 199–208 (2002). 34. Rizzo, T. & Crisanti, A. Chaos in temperature in the Sherrington-Kirkpatrick model. Phys. Rev. Lett. 90, 137201 (2003). 35. Parisi, G. & Rizzo, T. Chaos in temperature in diluted mean-field spin-glass. J. Phys. A 43, 235003 (2010). 36. Sasaki, M., Hukushima, K., Yoshino, H. & Takayama, H. Temperature chaos and bond chaos in Edwards-Anderson Ising spin glasses: Domain-wall free-energy measurements. Phys. Rev. Lett. 95, 267203 (2005). 37. Katzgraber, H. G. & Krzakala, F. Temperature and disorder chaos in three-dimensional Ising spin glasses. Phys. Rev. Lett. 98, 017201 (2007). 38. Billoire, A. Rare events analysis of temperature chaos in the Sherrington-Kirkpatrick model. J. Stat. Mech. 2014, P04016 (2014). 39. Thomas, C. K., Huse, D. A. & Middleton, A. A. Zero and low temperature behavior of the two-dimensional ± j Ising spin glass. Phys. Rev. Lett. 107, 047203 (2011). 40. 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, 021008 (2014). 41. Hamze, F. & de Freitas, N. From fields to trees. arXiv:1207.4149 (2012). 42. Selby, A. Efficient subgraph-based sampling of Ising-type models with frustration. arXiv:1409.3934 (2014). 43. Hen, I. & Young, A. P. Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems. Phys. Rev. E. 84, 061152 (2011). 44. Farhi, E. et al. Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs. Phys. Rev. A 86, 052334 (2012). 45. Cugliandolo, L. F., Kurchan, J. & Peliti, L. Energy flow, partial equilibration, and effective temperatures in systems with slow dynamics. Phys. Rev. E 55, 3898–3914 (1997). 46. Nifle, M. & Hilhorst, H. J. New critical-point exponent and new scaling laws for short-range Ising spin glasses. Phys. Rev. Lett. 68, 2992–2995 (1992). 47. Ney-Nifle, M. Chaos and universality in a four-dimensional spin glass. Phys. Rev. B 57, 492–496 (1998). 48. Krzakala, F. & Bouchaud, J. P. Disorder chaos in spin glasses. Europhys. Lett. 72, 472–478 (2005). 49. Pudenz, K. L., Albash, T. & Lidar, D. A. Error-corrected quantum annealing with hundreds of qubits. Nature Communications 5, 3243 (2014). | |
| dspace.entity.type | Publication | |
| relation.isAuthorOfPublication | 061118c0-eadf-4ee3-8897-2c9b65a6df66 | |
| relation.isAuthorOfPublication.latestForDiscovery | 061118c0-eadf-4ee3-8897-2c9b65a6df66 |
Download
Original bundle
1 - 1 of 1
Loading...
- Name:
- MartínMayorV LIBRE 39 + CC.pdf
- Size:
- 399.2 KB
- Format:
- Adobe Portable Document Format
