In 2009, using the $\textsf{Fourier Checking}$ problem, Aaronson claimed to construct the relativized worlds such that $\textsf{BQP} \not\subset \mathsf{BPP_{path}}$ and $\textsf{BQP} \not\subset \textsf{SZK}$ . However, there are subtle errors in the original proof. In this paper, we point out the issues, and rescue these two separations by using more sophisticated constructions. Meanwhile, we take the opportunity to study the complexity classes $\mathsf{BPP_{path}}$ and $\textsf{SZK}$ . We give general ways to construct functions which are hard for $\textsf{SZK}$ and $\mathsf{BPP_{path}}$ (in the query complexity sense). Using these techniques, we give alternative construction for the oracle separation $\textsf{BQP} \not\subset \textsf{SZK}$ , using only Simon's problem. We also give new oracle separations for $\textsf{P}^{\textsf{SZK}}$ from $\mathsf{BPP_{path}}$ and $\textsf{P}^{\textsf{SZK}}$ from $\textsf{QSK}$ . The latter result suggests that $\textsf{P}^{\textsf{SZK}}$ might be strictly larger than $\textsf{SZK}$ .In 2009, using the $\textsf{Fourier Checking}$ problem, Aaronson claimed to construct the relativized worlds such that $\textsf{BQP} \not\subset \mathsf{BPP_{path}}$ and $\textsf{BQP} \not\subset \textsf{SZK}$. However, there are subtle errors in the original proof. In this paper, we point out the issues, and rescue these two separations by using more sophisticated constructions. Meanwhile, we take the opportunity to study the complexity classes $\mathsf{BPP_{path}}$ and $\textsf{SZK}$. We give general ways to construct functions which are hard for $\textsf{SZK}$ and $\mathsf{BPP_{path}}$ (in the query complexity sense). Using these techniques, we give alternative construction for the oracle separation $\textsf{BQP} \not\subset \textsf{SZK}$, using only Simon's problem. We also give new oracle separations for $\textsf{P}^{\textsf{SZK}}$ from $\mathsf{BPP_{path}}$ and $\textsf{P}^{\textsf{SZK}}$ from $\textsf{QSK}$. The latter result suggests that $\textsf{P}^{\textsf{SZK}}$ might be strictly larger than $\textsf{SZK}$.

arXiv:1605.00619May 2, 20168 citations

Random Garbage Separates XOR from Forward-Only Queries

Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray

We give exponential quantum query separations between the standard XOR interface and two forward-only interfaces that supply neither an adjoint nor an inverse oracle. Let $X=\F_2^n$, $N=|X|$ , and $f_{h,r}(x)=(h(x),x,r_x)$ , where $h:X\to X$ is promised to be either a permutation or a Simon two-to-one function, and $r$ is a fixed table of $n$ -bit tags, unrestricted by the promise and reused on every query. The resulting problem is solvable with at most $n+2$ standard XOR queries, but has forward-erasing query complexity $Θ(\sqrt N)$ . This answers affirmatively open question 11 in [Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):14:1-14:9, 2021] . We also embed these instances into permutations. The detailed construction retains the copy of $x$ in each prescribed output, but for these promises that copy can be replaced by one bit that distinguishes the two inputs in every Simon pair. This gives a permutation domain of size $L=4N^2$ and a permutation problem with the same standard-query upper bound and forward-only in-place query complexity $Θ(\sqrt N)=Θ(L^{1/4})$ . Both lower bounds remain valid with a clean coherent bypass. The common lower bound uses an analysis-only recording replacement. In the replacement computation, tracing out the fixed random tag table after $T$ calls gives a sum of positive-semidefinite operator contributions, each depending on $h$ at no more than $T$ addresses. On such a set, the restrictions induced by random permutations and random Simon functions differ only if the set contains a hidden Simon pair, an event of probability $O(T^2/N)$ .We give exponential quantum query separations between the standard XOR interface and two forward-only interfaces that supply neither an adjoint nor an inverse oracle. Let $X=\F_2^n$, $N=|X|$, and $f_{h,r}(x)=(h(x),x,r_x)$, where $h:X\to X$ is promised to be either a permutation or a Simon two-to-one function, and $r$ is a fixed table of $n$-bit tags, unrestricted by the promise and reused on every query. The resulting problem is solvable with at most $n+2$ standard XOR queries, but has forward-erasing query complexity $Θ(\sqrt N)$. This answers affirmatively open question 11 in [Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):14:1-14:9, 2021] . We also embed these instances into permutations. The detailed construction retains the copy of $x$ in each prescribed output, but for these promises that copy can be replaced by one bit that distinguishes the two inputs in every Simon pair. This gives a permutation domain of size $L=4N^2$ and a permutation problem with the same standard-query upper bound and forward-only in-place query complexity $Θ(\sqrt N)=Θ(L^{1/4})$. Both lower bounds remain valid with a clean coherent bypass. The common lower bound uses an analysis-only recording replacement. In the replacement computation, tracing out the fixed random tag table after $T$ calls gives a sum of positive-semidefinite operator contributions, each depending on $h$ at no more than $T$ addresses. On such a set, the restrictions induced by random permutations and random Simon functions differ only if the set contains a hidden Simon pair, an event of probability $O(T^2/N)$.

