Help us understand the problem. What is going on with this article?

「量子アニーリングの基礎」の参考文献の参考文献

More than 1 year has passed since last update.

「量子アニーリングの基礎」を読む
https://qiita.com/kaizen_nagoya/items/29580dc526e142cb64e9

量子アニーリングの基礎 西森 秀稔, 大関 真之, 共立出版, 2018
68747470733a2f2f71696974612d696d6167652d73746f72652e73332e61702d6e6f727468656173742d312e616d617a6f6e6177732e636f6d2f302f35313432332f64386632366435342d303330632d643861612d363035332d3362316663633337653763332e6a706567.jpeg
https://www.amazon.co.jp/dp/4320035380

2019年7月19日から、読書会を毎週第三金曜日に予定しています。
T-QARDの日々 量子コンピュータへのお勧めの入口
https://qiita.com/kaizen_nagoya/items/fb869e5f38ae354e6294

参加条件は、上記の動画の一つ以上を見て、感想を16文字以上(言語は問わない)書いて出してくださることです。あわせて、担当の希望(どれか1つの章)を書いていただけると幸いです。
場所:名古屋市熱田区六番3−4−41 名古屋市工業研究所 電子技術総合センター5F コンピュータ研修室(地下鉄名港線「六番町」下車(3番出口))
https://www.nmiri.city.nagoya.jp/access.html
参加費:無償

4

[1] D. Aharonov and M. Ben-Or, “Polynomial Simulations of Decohered
Quantum Computers,” in Proceedings of 37th Conference
on Foundations of Computer Science (FOCS) (IEEE Comput.
Soc. Press, Los Alamitos, CA, 1996) p. 46.
[2] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, “Quantum
computation by adiabatic evolution,” ArXiv (2000), quantph/
0001106 (2000).
[3] Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau,
Seth Lloyd, and Oded Regev, “Adiabatic quantum computation
is equivalent to standard quantum computation,” SIAM J.
Comput. 37, 166–194 (2007).
[4] Ari Mizel, Daniel A. Lidar, and Morgan Mitchell, “Simple
proof of equivalence between adiabatic quantum computation
and the circuit model,” Phys. Rev. Lett. 99, 070502 (2007).
[5] David Gosset, Barbara M. Terhal, and Anna Vershynina,
“Universal adiabatic quantum computation via the space-time
circuit-to-hamiltonian construction,” arXiv:1409.7745 (2014).
[6] Andrew M. Childs, Edward Farhi, and John Preskill, “Robustness
of adiabatic quantum computation,” Phys. Rev. A 65,
012322 (2001).
[7] M. S. Sarandy and D. A. Lidar, “Adiabatic quantum computation
in open systems,” Phys. Rev. Lett. 95, 250503– (2005).
[8] Johan A° berg, David Kult, and Erik Sjo¨qvist, “Quantum adiabatic
search with decoherence in the instantaneous energy
eigenbasis,” Phys. Rev. A 72, 042317 (2005).
[9] J´er´emie Roland and Nicolas J. Cerf, “Noise resistance of adiabatic
quantum computation using random matrix theory,” Phys.
Rev. A 71, 032330 (2005).
[10] W. M. Kaminsky and S. Lloyd, “Scalable Architecture for Adiabatic
Quantum Computing of NP-Hard Problems,” in Quantum
Computing and Quantum Bits in Mesoscopic Systems, edited by
A.A.J. Leggett, B. Ruggiero, and P. Silvestrini (Kluwer Academic/
Plenum Publ., 2004) arXiv:quant-ph/0211152.
[11] M. H. S. Amin, Dmitri V. Averin, and James A. Nesteroff,
“Decoherence in adiabatic quantum computation,” Phys. Rev.
A 79, 022107 (2009).
[12] M. H. S. Amin, C. J. S. Truncik, and D. V. Averin, “Role of
single-qubit decoherence time in adiabatic quantum computation,”
Phys. Rev. A 80, 022303 (2009).
[13] M. H. S. Amin, Peter J. Love, and C. J. S. Truncik, “Thermally
assisted adiabatic quantum computation,” Phys. Rev. Lett. 100,
17
060503 (2008).
[14] Tameem Albash, Sergio Boixo, Daniel A Lidar, and Paolo Zanardi,
“Quantum adiabatic markovian master equations,” New
J. of Phys. 14, 123016 (2012).
[15] Markus Tiersch and Ralf Sch¨utzhold, “Non-markovian decoherence
in the adiabatic quantum search algorithm,” Phys. Rev.
A 75, 062313 (2007).
[16] In´es de Vega, Mari Carmen Ba˜nuls, and A P´erez, “Effects of
dissipation on an adiabatic quantum search algorithm,” New J.
of Phys. 12 (2010).
[17] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting,
F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson,
P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi,
E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich,
M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin,
J. Wang, B. Wilson, and G. Rose, “Quantum annealing with
manufactured spins,” Nature 473, 194–198 (2011).
[18] A J Berkley, M W Johnson, P Bunyk, R Harris, J Johansson,
T Lanting, E Ladizinsky, E Tolkacheva, M H S Amin, and
G Rose, “A scalable readout system for a superconducting adiabatic
quantum optimization system,” Superconductor Science
and Technology 23, 105014 (2010).
[19] F. Yoshihara, K. Harrabi, A. O. Niskanen, Y. Nakamura, and
J. S. Tsai, “Decoherence of flux qubits due to 1=f flux noise,”
Phys. Rev. Lett. 97, 167001 (2006).
[20] R. Harris, J. Johansson, A. J. Berkley, M. W. Johnson, T. Lanting,
Siyuan Han, P. Bunyk, E. Ladizinsky, T. Oh, I. Perminov,
E. Tolkacheva, S. Uchaikin, E. M. Chapple, C. Enderud,
C. Rich, M. Thom, J. Wang, B. Wilson, and G. Rose, “Experimental
demonstration of a robust and scalable flux qubit,” Phys.
Rev. B 81, 134510 (2010).
[21] Ch Kaiser, J. M. Meckbach, K. S. Ilin, J. Lisenfeld, R. Sch¨afer,
A. V. Ustinov, and M. Siegel, “Aluminum hard mask technique
for the fabrication of high quality submicron Nb/Al–AlOx/Nb
josephson junctions,” Superconductor Science and Technology
24, 035005 (2011).
[22] N. G. Dickson, M. W. Johnson, M. H. Amin, R. Harris,
F. Altomare, A. J. Berkley, P. Bunyk, J. Cai, E. M. Chapple,
P. Chavez, F. Cioata, T. Cirip, P. deBuen, M. Drew-Brook,
C. Enderud, S. Gildert, F. Hamze, J. P. Hilton, E. Hoskinson,
K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Lanting, T. Mahon,
R. Neufeld, T. Oh, I. Perminov, C. Petroff, A. Przybysz,
C. Rich, P. Spear, A. Tcaciuc, M. C. Thom, E. Tolkacheva,
S. Uchaikin, J. Wang, A. B. Wilson, Z. Merali, and G. Rose,
“Thermally assisted quantum annealing of a 16-qubit problem,”
Nat. Commun. 4, 1903 (2013).
[23] Sergio Boixo, Tameem Albash, Federico M. Spedalieri,
Nicholas Chancellor, and Daniel A. Lidar, “Experimental signature
of programmable quantum annealing,” Nat. Commun. 4,
2067 (2013).
[24] Sergio Boixo, Troels F. Ronnow, Sergei V. Isakov, Zhihui
Wang, David Wecker, Daniel A. Lidar, John M. Martinis, and
Matthias Troyer, “Evidence for quantum annealing with more
than one hundred qubits,” Nat. Phys. 10, 218–224 (2014).
[25] Lei Wang, Troels F. Rønnow, Sergio Boixo, Sergei V. Isakov,
Zhihui Wang, David Wecker, Daniel A. Lidar, John M. Martinis,
and Matthias Troyer, “Comment on: ‘Classical signature
of quantum annealing’,” arXiv:1305.5837 (2013).
[26] P. J. D. Crowley, T. Duric, W. Vinci, P. A. Warburton, and
A. G. Green, “Quantum and classical in adiabatic computation,”
arXiv:1405.5185 (2014).
[27] Walter Vinci, Tameem Albash, Anurag Mishra, Paul A.Warburton,
and Daniel A. Lidar, “Distinguishing classical and quantum
models for the D-Wave device,” arXiv:1403.4228 (2014).
[28] Helmut G. Katzgraber, Firas Hamze, and Ruben S. Andrist,
“Glassy chimeras could be blind to quantum speedup: Designing
better benchmarks for quantum annealing machines,” Phys.
Rev. X 4, 021008– (2014).
[29] T. Lanting, A. J. Przybysz, A. Yu. Smirnov, F. M. Spedalieri,
M. H. Amin, A. J. Berkley, R. Harris, F. Altomare, S. Boixo,
P. Bunyk, N. Dickson, C. Enderud, J. P. Hilton, E. Hoskinson,
M. W. Johnson, E. Ladizinsky, N. Ladizinsky, R. Neufeld,
T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva,
S. Uchaikin, A. B. Wilson, and G. Rose, “Entanglement in a
quantum annealing processor,” Phys. Rev. X 4, 021041– (2014).
[30] Sergio Boixo, Vadim N. Smelyanskiy, Alireza Shabani,
Sergei V. Isakov, Mark Dykman, Vasil S. Denchev, Mohammad
Amin, Anatoly Smirnov, Masoud Mohseni, and Hartmut
Neven, “Computational role of collective tunneling in a quantum
annealer,” arXiv:1411.4036 (2014).
[31] Kristen L. Pudenz, Tameem Albash, and Daniel A. Lidar,
“Quantum annealing correction for random ising problems,”
arXiv:1408.4382 (2014).
[32] Daniel A. Lidar, Ali T. Rezakhani, and Alioscia Hamma,
“Adiabatic approximation with exponential accuracy for manybody
systems and quantum computation,” J. Math. Phys. 50, –
(2009).
[33] N. Wiebe and N. S. Babcock, “Improved error-scaling for adiabatic
quantum evolutions,” New J. Phys. 14, 013024 (2012).
[34] G. Lindblad, “On the generators of quantum dynamical semigroups,”
Comm. Math. Phys. 48, 119–130 (1976).
[35] Vittorio Gorini, Andrzej Kossakowski, and E. C. G. Sudarshan,
“Completely positive dynamical semigroups of n-level
systems,” J. Math. Phys. 17, 821–825 (1976).
[36] R. Alicki and K. Lendi, Quantum Dynamical Semigroups and
Applications, Lecture Notes in Physics, Vol. 286 (Springer-
Verlag, Berlin, 1987).
[37] H.-P. Breuer and F. Petruccione, The Theory of Open Quantum
Systems (Oxford University Press, Oxford, 2002).
[38] M.H. Levitt, Spin Dynamics: Basics of Nuclear Magnetic Resonance
(Wiley, 2001).
[39] E. Knill and R. Laflamme, “Power of one bit of quantum information,”
Phys. Rev. Lett. 81, 5672–5675 (1998).
[40] D.A. Lidar and T.A. Brun, eds., Quantum Error Correction
(Cambridge University Press, Cambridge, UK, 2013).
[41] Tadashi Kadowaki and Hidetoshi Nishimori, “Quantum annealing
in the transverse Ising model,” Phys. Rev. E 58, 5355
(1998).
[42] P. Ray, B. K. Chakrabarti, and Arunava Chakrabarti,
“Sherrington-kirkpatrick model in a transverse field: Absence
of replica symmetry breaking due to quantum fluctuations,”
Phys. Rev. B 39, 11828–11832 (1989).
[43] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan,
Andrew Lundgren, and Daniel Preda, “A quantum adiabatic
evolution algorithm applied to random instances of an
NP-Complete problem,” Science 292, 472–475 (2001).
[44] Arnab Das and Bikas K. Chakrabarti, “Colloquium: Quantum
annealing and analog quantum computation,” Rev. Mod. Phys.
80, 1061–1081 (2008).
[45] Andrew D. King and Catherine C. McGeoch, “Algorithm engineering
for a quantum annealing platform,” arXiv:1410.2628
(2014).
[46] Dorit Aharonov, Itai Arad, and Thomas Vidick, “The quantum
pcp conjecture,” ACM SIGACT News 44, 47 (2013).
[47] M. Born and V. Fock, “Beweis des adiabatensatzes,” Zeitschrift
f¨ur Physik 51, 165–180 (1928).
[48] Tosio Kato, “On the adiabatic theorem of quantum mechanics,”
Journal of the Physical Society of Japan 5, 435–439 (1950).
18
[49] Sabine Jansen, Mary-Beth Ruskai, and Ruedi Seiler, “Bounds
for the adiabatic approximation with applications to quantum
computation,” J. Math. Phys. 48, – (2007).
[50] M. H. S. Amin, “Consistency of the adiabatic theorem,” Phys.
Rev. Lett. 102, 220401 (2009).
[51] Matthias Steffen, Wim van Dam, Tad Hogg, Greg Breyta, and
Isaac Chuang, “Experimental implementation of an adiabatic
quantum optimization algorithm,” Phys. Rev. Lett. 90, 067903–
(2003).
[52] M. S. Sarandy and D. A. Lidar, “Adiabatic approximation in
open quantum systems,” Phys. Rev. A 71, 012331 (2005).
[53] Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin, Han-
Hsuan Lin, and Peter Shor, “Different strategies for optimization
using the quantum adiabatic algorithm,” arXiv preprint
arXiv:1401.7320 (2014).
[54] J´er´emie Roland and Nicolas J. Cerf, “Quantum search by local
adiabatic evolution,” Phys. Rev. A 65, 042308– (2002).
[55] A. T. Rezakhani,W. J. Kuo, A. Hamma, D. A. Lidar, and P. Zanardi,
“Quantum adiabatic brachistochrone,” Phys. Rev. Lett.
103, 080502– (2009).
[56] A. T. Rezakhani, A. K. Pimachev, and D. A. Lidar, “Accuracy
versus run time in an adiabatic quantum search,” Phys. Rev. A
82, 052305– (2010).
[57] J. E. Avron, M. Fraas, G. M. Graf, and P. Grech, “Optimal
time schedule for adiabatic evolution,” Phys. Rev. A 82, 040304
(2010).
[58] S. P. Jordan, E. Farhi, and P. W. Shor, “Error-correcting codes
for adiabatic quantum computation,” Phys. Rev. A 74, 052322
(2006).
[59] D. A. Lidar, “Towards fault tolerant adiabatic quantum computation,”
Phys. Rev. Lett. 100, 160506 (2008).
[60] Gerardo A. Paz-Silva, A. T. Rezakhani, Jason M. Dominy, and
D. A. Lidar, “Zeno effect for quantum computation and control,”
Phys. Rev. Lett. 108, 080501 (2012).
[61] Kristen L Pudenz, Tameem Albash, and Daniel A Lidar,
“Error-corrected quantum annealing with hundreds of qubits,”
Nat. Commun. 5, 3243 (2014).
[62] Kevin C. Young, Mohan Sarovar, and Robin Blume-Kohout,
“Error suppression and error correction in adiabatic quantum
computation: Techniques and challenges,” Phys. Rev. X 3,
041013– (2013).
[63] Kevin C. Young, Robin Blume-Kohout, and Daniel A. Lidar,
“Adiabatic quantum optimization with the wrong hamiltonian,”
Phys. Rev. A 88, 062314– (2013).
[64] Mohan Sarovar and Kevin C Young, “Error suppression and
error correction in adiabatic quantum computation: nonequilibrium
dynamics,” New J. of Phys. 15, 125032 (2013).
[65] Anand Ganti, Uzoma Onunkwo, and Kevin Young, “Family
of [[6k,2k,2]] codes for practical, scalable adiabatic quantum
computation,” Phys. Rev. A 89, 042313– (2014).
[66] Adam D. Bookatz, Edward Farhi, and Leo Zhou, “Error suppression
in hamiltonian based quantum computation using energy
penalties,” arXiv:1407.1485 (2014).
[67] P. Zanardi and M. Rasetti, “Noiseless quantum codes,”
Phys. Rev. Lett. 79, 3306–3309 (1997).
[68] D. A. Lidar, I. L. Chuang, and K. B. Whaley, “Decoherencefree
subspaces for quantum computation,” Phys. Rev. Lett. 81,
2594–2597 (1998).
[69] L. A. Wu and D. A. Lidar, “Creating decoherence-free subspaces
using strong and fast pulses,” Phys. Rev. Lett. 88,
207902– (2002).
[70] Mark S. Byrd and Daniel A. Lidar, “Comprehensive encoding
and decoupling solution to problems of decoherence and design
in solid-state quantum computing,” Phys. Rev. Lett. 89, 047901
(2002).
[71] A. J. Leggett, S. Chakravarty, A. T. Dorsey, Matthew P. A.
Fisher, Anupam Garg, and W. Zwerger, “Dynamics of the dissipative
two-state system,” Rev. Mod. Phys. 59, 1–85 (1987).
[72] H. Dekker, “Noninteracting-blip approximation for a two-level
system coupled to a heat bath,” Phys. Rev. A 35, 1436–1437
(1987).
[73] Satoshi Morita and Hidetoshi Nishimori, “Mathematical foundation
of quantum annealing,” J. Math. Phys. 49, 125210–47
(2008).
[74] Roman Martoˇn´ak, Giuseppe E. Santoro, and Erio Tosatti,
“Quantum annealing by the path-integral Monte Carlo method:
The two-dimensional random Ising model,” Phys. Rev. B 66,
094203 (2002).
[75] Giuseppe E. Santoro, Roman Martoˇn´ak, Erio Tosatti, and
Roberto Car, “Theory of quantum annealing of an Ising spin
glass,” Science 295, 2427–2430 (2002).
[76] V. J. Emery and A. Luther, “Low- temperature properties of the
kondo hamiltonian,” Phys. Rev. B 9, 215–226 (1974).
[77] Philipp Werner, Klaus V¨olker, Matthias Troyer, and Sudip
Chakravarty, “Phase diagram and critical exponents of a dissipative
ising spin chain in a transverse magnetic field,” Phys.
Rev. Lett. 94, 047201 (2005).
[78] PhilippWerner and Matthias Troyer, “Cluster monte carlo algorithms
for dissipative quantum systems,” Progress of Theoretical
Physics Supplement 160, 395–417 (2005).
[79] G. Peskir and A. Shiryaev, Optimal Stopping and Free-
Boundary Problems, Lectures in Mathematics (ETH Z¨urich,
2006).
[80] Iman Marvian and Daniel A. Lidar, “Quantum error suppression
with commuting hamiltonians: Two local is too local,”
Phys. Rev. Lett. 113, 260504– (2014).
[81] Hidetoshi Nishimori, Junichi Tsuda, and Sergey Knysh, “Comparative
study of the performance of quantum annealing and
simulated annealing,” Phys. Rev. E 91, 012104– (2015).

5

