A Caltech Library Service

Self-testing of a single quantum device under computational assumptions

Metger, Tony and Vidick, Thomas (2021) Self-testing of a single quantum device under computational assumptions. Quantum, 5 . Art. No. 544. ISSN 2521-327X. doi:10.22331/q-2021-09-16-544.

[img] PDF (2 Sep 2021) - Published Version
Creative Commons Attribution.

[img] PDF (24 Jan 2020) - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information: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. A short version of this work has appeared in the Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). We thank Andrea Coladangelo, Andru Gheorghiu, Anand Natarajan, and Tina Zhang for helpful discussions; Andrea Coladangelo, Andru Gheorghiu, Urmila Mahadev, Akihiro Mizutani, and the Quantum referees for valuable comments on the manuscript; and Lídia del Rio for pointing out the reference [BRV+19]. Tony Metger acknowledges support from ETH Zürich and the ETH Foundation through the Excellence Scholarship & Opportunity Programme, from the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028), and from the National Centres of Competence in Research (NCCRs) QSIT and SwissMAP. Thomas Vidick is 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). Most of this work was carried out while Tony Metger was a visiting student researcher at the Department of Computing and Mathematical Sciences at Caltech.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Swiss National Science Foundation (SNSF)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Canadian Institute for Advanced Research (CIFAR)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0161
Record Number:CaltechAUTHORS:20200417-132557882
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:102608
Deposited By: George Porter
Deposited On:17 Apr 2020 20:58
Last Modified:05 Oct 2021 20:03

Repository Staff Only: item control page