Document Open Access Logo

Complexity-Theoretic Limitations on Blind Delegated Quantum Computation

Authors Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu , Elham Kashefi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.6.pdf
  • Filesize: 0.56 MB
  • 13 pages

Document Identifiers

Author Details

Scott Aaronson
  • Department of Computer Science, University of Texas at Austin, USA
Alexandru Cojocaru
  • School of Informatics, University of Edinburgh, UK
Alexandru Gheorghiu
  • Department of Computing and Mathematical Sciences, California Institute of Technology, USA
  • School of Informatics, University of Edinburgh, UK
Elham Kashefi
  • School of Informatics, University of Edinburgh, UK
  • CNRS LIP6, Université Pierre et Marie Curie, Paris, France

Funding

  • Aaronson, Scott: Vannevar Bush Fellowship from the US Department of Defense.
  • Cojocaru, Alexandru: EPSRC grants EP/N003829/1, EP/M013243/1.
  • Gheorghiu, Alexandru: MURI Grant FA9550-18-1-0161 and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028).
  • Kashefi, Elham: EPSRC grants EP/N003829/1, EP/M013243/1.

Acknowledgements

We would like to thank the following people for useful discussions and comments: Petros Wallden, Matty J Hoban, Kousha Etessami, Marc Kaplan, Ronald de Wolf, Urmila Mahadev, Umesh Vazirani, Chris Heunen, Thomas Vidick, Ashley Montanaro, Tina Zhang and Pia Kullik. A.G. is in particular grateful to Petros Wallden and Matty J Hoban for their patience and for their help in clarifying several technical issues.

Cite AsGet BibTex

Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, and Elham Kashefi. Complexity-Theoretic Limitations on Blind Delegated Quantum Computation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.6

Abstract

Blind delegation protocols allow a client to delegate a computation to a server so that the server learns nothing about the input to the computation apart from its size. For the specific case of quantum computation we know, from work over the past decade, that blind delegation protocols can achieve information-theoretic security (provided the client and the server exchange some amount of quantum information). In this paper we prove, provided certain complexity-theoretic conjectures are true, that the power of information-theoretically secure blind delegation protocols for quantum computation (ITS-BQC protocols) is in a number of ways constrained. In the first part of our paper we provide some indication that ITS-BQC protocols for delegating polynomial-time quantum computations in which the client and the server interact only classically are unlikely to exist. We first show that having such a protocol in which the client and the server exchange O(n^d) bits of communication, implies that BQP subset MA/O(n^d). We conjecture that this containment is unlikely by proving that there exists an oracle relative to which BQP not subset MA/O(n^d). We then show that if an ITS-BQC protocol exists in which the client and the server interact only classically and which allows the client to delegate quantum sampling problems to the server (such as BosonSampling) then there exist non-uniform circuits of size 2^{n - Omega(n/log(n))}, making polynomially-sized queries to an NP^{NP} oracle, for computing the permanent of an n x n matrix. The second part of our paper concerns ITS-BQC protocols in which the client and the server engage in one round of quantum communication and then exchange polynomially many classical messages. First, we provide a complexity-theoretic upper bound on the types of functions that could be delegated in such a protocol by showing that they must be contained in QCMA/qpoly cap coQCMA/qpoly. Then, we show that having such a protocol for delegating NP-hard functions implies coNP^{NP^{NP}} subseteq NP^{NP^{PromiseQMA}}.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
  • Theory of computation → Quantum complexity theory