[1] M. Mariantoni, H. Wang, T. Yamamoto, M. Neeley, R.
C. Bialczak, Y. Chen, M. Lenander, E. Lucero, A. D.
O'Connell, D. Sank, M. Weides, J. Wenner, Y. Yin, J.
Zhao, A. N. Korotkov, A. N. Cleland, J. M. Martinis, Im-
plementing the quantum von Neumann architecture with
superconducting circuits, Science 334, 61 (2011).
[2] E. Lucero, R. Barends, Y. Chen, J. Kelly, M. Mariantoni,
A. Megrant, P. O'Malley, D. Sank, A. Vainsencher, J.
Wenner, T. White, Y. Yin, A. N. Cleland, and J. M. Martinis,
Computing prime factors with a Josephson phase
qubit quantum processor, Nature Physics 8, 719 (2012).
[3] M. D. Reed, L. DiCarlo, S. E. Nigg, L. Sun, L. Frunzio,
S. M. Girvin, and R. J. Schoelkopf, Realization of
three-qubit quantum error correction with superconduct-
ing circuits, Nature 428, 382 (2012).
[4] A.G. Fowler, M. Mariantoni, J. M. Martinis, and A. N.
Cleland, et al., Surface codes: Towards practical large-
scale quantum computation, Phys. Rev. A 86, 032324
(2012).
[5] T.S. Metodi, D. D. Thaker, and A. W. Cross, A quan-
tum logic array microarchitecture: scalable quantum data
12
movement and computation, Proceedings of the 38th annual
IEEE/ACM International Symposium on Microarchitecture,
305 (2005); arXiv:quant-ph/0509051.
[6] M.W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting,
F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson,
P. Bunyk, E. M. Chapple, C. Enderud, J. P.
Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh,
I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C.
J. S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G.
Rose, Quantum annealing with manufactured spins, Nature
473, 194 (2011).
[7] N.G. Dickson, M. W. Johnson, M. H. Amin, R. Harris, F.
Altomare, A. J. Berkley, P. Bunyk, J. Cai, E. M. Chapple,
P. Chavez, F. Cioata, T. Cirip, P. deBuen, M. Drew-
Brook, C. Enderud, S. Gildert, F. Hamze, J. P. Hilton,
E. Hoskinson, K. Karimi, E. Ladizinsky, N. Ladizinsky,
T. Lanting, T. Mahon, R. Neufeld, T. Oh, I. Perminov,
C. Petro, A. Przybysz, C. Rich, P. Spear, A. Tcaciuc,
M. C. Thom, E. Tolkacheva, S. Uchaikin, J. Wang, A.
B. Wilson, Z. Merali, and G. Rose, Thermally assisted
quantum annealing of a 16-qubit problem, Nature Communications
4, 1903 (2013).
[8] R. Harris, M. W. Johnson, T. Lanting, A. J. Berkley,
J. Johansson, P. Bunyk, E. Tolkacheva, E. Ladizinsky,
N. Ladizinsky, T. Oh, F. Cioata, I. Perminov, P. Spear,
C. Enderud, C. Rich, S. Uchaikin, M. C. Thom, E. M.
Chapple, J.Wang, B. Wilson, M. H. S. Amin, N. Dickson,
K. Karimi, B. Macready, C. J. S. Truncik, and G. Rose,
Experimental investigation of an eight qubit unit cell in
a superconducting optimization processor, Phys. Rev. B
82, 024511 (2010).
[9] R. Blatt and D. Wineland, Entangled states of trapped
atomic ions, Nature 453, 1008 (2008).
[10] T. Monz, P. Schindler, J. T. Barreiro, M. Chwalla, D.
Nigg, W. A. Coish, M. Harlander, W. Hnsel, M. Hennrich,
and R. Blatt, 14-qubit entanglement: creation and
coherence, Phys. Rev. Lett. 106, 13506 (2011).
[11] M. Ansmann, H. Wang, R. C. Bialczak, M. Hofheinz, E. Lucero, M. Neeley, A. D. O'Connell, D. Sank, M. Weides, J. Wenner, A. N. Cleland, and J. M. Martinis, Violation of Bell's inequality in Josephson phase qubits, Nature 461, 504 (2009).
[12] M. Neeley, R. C. Bialczak, M. Lenander, E. Lucero, M.
Mariantoni, A. D. O'Connell, D. Sank, H.Wang, M.Weides,
J. Wenner, Y. Yin, T. Yamamoto, A. N. Cleland,
and J. M. Martinis, Generation of three-qubit entangled
states using superconducting phase qubits, Nature 467,
570 (2010).
[13] L. DiCarlo, M. D. Reed, L. Sun, B. R. Johnson, J. M.
Chow, J. M. Gambetta, L. Frunzio, S. M. Girvin, M. H.
Devoret, and R. J. Schoelkopf, Preparation and measure-
ment of three-qubit entanglement in a superconducting
circuit, Nature 467, 574 (2010).
[14] A.J. Berkley, H. Xu, R.C. Ramos, M.A. Gubrud, F.W.
Strauch, P.R. Johnson, J.R. Anderson, A.J. Dragt, C.J.
Lobb, and F.C. Wellstood, Entangled macroscopic quan-
tum states in two superconducting qubits, Science 300,
1548 (2003).
[15] G. Vidal, Ecient classical simulation of slightly entan-
gled quantum computations, Phys. Rev. Lett. 91, 147902
(2003).
[16] O. Guhne and G. Toth, Entanglement detection, Phys.
Rep. 474, 1 (2009).
[17] D. Greenberger, M. Horne, A. Shimony, and A. Zeilinger,
Bells theorem without inequalities, Am. J. Phys. 58, 1131
(1990).
[18] W.K. Wootters, Entanglement of formation of an arbitrary state of two qubits, Phys. Rev. Lett. 80, 2245 (1998).
[19] A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and
J.D. Doll, Quantum annealing: A new method for minimizing multidimensional functions, Chem. Phys. Lett. 219, 343 (1994).
[20] T. Kadowaki and H. Nishimori, Quantum annealing in
the transverse Ising model, Phys. Rev. E 58, 5355 (1998).
[21] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren,
and D. Preda, A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem, Science 292, 472 (2001).
[22] G.E. Santoro, R. Martonak, E. Tosatti, and R. Car, The-
ory of quantum annealing of an Ising spin glass, Science
295, 2427 (2002).
[23] A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose,
A. Aspuru-Guzik, Finding low-energy conformations of
lattice protein models by quantum annealing, Nature Scienti
c Reports 2, 571 (2012).
[24] S. Boixo, T. Albash, F. M. Spedalieri, N. Chancellor,
and D. A. Lidar, Experimental signature of programmable
quantum annealing, Nature Communications 4, 2067 (2013).
[25] R. Harris, T. Lanting, A. J. Berkley, J. Johansson, M.
W. Johnson, P. Bunyk, E. Ladizinsky, N. Ladizinsky, T.
Oh, and S. Han, A compound Josephson junction coupler
for ux qubits with minimal crosstalk, Phys. Rev. B 80, 052506 (2009).
[26] L. Amico, R. Fazio, A. Osterloch, and V. Vedral, Entan-
glement in many-body systems, Rev. Mod. Phys. 80, 517 (2008).
[27] X. Wang, Thermal and ground-state entanglement in
Heisenberg XX qubit rings, Phys. Rev. A 66, 034302 (2002).
[28] S. Ghosh, T.F. Rosenbaum, G. Aeppli, and S.N. Coppersmith,
Entangled quantum state of magnetic dipoles,
Nature 425, 48 (2003).
[29] T. Vertesi and E. Bene, Thermal entanglement in the
nanotubular system Na2V3O7, Phys. Rev. B 73, 134404
(2006).
[30] C. Brukner, V. Vedral , V. and A. Zeilinger, Crucial
role of quantum entanglement in bulk properties of solids,
Phys. Rev. A., 73, 012110 (2006).
[31] T.G. Rappoport, L. Ghivelder, J.C. Fernandes, R.B.
Guimaraes, and M.A. Continentino, Experimental obser-
vation of quantum entanglement in low-dimensional sys-
tems, Phys. Rev. B 75, 054422 (2007).
[32] N. B. Christensen,, H. M. Ronnow, D. F. McMorrow, A.
Harrison, T. G. Perring, T. G., M. Enderle, R. Coldea,
L. P Regnault, and G. Aeppli. Quantum dynamics and
entanglement of spins on a square lattice, PNAS 104,
15264 (2007).
[33] A. J. Berkley, A. J. Przybysz, T. Lanting, R. Harris,
N. Dickson, F. Altomare, M. H. Amin, P. Bunyk, C.
Enderud, E. Hoskinson, M. W. Johnson, E. Ladizinsky,
R. Neufeld, C. Rich, A. Yu. Smirnov, E. Tolkacheva, S.
Uchaikin, and A. B. Wilson, Tunneling spectroscopy us-
ing a probe qubit, Phys. Rev. B 87, 020502 (2013).
[34] A.Yu. Smirnov and M.H. Amin, Ground-state entangle-
ment in coupled qubits, Phys. Rev. A 88, 022329 (2013).
[35] G. Vidal and R.F. Werner, A computable measure of
entanglement, Phys. Rev. A 65, 032314 (2002).
[36] F.M. Spedalieri, Detecting entanglement with partial
state information, Phys. Rev. A 86, 062311 (2012).
[37] R. Harris, J. Johansson, A. J. Berkley, M. W. Johnson,
T. Lanting, Siyuan Han, P. Bunyk, E. Ladizinsky, T. Oh,
I. Perminov, E. Tolkacheva, S. Uchaikin, E. M. Chapple,
C. Enderud, C. Rich, M. Thom, J. Wang, B. Wilson,
and G. Rose, Experimental demonstration of a robust and
scalable ux qubit, Phys. Rev. B 81, 134510 (2010).
[38] J. Johansson, M. H. S. Amin, A. J. Berkley, P. Bunyk,
V. Choi, R. Harris, M. W. Johnson, T. M. Lanting, S. Lloyd, and G. Rose, Landau-Zener transitions in a superconducting ux qubit, Phys. Rev. B 80, 012507 (2009).
[39] R. Harris, M. W. Johnson, S. Han, A. J. Berkley, J. Johansson,
P. Bunyk, E. Ladizinsky, S. Govorkov, M. C. Thom, S. Uchaikin, B. Bumble, A. Fung, A. Kaul, A. Kleinsasser, M. H. S. Amin, and D. V. Averin, Probing
noise in ux qubits via macroscopic resonant tunneling, Phys. Rev. Lett., 101, 117003 (2008).

6

  1. Barahona, F. On the computational complexity of Ising spin glass models. J. Phys. Math. Gen. 15, 3241–3253 (1982).
  2. Kadowaki, T. & Nishimori, H. Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355–5363 (1998).
  3. Finnila, A. B., Gomez, M. A., Sebenik, C., Stenson, C. & Doll, J. D. Quantum annealing: a new method for minimizing multidimensional functions. Chem. Phys. Lett. 219, 343–348 (1994).
  4. Farhi, E. et al. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472–475 (2001).
  5. Hogg, T. Quantum search heuristics. Phys. Rev. A 61, 052311 (2000).
  6. Wernsdorfer, W. Molecular nanomagnets: towards molecular spintronics. Int. J. Nanotechnol. 7, 497–522 (2010).
  7. Carretta, S., Liviotti, E., Magnani, N., Santini, P. & Amoretti, G. S mixing and quantum tunneling of the magnetization in molecular nanomagnets. Phys. Rev. Lett. 92, 207205 (2004).
  8. Caciuffo, R. et al. Spin dynamics of heterometallic Cr7M wheels (M 5 Mn, Zn, Ni) probed by inelastic neutron scattering. Phys. Rev. B 71, 174407 (2005).
  9. Guidi, T. et al. Inelastic neutron scattering study of the molecular grid nanomagnet Mn-[3 3 3]. Phys. Rev. B 69, 104432 (2004).
  10. Waldmann,O.,Guidi,T.,Carretta,S.,Mondelli,C.&Dearden,A.L.Elementary excitations in the cyclic molecular nanomagnet Cr8. Phys. Rev. Lett. 91, 237202 (2003).
  11. Brooke,J.,Bitko,D.,Rosenbaum,T.F.&Aeppli,G.Quantumannealingofa disordered magnet. Science 284, 779–781 (1999).
  12. Ghosh,S.&Rosenbaum,T.F.Aeppli,G.&Coppersmith,S.N.Entangledquantum state of magnetic dipoles. Nature 425, 48–51 (2003).
  13. Harris, R. et al. Experimental demonstration of a robust and scalable flux qubit. Phys. Rev. B 81, 134510 (2010).
  14. Harris, R. et al. Experimental investigation of an eight-qubit unit cell in a superconducting optimization processor. Phys. Rev. B 82, 024511 (2010).
  15. Aharonov, D. et al. Adiabatic quantum computation is equivalent to standard quantum computation. SIAM J. Comput. 37, 166–194 (2007).
  16. Hinton, G. E. & Salakhutdinov, R. R. Reducing the dimensionality of data with neural networks. Science 313, 504–507 (2006).
  17. Chen, X. & Tompa, M. Comparative assessment of methods for aligning multiple genome sequences. Nature Biotechnol. 28, 567–572 (2010).
  18. Steffen,M.,vanDam,W.,Hogg,T.,Breyta,G.&Chuang,I.Experimental implementation of an adiabatic quantum optimization algorithm. Phys. Rev. Lett. 90, 067903 (2003).
  19. Kim, K. et al. Quantum simulation of frustrated Ising spins with trapped ions. Nature 465, 590–593 (2010).
  20. Lupas ̧cu, A. et al. Quantum non-demolition measurement of a superconducting two-level system. Nature Phys. 3, 119–125 (2007).
  21. Berns, D. M. et al. Amplitude spectroscopy of a solid-state artificial atom. Nature 455, 51–58 (2008).
  22. Poletto,S.etal.Coherentoscillationsinasuperconductingtunablefluxqubit manipulated without microwaves. N. J. Phys. 11, 013009 (2009).
  23. DiCarlo,L.etal.Demonstrationoftwo-qubitalgorithmswithasuperconducting quantum processor. Nature 460, 240–244 (2009).
  24. Bennett,D.A.etal.DecoherenceinrfSQUIDqubits.QuantumInf.Process.8, 217–243 (2009).
  25. Yoshihara,F.,Nakamura,Y.&Tsai,J.S.Correlatedfluxnoiseanddecoherencein two inductively coupled flux qubits. Phys. Rev. B 81, 132502 (2010).
  26. Il’ichev,E.etal.Multiphotonexcitationsandinversepopulationinasystemoftwo flux qubits. Phys. Rev. B 81, 012506 (2010).
  27. Vion,D.etal.Manipulatingthequantumstateofanelectricalcircuit.Science296, 886–889 (2002).
  28. Burkard,G.,Koch,R.H.&DiVincenzo,D.P.Multi level quantum description of decoherence in superconducting qubits. Phys. Rev. B 69, 064503 (2004).
  29. Harris,R.etal.CompoundJosephson-junctioncouplerforfluxqubitswithminimal crosstalk. Phys. Rev. B 80, 052506 (2009).
  30. Voss,R.F.&Webb,R.A.Macroscopicquantumtunnelingin1-mmNbJosephson junctions. Phys. Rev. Lett. 47, 265–268 (1981).
  31. Devoret,M.H.,Martinis,J.M.&Clarke,J.Measurements of macroscopic quantum tunneling out of the zero-voltage state of a current-biased josephson junction. Phys. Rev. Lett. 55, 1908–1911 (1985).
  32. Biamonte,J.D.&Love,P.J.RealizableHamiltoniansforuniversaladiabatic quantum computers. Phys. Rev. A 78, 012352 (2008).
  33. Harris,R.etal.Probing noise influxqubits via macroscopic resonant tunneling. Phys. Rev. Lett. 101, 117003 (2008). #7 [1] A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J. D. Doll, Chem. Phys. Lett. 219, 343 (1994). [2] T. Kadowaki and H. Nishimori, Phys. Rev. E 58, 5355 (1998). [3] G. E. Santoro, R. Martonak, E. Tosatti, and R. Car, Science 295, 2427 (2002). [4] S. Morita and H. Nishimori, J. Math. Phys. 49, 125210 (2008). [5] F. Barahona, J. Phys. A: Math. Gen 15, 3241 (1982). [6] H. Nishimori, Statistical Physics of Spin Glasses and Information Processing: An Introduction (Oxford University Press, Oxford, UK, 2001). [7] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science 220, 671 (1983). [8] J. Brooke, D. Bitko, T. F. Rosenbaum, and G. Aeppli, Science 284, 779 (1999). [9] J. Brooke, T. F. Rosenbaum, and G. Aeppli, Nature 413, 610 (2001). [10] A. Das and B. K. Chakrabarti, Rev. Mod. Phys. 80, 1061 (2008). [11] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, Science 292, 472 (2001). [12] S. Boixo and R. D. Somma, Phys. Rev. A 81, 032308 (2010), URL http://link.aps.org/doi/10.1103/PhysRevA.81.032308. [13] D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, SIAM J. Comput. 37, 166 (2007). [14] A. Mizel, D. A. Lidar, and M. Mitchell, Phys. Rev. Lett. 99, 070502 (2007), URL http://link.aps.org/doi/10.1103/PhysRevLett.99.070502. [15] R. D. Somma, S. Boixo, H. Barnum, and E. Knill, Phys. Rev. Lett. 101, 130504 (2008). [16] A. M. Childs, E. Farhi, and J. Preskill, Phys. Rev. A 65, 012322 (2001). [17] M. S. Sarandy and D. A. Lidar, Phys. Rev. Lett. 95, 250503 (2005). [18] M. H. S. Amin, P. J. Love, and C. J. S. Truncik, Phys. Rev. Lett. 100, 060503 (2008). [19] D. Patan`e, A. Silva, L. Amico, R. Fazio, and G. E. Santoro, Phys. Rev. Lett. 101, 175701 (2008). [20] I. de Vega, M. C. Ba˜nuls, and A. P´erez, New J. Phys. 12, 123010 (2010). [21] T. Albash, S. Boixo, D. A. Lidar, and P. Zanardi, arXiv:1206.4197 (2012). [22] R. Harris, M. W. Johnson, T. Lanting, A. J. Berkley, J. Johansson, P. Bunyk, E. Tolkacheva, E. Ladizinsky, N. Ladizinsky, T. Oh, et al., Physical Review B 82, 024511 (2010), URL http://link.aps.org/doi/10.1103/PhysRevB.82.024511. [23] A. J. Berkley, M. W. Johnson, P. Bunyk, R. Harris, J. Johansson, T. Lanting, E. Ladizinsky, E. Tolkacheva, M. H. S. Amin, and G. Rose, Superconductor Science and Technology 23, 105014 (2010), URL http://stacks.iop.org/0953-2048/23/i=10/a=105014. [24] M. W. Johnson, P. Bunyk, F. Maibaum, E. Tolkacheva, A. J. Berkley, E. M. Chapple, R. Harris, J. Johansson, T. Lanting, I. Perminov, et al., Superconductor Science and Technology 23, 065004 (2010), URL http://stacks.iop.org/0953-2048/23/i=6/a=065004. [25] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, et al., Nature 473, 194 (2011). [26] A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Aspuru-Guzik, Sci. Rep. 2, 571 (2012). [27] Z. Bian, F. Chudak, W. G. Macready, L. Clark, and F. Gaitan (2012), arXiv:1201.1842. [28] P. W. Shor, Phys. Rev. A 52, R2493 (1995). [29] J. Chiaverini, D. Leibfried, T. Schaetz, M. D. Barrett, R. B. Blakestad, J. Britton, W. M. Itano, J. D. Jost, E. Knill, C. Langer, et al., Nature 432, 602 (2004). [30] W. G. Unruh, Phys. Rev. A 51, 992 (1995), URL http://link.aps.org/doi/10.1103/PhysRevA.51.992. [31] M. Frigge, D. C. Hoaglin, and B. Iglewicz, The American Statistician 43, 50 (1989), URL http://www.jstor.org/stable/2685173. [32] H.-P. Breuer and F. Petruccione, The Theory of Open Quantum Systems (Oxford University Press, 2002). [33] J. H. Mathews and R. W. Howell, Complex Analysis: for Mathematics and Engineering (Jones and Bartlett Pub. Inc., Sudbury, MA, 2012), sixth ed. [34] R. Haag, N. M. Hugenholtz, and M. Winnink, Comm. Math. Phys. 5, 215 (1967). [35] J. Bertoin, F. Martinelli, Y. Peres, and P. Bernard, Lectures on Glauber Dynamics for Discrete Spin Models (Springer Berlin / Heidelberg, 2004), vol. 1717, pp. 93–191. #8 Muhly, J. in The beginning of the use of metals and alloys (ed Maddin, R.) The beginnings of metallurgy in the Old World. 2–20 (MIT Press, 1988).

Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Optimization by simulated annealing. Science 220, 671–680 (1983).

Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. & Teller, E. Equation of state calculations by fast computing machines. J. Chem. Phys. 21, 1087–1092 (1953).

Ray, P., Chakrabarti, B. K. & Chakrabarti, A. Sherrington–Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations. Phys. Rev. B 39, 11828–11832 (1989).

Finnila, A., Gomez, M., Sebenik, C., Stenson, C. & Doll, J. Quantum annealing: A new method for minimizing multidimensional functions. Chem. Phys. Lett. 219, 343–348 (1994).

Kadowaki, T. & Nishimori, H. Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355–5363 (1998).

Martoňák, R., Santoro, G. E. & Tosatti, E. Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model. Phys. Rev. B 66, 094203 (2002).

Santoro, G. E., Martoňák, R., Tosatti, E. & Car, R. Theory of quantum annealing of an Ising spin glass. Science 295, 2427–2430 (2002).

Battaglia, D. A., Santoro, G. E. & Tosatti, E. Optimization by quantum annealing: Lessons from hard satisfiability problems. Phys. Rev. E 71, 066707 (2005).

Brooke, J., Bitko, D., Rosenbaum, F. T. & Aeppli, G. Quantum annealing of a disordered magnet. Science 284, 779–781 (1999).

Johnson, M. W. et al. Quantum annealing with manufactured spins. Nature 473, 194–198 (2011).

Boixo, S., Albash, T., Spedalieri, F. M., Chancellor, N. & Lidar, D. A. Experimental signature of programmable quantum annealing. Nature Commun. 4, 2067 (2013).

Dickson, N. G. et al. Thermally assisted quantum annealing of a 16-qubit problem. Nature Commun. 4, 1903 (2013).

Barahona, F. On the computational complexity of Ising spin glass models. J. Phys. A 15, 3241–3253 (1982).

Farhi, E. et al. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472–475 (2001).
Jörg, T., Krzakala, F., Semerjian, G. & Zamponi, F. First-order transitions and the performance of quantum algorithms in random optimization problems. Phys. Rev. Lett. 104, 207206 (2010).

CASPubMedArticleGoogle Scholar
Hen, I. & Young, A. P. Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems. Phys. Rev. E 84, 061152 (2011).

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).

Bian, Z., Chudak, F., Macready, W. G., Clark, L. & Gaitan, F. Experimental determination of Ramsey numbers. Phys. Rev. Lett. 111, 130505 (2013).

CASPubMedArticleGoogle Scholar
Perdomo-Ortiz, A., Dickson, N., Drew-Brook, M., Rose, G. & Aspuru-Guzik, A. Finding low-energy conformations of lattice protein models by quantum annealing. Sci. Rep. 2, 571 (2012).

CASPubMedArticleGoogle Scholar
Kashurnikov, V. A., Prokof’ev, N. V., Svistunov, B. V. & Troyer, M. Quantum spin chains in a magnetic field. Phys. Rev. B 59, 1162–1167 (1999).

Young, A. P., Knysh, S. & Smelyanskiy, V. N. Size dependence of the minimum excitation gap in the quantum adiabatic algorithm. Phys. Rev. Lett. 101, 170503 (2008).

