{"data":{"id":"10.48550/arxiv.1910.11842","type":"dois","attributes":{"doi":"10.48550/arxiv.1910.11842","prefix":"10.48550","suffix":"arxiv.1910.11842","identifiers":[{"identifier":"1910.11842","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1910.11842"}],"creators":[{"name":"Chowdhury, Anirban N.","nameType":"Personal","givenName":"Anirban N.","familyName":"Chowdhury","affiliation":[],"nameIdentifiers":[]},{"name":"Somma, Rolando D.","nameType":"Personal","givenName":"Rolando D.","familyName":"Somma","affiliation":[],"nameIdentifiers":[]},{"name":"Subasi, Yigit","nameType":"Personal","givenName":"Yigit","familyName":"Subasi","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Computing partition functions in the one clean qubit model"}],"publisher":"arXiv","container":{},"publicationYear":2019,"subjects":[{"lang":"en","subject":"Quantum Physics (quant-ph)","subjectScheme":"arXiv"},{"subject":"FOS: Physical sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Physical sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2019-10-25T16:57:18Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2019-10-28T00:19:34Z","dateType":"Updated","dateInformation":"v1"},{"date":"2020-09-25T17:20:47Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2021-03-24T13:34:48Z","dateType":"Updated","dateInformation":"v2"},{"date":"2019-10","dateType":"Available","dateInformation":"v1"},{"date":"2019","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[{"relationType":"IsVersionOf","relatedIdentifier":"10.1103/physreva.103.032422","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"2","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"We present a method to approximate partition functions of quantum systems using mixed-state quantum computation. For positive semi-definite Hamiltonians, our method has expected running-time that is almost linear in $(M/(ε_{\\rm rel}\\mathcal{Z} ))^2$, where $M$ is the dimension of the quantum system, $\\mathcal{Z}$ is the partition function, and $ε_{\\rm rel}$ is the relative precision. It is based on approximations of the exponential operator as linear combinations of certain operators related to block-encoding of Hamiltonians or Hamiltonian evolutions. The trace of each operator is estimated using a standard algorithm in the one clean qubit model. For large values of $\\mathcal{Z}$, our method may run faster than exact classical methods, whose complexities are polynomial in $M$. We also prove that a version of the partition function estimation problem within additive error is complete for the so-called DQC1 complexity class, suggesting that our method provides a super-polynomial speedup for certain parameter values. To attain a desired relative precision, we develop a classical procedure based on a sequence of approximations within predetermined additive errors that may be of independent interest.","descriptionType":"Abstract"},{"description":"15 pages, 2 figures","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xOTEwLjExODQyPC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+MTkxMC4xMTg0MjwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5DaG93ZGh1cnksIEFuaXJiYW4gTi48L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPkFuaXJiYW4gTi48L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+Q2hvd2RodXJ5PC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPlNvbW1hLCBSb2xhbmRvIEQuPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5Sb2xhbmRvIEQuPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPlNvbW1hPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPlN1YmFzaSwgWWlnaXQ8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPllpZ2l0PC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPlN1YmFzaTwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+Q29tcHV0aW5nIHBhcnRpdGlvbiBmdW5jdGlvbnMgaW4gdGhlIG9uZSBjbGVhbiBxdWJpdCBtb2RlbDwvdGl0bGU+CiAgPC90aXRsZXM+CiAgPHB1Ymxpc2hlcj5hclhpdjwvcHVibGlzaGVyPgogIDxwdWJsaWNhdGlvblllYXI+MjAxOTwvcHVibGljYXRpb25ZZWFyPgogIDxzdWJqZWN0cz4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPlF1YW50dW0gUGh5c2ljcyAocXVhbnQtcGgpPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc3ViamVjdFNjaGVtZT0iRmllbGRzIG9mIFNjaWVuY2UgYW5kIFRlY2hub2xvZ3kgKEZPUykiPkZPUzogUGh5c2ljYWwgc2NpZW5jZXM8L3N1YmplY3Q+CiAgPC9zdWJqZWN0cz4KICA8ZGF0ZXM+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDE5LTEwLTI1VDE2OjU3OjE4WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDE5LTEwLTI4VDAwOjE5OjM0WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjIiPjIwMjAtMDktMjVUMTc6MjA6NDdaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjIiPjIwMjEtMDMtMjRUMTM6MzQ6NDhaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IkF2YWlsYWJsZSIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxOS0xMDwvZGF0ZT4KICA8L2RhdGVzPgogIDxyZXNvdXJjZVR5cGUgcmVzb3VyY2VUeXBlR2VuZXJhbD0iVGV4dCI+QXJ0aWNsZTwvcmVzb3VyY2VUeXBlPgogIDxyZWxhdGVkSWRlbnRpZmllcnM+CiAgICA8cmVsYXRlZElkZW50aWZpZXIgcmVsYXRlZElkZW50aWZpZXJUeXBlPSJET0kiIHJlbGF0aW9uVHlwZT0iSXNWZXJzaW9uT2YiPjEwLjExMDMvUGh5c1JldkEuMTAzLjAzMjQyMjwvcmVsYXRlZElkZW50aWZpZXI+CiAgPC9yZWxhdGVkSWRlbnRpZmllcnM+CiAgPHZlcnNpb24+MjwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vYXJ4aXYub3JnL2xpY2Vuc2VzL25vbmV4Y2x1c2l2ZS1kaXN0cmliLzEuMC8iPmFyWGl2Lm9yZyBwZXJwZXR1YWwsIG5vbi1leGNsdXNpdmUgbGljZW5zZTwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPldlIHByZXNlbnQgYSBtZXRob2QgdG8gYXBwcm94aW1hdGUgcGFydGl0aW9uIGZ1bmN0aW9ucyBvZiBxdWFudHVtIHN5c3RlbXMgdXNpbmcgbWl4ZWQtc3RhdGUgcXVhbnR1bSBjb21wdXRhdGlvbi4gRm9yIHBvc2l0aXZlIHNlbWktZGVmaW5pdGUgSGFtaWx0b25pYW5zLCBvdXIgbWV0aG9kIGhhcyBleHBlY3RlZCBydW5uaW5nLXRpbWUgdGhhdCBpcyBhbG1vc3QgbGluZWFyIGluICQoTS8ozrVfe1xybSByZWx9XG1hdGhjYWx7Wn0gKSleMiQsIHdoZXJlICRNJCBpcyB0aGUgZGltZW5zaW9uIG9mIHRoZSBxdWFudHVtIHN5c3RlbSwgJFxtYXRoY2Fse1p9JCBpcyB0aGUgcGFydGl0aW9uIGZ1bmN0aW9uLCBhbmQgJM61X3tccm0gcmVsfSQgaXMgdGhlIHJlbGF0aXZlIHByZWNpc2lvbi4gSXQgaXMgYmFzZWQgb24gYXBwcm94aW1hdGlvbnMgb2YgdGhlIGV4cG9uZW50aWFsIG9wZXJhdG9yIGFzIGxpbmVhciBjb21iaW5hdGlvbnMgb2YgY2VydGFpbiBvcGVyYXRvcnMgcmVsYXRlZCB0byBibG9jay1lbmNvZGluZyBvZiBIYW1pbHRvbmlhbnMgb3IgSGFtaWx0b25pYW4gZXZvbHV0aW9ucy4gVGhlIHRyYWNlIG9mIGVhY2ggb3BlcmF0b3IgaXMgZXN0aW1hdGVkIHVzaW5nIGEgc3RhbmRhcmQgYWxnb3JpdGhtIGluIHRoZSBvbmUgY2xlYW4gcXViaXQgbW9kZWwuIEZvciBsYXJnZSB2YWx1ZXMgb2YgJFxtYXRoY2Fse1p9JCwgb3VyIG1ldGhvZCBtYXkgcnVuIGZhc3RlciB0aGFuIGV4YWN0IGNsYXNzaWNhbCBtZXRob2RzLCB3aG9zZSBjb21wbGV4aXRpZXMgYXJlIHBvbHlub21pYWwgaW4gJE0kLiBXZSBhbHNvIHByb3ZlIHRoYXQgYSB2ZXJzaW9uIG9mIHRoZSBwYXJ0aXRpb24gZnVuY3Rpb24gZXN0aW1hdGlvbiBwcm9ibGVtIHdpdGhpbiBhZGRpdGl2ZSBlcnJvciBpcyBjb21wbGV0ZSBmb3IgdGhlIHNvLWNhbGxlZCBEUUMxIGNvbXBsZXhpdHkgY2xhc3MsIHN1Z2dlc3RpbmcgdGhhdCBvdXIgbWV0aG9kIHByb3ZpZGVzIGEgc3VwZXItcG9seW5vbWlhbCBzcGVlZHVwIGZvciBjZXJ0YWluIHBhcmFtZXRlciB2YWx1ZXMuIFRvIGF0dGFpbiBhIGRlc2lyZWQgcmVsYXRpdmUgcHJlY2lzaW9uLCB3ZSBkZXZlbG9wIGEgY2xhc3NpY2FsIHByb2NlZHVyZSBiYXNlZCBvbiBhIHNlcXVlbmNlIG9mIGFwcHJveGltYXRpb25zIHdpdGhpbiBwcmVkZXRlcm1pbmVkIGFkZGl0aXZlIGVycm9ycyB0aGF0IG1heSBiZSBvZiBpbmRlcGVuZGVudCBpbnRlcmVzdC48L2Rlc2NyaXB0aW9uPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iT3RoZXIiPjE1IHBhZ2VzLCAyIGZpZ3VyZXM8L2Rlc2NyaXB0aW9uPgogIDwvZGVzY3JpcHRpb25zPgo8L3Jlc291cmNlPg==","url":"https://arxiv.org/abs/1910.11842","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-02-27T12:03:25.000Z","registered":"2022-02-27T12:03:26.000Z","published":"2019","updated":"2022-02-27T12:03:26.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1910.11842","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}