  Fully homomorphic encryption is an encryption method with the property that
any computation on the plaintext can be performed by a party having access to
the ciphertext only. Here, we formally define and give schemes for quantum
homomorphic encryption, which is the encryption of quantum information such
that quantum computations can be performed given the ciphertext only. Our
schemes allows for arbitrary Clifford group gates, but become inefficient for
circuits with large complexity, measured in terms of the non-Clifford portion
of the circuit (we use the "$\pi/8$" non-Clifford group gate, which is also
known as the $T$-gate).
  More specifically, two schemes are proposed: the first scheme has a
decryption procedure whose complexity scales with the square of the number of
$T$-gates (compared with a trivial scheme in which the complexity scales with
the total number of gates); the second scheme uses a quantum evaluation key of
length given by a polynomial of degree exponential in the circuit's $T$-gate
depth, yielding a homomorphic scheme for quantum circuits with constant
$T$-depth. Both schemes build on a classical fully homomorphic encryption
scheme.
  A further contribution of ours is to formally define the security of
encryption schemes for quantum messages: we define quantum indistinguishability
under chosen plaintext attacks in both the public and private-key settings. In
this context, we show the equivalence of several definitions.
  Our schemes are the first of their kind that are secure under modern
cryptographic definitions, and can be seen as a quantum analogue of classical
results establishing homomorphic encryption for circuits with a limited number
of multiplication gates. Historically, such results appeared as precursors to
the breakthrough result establishing classical fully homomorphic encryption.
