Limitations on Transversal Computation through Quantum Homomorphic Encryption
This work addresses a fundamental limitation in fault-tolerant quantum computing for researchers in quantum information theory, showing that transversal computation of classical reversible gates is largely infeasible, which is incremental but clarifies a key open problem.
The paper tackles the problem of whether quantum error-correcting codes (QECCs) can transversally implement a classical reversible universal gate set, such as the Toffoli gate, and shows that, except for a small set of non-additive codes, no binary QECC can do so. This result is proven by constructing an information-theoretically secure quantum homomorphic encryption scheme that incurs exponential overhead, which would violate a lower bound if such transversal implementation were possible.
Transversality is a simple and effective method for implementing quantum computation fault-tolerantly. However, no quantum error-correcting code (QECC) can transversally implement a quantum universal gate set (Eastin and Knill, Phys. Rev. Lett., 102, 110502). Since reversible classical computation is often a dominating part of useful quantum computation, whether or not it can be implemented transversally is an important open problem. We show that, other than a small set of non-additive codes that we cannot rule out, no binary QECC can transversally implement a classical reversible universal gate set. In particular, no such QECC can implement the Toffoli gate transversally. We prove our result by constructing an information theoretically secure (but inefficient) quantum homomorphic encryption (ITS-QHE) scheme inspired by Ouyang et al. (arXiv:1508.00938). Homomorphic encryption allows the implementation of certain functions directly on encrypted data, i.e. homomorphically. Our scheme builds on almost any QECC, and implements that code's transversal gate set homomorphically. We observe a restriction imposed by Nayak's bound (FOCS 1999) on ITS-QHE, implying that any ITS quantum fully homomorphic scheme (ITS-QFHE) implementing the full set of classical reversible functions must be highly inefficient. While our scheme incurs exponential overhead, any such QECC implementing Toffoli transversally would still violate this lower bound through our scheme.