Future quantum computers are likely to be expensive and affordable outright by few, motivating client/server models for outsourced computation. However, the applications for quantum computing will often involve sensitive data, and the client would li
ke to keep her data secret, both from eavesdroppers and the server itself. Homomorphic encryption is an approach for encrypted, outsourced quantum computation, where the clients data remains secret, even during execution of the computation. We present a scheme for the homomorphic encryption of arbitrary quantum states of light with no more than a fixed number of photons, under the evolution of both passive and adaptive linear optics, the latter of which is universal for quantum computation. The scheme uses random coherent displacements in phase-space to obfuscate client data. In the limit of large coherent displacements, the protocol exhibits asymptotically perfect information-theoretic secrecy. The experimental requirements are modest, and easily implementable using present-day technology.
We show that any language in nondeterministic time $exp(exp(cdots exp(n)))$, where the number of iterated exponentials is an arbitrary function $R(n)$, can be decided by a multiprover interactive proof system with a classical polynomial-time verifier
and a constant number of quantum entangled provers, with completeness $1$ and soundness $1 - exp(-Cexp(cdotsexp(n)))$, where the number of iterated exponentials is $R(n)-1$ and $C>0$ is a universal constant. The result was previously known for $R=1$ and $R=2$; we obtain it for any time-constructible function $R$. The result is based on a compression technique for interactive proof systems with entangled provers that significantly simplifies and strengthens a protocol compression result of Ji (STOC17). As a separate consequence of this technique we obtain a different proof of Slofstras recent result (unpublished) on the uncomputability of the entangled value of multiprover games. Finally, we show that even minor improvements to our compression result would yield remarkable consequences in computational complexity theory and the foundations of quantum mechanics: first, it would imply that the class MIP* contains all computable languages; second, it would provide a negative resolution to a multipartite version of Tsirelsons problem on the relation between the commuting operator and tensor product models for quantum correlations.
We explore the space just above BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can p
erform measurements that do not collapse the wavefunction. This (non-physical) model of computation can efficiently solve problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. Furthermore, it can search an unstructured N-element list in $tilde O$(N^{1/3}) time, but no faster than {Omega}(N^{1/4}), and hence cannot solve NP-hard problems in a black box manner. In short, this model of computation is more powerful than standard quantum computation, but only slightly so. Our work is inspired by previous work of Aaronson on the power of sampling the histories of hidden variables. However Aaronsons work contains an error in its proof of the lower bound for search, and hence it is unclear whether or not his model allows for search in logarithmic time. Our work can be viewed as a conceptual simplification of Aaronsons approach, with a provable polynomial lower bound for search.
