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.
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] 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 (NISQ) algorithms”, arXiv:2101.08448.
[2] Alexandru Gheorghiu and Matty J. Hoban, “Estimating the entropy of shallow circuit outputs is hard”, arXiv:2002.12814.
[3] Thomas Vidick and Tina Zhang, “Classical proofs of quantum knowledge”, arXiv:2005.01691.
[4] 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).
[5] Tony Metger, Yfke Dulek, Andrea Coladangelo, and Rotem Arnon-Friedman, “Device-independent quantum key distribution from computational assumptions”, arXiv:2010.04175.
[6] Tomoyuki Morimae, “Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center”, arXiv:2003.10712.
[7] Tomoyuki Morimae and Yuki Takeuchi, “Trusted center verification model and classical channel remote state preparation”, arXiv:2008.05033.
[8] 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.
The above citations are from SAO/NASA ADS (last updated successfully 2021-09-16 17:11:41). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2021-09-16 17:11:40: Could not fetch cited-by data for 10.22331/q-2021-09-16-544 from Crossref. This is normal if the DOI was registered recently.
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.
PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.
Source: https://quantum-journal.org/papers/q-2021-09-16-544/
