# Self-testing of a single quantum device under computational assumptions

Tony Metger1 and Thomas Vidick2

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

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Updated version: The authors have uploaded version v4 of this work to the arXiv which may contain updates or corrections not contained in the published version v3. The authors left the following comment on the arXiv:
58 pages, published in Quantum

### 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.

### ► 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] 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).

[2] Manuel B. Santos, Paulo Mateus, and Armando N. Pinto, "Quantum Oblivious Transfer: A Short Review", Entropy 24 7, 945 (2022).

[3] 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).

[4] 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).

[5] 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).

[6] Thomas Vidick and Tina Zhang, "Classical proofs of quantum knowledge", arXiv:2005.01691.

[7] 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).

[8] Alexandru Gheorghiu and Matty J. Hoban, "Estimating the entropy of shallow circuit outputs is hard", arXiv:2002.12814.

[9] 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).

[10] Kishor Bharti, Maharshi Ray, Zhen-Peng Xu, Masahito Hayashi, Leong-Chuan Kwek, and Adán Cabello, "Graph-Theoretic Framework for Self-Testing in Bell Scenarios", arXiv:2104.13035.

[11] 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.

[12] 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.

[13] Tomoyuki Morimae, "Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center", arXiv:2003.10712.

[14] Tomoyuki Morimae and Yuki Takeuchi, "Trusted center verification model and classical channel remote state preparation", arXiv:2008.05033.

The above citations are from Crossref's cited-by service (last updated successfully 2022-10-04 15:48:22) and SAO/NASA ADS (last updated successfully 2022-10-04 15:48:23). The list may be incomplete as not all publishers provide suitable and complete citation data.