Template-Based Minor Embedding for Adiabatic Quantum Optimization

References

• Alghassi H, Dridi R, Tayur S (2019) Graver bases via quantum annealing with application to non-linear integer programs. Preprint, submitted February 12, https://arxiv.org/abs/1902.04215.Google Scholar
• Balas E, Jeroslow RG (1972) Canonical cuts on the unit hypercube. SIAM J. Appl. Math. 23(1):61–69.Crossref, Google Scholar
• Bian Z, Chudak F, Israel RB, Lackey B, Macready WG, Roy A (2016) Mapping constrained optimization problems to quantum annealing with application to fault diagnosis. Frontiers ICT 3:14.Crossref, Google Scholar
• Bixby RE (2012) A brief history of linear and mixed-integer programming computation. Documenta Math. Extra Volume (Optimization Stories):107–121.Google Scholar
• Bondy JA, Murty USR (2008) Graph Theory (Springer-Verlag, London).Crossref, Google Scholar
• Boothby T, King AD, Roy A (2016) Fast clique minor generation in chimera qubit connectivity graphs. Quantum Inform. Processing 15(1):495–508.Crossref, Google Scholar
• Boothby K, Bunyk P, Raymond J, Roy A (2019) Next-generation topology of D-Wave quantum processors. Technical Report 14-1026A-C, D-Wave Systems Inc., Burnaby, BC, Canada.Google Scholar
• Boros E, Hammer PL (2002) Pseudo-Boolean optimization. Discrete Appl. Math. 123(1–3):155–225.Crossref, Google Scholar
• Cai J, Macready WG, Roy A (2014) A practical heuristic for finding graph minors. Preprint, submitted June 10, https://arxiv.org/abs/1406.2741.Google Scholar
• Choi V (2008) Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inform. Processing 7(5):193–209.Crossref, Google Scholar
• Choi V (2011) Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inform. Processing 10(3):343–353.Crossref, Google Scholar
• Coffrin C, Nagarajan H, Bent R (2019) Evaluating ising processing units with integer programming. Rousseau LM, Stergiou K, eds. Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Springer International Publishing, Cham, Switzerland), 163–181.Crossref, Google Scholar
• Coppersmith D, Gamarnik D, Sviridenko M (2002) The diameter of a long-range percolation graph. Random Structures Algorithms 21(1):1–13.Crossref, Google Scholar
• Dash S (2013) A note on QUBO instances defined on Chimera graphs. Preprint, submitted June 5, https://arxiv.org/abs/1306.1202.Google Scholar
• Date P, Patton R, Schuman C, Potok T (2019) Efficiently embedding qubo problems on adiabatic quantum computers. Quantum Inform. Processing 18(4):Article 117.Crossref, Google Scholar
• Dattani N (2019) Quadratization in discrete optimization and quantum mechanics. Preprint, submitted January 14, https://arxiv.org/abs/1901.04405.Google Scholar
• Dattani N, Szalay S, Chancellor N (2019) Pegasus: The second connectivity graph for large-scale quantum annealing hardware. Preprint, submitted January 22, https://arxiv.org/abs/1901.07636.Google Scholar
• Dridi R, Alghassi H, Tayur S (2018) A novel algebraic geometry compiling framework for adiabatic quantum computations. Preprint, submitted October 2, https://arxiv.org/abs/1810.01440.Google Scholar
• D-Wave Systems (2019) Introduction to the D-Wave quantum hardware. Accessed May 3, 2019, https://www.dwavesys.com/tutorials/background-reading-series/introduction-d-wave-quantum-hardware.Google Scholar
• Farhi E, Goldstone J, Gutmann S, Sipser M (2000) Quantum computation by adiabatic evolution. Preprint, submitted January 28, https://arxiv.org/abs/quant-ph/0001106.Google Scholar
• Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A, Preda D (2001) A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Sci. 292(5516):472–475.Crossref, Google Scholar
• Finnila A, Gomez M, Sebenik C, Stenson C, Doll J (1994) Quantum annealing: A new method for minimizing multidimensional functions. Chemical Phys. Lett. 219(5–6):343–348.Crossref, Google Scholar
• Goodrich TD, Horton E, Sullivan BD (2018a) Practical graph bipartization with applications in near-term quantum computing. Preprint, submitted May 2, https://arxiv.org/abs/1805.01041.Google Scholar
• Goodrich TD, Sullivan BD, Humble TS (2018b) Optimizing adiabatic quantum program compilation using a graph-theoretic framework. Quantum Inform. Processing 17(5):Article 118.Crossref, Google Scholar
• Hamilton KE, Humble TS (2017) Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets. Quantum Inform. Processing 16(4):1–17.Crossref, Google Scholar
• Johnson DS (1987) The NP-completeness column: An ongoing guide. J. Algorithms 8(3):438–448.Crossref, Google Scholar
• Kadowaki T, Nishimori H (1998) Quantum annealing in the transverse Ising model. Phys. Rev. E 58(5):5355.Crossref, Google Scholar
• Kalantari B (1986) Quadratic functions with exponential number of local maxima. Oper. Res. Lett. 5(1):47–49.Crossref, Google Scholar
• Kaminsky WM, Lloyd S (2004) Scalable architecture for adiabatic quantum computing of NP-hard problems. Leggett AJ, Ruggiero B, Silvestrini P, eds. Quantum Computing and Quantum Bits in Mesoscopic Systems (Springer, Boston), 229–236.Crossref, Google Scholar
• Kaminsky WM, Lloyd S, Orlando TP (2004) Scalable superconducting architecture for adiabatic quantum computation. Preprint, March 11, https://arxiv.org/abs/quant-ph/0403090.Google Scholar
• Karimi H, Rosenberg G (2017) Boosting quantum annealer performance via sample persistence. Quantum Inform. Processing 16(7):Article 166.Crossref, Google Scholar
• Klymko C, Sullivan BD, Humble TS (2014) Adiabatic quantum programming: Minor embedding with hard faults. Quantum Inform. Processing 13(3):709–729.Crossref, Google Scholar
• Lucas A (2014) Ising formulations of many NP problems. Frontiers Phys. 2:5.Crossref, Google Scholar
• Lucas A (2019) Hard combinatorial problems and minor embeddings on lattice graphs. Quantum Inform. Processing 18(7):203.Google Scholar
• McGeoch CC, Wang C (2013) Experimental evaluation of an adiabiatic quantum system for combinatorial optimization. Proc. ACM Internat. Conf. Comput. Frontiers (Association for Computing Machinery, New York), 23:1–23:11.Google Scholar
• Padberg M (1989) The Boolean quadric polytope: Some characteristics, facets and relatives. Math. Programming 45(1):139–172.Crossref, Google Scholar
• Rønnow TF, Wang Z, Job J, Boixo S, Isakov SV, Wecker D, Martinis JM, Lidar DA, Troyer M (2014) Defining and detecting quantum speedup. Sci. 345(6195):420–424.Crossref, Google Scholar
• Van Dam W, Mosca M, Vazirani U (2001) How powerful is adiabatic quantum computation? Naor M, program chair. Proc. 42nd IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 279–287.Google Scholar
• Yang Z, Dinneen MJ (2016) Graph minor embeddings for D-Wave computer architecture. Technical Report CDMTCS-503, Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, Auckland, New Zealand.Google Scholar
• Zaribafiyan A, Marchand DJJ, Rezaei SSC (2017) Systematic and deterministic graph minor embedding for Cartesian products of graphs. Quantum Inform. Processing 16(5):Article 136.Crossref, Google Scholar