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:2608.24832

Certified Randomness without Structure Against Shallow-Query Adversaries

Dakshita Khurana, Bhaskar Roberts, Avishay Tal

quant-phcs.CRSubmitted Aug 25, 2026• Announced Aug 26, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
To be published at FOCS 2026

Related papers

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•0 citations

Certified Randomness with Optimal Rate

Siddhartha Jain, Saachi Mutreja, Bhaskar Roberts

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.

quant-pharXiv:2609.38945•Oct 1, 2026•0 citations

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•3 citations

Parallel Quantum Advantage with Limited Adaptivity Requires Structure

Qipeng Liu, Saachi Mutreja

Aaronson and Ambainis (Theory of Computing, 2014) conjectured that quantum query algorithms admit efficient almost-everywhere classical simulation: for any $T$-query quantum algorithm, its acceptance probability can be approximated on a $(1-δ)$ fraction of inputs, up to $ε$ additive error, using $\mathrm{poly}(T, 1/ε, 1/δ)$ classical queries. At a high level, the conjecture suggests that exponential quantum speedups are possible only on sufficiently structured inputs. In this work, we make progress on this conjecture by proving it for quantum algorithms that make massively parallel quantum queries. In contrast, Yamakawa and Zhandry (Journal of the ACM, 2024) showed that quantum algorithms restricted to parallel queries can still achieve exponential speedups over classical algorithms for sampling problems. We establish our simulation theorem by proving the stronger statement that parallel-query quantum algorithms cannot distinguish the uniform distribution over oracles from oracles drawn from so-called "dense distributions". Our main technical contribution is a coupling theorem that relates the uniform distribution over oracles to oracles drawn from dense distributions. We further extend this approach beyond the purely parallel setting. We prove simulation theorems for quantum algorithms with constant rounds of adaptivity, and for quantum algorithms with a bounded quantum-query prefix followed by a massively parallel quantum-query stage.

quant-pharXiv:2608.20297•Aug 21, 2026•0 citations

Thermodynamic Proof of Quantumness without Structure

Florian Meier, Hayata Yamasaki

Demonstrating that a machine performs genuinely quantum operations is a central challenge in quantum information processing. Existing proofs of quantumness typically rely on computational tasks that are infeasible for classical machines under assumptions such as computational hardness, or explicit bounds on classical runtime, memory, or oracle queries. Here we introduce an alternative paradigm: a thermodynamic proof of quantumness based on energy consumption. Using the search problem of Yamakawa and Zhandry with a structureless uniformly random oracle, we show that any classical machine solving the task with constant success probability must generate entropy that grows exponentially with the security parameter. By Landauer's principle, this implies an exponential lower bound on heat dissipation and hence on the energy consumption of any cyclic classical implementation. In contrast, the corresponding quantum prover solves the task with polynomial query and gate complexity, giving polynomial energy consumption under standard assumptions for quantum implementations. Thus, in the random-oracle setting, sufficiently low energy consumption in a successful implementation certifies quantumness through a macroscopic thermodynamic observation of energy consumption.

quant-pharXiv:2609.25211•Sep 23, 2026•0 citations

Verifiable Quantum Advantage without Structure

Takashi Yamakawa, Mark Zhandry

We show the following hold, unconditionally unless otherwise stated, relative to a random oracle with probability 1: •There are NP search problems solvable by BQP machines but not BPP machines.•There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the separation does not necessarily extend to the case of other cryptographic objects such as PRGs.•There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin.•Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction.By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.

Annual Symposium on Foundations of Computer Science•Oct 1, 2022•36 citations
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.
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.
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.
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.
Aaronson and Ambainis (Theory of Computing, 2014) conjectured that quantum query algorithms admit efficient almost-everywhere classical simulation: for any TTT-query quantum algorithm, its acceptance probability can be approximated on a (1−δ)(1-δ)(1−δ) fraction of inputs, up to εεε additive error, using poly(T,1/ε,1/δ)\mathrm{poly}(T, 1/ε, 1/δ)poly(T,1/ε,1/δ) classical queries. At a high level, the conjecture suggests that exponential quantum speedups are possible only on sufficiently structured inputs. In this work, we make progress on this conjecture by proving it for quantum algorithms that make massively parallel quantum queries. In contrast, Yamakawa and Zhandry (Journal of the ACM, 2024) showed that quantum algorithms restricted to parallel queries can still achieve exponential speedups over classical algorithms for sampling problems. We establish our simulation theorem by proving the stronger statement that parallel-query quantum algorithms cannot distinguish the uniform distribution over oracles from oracles drawn from so-called "dense distributions". Our main technical contribution is a coupling theorem that relates the uniform distribution over oracles to oracles drawn from dense distributions. We further extend this approach beyond the purely parallel setting. We prove simulation theorems for quantum algorithms with constant rounds of adaptivity, and for quantum algorithms with a bounded quantum-query prefix followed by a massively parallel quantum-query stage.
Demonstrating that a machine performs genuinely quantum operations is a central challenge in quantum information processing. Existing proofs of quantumness typically rely on computational tasks that are infeasible for classical machines under assumptions such as computational hardness, or explicit bounds on classical runtime, memory, or oracle queries. Here we introduce an alternative paradigm: a thermodynamic proof of quantumness based on energy consumption. Using the search problem of Yamakawa and Zhandry with a structureless uniformly random oracle, we show that any classical machine solving the task with constant success probability must generate entropy that grows exponentially with the security parameter. By Landauer's principle, this implies an exponential lower bound on heat dissipation and hence on the energy consumption of any cyclic classical implementation. In contrast, the corresponding quantum prover solves the task with polynomial query and gate complexity, giving polynomial energy consumption under standard assumptions for quantum implementations. Thus, in the random-oracle setting, sufficiently low energy consumption in a successful implementation certifies quantumness through a macroscopic thermodynamic observation of energy consumption.
We show the following hold, unconditionally unless otherwise stated, relative to a random oracle with probability 1: •There are NP search problems solvable by BQP machines but not BPP machines.•There exist functions that are one-way, and even collision resistant, against classical adversaries but are easily inverted quantumly. Similar separations hold for digital signatures and CPA-secure public key encryption (the latter requiring the assumption of a classically CPA-secure encryption scheme). Interestingly, the separation does not necessarily extend to the case of other cryptographic objects such as PRGs.•There are unconditional publicly verifiable proofs of quantumness with the minimal rounds of interaction: for uniform adversaries, the proofs are non-interactive, whereas for non-uniform adversaries the proofs are two message public coin.•Our results do not appear to contradict the Aaronson-Ambanis conjecture. Assuming this conjecture, there exist publicly verifiable certifiable randomness, again with the minimal rounds of interaction.By replacing the random oracle with a concrete cryptographic hash function such as SHA2, we obtain plausible Minicrypt instantiations of the above results. Previous analogous results all required substantial structure, either in terms of highly structured oracles and/or algebraic assumptions in Cryptomania and beyond.