{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T04:08:42Z","timestamp":1781582922369,"version":"3.54.5"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T00:00:00Z","timestamp":1628726400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>We consider a new model for the testing of untrusted quantum devices, consisting of a single polynomial time bounded quantum device interacting with a classical polynomial time verifier. In this model, we propose solutions to two tasks\u2014a protocol for efficient classical verification that the untrusted device is \u201ctruly quantum\u201d and a protocol for producing certifiable randomness from a single untrusted quantum device. Our solution relies on the existence of a new cryptographic primitive for constraining the power of an untrusted quantum device: post-quantum secure trapdoor claw-free functions that must satisfy an adaptive hardcore bit property. We show how to construct this primitive based on the hardness of the learning with errors (LWE) problem.<\/jats:p>","DOI":"10.1145\/3441309","type":"journal-article","created":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T19:06:46Z","timestamp":1628795206000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device"],"prefix":"10.1145","volume":"68","author":[{"given":"Zvika","family":"Brakerski","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Christiano","sequence":"additional","affiliation":[{"name":"OpenAI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Urmila","family":"Mahadev","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Umesh","family":"Vazirani","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Vidick","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,8,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993682"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3135595.3135617"},{"key":"e_1_2_1_3_1","volume-title":"Interactive proofs for quantum computations. Arxiv preprint arXiv:0810.5375","author":"Aharonov Dorit","year":"2008","unstructured":"Dorit Aharonov , Micahel Ben-Or , and Elad Eban . 2008. Interactive proofs for quantum computations. Arxiv preprint arXiv:0810.5375 ( 2008 ). Dorit Aharonov, Micahel Ben-Or, and Elad Eban. 2008. Interactive proofs for quantum computations. Arxiv preprint arXiv:0810.5375 (2008)."},{"key":"e_1_2_1_4_1","volume-title":"Interactive proofs for quantum computations. Arxiv preprint 1704.04487","author":"Aharonov Dorit","year":"2017","unstructured":"Dorit Aharonov , Michael Ben-Or , Elad Eban , and Urmila Mahadev . 2017. Interactive proofs for quantum computations. Arxiv preprint 1704.04487 ( 2017 ). Dorit Aharonov, Michael Ben-Or, Elad Eban, and Urmila Mahadev. 2017. Interactive proofs for quantum computations. Arxiv preprint 1704.04487 (2017)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-017-02307-4"},{"key":"e_1_2_1_7_1","volume-title":"Quantum supremacy using a programmable superconducting processor. Nature 574 (10","author":"Arute Frank","year":"2019","unstructured":"Frank Arute , Kunal Arya , Ryan Babbush , Dave Bacon , Joseph Bardin , Rami Barends , Rupak Biswas , Sergio Boixo , Fernando Brandao , David Buell , Brian Burkett , Yu Chen , Zijun Chen , Ben Chiaro , Roberto Collins , William Courtney , Andrew Dunsworth , Edward Farhi , Brooks Foxen , and John Martinis . 2019. Quantum supremacy using a programmable superconducting processor. Nature 574 (10 2019 ), 505\u2013510. DOI:DOI:https:\/\/doi.org\/10.1038\/s41586-019-1666-5 Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando Brandao, David Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, and John Martinis. 2019. Quantum supremacy using a programmable superconducting processor. Nature 574 (10 2019), 505\u2013510. DOI:DOI:https:\/\/doi.org\/10.1038\/s41586-019-1666-5"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-018-0019-0"},{"key":"e_1_2_1_9_1","volume-title":"Characterizing quantum supremacy in near-term devices. arXiv:1608.00263","author":"Boixo Sergio","year":"2016","unstructured":"Sergio Boixo , Sergei V. Isakov , Vadim N. Smelyanskiy , Ryan Babbush , Nan Ding , Zhang Jiang , John M. Martinis , and Hartmut Neven . 2016. Characterizing quantum supremacy in near-term devices. arXiv:1608.00263 ( 2016 ). Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, John M. Martinis, and Hartmut Neven. 2016. Characterizing quantum supremacy in near-term devices. arXiv:1608.00263 (2016)."},{"key":"e_1_2_1_10_1","volume-title":"On the complexity and verification of quantum random circuit sampling. Nat. Phys. 15 (02","author":"Bouland Adam","year":"2019","unstructured":"Adam Bouland , Bill Fefferman , Chinmay Nirkhe , and Umesh Vazirani . 2019. On the complexity and verification of quantum random circuit sampling. Nat. Phys. 15 (02 2019 ). DOI:DOI:https:\/\/doi.org\/10.1038\/s41567-018-0318-2 Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. 2019. On the complexity and verification of quantum random circuit sampling. Nat. Phys. 15 (02 2019). DOI:DOI:https:\/\/doi.org\/10.1038\/s41567-018-0318-2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488680"},{"key":"e_1_2_1_12_1","volume-title":"Universal blind quantum computation. Arxiv preprint arXiv:0807.4154","author":"Broadbent Anne","year":"2008","unstructured":"Anne Broadbent , Joseph F. Fitzsimons , and Elham Kashefi . 2008. Universal blind quantum computation. Arxiv preprint arXiv:0807.4154 ( 2008 ). Anne Broadbent, Joseph F. Fitzsimons, and Elham Kashefi. 2008. Universal blind quantum computation. Arxiv preprint arXiv:0807.4154 (2008)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25385-0_1"},{"key":"e_1_2_1_14_1","volume-title":"Delegated pseudo-secret random qubit generator. arXiv preprint arXiv:1802.08759","author":"Cojocaru Alexandru","year":"2018","unstructured":"Alexandru Cojocaru , L\u00e9o Colisson , Elham Kashefi , and Petros Wallden . 2018. Delegated pseudo-secret random qubit generator. arXiv preprint arXiv:1802.08759 ( 2018 ). Alexandru Cojocaru, L\u00e9o Colisson, Elham Kashefi, and Petros Wallden. 2018. Delegated pseudo-secret random qubit generator. arXiv preprint arXiv:1802.08759 (2018)."},{"key":"e_1_2_1_15_1","volume-title":"QFactory: classically-instructed remote secret qubits preparation. arXiv preprint arXiv:1904.06303","author":"Cojocaru Alexandru","year":"2019","unstructured":"Alexandru Cojocaru , L\u00e9o Colisson , Elham Kashefi , and Petros Wallden . 2019. QFactory: classically-instructed remote secret qubits preparation. arXiv preprint arXiv:1904.06303 ( 2019 ). Alexandru Cojocaru, L\u00e9o Colisson, Elham Kashefi, and Petros Wallden. 2019. QFactory: classically-instructed remote secret qubits preparation. arXiv preprint arXiv:1904.06303 (2019)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spa.2012.06.009"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.96.012303"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40041-4_5"},{"key":"e_1_2_1_20_1","volume-title":"Computationally-secure and composable remote state preparation. arXiv preprint arXiv:1904.06320","author":"Gheorghiu Alexandru","year":"2019","unstructured":"Alexandru Gheorghiu and Thomas Vidick . 2019. Computationally-secure and composable remote state preparation. arXiv preprint arXiv:1904.06320 ( 2019 ). Alexandru Gheorghiu and Thomas Vidick. 2019. Computationally-secure and composable remote state preparation. arXiv preprint arXiv:1904.06320 (2019)."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the International Conference on Supercomputing, Andrew Chi-Chih Yao (Ed.)","author":"Goldwasser Shafi","year":"2010","unstructured":"Shafi Goldwasser , Yael Tauman Kalai , Chris Peikert , and Vinod Vaikuntanathan . 2010 . Robustness of the learning with errors assumption . In Proceedings of the International Conference on Supercomputing, Andrew Chi-Chih Yao (Ed.) . Tsinghua University Press, 230\u2013240. Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan. 2010. Robustness of the learning with errors assumption. In Proceedings of the International Conference on Supercomputing, Andrew Chi-Chih Yao (Ed.). Tsinghua University Press, 230\u2013240."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Advances in Cryptology Conference (Lecture Notes in Computer Science), G. R. Blakley and David Chaum (Eds.)","volume":"196","author":"Goldwasser Shafi","unstructured":"Shafi Goldwasser , Silvio Micali , and Ronald L. Rivest . 1984. A \u201cParadoxical\u201d solution to the signature problem (abstract) . In Proceedings of the Advances in Cryptology Conference (Lecture Notes in Computer Science), G. R. Blakley and David Chaum (Eds.) , Vol. 196 . Springer, 467. DOI:DOI:https:\/\/doi.org\/10.1007\/3-540-39568-7_37 Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. 1984. A \u201cParadoxical\u201d solution to the signature problem (abstract). In Proceedings of the Advances in Cryptology Conference (Lecture Notes in Computer Science), G. R. Blakley and David Chaum (Eds.), Vol. 196. Springer, 467. DOI:DOI:https:\/\/doi.org\/10.1007\/3-540-39568-7_37"},{"key":"e_1_2_1_23_1","volume-title":"Creating superpositions that correspond to efficiently integrable probability distributions. arXiv preprint quant-ph\/0208112","author":"Grover Lov","year":"2002","unstructured":"Lov Grover and Terry Rudolph . 2002. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv preprint quant-ph\/0208112 ( 2002 ). Lov Grover and Terry Rudolph. 2002. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv preprint quant-ph\/0208112 (2002)."},{"key":"e_1_2_1_24_1","volume-title":"Harrow and Ashley Montanaro","author":"Aram","year":"2017","unstructured":"Aram W. Harrow and Ashley Montanaro . 2017 . Quantum computational supremacy. Nature 549, 7671 (2017), 203. Aram W. Harrow and Ashley Montanaro. 2017. Quantum computational supremacy. Nature 549, 7671 (2017), 203."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1964621.1964651"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.60.1103"},{"key":"e_1_2_1_27_1","volume-title":"Classical homomorphic encryption for quantum circuits. arXiv preprint arXiv:1708.02130","author":"Mahadev Urmila","year":"2017","unstructured":"Urmila Mahadev . 2017. Classical homomorphic encryption for quantum circuits. arXiv preprint arXiv:1708.02130 ( 2017 ). Urmila Mahadev. 2017. Classical homomorphic encryption for quantum circuits. arXiv preprint arXiv:1708.02130 (2017)."},{"key":"e_1_2_1_28_1","volume-title":"Classical verification of quantum computations. arXiv preprint arXiv:1804.01082","author":"Mahadev Urmila","year":"2018","unstructured":"Urmila Mahadev . 2018. Classical verification of quantum computations. arXiv preprint arXiv:1804.01082 ( 2018 ). Urmila Mahadev. 2018. Classical verification of quantum computations. arXiv preprint arXiv:1804.01082 (2018)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_41"},{"key":"e_1_2_1_30_1","volume-title":"Miller and Yaoyun Shi","author":"Carl","year":"2014","unstructured":"Carl A. Miller and Yaoyun Shi . 2014 . Universal security for randomness expansion from the spot-checking protocol. arXiv preprint arXiv:1411.6608 (2014). Carl A. Miller and Yaoyun Shi. 2014. Universal security for randomness expansion from the spot-checking protocol. arXiv preprint arXiv:1411.6608 (2014)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2885493"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1044333"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536461"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055489"},{"key":"e_1_2_1_35_1","volume-title":"D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manninget al.2010. Random numbers certified by Bell\u2019s theorem.Nature 464, 7291","author":"Pironio S.","year":"2010","unstructured":"S. Pironio , A. Acin , S. Massar , A. Boyer De La Giroday , D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manninget al.2010. Random numbers certified by Bell\u2019s theorem.Nature 464, 7291 ( 2010 ). S. Pironio, A. Acin, S. Massar, A. Boyer De La Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manninget al.2010. Random numbers certified by Bell\u2019s theorem.Nature 464, 7291 (2010)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1104017"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324"},{"key":"e_1_2_1_38_1","unstructured":"B. Reichardt F. Unger and U. Vazirani. 2012. A classical leash for a quantum system. Arxiv preprint arXiv:1209.0448 (2012).  B. Reichardt F. Unger and U. Vazirani. 2012. A classical leash for a quantum system. Arxiv preprint arXiv:1209.0448 (2012)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2796561.2796598"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581144"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2845098"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2032797"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213984"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.140501"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/2505455"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3441309","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3441309","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:04Z","timestamp":1750197784000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3441309"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,12]]},"references-count":44,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3441309"],"URL":"https:\/\/doi.org\/10.1145\/3441309","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,12]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}