{"data":{"id":"10.48550/arxiv.1712.02806","type":"dois","attributes":{"doi":"10.48550/arxiv.1712.02806","prefix":"10.48550","suffix":"arxiv.1712.02806","identifiers":[{"identifier":"1712.02806","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1712.02806"}],"creators":[{"name":"Pashayan, Hakop","nameType":"Personal","givenName":"Hakop","familyName":"Pashayan","affiliation":[],"nameIdentifiers":[]},{"name":"Bartlett, Stephen D.","nameType":"Personal","givenName":"Stephen D.","familyName":"Bartlett","affiliation":[],"nameIdentifiers":[]},{"name":"Gross, David","nameType":"Personal","givenName":"David","familyName":"Gross","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"From estimation of quantum probabilities to simulation of quantum circuits"}],"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-12-07T19:00:36Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2017-12-11T01:00:29Z","dateType":"Updated","dateInformation":"v1"},{"date":"2018-06-22T05:18:55Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2018-06-25T00:04:06Z","dateType":"Updated","dateInformation":"v2"},{"date":"2020-01-07T23:37:43Z","dateType":"Submitted","dateInformation":"v3"},{"date":"2020-01-15T14:40:53Z","dateType":"Updated","dateInformation":"v3"},{"date":"2017-12","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-2020-01-13-223","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"3","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":"Investigating the classical simulability of quantum circuits provides a promising avenue towards understanding the computational power of quantum systems. Whether a class of quantum circuits can be efficiently simulated with a probabilistic classical computer, or is provably hard to simulate, depends quite critically on the precise notion of \"classical simulation\" and in particular on the required accuracy. We argue that a notion of classical simulation, which we call epsilon-simulation, captures the essence of possessing \"equivalent computational power\" as the quantum system it simulates: It is statistically impossible to distinguish an agent with access to an epsilon-simulator from one possessing the simulated quantum system. We relate epsilon-simulation to various alternative notions of simulation predominantly focusing on a simulator we call a poly-box. A poly-box outputs 1/poly precision additive estimates of Born probabilities and marginals. This notion of simulation has gained prominence through a number of recent simulability results. Accepting some plausible computational theoretic assumptions, we show that epsilon-simulation is strictly stronger than a poly-box by showing that IQP circuits and unconditioned magic-state injected Clifford circuits are both hard to epsilon-simulate and yet admit a poly-box. In contrast, we also show that these two notions are equivalent under an additional assumption on the sparsity of the output distribution (poly-sparsity).","descriptionType":"Abstract"},{"description":"29 pages + appendix, 3 figures, comments welcome; v2 various improvements; v3 final version accepted to Quantum","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xNzEyLjAyODA2PC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+MTcxMi4wMjgwNjwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5QYXNoYXlhbiwgSGFrb3A8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPkhha29wPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPlBhc2hheWFuPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkJhcnRsZXR0LCBTdGVwaGVuIEQuPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5TdGVwaGVuIEQuPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkJhcnRsZXR0PC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkdyb3NzLCBEYXZpZDwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+RGF2aWQ8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+R3Jvc3M8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgPC9jcmVhdG9ycz4KICA8dGl0bGVzPgogICAgPHRpdGxlPkZyb20gZXN0aW1hdGlvbiBvZiBxdWFudHVtIHByb2JhYmlsaXRpZXMgdG8gc2ltdWxhdGlvbiBvZiBxdWFudHVtIGNpcmN1aXRzPC90aXRsZT4KICA8L3RpdGxlcz4KICA8cHVibGlzaGVyPmFyWGl2PC9wdWJsaXNoZXI+CiAgPHB1YmxpY2F0aW9uWWVhcj4yMDE3PC9wdWJsaWNhdGlvblllYXI+CiAgPHN1YmplY3RzPgogICAgPHN1YmplY3QgeG1sOmxhbmc9ImVuIiBzdWJqZWN0U2NoZW1lPSJhclhpdiI+UXVhbnR1bSBQaHlzaWNzIChxdWFudC1waCk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCBzdWJqZWN0U2NoZW1lPSJGaWVsZHMgb2YgU2NpZW5jZSBhbmQgVGVjaG5vbG9neSAoRk9TKSI+Rk9TOiBQaHlzaWNhbCBzY2llbmNlczwvc3ViamVjdD4KICA8L3N1YmplY3RzPgogIDxkYXRlcz4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTctMTItMDdUMTk6MDA6MzZaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTctMTItMTFUMDE6MDA6MjlaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MiI+MjAxOC0wNi0yMlQwNToxODo1NVo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MiI+MjAxOC0wNi0yNVQwMDowNDowNlo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYzIj4yMDIwLTAxLTA3VDIzOjM3OjQzWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYzIj4yMDIwLTAxLTE1VDE0OjQwOjUzWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTctMTI8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlRleHQiPkFydGljbGU8L3Jlc291cmNlVHlwZT4KICA8cmVsYXRlZElkZW50aWZpZXJzPgogICAgPHJlbGF0ZWRJZGVudGlmaWVyIHJlbGF0ZWRJZGVudGlmaWVyVHlwZT0iRE9JIiByZWxhdGlvblR5cGU9IklzVmVyc2lvbk9mIj4xMC4yMjMzMS9xLTIwMjAtMDEtMTMtMjIzPC9yZWxhdGVkSWRlbnRpZmllcj4KICA8L3JlbGF0ZWRJZGVudGlmaWVycz4KICA8dmVyc2lvbj4zPC92ZXJzaW9uPgogIDxyaWdodHNMaXN0PgogICAgPHJpZ2h0cyByaWdodHNVUkk9Imh0dHA6Ly9jcmVhdGl2ZWNvbW1vbnMub3JnL2xpY2Vuc2VzL2J5LzQuMC8iIHJpZ2h0c0lkZW50aWZpZXJTY2hlbWU9IlNQRFgiIHJpZ2h0c0lkZW50aWZpZXI9IkNDLUJZLTQuMCI+Q3JlYXRpdmUgQ29tbW9ucyBBdHRyaWJ1dGlvbiA0LjAgSW50ZXJuYXRpb25hbDwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPkludmVzdGlnYXRpbmcgdGhlIGNsYXNzaWNhbCBzaW11bGFiaWxpdHkgb2YgcXVhbnR1bSBjaXJjdWl0cyBwcm92aWRlcyBhIHByb21pc2luZyBhdmVudWUgdG93YXJkcyB1bmRlcnN0YW5kaW5nIHRoZSBjb21wdXRhdGlvbmFsIHBvd2VyIG9mIHF1YW50dW0gc3lzdGVtcy4gV2hldGhlciBhIGNsYXNzIG9mIHF1YW50dW0gY2lyY3VpdHMgY2FuIGJlIGVmZmljaWVudGx5IHNpbXVsYXRlZCB3aXRoIGEgcHJvYmFiaWxpc3RpYyBjbGFzc2ljYWwgY29tcHV0ZXIsIG9yIGlzIHByb3ZhYmx5IGhhcmQgdG8gc2ltdWxhdGUsIGRlcGVuZHMgcXVpdGUgY3JpdGljYWxseSBvbiB0aGUgcHJlY2lzZSBub3Rpb24gb2YgImNsYXNzaWNhbCBzaW11bGF0aW9uIiBhbmQgaW4gcGFydGljdWxhciBvbiB0aGUgcmVxdWlyZWQgYWNjdXJhY3kuIFdlIGFyZ3VlIHRoYXQgYSBub3Rpb24gb2YgY2xhc3NpY2FsIHNpbXVsYXRpb24sIHdoaWNoIHdlIGNhbGwgZXBzaWxvbi1zaW11bGF0aW9uLCBjYXB0dXJlcyB0aGUgZXNzZW5jZSBvZiBwb3NzZXNzaW5nICJlcXVpdmFsZW50IGNvbXB1dGF0aW9uYWwgcG93ZXIiIGFzIHRoZSBxdWFudHVtIHN5c3RlbSBpdCBzaW11bGF0ZXM6IEl0IGlzIHN0YXRpc3RpY2FsbHkgaW1wb3NzaWJsZSB0byBkaXN0aW5ndWlzaCBhbiBhZ2VudCB3aXRoIGFjY2VzcyB0byBhbiBlcHNpbG9uLXNpbXVsYXRvciBmcm9tIG9uZSBwb3NzZXNzaW5nIHRoZSBzaW11bGF0ZWQgcXVhbnR1bSBzeXN0ZW0uIFdlIHJlbGF0ZSBlcHNpbG9uLXNpbXVsYXRpb24gdG8gdmFyaW91cyBhbHRlcm5hdGl2ZSBub3Rpb25zIG9mIHNpbXVsYXRpb24gcHJlZG9taW5hbnRseSBmb2N1c2luZyBvbiBhIHNpbXVsYXRvciB3ZSBjYWxsIGEgcG9seS1ib3guIEEgcG9seS1ib3ggb3V0cHV0cyAxL3BvbHkgcHJlY2lzaW9uIGFkZGl0aXZlIGVzdGltYXRlcyBvZiBCb3JuIHByb2JhYmlsaXRpZXMgYW5kIG1hcmdpbmFscy4gVGhpcyBub3Rpb24gb2Ygc2ltdWxhdGlvbiBoYXMgZ2FpbmVkIHByb21pbmVuY2UgdGhyb3VnaCBhIG51bWJlciBvZiByZWNlbnQgc2ltdWxhYmlsaXR5IHJlc3VsdHMuIEFjY2VwdGluZyBzb21lIHBsYXVzaWJsZSBjb21wdXRhdGlvbmFsIHRoZW9yZXRpYyBhc3N1bXB0aW9ucywgd2Ugc2hvdyB0aGF0IGVwc2lsb24tc2ltdWxhdGlvbiBpcyBzdHJpY3RseSBzdHJvbmdlciB0aGFuIGEgcG9seS1ib3ggYnkgc2hvd2luZyB0aGF0IElRUCBjaXJjdWl0cyBhbmQgdW5jb25kaXRpb25lZCBtYWdpYy1zdGF0ZSBpbmplY3RlZCBDbGlmZm9yZCBjaXJjdWl0cyBhcmUgYm90aCBoYXJkIHRvIGVwc2lsb24tc2ltdWxhdGUgYW5kIHlldCBhZG1pdCBhIHBvbHktYm94LiBJbiBjb250cmFzdCwgd2UgYWxzbyBzaG93IHRoYXQgdGhlc2UgdHdvIG5vdGlvbnMgYXJlIGVxdWl2YWxlbnQgdW5kZXIgYW4gYWRkaXRpb25hbCBhc3N1bXB0aW9uIG9uIHRoZSBzcGFyc2l0eSBvZiB0aGUgb3V0cHV0IGRpc3RyaWJ1dGlvbiAocG9seS1zcGFyc2l0eSkuPC9kZXNjcmlwdGlvbj4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9Ik90aGVyIj4yOSBwYWdlcyArIGFwcGVuZGl4LCAzIGZpZ3VyZXMsIGNvbW1lbnRzIHdlbGNvbWU7IHYyIHZhcmlvdXMgaW1wcm92ZW1lbnRzOyB2MyBmaW5hbCB2ZXJzaW9uIGFjY2VwdGVkIHRvIFF1YW50dW08L2Rlc2NyaXB0aW9uPgogIDwvZGVzY3JpcHRpb25zPgo8L3Jlc291cmNlPg==","url":"https://arxiv.org/abs/1712.02806","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-03T13:47:17.000Z","registered":"2022-03-03T13:47:18.000Z","published":"2017","updated":"2022-03-03T13:47:18.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1712.02806","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}