DOI: 10.1073/pnas.1111758109. A quantum–quantum Metropolis algorithm

10.1073/pnas.1111758109

Crossref journal-article

Proceedings of the National Academy of Sciences

Proceedings of the National Academy of Sciences (341)

Abstract

The classical Metropolis sampling method is a cornerstone of many statistical modeling applications that range from physics, chemistry, and biology to economics. This method is particularly suitable for sampling the thermal distributions of classical systems. The challenge of extending this method to the simulation of arbitrary quantum systems is that, in general, eigenstates of quantum Hamiltonians cannot be obtained efficiently with a classical computer. However, this challenge can be overcome by quantum computers. Here, we present a quantum algorithm which fully generalizes the classical Metropolis algorithm to the quantum domain. The meaning of quantum generalization is twofold: The proposed algorithm is not only applicable to both classical and quantum systems, but also offers a quantum speedup relative to the classical counterpart. Furthermore, unlike the classical method of quantum Monte Carlo, this quantum algorithm does not suffer from the negative-sign problem associated with fermionic systems. Applications of this algorithm include the study of low-temperature properties of quantum systems, such as the Hubbard model, and preparing the thermal states of sizable molecules to simulate, for example, chemical reactions at an arbitrary temperature.

Bibliography

Yung, M.-H., & Aspuru-Guzik, A. (2012). A quantumâquantum Metropolis algorithm. Proceedings of the National Academy of Sciences, 109(3), 754â759.

Authors 2

Man-Hong Yung (first)
Alán Aspuru-Guzik (additional)

References 35 Referenced 104

10.1103/RevModPhys.39.883
10.1093/acprof:oso/9780198509417.001.0001
10.1088/1367-2630/13/9/093021
10.1103/RevModPhys.71.1253
JM Thijssen Computational Physics (Cambridge Univ Press, Cambridge, UK, 1999). / Computational Physics by Thijssen JM (1999)
10.1112/jlms/s2-25.3.564
M Mezard, G Parisi, MA Virasoro Spin Glass Theory and Beyond (World Scientific, Teaneck, NJ, 1987). / Spin Glass Theory and Beyond by Mezard M (1987)
10.1103/PhysRevLett.94.170201
10.1103/PhysRevLett.85.3547
10.1103/RevModPhys.73.33
10.1007/BF02650179
10.1126/science.1177838
10.1146/annurev-physchem-032210-103512
10.1038/415039a
10.1126/science.273.5278.1073
10.1103/PhysRevE.59.2429
10.1098/rspa.1998.0162
10.1073/pnas.0808245105
10.1103/PhysRevA.64.022319
10.1103/PhysRevLett.102.130503
10.1103/PhysRevLett.103.220502
10.1103/PhysRevLett.105.170405
10.1103/PhysRevA.82.060302
10.1103/PhysRevLett.83.5162
10.1126/science.1113479
10.1039/b804804e
10.1063/1.3503767
10.1080/00268976.2011.552441
10.1038/srep00088
10.1109/FOCS.2004.53
10.1103/PhysRevLett.101.130504
10.1103/PhysRevA.78.042336
10.1103/PhysRevA.61.022301
10.1038/nature09770
10.1038/299802a0

Dates

Type	When
Created	13 years, 8 months ago (Jan. 4, 2012, 1:38 a.m.)
Deposited	3 years, 4 months ago (April 15, 2022, 7:33 a.m.)
Indexed	6 days, 15 hours ago (Aug. 30, 2025, 12:51 p.m.)
Issued	13 years, 8 months ago (Jan. 3, 2012)
Published	13 years, 8 months ago (Jan. 3, 2012)
Published Online	13 years, 8 months ago (Jan. 3, 2012)
Published Print	13 years, 7 months ago (Jan. 17, 2012)

Funders 0

None

BibTeX