Keywords
  • Quantum cryptography
  • Complexity theory
  • Delegated quantum computation
  • Computing on encrypted data

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Scott Aaronson. Limits on efficient computation in the physical world. arXiv preprint, 2004. URL: http://arxiv.org/abs/quant-ph/0412143.
  2. Scott Aaronson. BQP and the polynomial hierarchy. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC '10, pages 141-150, New York, NY, USA, 2010. ACM. URL: http://dx.doi.org/10.1145/1806689.1806711.
  3. Scott Aaronson. The Equivalence of Sampling and Searching. In Proceedings of the 6th International Conference on Computer Science: Theory and Applications, CSR'11, pages 1-14, Berlin, Heidelberg, 2011. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=2017990.2017991.
  4. Scott Aaronson. 𝖯 ?= NP, 2017. URL: https://www.scottaaronson.com/papers/pnp.pdf.
  5. Scott Aaronson and Andris Ambainis. Forrelation: A Problem That Optimally Separates Quantum from Classical Computing. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 307-316, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2746539.2746547.
  6. Scott Aaronson and Alex Arkhipov. The Computational Complexity of Linear Optics. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 333-342, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/1993636.1993682.
  7. Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, and Elham Kashefi. Complexity-theoretic limitations on blind delegated quantum computation. arXiv preprint, 2017. URL: http://arxiv.org/abs/1704.08482.
  8. M. Abadi, J. Feigenbaum, and J. Kilian. On Hiding Information from an Oracle. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, pages 195-203, New York, NY, USA, 1987. ACM. URL: http://dx.doi.org/10.1145/28395.28417.
  9. Dorit Aharonov, Michael Ben-Or, and Elad Eban. Interactive Proofs For Quantum Computations. In Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, pages 453-469, 2010. URL: http://conference.itcs.tsinghua.edu.cn/ICS2010/content/papers/35.html.
  10. Gorjan Alagic, Anne Broadbent, Bill Fefferman, Tommaso Gagliardoni, Christian Schaffner, and Michael St. Jules. Computational Security of Quantum Encryption, pages 47-71. Springer International Publishing, Cham, 2016. URL: http://dx.doi.org/10.1007/978-3-319-49175-2_3.
  11. Joël Alwen, Manuel Barbosa, Pooya Farshim, Rosario Gennaro, S. Dov Gordon, Stefano Tessaro, and David A. Wilson. On the Relationship between Functional Encryption, Obfuscation, and Fully Homomorphic Encryption, pages 65-84. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. URL: http://dx.doi.org/10.1007/978-3-642-45239-0_5.
  12. Pablo Arrighi and Louis Salvail. Blind quantum computation. International Journal of Quantum Information, 04(05):883-898, 2006. URL: http://dx.doi.org/10.1142/S0219749906002171.
  13. Ethan Bernstein and Umesh Vazirani. Quantum Complexity Theory. SIAM J. Comput., 26(5):1411-1473, October 1997. URL: http://dx.doi.org/10.1137/S0097539796300921.
  14. Andreas Björklund. Below All Subsets for Some Permutational Counting Problems . In Rasmus Pagh, editor, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), volume 53 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:11, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.17.
  15. Zvika Brakerski. Quantum FHE (Almost) As Secure as Classical. Cryptology ePrint Archive, Report 2018/338, 2018. URL: https://eprint.iacr.org/2018/338.
  16. Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) Fully Homomorphic Encryption Without Bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, pages 309-325, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2090236.2090262.
  17. Zvika Brakerski and Vinod Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. In Proceedings of the 2011 IEEE 52Nd Annual Symposium on Foundations of Computer Science, FOCS '11, pages 97-106, Washington, DC, USA, 2011. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2011.12.
  18. Anne Broadbent. Delegating private quantum computations. Canadian Journal of Physics, 93(9):941-946, 2015. URL: http://dx.doi.org/10.1139/cjp-2015-0030.
  19. Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. Universal blind quantum computation. In Proceedings of the 50th Annual Symposium on Foundations of Computer Science, FOCS '09, pages 517-526. IEEE Computer Society, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.36.
  20. Anne Broadbent and Stacey Jeffery. Quantum Homomorphic Encryption for Circuits of Low T-gate Complexity. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, pages 609-629, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48000-7_30.
  21. Andrew M. Childs. Secure Assisted Quantum Computation. Quantum Info. Comput., 5(6):456-466, September 2005. URL: http://dl.acm.org/citation.cfm?id=2011670.2011674.
  22. Ivan Damgård, Jens Groth, and Gorm Salomonsen. The Theory and Implementation of an Electronic Voting System, pages 77-99. Springer US, Boston, MA, 2003. URL: http://dx.doi.org/10.1007/978-1-4615-0239-5_6.
  23. J Niel De Beaudrap, Richard Cleve, John Watrous, et al. Sharp quantum versus classical query complexity separations. Algorithmica, 34(4):449-461, 2002. Google Scholar
  24. Yfke Dulek, Christian Schaffner, and Florian Speelman. Quantum Homomorphic Encryption for Polynomial-Sized Circuits, pages 3-32. Springer Berlin Heidelberg, Berlin, Heidelberg, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53015-3_1.
  25. Vedran Dunjko and Elham Kashefi. Blind quantum computing with two almost identical states, 2016. URL: http://arxiv.org/abs/1604.01586.
  26. Joseph F Fitzsimons. Private quantum computation: an introduction to blind quantum computing and related protocols. npj Quantum Information, 3(1):23, 2017. Google Scholar
  27. Joseph F Fitzsimons and Elham Kashefi. Unconditionally verifiable blind quantum computation. Physical Review A, 96(1):012303, 2017. Google Scholar
  28. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits. In Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS '13, pages 40-49, Washington, DC, USA, 2013. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2013.13.
  29. Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, STOC '09, pages 169-178, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1536414.1536440.
  30. Alexandru Gheorghiu, Theodoros Kapourniotis, and Elham Kashefi. Verification of quantum computation: An overview of existing approaches. Theory of computing systems, pages 1-94, 2018. Google Scholar
  31. Vittorio Giovannetti, Lorenzo Maccone, Tomoyuki Morimae, and Terry G. Rudolph. Efficient Universal Blind Quantum Computation. Phys. Rev. Lett., 111:230501, December 2013. URL: http://dx.doi.org/10.1103/PhysRevLett.111.230501.
  32. Thore Graepel, Kristin Lauter, and Michael Naehrig. ML Confidential: Machine Learning on Encrypted Data. In Proceedings of the 15th International Conference on Information Security and Cryptology, ICISC'12, pages 1-21, Berlin, Heidelberg, 2013. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-642-37682-5_1.
  33. Lov K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC '96, pages 212-219, New York, NY, USA, 1996. ACM. URL: http://dx.doi.org/10.1145/237814.237866.
  34. Dominik Hangleiter, Martin Kliesch, Jens Eisert, and Christian Gogolin. Sample complexity of device-independently certified" quantum supremacy". arXiv preprint, 2018. URL: http://arxiv.org/abs/1812.01023.
  35. Aram W Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549(7671):203, 2017. Google Scholar
  36. Thomas Jansen. On the Black-Box Complexity of Example Functions: The Real Jump Function. In Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, FOGA '15, pages 16-24, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2725494.2725507.
  37. Arjan Jeckmans, Andreas Peter, and Pieter Hartel. Efficient Privacy-Enhanced Familiarity-Based Recommender System, pages 400-417. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40203-6_23.
  38. Elham Kashefi, Luka Music, and Petros Wallden. The Quantum Cut-and-Choose Technique and Quantum Two-Party Computation, 2017. URL: http://arxiv.org/abs/1703.03754.
  39. Elham Kashefi and Petros Wallden. Garbled quantum computation. Cryptography, 1(1):6, 2017. Google Scholar
  40. Jonathan Katz and Yehuda Lindell. Introduction to modern cryptography. CRC press, 2014. Google Scholar
  41. Kristin E. Lauter. Practical Applications of Homomorphic Encryption. In Proceedings of the 2012 ACM Workshop on Cloud Computing Security Workshop, CCSW '12, pages 57-58, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2381913.2381924.
  42. Sheng-Kai Liao, Wen-Qi Cai, Wei-Yue Liu, Liang Zhang, Yang Li, Ji-Gang Ren, Juan Yin, Qi Shen, Yuan Cao, Zheng-Ping Li, et al. Satellite-to-ground quantum key distribution. Nature, 549(7670):43, 2017. Google Scholar
  43. Urmila Mahadev. Classical homomorphic encryption for quantum circuits. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 332-338. IEEE, 2018. Google Scholar
  44. Atul Mantri, Tommaso F Demarie, and Joseph F Fitzsimons. Universality of quantum computation with cluster states and (X, Y)-plane measurements. Scientific reports, 7:42861, 2017. Google Scholar
  45. Atul Mantri, Carlos A. Pérez-Delgado, and Joseph F. Fitzsimons. Optimal Blind Quantum Computation. Phys. Rev. Lett., 111:230502, December 2013. URL: http://dx.doi.org/10.1103/PhysRevLett.111.230502.
  46. Tomoyuki Morimae, Vedran Dunjko, and Elham Kashefi. Ground State Blind Quantum Computation on AKLT State. Quantum Info. Comput., 15(3-4):200-234, March 2015. URL: http://dl.acm.org/citation.cfm?id=2871393.2871395.
  47. Tomoyuki Morimae and Keisuke Fujii. Blind quantum computation protocol in which Alice only makes measurements. Phys. Rev. A, 87:050301, May 2013. URL: http://dx.doi.org/10.1103/PhysRevA.87.050301.
  48. Tomoyuki Morimae and Takeshi Koshiba. Impossibility of perfectly-secure delegated quantum computing for classical client, 2014. URL: http://arxiv.org/abs/1407.1636.
  49. Michael Newman and Yaoyun Shi. Limitations on Transversal Computation through Quantum Homomorphic Encryption. Quantum Information and Computation, 18:0927-0948, 2018. Google Scholar
  50. John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2:79, 2018. Google Scholar
  51. Ran Raz and Avishay Tal. Oracle Separation of BQP and PH. eccc preprint TR18-107, 2018. Eprint: URL: https://eccc.weizmann.ac.il/report/2018/107/.
  52. Ronald L Rivest, Len Adleman, and Michael L. Dertouzos. On data banks and privacy homomorphisms. Foundations of Secure Computation, 4(11):169-180, 1978. Google Scholar
  53. Herbert John Ryser. Combinatorial mathematics, volume 14. JSTOR, 1963. Google Scholar
  54. Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Review, 41(2):303-332, 1999. URL: http://dx.doi.org/10.1137/S0036144598347011.
  55. Daniel R. Simon. On the Power of Quantum Computation. SIAM Journal on Computing, 26(5):1474-1483, 1997. URL: http://dx.doi.org/10.1137/S0097539796298637.
  56. Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865-877, 1991. URL: http://dx.doi.org/10.1137/0220053.
  57. Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully Homomorphic Encryption over the Integers. In Proceedings of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT'10, pages 24-43, Berlin, Heidelberg, 2010. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-642-13190-5_2.
  58. Chee K. Yap. Some consequences of non-uniform conditions on uniform classes. Theoretical Computer Science, 26(3):287-300, 1983. URL: http://dx.doi.org/10.1016/0304-3975(83)90020-8.
  59. Li Yu, Carlos A. Pérez-Delgado, and Joseph F. Fitzsimons. Limitations on information-theoretically-secure quantum homomorphic encryption. Phys. Rev. A, 90:050303, November 2014. URL: http://dx.doi.org/10.1103/PhysRevA.90.050303.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact