A quantum Goldreich-Levin theorem with cryptographic applications

Mark Adcock, Richard Cleve

We investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the computational problem of inverting a one-way function to the p…