Realistic noise-tolerant randomness amplification using finite number of devices
Abstract
Randomness is a fundamental concept, with implications from security of modern data systems, to fundamental laws of nature and even the philosophy of science. Randomness is called certified if it describes events that cannot be pre-determined by an external adversary. It is known that weak certified randomness can be amplified to nearly ideal randomness using quantum-mechanical systems. However, so far, it was unclear whether randomness amplification is a realistic task, as the existing proposals either do not tolerate noise or require an unbounded number of different devices. Here we provide an error-tolerant protocol using a finite number of devices for amplifying arbitrary weak randomness into nearly perfect random bits, which are secure against a no-signalling adversary. The correctness of the protocol is assessed by violating a Bell inequality, with the degree of violation determining the noise tolerance threshold. An experimental realization of the protocol is within reach of current technology.
Additional Information
© 2016 Macmillan Publishers Limited. This work is licensed under a Creative Commons Attribution 4.0 International License. The images or other third party material in this article are included in the article's Creative Commons license, unless indicated otherwise in the credit line; if the material is not included under the Creative Commons license, users will need to obtain permission from the license holder to reproduce the material. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/ Received 01 February 2016; Accepted 16 March 2016; Published 21 April 2016. We thank Rotem Arnon-Friedman for discussions. The work is supported by ERC AdG grant QOLAPS, EC grant RAQUEL and by Foundation for Polish Science TEAM project co-financed by the EU European Regional Development Fund. F.G.S.L.B. acknowledges support from EPSRC and Polish Ministry of Science and Higher Education Grant no. IdP2011 000361. Part of this work was done in the National Quantum Information Center of Gdańsk. Part of this work was done when F.G.S.L.B., R.R., K.H. and M.H. attended the programme 'Mathematical Challenges in Quantum Information' at the Isaac Newton Institute for Mathematical Sciences in the University of Cambridge. Another part was done in the programme 'Quantum Hamiltonian Complexity' in the Simons Institute for the Theory of Computing. Finally, M.H. thanks the Department of Physics and Astronomy and the Department of Computer Science of UCL, where part of this work was also performed, for hospitality. Author contributions: F.G.S.L.B. and M.H. conceptualized central ideas, all authors contributed extensively to the work presented in the paper. The authors declare no competing financial interests.Attached Files
Published - ncomms11345.pdf
Supplemental Material - ncomms11345-s1.pdf
Files
Name | Size | Download all |
---|---|---|
md5:2fea5c8b383f1190110464d3403c1eef
|
2.3 MB | Preview Download |
md5:9d01c457182bbc7000b3a1dfa030df88
|
565.7 kB | Preview Download |
Additional details
- PMCID
- PMC4844674
- Eprint ID
- 67300
- Resolver ID
- CaltechAUTHORS:20160524-103844109
- QOLAPS
- European Research Council (ERC)
- RAQUEL
- European Commission
- Foundation for Polish Science
- European Regional Development Fund
- Engineering and Physical Sciences Research Council (EPSRC)
- IdP2011 000361
- Polish Ministry of Science and Higher Education
- Created
-
2016-05-24Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field