Altshuler, B., Krovi, H. & Roland, J. Anderson localization makes adiabatic quantum optimization fail. Proc. Natl Acad. Sci. USA 107, 12446–12450 (2010).

PubMedArticleGoogle Scholar
Dechter, R. Bucket elimination: A unifying framework for reasoning. Artif. Intell. 113, 41–85 (1999).

ArticleGoogle Scholar
McGeoch, C. C. & Wang, C. Proc. 2013 ACM Conf. Comput. Frontiers (ACM, 2013).
Choi, V. Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quant. Inform. Process. 10, 343–353 (2011).

Harris, R. et al. Experimental demonstration of a robust and scalable flux qubit. Phys. Rev. B 81, 134510 (2010).
Harris, R. et al. Experimental investigation of an eight-qubit unit cell in a superconducting optimization processor. Phys. Rev. B 82, 024511 (2010).
Berkley, A. J. et al. A scalable readout system for a superconducting adiabatic quantum optimization system. Supercond. Sci. Tech. 23, 105014 (2010).

9

[1] M. Mohseni, Y. Omar, G. S. Engel, and M. B. Ple- nio, Quantum effects in biology (Cambridge Univer- sity Press, 2014).
[2] P. Ray, B. K. Chakrabarti, and A. Chakrabarti, Phys. Rev. B 39, 11828 (1989).
[3] A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J. D. Doll, Chem. Phys. Lett. 219, 343 (1994).
[4] T. Kadowaki and H. Nishimori, Phys. Rev. E 58, 5355 (1998).
[5] J. Brooke, D. Bitko, T. F. Rosenbaum, and G. Aep- pli, Science 284, 779 (1999).
[6] E. Farhi, J. Goldstone, and S. Gutmann, arXiv:quant-ph/0201031 (2002).
[7] G. E. Santoro, R. Martonˇa ́k, E. Tosatti, and R. Car, Science 295, 2427 (2002).
[8] J. Mooij, T. Orlando, L. Levitov, L. Tian, C. H. Van der Wal, and S. Lloyd, Science 285, 1036 (1999).
[9] R. Harris, M. W. Johnson, T. Lanting, A. J. Berkley, J. Johansson, P. Bunyk, E. Tolkacheva, E. Ladizin- sky, N. Ladizinsky, T. Oh, F. Cioata, I. Perminov, P. Spear, C. Enderud, C. Rich, S. Uchaikin, M. C. Thom, E. M. Chapple, J. Wang, B. Wilson, M. H. S. Amin, N. Dickson, K. Karimi, B. Macready, C. J. S. Truncik, and G. Rose, Phys. Rev. B 82, 024511 (2010).
[10] T. Lanting, R. Harris, J. Johansson, M. H. S. Amin, A. J. Berkley, S. Gildert, M. W. Johnson, P. Bunyk, E. Tolkacheva, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, E. M. Chapple, C. Enderud, C. Rich, B. Wilson, M. C. Thom, S. Uchaikin, and G. Rose, Phys. Rev. B 82, 060512 (2010).
[11] M. Johnson, M. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. Berkley, J. Jo- hansson, P. Bunyk, et al., Nature 473, 194 (2011).
[12] S. Boixo, T. Albash, F. M. Spedalieri, N. Chancellor,
FIG. 7. Success probability for a glass of clusters as a function of the number of qubits involved. We fit the mean probability of success p(nq) ∝ exp(−αnq) as a function of the number of qubits nq (dashed lines). The fitting exponent α for the D-Wave Two data is (1.1±0.05)·10−2, while the fitting exponent for PIMC-QA is (2.2±0.1)·10−2 and for the SVMC numerics is (2.8±0.17)·10−2. The error estimates for the exponents are obtained by bootstrapping.
and D. A. Lidar, Nat. Commun. 4 (2013).
[13] N. Dickson, M. Johnson, M. Amin, R. Harris, F. Al- tomare, A. Berkley, P. Bunyk, J. Cai, E. Chapple,
P. Chavez, et al., Nat. Commun. 4, 1903 (2013).
[14] C. C. McGeoch and C. Wang, in Proceedings of the ACM International Conference on Computing Fron-
tiers (ACM, 2013) p. 23.
[15] S. Boixo, T. F. Rønnow, S. V. Isakov, Z. Wang,
D. Wecker, D. A. Lidar, J. M. Martinis, and
M. Troyer, Nat. Phys. 10, 218 (2014).
[16]T. Lanting, A. Przybysz, A. Y. Smirnov,
F. Spedalieri, M. Amin, A. Berkley, R. Harris, F. Altomare, S. Boixo, P. Bunyk, et al., Phys. Rev. X 4, 021041 (2014).
[17] S. Santra, G. Quiroz, G. Ver Steeg, and D. A. Lidar, New J. Phys. 16, 045006 (2014).
[18] T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, and M. Troyer, Science 345, 420 (2014).
[19] W. Vinci, K. Markstro ̈m, S. Boixo, A. Roy, F. M. Spedalieri, P. A. Warburton, and S. Severini, Sci. Rep. 4 (2014).
[20] S. W. Shin, G. Smith, J. A. Smolin, and U. Vazirani, arXiv:1401.7087 (2014).
[21] W. Vinci, T. Albash, A. Mishra, P. A. Warburton, and D. A. Lidar, arXiv:1403.4228 (2014).
[22] D.Venturelli,S.Mandra`,S.Knysh,B.O’Gorman, R. Biswas, and V. Smelyanskiy, arXiv:1406.7553 (2014).
[23] T. Albash, T. F. Rønnow, M. Troyer, and D. A. Li- dar, arXiv:1409.3827 (2014).
[24] S. Boixo, V. N. Smelyanskiy, A. Shabani, S. V. Isakov, M. Dykman, V. S. Denchev, M. Amin, A. Smirnov, M. Mohseni, and H. Neven, arXiv:1411.4036 (2014).
[25] A. Boulatov and V. N. Smelyanskiy, Phys. Rev. A 68 (2003), 10.1103/PhysRevA.68.062321.
[26] R. Harris, M. Johnson, S. Han, A. Berkley, J. Johans- son, P. Bunyk, E. Ladizinsky, S. Govorkov, M. Thom, S. Uchaikin, B. Bumble, A. Fung, A. Kaul, A. Klein- sasser, M. Amin, and D. Averin, Phys. Rev.Lett. 101, 117003 (2008).
[27] T. Lanting, M. H. S. Amin, M. W. Johnson, F. Al-
tomare, A. J. Berkley, S. Gildert, R. Harris, J. Jo- hansson, P. Bunyk, E. Ladizinsky, E. Tolkacheva, and D. V. Averin, Phys. Rev. B 83, 180502 (2011).
[28] S. Sendelbach, D. Hover, A. Kittel, M. Mck, J. M. Martinis, and R. McDermott, Phys. Rev. B 67,
094510 (2003).
[29] M. H. S. Amin and D. V. Averin, Phys. Rev. Lett.
100, 197001 (2008).
[30] A. J. Leggett, S. Chakravarty, A. T. Dorsey, M. P. A.
Fisher, A. Garg, and W. Zwerger, Ref. Mod. Phys.
59, 1 (1987).
[31] W. H. Zurek, Phys. Rev. D 24, 1516 (1981).

11

  1. Farhi E., Goldstone J., Gutmann S., Lapan J., Lundgren A., Preda D., A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472–475 (2001). [PubMed]
  2. Harris R. Johnson M. W. , Lanting T. , Berkley A. J. , Johansson J. , Bunyk P. , Tolkacheva E. , Ladizinsky E. , Ladizinsky N. , Oh T. , Cioata F. , Perminov I. , Spear P. , Enderud C. , Rich C. , Uchaikin S. , Thom M. C. , Chapple E. M. , Wang J. , Wilson B. , Amin M. H. S. , Dickson N. ,Karimi K.,Macready B., Truncik C. J. S. , Rose G. , et al., Experimental investigation of an eight-qubit unit cell in a superconducting optimization processor. Phys. Rev. B 82, 024511 (2010).
  3. 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., Rose G., Quantum annealing with manufactured spins. Nature 473, 194–198 (2011). [PubMed]
  4. Troyer M., Wiese U.-J., Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations. Phys. Rev. Lett. 94, 170201 (2005). [PubMed]
  5. 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).
  6. Rønnow T. F., Wang Z., Job J., Boixo S., Isakov S. V., Wecker D., Martinis J. M., Lidar D. A., Troyer M., Defining and detecting quantum speedup. Science 345, 420–424 (2014) [PubMed]
  7. Altshuler B., Krovi H., Roland J., Anderson localization makes adiabatic quantum optimization fail. Proc. Natl. Acad. Sci. U.S.A. 107, 12446–12450 (2010). [PMC free article] [PubMed]
  8. Jörg T., Krzakala F., Kurchan J., Maggs A. C., Simple glass models and their quantum annealing. Phys. Rev. Lett. 101, 147204 (2008). [PubMed] [Google Scholar]
  9. Boixo S., Albash T., Spedalieri F. M., Chancellor N., Lidar D. A., Experimental signature of programmable quantum annealing. Nat. Commun. 4, 2067 (2013). [PubMed] [Google Scholar]
  10. 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, 218–224 2014. [Google Scholar]
  11. Steffen M., van Dam W., Hogg T., Breyta G., Chuang I., Experimental implementation of an adiabatic quantum optimization algorithm. Phys. Rev. Lett. 90, 067903 (2003). [PubMed]
  12. Santoro G. E., Martoňák R., Tosatti E., Car R., Theory of quantum annealing of an Ising spin glass. Science 295, 2427–2430 (2002). [PubMed]
  13. Bloch I., Quantum coherence and entanglement with ultracold atoms in optical lattices. Nature 453, 1016–1022 (2008). [PubMed]
  14. Urban E., Johnson T. A., Henage T., Isenhower L., Yavuz D. D., Walker T. G., Saffman M., Observation of Rydberg blockade between two atoms. Nat. Phys. 5, 110–114 (2009). [Google Scholar]
  15. Kogut J., Susskind L., Hamiltonian formulation of Wilson’s lattice gauge theories. Phys. Rev. D 11, 395 (1975).
  16. Klymko C., Sullivan B. D., Humble T. S., Adiabatic quantum programming: Minor embedding with hard faults. Quantum Inf. Process. 13, 709–729 (2013).
  17. Perdomo-Ortiz A., Dickson N., Drew-Brook M., Rose G., Aspuru-Guzik A., Finding low-energy conformations of lattice protein models by quantum annealing. Sci. Rep. 2, 571 (2012). [PMC free article] [PubMed]
  18. Dennis E., Kitaev A., Landahl A., Preskill J., Topological quantum memory. J. Math. Phys. 43, 4452 (2002). [Google Scholar]

12

[1] Lechner, W., Hauke, P., Zoller, P., A quantum annealing architecture with all-to-all connectivity from local inter- actions. Science Advances, 1 (9), e1500838 (2015).
[2] Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lund- gren, A., Preda, D. A quantum adiabatic evolution al- gorithm applied to random instances of an NP-complete problem. Science , 292 (5516), 472-475 (2001).
[3] Gallager, R. G. Low-Density Parity-Check Codes. IRE Transactions on Information Theory 8 (1), 21-28 (1962).
[4] Loeliger, H. An Introduction to factor graphs, IEEE Sig-
nal Processing Magazine 21 (1), 28-41 (2004).
[5] Pearl, J. Reverend Bayes on inference engines: A dis- tributed hierarchical approach. Proc. of the Second Nat.
Conf. on Artificial Intelligence. pp. 133-136, (1982).
[6] Braunstein, A., M ́ezard, M., Zecchina, R. Survey prop- agation: An algorithm for satisfiability, Random Struc-
tures and Algorithms 27 (2) pp. 201-226 (2005).
[7] Boixo, S. et al. Evidence for quantum annealing with more than one hundred qubits. Nat. Phys. 10 (3), 218-
224 (2014).
[8] Albash T., Vinci W., Lidar D. A. Simulated Quantum Annealing with Two All-to-All Connectivity Schemes. arXiv:1603.03755 (2016).
[9] Bunyk, P. I. et al. Architectural Considerations in the Design of a Superconducting Quantum Annealing Pro- cessor IEEE Transactions on Applied Superconductivity 24 (4), 1-10 (2014).
[10] Jordan, S., Farhi, E., Shor, P. Error-correcting codes for adiabatic quantum computation. Phys. Rev. A, 74 (5), 052322 (2006).
[11] Lidar, D. A. Towards fault-tolerant adiabatic quantum computation. Phys. Rev. Lett., 100 (16), 160506 (2008). [12] Young, K. C., Sarovar, M., Blume-Kohout, R. Error sup- pression and error correction in adiabatic quantum com- putation: techniques and challenges. Phys. Rev. X, 3 (4), 041013 (2013).
[13] This choice for H matches the FFG in Fig. 1, and also
makes manifest the invariance of the code space under cyclic permutations of the bits

13

[1] J Ignacio Cirac and Peter Zoller, “Goals and opportu- nities in quantum simulation,” Nat. Phys. 8, 264–266
[2] Immanuel Bloch, Jean Dalibard, and Sylvain Nascim- bene, “Quantum simulations with ultracold quantum gases,” Nat. Phys. 8, 267–276 (2012).
[3] I. M. Georgescu, S. Ashhab, and Franco Nori, “Quantum simulation,” Rev. Mod. Phys. 86, 153–185 (2014).
[4] Chr. Wunderlich, Th. Hannemann, T. Ko ̈rber, H. Ha ̈ffner, C. F Roos, W. Ha ̈nsel, R. Blatt, and F. Schmidt-Kaler, “Robust state preparation of a single trapped ion by adiabatic passage,” J. Mod. Opt. 54, 1541–1549 (2007).
[5] Johannes Zeiher, Rick van Bijnen, Peter Schausz, Se-
bastian Hild, Jae-yoon Choi, Thomas Pohl, Immanuel ph].
Bloch, and Christian Gross, “Many-body interferome- try of a Rydberg-dressed spin lattice,” Nat. Phys. 12, 1095–1099 (2016).
[6] L. DiCarlo, M. D. Reed, L. Sun, B. R. Johnson, J. M. Chow, J. M. Gambetta, L. Frunzio, S. M. Girvin, M. H. Devoret, and R. J. Schoelkopf, “Preparation and mea- surement of three-qubit entanglement in a superconduct- ing circuit,” Nature 467, 574–578 (2010).
[7] H. Bernien, S. Schwartz, A. Keesling, H. Levine, A. Om- ran, H. Pichler, S. Choi, A. S. Zibrov, M. Endres, M. Greiner, V. Vuleti ́c, and M. D. Lukin, “Probing many-body dynamics on a 51-atom quantum simulator,” ArXiv e-prints (2017), arXiv:1707.04344 [quant-ph].
[8] J. M. Raimond, M. Brune, and S. Haroche, “Manipulat- ing quantum entanglement with atoms and photons in a cavity,” Rev. Mod. Phys. 73, 565–582 (2001).
[9] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone, “Quantum random access memory,” Phys. Rev. Lett. 100, 160501 (2008).
[10] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone, “Architectures for a quantum random access memory,” Phys. Rev. A 78, 052310 (2008).
[11] S. Lloyd, M. Mohseni, and P. Rebentrost, “Quantum al- gorithms for supervised and unsupervised machine learn- ing,” ArXiv e-prints (2013), arXiv:1307.0411 [quant-ph].
[12] Tadashi Kadowaki and Hidetoshi Nishimori, “Quantum annealing in the transverse ising model,” Phys. Rev. E 58, 5355–5363 (1998).
[13] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, “Quantum Computation by Adiabatic Evolution,” ArXiv e-prints (2000), arXiv:quant-ph/0001106 [quant-ph].
[14] Mohammad H. Amin, “Searching for quantum speedup in quasistatic quantum annealers,” Phys. Rev. A 92, 052323 (2015).
[15] Sergio Boixo, Vadim N Smelyanskiy, Alireza Shabani, Sergei V Isakov, Mark Dykman, Vasil S Denchev, Mohammad H Amin, Anatoly Yu Smirnov, Masoud Mohseni, and Hartmut Neven, “Computational multi- qubit tunnelling in programmable quantum annealers,” Nat. Commun. 7, 1–7 (2016), arXiv:arXiv:1411.4036v2.
[16] Yoshiki Matsuda, Hidetoshi Nishimori, and Helmut G Katzgraber, “Ground-state statistics from annealing al- gorithms: quantum versus classical approaches,” New J. Phys. 11, 073021 (2009).
[17] Sergio Boixo, Troels F. Ronnow, Sergei V. Isakov, Zhihui Wang, David Wecker, Daniel A. Lidar, John M. Martinis, and Matthias Troyer, “Evidence for quantum annealing with more than one hundred qubits,” Nat Phys 10, 218– 224 (2014).
[18] SalvatoreMandra`,ZhengZhu,andHelmutG.Katz- graber, “Exponentially biased ground-state sampling of quantum annealing machines with transverse-field driving hamiltonians,” Phys. Rev. Lett. 118, 070502 (2017).
[19] Wolfgang Lechner, Philipp Hauke, and Peter Zoller, “A quantum annealing architecture with all-to-all connectiv-
ity from local interactions,” Science Advances 1 (2015).
[20] Alexander W Glaetzle, Rick MW van Bijnen, Peter Zoller, and Wolfgang Lechner, “A coherent quantum an- nealer with rydberg atoms,” Nature Communications 8
(2017).
[21] A. Rocchetto, S. C. Benjamin, and Y. Li, “Stabilisers as
a design tool for new forms of Lechner-Hauke-Zoller An-nealer,” ArXiv e-prints (2016), arXiv:1603.08554 [quantph]
[22] Shruti Puri, Samuel Boutin, and Alexandre Blais, “En- gineering the quantum states of light in a kerr-nonlinear resonator by two-photon driving,” npj Quantum Infor- mation 3, 18 (2017).
[23] Martin Leib, Peter Zoller, and Wolfgang Lechner, “A transmon quantum annealer: Decomposing many-body ising constraints into pair interactions,” Quantum Sci- ence and Technology 1, 015008 (2016).
[24] Itay Hen, Joshua Job, Tameem Albash, Troels F. Rønnow, Matthias Troyer, and Daniel A. Lidar, “Prob- ing for quantum speedup in spin-glass problems with planted solutions,” Phys. Rev. A 92, 042325 (2015).
[25] John J Hopfield, “Neural networks and physical systems with emergent collective computational abilities,” Pro- ceedings of the national academy of sciences 79, 2554– 2558 (1982).
[26] To be published.
[27] T.W.B. Kibble, “Some implications of a cosmological phase transition,” Phys. Rep. 67, 183–199 (1980); “Topology of cosmic domains and strings,” J. Phys. A. Math. Gen. 9, 1387–1398 (2001); W.H. Zurek, “Cosmo- logical experiments in superfluid helium?” Nature 317, 505–508 (1985); “Cosmic Strings in Laboratory Superflu- ids and the Topological Remnants of Other Phase Tran- sitions,” Acta Phys. Pol. B 24, 1301 (1993); “Cosmo- logical experiments in condensed matter systems,” Phys. Rep. 276, 177–221 (1996).
[28] Bogdan Damski, “The simplest quantum model support- ing the kibble-zurek mechanism of topological defect pro- duction: Landau-zener transitions from a new perspec- tive,” Phys. Rev. Lett. 95, 035701 (2005), arXiv:0411004 [cond-mat].
[29] J R Schrieffer and P A Wolff, “Relation between the An- derson and Kondo Hamiltonians,” Phys. Rev. 149, 491– 492 (1966).
[30] As described in Sec. III C, both Heff (t) and USW (t) can be
expressed as perturbative expansions in 1−t/T; then, for
each term of order (1 − t/T )n in Heff (t), the correspond-
ing term in USW(t)U ̇ † (t) is of order (1/T)(1 − t/T)n−1. SW
To determine the control parameters for the protocol, we evaluate the effective Hamiltonian at td, which is typi- cally a finite fraction of T. Then, 1/T ≪ 1 − td/T, and the second term in Bnn′ (t) can safely be neglected.
[31] C De Grandi and A Polkovnikov, “Quantum Quenching, Annealing and Computation,” (Springer Berlin Heidel- berg, Berlin, Heidelberg, 2010) Chap. Adiabatic Pertur- bation Theory: From Landau-Zener Problem to Quench- ing Through a Quantum Critical Point, pp. 75–114.
[32] Sergey Bravyi, David P. DiVincenzo, and Daniel Loss, “SchriefferWolff transformation for quantum many-body systems,” Ann. Phys. (N. Y). 326, 2793–2826 (2011).
[33] Landau L D and Lifshitz E M, Quantum Mechanics: Non-relativistic Theory, 3rd ed. (Pergamon Press, Ox- ford, 1977).
[34] Note, that the minimum Ω({an}) = 0 can only be reached if there are no transitions out of the AMF.
[35] M V Berry, “Transitionless quantum driving,” J. Phys.
A Math. Theor. J. Phys. A Math. Theor 42, 365303–9
(2009).
[36] Sebastian Deffner, Christopher Jarzynski, and Adolfo
del Campo, “Classical and Quantum Shortcuts to Adi- abaticity for Scale-Invariant Driving,” Phys. Rev. X 4, 021013 (2014).
[37] Dries Sels and Anatoli Polkovnikov, “Minimizing irre- versible losses in quantum systems by local counterdia-
batic driving.” Proc. Natl. Acad. Sci. U. S. A. 114,
E3909–E3916 (2017).
[38] Ayoti Patra and Christopher Jarzynski, “Shortcuts to
adiabaticity using flow fields,” (2017), arXiv:1707.01490. [39] T. Caneva, M. Murphy, T. Calarco, R. Fazio, S. Mon- tangero, V. Giovannetti, and G. E. Santoro, “Optimal control at the quantum speed limit,” Phys. Rev. Lett. 103, 240501 (2009).
[40] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, “A Quantum Approximate Optimization Algorithm,” arXiv Prepr. arXiv1411.4028 , 1–16 (2014), arXiv:1411.4028. [41] S. P. Jordan, K. S. M. Lee, and J. Preskill, “Quantum Algorithms for Quantum Field Theories,” Science (80-.). 336, 1130–1133 (2012), arXiv:arXiv:1111.3633v2.