@article{Yung_2012, title={A quantum–quantum Metropolis algorithm}, volume={109}, ISSN={1091-6490}, url={http://dx.doi.org/10.1073/pnas.1111758109}, DOI={10.1073/pnas.1111758109}, number={3}, journal={Proceedings of the National Academy of Sciences}, publisher={Proceedings of the National Academy of Sciences}, author={Yung, Man-Hong and Aspuru-Guzik, Alán}, year={2012}, month=jan, pages={754–759} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        30
      ]
    ],
    "date-time": "2025-08-30T16:51:42Z",
    "timestamp": 1756572702898
  },
  "reference-count": 35,
  "publisher": "Proceedings of the National Academy of Sciences",
  "issue": "3",
  "content-domain": {
    "domain": [
      "www.pnas.org"
    ],
    "crossmark-restriction": true
  },
  "published-print": {
    "date-parts": [
      [
        2012,
        1,
        17
      ]
    ]
  },
  "abstract": "<jats:p>The classical Metropolis sampling method is a cornerstone of many statistical modeling applications that range from physics, chemistry, and biology to economics. This method is particularly suitable for sampling the thermal distributions of classical systems. The challenge of extending this method to the simulation of arbitrary quantum systems is that, in general, eigenstates of quantum Hamiltonians cannot be obtained efficiently with a classical computer. However, this challenge can be overcome by quantum computers. Here, we present a quantum algorithm which fully generalizes the classical Metropolis algorithm to the quantum domain. The meaning of quantum generalization is twofold: The proposed algorithm is not only applicable to both classical and quantum systems, but also offers a quantum speedup relative to the classical counterpart. Furthermore, unlike the classical method of quantum Monte Carlo, this quantum algorithm does not suffer from the negative-sign problem associated with fermionic systems. Applications of this algorithm include the study of low-temperature properties of quantum systems, such as the Hubbard model, and preparing the thermal states of sizable molecules to simulate, for example, chemical reactions at an arbitrary temperature.</jats:p>",
  "DOI": "10.1073/pnas.1111758109",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2012,
        1,
        4
      ]
    ],
    "date-time": "2012-01-04T06:38:53Z",
    "timestamp": 1325659133000
  },
  "page": "754-759",
  "update-policy": "http://dx.doi.org/10.1073/pnas.cm10313",
  "source": "Crossref",
  "is-referenced-by-count": 104,
  "title": "A quantum\u2013quantum Metropolis algorithm",
  "prefix": "10.1073",
  "volume": "109",
  "author": [
    {
      "given": "Man-Hong",
      "family": "Yung",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Department of Chemistry and Chemical Biology, Harvard University, Cambridge MA, 02138"
        }
      ]
    },
    {
      "given": "Al\u00e1n",
      "family": "Aspuru-Guzik",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Department of Chemistry and Chemical Biology, Harvard University, Cambridge MA, 02138"
        }
      ]
    }
  ],
  "member": "341",
  "published-online": {
    "date-parts": [
      [
        2012,
        1,
        3
      ]
    ]
  },
  "reference": [
    {
      "key": "e_1_3_3_1_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/RevModPhys.39.883"
    },
    {
      "key": "e_1_3_3_2_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/acprof:oso/9780198509417.001.0001"
    },
    {
      "key": "e_1_3_3_3_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1088/1367-2630/13/9/093021"
    },
    {
      "key": "e_1_3_3_4_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/RevModPhys.71.1253"
    },
    {
      "key": "e_1_3_3_5_2",
      "volume-title": "Computational Physics",
      "author": "Thijssen JM",
      "year": "1999",
      "unstructured": "JM Thijssen Computational Physics (Cambridge Univ Press, Cambridge, UK, 1999)."
    },
    {
      "key": "e_1_3_3_6_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1112/jlms/s2-25.3.564"
    },
    {
      "key": "e_1_3_3_7_2",
      "volume-title": "Spin Glass Theory and Beyond",
      "author": "Mezard M",
      "year": "1987",
      "unstructured": "M Mezard, G Parisi, MA Virasoro Spin Glass Theory and Beyond (World Scientific, Teaneck, NJ, 1987)."
    },
    {
      "key": "e_1_3_3_8_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.94.170201"
    },
    {
      "key": "e_1_3_3_9_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.85.3547"
    },
    {
      "key": "e_1_3_3_10_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/RevModPhys.73.33"
    },
    {
      "key": "e_1_3_3_11_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02650179"
    },
    {
      "key": "e_1_3_3_12_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.1177838"
    },
    {
      "key": "e_1_3_3_13_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1146/annurev-physchem-032210-103512"
    },
    {
      "key": "e_1_3_3_14_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1038/415039a"
    },
    {
      "key": "e_1_3_3_15_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.273.5278.1073"
    },
    {
      "key": "e_1_3_3_16_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevE.59.2429"
    },
    {
      "key": "e_1_3_3_17_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1998.0162"
    },
    {
      "key": "e_1_3_3_18_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1073/pnas.0808245105"
    },
    {
      "key": "e_1_3_3_19_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.64.022319"
    },
    {
      "key": "e_1_3_3_20_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.102.130503"
    },
    {
      "key": "e_1_3_3_21_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.103.220502"
    },
    {
      "key": "e_1_3_3_22_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.105.170405"
    },
    {
      "key": "e_1_3_3_23_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.82.060302"
    },
    {
      "key": "e_1_3_3_24_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.83.5162"
    },
    {
      "key": "e_1_3_3_25_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.1113479"
    },
    {
      "key": "e_1_3_3_26_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1039/b804804e"
    },
    {
      "key": "e_1_3_3_27_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1063/1.3503767"
    },
    {
      "key": "e_1_3_3_28_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1080/00268976.2011.552441"
    },
    {
      "key": "e_1_3_3_29_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1038/srep00088"
    },
    {
      "key": "e_1_3_3_30_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/FOCS.2004.53"
    },
    {
      "key": "e_1_3_3_31_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.101.130504"
    },
    {
      "key": "e_1_3_3_32_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.78.042336"
    },
    {
      "key": "e_1_3_3_33_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.61.022301"
    },
    {
      "key": "e_1_3_3_34_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1038/nature09770"
    },
    {
      "key": "e_1_3_3_35_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1038/299802a0"
    }
  ],
  "container-title": "Proceedings of the National Academy of Sciences",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://pnas.org/doi/pdf/10.1073/pnas.1111758109",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2022,
        4,
        15
      ]
    ],
    "date-time": "2022-04-15T11:33:57Z",
    "timestamp": 1650022437000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://pnas.org/doi/full/10.1073/pnas.1111758109"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2012,
        1,
        3
      ]
    ]
  },
  "references-count": 35,
  "journal-issue": {
    "issue": "3",
    "published-print": {
      "date-parts": [
        [
          2012,
          1,
          17
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1073/pnas.1111758109"
  ],
  "URL": "http://dx.doi.org/10.1073/pnas.1111758109",
  "relation": {},
  "ISSN": [
    "0027-8424",
    "1091-6490"
  ],
  "subject": [],
  "container-title-short": "Proc. Natl. Acad. Sci. U.S.A.",
  "published": {
    "date-parts": [
      [
        2012,
        1,
        3
      ]
    ]
  },
  "assertion": [
    {
      "value": "2012-01-03",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}