Paper 2024/1726

On the Equivalence between Classical Position Verification and Certified Randomness

Fatih Kaleoglu, JPMorganChase, University of California, Santa Barbara
Minzhao Liu, JPMorganChase
Kaushik Chakraborty, JPMorganChase
David Cui, JPMorganChase, Massachusetts Institute of Technology
Omar Amer, JPMorganChase
Marco Pistoia, JPMorganChase
Charles Lim, JPMorganChase
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.