Quantum annealing with Markov chain Monte Carlo simulations and D-wave quantum computers. (English) Zbl 1442.81020

Summary: Quantum computation performs calculations by using quantum devices instead of electronic devices following classical physics and used by classical computers. Although general purpose quantum computers of practical scale may be many years away, special purpose quantum computers are being built with capabilities exceeding classical computers. One prominent case is the so-called D-Wave quantum computer, which is a computing hardware device built to implement quantum annealing for solving combinatorial optimization problems. Whether D-Wave computing hardware devices display a quantum behavior or can be described by a classical model has attracted tremendous attention, and it remains controversial to determine whether quantum or classical effects play a crucial role in exhibiting the computational input-output behaviors of the D-Wave devices. This paper consists of two parts where the first part provides a review of quantum annealing and its implementations, and the second part proposes statistical methodologies to analyze data generated from annealing experiments. Specifically, we introduce quantum annealing to solve optimization problems and describe D-Wave computing devices to implement quantum annealing. We illustrate implementations of quantum annealing using Markov chain Monte Carlo (MCMC) simulations carried out by classical computers. Computing experiments have been conducted to generate data and compare quantum annealing with classical annealing. We propose statistical methodologies to analyze computing experimental data from a D-Wave device and simulated data from the MCMC based annealing methods, and establish asymptotic theory and check finite sample performances for the proposed statistical methodologies. Our findings confirm bimodal histogram patterns displayed in input-output data from the D-Wave device and both U-shape and unimodal histogram patterns exhibited in input-output data from the MCMC based annealing methods. Further statistical explorations reveal possible sources for the U-shape patterns. On the other hand, our statistical analysis produces statistical evidence to indicate that input-output data from the D-Wave device are not consistent with the stochastic behaviors of any MCMC based annealing models under the study. We present a list of statistical research topics for the future study on quantum annealing and MCMC simulations.


81P68 Quantum computation
60J22 Computational methods in Markov chains
62P35 Applications of statistics to physics
Full Text: DOI Euclid


