{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T07:01:41Z","timestamp":1768633301872,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3519991","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"19-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture"],"prefix":"10.1145","author":[{"given":"Sevag","family":"Gharibian","sequence":"first","affiliation":[{"name":"Paderborn University, Germany"}]},{"given":"Fran\u00e7ois","family":"Le Gall","sequence":"additional","affiliation":[{"name":"Nagoya University, Japan"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1415"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993682"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.83.5162"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491533.2491549"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780546"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.12"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1666-5"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1113479"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1021\/acs.chemrev.9b00829"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591854"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-018-0318-2"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/aphy.2002.6254"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1038\/s42254-021-00348-9"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.33"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384314"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2020.47"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the 3rd ACM Symposium on Theory of Computing (STOC","author":"Cook Stephen","year":"1972","unstructured":"Stephen Cook . 1972 . The complexity of theorem proving procedures . In Proceedings of the 3rd ACM Symposium on Theory of Computing (STOC 1972). 151\u2013158. Stephen Cook. 1972. The complexity of theorem proving procedures. In Proceedings of the 3rd ACM Symposium on Theory of Computing (STOC 1972). 151\u2013158."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.104.035118"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/00268970701757875"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.46"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC14.1-2-9"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039494"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000066"},{"key":"e_1_3_2_1_25_1","unstructured":"Sevag Gharibian and Julia Kempe. 2012. Hardness of approximation for quantum problems. arXiv:quant-ph\/1209.1055  Sevag Gharibian and Julia Kempe. 2012. Hardness of approximation for quantum problems. arXiv:quant-ph\/1209.1055"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_33"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-09-30-189"},{"key":"e_1_3_2_1_28_1","unstructured":"Andr\u00e1s Gily\u00e9n Zhao Song and Ewin Tang. 2020. An improved quantum-inspired algorithm for linear regression. arXiv:2009.07268. arxiv:2009.07268 ArXiv:2009.07268  Andr\u00e1s Gily\u00e9n Zhao Song and Ewin Tang. 2020. An improved quantum-inspired algorithm for linear regression. arXiv:2009.07268. arxiv:2009.07268 ArXiv:2009.07268"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316366"},{"key":"e_1_3_2_1_30_1","volume-title":"Quantum proofs, the local Hamiltonian problem and applications. (Preuves quantiques, le probl\u00e8me des Hamiltoniens locaux et applications). Ph. D. Dissertation","author":"Grilo Alex Bredariol","unstructured":"Alex Bredariol Grilo . 2018. Quantum proofs, the local Hamiltonian problem and applications. (Preuves quantiques, le probl\u00e8me des Hamiltoniens locaux et applications). Ph. D. Dissertation . Sorbonne Paris Cit\u00e9, France . https:\/\/tel.archives-ouvertes.fr\/tel-02152364 Alex Bredariol Grilo. 2018. Quantum proofs, the local Hamiltonian problem and applications. (Preuves quantiques, le probl\u00e8me des Hamiltoniens locaux et applications). Ph. D. Dissertation. Sorbonne Paris Cit\u00e9, France. https:\/\/tel.archives-ouvertes.fr\/tel-02152364"},{"key":"e_1_3_2_1_31_1","first-page":"4","article-title":"QMA with Subset State Witnesses","volume":"2016","author":"Grilo Alex B.","year":"2016","unstructured":"Alex B. Grilo , Iordanis Kerenidis , and Jamie Sikora . 2016 . QMA with Subset State Witnesses . Chicago Journal of Theoretical Computer Science , 2016 (2016), 4 . http:\/\/cjtcs.cs.uchicago.edu\/articles\/2016\/4\/contents.html Alex B. Grilo, Iordanis Kerenidis, and Jamie Sikora. 2016. QMA with Subset State Witnesses. Chicago Journal of Theoretical Computer Science, 2016 (2016), 4. http:\/\/cjtcs.cs.uchicago.edu\/articles\/2016\/4\/contents.html","journal-title":"Chicago Journal of Theoretical Computer Science"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2020.53"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevApplied.12.064041"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01331938"},{"key":"e_1_3_2_1_38_1","unstructured":"Alexei Yu. Kitaev. 1995. Quantum measurements and the Abelian Stabilizer Problem. arXiv:quant-ph\/9511026  Alexei Yu. Kitaev. 1995. Quantum measurements and the Abelian Stabilizer Problem. arXiv:quant-ph\/9511026"},{"key":"e_1_3_2_1_39_1","volume-title":"Vyalyi","author":"Kitaev Alexei Yu.","year":"2002","unstructured":"Alexei Yu. Kitaev , Alexander H. Shen , and Mikhail N . Vyalyi . 2002 . Classical and Quantum Computation. American Mathematical Society . Alexei Yu. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi. 2002. Classical and Quantum Computation. American Mathematical Society."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.2.030305"},{"key":"e_1_3_2_1_41_1","first-page":"265","article-title":"Universal search problems","volume":"9","author":"Levin Leonid","year":"1973","unstructured":"Leonid Levin . 1973 . Universal search problems . Problems of Information Transmission , 9 , 3 (1973), 265 \u2013 266 . Leonid Levin. 1973. Universal search problems. Problems of Information Transmission, 9, 3 (1973), 265\u2013266.","journal-title":"Problems of Information Transmission"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-11-11-361"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.273.5278.1073"},{"key":"e_1_3_2_1_44_1","first-page":"05391","article-title":"Hamiltonian Simulation by Uniform Spectral Amplification. arxiv:1707.05391","volume":"1707","author":"Low Guang Hao","year":"2017","unstructured":"Guang Hao Low and Isaac L. Chuang . 2017 . Hamiltonian Simulation by Uniform Spectral Amplification. arxiv:1707.05391 . ArXiv : 1707 . 05391 Guang Hao Low and Isaac L. Chuang. 2017. Hamiltonian Simulation by Uniform Spectral Amplification. arxiv:1707.05391. ArXiv: 1707.05391","journal-title":"ArXiv"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-07-12-163"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/090745854"},{"key":"e_1_3_2_1_47_1","volume-title":"Chuang","author":"Martyn John M.","year":"2021","unstructured":"John M. Martyn , Zane M. Rossi , Andrew K. Tan , and Isaac L . Chuang . 2021 . A Grand Unification of Quantum Algorithms . arxiv:2105.02859. arXiv: 2105.02859 John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. 2021. A Grand Unification of Quantum Algorithms. arxiv:2105.02859. arXiv: 2105.02859"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1021\/jz501649m"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2015.0301"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1088\/0034-4885\/75\/2\/022001"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1619152114"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-02-20-234"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1370"},{"key":"e_1_3_2_1_54_1","unstructured":"Martin Schwarz and Maarten Van den Nest. 2013. Simulating quantum circuits with sparse output distributions. arxiv:1310.6749. arXiv: 1310.6749  Martin Schwarz and Maarten Van den Nest. 2013. Simulating quantum circuits with sparse output distributions. arxiv:1310.6749. arXiv: 1310.6749"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevResearch.1.033033"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.99.022308"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.53"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316310"},{"key":"e_1_3_2_1_59_1","first-page":"9","article-title":"Simulating Quantum Computers with Probabilistic Methods","volume":"11","author":"Den Nest Maarten Van","year":"2011","unstructured":"Maarten Van Den Nest . 2011 . Simulating Quantum Computers with Probabilistic Methods . Quantum Information and Computation , 11 , 9 \u2013 10 (2011), 784\u2013812. issn:1533-7146 Maarten Van Den Nest. 2011. Simulating Quantum Computers with Probabilistic Methods. Quantum Information and Computation, 11, 9\u201310 (2011), 784\u2013812. issn:1533-7146","journal-title":"Quantum Information and Computation"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2005\/09\/p09012"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.94.030301"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1039\/C2CP42695A"},{"key":"e_1_3_2_1_63_1","unstructured":"Pawel Wocjan and Shengyu Zhang. 2006. Several natural BQP-Complete problems. ArXiv: 0606179  Pawel Wocjan and Shengyu Zhang. 2006. Several natural BQP-Complete problems. ArXiv: 0606179"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519991","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519991","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:39Z","timestamp":1750268979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519991"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":63,"alternative-id":["10.1145\/3519935.3519991","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519991","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}