{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T20:37:39Z","timestamp":1778099859806,"version":"3.51.4"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["450041824"],"award-info":[{"award-number":["450041824"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["432788384"],"award-info":[{"award-number":["432788384"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP19H04066"],"award-info":[{"award-number":["JP19H04066"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H05966"],"award-info":[{"award-number":["JP20H05966"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H00579"],"award-info":[{"award-number":["JP20H00579"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H04139"],"award-info":[{"award-number":["JP20H04139"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP21H04879"],"award-info":[{"award-number":["JP21H04879"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JPMXS0118067394"],"award-info":[{"award-number":["JPMXS0118067394"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JPMXS0120319794"],"award-info":[{"award-number":["JPMXS0120319794"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2023,8,31]]},"DOI":"10.1137\/22m1513721","type":"journal-article","created":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T08:01:17Z","timestamp":1691654477000},"page":"1009-1038","source":"Crossref","is-referenced-by-count":9,"title":["Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture"],"prefix":"10.1137","volume":"52","author":[{"given":"Sevag","family":"Gharibian","sequence":"first","affiliation":[{"name":"Paderborn University, Paderborn 33098, Germany."}]},{"given":"Fran\u00e7ois","family":"Le Gall","sequence":"additional","affiliation":[{"name":"Nagoya University, Nagoya 464-8601, Japan."}]}],"member":"351","published-online":{"date-parts":[[2023,8,10]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1415"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.83.5162"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1145\/2491533.2491549"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1666-5"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1126\/science.1113479"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1021\/acs.chemrev.9b00829"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-018-0318-2"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"ref16","first-page":"1122","volume":"15","author":"Bravyi S.","year":"2015","journal-title":"Quantum Inf. Comput."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1006\/aphy.2002.6254"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1038\/s42254-021-00348-9"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.104.035118"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1080\/00268970701757875"},{"key":"ref26","first-page":"144","volume":"14","author":"Freedman M. H.","year":"2014","journal-title":"Quantum Inf. Comput."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039494"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1561\/0400000066"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1137\/110842272"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-09-30-189"},{"key":"ref37","first-page":"4","volume":"2016","author":"Grilo A. B.","year":"2016","journal-title":"Chicago J. Theor. Comput."},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevApplied.12.064041"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1007\/BF01331938"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/047"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.2.030305"},{"key":"ref47","first-page":"265","volume":"9","author":"Levin L.","year":"1973","journal-title":"Probl. Inf. Transm."},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-11-11-361"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1126\/science.273.5278.1073"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-07-12-163"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1137\/090745854"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1021\/jz501649m"},{"key":"ref56","first-page":"20150301","volume":"471","author":"Montanaro A.","year":"2015","journal-title":"Proc. R. Soc. A Math. Phys. Eng. Sci."},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1088\/0034-4885\/75\/2\/022001"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1619152114"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-02-20-234"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1370"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevResearch.1.033033"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.99.022308"},{"key":"ref66","first-page":"784","volume":"11","author":"Van Den Nest M.","year":"2011","journal-title":"Quantum Inf. Comput."},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2005\/09\/P09012"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.94.030301"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1039\/C2CP42695A"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T18:16:33Z","timestamp":1693505793000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1513721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,10]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8,31]]}},"alternative-id":["10.1137\/22M1513721"],"URL":"https:\/\/doi.org\/10.1137\/22m1513721","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,10]]}}}