Document Open Access Logo

A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round

Author Alex B. Grilo

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.28.pdf
  • Filesize: 0.51 MB
  • 13 pages

Document Identifiers

Author Details

Alex B. Grilo
  • CWI, Amsterdam, The Netherlands
  • QuSoft, Amsterdam, The Netherlands

Funding

  • Grilo, Alex B.: Supported by ERC Consolidator Grant 615307-QPROGRESS.

Acknowledgements

I thank Iordanis Kerenidis, Damián Pitalúa-García and Thomas Vidick for useful discussions and comments in early drafts of this manuscript. I also thank anonymous reviewers helped me improving the presentation of this work. Part of this work was done when I was member of IRIF, Université Paris Diderot, Paris, France, where I was supported by ERC QCC and French Programme d’Investissement d’Avenir RISQ P141580.

Cite AsGet BibTex

Alex B. Grilo. A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.28

Abstract

The importance of being able to verify quantum computation delegated to remote servers increases with recent development of quantum technologies. In some of the proposed protocols for this task, a client delegates her quantum computation to non-communicating servers in multiple rounds of communication. In this work, we propose the first protocol where the client delegates her quantum computation to two servers in one-round of communication. Another advantage of our protocol is that it is conceptually simpler than previous protocols. The parameters of our protocol also make it possible to prove security even if the servers are allowed to communicate, but respecting the plausible assumption that information cannot be propagated faster than speed of light, making it the first relativistic protocol for quantum computation.

Subject Classification

ACM Subject Classification
  • Hardware → Quantum communication and cryptography
  • Theory of computation → Quantum complexity theory
Keywords
  • quantum computation
  • quantum cryptography
  • delegation of quantum computation

Metrics

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

Related Versions

References

  1. Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, and Elham Kashefi. On the implausibility of classical client blind quantum computing. arXiv preprint, 2017. URL: http://arxiv.org/abs/1704.08482.
  2. Dorit Aharonov, Itai Arad, and Thomas Vidick. Guest column: the quantum PCP conjecture. SIGACT News, 44(2):47-79, 2013. URL: http://dblp.uni-trier.de/db/journals/sigact/sigact44.html#AharonovAV13.
  3. Dorit Aharonov, Michael Ben-Or, Elad Eban, and Urmila Mahadev. Interactive proofs for quantum computations. arXiv preprint, 2017. URL: http://arxiv.org/abs/1704.04487.
  4. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof Verification and the Hardness of Approximation Problems. J. ACM, 45(3):501-555, 1998. URL: http://dx.doi.org/10.1145/278298.278306.
  5. Sanjeev Arora and S Safra. Probabilistic Checking of Proofs: A New Characterization of NP. jacm, 45(1):70-122, 1998. URL: http://dx.doi.org/10.1145/273865.273901.
  6. John S Bell. On the Einstein-Podolsky-Rosen Paradox. Physics, 1:195-200, 1964. Google Scholar
  7. Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson. Multi-prover Interactive Proofs: How to Remove Intractability Assumptions. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC '88, pages 113-131. ACM, 1988. URL: http://dx.doi.org/10.1145/62212.62223.
  8. Anne Broadbent. How to Verify a Quantum Computation, 2018. Google Scholar
  9. Davide Castelvecchi. IBM’s quantum cloud computer goes commercial. Nature News, 543(7644), 2017. Google Scholar
  10. Andrea Coladangelo, Alex Grilo, Stacey Jeffery, and Thomas Vidick. Verifier-on-a-Leash: new schemes for verifiable delegated quantum computation, with quasilinear resources. arXiv preprint, 2017. URL: http://arxiv.org/abs/1708.07359.
  11. Toby S Cubitt and Ashley Montanaro. Complexity Classification of Local Hamiltonian Problems. In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS '14), pages 120-129, 2014. Google Scholar
  12. Irit Dinur. The PCP Theorem by Gap Amplification. jacm, 54(3), 2007. Google Scholar
  13. Joseph F. Fitzsimons, Michal Hajdušek, and Tomoyuki Morimae. Post hoc Verification of Quantum Computation. Phys. Rev. Lett., 120:040501, January 2018. Google Scholar
  14. Joseph F. Fitzsimons and Elham Kashefi. Unconditionally verifiable blind quantum computation. Physical Review A, 96(012303), 2012. Google Scholar
  15. Alexandru Gheorghiu, Elham Kashefi, and Petros Wallden. Robustness and device independence of verifiable blind quantum computing. New Journal of Physics, 17, 2015. Google Scholar
  16. Alex B. Grilo. Relativistic verifiable delegation of quantum computation. arXiv preprint, 2017. URL: http://arxiv.org/abs/1711.09585.
  17. Michal Hajdušek, Carlos A Pérez-Delgado, and Joseph F. Fitzsimons. Device-independent verifiable blind quantum computation. arXiv preprint, 2015. URL: http://arxiv.org/abs/1502.02563.
  18. Zhengfeng Ji. Classical verification of quantum proofs. In Proceedings of the Forty-eighth Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), pages 885-898, 2016. Google Scholar
  19. Alexei Kitaev, A Shen, and M N Vyalyi. Classical and quantum computation. Graduate studies in mathematics. American mathematical society, Providence (R.I.), 2002. URL: http://opac.inria.fr/record=b1100148.
  20. Urmila Mahadev. Classical Verification of Quantum Computations. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 259-267, 2018. Google Scholar
  21. Dominic Mayers and Andrew Yao. Self testing quantum apparatus. Quantum Information & Computation, 4:273-286, 2004. Google Scholar
  22. Matthew McKague. Interactive Proofs for BQP via Self-Tested Graph States. Theory of Computing, 12(3):1-42, 2016. Google Scholar
  23. David Mermin. Simple unified form for the major no-hidden-variables theorems. Physical Review Letters, 65:3373-3376, 1990. Google Scholar
  24. Ashely Montanaro. Quantum algorithms: an overview. npj Quantum Information, 2(15023), 2016. Google Scholar
  25. Tomoyuki Morimae. Verification for measurement-only blind quantum computing. Physical Review A, 89, 2014. Google Scholar
  26. Tomoyuki Morimae and Joseph F. Fitzsimons. Post hoc verification with a single prover. arXiv preprint, 2016. URL: http://arxiv.org/abs/arXiv:1603.06046.
  27. Anand Natarajan and Thomas Vidick. A quantum linearity test for robustly verifying entanglement. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 1003-1015, 2017. Google Scholar
  28. Anand Natarajan and Thomas Vidick. Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 731-742, 2018. Google Scholar
  29. Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge Series on Information and the Natural Sciences. Cambridge University Press, 2000. Google Scholar
  30. Asher Peres. Incompatible results of quantum measurements. Physics Letters A, 151(3):107-108, 1990. URL: http://dx.doi.org/10.1016/0375-9601(90)90172-K.
  31. Ran Raz. A Parallel Repetition Theorem. sicomp, 27(3):763-803, 1998. Google Scholar
  32. Ben W Reichardt, Falk Unger, and Umesh Vazirani. Classical Command of Quantum Systems. Nature, 496:456-460, 2013. Google Scholar
  33. Xingyao Wu, Jean-Daniel Bancal, Matthew McKague, and Valerio Scarani. Device-independent parallel self-testing of two singlets. Physical Review A, 93:62121, 2016. Google Scholar
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