Gate-based quantum computers can accelerate computational tasks beyond classical capabilities. Random circuit sampling is a task that has experimentally demonstrated algorithmic quantum advantage on near-term devices, but its practical utility has been limited. Recently, certified randomness generation based on random circuits was demonstrated on a trapped-ion quantum computer, advancing near-term applications. In this work, we connect single-device certified randomness to classically verifiable position verification, a classical communication primitive that avoids long-distance quantum communication challenges. We present a generic compiler that converts any such certified randomness protocol into a secure classically verifiable position verification scheme, extend it to multi-round protocols, and show its equivalence to a relaxed certified randomness variant. Our near-term instantiation based on random circuit sampling demonstrates classically verifiable position verification as a practical application for near-term devices. This article establishes a connection between single-device certified randomness and classically verifiable position verification. Through this connection, it shows that the latter can be implemented using noisy intermediate-scale quantum devices.
Gate-based quantum computers can accelerate computational tasks beyond classical capabilities. Random circuit sampling is a task that has experimentally demonstrated algorithmic quantum advantage on near-term devices, but its practical utility has been limited. Recently, certified randomness generation based on random circuits was demonstrated on a trapped-ion quantum computer, advancing near-term applications. In this work, we connect single-device certified randomness to classically verifiable position verification, a classical communication primitive that avoids long-distance quantum communication challenges. We present a generic compiler that converts any such certified randomness protocol into a secure classically verifiable position verification scheme, extend it to multi-round protocols, and show its equivalence to a relaxed certified randomness variant. Our near-term instantiation based on random circuit sampling demonstrates classically verifiable position verification as a practical application for near-term devices. This article establishes a connection between single-device certified randomness and classically verifiable position verification. Through this connection, it shows that the latter can be implemented using noisy intermediate-scale quantum devices.
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.
Abstract Although quantum computers can perform a wide range of practically important tasks beyond the abilities of classical computers 1,2 , realizing this potential remains a challenge. An example is to use an untrusted remote device to generate random bits that can be certified to contain a certain amount of entropy 3 . Certified randomness has many applications but is impossible to achieve solely by classical computation. Here we demonstrate the generation of certifiably random bits using the 56-qubit Quantinuum H2-1 trapped-ion quantum computer accessed over the Internet. Our protocol leverages the classical hardness of recent random circuit sampling demonstrations 4,5 : a client generates quantum ‘challenge’ circuits using a small randomness seed, sends them to an untrusted quantum server to execute and verifies the results of the server. We analyse the security of our protocol against a restricted class of realistic near-term adversaries. Using classical verification with measured combined sustained performance of 1.1 × 10 18 floating-point operations per second across multiple supercomputers, we certify 71,313 bits of entropy under this restricted adversary and additional assumptions. Our results demonstrate a step towards the practical applicability of present-day quantum computers.
We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing “quantum supremacy” experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain Ω(n) min-entropy, where n is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits—thereby “bootstrapping” from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol’s output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most n∼ 60 qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.
We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain Ω(n) min-entropy, where n is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits -- thereby "bootstrapping" from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol's output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most n∼60 qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.
Secure position verification certifies that a remote prover occupies a claimed location, a task that is provably impossible with classical resources alone against colluding adversaries. Most existing quantum position verification schemes require transmitting quantum states between verifiers and provers, and the resulting photon loss makes long-distance verification impractical. Classical verifier position verification (CVPV) schemes with classical verifier-prover communication exist, but rely on complex quantum processes that generate certifiable randomness, placing them outside the reach of near-term hardware. Here we introduce a general compiler that maps any complete-support non-local game with the required quantum advantage into a multi-prover CVPV protocol. This addresses both limitations, with entirely classical verifier-prover communication and all quantum resources confined to shared entanglement and local measurements on the prover devices. Instantiating with the CHSH game enables near-term implementation on existing experimental platforms. We prove finite-size security in the quantum random oracle model for both simultaneous verification of multiple provers and verification of a single prover with multiple prover devices. Notably, security in the multi-prover setting is governed not by the certified randomness of the joint provers' outputs, but by certified blind local randomness that depends critically on the spatial arrangement of provers and verifiers.
The generation of certifiable randomness is the most fundamental information-theoretic task that meaningfully separates quantum devices from their classical counterparts. We propose a protocol for exponential certified randomness expansion using a single quantum device. The protocol calls for the device to implement a simple quantum circuit of constant depth on a 2D lattice of qubits. The output of the circuit can be verified classically in linear time, and is guaranteed to contain a polynomial number of certified random bits assuming that the device used to generate the output operated using a (classical or quantum) circuit of sub-logarithmic depth. This assumption contrasts with the locality assumption used for randomness certification based on Bell inequality violation and more recent proposals for randomness certification based on computational assumptions. Furthermore, to demonstrate randomness generation it is sufficient for a device to sample from the ideal output distribution within constant statistical distance. Our procedure is inspired by recent work of Bravyi et al. (Science 362(6412):308-311, 2018), who introduced a relational problem that can be solved by a constant-depth quantum circuit, but provably cannot be solved by any classical circuit of sub-logarithmic depth. We develop the discovery of Bravyi et al. into a framework for robust randomness expansion. Our results lead to a new proposal for a demonstrated quantum advantage that has some advantages compared to existing proposals. First, our proposal does not rest on any complexity-theoretic conjectures, but relies on the physical assumption that the adversarial device being tested implements a circuit of sub-logarithmic depth. Second, success on our task can be easily verified in classical linear time. Finally, our task is more noise-tolerant than most other existing proposals that can only tolerate multiplicative error, or require additional conjectures from complexity theory; in contrast, we are able to allow a small constant additive error in total variation distance between the sampled and ideal distributions.