Abstract | ||
---|---|---|
We give a protocol for producing certifiable randomness from a single untrusted quantum device that is polynomial-time bounded. 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. 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. |
Year | Venue | Field |
---|---|---|
2018 | arXiv: Quantum Physics | Quantum,Quantum entanglement,Computer science,Theoretical computer science,Verifiable secret sharing,Adversary,Bounded function,Randomness,Learning with errors |
DocType | Volume | Citations |
Journal | abs/1804.00640 | 1 |
PageRank | References | Authors |
0.35 | 13 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zvika Brakerski | 1 | 2353 | 92.25 |
Paul Christiano | 2 | 340 | 19.40 |
Urmila Mahadev | 3 | 1 | 0.69 |
Umesh V. Vazirani | 4 | 3338 | 610.23 |
Thomas Vidick | 5 | 377 | 31.69 |