DOI: 10.1007/s11128-013-0683-9. Adiabatic quantum programming: minor embedding with hard faults

Adiabatic quantum programming: minor embedding with hard faults

10.1007/s11128-013-0683-9

Crossref journal-article

Springer Science and Business Media LLC

Quantum Information Processing (297)

Bibliography

Klymko, C., Sullivan, B. D., & Humble, T. S. (2013). Adiabatic quantum programming: minor embedding with hard faults. Quantum Information Processing, 13(3), 709â729.

Authors 3

Christine Klymko (first)
Blair D. Sullivan (additional)
Travis S. Humble (additional)

References 25 Referenced 70

Adler, I., et al.: Faster parameterized algorithms for minor containment. Theor. Comput. Sci. 412, 7018–7028 (2011) (10.1016/j.tcs.2011.09.015) / Theor. Comput. Sci. by I Adler (2011)
Altshuler, B., Karvi, H., Roland, J.: Anderson localization makes adiabatic quantum optimization fail. Proc. Natl. Acad. Sci. USA 108, E19–E20 (2011) (10.1073/pnas.1018310108) / Proc. Natl. Acad. Sci. USA by B Altshuler (2011)
Amir, E.: Approximation algorithms for treewidth. Algorithmica 56, 448–479 (2010) (10.1007/s00453-008-9180-4) / Algorithmica by E Amir (2010)
Bian, Z., Chudak, F., Macready, W.G., Clark, L., Gaitan, F.: Experimental determination of Ramsey numbers. Phys. Rev. Lett. 111, 130505 (2013) (10.1103/PhysRevLett.111.130505)
Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11, 1–23 (1993) / Acta Cybern. by HL Bodlaender (1993)
Bodlaender, H.L.: A linear-time algorithm for finding tree decompositions of small treewidth. SIAM J. Comput. 25, 1035–1317 (1996) (10.1137/S0097539793251219) / SIAM J. Comput. by HL Bodlaender (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) (10.1016/S0166-218X(01)00341-9) / Discret. Appl. Math. by E Boros (2002)
Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7, 193–209 (2008) (10.1007/s11128-008-0082-9) / Quantum Inf. Process. by V Choi (2008)
Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10, 343–353 (2011) (10.1007/s11128-010-0200-3) / Quantum Inf. Process. by V Choi (2011)
Dickson, N.G., Amin, M.H.S.: Does adiabatic quantum optimization fail for NP-complete problems? Phys. Rev. Lett. 106, 050502 (2011) (10.1103/PhysRevLett.106.050502)
Dickson, N.G., Amin, M.H.S.: Algorithmic approach to adiabatic quantum optimization. Phys. Rev. A 85, 032303 (2012) (10.1103/PhysRevA.85.032303)
Diestel, R.: Graph Theory. Springer, Heidelberg (2005) / Graph Theory by R Diestel (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) (10.1126/science.1057726) / Science by E Farhi (2001)
Fomin, F.V., Thilikos, D.M.: Dominating sets and local treewidth. LNCS 2832, 221–229 (2003) / LNCS by FV Fomin (2003)
Gaitan, F., Clark, L.: Ramsey numbers and adiabatic quantum computing. Phys. Rev. Lett. 108, 010501 (2012) (10.1103/PhysRevLett.108.010501)
Harris, R., et al.: Experimental investigation of an eight qubit unit cell in a superconducting optimization processor. Phys. Rev. B 82, 024511–024526 (2010) (10.1103/PhysRevB.82.024511) / Phys. Rev. B by R Harris (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) (10.1109/SFCS.1996.548467)
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) (10.1038/srep00571)
Pudenz, K.L., Lidar, D.A.: Quantum adiabatic machine learning. Quantum Inf. Process. 12, 2027–2070 (2012) (10.1007/s11128-012-0506-4)
Robertson, N., Seymour, P.D.: Graph minors. XIII: the disjoint paths problem. J. Comb. Theory Ser. B 63, 65–110 (1995) (10.1006/jctb.1995.1006) / J. Comb. Theory Ser. B by N Robertson (1995)
Xiong, L., Dinneen, M.J.: The Feasibility and Use of a Minor Containment Algorithm, Computer Science Technical Reports 171, University of Auckland (2000)

