Quantum garbled circuits

We present a garbling scheme for quantum circuits, thus achieving a decomposable randomized encoding scheme for quantum computation. Specifically, we show how to compute an encoding of a given quantum circuit and quantum input, from which it is possible to derive the output of the computation and nothing else. In the classical setting, garbled circuits (and randomized encodings in general) are a versatile cryptographic tool with many applications such as secure multiparty computation, delegated computation, depth-reduction of cryptographic primitives, complexity lower-bounds, and more. However, a quantum analogue for garbling general circuits was not known prior to this work. We hope that our quantum randomized encoding scheme can similarly be useful for applications in quantum computing and cryptography. The properties of our scheme are as follows: • Our scheme has perfect correctness, and has perfect information-theoretic security if we allow the encoding size to blow-up considerably (double-exponentially in the depth of the circuit in the worst-case). This blowup can be avoided via computational assumptions (specifically, the existence of quantum-secure pseudorandom generators). In the computational case, the size of the encoding is proportional to the size of the circuit being garbled, up to a polynomial in the security parameter. • The encoding process is decomposable: each input qubit can be encoded independently, when given access to classical randomness and EPR pairs.