14

  1. D.Aharonov,W.vanDam,J.Kempe,Z.Landau,S.Lloyd,and O.Regev. A diabatic quantum computation is equivalent to standard quantum computation. Proc. 45th FOCS, 42–51, 2004.
  2. N. Alon and M. Capalbo. Optimal universal graphs with deterministic embedding. Proc. 19th SODA, 2008.
  3. H.L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209, 1–45, 1998.
  4. E. Boros and P. Hammer. Pseudo-boolean optimization. Discrete Appl. Math., (123):155– 225, 2002.
  5. E. Boros, P. L. Hammer, and G. Tavares. Preprocessing of quadratic unconstrained binary optimization. Technical Report RRR 10-2006, RUTCOR Research Report., 2006.
  6. V. Choi. Minor-embedding in adiabatic quantum computation: I. The parameter set- ting problem. Quantum Inf. Processing., 7, 193–209, 2008. Available at arXiv:quant- ph/0804.4884.
  7. V. Choi. Systems, Devices and Methods For Analog Processing, US Patent Application US2009/0121215, May 14, 2009.
  8. R. Diestel. Graph Theory. Springer-Verlag, Heidelberg, 2005.
  9. D-Wave Systems Inc. 100-4401 Still Creek Dr., Burnaby, V5C 6G9, BC, Canada. http://www.dwavesys.com/
  10. E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution. arXiv:quant-ph/0001106, 2000.
  11. E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science, 292(5516), 472–476, 2001.
  12. R. Harris and J. Johansson and A. J. Berkley and M. W. Johnson and T. Lanting and S. Han et al.. Experimental Demonstration of a Robust and Scalable Flux Qubit. arXiv:quant-ph/0909.4321, 2009.
  13. W.M. Kaminsky and S. Lloyd. Scalable architecture for adiabatic quantum computing of NP-hard problems. Quantum Computing and Quantum Bits in Mesoscopic Systems, 2004.
  14. W.M. Kaminsky, S. Lloyd, and T.P. Orlando. Scalable superconducting architecture for adiabatic quantum computation. arXiv.org:quant-ph/0403090, 2004.
  15. J.M.KleinbergandR.Rubinfeld.Shortpathsinexpandergraphs.Proc.37thFOCS,1996.
  16. I.L. Markov and Y. Shi. Simulating quantum computation by contracting tensor networks SIAM Journal on Computing, 38, 2008.
  17. N. Robertson and P.D. Seymour. Graph minors. xiii: the disjoint paths problem. J. Comb. Theory Ser. B, 63(1), 65–110, 1995.
  18. G. Rose, P. Bunyk, M.D. Coury, W. Macready, V. Choi. Systems, Devices, and Methods For Interconnected Processor Topology, US Patent Application US2008/0176750, July 24, 2008.
  19. L.F. Thomson. Introduction to parallel algorithms and architectures: arrays, trees, hyper- cubes. Morgan Kaufmann, San Mateo, California, 1992. #38 [1] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adia- batic evolution, 2000. arXiv:quant-ph/0001106. [2] DanielNagaj,RolandoD.Somma,MariaKieferova.QuantumSpeedupbyQuantumAnnealing.Physical Review Letters, 109(5):050501, 2012. arXiv:1202.6257 [quant-ph]. [3] T. Caneva, T. Calarco, R. Fazio, G. E. Santoro, S. Montangero. Speeding Up Critical System Dy- namics Through Optimized Evolution. Physical Review A, 84(1):012312, 2011. arXiv:1011.6634 [cond- mat.other]. [4] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. Quantum adiabatic evolution algorithms with different paths, 2002. arXiv:quant-ph/0208135. [5] Sergey Bravyi, David P. DiVincenzo, Roberto I. Oliveira, Barbara M. Terhal. The Complexity of Stoquastic Local Hamiltonian Problems. Quantum Information & Computation, 8(5):0361-0385, 2008. arXiv:quant-ph/0606140. [6] Sergey Bravyi, Arvid J. Bessen, Barbara M. Terhal. Merlin-Arthur Games and Stoquastic Complexity, 2006. arXiv:quant-ph/0611021. [7] Anders W. Sandvik. Computational Studies of Quantum Spin Systems. AIP Conference Proceedings, 1297:135, 2010. arXiv:1101.3281 [cond-mat.str-el]. [8] Edward Farhi, David Gosset, Itay Hen, A. W. Sandvik, Peter Shor, A. P. Young, Francesco Zamponi. Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs. Physical Review A, 86(5):052334, 2012. arXiv:1208.3757 [quant-ph]. #15
  20. Albash, T., Vinci, W., Mishra, A., Warburton, P.A., Lidar, D.A.: Consistency tests of classical and quantum models for a quantum annealer. Physical Review A 91(4), 042,314 (2015)
  21. Boixo, S., Smelyanskiy, V.N., Shabani, A., Isakov, S.V., Dykman, M., Denchev, V.S., Amin, M., Smirnov, A., Mohseni, M., Neven, H.: Computational role of collective tunneling in a quantum annealer. arXiv preprint arXiv:1411.4036 (2014)
  22. Cai, J., Macready, W., Roy, A.: A practical heuristic for finding graph minors. arXiv preprint arXiv:1406.2741 (2014)
  23. Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Information Processing 7(5), 193–209 (2008)
  24. Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Information Processing 10(3), 343–353 (2011)
  25. Dickson, N., et al.: Thermally assisted quantum annealing of a 16-qubit problem. Nature Communications 4(May), 1903 (2013). DOI 10.1038/ncomms2920. URL http://www. ncbi.nlm.nih.gov/pubmed/23695697
  26. Dziarmaga, J.: Dynamics of a quantum phase transition: Exact solution of the quantum ising model. Physical review letters 95(24), 245,701 (2005)
  27. 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)
  28. King, A.D., McGeoch, C.C.: Algorithm engineering for a quantum annealing platform. arXiv preprint arXiv:1410.2628 (2014)
  29. Klymko, C., Sullivan, B.D., Humble, T.S.: Adiabatic quantum programming: minor embedding with hard faults. Quantum Information Processing 13(3), 709–729 (2014) 14 Tomas Boothby et al.
  30. 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)
  31. Vatter, V., Waton, S.: On points drawn from a circle. Electronic Journal of Combinatorics 18(1), P223 (2011)
  32. Venturelli, D., Mandr`a, S., Knysh, S., O’Gorman, B., Biswas, R., Smelyanskiy, V.: Quantum optimization of fully-connected spin glasses. arXiv preprint arXiv:1406.7553(2014)
  33. Young, K., Blume-Kohout, R., Lidar, D.: Adiabatic quantum optimization with the wrong Hamiltonian. Physical Review A 88(6), 062,314 (2013)

16

[1] Kadowaki, T. and Nishimori, H., Quantum annealing in
the transverse Ising model, Physical Review E 58, 5355
(1998).
[2] Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., and Preda, D., A quantum adiabatic evolution
algorithm applied to random instances of an NP-complete
problem, Science, 292, 5516 (2001).
[3] Martoˇn´ak, R., Santoro, G. and Tosatti, E., Quantum annealing by the path-integral Monte Carlo method: The
two-dimensional random Ising model, Physical Review
B, 66, 9 (2002).
[4] Kirkpatrick, S., and Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598 (1983).
[5] Childs A.M., Farhi E. and Preskill J., Robustness of
adiabatic quantum computation, Physical Review A, 65,
012322 (2001).
[6] Rønnow, T.F., Wang, Z., Job, J., Boixo, S., Isakov, S.
V., Wecker, D, Martinis J.M., Lidar D.A. and Troyer M.,
Defining and detecting quantum speedup, Science, 345,
6195 (2014).
[7] Heim, B., Rønnow, T.F., Isakov S.V. and Troyer M.,
Quantum versus classical annealing of Ising spin glasses,
Science, 348, 6231 (2015).
[8] 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. and Whittaker, J., Architectural considerations in the design of a superconducting quantum annealing processor Applied Superconductivity, 24, 4 (2014).
[9] J¨org, T., Krzakala, F., Kurchan, J., Maggs, A.C. and
Pujos, J., Energy gaps in quantum first-order meanfield–like transitions: The problems that quantum annealing cannot solve, EPL (Europhysics Letters), 89, 40004
(2010)
[10] J¨org, T., Krzakala, F., Semerjian, G. and Zamponi, F.,
First-order transitions and the performance of quantum
algorithms in random optimization problems, Physical review letters, 04, 207206 (2010).
[11] Choi, V., Minor-embedding in adiabatic quantum computation: I. The parameter setting problem, Quantum
Information Processing, 7, 5 (2008).
[12] Choi, V., Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design, Quantum Information Processing, 10, 3 (2011).
[13] Boothby T., King A.D., and Roy A., Fast clique minor
generation in Chimera qubit connectivity graphs, Quantum Information Processing, 15, 1 (2016).
[14] Cai J., Macready W.G. and Roy A., A
practical heuristic for finding graph minors,
http://arxiv.org/abs/1406.2741 (2014).
[15] Lechner W., Hauke P., and Zoller P., A quantum annealing architecture with all-to-all connectivity from local
interactions, Sci. Adv. 1, e1500838 (2015).
[16] N. Chancellor, S. Zohren, P. A. Warburton, Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture, arXiv:1603.09521.
[17] M. Leib, P. Zoller and W. Lechner, A Transmon Quantum Annealer: Decomposing Many-Body Ising Constraints Into Pair Interactions, arXiv:1604.02359.
[18] N. Chancellor, S. Zohren, P. A. Warburton, S. C. Benjamin, S. Roberts, A Direct Mapping of Max k-SAT
and High Order Parity Checks to a Chimera Graph,
arXiv:1604.00651.
[19] Albash T., Vinci W., and Lidar D. A., Simulated
Quantum Annealing with Two All-to-All Connectivity
Schemes, http://arxiv.org/abs/1603.03755 (2016).
[20] Cheeseman P., Kanefsky B., Taylor W.M., Where the
Really Hard Problems Are, IJCAI, 91, (1991).
[21] Bravyi, S. B. and Kitaev, A. Y., Quantum codes on
a lattice with boundary, http://arxiv.org/abs//9811052 (1998).
[22] Pastawski F. and Preskill J., Error correction
for a proposed quantum annealing architecture,
http://arxiv.org/abs/1511.00004 (2015).
[23] Bian, Z., Chudak F., Israel, R., Lackey, B., Macready,
W.G. and Roy, A., Discrete optimization using quantum
annealing on sparse Ising models, Frontiers in Physics, 2,
56 (2014).
[24] For details of the ARC service, please see
http://dx.doi.org/10.5281/zenodo.22558.

17(v.2)

[1] F Barahona, “On the computational complexity of Ising spin
glass models,” J. Phys. A: Math. Gen 15, 3241 (1982).
[2] A. Lucas, “Ising formulations of many NP problems,” Front.
Phys. 2, 5 (2014).
16
[3] Tadashi Kadowaki and Hidetoshi Nishimori, “Quantum annealing in the transverse Ising model,” Phys. Rev. E 58, 5355
(1998).
[4] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan,
Andrew Lundgren, and Daniel Preda, “A Quantum Adiabatic
Evolution Algorithm Applied to Random Instances of an NPComplete Problem,” Science 292, 472–475 (2001).
[5] Giuseppe E. Santoro, Roman Martonˇak, Erio Tosatti, and ´
Roberto Car, “Theory of quantum annealing of an Ising spin
glass,” Science 295, 2427–2430 (2002).
[6] W. M. Kaminsky and S. Lloyd, “Scalable Architecture for Adiabatic Quantum Computing of NP-Hard Problems,” in Quantum
Computing and Quantum Bits in Mesoscopic Systems, edited by
A.A.J. Leggett, B. Ruggiero, and P. Silvestrini (Kluwer Academic/Plenum Publ., 2004) arXiv:quant-ph/0211152.
[7] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting,
F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson,
P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi,
E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich,
M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin,
J. Wang, B. Wilson, and G. Rose, “Quantum annealing with
manufactured spins,” Nature 473, 194–198 (2011).
[8] Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo,
Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A.
Lidar, and Matthias Troyer, “Defining and detecting quantum
speedup,” Science 345, 420–424 (2014).
[9] David Sherrington and Scott Kirkpatrick, “Solvable model of a
spin-glass,” Physical Review Letters 35, 1792–1796 (1975).
[10] Scott Kirkpatrick and David Sherrington, “Infinite-ranged models of spin-glasses,” Physical Review B 17, 4384–4403 (1978).
[11] P. Ray, B. K. Chakrabarti, and Arunava Chakrabarti,
“Sherrington-kirkpatrick model in a transverse field: Absence
of replica symmetry breaking due to quantum fluctuations,”
Phys. Rev. B 39, 11828–11832 (1989).
[12] Vicky Choi, “Minor-embedding in adiabatic quantum computation: I. The parameter setting problem,” Quant. Inf. Proc. 7,
193–209 (2008).
[13] Vicky Choi, “Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design,” Quant. Inf. Proc. 10,
343–353 (2011).
[14] Christine Klymko, Blair D. Sullivan, and Travis S. Humble,
“Adiabatic quantum programming: minor embedding with hard
faults,” Quant. Inf. Proc. 13, 709–729 (2014).
[15] Jun Cai, William G. Macready, and Aidan Roy, “A practical
heuristic for finding graph minors,” arXiv:1406.2741 (2014).
[16] Walter Vinci, Tameem Albash, Gerardo Paz-Silva, Itay Hen,
and Daniel A. Lidar, “Quantum annealing correction with minor embedding,” Phys. Rev. A 92, 042310– (2015).
[17] Wolfgang Lechner, Philipp Hauke, and Peter Zoller, “A quantum annealing architecture with all-to-all connectivity from
local interactions,” Science Advances 1 (2015), 10.1126/sciadv.1500838.
[18] Tomas Boothby, Andrew D. King, and Aidan Roy, “Fast
clique minor generation in chimera qubit connectivity graphs,”
arXiv:1507.04774 (2015).
[19] P. I Bunyk, E. M. Hoskinson, M. W. Johnson, E. Tolkacheva,
F. Altomare, AJ. Berkley, R. Harris, J. P. Hilton, T. Lanting,
AJ. Przybysz, and J. Whittaker, “Architectural considerations
in the design of a superconducting quantum annealing processor,” IEEE Transactions on Applied Superconductivity 24, 1–10
(Aug. 2014).
[20] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John
Preskill, “Topological quantum memory,” Journal of Mathematical Physics 43, 4452–4505 (2002).
[21] Fernando Pastawski and John Preskill, “Error correction for encoded quantum annealing,” Phys. Rev. A 93, 052325 (2016).
[22] T. Kato, “On the adiabatic theorem of quantum mechanics,” J.
Phys. Soc. Jap. 5, 435 (1950).
[23] Sabine Jansen, Mary-Beth Ruskai, and Ruedi Seiler, “Bounds
for the adiabatic approximation with applications to quantum
computation,” J. Math. Phys. 48, – (2007).
[24] Daniel A. Lidar, Ali T. Rezakhani, and Alioscia Hamma,
“Adiabatic approximation with exponential accuracy for manybody systems and quantum computation,” J. Math. Phys. 50, –
(2009).
[25] Andrew M. Childs, Edward Farhi, and John Preskill, “Robustness of adiabatic quantum computation,” Phys. Rev. A 65,
012322 (2001).
[26] M. H. S. Amin, Dmitri V. Averin, and James A. Nesteroff,
“Decoherence in adiabatic quantum computation,” Phys. Rev.
A 79, 022107 (2009).
[27] Tameem Albash and Daniel A. Lidar, “Decoherence in adiabatic quantum computation,” Phys. Rev. A 91, 062320– (2015).
[28] Kevin C. Young, Mohan Sarovar, and Robin Blume-Kohout,
“Error suppression and error correction in adiabatic quantum
computation: Techniques and challenges,” Phys. Rev. X 3,
041013– (2013).
[29] Sergio Boixo, Troels F. Ronnow, Sergei V. Isakov, Zhihui
Wang, David Wecker, Daniel A. Lidar, John M. Martinis, and
Matthias Troyer, “Evidence for quantum annealing with more
than one hundred qubits,” Nat. Phys. 10, 218–224 (2014).
[30] Kristen L Pudenz, Tameem Albash, and Daniel A Lidar,
“Error-corrected quantum annealing with hundreds of qubits,”
Nat. Commun. 5, 3243 (2014).
[31] Kristen L. Pudenz, Tameem Albash, and Daniel A. Lidar,
“Quantum annealing correction for random Ising problems,”
Phys. Rev. A 91, 042302 (2015).
[32] A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and
A. Aspuru-Guzik, “Finding low-energy conformations of lattice
protein models by quantum annealing,” Sci. Rep. 2, 571 (2012).
[33] Zhengbing Bian, Fabian Chudak, William G. Macready, Lane
Clark, and Frank Gaitan, “Experimental determination of ramsey numbers,” Physical Review Letters 111, 130505– (2013).
[34] A. Perdomo-Ortiz, J. Fluegemann, S. Narasimhan, R. Biswas,
and V.N. Smelyanskiy, “A quantum annealing approach for
fault detection and diagnosis of graph-based systems,” The European Physical Journal Special Topics 224, 131–148 (2015).
[35] Immanuel Trummer and Christoph Koch, “Multiple query optimization on the d-wave 2x adiabatic quantum computer,”
arXiv:1510.06437 (2015).
[36] Daryl P Nazareth and Jason D Spaans, “First application of
quantum annealing to imrt beamlet intensity optimization,”
Physics in Medicine and Biology 60, 4137 (2015).
[37] Gili Rosenberg, Poya Haghnegahdar, Phil Goddard, Peter Carr,
Kesheng Wu, and Marcos Lopez de Prado, “Solving the op- ´
timal trading trajectory problem using a quantum annealer,”
arXiv:1508.06182 (2015).
[38] Walter Vinci, Klas Markstrom, Sergio Boixo, Aidan Roy, Fed- ¨
erico M Spedalieri, Paul A Warburton, and Simone Severini,
“Hearing the shape of the ising model with a programmable
superconducting-flux annealer,” Scientific reports 4 (2014).
[39] Steven H. Adachi and Maxwell P. Henderson, “Application
of quantum annealing to training of deep neural networks,”
arXiv:1510.06356 (2015).
[40] Roman Martonˇak, Giuseppe E. Santoro, and Erio Tosatti, ´
“Quantum annealing by the path-integral Monte Carlo method:
The two-dimensional random Ising model,” Phys. Rev. B 66,
094203 (2002).
17
[41] Bettina Heim, Troels F. Rønnow, Sergei V. Isakov, and
Matthias Troyer, “Quantum versus classical annealing of ising
spin glasses,” Science 348, 215–217 (2015).
[42] Sergey Bravyi and Matthew Hastings, “On complexity of the
quantum ising model,” arXiv:1410.0703 (2014).
[43] Sergio Boixo, Tameem Albash, Federico M. Spedalieri,
Nicholas Chancellor, and Daniel A. Lidar, “Experimental signature of programmable quantum annealing,” Nat. Commun. 4,
2067 (2013).
[44] N. G. Dickson, M. W. Johnson, M. H. Amin, R. Harris,
F. Altomare, A. J. Berkley, P. Bunyk, J. Cai, E. M. Chapple,
P. Chavez, F. Cioata, T. Cirip, P. deBuen, M. Drew-Brook,
C. Enderud, S. Gildert, F. Hamze, J. P. Hilton, E. Hoskinson,
K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Lanting, T. Mahon, R. Neufeld, T. Oh, I. Perminov, C. Petroff, A. Przybysz,
C. Rich, P. Spear, A. Tcaciuc, M. C. Thom, E. Tolkacheva,
S. Uchaikin, J. Wang, A. B. Wilson, Z. Merali, and G. Rose,
“Thermally assisted quantum annealing of a 16-qubit problem,”
Nat. Commun. 4, 1903 (2013).
[45] T. Lanting, A. J. Przybysz, A. Yu. Smirnov, F. M. Spedalieri,
M. H. Amin, A. J. Berkley, R. Harris, F. Altomare, S. Boixo,
P. Bunyk, N. Dickson, C. Enderud, J. P. Hilton, E. Hoskinson, M. W. Johnson, E. Ladizinsky, N. Ladizinsky, R. Neufeld,
T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva,
S. Uchaikin, A. B. Wilson, and G. Rose, “Entanglement in a
quantum annealing processor,” Phys. Rev. X 4, 021041– (2014).
[46] Sergio Boixo, Vadim N. Smelyanskiy, Alireza Shabani,
Sergei V. Isakov, Mark Dykman, Vasil S. Denchev, Mohammad H. Amin, Anatoly Yu Smirnov, Masoud Mohseni, and
Hartmut Neven, “Computational multiqubit tunnelling in programmable quantum annealers,” Nat Commun 7 (2016).
[47] Tameem Albash, Walter Vinci, Anurag Mishra, Paul A. Warburton, and Daniel A. Lidar, “Consistency tests of classical
and quantum models for a quantum annealer,” Phys. Rev. A 91,
042314– (2015).
[48] C. J. Geyer, “Parallel tempering,” in Computing Science and
Statistics Proceedings of the 23rd Symposium on the Interface,
edited by E. M. Keramidas (American Statistical Association,
New York, 1991) p. 156.
[49] Koji Hukushima and Koji Nemoto, “Exchange monte carlo
method and application to spin glass simulations,” Journal of
the Physical Society of Japan 65, 1604–1608 (1996).
[50] Nicolas Sourlas, “Spin-glass models as error-correcting codes,”
Nature 339, 693–695 (1989).
[51] N. Sourlas, “Spin glasses, error-correcting codes and finitetemperature decoding,” EPL (Europhysics Letters) 25, 159
(1994).
[52] Giorgio Parisi, “Constraint optimization and statistical mechanics,” arXiv preprint cs/0312011 (2003).
[53] R. Islam, C. Senko, W. C. Campbell, S. Korenblit, J. Smith,
A. Lee, E. E. Edwards, C. C. J. Wang, J. K. Freericks, and
C. Monroe, “Emergence and frustration of magnetism with
variable-range interactions in a quantum simulator,” Science
340, 583–587 (2013).
[54] R. Barends, A. Shabani, L. Lamata, J. Kelly, A. Mezzacapo, U. Las Heras, R. Babbush, A. G. Fowler, B. Campbell, Yu Chen, Z. Chen, B. Chiaro, A. Dunsworth, E. Jeffrey,
E. Lucero, A. Megrant, J. Y. Mutus, M. Neeley, C. Neill, P. J. J.
O’Malley, C. Quintana, P. Roushan, D. Sank, A. Vainsencher,
J. Wenner, T. C. White, E. Solano, H. Neven, and John M.
Martinis, “Digitized adiabatic quantum computing with a superconducting circuit,” arXiv:1511.03316 (2015).
[55] Kevin Eng, Thaddeus D. Ladd, Aaron Smith, Matthew G.
Borselli, Andrey A. Kiselev, Bryan H. Fong, Kevin S. Holabird, Thomas M. Hazard, Biqin Huang, Peter W. Deelman,
Ivan Milosavljevic, Adele E. Schmitz, Richard S. Ross, Mark F.
Gyure, and Andrew T. Hunter, “Isotopically enhanced triplequantum-dot qubit,” Science Advances 1 (2015).
[56] L. Casparis, T. W. Larsen, M. S. Olsen, F. Kuemmeth,
P. Krogstrup, J. Nygard, K. D. Petersson, and C. M. ˚
Marcus, “Gatemon benchmarking and two-qubit operation,”
arXiv:1512.09195v1 (2015).
[57] Immanuel Bloch, “Quantum coherence and entanglement with
ultracold atoms in optical lattices,” Nature 453, 1016–1022
(2008).
[58] Davide Venturelli, Salvatore Mandra, Sergey Knysh, Bryan `
O’Gorman, Rupak Biswas, and Vadim Smelyanskiy, “Quantum optimization of fully connected spin glasses,” Phys. Rev. X
5, 031040– (2015).
[59] Davide Venturelli, Dominic J. J. Marchand, and Galo Rojo,
“Quantum annealing implementation of job-shop scheduling,”
arXiv:1506.08479 (2015).
[60] Kenneth M. Zick, Omar Shehab, and Matthew French, “Experimental quantum annealing: case study involving the graph isomorphism problem,” Scientific Reports 5, 11168 EP – (2015).
[61] Travis S Humble, Alex J McCaskey, Ryan S Bennink, Jay Jay
Billings, EF D Azevedo, Blair D Sullivan, Christine F Klymko,
and Hadayat Seddiqi, “An integrated programming and development environment for adiabatic quantum optimization,”
Computational Science & Discovery 7, 015006 (2014).
[62] Andrew D. King and Catherine C. McGeoch, “Algorithm engineering for a quantum annealing platform,” arXiv:1410.2628
(2014).
[63] Anurag Mishra, Tameem Albash, and Daniel A. Lidar, “Performance of two different quantum annealing correction codes,”
Quant. Inf. Proc. 15, 609–636 (2015).
[64] Walter Vinci, Tameem Albash, and Daniel A. Lidar, “Nested
quantum annealing correction,” arXiv:1511.07084 (2015).
[65] Helmut G Katzgraber, Simon Trebst, David A Huse, and
Matthias Troyer, “Feedback-optimized parallel tempering
monte carlo,” J. Stat. Mech. 2006, P03018 (2006).
[66] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization
by simulated annealing,” Science 220, 671–680 (1983).
[67] Pal Ruj ´ an, “Finite temperature error-correcting codes,” ´ Phys.
Rev. Lett. 70, 2968–2971 (1993).
[68] Hidetoshi Nishimori, “Optimum decoding temperature for
error-correcting codes,” Journal of the Physical Society of
Japan 62, 2973–2975 (1993).
[69] C.H. Papadimitriou, Computational Complexity (Addison Wesley Longman, Reading, Massachusetts, 1995).
[70] Leslie G. Valiant, “The complexity of enumeration and reliability problems,” SIAM Journal on Computing 8, 410–421 (1979).
[71] Vilhelm Dahllof, Peter Jonsson, and Magnus Wahlstr ¨ om, ¨
“Counting models for 2sat and 3sat formulae,” Theoretical
Computer Science 332, 265 – 291 (2005).
[72] John Preskill, “Quantum computing and the entanglement frontier,” arXiv:1203.5813 (2012).
[73] Victor Martin-Mayor and Itay Hen, “Unraveling quantum annealers using classical hardness,” Scientific Reports 5, 15324
EP – (2015).
[74] Zheng Zhu, Andrew J. Ochoa, Stefan Schnabel, Firas Hamze,
and Helmut G. Katzgraber, “Best-case performance of quantum
annealers on native spin-glass benchmarks: How chaos can affect success probabilities,” Phys. Rev. A 93, 012317 (2016).
[75] Siddharth Muthukrishnan, Tameem Albash, and Daniel A.
Lidar, “Tunneling and speedup in quantum optimization for
permutation-symmetric problems,” arXiv:1511.03910 (2015).
[76] T. Albash, T. F. Rønnow, M. Troyer, and D. A. Lidar, “Reexamining classical and quantum models for the d-wave one
processor,” Eur. Phys. J. Spec. Top. 224, 111–129 (2015)

