{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T18:01:23Z","timestamp":1775671283746,"version":"3.50.1"},"reference-count":38,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,9,16]],"date-time":"2021-09-16T00:00:00Z","timestamp":1631750400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["PHY-1125565"],"award-info":[{"award-number":["PHY-1125565"]}]},{"DOI":"10.13039\/100000936","name":"Gordon and Betty Moore Foundation","doi-asserted-by":"crossref","award":["GBMF-12500028"],"award-info":[{"award-number":["GBMF-12500028"]}],"id":[{"id":"10.13039\/100000936","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["CCF-1553477"],"award-info":[{"award-number":["CCF-1553477"]}]},{"name":"AFOSR YIP","award":["FA9550-16-1-0495"],"award-info":[{"award-number":["FA9550-16-1-0495"]}]},{"DOI":"10.13039\/100014036","name":"MURI","doi-asserted-by":"crossref","award":["FA9550-18-1-0161"],"award-info":[{"award-number":["FA9550-18-1-0161"]}],"id":[{"id":"10.13039\/100014036","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mtext class=\"MJX-tex-mathit\" mathvariant=\"italic\">multiple non-communicating<\/mml:mtext><\/mml:mrow><\/mml:math> parties, which is difficult to enforce in practice, by a <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mtext class=\"MJX-tex-mathit\" mathvariant=\"italic\">single computationally bounded<\/mml:mtext><\/mml:mrow><\/mml:math> 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.<\/jats:p>","DOI":"10.22331\/q-2021-09-16-544","type":"journal-article","created":{"date-parts":[[2021,9,16]],"date-time":"2021-09-16T17:25:25Z","timestamp":1631813125000},"page":"544","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":21,"title":["Self-testing of a single quantum device under computational assumptions"],"prefix":"10.22331","volume":"5","author":[{"given":"Tony","family":"Metger","sequence":"first","affiliation":[{"name":"Institute for Theoretical Physics, ETH Z\u00fcrich, 8093 Z\u00fcrich, Switzerland"}]},{"given":"Thomas","family":"Vidick","sequence":"additional","affiliation":[{"name":"Department of Computing and Mathematical Sciences, California Institute of Technology, CA 91125, United States"}]}],"member":"9598","published-online":{"date-parts":[[2021,9,16]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1007\/3-540-45022-X_39"},{"key":"1","doi-asserted-by":"crossref","unstructured":"G. Alagic, A. M. Childs, A. B. Grilo, and S.-H. Hung. ``Non-interactive classical verification of quantum computation'', Preprint (2019). arXiv:1911.08101.","DOI":"10.1007\/978-3-030-64381-2_6"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1109\/FOCS.2006.68"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1109\/FOCS.2018.00038"},{"key":"4","doi-asserted-by":"publisher","unstructured":"J. S. Bell. ``On the Einstein Podolsky Rosen paradox'', Physics Physique Fizika 1, 195\u2013200 (1964).","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"5","doi-asserted-by":"publisher","unstructured":"A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani. ``On the complexity and verification of quantum random circuit sampling'', Nature Physics 15, 159\u2013163 (2019).","DOI":"10.1038\/s41567-018-0318-2"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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\u2013205 (2020).","DOI":"10.1109\/FOCS46700.2020.00027"},{"key":"7","unstructured":"Z. Brakerski, V. Koppula, U. Vazirani, and T. Vidick. ``Simpler Proofs of Quantumness'', Preprint (2020). arXiv:2005.04826."},{"key":"8","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.122.250403"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/978-3-030-34578-5_22"},{"key":"10","doi-asserted-by":"crossref","unstructured":"N.-H. Chia, K.-M. Chung, and T. Yamakawa. ``Classical Verification of Quantum Computations with Efficient Verifier'', Preprint (2019). arXiv:1912.00990.","DOI":"10.1007\/978-3-030-64381-2_7"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/978-3-030-17659-4_9"},{"key":"12","doi-asserted-by":"publisher","unstructured":"C. Cr\u00e9peau, D. Gottesman, and A. Smith. ``Secure Multi-Party Quantum Computation'', Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 643-652 (2002).","DOI":"10.1145\/509907.510000"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/ncomms15485"},{"key":"14","unstructured":"R. Colbeck. Quantum and relativistic protocols for secure multi-party computation, PhD Thesis, University of Cambridge (2006). arXiv:0911.3814."},{"key":"15","doi-asserted-by":"publisher","unstructured":"A. Coladangelo, T. Vidick, and T. Zhang. ``Non-interactive zero-knowledge arguments for QMA, with preprocessing'', Annual International Cryptology Conference (CRYPTO), 799\u2013828 (2020).","DOI":"10.1007\/978-3-030-56877-1_28"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1007\/978-3-662-53015-3_4"},{"key":"17","doi-asserted-by":"publisher","unstructured":"W. T. Gowers and O. Hatami. ``Inverse and stability theorems for approximate representations of finite groups'', Sbornik: Mathematics 208, 1784 (2017).","DOI":"10.1070\/SM8872"},{"key":"18","doi-asserted-by":"publisher","unstructured":"A. Gheorghiu and T. Vidick. ``Computationally-secure and composable remote state preparation'', IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 1024\u20131033 (2019).","DOI":"10.1109\/FOCS.2019.00066"},{"key":"19","unstructured":"Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen. ``${MIP}^*={RE}$'', Preprint (2020). arXiv:2001.04383."},{"key":"20","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1145\/2591796.2591809"},{"key":"21","doi-asserted-by":"publisher","unstructured":"U. Mahadev. ``Classical Verification of Quantum Computations'', IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 259-267 (2018). arXiv:1804.01082v2.","DOI":"10.1109\/FOCS.2018.00033"},{"key":"22","unstructured":"T. Metger, Y. Dulek, A. Coladangelo, and R. Arnon-Friedman. ``Device-independent quantum key distribution from computational assumptions'', Preprint (2020). arXiv:2010.04175."},{"key":"23","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1137\/15M1044333"},{"key":"24","doi-asserted-by":"crossref","unstructured":"D. Mayers and A. Yao. ``Self Testing Quantum Apparatus'', Quantum Info. Comput. 4, 273-286 (2004). arXiv:quant-ph\/0307205.","DOI":"10.26421\/QIC4.4-3"},{"key":"25","doi-asserted-by":"publisher","unstructured":"M. McKague, T. H. Yang, and V. Scarani. ``Robust self-testing of the singlet'', Journal of Physics A: Mathematical and Theoretical 45, 455304 (2012).","DOI":"10.1088\/1751-8113\/45\/45\/455304"},{"key":"26","doi-asserted-by":"publisher","unstructured":"A. Natarajan and J. Wright. ``NEEXP in MIP*'', IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 510-518 (2019). arXiv:1904.05870.","DOI":"10.1109\/FOCS.2019.00039"},{"key":"27","doi-asserted-by":"publisher","unstructured":"S. Popescu and D. Rohrlich. ``Which states violate Bell's inequality maximally?'', Physics Letters A 169, 411\u2013414 (1992).","DOI":"10.1016\/0375-9601(92)90819-8"},{"key":"28","doi-asserted-by":"publisher","unstructured":"R. Raz. ``A parallel repetition theorem'', SIAM Journal on Computing 27, 763\u2013803 (1998).","DOI":"10.1137\/S0097539795280895"},{"key":"29","doi-asserted-by":"publisher","unstructured":"O. Regev. ``On Lattices, Learning with Errors, Random Linear Codes, and Cryptography'', J. ACM 56 (2009).","DOI":"10.1145\/1568318.1568324"},{"key":"30","doi-asserted-by":"publisher","unstructured":"B. W. Reichardt, F. Unger, and U. Vazirani. ``Classical command of quantum systems'', Nature 496, 456 (2013). arXiv:1209.0449.","DOI":"10.1038\/nature12035"},{"key":"31","doi-asserted-by":"publisher","unstructured":"I. \u0160upi\u0107 and J. Bowles. ``Self-testing of quantum systems: a review'', Preprint (2019). arXiv:1904.10042.","DOI":"10.22331\/q-2020-09-30-337"},{"key":"32","doi-asserted-by":"crossref","unstructured":"V. Scarani. Bell Nonlocality, Oxford University Press (2019).","DOI":"10.1093\/oso\/9780198788416.001.0001"},{"key":"33","doi-asserted-by":"publisher","unstructured":"S. J. Summers and R. Werner. ``Maximal violation of Bell's inequalities is generic in quantum field theory'', Communications in Mathematical Physics 110, 247\u2013259 (1987).","DOI":"10.1007\/BF01207366"},{"key":"34","unstructured":"T. Vidick. The complexity of entangled games. PhD thesis, 2011."},{"key":"35","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/2213977.2213984"},{"key":"36","unstructured":"T. Vidick and T. Zhang. ``Classical proofs of quantum knowledge'', Preprint (2020). arXiv:2005.01691."},{"key":"37","doi-asserted-by":"publisher","unstructured":"M. Wilde. ``From Classical to Quantum Shannon Theory'', Preprint (2011). arXiv:1106.1445v8.","DOI":"10.1017\/9781316809976.001"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-09-16-544\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,9,16]],"date-time":"2021-09-16T17:26:11Z","timestamp":1631813171000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-09-16-544\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,16]]},"references-count":38,"URL":"https:\/\/doi.org\/10.22331\/q-2021-09-16-544","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,16]]},"article-number":"544"}}