{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:15:35Z","timestamp":1781259335055,"version":"3.54.1"},"reference-count":32,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T00:00:00Z","timestamp":1743033600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000288","name":"Royal Society","doi-asserted-by":"crossref","award":["URF\\R1\\211106"],"award-info":[{"award-number":["URF\\R1\\211106"]}],"id":[{"id":"10.13039\/501100000288","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000185","name":"DARPA","doi-asserted-by":"crossref","award":["HR00112020023."],"award-info":[{"award-number":["HR00112020023."]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"There is a large body of work studying what forms of computational hardness are needed to realize classical cryptography. In particular, one-way functions and pseudorandom generators can be built from each other, and thus require equivalent computational assumptions to be realized. Furthermore, the existence of either of these primitives implies that P<\/mml:mi><\/mml:mrow>&#x2260;<\/mml:mo>N<\/mml:mi>P<\/mml:mi><\/mml:mrow><\/mml:math>, which gives a lower bound on the necessary hardness.One can also define versions of each of these primitives with quantum output: respectively one-way state generators and pseudorandom state generators. Unlike in the classical setting, it is not known whether either primitive can be built from the other. Although it has been shown that pseudorandom state generators for certain parameter regimes can be used to build one-way state generators, the implication has not been previously known in full generality. Furthermore, to the best of our knowledge, the existence of one-way state generators has no known implications in complexity theory.We show that pseudorandom states compressing n<\/mml:mi><\/mml:math> bits to log<\/mml:mi>&#x2061;<\/mml:mo>n<\/mml:mi>+<\/mml:mo>1<\/mml:mn><\/mml:math> qubits can be used to build one-way state generators and pseudorandom states compressing n<\/mml:mi><\/mml:math> bits to &#x03C9;<\/mml:mi>(<\/mml:mo>log<\/mml:mi>&#x2061;<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:math> qubits are one-way state generators. This is a nearly optimal result since pseudorandom states with fewer than c<\/mml:mi>log<\/mml:mi>&#x2061;<\/mml:mo>n<\/mml:mi><\/mml:math>-qubit output can be shown to exist unconditionally. We also show that any one-way state generator can be broken by a quantum algorithm with classical access to a P<\/mml:mi>P<\/mml:mi><\/mml:mrow><\/mml:math> oracle.An interesting implication of our results is that a t<\/mml:mi>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:math>-copy one-way state generator exists unconditionally, for every t<\/mml:mi>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo>=<\/mml:mo>o<\/mml:mi>(<\/mml:mo>n<\/mml:mi>\/<\/mml:mo><\/mml:mrow>log<\/mml:mi>&#x2061;<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:math>. This contrasts nicely with the previously known fact that O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:math>-copy one-way state generators require computational hardness. We also outline a new route towards a black-box separation between one-way state generators and quantum bit commitments.<\/jats:p>","DOI":"10.22331\/q-2025-03-27-1679","type":"journal-article","created":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T10:41:55Z","timestamp":1743072115000},"page":"1679","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":4,"title":["On the Computational Hardness of Quantum One-Wayness"],"prefix":"10.22331","volume":"9","author":[{"given":"Bruno","family":"Cavalar","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eli","family":"Goldin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, New York University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthew","family":"Gray","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Hall","sequence":"additional","affiliation":[{"name":"Department of Computer Science, New York University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yanyi","family":"Liu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Cornell Tech, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Angelos","family":"Pelecanos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, UC Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2025,3,27]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Mihir Bellare, Lenore Cowen, and Shafi Goldwasser. ``On the structure of secret key exchange protocols''. In Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings. Volume 435 of Lecture Notes in Computer Science, pages 604\u2013605. Springer (1989).","DOI":"10.1007\/0-387-34805-0_53"},{"key":"1","doi-asserted-by":"publisher","unstructured":"R. Impagliazzo and S. Rudich. ``Limits on the provable consequences of one-way permutations''. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing. Page 44\u201361. STOC '89New York, NY, USA (1989). Association for Computing Machinery.","DOI":"10.1145\/73007.73012"},{"key":"2","doi-asserted-by":"publisher","unstructured":"R. Impagliazzo. ``A personal view of average-case complexity''. In Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference. Pages 134\u2013147. (1995).","DOI":"10.1109\/SCT.1995.514853"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Charles H. Bennett and Gilles Brassard. ``Quantum cryptography: Public key distribution and coin tossing''. Theoretical Computer Science 560, 7\u201311 (2014).","DOI":"10.1016\/j.tcs.2014.05.025"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Stephen Wiesner. ``Conjugate coding''. SIGACT News 15, 78\u201388 (1983).","DOI":"10.1145\/1008908.1008920"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Hoi-Kwong Lo and H. F. Chau. ``Is quantum bit commitment really possible?''. Physical Review Letters 78, 3410\u20133413 (1997).","DOI":"10.1103\/physrevlett.78.3410"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Zhengfeng Ji, Yi-Kai Liu, and Fang Song. ``Pseudorandom quantum states''. In Advances in Cryptology\u2013CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19\u201323, 2018, Proceedings, Part III 38. Pages 126\u2013152. Springer (2018).","DOI":"10.1007\/978-3-319-96878-0_5"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Dakshita Khurana and Kabir Tomer. ``Commitments from quantum one-wayness''. CoRR abs\/2310.11526 (2023). arXiv:2310.11526.","DOI":"10.48550\/ARXIV.2310.11526"},{"key":"8","doi-asserted-by":"publisher","unstructured":"William Kretschmer. ``Quantum pseudorandomness and classical complexity''. In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2021, July 5-8, 2021, Virtual Conference. Volume 197 of LIPIcs, pages 2:1\u20132:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021).","DOI":"10.4230\/LIPICS.TQC.2021.2"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Tomoyuki Morimae and Takashi Yamakawa. ``Quantum commitments and signatures without one-way functions''. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part I. Volume 13507 of Lecture Notes in Computer Science, pages 269\u2013295. Springer (2022).","DOI":"10.1007\/978-3-031-15802-5_10"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. ``Pseudorandom (function-like) quantum state generators: New definitions and applications''. In Eike Kiltz and Vinod Vaikuntanathan, editors, Theory of Cryptography - 20th International Conference, TCC 2022, Chicago, IL, USA, November 7-10, 2022, Proceedings, Part I. Volume 13747 of Lecture Notes in Computer Science, pages 237\u2013265. Springer (2022).","DOI":"10.1007\/978-3-031-22318-1_9"},{"key":"11","doi-asserted-by":"crossref","unstructured":"Zvika Brakerski and Omri Shmueli. ``Scalable pseudorandom quantum states'' (2020). arXiv:2004.01976.","DOI":"10.1007\/978-3-030-56880-1_15"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Tomoyuki Morimae and Takashi Yamakawa. ``One-wayness in quantum cryptography''. In Fr\u00e9d\u00e9ric Magniez and Alex Bredariol Grilo, editors, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2024, September 9-13, 2024, Okinawa, Japan. Volume 310 of LIPIcs, pages 4:1\u20134:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024).","DOI":"10.4230\/LIPICS.TQC.2024.4"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Zvika Brakerski, Ran Canetti, and Luowen Qian. ``On the computational hardness needed for quantum cryptography''. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA. Volume 251 of LIPIcs, pages 24:1\u201324:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023).","DOI":"10.4230\/LIPICS.ITCS.2023.24"},{"key":"14","unstructured":"Daniel Gottesman and Isaac Chuang. ``Quantum digital signatures'' (2001). arXiv:quant-ph\/0105032."},{"key":"15","unstructured":"Alex Lombardi, Fermi Ma, and John Wright. ``A one-query lower bound for unitary synthesis and breaking quantum cryptography''. Cryptology ePrint Archive, Paper 2023\/1602 (2023). https:\/\/eprint.iacr.org\/2023\/1602."},{"key":"16","doi-asserted-by":"publisher","unstructured":"Jun Yan. ``General properties of quantum bit commitments (extended abstract)''. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part IV. Volume 13794 of Lecture Notes in Computer Science, pages 628\u2013657. Springer (2022).","DOI":"10.1007\/978-3-031-22972-5_22"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. ``Exact and approximate unitary 2-designs and their application to fidelity estimation''. Physical Review A 80, 012304 (2009).","DOI":"10.1103\/PhysRevA.80.012304"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Jonas Haferkamp, Felipe Montealegre-Mora, Markus Heinrich, Jens Eisert, David Gross, and Ingo Roth. ``Efficient unitary designs with a system-size independent number of non-clifford gates''. Communications in Mathematical Physics 397, 995\u20131041 (2023).","DOI":"10.1007\/s00220-022-04507-6"},{"key":"19","doi-asserted-by":"crossref","unstructured":"Ryan O'Donnell, Rocco A. Servedio, and Pedro Paredes. ``Explicit orthogonal and unitary designs'' (2023). arXiv:2310.13597.","DOI":"10.1109\/FOCS57990.2023.00073"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Scott Aaronson. ``Quantum computing, postselection, and probabilistic polynomial-time''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 461, 3473 \u2013 3482 (2005). url: https:\/\/api.semanticscholar.org\/CorpusID:1770389.","DOI":"10.1098\/rspa.2005.1546"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. ``Quantum search-to-decision reductions and the state synthesis problem''. In Shachar Lovett, editor, 37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA. Volume 234 of LIPIcs, pages 5:1\u20135:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022).","DOI":"10.4230\/LIPICS.CCC.2022.5"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Minki Hhan, Tomoyuki Morimae, and Takashi Yamakawa. ``A note on output length of one-way state generators''. CoRR abs\/2312.16025 (2023). arXiv:2312.16025.","DOI":"10.48550\/ARXIV.2312.16025"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Rishabh Batra and Rahul Jain. ``Commitments are equivalent to statistically-verifiable one-way state generators''. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). Pages 1178\u20131192. (2024).","DOI":"10.1109\/FOCS61266.2024.00077"},{"key":"24","unstructured":"Dakshita Khurana and Kabir Tomer. ``Founding quantum cryptography on quantum advantage, or, towards cryptography from $\\#\\mathsf{P}$-hardness''. Cryptology ePrint Archive, Paper 2024\/1490 (2024)."},{"key":"25","unstructured":"Amit Behera, Giulio Malavolta, Tomoyuki Morimae, Tamer Mour, and Takashi Yamakawa. ``A new world in the depths of microcrypt: Separating owsgs and quantum money from qefid'' (2025). arXiv:2410.03453."},{"key":"26","unstructured":"John Bostanci, Boyang Chen, and Barak Nehoran. ``Oracle separation between quantum commitments and quantum one-wayness'' (2024). arXiv:2410.03358."},{"key":"27","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora and Boaz Barak. ``Computational complexity - A modern approach''. Cambridge University Press. (2009). url: http:\/\/www.cambridge.org\/catalogue\/catalogue.asp?isbn=9780521424264.","DOI":"10.1017\/CBO9780511804090"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Greg Kuperberg. ``How hard is it to approximate the jones polynomial?''. Theory of Computing 11, 183\u2013219 (2015).","DOI":"10.4086\/toc.2015.v011a006"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Fernando GSL Brandao, Aram W Harrow, and Micha\u0142 Horodecki. ``Local random quantum circuits are approximate polynomial-designs''. Communications in Mathematical Physics 346, 397\u2013434 (2016).","DOI":"10.1007\/s00220-016-2706-8"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Patrick Hayden, Debbie W Leung, and Andreas Winter. ``Aspects of generic entanglement''. Communications in mathematical physics 265, 95\u2013117 (2006).","DOI":"10.1007\/s00220-006-1535-6"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Mervin E. Muller. ``A note on a method for generating points uniformly on n-dimensional spheres''. Commun. ACM 2, 19\u201320 (1959).","DOI":"10.1145\/377939.377946"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-03-27-1679\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T10:42:09Z","timestamp":1743072129000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-03-27-1679\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,27]]},"references-count":32,"URL":"https:\/\/doi.org\/10.22331\/q-2025-03-27-1679","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,27]]},"article-number":"1679"}}