Paper 2024/1726
On the Equivalence between Classical Position Verification and Certified Randomness
Abstract
Gate-based quantum computers hold enormous potential to accelerate classically intractable computational tasks. Random circuit sampling (RCS) is the only known task that has been able to be experimentally demonstrated using current-day NISQ devices. However, for a long time, it remained challenging to demonstrate the quantum utility of RCS on practical problems. Recently, leveraging RCS, an interactive protocol generating certified randomness was demonstrated using a trapped ion quantum computer, advancing the practical utility of near-term gate-based quantum computers. In this work, we establish a strong connection between certified randomness and another quantum computation classical communication primitive, classically verifiable position verification (CVPV), which circumvents the practical challenges that may arise from long-distance quantum communications. We provide a new generic compiler that can convert any single-round proof of quantumness based certified randomness protocol into a secure classical communication-based position verification scheme. Later, we extend our compiler to different types of multi-round protocols. Notably, our compiler can be applied to any multi-round certified randomness protocol that can be analyzed using the entropy accumulation theorem, making its applicability very general. Moreover, we show that CVPV is equivalent to a relaxed variant of certified randomness that we define. We instantiate each of our compilers using existing certified randomness protocols. In particular, building on the work of Aaronson and Hung (STOC '23), we give a NISQ-friendly instantiation based on RCS, which was experimentally demonstrated by Liu et al. Hence, we show that CVPV is another application within reach of NISQ devices.
Note: Updated author order.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- certified-randomnessposition-verificationquantumrandom-oracle-modelrandom-circuit-sampling
- Contact author(s)
-
fatih kaleoglu @ jpmchase com
minzhao liu @ jpmchase com
kaushik chakraborty @ jpmchase com
dzcui @ mit edu
omar amer @ jpmchase com
marco pistoia @ jpmchase com
charles lim @ jpmchase com - History
- 2025-06-18: last of 2 revisions
- 2024-10-21: received
- See all versions
- Short URL
- https://ia.cr/2024/1726
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1726, author = {Fatih Kaleoglu and Minzhao Liu and Kaushik Chakraborty and David Cui and Omar Amer and Marco Pistoia and Charles Lim}, title = {On the Equivalence between Classical Position Verification and Certified Randomness}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1726}, year = {2024}, url = {https://eprint.iacr.org/2024/1726} }