Adiabatic quantum programming: minor embedding with hard faults

Quantum Information Processing - Tập 13 Số 3 - Trang 709-729 - 2014
Christine Klymko1, Blair D. Sullivan2, Travis S. Humble2
1Department of Mathematics and Computer Science, Emory University, 400 Dowman Drive, Atlanta, GA , 30322, USA
2Oak Ridge National Laboratory, Quantum Computing Institute, 1 Bethel Valley Road, Oak Ridge, TN , 37831, USA

Tóm tắt

Từ khóa


Tài liệu tham khảo

Adler, I., et al.: Faster parameterized algorithms for minor containment. Theor. Comput. Sci. 412, 7018–7028 (2011)

Altshuler, B., Karvi, H., Roland, J.: Anderson localization makes adiabatic quantum optimization fail. Proc. Natl. Acad. Sci. USA 108, E19–E20 (2011)

Amir, E.: Approximation algorithms for treewidth. Algorithmica 56, 448–479 (2010)

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

Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11, 1–23 (1993)

Bodlaender, H.L.: A linear-time algorithm for finding tree decompositions of small treewidth. SIAM J. Comput. 25, 1035–1317 (1996)

Bodlaender, H.L., Koster, A.M.C.A.: Treewidth Computations II. Lower Bounds, Technical Report UU-CS-2010-022. Department of Information and Computing Sciences, Utrecht University (2010)

Boros, E., Hammer, P.L.: Pseudo-boolean optimization. Discret. Appl. Math. 123, 155–225 (2002)

Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7, 193–209 (2008)

Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10, 343–353 (2011)

Dickson, N.G., Amin, M.H.S.: Does adiabatic quantum optimization fail for NP-complete problems? Phys. Rev. Lett. 106, 050502 (2011)

Dickson, N.G., Amin, M.H.S.: Algorithmic approach to adiabatic quantum optimization. Phys. Rev. A 85, 032303 (2012)

Diestel, R.: Graph Theory. Springer, Heidelberg (2005)

D-Wave Systems Inc., 100–4401 Still Creek Drive, Burnaby V5C 6G9, BC, Canada. http://www.dwavesys.com/

Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution, arxiv:quant-ph/0001106 (2000)

Farhi, E., et al.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472–476 (2001)

Fomin, F.V., Thilikos, D.M.: Dominating sets and local treewidth. LNCS 2832, 221–229 (2003)

Gaitan, F., Clark, L.: Ramsey numbers and adiabatic quantum computing. Phys. Rev. Lett. 108, 010501 (2012)

Harris, R., et al.: Experimental investigation of an eight qubit unit cell in a superconducting optimization processor. Phys. Rev. B 82, 024511–024526 (2010)

Kleinberg, J., Rubinfeld, R.: Short paths in expander graphs. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pp. 86–95 (1996)

Neven, H., Rose, G., Macready, W.G.: Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization, arXiv:0804.4457v1 [quant-ph] (2008)

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)

Pudenz, K.L., Lidar, D.A.: Quantum adiabatic machine learning. Quantum Inf. Process. 12, 2027–2070 (2012)

Robertson, N., Seymour, P.D.: Graph minors. XIII: the disjoint paths problem. J. Comb. Theory Ser. B 63, 65–110 (1995)

Xiong, L., Dinneen, M.J.: The Feasibility and Use of a Minor Containment Algorithm, Computer Science Technical Reports 171, University of Auckland (2000)