CaltechAUTHORS
  A Caltech Library Service

A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device

Brakerski, Zvika and Christiano, Paul and Mahadev, Urmila and Vazirani, Umesh and Vidick, Thomas (2018) A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 320-331. ISBN 9781538642306. https://resolver.caltech.edu/CaltechAUTHORS:20190201-143229032

[img] PDF - Submitted Version
See Usage Policy.

474Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190201-143229032

Abstract

We give a protocol for producing certifiable randomness from a single untrusted quantum device that is polynomial-time bounded. The randomness is certified to be statistically close to uniform from the point of view of any computationally unbounded quantum adversary, that may share entanglement with the quantum device. The protocol relies on the existence of post-quantum secure trapdoor claw-free functions, and introduces a new primitive for constraining the power of an untrusted quantum device. We then show how to construct this primitive based on the hardness of the learning with errors (LWE) problem. The randomness protocol can also be used as the basis for an efficiently verifiable "quantum supremacy" proposal, thus answering an outstanding challenge in the field.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/focs.2018.00038DOIArticle
https://arxiv.org/abs/1804.00640arXivDiscussion Paper
ORCID:
AuthorORCID
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2018 IEEE. A full version of this extended abstact can be found at [BCM+18].
Group:Institute for Quantum Information and Matter, IQIM
Subject Keywords:randomness; quantum information; cryptography
Record Number:CaltechAUTHORS:20190201-143229032
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190201-143229032
Official Citation:Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani and T. Vidick, "A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device," 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), Paris, 2018, pp. 320-331. doi: 10.1109/FOCS.2018.00038
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:92582
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:01 Feb 2019 23:08
Last Modified:03 Oct 2019 20:46

Repository Staff Only: item control page