Limitations on Transversal Computation through Quantum Homomorphic Encryption
Newman, Michael; Shi, Yaoyun;
Subject: Computer Science - Information Theory | Quantum Physics | Computer Science - Cryptography and Security
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 reve... View more
 A. Ambainis, D. Leung, L. Mancinska, and M. Ozols. Quantum random access codes with shared randomness, October 2008. arXiv:0810.2937.
 L. Arnaud and N. J. Cerf. Exploring pure quantum states with maximally mixed reductions, January 2013. Phys. Rev. A 87, 012319 (2013).
 A. Baumeler and A. Broadbent. Quantum private information retrieval has linear communication complexity, April 2013. Journal of Cryptology. Volume 28, Issue 1, pp 161-175 (2015).
 H. Bombin. Gauge color codes: Optimal transversal gates and gauge fixing in topological stabilizer codes, August 2015. New J. Phys. 17 (2015) 083002.
 M. J. Bremner, R. Jozsa, and D. J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy, August 2010. Proceedings of the Royal Society A, Volume 467, Issue 2126.
 A. Broadbent. Delegating private quantum computations, June 2015. Canadian Journal of Physics, 2015, 93(9): 941-946.
 A. Broadbent, J. Fitzsimons, and E. Kashefi. Universal blind quantum computation, 2009. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pp. 517-526.
 A. Broadbent and S. Jeffery. Quantum homomorphic encryption for circuits of low T-gate complexity, 2015. In Proceedings of Advances in Cryptology - CRYPTO 2015, pp 609-629.
 A. Broadbent, Z. Ji, F. Song, and J. Watrous. Zero-knowledge proof systems for QMA, April 2016. Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016) pp.31-40.
 R. Cramer, L. Ducas, C. Peikert, and O. Regev. Recovering short generators of principal ideals in cyclotomic rings. Cryptology ePrint Archive, Report 2015/313, 2015.