cs.CCCross-listedarXiv:2609.03628Sep 4, 20260 citations

Tight Bounds for Simon’s Algorithm

Xavier Bonnetain

Lecture notes in computer scienceJan 1, 202117 citations

Query Complexity in Expectation

Jędrzej Kaniewski, Troy Lee, Ronald de Wolf

Lecture notes in computer scienceJan 1, 201510 citations

In 2009, using the

\textsf{Fourier Checking}

problem, Aaronson claimed to construct the relativized worlds such that

\textsf{BQP} \not\subset \mathsf{BPP_{path}}

and

\textsf{BQP} \not\subset \textsf{SZK}

. However, there are subtle errors in the original proof. In this paper, we point out the issues, and rescue these two separations by using more sophisticated constructions. Meanwhile, we take the opportunity to study the complexity classes

\mathsf{BPP_{path}}

and

\textsf{SZK}

. We give general ways to construct functions which are hard for

\textsf{SZK}

and

\mathsf{BPP_{path}}

(in the query complexity sense). Using these techniques, we give alternative construction for the oracle separation

\textsf{BQP} \not\subset \textsf{SZK}

, using only Simon's problem. We also give new oracle separations for

\textsf{P}^{\textsf{SZK}}

from

\mathsf{BPP_{path}}

and

\textsf{P}^{\textsf{SZK}}

from

\textsf{QSK}

. The latter result suggests that

\textsf{P}^{\textsf{SZK}}

might be strictly larger than

\textsf{SZK}

We give exponential quantum query separations between the standard XOR interface and two forward-only interfaces that supply neither an adjoint nor an inverse oracle. Let $X=\F_2^n$,

N=|X|

, and

f_{h,r}(x)=(h(x),x,r_x)

, where

h:X\to X

is promised to be either a permutation or a Simon two-to-one function, and

r

is a fixed table of

n

-bit tags, unrestricted by the promise and reused on every query. The resulting problem is solvable with at most

n+2

standard XOR queries, but has forward-erasing query complexity

Θ(\sqrt N)

. This answers affirmatively open question 11 in [Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):14:1-14:9, 2021] . We also embed these instances into permutations. The detailed construction retains the copy of

x

in each prescribed output, but for these promises that copy can be replaced by one bit that distinguishes the two inputs in every Simon pair. This gives a permutation domain of size

L=4N^2

and a permutation problem with the same standard-query upper bound and forward-only in-place query complexity

Θ(\sqrt N)=Θ(L^{1/4})

. Both lower bounds remain valid with a clean coherent bypass. The common lower bound uses an analysis-only recording replacement. In the replacement computation, tracing out the fixed random tag table after

T

calls gives a sum of positive-semidefinite operator contributions, each depending on

h

at no more than

T

addresses. On such a set, the restrictions induced by random permutations and random Simon functions differ only if the set contains a hidden Simon pair, an event of probability

O(T^2/N)