Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.38945

Certified Randomness with Optimal Rate

Siddhartha Jain, Saachi Mutreja, Bhaskar Roberts

quant-phcs.CRSubmitted Sep 30, 2026• Announced Oct 1, 2026• 1 citation
arXivHTMLPDF

Abstract

The generation of certified random bits is an emerging near-term application of quantum computers. Potential applications, such as randomness beacons and CRS generation, require nearly uniform randomness, whose rate (the ratio of min-entropy to bitlength) is ~ 1. However, existing protocols for certified randomness either produce weakly random strings with rate o(1), or they require a trusted random seed. We show how to certify randomness with the optimal rate ~ 1 without requiring any trusted randomness from the verifier. Our protocol is secure unconditionally in the quantum random oracle model (QROM). This improves the result of Coladangelo et al., who certified weakly random strings unconditionally in the QROM, and answers a question posed by Aaronson and Hung. We also define and construct a proof of conditional min-entropy, which certifies optimal min-entropy even conditioned on an adversarially chosen transcript. We show an application of this primitive to randomness beacons, where each pulse should have high min-entropy conditioned on all previous messages.

AI Summary

The paper asks how much randomness a deterministic classical verifier can certify from a single untrusted quantum prover without a trusted random seed. It works in the quantum random oracle model (QROM), with non-interactive, publicly verifiable proofs and polynomial-query adversaries, including adversaries with unbounded computation. The construction certifies an $n$-bit output with average conditional min-entropy greater than $n-\gamma(\lambda)$ for every $\gamma(\lambda)=\omega(\log\lambda)$, where $n=\omega(\log\lambda)$. The guarantee holds conditioned on an adversarially chosen classical label and the fixed random oracles: except for a negligible fraction of oracles, any prover accepted with inverse-polynomial probability produces accepted outputs satisfying this entropy bound. Polynomial-time rejection sampling can fix $O(\log\lambda)$ output bits, providing the corresponding obstruction to stronger universal guarantees. The protocol starts from an existing QROM proof of min-entropy, strengthens its soundness analysis, and hashes the verified source together with its label through a separate, domain-separated random oracle. The proof establishes quantum-secure seedless condensation using heavy/light query decompositions, oracle reprogramming, and concentration bounds. A block measure-and-reprogram argument handles labels selected after adaptive quantum oracle queries. An application binds successive randomness-beacon pulses to their preceding public history. The output is not guaranteed uniform, and the result is unconditional only within the QROM; replacing the oracle with a concrete hash function is heuristic. The beacon construction provides neither liveness nor an entropy guarantee when acceptance is overwhelmingly unlikely.

No sign of AI-generated textStrong assumptions

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Certified Randomness from Quantum Supremacy

Scott Aaronson, Shih-Han Hung

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.

arXiv:2303.01625•ACM Symposium on Theory of Computing (STOC)•May 16, 2023•42 citations

Unconditional Certified Randomness without Structure

Andrea Coladangelo, Dakshita Khurana, Saachi Mutreja +3 more

We obtain a certified randomness protocol in the quantum random oracle model. The protocol is non-interactive and publicly verifiable with a classical verifier, and is based on Yamakawa and Zhandry's proof of quantumness [JACM'24]. We prove unconditional security of this protocol against adversaries making subexponentially-many adaptive quantum queries to the random oracle. Prior work on certified randomness relative to a random oracle additionally assumed the Aaronson--Ambainis conjecture or proved security only against low query-depth adversaries.

quant-pharXiv:2608.31112•Sep 1, 2026•1 citation

Certified Randomness without Structure Against Shallow-Query Adversaries

Dakshita Khurana, Bhaskar Roberts, Avishay Tal

In a recent breakthrough, Yamakawa and Zhandry (J. ACM 2024) constructed a proof of quantumness in the quantum random oracle model (QROM) in which the quantum prover samples a codeword preimage of a publicly computable function H. They conjectured that given any H, a successful prover must sample their preimage from a high-entropy distribution over possible answers. If true, this would give a certifiable randomness protocol in the quantum random oracle model. As partial evidence for their conjecture, Yamakawa and Zhandry proved the security of their certifiable randomness protocol assuming the Aaronson-Ambainis conjecture. We prove the security of the certifiable randomness protocol of Yamakawa-Zhandry unconditionally, without relying on the unproven Aaronson-Ambainis conjecture, against low query-depth quantum adversaries: specifically, adversaries that make up to o(\log λ) adaptive quantum queries to the random oracle.

quant-pharXiv:2608.24832•Aug 26, 2026•1 citation

