Document Open Access Logo

Self-Testing of a Single Quantum Device Under Computational Assumptions

Authors Tony Metger , Thomas Vidick

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2021.19.pdf
  • Filesize: 466 kB
  • 12 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • Quantum computing
  • quantum cryptography
  • device-independence
  • self-testing
  • post-quantum cryptography

Metrics

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

Abstract

Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.

Cite As Get BibTex

Tony Metger and Thomas Vidick. Self-Testing of a Single Quantum Device Under Computational Assumptions. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 19:1-19:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITCS.2021.19

Author Details

Tony Metger
  • Institute for Theoretical Physics, ETH Zürich, Switzerland
Thomas Vidick
  • Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA, USA

Funding

  • Metger, Tony: supported by the ETH Foundation through the Excellence Scholarship & Opportunity Programme, and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028).
  • Vidick, Thomas: supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-1-0495, a CIFAR Azrieli Global Scholar award, 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).

Acknowledgements

We thank Andrea Coladangelo, Andru Gheorghiu, Anand Natarajan, and Tina Zhang for helpful discussions; Andrea Coladangelo, Andru Gheorghiu, Urmila Mahadev, and Akihiro Mizutani for comments on the manuscript; and Lídia del Rio for pointing out the reference [Bharti et al., 2019]. This work was carried out while Tony Metger was a visiting student researcher at the Department of Computing and Mathematical Sciences at Caltech.

