On the computational complexity of curing non-stoquastic Hamiltonians. View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2019-12

AUTHORS

Milad Marvian, Daniel A Lidar, Itay Hen

ABSTRACT

Quantum many-body systems whose Hamiltonians are non-stoquastic, i.e., have positive off-diagonal matrix elements in a given basis, are known to pose severe limitations on the efficiency of Quantum Monte Carlo algorithms designed to simulate them, due to the infamous sign problem. We study the computational complexity associated with 'curing' non-stoquastic Hamiltonians, i.e., transforming them into sign-problem-free ones. We prove that if such transformations are limited to single-qubit Clifford group elements or general single-qubit orthogonal matrices, finding the curing transformation is NP-complete. We discuss the implications of this result. More... »

PAGES

1571

References to SciGraph publications

  • 1972. Reducibility among Combinatorial Problems in COMPLEXITY OF COMPUTER COMPUTATIONS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1038/s41467-019-09501-6

    DOI

    http://dx.doi.org/10.1038/s41467-019-09501-6

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1113261499

    PUBMED

    https://www.ncbi.nlm.nih.gov/pubmed/30952854


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0105", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Physics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Southern California", 
              "id": "https://www.grid.ac/institutes/grid.42505.36", 
              "name": [
                "Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA. mmarvian@mit.edu.", 
                "Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, CA, 90089, USA. mmarvian@mit.edu.", 
                "Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, CA, 90089, USA. mmarvian@mit.edu."
              ], 
              "type": "Organization"
            }, 
            "familyName": "Marvian", 
            "givenName": "Milad", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Southern California", 
              "id": "https://www.grid.ac/institutes/grid.42505.36", 
              "name": [
                "Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, CA, 90089, USA.", 
                "Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, CA, 90089, USA.", 
                "Department of Physics and Astronomy, University of Southern California, Los Angeles, CA, 90089, USA.", 
                "Department of Chemistry, University of Southern California, Los Angeles, CA, 90089, USA."
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lidar", 
            "givenName": "Daniel A", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Southern California", 
              "id": "https://www.grid.ac/institutes/grid.42505.36", 
              "name": [
                "Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, CA, 90089, USA.", 
                "Department of Physics and Astronomy, University of Southern California, Los Angeles, CA, 90089, USA.", 
                "Information Sciences Institute, University of Southern California, Marina del Rey, CA, 90292, USA."
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hen", 
            "givenName": "Itay", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1103/physreva.92.042325", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002022619"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreva.92.042325", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002022619"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.94.170201", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005409869"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.94.170201", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005409869"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4684-2001-2_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007977430", 
              "https://doi.org/10.1007/978-1-4684-2001-2_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevb.89.134422", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010503988"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevb.89.134422", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010503988"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1063/1.4936216", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017840462"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0166-218x(84)90081-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050792184"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1088/0305-4470/15/10/028", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059065892"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevb.41.9301", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060554544"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevb.41.9301", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060554544"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevb.93.054408", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060648868"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevb.93.054408", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060648868"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.117.197203", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060766672"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.117.197203", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060766672"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/08072689x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062854854"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/140998287", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062873087"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511614460", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098707127"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.97.043303", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1103993061"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physreve.97.043303", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1103993061"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2019-12", 
        "datePublishedReg": "2019-12-01", 
        "description": "Quantum many-body systems whose Hamiltonians are non-stoquastic, i.e., have positive off-diagonal matrix elements in a given basis, are known to pose severe limitations on the efficiency of Quantum Monte Carlo algorithms designed to simulate them, due to the infamous sign problem. We study the computational complexity associated with 'curing' non-stoquastic Hamiltonians, i.e., transforming them into sign-problem-free ones. We prove that if such transformations are limited to single-qubit Clifford group elements or general single-qubit orthogonal matrices, finding the curing transformation is NP-complete. We discuss the implications of this result.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1038/s41467-019-09501-6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1043282", 
            "issn": [
              "2041-1723"
            ], 
            "name": "Nature Communications", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "10"
          }
        ], 
        "name": "On the computational complexity of curing non-stoquastic Hamiltonians.", 
        "pagination": "1571", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1038/s41467-019-09501-6"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1113261499"
            ]
          }, 
          {
            "name": "nlm_unique_id", 
            "type": "PropertyValue", 
            "value": [
              "101528555"
            ]
          }, 
          {
            "name": "pubmed_id", 
            "type": "PropertyValue", 
            "value": [
              "30952854"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1038/s41467-019-09501-6", 
          "https://app.dimensions.ai/details/publication/pub.1113261499"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-16T06:25", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000377_0000000377/records_106840_00000003.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://www.nature.com/articles/s41467-019-09501-6"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1038/s41467-019-09501-6'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1038/s41467-019-09501-6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1038/s41467-019-09501-6'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1038/s41467-019-09501-6'


     

    This table displays all metadata directly associated to this object as RDF triples.

    125 TRIPLES      21 PREDICATES      42 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1038/s41467-019-09501-6 schema:about anzsrc-for:01
    2 anzsrc-for:0105
    3 schema:author Na5ef78205f6a487f9af2d45f5a3c9c70
    4 schema:citation sg:pub.10.1007/978-1-4684-2001-2_9
    5 https://doi.org/10.1016/0166-218x(84)90081-7
    6 https://doi.org/10.1017/cbo9780511614460
    7 https://doi.org/10.1063/1.4936216
    8 https://doi.org/10.1088/0305-4470/15/10/028
    9 https://doi.org/10.1103/physreva.92.042325
    10 https://doi.org/10.1103/physrevb.41.9301
    11 https://doi.org/10.1103/physrevb.89.134422
    12 https://doi.org/10.1103/physrevb.93.054408
    13 https://doi.org/10.1103/physreve.97.043303
    14 https://doi.org/10.1103/physrevlett.117.197203
    15 https://doi.org/10.1103/physrevlett.94.170201
    16 https://doi.org/10.1137/08072689x
    17 https://doi.org/10.1137/140998287
    18 schema:datePublished 2019-12
    19 schema:datePublishedReg 2019-12-01
    20 schema:description Quantum many-body systems whose Hamiltonians are non-stoquastic, i.e., have positive off-diagonal matrix elements in a given basis, are known to pose severe limitations on the efficiency of Quantum Monte Carlo algorithms designed to simulate them, due to the infamous sign problem. We study the computational complexity associated with 'curing' non-stoquastic Hamiltonians, i.e., transforming them into sign-problem-free ones. We prove that if such transformations are limited to single-qubit Clifford group elements or general single-qubit orthogonal matrices, finding the curing transformation is NP-complete. We discuss the implications of this result.
    21 schema:genre research_article
    22 schema:inLanguage en
    23 schema:isAccessibleForFree true
    24 schema:isPartOf N0fc79af255444c0385fc974119e8afc7
    25 N3a4899d444a24bd8b72a15a9a10d3378
    26 sg:journal.1043282
    27 schema:name On the computational complexity of curing non-stoquastic Hamiltonians.
    28 schema:pagination 1571
    29 schema:productId N1c306afcad264360a71176f09430cd91
    30 N201ef1c4032a4190a5b18a1e3e470ace
    31 N22f2f9dd3d7f48e0914a005730421f6d
    32 N84a942e8244243b1a674bb09b3ac4181
    33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1113261499
    34 https://doi.org/10.1038/s41467-019-09501-6
    35 schema:sdDatePublished 2019-04-16T06:25
    36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    37 schema:sdPublisher Nde66da3e48d54f359e92140632b28232
    38 schema:url http://www.nature.com/articles/s41467-019-09501-6
    39 sgo:license sg:explorer/license/
    40 sgo:sdDataset articles
    41 rdf:type schema:ScholarlyArticle
    42 N0fc79af255444c0385fc974119e8afc7 schema:issueNumber 1
    43 rdf:type schema:PublicationIssue
    44 N17bb5111c4d14054858da46521b58f38 schema:affiliation https://www.grid.ac/institutes/grid.42505.36
    45 schema:familyName Lidar
    46 schema:givenName Daniel A
    47 rdf:type schema:Person
    48 N1c306afcad264360a71176f09430cd91 schema:name doi
    49 schema:value 10.1038/s41467-019-09501-6
    50 rdf:type schema:PropertyValue
    51 N201ef1c4032a4190a5b18a1e3e470ace schema:name nlm_unique_id
    52 schema:value 101528555
    53 rdf:type schema:PropertyValue
    54 N22f2f9dd3d7f48e0914a005730421f6d schema:name pubmed_id
    55 schema:value 30952854
    56 rdf:type schema:PropertyValue
    57 N25eb020380114d7f8a511e593e4123b1 rdf:first N6cf7372a6ecd46a0a273b98d504a35ac
    58 rdf:rest rdf:nil
    59 N3a4899d444a24bd8b72a15a9a10d3378 schema:volumeNumber 10
    60 rdf:type schema:PublicationVolume
    61 N576c4edf57cb48b39c435a24d9109703 schema:affiliation https://www.grid.ac/institutes/grid.42505.36
    62 schema:familyName Marvian
    63 schema:givenName Milad
    64 rdf:type schema:Person
    65 N6cf7372a6ecd46a0a273b98d504a35ac schema:affiliation https://www.grid.ac/institutes/grid.42505.36
    66 schema:familyName Hen
    67 schema:givenName Itay
    68 rdf:type schema:Person
    69 N726b80ab15854cdf9c933e1ef76c8f69 rdf:first N17bb5111c4d14054858da46521b58f38
    70 rdf:rest N25eb020380114d7f8a511e593e4123b1
    71 N84a942e8244243b1a674bb09b3ac4181 schema:name dimensions_id
    72 schema:value pub.1113261499
    73 rdf:type schema:PropertyValue
    74 Na5ef78205f6a487f9af2d45f5a3c9c70 rdf:first N576c4edf57cb48b39c435a24d9109703
    75 rdf:rest N726b80ab15854cdf9c933e1ef76c8f69
    76 Nde66da3e48d54f359e92140632b28232 schema:name Springer Nature - SN SciGraph project
    77 rdf:type schema:Organization
    78 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Mathematical Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0105 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Mathematical Physics
    83 rdf:type schema:DefinedTerm
    84 sg:journal.1043282 schema:issn 2041-1723
    85 schema:name Nature Communications
    86 rdf:type schema:Periodical
    87 sg:pub.10.1007/978-1-4684-2001-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007977430
    88 https://doi.org/10.1007/978-1-4684-2001-2_9
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1016/0166-218x(84)90081-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050792184
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1017/cbo9780511614460 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098707127
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1063/1.4936216 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017840462
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1088/0305-4470/15/10/028 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059065892
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1103/physreva.92.042325 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002022619
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1103/physrevb.41.9301 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060554544
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1103/physrevb.89.134422 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010503988
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1103/physrevb.93.054408 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060648868
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1103/physreve.97.043303 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103993061
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1103/physrevlett.117.197203 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060766672
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1103/physrevlett.94.170201 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005409869
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1137/08072689x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062854854
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1137/140998287 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062873087
    115 rdf:type schema:CreativeWork
    116 https://www.grid.ac/institutes/grid.42505.36 schema:alternateName University of Southern California
    117 schema:name Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, CA, 90089, USA.
    118 Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, CA, 90089, USA. mmarvian@mit.edu.
    119 Department of Chemistry, University of Southern California, Los Angeles, CA, 90089, USA.
    120 Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, CA, 90089, USA.
    121 Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, CA, 90089, USA. mmarvian@mit.edu.
    122 Department of Physics and Astronomy, University of Southern California, Los Angeles, CA, 90089, USA.
    123 Information Sciences Institute, University of Southern California, Marina del Rey, CA, 90292, USA.
    124 Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA. mmarvian@mit.edu.
    125 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...