MathDB

Aaronson’s Open Question 11 on forward-only quantum query complexity

For each nn, let X=F2nX=\mathbb{F}_2^n and N=∣X∣=2nN=|X|=2^n. Let r=(rx)x∈Xr=(r_x)_{x\in X} be a fixed table of nn-bit strings, and define fh,r:X→X×X×{0,1}nf_{h,r}:X\to X\times X\times\{0,1\}^n by fh,r(x)=(h(x),x,rx)f_{h,r}(x)=(h(x),x,r_x). The promise is that h:X→Xh:X\to X is either a permutation or a Simon two-to-one function: there exists a nonzero s∈Xs\in X such that h(x)=h(x⊕s)h(x)=h(x\oplus s) for every x∈Xx\in X, with every value in the image having exactly two preimages. Can one distinguish these two cases with few standard XOR queries but not with few forward-only, erasing queries? More specifically, does this promise problem have standard XOR query complexity O(n)O(n) and forward-erasing query complexity asymptotically larger, such as Ω(N)\Omega(\sqrt{N})?

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. Permutation-embedded form of the garbage separation

    The same separation is embedded into a problem whose oracle is a permutation on a domain of size L=4N2L=4N^2: the standard-query complexity is at most n+2n+2, while the forward-only in-place query complexity is Θ(N)=Θ(L1/4)\Theta(\sqrt{N})=\Theta(L^{1/4}).

    source: Random Garbage Separates XOR from Forward-Only Queries

References

Primary source

arXiv

Additional references

quantum-computingquantum-query-complexity
Posted

Progress summary

Refreshed
Claimed solved

A new preprint claims to settle Aaronson’s question by showing that forward-only quantum queries can be much weaker than ordinary queries, but the result has not yet been independently checked.

Aaronson posed the question in 2021: can a quantum computer learn a property of an injective function with few ordinary queries but not with few forward-only, erasing queries? His proposed test case was Simon’s problem with long random garbage, where ordinary queries can remove the garbage but forward-only queries apparently cannot.

Known results

Aaronson, 2021: formulated the problem and proposed Simon’s problem with garbage as a candidate separation; the related earlier direction had been answered affirmatively following work prompted by Kashefi, 2000.

September 2026 claimed separation

A new arXiv preprint, Random Garbage Separates XOR from Forward-Only Queries, claims an O(n)O(n)-versus-Θ(N)\Theta(\sqrt{N}) separation for a Simon-versus-permutation promise problem and embeds it into permutations with the same asymptotic gap. This would settle Aaronson’s Open Question 11, but the claim is unverified and has not been independently confirmed or peer reviewed.

Current status (as of September 2026): A new preprint claims the question is solved with an O(n)O(n)-versus-Θ(N)\Theta(\sqrt{N}) separation, but independent verification and peer review remain outstanding.

Sources

Solutions 0

No solutions have been posted yet.