For every publicly computable function H used in the Yamakawa–Zhandry quantum random-oracle certifiable-randomness protocol, every quantum prover that succeeds in the protocol must sample a codeword preimage of H from a distribution having high entropy over the possible preimages, in the sense required to certify randomness.

Yamakawa–Zhandry certifiable-randomness conjecture

Yamakawa and Zhandry's conjecture concerns the high-entropy output of successful quantum provers in certifiable-randomness protocols. Their 2022 construction established the relevant security only conditional on the Aaronson–Ambainis conjecture.

Known results

Yamakawa and Zhandry (2022): one-message and two-message certifiable-randomness protocols in the random-oracle model, conditional on the Aaronson–Ambainis conjecture.
Yamakawa and Zhandry (2022): unconditional results for search problems do not establish the conjectured decision-problem simulation.

August 2026 shallow-query advance

A new preprint claims unconditional protocol security for adversaries making $o(\log \lambda)$ adaptive quantum queries, removing the Aaronson–Ambainis assumption in that regime. A related preprint claims constant-round simulation results and derives restricted certifiable-randomness protocols; it credits ChatGPT 5.5 Pro with assisting the proofs, but the claims remain independently unverified and do not cover the full conjecture.

Current status (as of August 2026): The conjecture is claimed to hold unconditionally for adversaries with $o(\log \lambda)$ adaptive quantum queries, while the full conjecture remains open and the new claims are unverified.

Yamakawa–Zhandry certifiable-randomness conjecture

Primary source

Additional references

Progress summary

Solutions 0