{"data":{"id":"10.48550/arxiv.0811.3171","type":"dois","attributes":{"doi":"10.48550/arxiv.0811.3171","prefix":"10.48550","suffix":"arxiv.0811.3171","identifiers":[{"identifier":"0811.3171","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"0811.3171"}],"creators":[{"name":"Harrow, Aram W.","nameType":"Personal","givenName":"Aram W.","familyName":"Harrow","affiliation":[],"nameIdentifiers":[]},{"name":"Hassidim, Avinatan","nameType":"Personal","givenName":"Avinatan","familyName":"Hassidim","affiliation":[],"nameIdentifiers":[]},{"name":"Lloyd, Seth","nameType":"Personal","givenName":"Seth","familyName":"Lloyd","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Quantum algorithm for solving linear systems of equations"}],"publisher":"arXiv","container":{},"publicationYear":2008,"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":"2008-11-19T20:36:41Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2009-12-01T11:32:24Z","dateType":"Updated","dateInformation":"v1"},{"date":"2009-02-03T16:43:33Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2009-12-01T11:32:24Z","dateType":"Updated","dateInformation":"v2"},{"date":"2009-09-30T15:24:42Z","dateType":"Submitted","dateInformation":"v3"},{"date":"2009-12-01T11:32:24Z","dateType":"Updated","dateInformation":"v3"},{"date":"2008-11","dateType":"Available","dateInformation":"v1"},{"date":"2008","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[{"relationType":"IsVersionOf","relatedIdentifier":"10.1103/physrevlett.103.150502","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"3","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and a vector b, find a vector x such that Ax=b. We consider the case where one doesn't need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x, e.g., x'Mx for some matrix M. In this case, when A is sparse, N by N and has condition number kappa, classical algorithms can find x and estimate x'Mx in O(N sqrt(kappa)) time. Here, we exhibit a quantum algorithm for this task that runs in poly(log N, kappa) time, an exponential improvement over the best classical algorithm.","descriptionType":"Abstract"},{"description":"15 pages. v2 is much longer, with errors fixed, run-time improved and a new BQP-completeness result added. v3 is the final published version and mostly adds clarifications and corrections to v2","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4wODExLjMxNzE8L2lkZW50aWZpZXI+CiAgPGFsdGVybmF0ZUlkZW50aWZpZXJzPgogICAgPGFsdGVybmF0ZUlkZW50aWZpZXIgYWx0ZXJuYXRlSWRlbnRpZmllclR5cGU9ImFyWGl2Ij4wODExLjMxNzE8L2FsdGVybmF0ZUlkZW50aWZpZXI+CiAgPC9hbHRlcm5hdGVJZGVudGlmaWVycz4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+SGFycm93LCBBcmFtIFcuPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5BcmFtIFcuPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkhhcnJvdzwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5IYXNzaWRpbSwgQXZpbmF0YW48L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPkF2aW5hdGFuPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkhhc3NpZGltPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkxsb3lkLCBTZXRoPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5TZXRoPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkxsb3lkPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogIDwvY3JlYXRvcnM+CiAgPHRpdGxlcz4KICAgIDx0aXRsZT5RdWFudHVtIGFsZ29yaXRobSBmb3Igc29sdmluZyBsaW5lYXIgc3lzdGVtcyBvZiBlcXVhdGlvbnM8L3RpdGxlPgogIDwvdGl0bGVzPgogIDxwdWJsaXNoZXI+YXJYaXY8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMDg8L3B1YmxpY2F0aW9uWWVhcj4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5RdWFudHVtIFBoeXNpY3MgKHF1YW50LXBoKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IFBoeXNpY2FsIHNjaWVuY2VzPC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAwOC0xMS0xOVQyMDozNjo0MVo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAwOS0xMi0wMVQxMTozMjoyNFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDA5LTAyLTAzVDE2OjQzOjMzWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDA5LTEyLTAxVDExOjMyOjI0WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjMiPjIwMDktMDktMzBUMTU6MjQ6NDJaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjMiPjIwMDktMTItMDFUMTE6MzI6MjRaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IkF2YWlsYWJsZSIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAwOC0xMTwvZGF0ZT4KICA8L2RhdGVzPgogIDxyZXNvdXJjZVR5cGUgcmVzb3VyY2VUeXBlR2VuZXJhbD0iVGV4dCI+QXJ0aWNsZTwvcmVzb3VyY2VUeXBlPgogIDxyZWxhdGVkSWRlbnRpZmllcnM+CiAgICA8cmVsYXRlZElkZW50aWZpZXIgcmVsYXRlZElkZW50aWZpZXJUeXBlPSJET0kiIHJlbGF0aW9uVHlwZT0iSXNWZXJzaW9uT2YiPjEwLjExMDMvUGh5c1JldkxldHQuMTAzLjE1MDUwMjwvcmVsYXRlZElkZW50aWZpZXI+CiAgPC9yZWxhdGVkSWRlbnRpZmllcnM+CiAgPHZlcnNpb24+MzwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vYXJ4aXYub3JnL2xpY2Vuc2VzL25vbmV4Y2x1c2l2ZS1kaXN0cmliLzEuMC8iPmFyWGl2Lm9yZyBwZXJwZXR1YWwsIG5vbi1leGNsdXNpdmUgbGljZW5zZTwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPlNvbHZpbmcgbGluZWFyIHN5c3RlbXMgb2YgZXF1YXRpb25zIGlzIGEgY29tbW9uIHByb2JsZW0gdGhhdCBhcmlzZXMgYm90aCBvbiBpdHMgb3duIGFuZCBhcyBhIHN1YnJvdXRpbmUgaW4gbW9yZSBjb21wbGV4IHByb2JsZW1zOiBnaXZlbiBhIG1hdHJpeCBBIGFuZCBhIHZlY3RvciBiLCBmaW5kIGEgdmVjdG9yIHggc3VjaCB0aGF0IEF4PWIuIFdlIGNvbnNpZGVyIHRoZSBjYXNlIHdoZXJlIG9uZSBkb2Vzbid0IG5lZWQgdG8ga25vdyB0aGUgc29sdXRpb24geCBpdHNlbGYsIGJ1dCByYXRoZXIgYW4gYXBwcm94aW1hdGlvbiBvZiB0aGUgZXhwZWN0YXRpb24gdmFsdWUgb2Ygc29tZSBvcGVyYXRvciBhc3NvY2lhdGVkIHdpdGggeCwgZS5nLiwgeCdNeCBmb3Igc29tZSBtYXRyaXggTS4gSW4gdGhpcyBjYXNlLCB3aGVuIEEgaXMgc3BhcnNlLCBOIGJ5IE4gYW5kIGhhcyBjb25kaXRpb24gbnVtYmVyIGthcHBhLCBjbGFzc2ljYWwgYWxnb3JpdGhtcyBjYW4gZmluZCB4IGFuZCBlc3RpbWF0ZSB4J014IGluIE8oTiBzcXJ0KGthcHBhKSkgdGltZS4gSGVyZSwgd2UgZXhoaWJpdCBhIHF1YW50dW0gYWxnb3JpdGhtIGZvciB0aGlzIHRhc2sgdGhhdCBydW5zIGluIHBvbHkobG9nIE4sIGthcHBhKSB0aW1lLCBhbiBleHBvbmVudGlhbCBpbXByb3ZlbWVudCBvdmVyIHRoZSBiZXN0IGNsYXNzaWNhbCBhbGdvcml0aG0uPC9kZXNjcmlwdGlvbj4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9Ik90aGVyIj4xNSBwYWdlcy4gdjIgaXMgbXVjaCBsb25nZXIsIHdpdGggZXJyb3JzIGZpeGVkLCBydW4tdGltZSBpbXByb3ZlZCBhbmQgYSBuZXcgQlFQLWNvbXBsZXRlbmVzcyByZXN1bHQgYWRkZWQuIHYzIGlzIHRoZSBmaW5hbCBwdWJsaXNoZWQgdmVyc2lvbiBhbmQgbW9zdGx5IGFkZHMgY2xhcmlmaWNhdGlvbnMgYW5kIGNvcnJlY3Rpb25zIHRvIHYyPC9kZXNjcmlwdGlvbj4KICA8L2Rlc2NyaXB0aW9ucz4KPC9yZXNvdXJjZT4=","url":"https://arxiv.org/abs/0811.3171","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-03-15T13:09:09.000Z","registered":"2022-03-15T13:09:10.000Z","published":"2008","updated":"2022-03-15T13:09:10.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.0811.3171","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}