Dates

Type	When
Created	11 years, 9 months ago (Nov. 19, 2013, 4:48 a.m.)
Deposited	6 years, 2 months ago (June 1, 2019, 3:39 a.m.)
Indexed	3 weeks, 2 days ago (Aug. 6, 2025, 8:53 a.m.)
Issued	11 years, 9 months ago (Nov. 20, 2013)
Published	11 years, 9 months ago (Nov. 20, 2013)
Published Online	11 years, 9 months ago (Nov. 20, 2013)
Published Print	11 years, 5 months ago (March 1, 2014)

Funders 0

None

BibTeX

@article{Klymko_2013, title={Adiabatic quantum programming: minor embedding with hard faults}, volume={13}, ISSN={1573-1332}, url={http://dx.doi.org/10.1007/s11128-013-0683-9}, DOI={10.1007/s11128-013-0683-9}, number={3}, journal={Quantum Information Processing}, publisher={Springer Science and Business Media LLC}, author={Klymko, Christine and Sullivan, Blair D. and Humble, Travis S.}, year={2013}, month=nov, pages={709–729} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        6
      ]
    ],
    "date-time": "2025-08-06T12:53:42Z",
    "timestamp": 1754484822859
  },
  "reference-count": 25,
  "publisher": "Springer Science and Business Media LLC",
  "issue": "3",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            2013,
            11,
            20
          ]
        ],
        "date-time": "2013-11-20T00:00:00Z",
        "timestamp": 1384905600000
      },
      "content-version": "tdm",
      "delay-in-days": 0,
      "URL": "http://www.springer.com/tdm"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        2014,
        3
      ]
    ]
  },
  "DOI": "10.1007/s11128-013-0683-9",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2013,
        11,
        19
      ]
    ],
    "date-time": "2013-11-19T09:48:41Z",
    "timestamp": 1384854521000
  },
  "page": "709-729",
  "source": "Crossref",
  "is-referenced-by-count": 70,
  "title": "Adiabatic quantum programming: minor embedding with hard faults",
  "prefix": "10.1007",
  "volume": "13",
  "author": [
    {
      "given": "Christine",
      "family": "Klymko",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "Blair D.",
      "family": "Sullivan",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Travis S.",
      "family": "Humble",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "297",
  "published-online": {
    "date-parts": [
      [
        2013,
        11,
        20
      ]
    ]
  },
  "reference": [
    {
      "key": "683_CR1",
      "doi-asserted-by": "crossref",
      "first-page": "7018",
      "DOI": "10.1016/j.tcs.2011.09.015",
      "volume": "412",
      "author": "I Adler",
      "year": "2011",
      "unstructured": "Adler, I., et al.: Faster parameterized algorithms for minor containment. Theor. Comput. Sci. 412, 7018\u20137028 (2011)",
      "journal-title": "Theor. Comput. Sci."
    },
    {
      "key": "683_CR2",
      "doi-asserted-by": "crossref",
      "first-page": "E19",
      "DOI": "10.1073/pnas.1018310108",
      "volume": "108",
      "author": "B Altshuler",
      "year": "2011",
      "unstructured": "Altshuler, B., Karvi, H., Roland, J.: Anderson localization makes adiabatic quantum optimization fail. Proc. Natl. Acad. Sci. USA 108, E19\u2013E20 (2011)",
      "journal-title": "Proc. Natl. Acad. Sci. USA"
    },
    {
      "key": "683_CR3",
      "doi-asserted-by": "crossref",
      "first-page": "448",
      "DOI": "10.1007/s00453-008-9180-4",
      "volume": "56",
      "author": "E Amir",
      "year": "2010",
      "unstructured": "Amir, E.: Approximation algorithms for treewidth. Algorithmica 56, 448\u2013479 (2010)",
      "journal-title": "Algorithmica"
    },
    {
      "key": "683_CR4",
      "doi-asserted-by": "crossref",
      "unstructured": "Bian, Z., Chudak, F., Macready, W.G., Clark, L., Gaitan, F.: Experimental determination of Ramsey numbers. Phys. Rev. Lett. 111, 130505 (2013)",
      "DOI": "10.1103/PhysRevLett.111.130505"
    },
    {
      "key": "683_CR5",
      "first-page": "1",
      "volume": "11",
      "author": "HL Bodlaender",
      "year": "1993",
      "unstructured": "Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11, 1\u201323 (1993)",
      "journal-title": "Acta Cybern."
    },
    {
      "key": "683_CR6",
      "doi-asserted-by": "crossref",
      "first-page": "1035",
      "DOI": "10.1137/S0097539793251219",
      "volume": "25",
      "author": "HL Bodlaender",
      "year": "1996",
      "unstructured": "Bodlaender, H.L.: A linear-time algorithm for finding tree decompositions of small treewidth. SIAM J. Comput. 25, 1035\u20131317 (1996)",
      "journal-title": "SIAM J. Comput."
    },
    {
      "key": "683_CR7",
      "unstructured": "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)"
    },
    {
      "key": "683_CR8",
      "doi-asserted-by": "crossref",
      "first-page": "155",
      "DOI": "10.1016/S0166-218X(01)00341-9",
      "volume": "123",
      "author": "E Boros",
      "year": "2002",
      "unstructured": "Boros, E., Hammer, P.L.: Pseudo-boolean optimization. Discret. Appl. Math. 123, 155\u2013225 (2002)",
      "journal-title": "Discret. Appl. Math."
    },
    {
      "key": "683_CR9",
      "doi-asserted-by": "crossref",
      "first-page": "193",
      "DOI": "10.1007/s11128-008-0082-9",
      "volume": "7",
      "author": "V Choi",
      "year": "2008",
      "unstructured": "Choi, V.: Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Inf. Process. 7, 193\u2013209 (2008)",
      "journal-title": "Quantum Inf. Process."
    },
    {
      "key": "683_CR10",
      "doi-asserted-by": "crossref",
      "first-page": "343",
      "DOI": "10.1007/s11128-010-0200-3",
      "volume": "10",
      "author": "V Choi",
      "year": "2011",
      "unstructured": "Choi, V.: Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Inf. Process. 10, 343\u2013353 (2011)",
      "journal-title": "Quantum Inf. Process."
    },
    {
      "key": "683_CR11",
      "doi-asserted-by": "crossref",
      "unstructured": "Dickson, N.G., Amin, M.H.S.: Does adiabatic quantum optimization fail for NP-complete problems? Phys. Rev. Lett. 106, 050502 (2011)",
      "DOI": "10.1103/PhysRevLett.106.050502"
    },
    {
      "key": "683_CR12",
      "doi-asserted-by": "crossref",
      "unstructured": "Dickson, N.G., Amin, M.H.S.: Algorithmic approach to adiabatic quantum optimization. Phys. Rev. A 85, 032303 (2012)",
      "DOI": "10.1103/PhysRevA.85.032303"
    },
    {
      "key": "683_CR13",
      "volume-title": "Graph Theory",
      "author": "R Diestel",
      "year": "2005",
      "unstructured": "Diestel, R.: Graph Theory. Springer, Heidelberg (2005)"
    },
    {
      "key": "683_CR14",
      "unstructured": "D-Wave Systems Inc., 100\u20134401 Still Creek Drive, Burnaby V5C 6G9, BC, Canada. http://www.dwavesys.com/"
    },
    {
      "key": "683_CR15",
      "unstructured": "Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution, arxiv:quant-ph/0001106 (2000)"
    },
    {
      "key": "683_CR16",
      "doi-asserted-by": "crossref",
      "first-page": "472",
      "DOI": "10.1126/science.1057726",
      "volume": "292",
      "author": "E Farhi",
      "year": "2001",
      "unstructured": "Farhi, E., et al.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472\u2013476 (2001)",
      "journal-title": "Science"
    },
    {
      "key": "683_CR17",
      "first-page": "221",
      "volume": "2832",
      "author": "FV Fomin",
      "year": "2003",
      "unstructured": "Fomin, F.V., Thilikos, D.M.: Dominating sets and local treewidth. LNCS 2832, 221\u2013229 (2003)",
      "journal-title": "LNCS"
    },
    {
      "key": "683_CR18",
      "doi-asserted-by": "crossref",
      "unstructured": "Gaitan, F., Clark, L.: Ramsey numbers and adiabatic quantum computing. Phys. Rev. Lett. 108, 010501 (2012)",
      "DOI": "10.1103/PhysRevLett.108.010501"
    },
    {
      "key": "683_CR19",
      "doi-asserted-by": "crossref",
      "first-page": "024511",
      "DOI": "10.1103/PhysRevB.82.024511",
      "volume": "82",
      "author": "R Harris",
      "year": "2010",
      "unstructured": "Harris, R., et al.: Experimental investigation of an eight qubit unit cell in a superconducting optimization processor. Phys. Rev. B 82, 024511\u2013024526 (2010)",
      "journal-title": "Phys. Rev. B"
    },
    {
      "key": "683_CR20",
      "doi-asserted-by": "crossref",
      "unstructured": "Kleinberg, J., Rubinfeld, R.: Short paths in expander graphs. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pp. 86\u201395 (1996)",
      "DOI": "10.1109/SFCS.1996.548467"
    },
    {
      "key": "683_CR21",
      "unstructured": "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)"
    },
    {
      "key": "683_CR22",
      "doi-asserted-by": "crossref",
      "unstructured": "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)",
      "DOI": "10.1038/srep00571"
    },
    {
      "key": "683_CR23",
      "doi-asserted-by": "crossref",
      "unstructured": "Pudenz, K.L., Lidar, D.A.: Quantum adiabatic machine learning. Quantum Inf. Process. 12, 2027\u20132070 (2012)",
      "DOI": "10.1007/s11128-012-0506-4"
    },
    {
      "key": "683_CR24",
      "doi-asserted-by": "crossref",
      "first-page": "65",
      "DOI": "10.1006/jctb.1995.1006",
      "volume": "63",
      "author": "N Robertson",
      "year": "1995",
      "unstructured": "Robertson, N., Seymour, P.D.: Graph minors. XIII: the disjoint paths problem. J. Comb. Theory Ser. B 63, 65\u2013110 (1995)",
      "journal-title": "J. Comb. Theory Ser. B"
    },
    {
      "key": "683_CR25",
      "unstructured": "Xiong, L., Dinneen, M.J.: The Feasibility and Use of a Minor Containment Algorithm, Computer Science Technical Reports 171, University of Auckland (2000)"
    }
  ],
  "container-title": "Quantum Information Processing",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "http://link.springer.com/content/pdf/10.1007/s11128-013-0683-9.pdf",
      "content-type": "application/pdf",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "http://link.springer.com/article/10.1007/s11128-013-0683-9/fulltext.html",
      "content-type": "text/html",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "http://link.springer.com/content/pdf/10.1007/s11128-013-0683-9",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2019,
        6,
        1
      ]
    ],
    "date-time": "2019-06-01T07:39:15Z",
    "timestamp": 1559374755000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "http://link.springer.com/10.1007/s11128-013-0683-9"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2013,
        11,
        20
      ]
    ]
  },
  "references-count": 25,
  "journal-issue": {
    "issue": "3",
    "published-print": {
      "date-parts": [
        [
          2014,
          3
        ]
      ]
    }
  },
  "alternative-id": [
    "683"
  ],
  "URL": "http://dx.doi.org/10.1007/s11128-013-0683-9",
  "relation": {},
  "ISSN": [
    "1570-0755",
    "1573-1332"
  ],
  "subject": [],
  "container-title-short": "Quantum Inf Process",
  "published": {
    "date-parts": [
      [
        2013,
        11,
        20
      ]
    ]
  }
}