On Certified Randomness from Fourier Sampling or Random Circuit Sampling

Roozbeh Bassirian, Adam Bouland, Bill Fefferman +2 more

Certified randomness has a long history in quantum information, with many potential applications. Recently Aaronson and Hung proposed a novel public certified randomness protocol based on existing random circuit sampling (RCS) experiments. The security of their protocol, however, relies on non-standard complexity-theoretic conjectures which were not previously studied in the literature. Inspired by this work, we study certified randomness in the quantum random oracle model (QROM). We show that quantum Fourier Sampling can be used to define a publicly verifiable certified randomness protocol with black-box security without any computational assumptions. In addition to giving a certified randomness protocol in the QROM, our work can also be seen as supporting Aaronson and Hung's conjectures for RCS-based randomness generation, as our protocol is in some sense the "black-box version" of Aaronson and Hung's protocol. In further support of Aaronson and Hung's proposal, we prove a Fourier Sampling version of Aaronson and Hung's conjecture by extending Raz and Tal's separation of BQP vs PH. Our work complements the subsequent certified randomness protocol of Yamakawa and Zhandry (2022) in the QROM. Whereas the security of that protocol relied on the Aaronson-Ambainis conjecture, ours does not rely on any computational assumption – at the expense of requiring exponential-time classical verification. Our protocol also has a simple heuristic implementation.

arXiv:2111.14846•Quantum•Feb 10, 2026•20 citations

Certified Randomness Generation against Quantum Adversaries via Energy Constraints

Thomas A. Hahn, Efrat Gerchkovitz, Ester Yehuda +1 more

For quantum random number generators (QRNGs), strong security guarantees can be obtained under various assumptions. The most well-known assumptions are the non-signalling assumption (needed for device-independent (DI) QRNG) and post-quantum computational assumptions (needed for computationally bounded single-prover QRNG protocols). In this work, we study a third model: a simple prepare-and-measure QRNG whose security relies on physically motivated energy constraints. This physically motivated set-up allows for easier implementations of QRNGs and can supply better rates. So far, previous works that studied the energy-constrained model either assumed that the adversary is classical in their security proof or supplied relatively weak bounds on the certified randomness, by bounding the conditional min-entropy. In this work, we prove a new, essentially tight, lower bound on the single-round von Neumann entropy against adversaries holding both classical and quantum side-information. Our work reveals that working with the von Neumann entropy, rather than the min-entropy, in the quantum case can lead to a major improvement, nearly matching the classical bound in many cases. We further study the robustness of our entropy bound. Since the single-round von Neumann entropy is the main quantity of interest when characterizing the key rate of QRNGs, our bound establishes the main ingredient for rigorous security proofs against general quantum attacks in this framework.

quant-pharXiv:2610.05766•Oct 6, 2026•0 citations

Certified randomness using a trapped-ion quantum processor

Minzhao Liu, Ruslan Shaydulin, Pradeep Niroula +29 more

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.

