{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T20:48:49Z","timestamp":1757450929313,"version":"3.40.3"},"publisher-location":"Cham","reference-count":58,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031683879"},{"type":"electronic","value":"9783031683886"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-68388-6_13","type":"book-chapter","created":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T08:02:51Z","timestamp":1723795371000},"page":"359-392","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Quantum Advantage from\u00a0One-Way Functions"],"prefix":"10.1007","author":[{"given":"Tomoyuki","family":"Morimae","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takashi","family":"Yamakawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,17]]},"reference":[{"key":"13_CR1","unstructured":"Aaronson, S.: On perfect completeness for qma. arXiv:0806.0450 (2008)"},{"key":"13_CR2","doi-asserted-by":"publisher","unstructured":"Aaronson, S.: BQP and the polynomial hierarchy. In: Schulman, L.J. (ed.) 42nd ACM STOC, pp. 141\u2013150. ACM Press (2010). https:\/\/doi.org\/10.1145\/1806689.1806711","DOI":"10.1145\/1806689.1806711"},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s00224-013-9527-3","volume":"55","author":"S Aaronson","year":"2014","unstructured":"Aaronson, S.: The equivalence of sampling and searching. Theory Comput. Syst. 55, 281\u2013298 (2014)","journal-title":"Theory Comput. Syst."},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"133","DOI":"10.4086\/toc.2014.v010a006","volume":"10","author":"S Aaronson","year":"2014","unstructured":"Aaronson, S., Ambainis, A.: The need for structure in quantum speedups. Theory Comput. 10, 133\u2013166 (2014)","journal-title":"Theory Comput."},{"key":"13_CR5","doi-asserted-by":"publisher","unstructured":"Aaronson, S., Ambainis, A.: Forrelation: a problem that optimally separates quantum from classical computing. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th ACM STOC, pp. 307\u2013316. ACM Press (2015). https:\/\/doi.org\/10.1145\/2746539.2746547","DOI":"10.1145\/2746539.2746547"},{"key":"13_CR6","doi-asserted-by":"publisher","unstructured":"Aaronson, S., Arkhipov, A.: The computational complexity of linear optics. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd ACM STOC, pp. 333\u2013342. ACM Press (2011). https:\/\/doi.org\/10.1145\/1993636.1993682","DOI":"10.1145\/1993636.1993682"},{"key":"13_CR7","unstructured":"Aaronson, S., Chen, L.: Complexity-theoretic foundations of quantum supremacy experiments. In: CCC\u201917: Proceedings of the 32nd Computational Complexity Conference (2017)"},{"key":"13_CR8","unstructured":"Aaronson, S., Gunn, S.: On the classical hardness of spoofing linear cross-entropy benchmarking. arXiv:1910.12085 (2019)"},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-031-22318-1_9","volume-title":"TCC","author":"P Ananth","year":"2022","unstructured":"Ananth, P., Gulati, A., Qian, L., Yuen, H.: Pseudorandom (function-like) quantum state generators: New definitions and applications. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC, vol. 13747, pp. 237\u2013265. Springer, Heidelberg (2022). https:\/\/doi.org\/10.1007\/978-3-031-22318-1_9"},{"key":"13_CR10","doi-asserted-by":"publisher","unstructured":"Ananth, P., Qian, L., Yuen, H.: Cryptography from pseudorandom quantum states. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO\u00a02022, Part\u00a0I. LNCS, vol. 13507, pp. 208\u2013236. Springer, Heidelberg (2022). https:\/\/doi.org\/10.1007\/978-3-031-15802-5_8","DOI":"10.1007\/978-3-031-15802-5_8"},{"key":"13_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/978-3-662-53015-3_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"B Applebaum","year":"2016","unstructured":"Applebaum, B., Raykov, P.: On the relationship between statistical zero-knowledge and statistical randomized encodings. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 449\u2013477. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53015-3_16"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Arora, A.S., Coladangelo, A., Coudron, M., Gheorghiu, A., Singh, U., Waldner, H.: Quantum depth in the random oracle model. arXiv:2210.06454 (2022)","DOI":"10.1145\/3564246.3585153"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity - A Modern Approach. Cambridge University Press, Cambridge (2009). http:\/\/www.cambridge.org\/catalogue\/catalogue.asp?isbn=9780521424264","DOI":"10.1017\/CBO9780511804090"},{"key":"13_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-319-78375-8_5","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"I Berman","year":"2018","unstructured":"Berman, I., Degwekar, A., Rothblum, R.D., Vasudevan, P.N.: Multi-collision resistant hash functions and their applications. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 133\u2013161. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78375-8_5"},{"key":"13_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1007\/978-3-030-17659-4_23","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"N Bitansky","year":"2019","unstructured":"Bitansky, N., Haitner, I., Komargodski, I., Yogev, E.: Distributional collision resistance beyond one-way functions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 667\u2013695. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17659-4_23"},{"key":"13_CR16","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1038\/s41567-018-0318-2","volume":"15","author":"A Bouland","year":"2019","unstructured":"Bouland, A., Fefferman, B., Nirkhe, C., Vazirani, U.: On the complexity and verification of quantum random circuit sampling. Nat. Phys. 15, 159\u2013163 (2019)","journal-title":"Nat. Phys."},{"key":"13_CR17","unstructured":"Brakerski, Z., Canetti, R., Qian, L.: On the computational hardness needed for quantum cryptography. In: ITCS 2023: 14th Innovations in Theoretical Computer Science (2023)"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Christiano, P., Mahadev, U., Vazirani, U., Vidick, T.: A cryptographic test of quantumness and certifiable randomness from a single quantum device. J. ACM 68(5), 31:1\u201331:47 (2021)","DOI":"10.1145\/3441309"},{"key":"13_CR19","doi-asserted-by":"publisher","unstructured":"Brakerski, Z., Koppula, V., Vazirani, U., Vidick, T.: Simpler proofs of quantumness. In: Flammia, S.T. (ed.) 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2020, Riga, Latvia, 9\u201312 June 2020. LIPIcs, vol.\u00a0158, pp. 8:1\u20138:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.TQC.2020.4","DOI":"10.4230\/LIPIcs.TQC.2020.4"},{"key":"13_CR20","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1126\/science.aar3106","volume":"362","author":"S Bravyi","year":"2018","unstructured":"Bravyi, S., Gosset, D., K\u00f6nig, R.: Quantum advantage with shallow circuits. Science 362, 308\u2013311 (2018)","journal-title":"Science"},{"key":"13_CR21","doi-asserted-by":"publisher","first-page":"1040","DOI":"10.1038\/s41567-020-0948-z","volume":"16","author":"S Bravyi","year":"2020","unstructured":"Bravyi, S., Gosset, D., K\u00f6nig, R., Tomamichel, M.: Quantum advantage with noisy shallow circuits. Nat. Phys. 16, 1040\u20131045 (2020)","journal-title":"Nat. Phys."},{"key":"13_CR22","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1098\/rspa.2010.0301","volume":"467","author":"MJ Bremner","year":"2011","unstructured":"Bremner, M.J., Jozsa, R., Shepherd, D.J.: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. Roy. Soc. A: Math. Phys. Eng. Sci. 467, 459\u2013472 (2011)","journal-title":"Proc. Roy. Soc. A: Math. Phys. Eng. Sci."},{"key":"13_CR23","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.117.080501","volume":"117","author":"MJ Bremner","year":"2016","unstructured":"Bremner, M.J., Montanaro, A., Shepherd, D.J.: Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117, 080501 (2016)","journal-title":"Phys. Rev. Lett."},{"issue":"4","key":"13_CR24","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/1008731.1008734","volume":"51","author":"R Canetti","year":"2004","unstructured":"Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM 51(4), 557\u2013594 (2004). https:\/\/doi.org\/10.1145\/1008731.1008734","journal-title":"J. ACM"},{"key":"13_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-540-30576-7_2","volume-title":"Theory of Cryptography","author":"R Canetti","year":"2005","unstructured":"Canetti, R., Halevi, S., Steiner, M.: Hardness amplification of weakly verifiable puzzles. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 17\u201333. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/978-3-540-30576-7_2"},{"key":"13_CR26","unstructured":"Cao, S., Xue, R.: On constructing one-way quantum state generators, and more. Cryptology ePrint Archive, Report 2022\/1323 (2022). https:\/\/eprint.iacr.org\/2022\/1323"},{"key":"13_CR27","doi-asserted-by":"publisher","unstructured":"Dubrov, B., Ishai, Y.: On the randomness complexity of efficient sampling. In: Kleinberg, J.M. (ed.) 38th ACM STOC, pp. 711\u2013720. ACM Press (2006). https:\/\/doi.org\/10.1145\/1132516.1132615","DOI":"10.1145\/1132516.1132615"},{"key":"13_CR28","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.120.200502","volume":"120","author":"K Fujii","year":"2018","unstructured":"Fujii, K., Kobayashi, H., Morimae, T., Nishimura, H., Tani, S., Tamate, S.: Impossibility of classically simulating one-clean-qubit model with multiplicative error. Phys. Rev. Lett. 120, 200502 (2018)","journal-title":"Phys. Rev. Lett."},{"key":"13_CR29","doi-asserted-by":"publisher","unstructured":"Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd ACM STOC, pp. 99\u2013108. ACM Press (2011). https:\/\/doi.org\/10.1145\/1993636.1993651","DOI":"10.1145\/1993636.1993651"},{"key":"13_CR30","doi-asserted-by":"publisher","unstructured":"Goldreich, O.: The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press, Cambridge (2001). https:\/\/doi.org\/10.1017\/CBO9780511546891. http:\/\/www.wisdom.weizmann.ac.il\/%7Eoded\/foc-vol1.html","DOI":"10.1017\/CBO9780511546891"},{"key":"13_CR31","doi-asserted-by":"publisher","unstructured":"Goldreich, O.: The Foundations of Cryptography - Volume 2: Basic Applications. Cambridge University Press, Cambridge (2004). https:\/\/doi.org\/10.1017\/CBO9780511721656. http:\/\/www.wisdom.weizmann.ac.il\/%7Eoded\/foc-vol2.html","DOI":"10.1017\/CBO9780511721656"},{"key":"13_CR32","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: STOC, pp. 25\u201332. ACM (1989)","DOI":"10.1145\/73007.73010"},{"key":"13_CR33","doi-asserted-by":"publisher","unstructured":"Grier, D., Schaeffer, L.: Interactive shallow Clifford circuits: quantum advantage against $$\\text{NC}^1$$ and beyond. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. (eds.) 52nd ACM STOC, pp. 875\u2013888. ACM Press (2020). https:\/\/doi.org\/10.1145\/3357713.3384332","DOI":"10.1145\/3357713.3384332"},{"issue":"3","key":"13_CR34","doi-asserted-by":"publisher","first-page":"1153","DOI":"10.1137\/080725404","volume":"39","author":"I Haitner","year":"2009","unstructured":"Haitner, I., Nguyen, M.H., Ong, S.J., Reingold, O., Vadhan, S.: Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM J. Comput. 39(3), 1153\u20131218 (2009)","journal-title":"SIAM J. Comput."},{"key":"13_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/3-540-68697-5_16","volume-title":"Advances in Cryptology \u2014 CRYPTO \u201996","author":"S Halevi","year":"1996","unstructured":"Halevi, S., Micali, S.: Practical and provably-secure commitment schemes from collision-free hashing. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 201\u2013215. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-68697-5_16"},{"key":"13_CR36","doi-asserted-by":"publisher","first-page":"21050","DOI":"10.1103\/PhysRevLett.122.210502","volume":"122","author":"D Hangleiter","year":"2019","unstructured":"Hangleiter, D., Kliesch, M., Eisert, J., Gogolin, C.: Sample complexity of device-independently certified \u201cquantum supremacy\u2019\u2019. Phys. Rev. Lett. 122, 21050 (2019)","journal-title":"Phys. Rev. Lett."},{"key":"13_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/978-3-319-96878-0_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"Z Ji","year":"2018","unstructured":"Ji, Z., Liu, Y.-K., Song, F.: Pseudorandom quantum states. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 126\u2013152. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96878-0_5"},{"key":"13_CR38","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1038\/s41567-022-01643-7","volume":"18","author":"GD Kahanamoku-Meyer","year":"2022","unstructured":"Kahanamoku-Meyer, G.D., Choi, S., Vazirani, U.V., Yao, N.Y.: Classically verifiable quantum advantage from a computational bell test. Nat. Phys. 18, 918\u2013924 (2022)","journal-title":"Nat. Phys."},{"key":"13_CR39","unstructured":"Kalai, Y.T., Lombardi, A., Vaikuntanathan, V., Yang, L.: Quantum advantage from any non-local game. Cryptology ePrint Archive, Paper 2022\/400 (2022). https:\/\/eprint.iacr.org\/2022\/400"},{"key":"13_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-319-78375-8_6","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"I Komargodski","year":"2018","unstructured":"Komargodski, I., Naor, M., Yogev, E.: Collision resistant hashing for paranoids: dealing with multiple collisions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 162\u2013194. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78375-8_6"},{"key":"13_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-319-96881-0_11","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"I Komargodski","year":"2018","unstructured":"Komargodski, I., Yogev, E.: On distributional collision resistant\u00a0hashing. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 303\u2013327. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96881-0_11"},{"key":"13_CR42","doi-asserted-by":"publisher","unstructured":"Kretschmer, W.: Quantum pseudorandomness and classical complexity. In: TQC 2021 (2021). https:\/\/doi.org\/10.4230\/LIPICS.TQC.2021.2","DOI":"10.4230\/LIPICS.TQC.2021.2"},{"key":"13_CR43","doi-asserted-by":"crossref","unstructured":"Kretschmer, W., Qian, L., Sinha, M., Tal, A.: Quantum cryptography in algorithmica. arXiv:2212.00879 (2022)","DOI":"10.1145\/3564246.3585225"},{"key":"13_CR44","unstructured":"Liu, J., Liu, Q., Qian, L.: Beating classical impossibility of position verification. In: ITCS 2022: 13rd Innovations in Theoretical Computer Science (2022)"},{"key":"13_CR45","doi-asserted-by":"publisher","unstructured":"Mahadev, U.: Classical homomorphic encryption for quantum circuits. In: Thorup, M. (ed.) 59th FOCS, pp. 332\u2013338. IEEE Computer Society Press (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00039","DOI":"10.1109\/FOCS.2018.00039"},{"key":"13_CR46","doi-asserted-by":"publisher","first-page":"040302(R)","DOI":"10.1103\/PhysRevA.96.040302","volume":"96","author":"T Morimae","year":"2017","unstructured":"Morimae, T.: Hardness of classically sampling the one-clean-qubit model with constant total variation distance error. Phys. Rev. A 96, 040302(R) (2017)","journal-title":"Phys. Rev. A"},{"key":"13_CR47","unstructured":"Morimae, T., Yamakawa, T.: One-wayness in quantum cryptography. Cryptology ePrint Archive, Report 2022\/1336 (2022). https:\/\/eprint.iacr.org\/2022\/1336"},{"key":"13_CR48","doi-asserted-by":"publisher","unstructured":"Morimae, T., Yamakawa, T.: Quantum commitments and signatures without one-way functions. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO\u00a02022, Part\u00a0I. LNCS, vol. 13507, pp. 269\u2013295. Springer, Heidelberg (2022). https:\/\/doi.org\/10.1007\/978-3-031-15802-5_10","DOI":"10.1007\/978-3-031-15802-5_10"},{"key":"13_CR49","unstructured":"Morimae, T., Yamakawa, T.: Proofs of quantumness from trapdoor permutations. In: ITCS 2023: 14th Innovations in Theoretical Computer Science (ITCS) (2023)"},{"key":"13_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-540-45146-4_6","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"M Naor","year":"2003","unstructured":"Naor, M.: On cryptographic assumptions and challenges. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 96\u2013109. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45146-4_6"},{"key":"13_CR51","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/3-540-48071-4_14","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 92","author":"M Naor","year":"1993","unstructured":"Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP can be based on general complexity assumptions. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 196\u2013214. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-48071-4_14"},{"key":"13_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/978-3-540-78524-8_27","volume-title":"Theory of Cryptography","author":"SJ Ong","year":"2008","unstructured":"Ong, S.J., Vadhan, S.: An equivalence between zero knowledge and commitments. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 482\u2013500. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78524-8_27"},{"key":"13_CR53","doi-asserted-by":"publisher","unstructured":"Ostrovsky, R., Wigderson, A.: One-way fuctions are essential for non-trivial zero-knowledge. In: Second Israel Symposium on Theory of Computing Systems, ISTCS 1993, Natanya, Israel, 7\u20139 June 1993, Proceedings, pp. 3\u201317. IEEE Computer Society (1993). https:\/\/doi.org\/10.1109\/ISTCS.1993.253489","DOI":"10.1109\/ISTCS.1993.253489"},{"key":"13_CR54","doi-asserted-by":"publisher","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th FOCS, pp. 124\u2013134. IEEE Computer Society Press (1994). https:\/\/doi.org\/10.1109\/SFCS.1994.365700","DOI":"10.1109\/SFCS.1994.365700"},{"issue":"2","key":"13_CR55","first-page":"134","volume":"4","author":"BM Terhal","year":"2004","unstructured":"Terhal, B.M., DiVincenzo, D.P.: Adaptive quantum computation, constant-depth circuits and arthur-merlin games. Quant. Inf. Comput. 4(2), 134\u2013145 (2004)","journal-title":"Quant. Inf. Comput."},{"issue":"3","key":"13_CR56","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"LG Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theor. Comput. Sci. 47(3), 85\u201393 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90135-0","journal-title":"Theor. Comput. Sci."},{"key":"13_CR57","doi-asserted-by":"publisher","unstructured":"Watts, A.B., Kothari, R., Schaeffer, L., Tal, A.: Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. In: Charikar, M., Cohen, E. (eds.) 51st ACM STOC, pp. 515\u2013526. ACM Press (2019). https:\/\/doi.org\/10.1145\/3313276.3316404","DOI":"10.1145\/3313276.3316404"},{"key":"13_CR58","doi-asserted-by":"crossref","unstructured":"Yamakawa, T., Zhandry, M.: Verifiable quantum advantage without structure. In: FOCS 2022: 63rd IEEE Symposium on Foundations of Computer Science (2022)","DOI":"10.1109\/FOCS54457.2022.00014"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2024"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-68388-6_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,16]],"date-time":"2024-08-16T08:05:12Z","timestamp":1723795512000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-68388-6_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031683879","9783031683886"],"references-count":58,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-68388-6_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"17 August 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"44","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}