2026-07-24T10:12:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25343 2026-03-19T13:03:47Z ddc:004 open_access

The Hardness of Learning Quantum Circuits and Its Cryptographic Applications Fefferman, Bill Ghosh, Soumik Sinha, Makrand Yuen, Henry quantum learning quantum circuits cryptographic hardness one-way state generators We show that concrete hardness assumptions about learning or cloning the output state of a random quantum circuit can be used as the foundation for secure quantum cryptography. In particular, under these assumptions we construct secure one-way state generators (OWSGs), digital signature schemes, quantum bit commitments, and private key encryption schemes. We also discuss evidence for these hardness assumptions by analyzing the best-known quantum learning algorithms, as well as proving black-box lower bounds for cloning and learning given state preparation oracles. Our random circuit-based constructions provide concrete instantiations of quantum cryptographic primitives whose security do not depend on the existence of one-way functions. The use of random circuits in our constructions also opens the door to {NISQ-friendly quantum cryptography}. We discuss noise tolerant versions of our OWSG and digital signature constructions which can potentially be implementable on noisy quantum computers connected by a quantum network. On the other hand, they are still secure against {noiseless} quantum adversaries, raising the intriguing possibility of a useful implementation of an end-to-end cryptographic protocol on near-term quantum computers. Finally, our explorations suggest that the rich interconnections between learning theory and cryptography in classical theoretical computer science also extend to the quantum setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bill Fefferman and Soumik Ghosh and Makrand Sinha and Henry Yuen 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.56 urn:nbn:de:0030-drops-253431 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.56 eng https://creativecommons.org/licenses/by/4.0/legalcode