[1] Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S. and Regev, O. (2007). Adiabatic quantum computation is equivalent to standard quantum computation. SIAM J. Comput.37 166-194. · Zbl 1134.81009
[2] Albash, T., Rønnow, T. F., Troyer, M. and Lidar, D. A. (2014). Reexamining classical and quantum models for the D-Wave One processor: The role of excited states and ground state degeneracy. Available at arXiv:1409.3827v1.
[3] Aspuru-Guzik, A., Dutoi, A. D., Love, P. J. and Head-Gordon, M. (2005). Simulated quantum computation of molecular energies. Science309 1704-1707.
[4] Benjamini, Y. (2010). Discovering the false discovery rate. J. R. Stat. Soc. Ser. B Stat. Methodol.72 405-416. · Zbl 1411.62043
[5] Benjamini, Y. and Hochberg, Y. (1995). Controlling the false discovery rate: A practical and powerful approach to multiple testing. J. Roy. Statist. Soc. Ser. B57 289-300. · Zbl 0809.62014
[6] Bertsimas, D. and Tsitsiklis, J. (1992). Simulated annealing. In Probability and Algorithms 17-29. Nat. Acad. Press, Washington, DC. · Zbl 0764.60073
[7] Bian, Z., Chudak, F., Macready, W. G., Clark, L. and Gaitan, F. (2012). Experimental determination of Ramsey numbers. Available at arXiv:1201.1842.
[8] Boixo, S., Albash, T., Spedalieri, F. M., Chancellor, N. and Lidar, D. A. (2014a). Experimental signature of programmable quantum annealing. Nature Comm.4. 2067.
[9] Boixo, S., Rønnow, T. F., Isakov, S. V., Wang, Z., Wecker, D., Lidar, D. A., Martinis, J. M. and Troyer, M. (2014b). Evidence for quantum annealing with more than one hundred qubits. Nature Physics10 218-224.
[10] Boixo, S., Smelyanskiy, V. N., Shabani, A., Isakov, S. V., Dykman, M., Denchev, V. S., Amin, M., Smirnov, A., Mohseni, M. and Neven, H. (2015a). Computational role of collective tunneling in a quantum annealer. Available at arXiv:1411.4036v2.
[11] Boixo, S., Smelyanskiy, V. N., Shabani, A., Isakov, S. V., Dykman, M., Denchev, V. S., Amin, M., Smirnov, A., Mohseni, M. and Neven, H. (2015b). Computational role of multiqubit tunneling in a quantum annealer. Available at arXiv:1502.05754v1.
[12] Born, M. and Fock, V. (1928). Beweis des Adiabatensatzes. Zeitschrift Für Physik A51 165-180. · JFM 54.0994.03
[13] Britton, J. W., Sawyer, B. C., Keith, A., Wang, C.-C. J., Freericks, J. K., Uys, H., Biercuk, M. J. and Bollinger, J. J. (2012). Engineered 2D Ising interactions on a trapped-ion quantum simulator with hundreds of spins. Nature484 489-492.
[14] Brooke, J., Bitko, D., Rosenbaum, T. F. and Aeppli, G. (1999). Quantum annealing of a disordered magnet. Science284 779-781.
[15] Browne, D. (2014). Model versus machine. Nature Physics10 179-180.
[16] Brumfiel, G. (2012). Simulation: Quantum leaps. Nature491 322-324.
[17] Cai, T., Kim, D., Wang, Y., Yuan, M. and Zhou, H. H. (2016). Optimal large-scale quantum state tomography with Pauli measurements. Ann. Statist.44 682-712. · Zbl 1341.62116
[18] Clarke, J. and Wilhelm, F. K. (2008). Superconducting quantum bits. Nature453 1031-1042.
[19] Dechter, R. (1999). Bucket elimination: A unifying framework for reasoning. Artificial Intelligence113 41-85. · Zbl 0939.68847
[20] Denchev, V. S., Boixo, S., Isakov, S. V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J. and Neven, H. (2016). What is the computational value of finite range tunneling? Available at arXiv:1512.02206v4.
[21] Deutsch, D. (1985). Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. Roy. Soc. London Ser. A400 97-117. · Zbl 0900.81019
[22] Devoret, M. H., Wallra, A. and Martinis, J. M. (2004). Superconducting qubits: A short review. Available at arXiv:cond-mat/0411174v1.
[23] DiCarlo, L., Chow, J. M., Gambetta, J. M., Bishop, L. S., Johnson, B. R., Schuster, D. I., Majer, J., Blais, A., Frunzio, L., Girvin, S. M. and Schoelkopf, R. J. (2009). Demonstration of two-qubit algorithms with a superconducting quantum processor. Nature460 240-244.
[24] DiVincenzo, D. P. (1995). Quantum computation. Science270 255-261. · Zbl 1226.68037
[25] Farhi, E., Goldstone, J., Gutmann, S. and Sipser, M. (2000). Quantum computation by adiabatic evolution. Available at arXiv:quant-ph/0001106v1.
[26] Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A. and Preda, D. (2001). A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science292 472-476. · Zbl 1226.81046
[27] Farhi, E., Goldstone, J., Gutmann, S. and Sipser, M. (2002). Quantum adiabatic evolution algorithms versus simulated annealing. Available at arXiv:quant-ph/0201031v1.
[28] Feynman, R. P. (1981/82). Simulating physics with computers. Internat. J. Theoret. Phys.21 467-488.
[29] Geman, S. and Geman, D. (1984). Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell.6 721-741. · Zbl 0573.62030
[30] Hajek, B. (1988). Cooling schedules for optimal annealing. Math. Oper. Res.13 311-329. · Zbl 0652.65050
[31] Hartigan, J. A. and Hartigan, P. M. (1985). The dip test of unimodality. Ann. Statist.13 70-84. · Zbl 0575.62045
[32] Hen, I., Job, J., Albash, T., Rønnow, T. F., Troyer, M. and Lidar, D. A. (2015). Probing for quantum speedup in spin glass problems with planted solutions. Available at arXiv:1502.01663v2.
[33] Holevo, A. S. (1982). Probabilistic and Statistical Aspects of Quantum Theory. North-Holland Series in Statistics and Probability1. North-Holland, Amsterdam. · Zbl 0497.46053
[34] Irback, A., Peterson, C. and Potthast, F. (1996). Evidence for nonrandom hydrophobicity structures in protein chains. Proc. Natl. Acad. Sci. USA93 533-538.
[35] Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., Chapple, E. M., Enderud, C., Hilton, J. P., Karimi, K., Ladizinsky, E., Ladizinsky, N., Oh, T., Perminov, I., Rich, C., Thom, M. C., Tolkacheva, E., Truncik, C. J. S., Uchaikin, S., Wang, J., Wilson, B. and Rose, G. (2011). Quantum annealing with manufactured spins. Nature473 194-198.
[36] Jones, N. (2013). D-Wave is pioneering a novel way of making quantum computers—but it is also courting controversy. Nature498 286-288.
[37] Kato, T. (1978). Trotter’s product formula for an arbitrary pair of self-adjoint contraction semigroups. In Topics in Functional Analysis (Essays Dedicated to M. G. KreĭN on the Occasion of His 70th Birthday). Adv. in Math. Suppl. Stud.3 185-195. Academic Press, New York. · Zbl 0461.47018
[38] Katzgraber, H. G., Hamze, F. and Andrist, R. S. (2014). Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines. Phys. Rev. X4 021008.
[39] Kechedzhi, K. and Smelyanskiy, V. N. (2015). Open system quantum annealing in mean field models with exponential degeneracy. Available at arXiv:1505.05878v1.
[40] Kirkpatrick, S., Gelatt, C. D. Jr. and Vecchi, M. P. (1983). Optimization by simulated annealing. Science220 671-680. · Zbl 1225.90162
[41] Lanting, T., Przybysz, A. J., Smirnov, A. Yu., Spedalieri, F. M., Amin, M. H., Berkley, A. J., Harris, R., Altomare, F., Boixo, S., Bunyk, P., Dickson, N., Enderud, C., Hilton, J. P., Hoskinson, E., Johnson, M. W., Ladizinsky, E., Ladizinsky, N., Neufeld, R., Oh, T., Perminov, I., Rich, C., Thom, M. C., Tolkacheva, E., Uchaikin, S., Wilson, A. B. and Rose, G. (2014). Entanglement in a quantum annealing processor. Phys. Rev. X4 021041.
[42] Majewski, J., Li, H. and Ott, J. (2001). The Ising model in physics and statistical genetics. Am. J. Hum. Genet.69 853-862.
[43] Martin-Mayor, V. and Hen, I. (2015). Unraveling quantum annealers using classical hardness. Available at arXiv:1502.02494v1.
[44] Martoňák, R., Santoro, G. E. and Tosatti, E. (2002). Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model. Phys. Rev. B66 094203.
[45] McGeoch, C. C. (2014). Adiabatic Quantum Computation and Quantum Annealing. Synthesis Lectures on Quantum Computing. Morgan & Claypool Publisher, San Rafael, CA.
[46] Morita, S. and Nishimori, H. (2008). Mathematical foundation of quantum annealing. J. Math. Phys.49 125210, 47. · Zbl 1159.81332
[47] Neumann, P., Mizuochi, N., Rempp, F., Hemmer, P., Watanabe, H., Yamasaki, S., Jacques, V., Gaebel, T., Jelezko, F. and Wrachtrup, J. (2008). Multipartite entanglement among single spins in diamond. Science320 1326-1329.
[48] Nielsen, M. A. and Chuang, I. L. (2000). Quantum Computation and Quantum Information. Cambridge Univ. Press, Cambridge. · Zbl 1049.81015
[49] O’Gorman, B., Babbush, R., Perdomo-Ortiz, A., Aspuru-Guzik, A. and Smelyanskiy, V. (2014). Bayesian network structure learning using quantum annealing. Available at arXiv:1407.3897v2.
[50] Perdomo-Ortiz, A., Dickson, N., Drew-Brook, M., Rose, G. and Aspuru-Guzik, A. (2012). Finding low-energy conformations of lattice protein models by quantum annealing. Sci. Rep.2 571.
[51] Perdomo-Ortiz, A., Fluegemann, J., Narasimhan, S., Biswas, R. and Smelyanskiy, V. N. (2014). A quantum annealing approach for fault detection and diagnosis of graph-based systems. Available at arXiv:1406.7601v2.
[52] Pudenz, K. L., Albash, T. and Lidar, D. A. (2014). Error corrected quantum annealing with hundreds of qubits. Nature Comm.5 3243.
[53] Rieffel, E., Venturelli, D., O’Gorman, B., Do, M., Prystay, E. and Smelyanskiy, V. (2014). A case study in programming a quantum annealer for hard operational planning problems. Available at arXiv:1407.2887v1. · Zbl 1311.81084
[54] Rieger, H. and Kawashima, N. (1999). Application of a continuous time cluster algorithm to the two-dimensional random quantum Ising ferromagnet. Eur. Phys. J. B9 233-236.
[55] Robertson, T., Wright, F. T. and Dykstra, R. L. (1988). Order Restricted Statistical Inference. Wiley, Chichester. · Zbl 0645.62028
[56] Rønnow, T. F., Wang, Z., Job, J., Boixo, S., Isakov, S. V., Wecker, D., Martinis, J. M., Lidar, D. A. and Troyer, M. (2014). Defining and detecting quantum speedup. Science25 420-424. 6195.
[57] Sakurai, J. J. and Napolitano, J. (2010). Modern Quantum Mechanics, 2nd ed. Addison-Wesley, Reading. · Zbl 1392.81003
[58] Santoro, G. E., Martonák, R., Tosatti, E. and Car, R. (2002). Theory of quantum annealing of an Ising spin glass. Science295 2427-2430.
[59] Shankar, R. (1994). Principles of Quantum Mechanics, 2nd ed. Plenum Press, New York. · Zbl 0893.00007
[60] Shin, S. W., Smith, G., Smolin, J. A. and Vazirani, U. (2014). How “quantum” is the D-Wave machine? Available at arXiv:1401.7087v1.
[61] Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM, 1994) 124-134. IEEE Comput. Soc. Press, Los Alamitos, CA.
[62] Smolin, J. A. and Smith, G. (2014). Classical signature of quantum annealing. Front. Phys.2 52.
[63] Stauffer, D. (2008). Social applications of two-dimensional Ising models. Am. J. Phys.76 470-473.
[64] Suzuki, M. (1976). Generalized Trotter’s formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems. Comm. Math. Phys.51 183-190. · Zbl 0341.47028
[65] Trotter, H. F. (1959). On the product of semi-groups of operators. Proc. Amer. Math. Soc.10 545-551. · Zbl 0099.10401
[66] Venturelli, D., Mandrá, S., Knysh, S., O’Gorman, B., Biswas, R. and Smelyanskiy, V. N. (2014). Quantum optimization of fully-connected spin glasses. Available at arXiv:1406.7553v1.
[67] Vinci, W., Albash, T., Mishra, A., Warburton, P. A. and Lidar, D. A. (2014). Distinguishing classical and quantum models for the D-Wave device. Available at arXiv:1403.4228v1.
[68] Wang, Y. (1995). The \(L_1\) theory of estimation of monotone and unimodal densities. J. Nonparametr. Statist.4 249-261. · Zbl 1383.62103
[69] Wang, Y. (2011). Quantum Monte Carlo simulation. Ann. Appl. Stat.5 669-683. · Zbl 1223.62174
[70] Wang, Y. (2012). Quantum computation and quantum information. Statist. Sci.27 373-394. · Zbl 1331.81080
[71] Wang, Y. (2013). Asymptotic equivalence of quantum state tomography and noisy matrix completion. Ann. Statist.41 2462-2504. · Zbl 1294.62006
[72] Wang, Y. and Xu, C. (2015). Density matrix estimation in quantum homodyne tomography. Statist. Sinica25 953-973. · Zbl 1415.81016
[73] Wang, L., Rønnow, T. F., Boixo, S., Isakov, S. V., Wang, Z., Wecker, D., Lidar, D. A., Martinis, J. M. and Troyer, M. (2013). Comment on “Classical signature of quantum annealing.” Available at arXiv:1305.5837v1.
[74] Winker, P. (2001). Optimization Heuristics in Econometrics: Applications of Threshold Accepting. Wiley, Chichester. · Zbl 1001.62043
[75] Xu, C.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.