References

  1. William Aiello, Sandeep Bhatt, Rafail Ostrovsky, and S. Raj. Rajagopalan. Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP. Automata, Languages and Programming - ICALP 2000, Lecture Notes in Computer Science, Springer, pages 463-474, 2000. URL: https://doi.org/10.1007/3-540-45022-X_39.
  2. Gorjan Alagic, Andrew M Childs, Alex B Grilo, and Shih-Han Hung. Non-interactive classical verification of quantum computation. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.08101.
  3. John S. Bell. On the Einstein Podolsky Rosen paradox. Physics Physique Fizika, 1(3):195-200, November 1964. URL: https://doi.org/10.1103/PhysicsPhysiqueFizika.1.195.
  4. Michael Ben-Or, Claude Crépeau, Daniel Gottesman, Avinatan Hassidim, and Adam Smith. Secure multiparty quantum computation with (only) a strict honest majority. IEEE 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 249-260, 2006. URL: https://doi.org/10.1109/FOCS.2006.68.
  5. Kishor Bharti, Maharshi Ray, Antonios Varvitsiotis, Adán Cabello, and Leong-Chuan Kwek. Local certification of programmable quantum devices of arbitrary high dimensionality. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.09448.
  6. Kishor Bharti, Maharshi Ray, Antonios Varvitsiotis, Naqueeb Ahmad Warsi, Adán Cabello, and Leong-Chuan Kwek. Robust self-testing of quantum systems via noncontextuality inequalities. Phys. Rev. Lett., 122:250403, June 2019. URL: https://doi.org/10.1103/PhysRevLett.122.250403.
  7. Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15(2):159-163, February 2019. URL: https://doi.org/10.1038/s41567-018-0318-2.
  8. Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, and T. Vidick. A cryptographic test of quantumness and certifiable randomness from a single quantum device. IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 320-331, 2018. URL: https://doi.org/10.1109/FOCS.2018.00038.
  9. Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick. Simpler proofs of quantumness. arXiv preprint, 2020. URL: http://arxiv.org/abs/2005.04826.
  10. Anne Broadbent and Alex B Grilo. Zero-knowledge for QMA from locally simulatable proofs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.07782.
  11. Nai-Hui Chia, Kai-Min Chung, and Takashi Yamakawa. Classical verification of quantum computations with efficient verifier. arXiv preprint, 2019. URL: http://arxiv.org/abs/1912.00990.
  12. Alexandru Cojocaru, Léo Colisson, Elham Kashefi, and Petros Wallden. QFactory: Classically-Instructed Remote Secret Qubits Preparation. Advances in Cryptology - ASIACRYPT 2019, Lecture Notes in Computer Science, Springer, pages 615-645, 2019. URL: https://doi.org/10.1007/978-3-030-34578-5_22.
  13. Andrea Coladangelo, Koon Tong Goh, and Valerio Scarani. All pure bipartite entangled states can be self-tested. Nature Communications, 8(1):15485, August 2017. URL: https://doi.org/10.1038/ncomms15485.
  14. Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery, and Thomas Vidick. Verifier-on-a-leash: New schemes for verifiable delegated quantum computation, with quasilinear resources. Advances in Cryptology - EUROCRYPT 2019, Lecture Notes in Computer Science, Springer, 11478 LNCS:247-277, 2019. URL: https://doi.org/10.1007/978-3-030-17659-4_9.
  15. Andrea Coladangelo, Thomas Vidick, and Tina Zhang. Non-interactive zero-knowledge arguments for QMA, with preprocessing. In Annual International Cryptology Conference, pages 799-828. Springer, 2020. Google Scholar
  16. Roger Colbeck. Quantum and relativistic protocols for secure multi-party computation. PhD Thesis, University of Cambridge, 2006. URL: http://arxiv.org/abs/0911.3814.
  17. Claude Crépeau, Daniel Gottesman, and Adam Smith. Secure multi-party quantum computation. Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pages 643-652, 2002. URL: https://doi.org/10.1145/509907.510000.
  18. Yevgeniy Dodis, Shai Halevi, Ron D. Rothblum, and Daniel Wichs. Spooky Encryption and Its Applications. Advances in Cryptology - CRYPTO 2016, Lecture Notes in Computer Science, Springer, pages 93-122, 2016. URL: https://doi.org/10.1007/978-3-662-53015-3_4.
  19. Alexandru Gheorghiu and Thomas Vidick. Computationally-secure and composable remote state preparation. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1024-1033. IEEE, 2019. Google Scholar
  20. William T. Gowers and Omid Hatami. Inverse and stability theorems for approximate representations of finite groups. Sbornik: Mathematics, 208(12):1784, 2017. URL: https://doi.org/10.1070/SM8872.
  21. Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP^* = RE. arXiv preprint, 2020. URL: http://arxiv.org/abs/2001.04383.
  22. Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. How to delegate computations: The power of no-signaling proofs. Proceedings of the 46th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 485-494, 2014. URL: https://doi.org/10.1145/2591796.2591809.
  23. Urmila Mahadev. Classical verification of quantum computations. IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 259-267, 2018. URL: https://doi.org/10.1109/FOCS.2018.00033.
  24. Dominic Mayers and Andrew Yao. Self testing quantum apparatus. Quantum Info. Comput., 4(4):273-286, July 2004. URL: https://dl.acm.org/doi/10.5555/2011827.2011830.
  25. M McKague, T H Yang, and V Scarani. Robust self-testing of the singlet. Journal of Physics A: Mathematical and Theoretical, 45(45):455304, October 2012. URL: https://doi.org/10.1088/1751-8113/45/45/455304.
  26. Tony Metger, Yfke Dulek, Andrea Coladangelo, and Rotem Arnon-Friedman. Device-independent quantum key distribution from computational assumptions. arXiv preprint, 2020. URL: http://arxiv.org/abs/2010.04175.
  27. Tony Metger and Thomas Vidick. Self-testing of a single quantum device under computational assumptions. CoRR, 2020. (Full version: https://arxiv.org/abs/2001.09161).
  28. Carl A. Miller and Yaoyun. Shi. Universal security for randomness expansion from the spot-checking protocol. SIAM Journal on Computing, 46(4):1304-1335, 2017. URL: https://doi.org/10.1137/15M1044333.
  29. Sandu Popescu and Daniel Rohrlich. Which states violate Bell’s inequality maximally? Physics Letters A, 169(6):411-414, October 1992. URL: https://doi.org/10.1016/0375-9601(92)90819-8.
  30. Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763-803, 1998. URL: https://doi.org/10.1137/S0097539795280895.
  31. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6), 2009. URL: https://doi.org/10.1145/1568318.1568324.
  32. Ben W Reichardt, Falk Unger, and Umesh Vazirani. Classical command of quantum systems. Nature, 496(7446):456, 2013. URL: https://doi.org/10.1038/nature12035.
  33. Valerio Scarani. Bell Nonlocality. Oxford University Press, 2019. Google Scholar
  34. Stephen J. Summers and Reinhard Werner. Maximal violation of Bell’s inequalities is generic in quantum field theory. Communications in Mathematical Physics, 110(2):247-259, June 1987. URL: https://doi.org/10.1007/BF01207366.
  35. Ivan Šupić and Joseph Bowles. Self-testing of quantum systems: a review. Quantum, 4:337, 2020. Google Scholar
  36. Umesh Vazirani and Thomas Vidick. Certifiable quantum dice: Or, true random number generation secure against quantum adversaries. Proceedings of the 44th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 61-76, 2012. URL: https://doi.org/10.1145/2213977.2213984.
  37. Thomas Vidick and Tina Zhang. Classical proofs of quantum knowledge. arXiv preprint, 2020. URL: http://arxiv.org/abs/2005.01691.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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