arXiv:2611.00609
Compressed Oracle Duality: A simple framework for knowing what quantum adversaries know
Matthew Ding, Mark Zhandry
Abstract
Given a quantum adversary that queries a random oracle, how do we characterize the information that they "know"? The Compressed Oracle method of Zhandry (CRYPTO 2019) is one method that records the queries that the adversary makes; this recording serves as a representation of the information that is learned. However, a significant limitation of the Compressed Oracle method is that it may continue to store information that the adversary has "forgotten." This issue is especially pertinent in the space-bounded setting, where the adversary may uncompute information to free up space, while the information may still reside in the compressed oracle. In this work, we present a simple and interpretable framework called "Compressed Oracle Duality," which extends the Compressed Oracle method for space-bounded algorithms. By applying an isometry to the memory of a quantum adversary, we obtain a pair of compressed oracles with identical marginal distributions and classical correlations which correspond to the knowledge the adversary retains. In fact, we show that the outcome of measuring the new compressed oracle database corresponds exactly to applying the pretty-good measurement on the adversary's memory. As an application of our framework for collision search, we give a simplified proof of the recent $T^2S = Ω(N\log N)$ quantum time-space tradeoff for label-symmetric algorithms due to Magniez-Zur (arXiv:2609.10808); we also prove a stronger classical tradeoff of $TS=Ω(N\log N)$ assuming label symmetry. The proofs under our framework do not require representation theory and instead bound the mutual information between the compressed oracle pairs. This highlights both how the label symmetry assumption bypasses known proof barriers as well as the challenges that remain in achieving unconditional quantum time-space tradeoffs.
AI Summary
The paper asks how to characterize information a space-bounded quantum algorithm retains about a random oracle, rather than information recorded in its query history. A compressed-oracle database can remain large even after the algorithm has forgotten individual outputs, obstructing direct space bounds. “Compressed Oracle Duality” canonically re-encodes the algorithm’s memory as a second database: if $A$ is the joint state’s coefficient matrix and $G=A^\dagger A$, the new joint state has coefficient matrix $\sqrt G$. The two measured databases have identical marginals; measuring the dual database implements the pretty-good measurement on the memory. Their classical mutual information is at most $S$ for $S$ qubits. Potentials counting certificates shared by both databases bound query-free extraction success, with quantitative slack. An unconditional shared-point bound gives $O(S/\log N)$ expected shared entries after at most $\sqrt N$ queries. For collision search in a random function with range size $N$, the framework reproves the existing label-symmetric quantum tradeoff $T^2S=\Omega(N\log N)$ without representation theory. The proof bounds matched labels through mutual information and unmatched labels through symmetry and compressed-oracle validity. A separate branching-program comparison with an injective oracle establishes the classical label-symmetric bound $TS=\Omega(N\log N)$. No unrestricted collision tradeoff follows: the proposed per-query joint-potential bound has counterexamples, and label symmetry excludes Pollard’s rho. The general memory characterization assumes no intermediate measurements; only the label-symmetric application is extended to measurements under a conditional symmetry assumption.
the authors used ChatGPT 6 Astra along with this new framework to develop the simplified proofs.
Central claim may not hold: The abstract presents the retained-knowledge framework without an intermediate-measurement restriction, although the general characterization is established only for unitary algorithms and the paper explicitly leaves knowledge characterization after intermediate measurements open.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 34 pages