26

[1] Amir Ben-Dor, Ron Shamir, and Zohar Yakhini. Clustering gene expression patterns. Journal of computational biology, 6(3-4):281–297, 1999.
[2] RanjitaDasandSriparnaSaha.Geneexpressiondataclassificationusingautomaticdifferential evolution based algorithm. In Evolutionary Computation (CEC), 2016 IEEE Congress on, pages 3124–3130. IEEE, 2016.
[3] Marian B Gorzałczany, Filip Rudzínski, and Jakub Piekoszewski. Gene expression data clus- tering using tree-like soms with evolving splitting-merging structures. In Neural Networks
15

(IJCNN), 2016 International Joint Conference on, pages 3666–3673. IEEE, 2016.
[4] Laetitia Marisa, Aurélien de Reyniès, Alex Duval, Janick Selves, Marie Pierre Gaub, Laure Vescovo, Marie-Christine Etienne-Grimaldi, Renaud Schiappa, Dominique Guenot, Mira Ayadi, et al. Gene expression classification of colon cancer into molecular subtypes: char-
acterization, validation, and prognostic value. PLoS Med, 10(5):e1001453, 2013.
[5] Pengtao Xie and Eric P. Xing. Integrating document clustering and topic modeling. CoRR,
abs/1309.6874, 2013.
[6] Rakesh Chandra Balabantaray, Chandrali Sarma, and Monica Jha. Document clustering using
k-means and k-medoids. CoRR, abs/1502.07938, 2015.
[7] Susan Mudambi. Branding importance in business-to-business markets: Three buyer clusters.
Industrial marketing management, 31(6):525–533, 2002.
[8] Arun Sharma and Douglas M Lambert. Segmentation of markets based on customer service.
International Journal of Physical Distribution & Logistics Management, 2013.
[9] Kit Yan Chan, CK Kwong, and Bao Qing Hu. Market segmentation and ideal point identi- fication for new product design using fuzzy data compression and fuzzy clustering methods.
Applied Soft Computing, 12(4):1371–1378, 2012.
[10] Jerome Friedman, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning,
volume 1. Springer series in statistics New York, 2001.
[11] John A Hartigan and Manchek A Wong. Algorithm as 136: A k-means clustering algorithm.
Journal of the Royal Statistical Society. Series C (Applied Statistics), 28(1):100–108, 1979.
[12] Stephen C Johnson. Hierarchical clustering schemes. Psychometrika, 32(3):241–254, 1967.
[13] Anil K Jain. Data clustering: 50 years beyond k-means. Pattern recognition letters, 31(8):651–
666, 2010.
[14] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory
of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.
[15] Christos H Papadimitriou. The euclidean travelling salesman problem is np-complete. Theo-
retical computer science, 4(3):237–244, 1977.
[16] Khaled S Al-Sultana and M Maroof Khan. Computational experience on four algorithms for
the hard clustering problem. Pattern recognition letters, 17(3):295–308, 1996.
[17] Scott Kirkpatrick, C Daniel Gelatt, Mario P Vecchi, et al. Optimization by simulated anneal-
ing. science, 220(4598):671–680, 1983.
16
[18] Shokri Z Selim and K1 Alsultan. A simulated annealing algorithm for the clustering problem. Pattern recognition, 24(10):1003–1008, 1991.
[19] Debasis Mitra, Fabio Romeo, and Alberto Sangiovanni-Vincentelli. Convergence and finite- time behavior of simulated annealing. In Decision and Control, 1985 24th IEEE Conference on, volume 24, pages 761–767. IEEE, 1985.
[20] Harold Szu and Ralph Hartley. Fast simulated annealing. Physics letters A, 122(3-4):157–162, 1987.
[21] Lester Ingber. Very fast simulated re-annealing. Mathematical and computer modelling, 12(8):967–973, 1989.
[22] KLEIN Bouleimen and HOUSNI Lecocq. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research, 149(2):268–281, 2003.
[23] Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model. Physical Review E, 58(5):5355, 1998.
[24] Giuseppe E Santoro and Erio Tosatti. Optimization using quantum mechanics: quantum annealing through adiabatic evolution. Journal of Physics A: Mathematical and General, 39(36):R393, 2006.
[25] Vasil S Denchev, Sergio Boixo, Sergei V Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, and Hartmut Neven. What is the computational value of finite-range tunneling? Physical Review X, 6(3):031015, 2016.
[26] M. Born and V. Fock. Beweis des Adiabatensatzes. Zeitschrift fur Physik, 51:165–180, March 1928.
[27] T. Albash and D. A. Lidar. Adiabatic Quantum Computing. ArXiv e-prints, November 2016.
[28] J.Biamonte,P.Wittek,N.Pancotti,P.Rebentrost,N.Wiebe,andS.Lloyd.QuantumMachine
Learning. ArXiv e-prints, November 2016.
[29] J. Dulny, III and M. Kim. Developing Quantum Annealer Driven Data Discovery. ArXiv
e-prints, March 2016.
[30] Harmut Neven, Vasil S Denchev, Marshall Drew-Brook, Jiayong Zhang, William G Macready,
and Geordie Rose. Nips 2009 demonstration: Binary classification using hardware implemen-
tation of quantum annealing. Quantum, pages 1–17, 2009.
[31] Vasil S Denchev. Binary classification with adiabatic quantum optimization. PhD thesis,
17
Purdue University, 2013.
[32] Alessandro Farinelli. A quantum annealing approach to biclustering. In Theory and Practice
of Natural Computing: 5th International Conference, TPNC 2016, Sendai, Japan, December
12-13, 2016, Proceedings, volume 10071, page 175. Springer, 2016.
[33] Kenichi Kurihara, Shu Tanaka, and Seiji Miyashita. Quantum annealing for clustering. In
Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages
321–328. AUAI Press, 2009.
[34] Issei Sato, Shu Tanaka, Kenichi Kurihara, Seiji Miyashita, and Hiroshi Nakagawa. Quan-
tum annealing for dirichlet process mixture models with applications to network clustering.
Neurocomputing, 121:523–531, 2013.
[35] Ernst Ising. Beitrag zur theorie des ferromagnetismus. Zeitschrift für Physik, 31(1):253–258,
Feb 1925.
[36] ED Dahl. Programming with d-wave: Map coloring problem (2013), 2013.
[37] H. Ishikawa. Transformation of general binary mrf minimization to the first-order case. IEEE
Transactions on Pattern Analysis and Machine Intelligence, 33(6):1234–1249, June 2011.
[38] Michael Booth, Steven P. Reinhardt, and Aidan year="2009" Roy. Partitioning optimization
problems for hybrid classical/quantum execution.
[39] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel,
P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011.
[40] David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1027–1035. Society for Industrial and Applied Mathematics, 2007.
[41] Sergio M Savaresi and Daniel L Boley. On the performance of bisecting k-means and pddp. In Proceedings of the 2001 SIAM International Conference on Data Mining, pages 1–14. SIAM, 2001.
[42] Jun Cai, William G Macready, and Aidan Roy. A practical heuristic for finding graph minors. arXiv preprint arXiv:1406.2741, 2014.
[43] A. Guénoche, P. Hansen, and B. Jaumard. Efficient algorithms for divisive hierarchical clus- tering with the diameter criterion. Journal of Classification, 8(1):5–30, Jan 1991.

40

[1] A. Lucas, 10.3389/fphy.2014.00005.
in Physics 2
(2014),
Frontiers
[2] M. Troyer, B. Heim, E. Brown, and D. Wecker, in APS Meeting Abstracts (2015).
[3] F. Barahona, Journal of Physics A: Mathematical and General 15, 3241 (1982).
[4] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science 220, 671 (1983).
[5] N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, The Journal of Chemical Physics 21, 1087 (1953).
[6] D. Bertsimas and J. Tsitsiklis, Statistical Science 8, 10 (1993).
[7] P. Ray, B. K. Chakrabarti, and A. Chakrabarti, Physical Review
B 39, 11828 (1989).
[8] A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J. D.
Doll, Chemical Physics Letters 219, 343 (1994).
[9] T. Kadowaki and H. Nishimori, Physical Review E 58, 5355 (1998).
[10] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and
D. Preda, Science 292, 472 (2001).
[11] A. Das and B. K. Chakrabarti, Rev. Mod. Phys. 80, 1061 (2008).
[12] P. I. Bunyk, E. M. Hoskinson, M. W. Johnson, E. Tolkacheva,
F. Altomare, A. J. Berkley, R. Harris, J. P. Hilton, T. Lanting, A. J. Przybysz, and J. Whittaker, IEEE Transactions on Applied Superconductivity 24, 1 (2014).
[13] R. Harris, M. W. Johnson, T. Lanting, A. J. Berkley, J. Johans- son, P. Bunyk, E. Tolkacheva, E. Ladizinsky, N. Ladizinsky, T. Oh, F. Cioata, I. Perminov, P. Spear, C. Enderud, C. Rich, S. Uchaikin, M. C. Thom, E. M. Chapple, J. Wang, B. Wilson, M. H. S. Amin, N. Dickson, K. Karimi, B. Macready, C. J. S. Truncik, and G. Rose, Phys. Rev. B 82, 024511 (2010).
[14] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, a. J. Berkley, J. Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose, Nature 473, 194 (2011).
[15] M. Suzuki, Progress of Theoretical Physics 56, 1454 (1976).
[16] G. Mazzola, V. N. Smelyanskiy, and M. Troyer, arXiv (2017),
arXiv:1609.04673.
[17] S.V.Isakov,G.Mazzola,V.N.Smelyanskiy,Z.Jiang,S.Boixo,
H. Neven, and M. Troyer, Phys. Rev. Lett. 117, 180402 (2016).
[18] Z. Jiang, V. N. Smelyanskiy, S. V. Isakov, S. Boixo, G. Mazzola, M. Troyer, and H. Neven, Phys. Rev. A 95, 012322 (2017).
[19] V. S. Denchev, S. Boixo, S. V. Isakov, N. Ding, R. Babbush, V. Smelyanskiy, J. Martinis, and H. Neven, Phys. Rev. X 6, 031015 (2016).
[20] T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Li- dar, and M. Troyer, Science 345, 420 (2014), http://www.sciencemag.org/content/345/6195/420.full.pdf.
[21] B. Heim, T. F. Rønnow, S. V. Isakov, and M. Troyer, Science 348, 215 (2015), http://www.sciencemag.org/content/348/6231/215.full.pdf.
[22] H. G. Katzgraber, F. Hamze, and R. S. Andrist, Phys. Rev. X 4, 021008 (2014).
[23] F. R. Huang, M.D. and A. Sangiovanni-Vincentelli, in Proc. IEEE Int. Conference on Computer-Aided Design (Santa Clara, 1986) pp. 381–384.
[24] P. J. van Laarhoven and E. H. Aarts, Simulated Annealing: The- ory and Applications (Springer Netherlands, 1987).
[25] T. H. Fischer, W. P. Petersen, and H. P. L thi, 16, 923 (1995). [26] J. Bricmont and A. Kupiainen, Communications in Mathemati-
cal Physics 116, 539 (1988).
[27] D. S. Steiger, T. F. Rønnow, and M. Troyer, Phys. Rev. Lett.
115, 230501 (2015).
[28] T. Zanca and G. E. Santoro, Phys. Rev. B 93, 224431 (2016). [29] COPhy and M. Ju ̈nger, “Spin Glass Server,” http://www.informatik.uni- koeln.de/spinglass/ (ac- cessed 2016).

59

[1] S. V. Isakov, G. Mazzola, V. N. Smelyanskiy, Z. Jiang, S. Boixo, H. Neven, and M. Troyer, Phys. Rev. Lett. 117, 180402 (2016).
[2] Z. Jiang, V. N. Smelyanskiy, S. V. Isakov, S. Boixo, G. Mazzola, M. Troyer, and H. Neven, Phys. Rev. A95, 012322 (2017).
[3] V. S. Denchev, S. Boixo, S. V. Isakov, N. Ding, R. Bab- bush, V. Smelyanskiy, J. Martinis, and H. Neven, Phys. Rev. X 6, 031015 (2016).
[4] A. Finnila, M. Gomez, C. Sebenik, C. Stenson, and J. Doll, Chemical Physics Letters 219, 343 (1994).
[5] T. Kadowaki and H. Nishimori, Phys. Rev. E 58, 5355 (1998).
[6] J. Brooke, D. Bitko, G. Aeppli, et al., Science 284, 779 (1999).
[7] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lund- gren, and D. Preda, Science 292, 472 (2001).
[8] S. Morita and H. Nishimori, Journal of Mathematical Physics 49, 125210 (2008).
[9] M. H. Amin, Phys. Rev. A 92, 052323 (2015).
[10] R. Martonˇ ́ak, G. E. Santoro, and E. Tosatti, Phys. Rev.
B 66, 094203 (2002).
[11] S. Bravyi, D. P. Divincenzo, R. I. Oliveira, and B. M.
Terhal, Quant. Inf. Comp. 8, 0361 (2008).
[12] G.E.Santoro,R.Martonˇa ́k,E.Tosatti,andR.Car,
Science 295, 2427 (2002).
[13] B. Heim, T. F. Rønnow, S. V. Isakov, and M. Troyer,
Science 348, 215 (2015).
[14] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting,
F. Hamze, N. Dickson, R. Harris, a. J. Berkley, J. Jo-
hansson, P. Bunyk, et al., Nature 473, 194 (2011).
[15] S. Boixo, T. F. Rønnow, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M. Martinis, and M. Troyer,
Nature Physics 10, 218 (2014).
[16] T. Albash, T. F. Rønnow, M. Troyer, and D. A. Lidar,
The European Physical Journal Special Topics 224, 111
(2015).
[17] T. Albash, I. Hen, F. M. Spedalieri, and D. A. Lidar,
Phys. Rev. A 92, 062328 (2015).
[18] N. G. Dickson, M. W. Johnson, M. H. Amin, R. Har-
ris, F. Altomare, a. J. Berkley, P. Bunyk, J. Cai, E. M. Chapple, P. Chavez, et al., Nature Communications 4, 1903 (2013).
[19] M. H. S. Amin and D. V. Averin, Phys. Rev. Lett. 100, 197001 (2008).
[20] H. Neven, V. Smelyanskiy, S. Boixo, A. Shabani, S. Isakov, M. Dykman, V. Denchev, M. Amin, A. Smirnov, and M. Mohseni, Bulletin of the American Physical Society 60 (2015).
[21] M. Jarret, S. P. Jordan, and B. Lackey, Phys. Rev. A 94, 042318 (2016).
[22] T. Lanting, A. Przybysz, A. Y. Smirnov, F. Spedalieri, M. Amin, A. Berkley, R. Harris, F. Altomare, S. Boixo, P. Bunyk, et al., Phys. Rev. X 4, 021041 (2014).
[23] R. D. Somma, D. Nagaj, and M. Kieferova ́, Phys. Rev. Lett. 109, 050501 (2012).
[24] M. B. Hastings and M. Freedman, QIC 13, 1038 (2013).
[25] M. H. Amin, A. Y. Smirnov, N. G. Dickson, and
M. Drew-Brook, Phys. Rev. A 86, 052314 (2012).
[26] T. Albash, G. Wagenbreth, and I. Hen, arXiv preprint
arXiv:1701.01499 (2017).
[27] A. W. Sandvik, Phys. Rev. E 68, 056701 (2003).
[28] P. H ̈anggi, P. Talkner, and M. Borkovec, Reviews of Mod-
ern Physics 62, 251 (1990).
[29] H. A. Kramers, Physica 7, 284 (1940).
[30] T. Lanting, R. Harris, J. Johansson, M. Amin,
A. Berkley, S. Gildert, M. Johnson, P. Bunyk, E. Tolka- cheva, E. Ladizinsky, et al., Phys. Rev. B 82, 060512 (2010).
[31] K. E. Atkinson, An introduction to numerical analysis (John Wiley & Sons, 2008).
[32] When T ≪ 2g, open boundary QMC does simulate equi- librium statistics of zero temperature quantum Boltz- mann distribution (ground state statistics). However, here we consider T 􏶱 2g, which is a more realistic and interesting regime for incoherent tunneling.

