Self-testing of a single quantum device under computational assumptions
1Institute for Theoretical Physics, ETH Zürich, 8093 Zürich, Switzerland
2Department of Computing and Mathematical Sciences, California Institute of Technology, CA 91125, United States
| Published: | 2021-09-16, volume 5, page 544 |
| Eprint: | arXiv:2001.09161v3 |
| Doi: | https://doi.org/10.22331/q-2021-09-16-544 |
| Citation: | Quantum 5, 544 (2021). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
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 $\textit{multiple non-communicating}$ parties, which is difficult to enforce in practice, by a $\textit{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.
Featured image: Interactive protocol between classical verifier and untrusted computationally bounded quantum device. If the device passes in the protocol, it must have prepared and measured an EPR state to generate its responses in the protocol. The protocol therefore allows the verifier to certify preparation and measurement of an EPR state in a device-independent way.
► BibTeX data
► References
[1] W. Aiello, S. Bhatt, R. Ostrovsky, and S. R. 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, 463-474 (2000).
https://doi.org/10.1007/3-540-45022-X_39
[2] G. Alagic, A. M. Childs, A. B. Grilo, and S.-H. Hung. ``Non-interactive classical verification of quantum computation'', Preprint (2019). arXiv:1911.08101.
arXiv:1911.08101
[3] M. Ben-Or, C. Crepeau, D. Gottesman, A. Hassidim, and A. Smith. ``Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority'', IEEE 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 249-260 (2006).
https://doi.org/10.1109/FOCS.2006.68
[4] 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), 320-331 (2018). arXiv:1804.00640v3.
https://doi.org/10.1109/FOCS.2018.00038
arXiv:1804.00640v3
[5] J. S. Bell. ``On the Einstein Podolsky Rosen paradox'', Physics Physique Fizika 1, 195–200 (1964).
https://doi.org/10.1103/PhysicsPhysiqueFizika.1.195
[6] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani. ``On the complexity and verification of quantum random circuit sampling'', Nature Physics 15, 159–163 (2019).
https://doi.org/10.1038/s41567-018-0318-2
[7] A. Broadbent and A. B. Grilo. ``QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge'', IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 196–205 (2020).
https://doi.org/10.1109/FOCS46700.2020.00027
[8] Z. Brakerski, V. Koppula, U. Vazirani, and T. Vidick. ``Simpler Proofs of Quantumness'', Preprint (2020). arXiv:2005.04826.
arXiv:2005.04826
[9] K. Bharti, M. Ray, A. Varvitsiotis, N. A. Warsi, A. Cabello, and L.-C. Kwek. ``Robust Self-Testing of Quantum Systems via Noncontextuality Inequalities'', Phys. Rev. Lett. 122, 250403 (2019). arXiv:1812.07265.
https://doi.org/10.1103/PhysRevLett.122.250403
arXiv:1812.07265
[10] A. Cojocaru, L. Colisson, E. Kashefi, and P. Wallden. ``QFactory: Classically-Instructed Remote Secret Qubits Preparation'', Advances in Cryptology - ASIACRYPT 2019, Lecture Notes in Computer Science, Springer, 615-645 (2019). arXiv:1904.06303.
https://doi.org/10.1007/978-3-030-34578-5_22
arXiv:1904.06303
[11] N.-H. Chia, K.-M. Chung, and T. Yamakawa. ``Classical Verification of Quantum Computations with Efficient Verifier'', Preprint (2019). arXiv:1912.00990.
arXiv:1912.00990
[12] A. Coladangelo, A. B. Grilo, S. Jeffery, and T. 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). arXiv:1708.07359.
https://doi.org/10.1007/978-3-030-17659-4_9
arXiv:1708.07359
[13] C. Crépeau, D. Gottesman, and A. Smith. ``Secure Multi-Party Quantum Computation'', Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 643-652 (2002).
https://doi.org/10.1145/509907.510000
[14] A. Coladangelo, K. T. Goh, and V. Scarani. ``All pure bipartite entangled states can be self-tested'', Nature Communications 8, 15485 (2017). arXiv:1611.08062.
https://doi.org/10.1038/ncomms15485
arXiv:1611.08062
[15] R. Colbeck. Quantum and relativistic protocols for secure multi-party computation, PhD Thesis, University of Cambridge (2006). arXiv:0911.3814.
arXiv:0911.3814
[16] A. Coladangelo, T. Vidick, and T. Zhang. ``Non-interactive zero-knowledge arguments for QMA, with preprocessing'', Annual International Cryptology Conference (CRYPTO), 799–828 (2020).
https://doi.org/10.1007/978-3-030-56877-1_28
[17] Y. Dodis, S. Halevi, R. D. Rothblum, and D. Wichs. ``Spooky Encryption and Its Applications'', Advances in Cryptology - CRYPTO 2016, Lecture Notes in Computer Science, Springer, 93-122 (2016).
https://doi.org/10.1007/978-3-662-53015-3_4
[18] W. T. Gowers and O. Hatami. ``Inverse and stability theorems for approximate representations of finite groups'', Sbornik: Mathematics 208, 1784 (2017).
https://doi.org/10.1070/SM8872
[19] A. Gheorghiu and T. Vidick. ``Computationally-secure and composable remote state preparation'', IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 1024–1033 (2019).
https://doi.org/10.1109/FOCS.2019.00066
[20] Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen. ``${MIP}^*={RE}$'', Preprint (2020). arXiv:2001.04383.
arXiv:2001.04383
[21] Y. T. Kalai, R. Raz, and R. 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), 485-494 (2014).
https://doi.org/10.1145/2591796.2591809
[22] U. Mahadev. ``Classical Verification of Quantum Computations'', IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 259-267 (2018). arXiv:1804.01082v2.
https://doi.org/10.1109/FOCS.2018.00033
arXiv:1804.01082v2
[23] T. Metger, Y. Dulek, A. Coladangelo, and R. Arnon-Friedman. ``Device-independent quantum key distribution from computational assumptions'', Preprint (2020). arXiv:2010.04175.
arXiv:2010.04175
[24] C. A. Miller and Y. Shi. ``Universal Security for Randomness Expansion from the Spot-Checking Protocol'', SIAM Journal on Computing 46, 1304-1335 (2017). arXiv:1411.6608.
https://doi.org/10.1137/15M1044333
arXiv:1411.6608
[25] D. Mayers and A. Yao. ``Self Testing Quantum Apparatus'', Quantum Info. Comput. 4, 273-286 (2004). arXiv:quant-ph/0307205.
arXiv:quant-ph/0307205
https://dl.acm.org/doi/10.5555/2011827.2011830
[26] M. McKague, T. H. Yang, and V. Scarani. ``Robust self-testing of the singlet'', Journal of Physics A: Mathematical and Theoretical 45, 455304 (2012).
https://doi.org/10.1088/1751-8113/45/45/455304
[27] A. Natarajan and J. Wright. ``NEEXP in MIP*'', IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 510-518 (2019). arXiv:1904.05870.
https://doi.org/10.1109/FOCS.2019.00039
arXiv:1904.05870
[28] S. Popescu and D. Rohrlich. ``Which states violate Bell's inequality maximally?'', Physics Letters A 169, 411–414 (1992).
https://doi.org/10.1016/0375-9601(92)90819-8
[29] R. Raz. ``A parallel repetition theorem'', SIAM Journal on Computing 27, 763–803 (1998).
https://doi.org/10.1137/S0097539795280895
[30] O. Regev. ``On Lattices, Learning with Errors, Random Linear Codes, and Cryptography'', J. ACM 56 (2009).
https://doi.org/10.1145/1568318.1568324
[31] B. W. Reichardt, F. Unger, and U. Vazirani. ``Classical command of quantum systems'', Nature 496, 456 (2013). arXiv:1209.0449.
https://doi.org/10.1038/nature12035
arXiv:1209.0449
[32] I. Šupić and J. Bowles. ``Self-testing of quantum systems: a review'', Preprint (2019). arXiv:1904.10042.
https://doi.org/10.22331/q-2020-09-30-337
arXiv:1904.10042
[33] V. Scarani. Bell Nonlocality, Oxford University Press (2019).
[34] S. J. Summers and R. Werner. ``Maximal violation of Bell's inequalities is generic in quantum field theory'', Communications in Mathematical Physics 110, 247–259 (1987).
https://doi.org/10.1007/BF01207366
[35] T. Vidick. The complexity of entangled games. PhD thesis, 2011.
https://digitalassets.lib.berkeley.edu/etd/ucb/text/Vidick_berkeley_0028E_11907.pdf
[36] U. Vazirani and T. 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), 61-76 (2012). arXiv:1111.6054.
https://doi.org/10.1145/2213977.2213984
arXiv:1111.6054
[37] T. Vidick and T. Zhang. ``Classical proofs of quantum knowledge'', Preprint (2020). arXiv:2005.01691.
arXiv:2005.01691
[38] M. Wilde. ``From Classical to Quantum Shannon Theory'', Preprint (2011). arXiv:1106.1445v8.
https://doi.org/10.1017/9781316809976.001
arXiv:1106.1445v8
Cited by
[1] Xiao-Min Hu, Yi Xie, Atul Singh Arora, Ming-Zhong Ai, Kishor Bharti, Jie Zhang, Wei Wu, Ping-Xing Chen, Jin-Ming Cui, Bi-Heng Liu, Yun-Feng Huang, Chuan-Feng Li, Guang-Can Guo, Jérémie Roland, Adán Cabello, and Leong-Chuan Kwek, "Self-testing of a single quantum system from theory to experiment", npj Quantum Information 9 1, 103 (2023).
[2] Yun-Guang Han, Zihao Li, Yukun Wang, and Huangjun Zhu, "Optimal verification of the Bell state and Greenberger–Horne–Zeilinger states in untrusted quantum networks", npj Quantum Information 7 1, 164 (2021).
[3] Manuel B. Santos, Paulo Mateus, and Armando N. Pinto, "Quantum Oblivious Transfer: A Short Review", Entropy 24 7, 945 (2022).
[4] Thomas Vidick and Tina Zhang, Lecture Notes in Computer Science 12697, 630 (2021) ISBN:978-3-030-77885-9.
[5] Aby Philip, Eneet Kaur, Peter Bierhorst, and Mark M. Wilde, "Multipartite Intrinsic Non-Locality and Device-Independent Conference Key Agreement", Quantum 7, 898 (2023).
[6] Zvika Brakerski, Alexandru Gheorghiu, Gregory D. Kahanamoku-Meyer, Eitan Porat, and Thomas Vidick, Lecture Notes in Computer Science 14085, 162 (2023) ISBN:978-3-031-38553-7.
[7] Anne Broadbent and Peter Yuen, "Device-independent oblivious transfer from the bounded-quantum-storage-model and computational assumptions", New Journal of Physics 25 5, 053019 (2023).
[8] Anand Natarajan and Tina Zhang, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) 1342 (2023) ISBN:979-8-3503-1894-4.
[9] Dian Wu, Qi Zhao, Can Wang, Liang Huang, Yang-Fan Jiang, Bing Bai, You Zhou, Xue-Mei Gu, Feng-Ming Liu, Ying-Qiu Mao, Qi-Chao Sun, Ming-Cheng Chen, Jun Zhang, Cheng-Zhi Peng, Xiao-Bo Zhu, Qiang Zhang, Chao-Yang Lu, and Jian-Wei Pan, "Closing the Locality and Detection Loopholes in Multiparticle Entanglement Self-Testing", Physical Review Letters 128 25, 250401 (2022).
[10] Akihiro Mizutani, Yuki Takeuchi, Ryo Hiromasa, Yusuke Aikawa, and Seiichiro Tani, "Computational self-testing for entangled magic states", Physical Review A 106 1, L010601 (2022).
[11] Jiayu Zhang, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) 46 (2022) ISBN:978-1-6654-5519-0.
[12] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang, Proceedings of the 55th Annual ACM Symposium on Theory of Computing 1617 (2023) ISBN:9781450399135.
[13] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, "Noisy intermediate-scale quantum algorithms", Reviews of Modern Physics 94 1, 015004 (2022).
[14] Kishor Bharti, Maharshi Ray, Zhen-Peng Xu, Masahito Hayashi, Leong-Chuan Kwek, and Adán Cabello, "Graph-Theoretic Approach for Self-Testing in Bell Scenarios", PRX Quantum 3 3, 030344 (2022).
[15] Tony Metger, Yfke Dulek, Andrea Coladangelo, and Rotem Arnon-Friedman, "Device-independent quantum key distribution from computational assumptions", New Journal of Physics 23 12, 123021 (2021).
[16] Alexandru Gheorghiu and Matty J. Hoban, "Estimating the entropy of shallow circuit outputs is hard", arXiv:2002.12814, (2020).
[17] Alexandru Gheorghiu, Tony Metger, and Alexander Poremba, "Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more", arXiv:2201.13445, (2022).
[18] Honghao Fu, Daochen Wang, and Qi Zhao, "Parallel self-testing of EPR pairs under computational assumptions", arXiv:2201.13430, (2022).
[19] Thomas Vidick and Tina Zhang, "Classical proofs of quantum knowledge", arXiv:2005.01691, (2020).
[20] Yu Cai, Baichu Yu, Pooja Jayachandran, Nicolas Brunner, Valerio Scarani, and Jean-Daniel Bancal, "Entanglement for any definition of two subsystems", Physical Review A 103 5, 052432 (2021).
[21] Xiao-Min Hu, Yi Xie, Atul Singh Arora, Ming-Zhong Ai, Kishor Bharti, Jie Zhang, Wei Wu, Ping-Xing Chen, Jin-Ming Cui, Bi-Heng Liu, Yun-Feng Huang, Chuan-Feng Li, Guang-Can Guo, Jérémie Roland, Adán Cabello, and Leong-Chuan Kwek, "Self-Testing of a Single Quantum System: Theory and Experiment", arXiv:2203.09003, (2022).
[22] Anand Natarajan and Tina Zhang, "Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification", arXiv:2303.01545, (2023).
[23] Tomoyuki Morimae, "Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center", arXiv:2003.10712, (2020).
[24] Tomoyuki Morimae and Yuki Takeuchi, "Trusted center verification model and classical channel remote state preparation", arXiv:2008.05033, (2020).
[25] Xingyu Yan, Licheng Wang, Lize Gu, Ziyi Li, and Jingwen Suo, "Post-Quantum $\kappa$-to-1 Trapdoor Claw-free Functions from Extrapolated Dihedral Cosets", arXiv:2211.16993, (2022).
[26] Tony Metger, Anand Natarajan, and Tina Zhang, "Succinct arguments for QMA from standard assumptions via compiled nonlocal games", arXiv:2404.19754, (2024).
The above citations are from Crossref's cited-by service (last updated successfully 2024-05-13 20:23:04) and SAO/NASA ADS (last updated successfully 2024-05-13 20:23:04). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.