arXiv:2503.20498•Nature•Mar 26, 2025•56 citations
The generation of certified random bits is an emerging near-term application of quantum computers. Potential applications, such as randomness beacons and CRS generation, require nearly uniform randomness, whose rate (the ratio of min-entropy to bitlength) is ~ 1. However, existing protocols for certified randomness either produce weakly random strings with rate o(1), or they require a trusted random seed.
We show how to certify randomness with the optimal rate ~ 1 without requiring any trusted randomness from the verifier. Our protocol is secure unconditionally in the quantum random oracle model (QROM). This improves the result of Coladangelo et al., who certified weakly random strings unconditionally in the QROM, and answers a question posed by Aaronson and Hung.
We also define and construct a proof of conditional min-entropy, which certifies optimal min-entropy even conditioned on an adversarially chosen transcript. We show an application of this primitive to randomness beacons, where each pulse should have high min-entropy conditioned on all previous messages.
The paper asks how much randomness a deterministic classical verifier can certify from a single untrusted quantum prover without a trusted random seed. It works in the quantum random oracle model (QROM), with non-interactive, publicly verifiable proofs and polynomial-query adversaries, including adversaries with unbounded computation.
The construction certifies an nnn-bit output with average conditional min-entropy greater than n−γ(λ)n-\gamma(\lambda)n−γ(λ) for every γ(λ)=ω(log⁡λ)\gamma(\lambda)=\omega(\log\lambda)γ(λ)=ω(logλ), where n=ω(log⁡λ)n=\omega(\log\lambda)n=ω(logλ). The guarantee holds conditioned on an adversarially chosen classical label and the fixed random oracles: except for a negligible fraction of oracles, any prover accepted with inverse-polynomial probability produces accepted outputs satisfying this entropy bound. Polynomial-time rejection sampling can fix O(log⁡λ)O(\log\lambda)O(logλ) output bits, providing the corresponding obstruction to stronger universal guarantees.
The protocol starts from an existing QROM proof of min-entropy, strengthens its soundness analysis, and hashes the verified source together with its label through a separate, domain-separated random oracle. The proof establishes quantum-secure seedless condensation using heavy/light query decompositions, oracle reprogramming, and concentration bounds. A block measure-and-reprogram argument handles labels selected after adaptive quantum oracle queries.
An application binds successive randomness-beacon pulses to their preceding public history. The output is not guaranteed uniform, and the result is unconditional only within the QROM; replacing the oracle with a concrete hash function is heuristic. The beacon construction provides neither liveness nor an entropy guarantee when acceptance is overwhelmingly unlikely.
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 obtain a certified randomness protocol in the quantum random oracle model. The protocol is non-interactive and publicly verifiable with a classical verifier, and is based on Yamakawa and Zhandry's proof of quantumness [JACM'24]. We prove unconditional security of this protocol against adversaries making subexponentially-many adaptive quantum queries to the random oracle. Prior work on certified randomness relative to a random oracle additionally assumed the Aaronson--Ambainis conjecture or proved security only against low query-depth adversaries.
In a recent breakthrough, Yamakawa and Zhandry (J. ACM 2024) constructed a proof of quantumness in the quantum random oracle model (QROM) in which the quantum prover samples a codeword preimage of a publicly computable function H. They conjectured that given any H, a successful prover must sample their preimage from a high-entropy distribution over possible answers. If true, this would give a certifiable randomness protocol in the quantum random oracle model. As partial evidence for their conjecture, Yamakawa and Zhandry proved the security of their certifiable randomness protocol assuming the Aaronson-Ambainis conjecture. We prove the security of the certifiable randomness protocol of Yamakawa-Zhandry unconditionally, without relying on the unproven Aaronson-Ambainis conjecture, against low query-depth quantum adversaries: specifically, adversaries that make up to o(\log λ) adaptive quantum queries to the random oracle.
Certified randomness has a long history in quantum information, with many potential applications. Recently Aaronson and Hung proposed a novel public certified randomness protocol based on existing random circuit sampling (RCS) experiments. The security of their protocol, however, relies on non-standard complexity-theoretic conjectures which were not previously studied in the literature. Inspired by this work, we study certified randomness in the quantum random oracle model (QROM). We show that quantum Fourier Sampling can be used to define a publicly verifiable certified randomness protocol with black-box security without any computational assumptions. In addition to giving a certified randomness protocol in the QROM, our work can also be seen as supporting Aaronson and Hung's conjectures for RCS-based randomness generation, as our protocol is in some sense the "black-box version" of Aaronson and Hung's protocol. In further support of Aaronson and Hung's proposal, we prove a Fourier Sampling version of Aaronson and Hung's conjecture by extending Raz and Tal's separation of BQP vs PH. Our work complements the subsequent certified randomness protocol of Yamakawa and Zhandry (2022) in the QROM. Whereas the security of that protocol relied on the Aaronson-Ambainis conjecture, ours does not rely on any computational assumption – at the expense of requiring exponential-time classical verification. Our protocol also has a simple heuristic implementation.
For quantum random number generators (QRNGs), strong security guarantees can be obtained under various assumptions. The most well-known assumptions are the non-signalling assumption (needed for device-independent (DI) QRNG) and post-quantum computational assumptions (needed for computationally bounded single-prover QRNG protocols). In this work, we study a third model: a simple prepare-and-measure QRNG whose security relies on physically motivated energy constraints. This physically motivated set-up allows for easier implementations of QRNGs and can supply better rates. So far, previous works that studied the energy-constrained model either assumed that the adversary is classical in their security proof or supplied relatively weak bounds on the certified randomness, by bounding the conditional min-entropy. In this work, we prove a new, essentially tight, lower bound on the single-round von Neumann entropy against adversaries holding both classical and quantum side-information. Our work reveals that working with the von Neumann entropy, rather than the min-entropy, in the quantum case can lead to a major improvement, nearly matching the classical bound in many cases. We further study the robustness of our entropy bound. Since the single-round von Neumann entropy is the main quantity of interest when characterizing the key rate of QRNGs, our bound establishes the main ingredient for rigorous security proofs against general quantum attacks in this framework.
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.