64

[1] A. Messiah, Quantum Mechanics, Vol. II, Amsterdam: North Holland; New York: Wiley (1976).
[2] L.K. Grover, “A Fast Quantum Mechanical Algorithm for Database Search”, quant-ph/9605043;
Phys. Rev. Lett. 78, 325 (1997).
[3] E. Farhi, S. Gutmann, “An Analog Analogue of a Digital Quantum Computation”, quant-
ph/9612026; Phys. Rev. A 57, 2403 (1998).
[4] C.H. Bennett, E. Bernstein, G. Brassard and U.V. Vazirani, “Strengths and Weaknesses of
Quantum Computing”, quant-ph/9701001.
[5] S. Lloyd, “Universal Quantum Simulators”, Science 273, 1073 (1996).

82

[AAR+16] [AH15] [Ami15]
[ATA09]
M. H. Amin, E. Andriyash, J. Rolfe, B. Kulchytskyy, and R. Melko. Quantum Boltzmann machine. See https://arxiv.org/abs/1601.02036, January 2016.
S. Adachi and M. Henderson. Application of quantum annealing to training of deep neural networks. See https://arxiv.org/abs/1510.06356, October 2015.
M. H. S. Amin. Searching for quantum speedup in quasistatic quantum annealers. Phys. Rev. A, 92:052323, November 2015. See https://arxiv.org/abs/1503. 04216.
M. H. S. Amin, C. J. S. Truncik, and D. V. Averin. Role of single-qubit deco- herence time in adiabatic quantum computation. Physical Review A, pages 1–5, 2009. See http://arxiv.org/abs/0803.1196.
20
[Ben80] P. Benioff. The computer as a physical system: A microscopic quantum mechani- cal Hamiltonian model of computers as represented by Turing machines. Journal of statistical physics, 22(5), 1980.
[BGBO16] M. Benedetti, J. Realpe Gomez, R. Biswas, and A. Perdomo Ortiz. Quantum- assisted learning of graphical models with arbitrary pairwise connectivity. See https://arxiv.org/abs/1609.02542, September 2016.
[CPH05] M. A. Carreira-Perpinan and G. E. Hinton. On contrastive divergence learning. In Proc. of the 10th AIStats, pages 33–40, 2005. See http://www.cs.toronto. edu/~fritz/absps/cdmiguel.pdf.
[DBI+ 15] V. S. Denchev, S. Boixo, S. V. Isakov, N. Ding, R. Babbush, V. Smelyanskiy, J. Martinis, and H. Neven. What is the computational value of finite range tunneling? See http://arxiv.org/abs/1512.02206, December 2015.
[Deu85] D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London A, 400:97– 117, 1985. See http://people.eecs.berkeley.edu/~christos/classics/ Deutsch_quantum_theory.pdf.
[DGN14] O. Devolder, F. Glineur, and Y. Nesterov. First-order methods of smooth con- vex optimization with inexact oracle. Mathematical Programming, 146(1):37–75, 2014. See http://www.optimization-online.org/DB_FILE/2010/12/2865. pdf.
[Fey82] R. P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21(6/7), 1982. See https://people.eecs.berkeley.edu/ ~christos/classics/Feynman.pdf.
[Hin02] G. E. Hinton. Training products of experts by minimizing contrastive divergence. Neural computation, 14(8):1771–1800, 2002.
[KN98]T. Kadowaki and H. Nishimori. Quantum annealing in the transverse Ising model. Phys. Rev. E, 58(5), 1998. See http://www.stat.phys.titech.ac. jp/~nishimori/papers/98PRE5355.pdf.
[KYN+15] J. King, S. Yarkoni, M. M. Nevisi, J. P. Hilton, and C. C. McGeoch. Bench- marking a quantum annealing processor with the time-to-target metric. See http://arxiv.org/abs/1508.05087, August 2015.
[LM11] H. Larochelle and I. Murray. The neural autoregressive distribution estimator. In Proc. of the 14th AISTATS, pages 29–37, 2011. See http://jmlr.csail.mit. edu/proceedings/papers/v15/larochelle11a/larochelle11a.pdf.
[LPS+ 14] T. Lanting, A.J. Przybysz, A. Yu. Smirnov, F.M. Spedalieri, M.H. Amin, A.J. Berkley, R. Harris, F. Altomare, S. Boixo, P. Bunyk, N. Dickson, C. Enderud, J.P. Hilton, E. Hoskinson, M.W. Johnson, E. Ladizinsky, N. Ladizinsky, R. Neufeld,
T. Oh, I. Perminov, C. Rich, M.C. Thom, E. Tolkacheva, S. Uchaikin, A.B. Wilson, and G. Rose. Entanglement in a quantum annealing processor. Phys. Rev. X, 4:021041, 2014. See https://arxiv.org/abs/1401.3500.
[LS10] P. M. Long and R. Servedio. Restricted Boltzmann machines are hard to approx- imately evaluate or simulate. In Johannes Fu ̈rnkranz and Thorsten Joachims, editors, Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 703–710. Omnipress, 2010. See http://www.cs.columbia. edu/~rocco/Public/final-camera-ready-icml10.pdf.
[Nes83] Y. Nesterov. A method of solving a convex programming problem with conver- gence rate o(1/k2). Soviet Mathematics Doklady, 27(2):372–376, 1983.
[RYA16] J. Raymond, S. Yarkoni, and E. Andriyash. Global warming: Temperature esti- mation in annealers. Frontiers in ICT, 3:23, 2016.
[SH09] R. Salakhutdinov and G. Hinton. Deep Boltzmann machines. In Proceedings of the International Conference on Artificial Intelligence and Statistics, volume 5, pages 448–455, 2009. See http://www.cs.toronto.edu/~fritz/absps/dbm.pdf.
[SMDH13] I. Sutskever, J. Martens, G. E. Dahl, and G. E. Hinton. On the importance of initialization and momentum in deep learning. In Sanjoy Dasgupta and David Mcallester, editors, Proceedings of the 30th International Conference on Machine Learning (ICML-13), volume 28, pages 1139–1147. JMLR Workshop and Con- ference Proceedings, May 2013.
[Tie08] T. Tieleman. Training restricted Boltzmann machines using approximations to the likelihood gradient. In Proceedings of the 25th international conference on Machine learning, pages 1064–1071. ACM New York, NY, USA, 2008. See http: //www.cs.toronto.edu/~tijmen/pcd/pcd.pdf.
[You98] L. Younes. Stochastic gradient estimation strategies for Markov random fields. Proc. SPIE, 3459:315–325, 1998.

84

