Random Garbage Separates XOR from Forward-Only Queries
Abstract
We prove an exponential separation between standard (XOR) quantum queries and forward-erasing queries for a Boolean property of injective functions, answering a question of Aaronson~\cite{Aaronson2021Open}. We also obtain an exponential separation for a Boolean promise problem on permutations, where forward in-place queries are unitary but inverse queries are not supplied. Our construction follows Aaronson's suggestion of appending fixed random garbage to a Simon function. Let X={0,1}n and N=2n. We use the injection fh,r(x)=(h(x),x,rx), where h:X→ X is promised to be either a permutation or a Simon function, and r:X→ X is an arbitrary tag table that is reused on every query. The resulting problem is solvable with at most n+2 standard queries, but requires Θ(√N) forward-erasing queries, matching classical collision sampling. Embedding these instances into permutations, with the copy of x replaced by a single bit that keeps the embedding injective, gives a promise problem on permutations of L=4N2 elements that requires O(log L) standard queries versus Θ(L1/4) forward in-place queries. The lower bounds use the recording method. We replace each query by a nearby contraction that records cells of a purified tag table. After T queries, tracing out the purified tag table yields a sum of positive-semidefinite contributions, each depending on h at no more than T addresses. A query-by-query hybrid bounds the trace-norm difference between the actual and auxiliary final operators by O(T/√N). Random permutations and random Simon functions have the same restriction distribution on such a set unless it contains a hidden Simon pair, an event of probability O(T2/N). Consequently, the actual final states in the two cases remain close unless T=Ω(√N), giving the required lower bounds.
Related
- Spin-Hall devices: spin relaxation spatially separates current injection from Joule dissipation
- Exponentially Compressed and Garbage-Free Alias Sampling for Polynomial State Preparation
- Scrambling Separates Superradiance from Quantum Chaos
- Reciprocity Separates Gradient Flow from Rotation in Conservative Physical Learning
- Two exact quantum queries use at most six variables
BibTeX
@misc{elbassioni2026random,
title = {{Random Garbage Separates XOR from Forward-Only Queries}},
author = {Khaled Elbassioni and Rishikesh Gajjala and Saurabh Ray},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03628},
eprint = {2609.03628},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03628},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Random Garbage Separates XOR from Forward-Only Queries
AU - Khaled Elbassioni
AU - Rishikesh Gajjala
AU - Saurabh Ray
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.03628
UR - https://arxiv.org/abs/2609.03628
AB - We prove an exponential separation between standard (XOR) quantum queries and forward-erasing queries for a Boolean property of injective functions, answering a question of Aaronson~\cite{Aaronson2021Open}. We also obtain an exponential separation for a Boolean promise problem on permutations, where forward in-place queries are unitary but inverse queries are not supplied. Our construction follows Aaronson's suggestion of appending fixed random garbage to a Simon function. Let X={0,1}^n and N=2^n. We use the injection f_h,r(x)=(h(x),x,r_x), where h:X→ X is promised to be either a permutation or a Simon function, and r:X→ X is an arbitrary tag table that is reused on every query. The resulting problem is solvable with at most n+2 standard queries, but requires Θ(√N) forward-erasing queries, matching classical collision sampling. Embedding these instances into permutations, with the copy of x replaced by a single bit that keeps the embedding injective, gives a promise problem on permutations of L=4N^2 elements that requires O(log L) standard queries versus Θ(L^1/4) forward in-place queries. The lower bounds use the recording method. We replace each query by a nearby contraction that records cells of a purified tag table. After T queries, tracing out the purified tag table yields a sum of positive-semidefinite contributions, each depending on h at no more than T addresses. A query-by-query hybrid bounds the trace-norm difference between the actual and auxiliary final operators by O(T/√N). Random permutations and random Simon functions have the same restriction distribution on such a set unless it contains a hidden Simon pair, an event of probability O(T^2/N). Consequently, the actual final states in the two cases remain close unless T=Ω(√N), giving the required lower bounds.
ER -