In this dissertation, we solve two open questions. First, can the output of a quantum computation be verified classically? We give the first protocol for provable classical verifica- tion of efficient quantum computations, depending only on the assumption that the learning with errors problem is post-quantum secure.

The second question, which is related to verifiability and is often referred to as blind computation, asks the following: can a classical client delegate a desired quantum compu- tation to a remote quantum server while hiding all data from the server? This is especially relevant to proposals for quantum computing in the cloud. For classical computations, this task is achieved by the celebrated result of fully homomorphic encryption ([21]). We prove an analogous result for quantum computations by showing that certain classical homomorphic encryption schemes, when used in a different manner, are able to homomorphically evaluate quantum circuits.

While we use entirely different techniques to construct the verification and homomorphic encryption protocols, they both rely on the same underlying cryptographic primitive of trapdoor claw-free functions.