{"data":{"id":"10.48550/arxiv.1703.00454","type":"dois","attributes":{"doi":"10.48550/arxiv.1703.00454","prefix":"10.48550","suffix":"arxiv.1703.00454","identifiers":[{"identifier":"1703.00454","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1703.00454"}],"creators":[{"name":"Jordan, Stephen P.","nameType":"Personal","givenName":"Stephen P.","familyName":"Jordan","affiliation":[],"nameIdentifiers":[]},{"name":"Krovi, Hari","nameType":"Personal","givenName":"Hari","familyName":"Krovi","affiliation":[],"nameIdentifiers":[]},{"name":"Lee, Keith S. M.","nameType":"Personal","givenName":"Keith S. M.","familyName":"Lee","affiliation":[],"nameIdentifiers":[]},{"name":"Preskill, John","nameType":"Personal","givenName":"John","familyName":"Preskill","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"BQP-completeness of Scattering in Scalar Quantum Field Theory"}],"publisher":"arXiv","container":{},"publicationYear":2017,"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":"2017-03-01T19:00:02Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2017-03-03T01:00:17Z","dateType":"Updated","dateInformation":"v1"},{"date":"2017-11-13T20:03:13Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2017-11-15T01:33:29Z","dateType":"Updated","dateInformation":"v2"},{"date":"2017-12-25T02:47:50Z","dateType":"Submitted","dateInformation":"v3"},{"date":"2017-12-27T01:08:56Z","dateType":"Updated","dateInformation":"v3"},{"date":"2018-01-04T16:19:26Z","dateType":"Submitted","dateInformation":"v4"},{"date":"2018-01-09T01:14:53Z","dateType":"Updated","dateInformation":"v4"},{"date":"2017-03","dateType":"Available","dateInformation":"v1"},{"date":"2017","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[{"relationType":"IsVersionOf","relatedIdentifier":"10.22331/q-2018-01-08-44","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"4","rightsList":[{"rights":"Creative Commons Attribution 4.0 International","rightsUri":"https://creativecommons.org/licenses/by/4.0/legalcode","schemeUri":"https://spdx.org/licenses/","rightsIdentifier":"cc-by-4.0","rightsIdentifierScheme":"SPDX"}],"descriptions":[{"description":"Recent work has shown that quantum computers can compute scattering probabilities in massive quantum field theories, with a run time that is polynomial in the number of particles, their energy, and the desired precision. Here we study a closely related quantum field-theoretical problem: estimating the vacuum-to-vacuum transition amplitude, in the presence of spacetime-dependent classical sources, for a massive scalar field theory in (1+1) dimensions. We show that this problem is BQP-hard; in other words, its solution enables one to solve any problem that is solvable in polynomial time by a quantum computer. Hence, the vacuum-to-vacuum amplitude cannot be accurately estimated by any efficient classical algorithm, even if the field theory is very weakly coupled, unless BQP=BPP. Furthermore, the corresponding decision problem can be solved by a quantum computer in a time scaling polynomially with the number of bits needed to specify the classical source fields, and this problem is therefore BQP-complete. Our construction can be regarded as an idealized architecture for a universal quantum computer in a laboratory system described by massive phi^4 theory coupled to classical spacetime-dependent sources.","descriptionType":"Abstract"},{"description":"41 pages, 7 figures. Corrected typo in footer","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xNzAzLjAwNDU0PC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+MTcwMy4wMDQ1NDwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5Kb3JkYW4sIFN0ZXBoZW4gUC48L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPlN0ZXBoZW4gUC48L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+Sm9yZGFuPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPktyb3ZpLCBIYXJpPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5IYXJpPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPktyb3ZpPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkxlZSwgS2VpdGggUy4gTS48L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPktlaXRoIFMuIE0uPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkxlZTwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5QcmVza2lsbCwgSm9objwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+Sm9objwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5QcmVza2lsbDwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+QlFQLWNvbXBsZXRlbmVzcyBvZiBTY2F0dGVyaW5nIGluIFNjYWxhciBRdWFudHVtIEZpZWxkIFRoZW9yeTwvdGl0bGU+CiAgPC90aXRsZXM+CiAgPHB1Ymxpc2hlcj5hclhpdjwvcHVibGlzaGVyPgogIDxwdWJsaWNhdGlvblllYXI+MjAxNzwvcHVibGljYXRpb25ZZWFyPgogIDxzdWJqZWN0cz4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPlF1YW50dW0gUGh5c2ljcyAocXVhbnQtcGgpPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc3ViamVjdFNjaGVtZT0iRmllbGRzIG9mIFNjaWVuY2UgYW5kIFRlY2hub2xvZ3kgKEZPUykiPkZPUzogUGh5c2ljYWwgc2NpZW5jZXM8L3N1YmplY3Q+CiAgPC9zdWJqZWN0cz4KICA8ZGF0ZXM+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDE3LTAzLTAxVDE5OjAwOjAyWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDE3LTAzLTAzVDAxOjAwOjE3WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjIiPjIwMTctMTEtMTNUMjA6MDM6MTNaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjIiPjIwMTctMTEtMTVUMDE6MzM6MjlaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MyI+MjAxNy0xMi0yNVQwMjo0Nzo1MFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MyI+MjAxNy0xMi0yN1QwMTowODo1Nlo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InY0Ij4yMDE4LTAxLTA0VDE2OjE5OjI2WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InY0Ij4yMDE4LTAxLTA5VDAxOjE0OjUzWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTctMDM8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlRleHQiPkFydGljbGU8L3Jlc291cmNlVHlwZT4KICA8cmVsYXRlZElkZW50aWZpZXJzPgogICAgPHJlbGF0ZWRJZGVudGlmaWVyIHJlbGF0ZWRJZGVudGlmaWVyVHlwZT0iRE9JIiByZWxhdGlvblR5cGU9IklzVmVyc2lvbk9mIj4xMC4yMjMzMS9xLTIwMTgtMDEtMDgtNDQ8L3JlbGF0ZWRJZGVudGlmaWVyPgogIDwvcmVsYXRlZElkZW50aWZpZXJzPgogIDx2ZXJzaW9uPjQ8L3ZlcnNpb24+CiAgPHJpZ2h0c0xpc3Q+CiAgICA8cmlnaHRzIHJpZ2h0c1VSST0iaHR0cDovL2NyZWF0aXZlY29tbW9ucy5vcmcvbGljZW5zZXMvYnkvNC4wLyIgcmlnaHRzSWRlbnRpZmllclNjaGVtZT0iU1BEWCIgcmlnaHRzSWRlbnRpZmllcj0iQ0MtQlktNC4wIj5DcmVhdGl2ZSBDb21tb25zIEF0dHJpYnV0aW9uIDQuMCBJbnRlcm5hdGlvbmFsPC9yaWdodHM+CiAgPC9yaWdodHNMaXN0PgogIDxkZXNjcmlwdGlvbnM+CiAgICA8ZGVzY3JpcHRpb24gZGVzY3JpcHRpb25UeXBlPSJBYnN0cmFjdCI+UmVjZW50IHdvcmsgaGFzIHNob3duIHRoYXQgcXVhbnR1bSBjb21wdXRlcnMgY2FuIGNvbXB1dGUgc2NhdHRlcmluZyBwcm9iYWJpbGl0aWVzIGluIG1hc3NpdmUgcXVhbnR1bSBmaWVsZCB0aGVvcmllcywgd2l0aCBhIHJ1biB0aW1lIHRoYXQgaXMgcG9seW5vbWlhbCBpbiB0aGUgbnVtYmVyIG9mIHBhcnRpY2xlcywgdGhlaXIgZW5lcmd5LCBhbmQgdGhlIGRlc2lyZWQgcHJlY2lzaW9uLiBIZXJlIHdlIHN0dWR5IGEgY2xvc2VseSByZWxhdGVkIHF1YW50dW0gZmllbGQtdGhlb3JldGljYWwgcHJvYmxlbTogZXN0aW1hdGluZyB0aGUgdmFjdXVtLXRvLXZhY3V1bSB0cmFuc2l0aW9uIGFtcGxpdHVkZSwgaW4gdGhlIHByZXNlbmNlIG9mIHNwYWNldGltZS1kZXBlbmRlbnQgY2xhc3NpY2FsIHNvdXJjZXMsIGZvciBhIG1hc3NpdmUgc2NhbGFyIGZpZWxkIHRoZW9yeSBpbiAoMSsxKSBkaW1lbnNpb25zLiBXZSBzaG93IHRoYXQgdGhpcyBwcm9ibGVtIGlzIEJRUC1oYXJkOyBpbiBvdGhlciB3b3JkcywgaXRzIHNvbHV0aW9uIGVuYWJsZXMgb25lIHRvIHNvbHZlIGFueSBwcm9ibGVtIHRoYXQgaXMgc29sdmFibGUgaW4gcG9seW5vbWlhbCB0aW1lIGJ5IGEgcXVhbnR1bSBjb21wdXRlci4gSGVuY2UsIHRoZSB2YWN1dW0tdG8tdmFjdXVtIGFtcGxpdHVkZSBjYW5ub3QgYmUgYWNjdXJhdGVseSBlc3RpbWF0ZWQgYnkgYW55IGVmZmljaWVudCBjbGFzc2ljYWwgYWxnb3JpdGhtLCBldmVuIGlmIHRoZSBmaWVsZCB0aGVvcnkgaXMgdmVyeSB3ZWFrbHkgY291cGxlZCwgdW5sZXNzIEJRUD1CUFAuIEZ1cnRoZXJtb3JlLCB0aGUgY29ycmVzcG9uZGluZyBkZWNpc2lvbiBwcm9ibGVtIGNhbiBiZSBzb2x2ZWQgYnkgYSBxdWFudHVtIGNvbXB1dGVyIGluIGEgdGltZSBzY2FsaW5nIHBvbHlub21pYWxseSB3aXRoIHRoZSBudW1iZXIgb2YgYml0cyBuZWVkZWQgdG8gc3BlY2lmeSB0aGUgY2xhc3NpY2FsIHNvdXJjZSBmaWVsZHMsIGFuZCB0aGlzIHByb2JsZW0gaXMgdGhlcmVmb3JlIEJRUC1jb21wbGV0ZS4gT3VyIGNvbnN0cnVjdGlvbiBjYW4gYmUgcmVnYXJkZWQgYXMgYW4gaWRlYWxpemVkIGFyY2hpdGVjdHVyZSBmb3IgYSB1bml2ZXJzYWwgcXVhbnR1bSBjb21wdXRlciBpbiBhIGxhYm9yYXRvcnkgc3lzdGVtIGRlc2NyaWJlZCBieSBtYXNzaXZlIHBoaV40IHRoZW9yeSBjb3VwbGVkIHRvIGNsYXNzaWNhbCBzcGFjZXRpbWUtZGVwZW5kZW50IHNvdXJjZXMuPC9kZXNjcmlwdGlvbj4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9Ik90aGVyIj40MSBwYWdlcywgNyBmaWd1cmVzLiBDb3JyZWN0ZWQgdHlwbyBpbiBmb290ZXI8L2Rlc2NyaXB0aW9uPgogIDwvZGVzY3JpcHRpb25zPgo8L3Jlc291cmNlPg==","url":"https://arxiv.org/abs/1703.00454","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-05T02:54:49.000Z","registered":"2022-03-05T02:54:49.000Z","published":"2017","updated":"2022-03-05T02:54:49.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1703.00454","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}