[1] R. S. Sutton and A. G. Barto, Reinforcement Learning : An Introduction (MIT Press, 1998).
[2] D. Bertsekas and J. Tsitsiklis, Neuro-dynamic Pro- gramming, Anthropological Field Studies (Athena Scien- tific, 1996), ISBN 9781886529106, URL https://books. google.ca/books?id=WxCCQgAACAAJ.
[3] V. Derhami, E. Khodadadian, M. Ghasemzadeh, and A. M. Z. Bidoki, Applied Soft Computing 13, 1686 (2013). [4] S. Syafiie, F. Tadeo, and E. Martinez, Engineering Appli-
cations of Artificial Intelligence 20, 767 (2007).
[5] I. Erev and A. E. Roth, American Economic Review pp.
848–881 (1998).
[6] H. Shteingart and Y. Loewenstein, Current Opinion in
Neurobiology 25, 93 (2014).
[7] T. Matsui, T. Goto, K. Izumi, and Y. Chen, in European
Workshop on Reinforcement Learning (Springer, 2011), pp. 321–332.
[8] Z. Sui, A. Gosavi, and L. Lin, Engineering Management Journal 22, 44 (2010).
[9] B. Sallans and G. E. Hinton, JMLR 5, 1063 (2004).
[10] J. Martens, A. Chattopadhya, T. Pitassi, and R. Zemel, in Advances in Neural Information Processing Systems
(2013), pp. 2877–2885.
[11] K. Hornik, M. Stinchcombe, and H. White, Neural Net-
and Raymond et al. [39] provide methods for estimating the effective inverse temperature β for other applications. However, in both studies, the samples obtained from the quantum annealer are matched to the Boltzmann distribu- tion of a classical Ising model. In fact, the transverse-field strength is a second virtual parameter that we consider. The optimal choice Γ “ 0.5 corresponds to 2{3 of the annealing time, in agreement with the work of [26], who also consider TFIM with 16 qubits.
The agreement of FERL using quantum annealer reads treated as classical Boltzmann samples, with that of FERL using SA and classical Boltzmann machines, suggests that, at least for this task, and this size of Boltzmann machine, the measurements provided by the D-Wave 2000Q can be considered good approximations of Boltzmann distribu- tion samples of classical Ising models.
VI. CONCLUSION
In this paper, we perform free energy-based reinforce- ment learning using existing quantum hardware, namely the D-Wave 2000Q. Our methods rely on Suzuki–Trotter decomposition and realization of the measured configu- rations by the quantum device as replicas of an effective classical Ising model of one dimension higher. Future research can employ these principles to solve larger-scale reinforcement learning tasks in the emerging field of quan- tum machine learning.
Acknowledgement. The authors would like to thank Marko Bucyk for editing this manuscript.
works 2, 359 (1989).
[12] N. Le Roux and Y. Bengio, Neural Computation 20, 1631
(2008).
[13] D. Crawford, A. Levit, N. Ghadermarzy, J. S. Oberoi,
and P. Ronagh, ArXiv e-prints (2016), 1612.05695.
[14] S. Yuksel (2016), course lecture notes, Queen’s Uni- versity (Kingston, ON Canada), Retrieved in May 2016, URL http://www.mast.queensu.ca/~math472/
Math472872LectureNotes.pdf.
[15] R. Bellman, Proceedings of the National Academy of
Sciences 42, 767 (1956).
[16] M. H. Amin, E. Andriyash, J. Rolfe, B. Kulchytskyy, and
R. Melko, arXiv:1601.02036 (2016).
[17] M. Born and V. Fock, Zeitschrift fur Physik 51, 165
(1928).
[18] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, eprint
arXiv:quant-ph/0001106 (2000), quant-ph/0001106.
[19] T. Kadowaki and H. Nishimori, Phys. Rev. E 58, 5355 (1998), URL https://link.aps.org/doi/10.1103/
PhysRevE.58.5355.
[20] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting,
F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Jo- hansson, P. Bunyk, et al., Nature 473, 194 (2011), URL http://dx.doi.org/10.1038/nature10012.
7

[21] M. S. Sarandy and D. A. Lidar, Phys. Rev. A 71, 012331 (2005), URL https://link.aps.org/doi/10. 1103/PhysRevA.71.012331.
[22] L. C. Venuti, T. Albash, D. A. Lidar, and P. Zanardi, Phys. Rev. A 93, 032118 (2016), URL http://link.aps. org/doi/10.1103/PhysRevA.93.032118.
[23] T. Albash, S. Boixo, D. A. Lidar, and P. Zanardi, New Journal of Physics 14, 123016 (2012), URL http: //stacks.iop.org/1367- 2630/14/i=12/a=123016.
[24] J. E. Avron, M. Fraas, G. M. Graf, and P. Grech, Communications in Mathematical Physics 314, 163
(2012), ISSN 1432-0916, URL http://dx.doi.org/10.
1007/s00220-012-1504-1.
[25] S. Bachmann, W. De Roeck, and M. Fraas, ArXiv e-prints
(2016), 1612.01505.
[26] M. H. Amin, Phys. Rev. A 92, 052323 (2015).
[27] M. Suzuki, Progress of Theoretical Physics 56, 1454
(1976).
[28] S. M. Anthony Brabazon, Michael O’Neill, Natural Com-
puting Algorithms (Springer-Verlag Berlin Heidelberg,
2015).
[29] R. Martoňák, G. E. Santoro, and E. Tosatti, Phys. Rev.
B 66, 094203 (2002).
[30] B. Heim, T. F. Rønnow, S. V. Isakov, and M. Troyer,
Science 348, 215 (2015).
[31] S. V. Isakov, G. Mazzola, V. N. Smelyanskiy, Z. Jiang,
S. Boixo, H. Neven, and M. Troyer, arXiv:1510.08057 (2015).
[32] T. Albash, T. F. Rønnow, M. Troyer, and D. A. Lidar, ArXiv e-prints (2014), 1409.3827.
[33] L. T. Brady and W. van Dam, Phys. Rev. A 93, 032304 (2016).
[34] S. W. Shin, G. Smith, J. A. Smolin, and U. Vazirani, ArXiv e-prints (2014), 1401.7087.
[35] S. Morita and H. Nishimori, Journal of Physics A: Math- ematical and General 39, 13903 (2006).
[36] R. S. Sutton, in In Proceedings of the Seventh Interna- tional Conference on Machine Learning (Morgan Kauf- mann, 1990), pp. 216–224.
[37] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Ve- ness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al., Nature 518, 529 (2015), URL http://dx.doi.org/10.1038/nature14236.
[38] M. Benedetti, J. Realpe-Gómez, R. Biswas, and A. Perdomo-Ortiz, Phys. Rev. A 94, 022308 (2016), URL https://link.aps.org/doi/10.1103/PhysRevA. 94.022308.
[39] J. Raymond, S. Yarkoni, and E. Andriyash, Frontiers in ICT 3, 23 (2016), ISSN 2297-198X, URL http://journal. frontiersin.org/article/10.3389/fict.2016.00023.

88

1 Mukherjee, S. and Chakrabarti, B.K. (2015) Multivariable optimization: Quantum annealing and computation. Eur. Phys. J. Special Topics 224, 17–24.
2 Johnson, M.W., Amin, M.H.S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A.J., Hohansson, 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, Nature 473, 194- 198. doi:10.1038/nature10012.
3 Venturelli, D., Mandrà, S., Knysh, S., O'Gorman, B., Biswas, R., and Smelyanskiy, V. (2014) Quantum Optimization of Fully-Connected Spin Glasses. http://arxiv.org/abs/1406.7553
4 Wiebe, N., Kapoor, A., and Svore, K.M. (2014) Quantum Deep Learning. http://arxiv.org/abs/1412.3489 5 Dumoulin, V., Goodfellow, I.J., Courville, A., and Bengio, Y. (2014) On the Challenges of Physical Implementations of RBMs. AAAI 2014: 1199-1205.
6 Denil, M. and de Freitas, N. (2011). Toward the implementation of a quantum RBM. NIPS*2011 Workshop on Deep Learning and Unsupervised Feature Learning.
7 Rose, G. (2014) First ever DBM trained using a quantum computer. https://dwave.wordpress.com/2014/01/06/first-ever-dbm-trained-using-a-quantum-computer/
8 Montavon, G., and Müller, K.-R. (2012) Deep Boltzmann Machines and the Centering Trick. In Montavon, G., Orr, G. B., and Müller, K.-R. (Eds.), Neural Networks: Tricks of the Trade, 2nd edn, Springer LNCS 7700.
9 Koller, D. and Friedman, N. (2009) Probabilistic Graphical Models: Principles and Techniques, MIT Press, Cambridge MA, pp. 391-429.
10 Hinton, G. E. (2002) Training Products of Experts by Minimizing Contrastive Divergence. Neural Computation, 14, pp 1771-1800.
11 Hinton, G. E., Osindero, S., and Teh, Y. (2006). A fast learning algorithm for deep belief nets. Neural Computation 18 (7): 1527–1554.
12 Tanaka, M. (2013) Deep Neural Network Toolbox, MATLAB File Exchange. http://www.mathworks.com/matlabcentral/fileexchange/42853-deep-neural-network
13 Sonoda, S. and Murata, N. (2014) Nonparametric Weight Initialization of Neural Networks via Integral Representation. arXiv:1312.6461v3 [cs.LG]
14 Shepanski, J. F. (1988) Fast learning in artificial neural systems: multilayer perceptron training using optimal estimation. ICNN1988, volume 1, pages 465–472, 1988.
15 Yam, J. Y. F. and Chow, T.W.S. (2000) A weight initialization method for improving training speed in feedforward neural network. Neurocomputing, 30(1-4):219–232, 2000.
16 Rumelhart, D.E., Hinton, G.E., and Williams, R.J. (1986) Learning representations by back-propagating errors. Nature, Vol. 323, 1986, pp. 533–536.
17 Boixo, S., Albash, T., Spedalieri, F.M., Chancellor, N., and Lidar, D.A. (2013) Experimental signature of programmable quantum annealing, Nature Communications 4, 2067. doi: 10.1038/ncomms3067.
18 LeCun, Y., Cortes, C., and Burges, C.J.C. (1998) The MNIST database of handwritten digits. http://yann.lecun.com/exdb/mnist/
19 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. Science 345, 420. doi:10.1126/science.1252319

89

[1] Harmut Neven, Vasil S Denchev, Marshall Drew-Brook, Jiayong Zhang, William G Macready, and Geordie Rose, “Binary classification using hardware implementation of quantum annealing,” in Demonstrations at NIPS-09, 24th Annual Conference on Neural Information Process- ing Systems (2009) pp. 1–17.
[2] Zhengbing Bian, Fabian Chudak, William G Macready, and Geordie Rose, The Ising model: teaching an old prob- lem new tricks, Tech. Rep. (D-Wave Systems, 2010).
[3] Misha Denil and Nando De Freitas, “Toward the imple- mentation of a quantum RBM,” NIPS Deep Learning and Unsupervised Feature Learning Workshop (2011).
[4] Nathan Wiebe, Daniel Braun, and Seth Lloyd, “Quan- tum algorithm for data fitting,” Physical review letters 109, 050505 (2012).
[5] Kristen L. Pudenz and Daniel A. Lidar, “Quantum adia- batic machine learning,” Quantum Information Process- ing 12, 2027–2070 (2013).
[6] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost, “Quantum algorithms for supervised and unsupervised machine learning,” arXiv:1307.0411 (2013).
􏰄 e−Ei
Z |i⟩⟨i|, (B1)
where Z = 􏶣i e−Ei is the normalization constant. Then, plug this expansion into the intractable expression and use Jensen’s inequality
ln⟨u|ρ|u⟩
ρ=
9
i
􏰄 e−Ei = ln⟨u| Z
|i⟩⟨i|u⟩ = ln 􏰄 |⟨i|u⟩|2 e−Ei
i
Z
≥ 􏰄 |⟨i|u⟩|2 ln e−Ei (B2)
i
i
Z
|i⟩⟨i|u⟩
􏰄 e−Ei = ⟨u| ln Z
i
= ⟨u| ln ρ|u⟩,
where |⟨i|u⟩|2 are probabilities and sum up to 1.
[7] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd, “Quantum support vector machine for big data classifi- cation,” Phys. Rev. Lett. 113, 130503 (2014).
[8] Guoming Wang, “Quantum algorithm for linear regres- sion,” Physical Review A 96, 012335 (2017).
[9] Z. Zhao, J. K. Fitzsimons, and J. F. Fitzsimons, “Quan- tum assisted Gaussian process regression,” ArXiv e- prints (2015), arXiv:1512.03929 [quant-ph].
[10] Seth Lloyd, Masoud Mohseni, and Patrick Reben- trost, “Quantum principal component analysis,” Nature Physics 10, 631–633 (2014).
[11] Maria Schuld, Ilya Sinayskiy, and Francesco Petruc- cione, “Prediction by linear regression on a quantum computer,” Physical Review A 94, 022342 (2016).
[12] Krysta M. Svore Nathan Wiebe, Ashish Kapoor, “Quan- tum deep learning,” arXiv:1412.3489 (2015).
[13] Scott Aaronson, “Read the fine print,” Nature Physics 11, 291–293 (2015), commentary.
[14] Marcello Benedetti, John Realpe-Go ́mez, Rupak Biswas, and Alejandro Perdomo-Ortiz, “Estimation of effective temperatures in quantum annealers for sampling appli- cations: A case study with possible applications in deep

learning,” Phys. Rev. A 94, 022308 (2016).
[15] Marcello Benedetti, John Realpe-Go ́mez, Rupak Biswas, and Alejandro Perdomo-Ortiz, “Quantum-assisted learn- ing of hardware-embedded probabilistic graphical mod-
els,” Phys. Rev. X 7, 041052 (2017).
[16] Steven H. Adachi and Maxwell P. Henderson, “Appli-
cation of quantum annealing to training of deep neural
networks,” arXiv:1510.06356 (2015).
[17] Nicholas Chancellor, Szilard Szoke, Walter Vinci, Gabriel
Aeppli, and Paul A Warburton, “Maximum-entropy in- ference with a programmable annealer,” Scientific reports 6 (2016).
[18] Thomas E. Potok, Catherine Schuman, Steven R. Young, Robert M. Patton, Federico Spedalieri, Jeremy Liu, Ke-Thia Yao, Garrett Rose, and Gangotree Chakma, “A study of complex deep learning networks on high performance, neuromorphic, and quantum computers,” arXiv:1703.05364 (2017).
[19] Mohammad H. Amin and Evgeny Andriyash and Jason Rolfe and Bohdan Kulchytskyy and Roger Melko, “Quan- tum Boltzmann Machine,” arXiv:1601.02036 (2016).
[20] Ma ́ria Kieferova ́ and Nathan Wiebe, “Tomography and generative training with quantum boltzmann machines,” Phys. Rev. A 96, 062327 (2017).
[21] Iordanis Kerenidis and Anupam Prakash, “Quantum rec- ommendation systems,” arXiv preprint arXiv:1603.08675 (2016).
[22] Peter Wittek and Christian Gogolin, “Quantum en- hanced inference in markov logic networks,” Scientific Reports 7 (2017).
[23] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione, “An introduction to quantum machine learning,” Con- temporary Physics 56, 172–185 (2015).
[24] Jonathan Romero, Jonathan P Olson, and Alan Aspuru- Guzik, “Quantum autoencoders for efficient compression of quantum data,” Quantum Sci. Technol. 2, 045001 (2017).
[25] Jeremy Adcock, Euan Allen, Matthew Day, Stefan Frick, Janna Hinchliff, Mack Johnson, Sam Morley-Short, Sam Pallister, Alasdair Price, and Stasja Stanisic, “Ad- vances in quantum machine learning,” arXiv preprint arXiv:1512.02900 (2015).
[26] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd, “Quan- tum machine learning,” arXiv preprint arXiv:1611.09347 (2016).
[27] Unai Alvarez-Rodriguez, Lucas Lamata, Pablo Escandell-Montero, Jos ́e D Mart ́ın-Guerrero, and Enrique Solano, “Quantum machine learning with- out measurements,” arXiv preprint arXiv:1612.05535 (2016).
[28] Lucas Lamata, “Basic protocols in quantum reinforce- ment learning with superconducting circuits,” Scientific Reports 7 (2017).
[29] Maria Schuld, Mark Fingerhuth, and Francesco Petruccione, “Quantum machine learning with small- scale devices: Implementing a distance-based classifier with a quantum interference circuit,” arXiv preprint arXiv:1703.10793 (2017).
[30] C. Ciliberto, M. Herbster, A. Davide Ialongo, M. Pontil, A. Rocchetto, S. Severini, and L. Wossnig, “Quantum machine learning: a classical perspective,” ArXiv e-prints (2017), arXiv:1707.08561 [quant-ph].
[31] Alejandro Perdomo-Ortiz, Marcello Benedetti, John Realpe-Go ́mez, and Rupak Biswas, “Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers,” arXiv:1708.09757 (2017).
[32] Marcello Benedetti, Delfina Garcia-Pintos, Yunseong Nam, and Alejandro Perdomo-Ortiz, “A generative mod- eling approach for benchmarking and training shallow quantum circuits,” arXiv:1801.07686 (2018).
[33] Edward Farhi and Hartmut Neven, “Classification with quantum neural networks on near term processors,” arXiv:1802.06002 (2018).
[34] Yoshua Bengio et al., “Learning deep architectures for ai,” Foundations and trend in Machine Learning 2, 1– 127 (2009).
[35] Geoffrey E Hinton, Simon Osindero, and Yee-Whye Teh, “A fast learning algorithm for deep belief nets,” Neural computation 18, 1527–1554 (2006).
[36] Seth Lloyd and Samuel L Braunstein, “Quantum compu- tation over continuous variables,” Physical Review Let- ters 82, 1784 (1999).
[37] Hoi-Kwan Lau, Raphael Pooser, George Siopsis, and Christian Weedbrook, “Quantum machine learning over infinite dimensions,” Physical Review Letters 118, 080501 (2017).
[38] S. Das, G. Siopsis, and C. Weedbrook, “Continuous- variable quantum Gaussian process regression and quan- tum singular value decomposition of non-sparse low rank matrices,” ArXiv e-prints (2017), arXiv:1707.00360 [quant-ph].
[39] Ian Goodfellow Yoshua Bengio and Aaron Courville, “Deep learning,” (2016), mIT Press.
[40] Geoffrey E. Hinton, Peter Dayan, Brendan J. Frey, and Radford M. Neal, “The wake-sleep algorithm for unsu- pervised neural networks,” Science 268, 1158 (1995).
[41] Peter Dayan, Geoffrey E Hinton, Radford M Neal, and Richard S Zemel, “The helmholtz machine,” Neural com- putation 7, 889–904 (1995).
[42] Jorg Bornschein, Samira Shabanian, Asja Fischer, and Yoshua Bengio, “Bidirectional helmholtz machines,” in International Conference on Machine Learning (2016) pp. 2511–2519.
[43] David H Ackley, Geoffrey E Hinton, and Terrence J Se- jnowski, “A learning algorithm for boltzmann machines,” Cognitive science 9, 147–169 (1985).
[44] Ruslan Salakhutdinov and Geoffrey Hinton, “Deep boltz- mann machines,” in Artificial Intelligence and Statistics (2009) pp. 448–455.
[45] Thomas E Potok, Catherine D Schuman, Steven R Young, Robert M Patton, Federico Spedalieri, Jeremy Liu, Ke-Thia Yao, Garrett Rose, and Gangotree Chakma, “A study of complex deep learning networks on high performance, neuromorphic, and quantum com- puters,” in Proceedings of the Workshop on Machine Learning in High Performance Computing Environments (IEEE Press, 2016) pp. 47–55.
[46] Jo ̈rg Bornschein and Yoshua Bengio, “Reweighted wake- sleep,” arXiv preprint arXiv:1406.2751 (2014).
[47] Ruslan Salakhutdinov and Hugo Larochelle, “Efficient learning of deep boltzmann machines,” in Proceedings of the Thirteenth International Conference on Artificial In- telligence and Statistics (2010) pp. 693–700.
[48] Wolfgang Lechner, Philipp Hauke, and Peter Zoller, “A quantum annealing architecture with all-to-all connectivity from local interactions,” Science advances 1, e1500838 (2015).
[49] Alejandro Perdomo-Ortiz, Alexander Feldman, Asier
Ozaeta, Sergei V. Isakov, Zheng Zhu, Bryan O’Gorman, Helmut G. Katzgraber, Alexander Diedrich, Hartmut Neven, Johan de Kleer, Brad Lackey, and Rupak Biswas, “On the readiness of quantum optimization machines for industrial applications,” arXiv:1708.09780 (2017).
[50] Laurent Younes, “On the convergence of markovian stochastic algorithms with rapidly decreasing ergodicity rates,” Stochastics: An International Journal of Proba- bility and Stochastic Processes 65, 177–228 (1999).
[51] “A sub-sampled version of the mnist dataset,” https://github.com/marybigday/stat665- 1/tree/master/data (Accessed: August 2017).
[52] Jun Cai, William G Macready, and Aidan Roy, “A prac- tical heuristic for finding graph minors,” arXiv:1406.2741 (2014).
[53] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio, “Generative adversarial nets,” in Ad- vances in neural information processing systems (2014) pp. 2672–2680.

91

[FGG+01]
[FGGS00] [FS99] [HR98] [KN01]
[KSJ00] [OT92]
[Pal04] [Sau72] [Vez06]
[Zha08]
EdwardFarhi,JeffreyGoldstone,SamGutmann,JoshuaLapan,AndrewLundgren,and Daniel Preda. A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science, 292:472, 2001.
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum com- putation by adiabatic evolution. 2000. preprint quant-ph/0001106v1.
Yoav Freund and Robert E. Schapire. A short introduction to boosting. Journal of Japanese Society for Artificial Intelligence, 14(5):771–780, 1999.
Christoph Helmberg and Franz Rendl. Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math. Program., 82(3):291–315, 1998.
Kengo Katayama and Hiroyuki Narihisa. Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem. European Jour- nal of Operational Research, 134(1):103–119, 2001.
Eric R. Kandel, James H. Schwartz, and Thomas M. Jessell. Principles of Neural Sci- ence. McGraw-Hill, 2000.
Peter Orlik and Hiroaki Terao. Arrangements of hyperplanes. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, Germany, 1992.
Gintaras Palubeckis. Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Ann. Oper. Res., 131:259–282, 2004.
Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, 13:145–147, 1972.
Alexander Vezhnevets. GML AdaBoost Matlab toolbox 0.3. MSU Graphics & Media Lab, Computer Vision Group, Department of Computer Science, Moscow State Univer- sity, 2006.
Tong Zhang. Forward-backward greedy algorithm for learning sparse representations. Rutgers Statistics Department Technical Report, 2008.

92

[AC09] [FGG+ 09]
[FGGS00]
[FHT98]
[Fre09] [FS95]
[LS08] [Mes99] [NDRM08]
[Pal04] [VC71]
[Wyn02] [YKS08]
[YKS09] [Zha04]
Mohammad H. S. Amin and Vicki Choi. First order quantum phase transition in adia- batic quantum computation, 2009. arXiv: quant-ph/0904.1387.
Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Harvey B. Meyer, and Peter Shor. Quantum adiabatic algorithms, small gaps, and different paths. 2009. arXiv: quant-ph/0909.4766v1.
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum com- putation by adiabatic evolution. 2000. arXiv: quant-ph/0001106v1.
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Additive logistic regression: a statistical view of boosting. Annals of Statistics, 28:2000, 1998.
Yoav Freund. A more robust boosting algorithm. 2009. arXiv: stat.ML/0905.2138v1.
Yoav Freund and Robert E. Shapire. A decision-theoretic generalization of online learning and an application to boosting. AT&T Bell Laboratories Technical Report, 1995.
Philip M. Long and Rocco A. Servedio. Random classification noise defeats all convex potential boosters. 25th International Conference on Machine Learning (ICML), 2008.
Albert Messiah. Quantum mechanics: Two volumes bound as one. Dover, Mineola, NY, 1999. Trans. of : Mcanique quantique, t.1. Paris, Dunod, 1959.
Hartmut Neven, Vasil S. Denchev, Geordie Rose, and William G. MacReady. Train- ing a binary classifier with the quantum adiabatic algorithm. 2008. arXiv: quant- ph/0811.0416v1.
Gintaras Palubeckis. Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Ann. Oper. Res., 131:259–282, 2004.
Vladimir Vapnik and Alexey Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264–280, 1971.
Abraham J. Wyner. Boosting and the exponential loss. Proceedings of the Ninth Annual Conference on AI and Statistics, 2002.
A. P. Young, S. Knysh, and V. N. Smelyanskiy. Size dependence of the minimum ex- citation gap in the quantum adiabatic algorithm. Physical Review Letters, 101:170503, 2008.
A. P. Young, S. Knysh, and V. N. Smelyanskiy. First order phase transition in the quantum adiabatic algorithm. 2009. arXiv:quant-ph/0910.1378v1.
Tong Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32:56–85, 2004.

95

[1] Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, R Harris, Andrew J Berkley, Jan Johansson, Paul Bunyk, et al. Quantum annealing with manufactured spins. Nature, 473(7346):194–198, 2011.
[2] Troels F Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V Isakov, David Wecker, John M Martinis, Daniel A Lidar, and Matthias Troyer. Defining and detecting quantum speedup. Science, 345(6195):420–424, 2014.
[3] Elizabeth Gibney. D-wave upgrade: How scientists are using the world’s most controversial quantum computer. Nature, 541(7638):447–448, 2017.
[4] Rocco A Servedio and Steven J Gortler. Equivalences and separations between quantum and classical learnability. SIAM Journal on Computing, 33(5):1067–1092, 2004.
[5] Esma A ̈ımeur, Gilles Brassard, and S ́ebastien Gambs. Machine learning in a quantum world. In Conference of the Canadian Society for Computational Studies of Intelligence, pages 431–442. Springer, 2006.
[6] Kristen L Pudenz and Daniel A Lidar. Quantum adiabatic machine learn- ing. Quantum information processing, 12(5):2027–2070, 2013.
[7] Andrew Danowitz, Kyle Kelley, James Mao, John P Stevenson, and Mark Horowitz. Cpu db: recording microprocessor history. Communications of the ACM, 55(4):55–63, 2012.
11

[8] David Geer. Chip makers turn to multicore processors. Computer, 38(5):11– 13, 2005.
[9] John D Owens, Mike Houston, David Luebke, Simon Green, John E Stone, and James C Phillips. GPU computing. Proceedings of the IEEE, 96(5):879–899, 2008.
[10] Don Monroe. Neuromorphic computing gets ready for the (really) big time. Communications of the ACM, 57(6):13–15, 2014.
[11] Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model. Physical Review E, 58(5):5355, 1998.
[12] Catherine C McGeoch and Cong Wang. Experimental evaluation of an adiabiatic quantum system for combinatorial optimization. In Proceedings of the ACM International Conference on Computing Frontiers, page 23. ACM, 2013.
[13] Sergei V Isakov, Ilia N Zintchenko, Troels F Rønnow, and Matthias Troyer. Optimised simulated annealing for ising spin glasses. Computer Physics Communications, 192:265–271, 2015.
[14] James King, Sheir Yarkoni, Jack Raymond, Isil Ozfidan, Andrew D King, Mayssam Mohammadi Nevisi, Jeremy P Hilton, and Catherine C McGeoch. Quantum annealing amid local ruggedness and global frustration. arXiv preprint arXiv:1701.04579, 2017.
[15] Salvatore Mandr`a, Helmut G Katzgraber, and Creighton Thomas. The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum an- nealers (again). arXiv preprint arXiv:1703.00622, 2017.
[16] Daniel D Lee and H Sebastian Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755):788–791, 1999.
[17] Chih-Jen Lin. Projected gradient methods for nonnegative matrix factor- ization. Neural computation, 19(10):2756–2779, 2007.
[18] Daniel O’Malley and Velimir V Vesselinov. Toq. jl: A high-level program- ming language for d-wave machines based on julia. In High Performance Extreme Computing Conference (HPEC), 2016 IEEE, pages 1–7. IEEE, 2016.
[19] D-Wave Systems. qbsolv. https://github.com/dwavesystems/qbsolv, 2017.
[20] Fred Glover. Tabu searchpart i. ORSA Journal on computing, 1(3):190– 206, 1989.
[21] Fred Glover. Tabu searchpart ii. ORSA Journal on computing, 2(1):4–32, 1990.
12

[22] Iain Dunning, Joey Huchette, and Miles Lubin. JuMP: A modeling lan- guage for mathematical optimization. arXiv:1508.01982 [math.OC], 2015.
[23] Gurobi Optimization. Gurobi optimizer version 7.0.2. http://www.gurobi.com, 2017.
[24] James King, Sheir Yarkoni, Mayssam M Nevisi, Jeremy P Hilton, and Catherine C McGeoch. Benchmarking a quantum annealing processor with the time-to-target metric. arXiv preprint arXiv:1508.05087, 2015.
[25] Catherine C McGeoch. Adiabatic quantum computation and quantum an- nealing: Theory and practice. Synthesis Lectures on Quantum Computing, 5(2):1–93, 2014.
[26] Vicky Choi. Minor-embedding in adiabatic quantum computation: I. the parameter setting problem. Quantum Information Processing, 7(5):193– 209, 2008.
[27] Vicky Choi. Minor-embedding in adiabatic quantum computation: II. minor-universal graph design. Quantum Information Processing, 10(3):343– 353, 2011.
[28] Vasil S Denchev, Sergio Boixo, Sergei V Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, and Hartmut Neven. What is the com- putational value of finite-range tunneling? Physical Review X, 6(3):031015, 2016.
[29] Robert E Bixby. A brief history of linear and mixed-integer programming computation. Documenta Mathematica, pages 107–121, 2012.
[30] Jeremy Hilton. Systems progress. Presented at the D-Wave “Qubits” User Group Meeting, 2016.
[31] Andrey Y Lokhov, Marc Vuffray, Sidhant Misra, and Michael Chertkov. Optimal structure and parameter learning of ising models. arXiv preprint arXiv:1612.05024, 2016.

96

[1] M.I. Jordan and T.M. Mitchell, Machine learning: Trends, perspectives, and prospects, Science 349, 255 (2015).
[2] C.M. Bishop, Pattern Recognition and Machine Learn- ing, Springer 2006.
[3] S. Lloyd, M. Mohseni, P. Rebentrost, Quantum algo- rithms for supervised and unsupervised machine learn- ing, eprint: arXiv:1307.0411.
[4] P. Rebentrost, M. Mohseni, S. Lloyd, Quantum support vector machine for big data classification, Phys. Rev. Lett. 113, 130503 (2014).
[5] N. Wiebe, A. Kapoor, and K.M. Svore, Quantum Deep Learning, eprint: arXiv:1412.3489.
[6] H. Neven, G. Rose, W.G. Macready, Image recog- nition with an adiabatic quantum computer I. Map- ping to quadratic unconstrained binary optimization, arXiv:0804.4457.
[7] H. Neven, V.S. Denchev, G. Rose, W.G. Macready, Training a Binary Classifier with the Quantum Adiabatic Algorithm, arXiv:0811.0416.
[8] H. Neven, V.S. Denchev, G. Rose, W.G. Macready, Training a Large Scale Classifier with the Quantum Adi- abatic Algorithm, arXiv:0912.0779.
[9] K.L. Pudenz, D.A. Lidar, Quantum adiabatic machine learning, arXiv:1109.0325.
[10] M. Denil and N. de Freitas, Toward the implementa- tion of a quantum RBM, NIPS*2011 Workshop on Deep Learning and Unsupervised Feature Learning.
[11] V.S. Denchev, N. Ding, S.V.N. Vishwanathan, H. Neven, Robust Classification with Adiabatic Quantum Opti- mization, arXiv:1205.1148.
[12] V. Dumoulin, I.J. Goodfellow, A. Courville, Y. and Ben- gio, On the Challenges of Physical Implementations of RBMs, AAAI 2014: 1199-1205.
[13] R. Babbush, V. Denchev, N. Ding, S. Isakov, H. Neven, Construction of non-convex polynomial loss functions for training a binary classifier with quantum annealing, arXiv:1406.4203.
[14] M.W. Johnson, M.H.S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A.J. Berkley, J. Johans- son, P. Bunyk, E.M. Chapple, C. Enderud, J.P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Permi- nov, C. Rich, M.C. Thom, E. Tolkacheva, C.J.S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose, Quantum Annealing with Manufactured Spins, Nature 473, 194 (2011).
[15] S.H. Adachi, M.P. Henderson, Application of Quantum Annealing to Training of Deep Neural Networks, eprint: arXiv:1510.06356.
[16] M. Benedetti, J. Realpe-Gmez, R. Biswas, A. Perdomo- Ortiz, Estimation of effective temperatures in a quan- tum annealer and its impact in sampling applica- tions: A case study towards deep learning applications, arXiv:1510.07611.
[17] G. E. Hinton, T. J. Sejnowski, Optimal perceptual infer- ence, CVPR 1983.
[18] G. E. Hinton, S. Osindero, Y-W. Teh, A fast learning algorithm for deep belief nets, Neural Comput. 18, 1527– 1554 (2006).
[19] T. J. Sejnowski, Higher-order Boltzmann machines, AIP Conference Proceedings 151: Neural Networks for Com- puting (1986).
[20] R. Salakhutdinov, G. E. Hinton, Deep Boltzmann ma- chines, AISTATS 2009.
[21] M. Ranzato, G. E. Hinton, Modeling pixel means and covariances using factorized third-order Boltzmann ma- chines, CVPR 2010.
[22] R. Memisevic, G. E. Hinton, Learning to represent spatial transformation with factored higher-order Boltzmann machines, Neural Comput. 22, 1473–1492 (2010).
[23] S. Golden, Lower bounds for the Helmholtz function, Phys. Rev., 137, B1127 (1965).
[24] C.J. Thompson, Inequality with applications in statisti- cal mechanics, J. Math. Phys. 6, 1812 (1965).
[25] https://en.wikipedia.org/wiki/Broyden-Fletcher- Goldfarb-Shanno algorithm.
[26] S. Osindero and G.E. Hinton, Modeling image patches with a directed hierarchy of Markov random fields, Ad- vances in neural information processing systems (2008).
[27] R. Harris et al., Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Pro- cessor, Phys. Rev. B 82, 024511 (2010).
[28] S. Boixo, T. Albash, F. M. Spedalieri, N. Chancellor, and D.A. Lidar, Experimental Signature of Programmable Quantum Annealing, Nat. Commun. 4, 2067 (2013).
[29] S. Boixo, T.F. Rønnow, S.V. Isakov, Z. Wang, D. Wecker, D.A. Lidar, J.M. Martinis, M. Troyer, Nature Phys. 10, 218 (2014).
[30] S. Boixo, V. N. Smelyanskiy, A. Shabani, S. V. Isakov, M. Dykman, V. S. Denchev, M. Amin, A. Smirnov, M. Mohseni, and H. Neven, eprint arXiv:1502.05754, long version: arXiv:1411.4036 (2014).
[31] T. Lanting et al., Phys. Rev. X, 4, 021041 (2014).
[32] M.H. Amin, Searching for quantum speedup in qua- sistatic quantum annealers, Phys. Rev. A 92 052323,
(2015).
[33] N.G. Dickson, M.W. Johnson, M.H. Amin, R. Harris, F.
Altomare, A. J. Berkley, P. Bunyk, J. Cai, E. M. Chap- ple, P. Chavez, F. Cioata, T. Cirip, P. deBuen, M. Drew- Brook, C. Enderud, S. Gildert, F. Hamze, J.P. Hilton, E. Hoskinson, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Lanting, T. Mahon, R. Neufeld, T. Oh, I. Perminov, C. Petroff, A. Przybysz, C. Rich, P. Spear, A. Tcaciuc, M.C. Thom, E. Tolkacheva, S. Uchaikin, J. Wang, A. B. Wilson, Z. Merali, and G. Rose, Thermally assisted quan- tum annealing of a 16-qubit problem, Nature Commun. 4 1903, (2013).
[34] In physical systems, Hamiltonian parameters have unit of energy. We normalize these parameters by kBT ≡ β−1, where T is temperature and kB is the Boltzmann con- stant; we absorb β into the parameters.
[35] There are other techniques used for supervised learning, for example, when only a small fraction of the available data is labeled.
[36] This choice was made to keep the number of qubits small to allow for exact diagonalization.

99

[1] P. W. Shor, “Algorithms for quantum computation: dis- crete logarithms and factoring,” Foundations of Com- puter Science, 1994 Proceedings., 35th Annual Sympo- sium on, 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings , 124–134 (20-22 Nov 1994).
[2] R.P. Feynman, “Simulating Physics with Computers,” Intl. J. Theor. Phys. 21, 467 (1982).
[3] Seth Lloyd, “Universal quantum simulators,” Science 273, 1073–1078 (1996).
[4] J. Ignacio Cirac and Peter Zoller, “Goals and opportu- nities in quantum simulation,” Nat. Phys. 8, 264–266 (2012).
[5] Julian Kelly, “A preview of bristlecone, google’s new quantum processor,” (2018).
[6] Dario Gil, “The future is quantum,” (2017).
[7] “2018 ces: Intel advances quantum and neuromorphic
computing research,” (2018).
[8] J. S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick,
M. Block, B. Bloom, S. Caldwell, N. Didier, E. Schuyler Fried, S. Hong, P. Karalekas, C. B. Osborn, A. Papa- george, E. C. Peterson, G. Prawiroatmodjo, N. Rubin, Colm A. Ryan, D. Scarabelli, M. Scheer, E. A. Sete, P. Sivarajah, Robert S. Smith, A. Staley, N. Tezak, W. J. Zeng, A. Hudson, Blake R. Johnson, M. Reagor, M. P. da Silva, and C. Rigetti, “Unsupervised machine learning on a hybrid quantum computer,” arXiv:1712.05771 (2017).
[9] J. Zhang, G. Pagano, P. W. Hess, A. Kyprianidis, P. Becker, H. Kaplan, A. V. Gorshkov, Z. X. Gong, and C. Monroe, “Observation of a many-body dynami- cal phase transition with a 53-qubit quantum simulator,” Nature 551, 601 EP – (2017).
[10] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, Soon- won Choi, Alexander S. Zibrov, Manuel Endres, Markus Greiner, Vladan Vuleti ́c, and Mikhail D. Lukin, “Prob- ing many-body dynamics on a 51-atom quantum simula- tor,” Nature 551, 579 EP – (2017).
[11] C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, A. Megrant, B. Chiaro, A. Dunsworth, K. Arya, R. Barends, B. Burkett, Y. Chen, Z. Chen, A. Fowler, B. Foxen, M. Giustina, R. Graff, E. Jeffrey, T. Huang, J. Kelly, P. Klimov, E. Lucero, J. Mutus, M. Neeley, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. C. White, H. Neven, and J. M. Martinis, “A blueprint for demonstrating quantum supremacy with superconducting qubits,” Science 360, 195 (2018).
[12] John Preskill, “Quantum computing in the nisq era and beyond,” arXiv:1801.00862 (2018).
[13] Aram W. Harrow and Ashley Montanaro, “Quantum computational supremacy,” Nature 549, 203 EP – (2017).
[14] Michael A Nielsen and Isaac L Chuang, Quantum compu- tation and quantum information (Cambridge University Press, 2010).
[15] Tadashi Kadowaki and Hidetoshi Nishimori, “Quantum annealing in the transverse Ising model,” Phys. Rev. E 58, 5355 (1998).
[16] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda, “A Quan- tum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem,” Science 292, 472–475 (2001).
[17] Sergio Boixo, Troels F. Ronnow, Sergei V. Isakov, Zhihui Wang, David Wecker, Daniel A. Lidar, John M. Martinis, and Matthias Troyer, “Evidence for quantum annealing with more than one hundred qubits,” Nat. Phys. 10, 218– 224 (2014).
[18] Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Mar- tinis, Daniel A. Lidar, and Matthias Troyer, “Defining and detecting quantum speedup,” Science 345, 420–424 (2014).
[19] James King, Sheir Yarkoni, Mayssam M. Nevisi, Jeremy P. Hilton, and Catherine C. McGeoch, “Bench- marking a quantum annealing processor with the time- to-target metric,” arXiv:1508.05087 (2015).
[20] Itay Hen, Joshua Job, Tameem Albash, Troels F. Rønnow, Matthias Troyer, and Daniel A. Lidar, “Prob- ing for quantum speedup in spin-glass problems with planted solutions,” Phys. Rev. A 92, 042325 (2015).
[21] Andrew D. King, Trevor Lanting, and Richard Harris, “Performance of a quantum annealer on range-limited constraint satisfaction problems,” arXiv:1502.02098 (2015).
[22] James King, Sheir Yarkoni, Jack Raymond, Isil Ozfi- dan, Andrew D. King, Mayssam Mohammadi Nevisi, Jeremy P. Hilton, and Catherine C. McGeoch, “Quan- tum annealing amid local ruggedness and global frustra-
tion,” arXiv:1701.04579 (2017).
[23] Salvatore Mandra, Zheng Zhu, Wenlong Wang, Alejandro
Perdomo-Ortiz, and Helmut G. Katzgraber, “Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics versus quantum approaches,” Physical Review A 94, 022337– (2016).
[24] Walter Vinci and Daniel A. Lidar, “Optimally stopped optimization,” Physical Review Applied 6, 054016– (2016).
[25] Vasil S. Denchev, Sergio Boixo, Sergei V. Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Marti- nis, and Hartmut Neven, “What is the computational value of finite-range tunneling?” Phys. Rev. X 6, 031015 (2016).
[26] Helmut G. Katzgraber, Firas Hamze, Zheng Zhu, An- drew J. Ochoa, and H. Munoz-Bauza, “Seeking quan- tum speedup through spin glasses: The good, the bad, and the ugly,” Phys. Rev. X 5, 031026– (2015).
[27] Quantum annealers have also been studied outside the context of combinatorial optimization. See, e.g., Refs. [87–92].
[28] “The d-wave 2000q system,” .
[29] We stress that our observation of an optimal anneal-
ing time is not simply due to advances in the quantum annealing hardware; we demonstrate optimal annealing times for these problem instances on the two most recent generations of D-Wave processors.
[30] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Opti- [38]
of the hardware-planted instances using SAC with y = log TTS
mization by simulated annealing,” Science 220, 671–680
(1983). T. Lanting, AJ. Przybysz, and J. Whittaker, “Archi-
[31] GiuseppeE.Santoro,RomanMartonˇa ́k,ErioTosatti, and Roberto Car, “Theory of quantum annealing of an Ising spin glass,” Science 295, 2427–2430 (2002).
[32] Seung Woo Shin, Graeme Smith, John A. Smolin, and [39] Umesh Vazirani, “How “quantum” is the D-Wave ma-
chine?” arXiv:1401.7087 (2014).
[33] Sergei V. Isakov, Guglielmo Mazzola, Vadim N. Smelyan- [40] skiy, Zhang Jiang, Sergio Boixo, Hartmut Neven, and Matthias Troyer, “Understanding Quantum Tunneling through Quantum Monte Carlo Simulations,” Physical [41] Review Letters 117, 180402– (2016).
[34] Zhang Jiang, Vadim N. Smelyanskiy, Sergei V. Isakov,
Sergio Boixo, Guglielmo Mazzola, Matthias Troyer, and Hartmut Neven, “Scaling analysis and instantons for [42] thermally assisted tunneling and quantum Monte Carlo simulations,” Physical Review A 95, 012322– (2017).
[35] Sergio Boixo, Vadim N. Smelyanskiy, Alireza Shabani,
Sergei V. Isakov, Mark Dykman, Vasil S. Denchev, [43] Mohammad H. Amin, Anatoly Yu Smirnov, Masoud Mohseni, and Hartmut Neven, “Computational multi-
qubit tunnelling in programmable quantum annealers,” [44] Nat Commun 7 (2016).
[36] Siddharth Muthukrishnan, Tameem Albash, and
Daniel A. Lidar, “Tunneling and speedup in quantum op- [45] timization for permutation-symmetric problems,” Phys.
Rev. X 6, 031010 (2016).
[37] Vicky Choi, “Minor-embedding in adiabatic quantum [46]
tectural considerations in the design of a superconduct- ing quantum annealing processor,” IEEE Transactions on Applied Superconductivity 24, 1–10 (Aug. 2014).
M. B. Hastings and M. H. Freedman, “Obstructions to classically simulating the quantum adiabatic algorithm,” Quant. Inf. & Comp. 13, 1038 (2013).
Tameem Albash, Victor Martin-Mayor, and Itay Hen, “Temperature scaling law for quantum annealing opti- mizers,” Physical Review Letters 119, 110502– (2017). Helmut G. Katzgraber, Firas Hamze, and Ruben S. Andrist, “Glassy chimeras could be blind to quantum speedup: Designing better benchmarks for quantum an- nealing machines,” Phys. Rev. X 4, 021008– (2014). Matthias Steffen, Wim van Dam, Tad Hogg, Greg Breyta, and Isaac Chuang, “Experimental implemen- tation of an adiabatic quantum optimization algorithm,” Phys. Rev. Lett. 90, 067903– (2003).
M. S. Sarandy and D. A. Lidar, “Adiabatic quantum computation in open systems,” Phys. Rev. Lett. 95, 250503– (2005).
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, “Quantum adiabatic evolution algorithms versus simu- lated annealing,” arXiv:quant-ph/0201031 (2002). Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, “Quantum adiabatic evolution algorithms with different paths,” arXiv:quant-ph/0208135 (2002).
Gernot Schaller and Ralf Schu ̈tzhold, “The role of sym-
computation: I. The parameter setting problem,” Quant. Inf. Proc. 7, 193–209 (2008).
P. I Bunyk, E. M. Hoskinson, M. W. Johnson, E. Tolka- cheva, F. Altomare, AJ. Berkley, R. Harris, J. P. Hilton,
metries in adiabatic quantum algorithms,” Quantum In-
formation & Computation 10, 0109 (2010).
[47] SA Owerre and MB Paranjape, “Macroscopic quantum tunneling and quantum–classical phase transitions of the escape rate in large spin systems,” Physics Reports 546,
1–60 (2015).
[48] ThomasJo ̈rg,FlorentKrzakala,JorgeKurchan,and
A. C. Maggs, “Simple glass models and their quan- tum annealing,” Physical Review Letters 101, 147204– (2008).
[49] Evgeny Andriyash and Mohammad H. Amin, “Can quantum Monte Carlo simulate quantum annealing?” arXiv:1703.09277 (2017).
[50] Mohammad H. Amin, “Searching for quantum speedup in quasistatic quantum annealers,” Physical Review A 92, 052323– (2015).
[51] D. Aharonov, A. Kitaev, and J. Preskill, “Fault-tolerant quantum computation with long-range correlated noise,” Phys. Rev. Lett. 96, 050504 (2006).
[52] Philip J. D. Crowley and A. G. Green, “Anisotropic landau-lifshitz-gilbert models of dissipation in qubits,” Physical Review A 94, 062106– (2016).
[53] Sergio Boixo, Tameem Albash, Federico M. Spedalieri, Nicholas Chancellor, and Daniel A. Lidar, “Experimen- tal signature of programmable quantum annealing,” Nat. Commun. 4, 2067 (2013).
[54] Tameem Albash, Troels F. Rønnow, Matthias Troyer, and Daniel A. Lidar, “Reexamining classical and quan- tum models for the D-Wave One processor,” Eur. Phys. J. Spec. Top. 224, 111–129 (2015).
[55] Tameem Albash, Walter Vinci, Anurag Mishra, Paul A. Warburton, and Daniel A. Lidar, “Consistency tests of classical and quantum models for a quantum annealer,” Phys. Rev. A 91, 042314– (2015).
[56] T. Lanting, A. J. Przybysz, A. Yu. Smirnov, F. M. Spedalieri, M. H. Amin, A. J. Berkley, R. Harris, F. Al- tomare, S. Boixo, P. Bunyk, N. Dickson, C. Enderud, J. P. Hilton, E. Hoskinson, M. W. Johnson, E. Ladizin- sky, N. Ladizinsky, R. Neufeld, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, S. Uchaikin, A. B. Wilson, and G. Rose, “Entanglement in a quantum an- nealing processor,” Phys. Rev. X 4, 021041– (2014).
[57] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Jo- hansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose, “Quantum annealing with manufactured spins,” Nature 473, 194–198 (2011).
[58] Guglielmo Mazzola, Vadim N. Smelyanskiy, and Matthias Troyer, “Quantum monte carlo tunneling from quantum chemistry to quantum annealing,” Physical Re- view B 96, 134305– (2017).
[59] S. P. Jordan, E. Farhi, and P. W. Shor, “Error-correcting codes for adiabatic quantum computation,” Phys. Rev. A 74, 052322 (2006).
[60] Adam D. Bookatz, Edward Farhi, and Leo Zhou, “Error suppression in hamiltonian-based quantum computation using energy penalties,” Physical Review A 92, 022317– (2015).
[61] Zhang Jiang and Eleanor G. Rieffel, “Non-commuting two-local hamiltonians for quantum error suppression,” Quantum Information Processing 16, 89 (2017).
[62] Milad Marvian and Daniel A. Lidar, “Error Suppres- sion for Hamiltonian-Based Quantum Computation Us- ing Subsystem Codes,” Physical Review Letters 118, 030504– (2017).
[63] Milad Marvian and Daniel A. Lidar, “Error suppression for hamiltonian quantum computing in markovian envi- ronments,” Physical Review A 95, 032302– (2017).
[64] Bettina Heim, Troels F. Rønnow, Sergei V. Isakov, and Matthias Troyer, “Quantum versus classical annealing of Ising spin glasses,” Science 348, 215–217 (2015).
[65] H. Rieger and N. Kawashima, “Application of a continu- ous time cluster algorithm to the two-dimensional ran- dom quantum Ising ferromagnet,” Eur. Phys. J. B 9, 233–236 (1999).
[66] Anders W. Sandvik, “Stochastic series expansion method for quantum Ising models with arbitrary interactions,” Phys. Rev. E 68, 056701 (2003).
[67] Tameem Albash, Gene Wagenbreth, and Itay Hen, “Off- diagonal expansion quantum monte carlo,” Phys. Rev. E 96, 063309 (2017).
[68] Tameem Albash, Sergio Boixo, Daniel A Lidar, and Paolo Zanardi, “Quantum adiabatic Markovian master equations,” New J. of Phys. 14, 123016 (2012).
[69] Ka Wa Yip, Tameem Albash, and Daniel A. Li- dar, “Quantum trajectories for time-dependent adiabatic master equations,” Phys. Rev. A 97, 022116 (2018).
[70] Salvatore Mandra
, Helmut G. Katzgraber, and Creighton Thomas, “The pitfalls of planar spin-glass benchmarks: raising the bar for quantum annealers (again),” Quantum Science and Technology 2, 038501 (2017).
[71] Firas Hamze and Nando de Freitas, “From fields to trees,” in UAI , edited by David Maxwell Chickering and Joseph Y. Halpern (AUAI Press, Arlington, Virginia, 2004) pp. 243–250.
[72] Alex Selby, “Efficient subgraph-based sampling of Ising- type models with frustration,” arXiv:1409.3934 (2014).
[73] J. Houdayer, “A cluster monte carlo algorithm for 2- dimensional spin glasses,” The European Physical Jour- nal B - Condensed Matter and Complex Systems 22, 479– 484 (2001).
[74] Zheng Zhu, Andrew J. Ochoa, and Helmut G. Katz- graber, “Efficient cluster algorithm for spin glasses in any space dimension,” Phys. Rev. Lett. 115, 077201 (2015).
[75] Yoshiki Matsuda, Hidetoshi Nishimori, and Helmut G Katzgraber, “Quantum annealing for problems with ground-state degeneracy,” Journal of Physics: Confer- ence Series 143, 012003 (2009).
[76] Brian Hu Zhang, Gene Wagenbreth, Victor Martin- Mayor, and Itay Hen, “Advantages of unfair quan- tum ground-state sampling,” Scientific Reports 7, 1044 (2017).
[77] SalvatoreMandra`,ZhengZhu,andHelmutG.Katz- graber, “Exponentially biased ground-state sampling of quantum annealing machines with transverse-field driv- ing hamiltonians,” Phys. Rev. Lett. 118, 070502 (2017).
[78] James King, “Simulating a Quantum Annealer with GPU-Based Monte Carlo Algoritms,” in GTC 2016, S6380 (2016).
[79] W. K. Hastings, “Monte Carlo sampling methods using Markov chains and their applications,” Biometrika 57, 97–109 (1970).
[80] Nicholas Metropolis, Arianna W. Rosenbluth, Mar- shall N. Rosenbluth, Augusta H. Teller, and Edward
24

Teller, “Equation of state calculations by fast computing machines,” The Journal of Chemical Physics 21, 1087– 1092 (1953).
[81] Ulli Wolff, “Collective Monte Carlo updating for spin sys- tems,” Phys. Rev. Lett. 62, 361–364 (1989).
[82] S. Bravyi and B. Terhal, “Complexity of stoquastic frustration-free hamiltonians,” SIAM Journal on Com- puting, SIAM Journal on Computing 39, 1462–1485 (2009).
[83] Alex Selby, “Prog-QUBO,” https://github.com/ alex1770/QUBO-Chimera (2013).
[84] Jack Edmonds, “Paths, trees, and flowers,” Canad. J. Math. 17, 449–467 (1965).
[85] Vladimir Kolmogorov, “Blossom v: a new imple- mentation of a minimum cost perfect matching algo- rithm,” Mathematical Programming Computation 1, 43– 67 (2009).
[86] L Bieche, J P Uhry, R Maynard, and R Rammal, “On the ground states of the frustration model of a spin glass by a matching method of graph theory,” Journal of Physics A: Mathematical and General 13, 2553 (1980).
[87] Steven H. Adachi and Maxwell P. Henderson, “Appli- cation of quantum annealing to training of deep neural networks,” arXiv:1510.06356 (2015).
[88] Mohammad H. Amin, Evgeny Andriyash, Jason Rolfe, Bohdan Kulchytskyy, and Roger Melko, Phys. Rev. X 8, 021050 (2018).
[89] Marcello Benedetti, John Realpe-Go ́mez, Rupak Biswas, and Alejandro Perdomo-Ortiz, “Quantum-assisted learn- ing of hardware-embedded probabilistic graphical mod- els,” Phys. Rev. X 7, 041052 (2017).
[90] Alex Mott, Joshua Job, Jean-Roch Vlimant, Daniel Li- dar, and Maria Spiropulu, “Solving a higgs optimization problem with quantum annealing for machine learning,” Nature 550, 375 EP – (2017).
[91] Richard Y. Li, Rosa Di Felice, Remo Rohs, and Daniel A. Lidar, “Quantum annealing versus classical machine learning applied to a simplified computational biology problem,” npj Quantum Information 4, 14 (2018).
[92] Andrew D. King, Juan Carrasquilla, Isil Ozfidan, Jack Raymond, Evgeny Andriyash, Andrew Berkley, Mauri- cio Reis, Trevor M. Lanting, Richard Harris, Gabriel Poulin-Lamarre, Anatoly Yu. Smirnov, Christopher Rich, Fabio Altomare, Paul Bunyk, Jed Whittaker, Loren Swenson, Emile Hoskinson, Yuki Sato, Mark Volkmann, Eric Ladizinsky, Mark Johnson, Jeremy Hilton, and Mohammad H. Amin, “Observation of topological phe- nomena in a programmable lattice of 1,800 qubits,” arXiv:1803.02047 (2018).

文書履歴

ver. 0.01 初稿
ver. 0.02 26追加 20190920

kaizen_nagoya
I'm a network designer.I work on TOPPERS SmallestSetProfile Kernel,MISRA-C, STARC RTL Design StyleGuide (Verilog-HDL),HAZOP,ISO/IEC15504(AutomotiveSPICE),ISO26262. I was an editor on ISO/IEC 15504.
https://researchmap.jp/blogs/blog_entries/view/81777/f691323917cc4ea12caf0b03b34c8ea0?frame_id=442673
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away