Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1610.01920 · Journal of Computer and System Sciences

Optimal separation in exact query complexities for Simon's problem

Guangya Cai, Daowen Qiu

Published Jun 4, 2018• 24 citations
arXivHTMLPDF
DOI
10.1016/j.jcss.2018.05.001

Related papers

Query complexity of generalized Simon's problem

Zekun Ye, Yunqi Huang, Lvzhou Li +1 more

arXiv:1907.07367•Information and Computation•Aug 27, 2021•9 citations

Quantum and classical query complexities for generalized Simon's problem

Zhenggang Wu, Daowen Qiu, Jiawei Tan +2 more

arXiv:1905.08549•Theoretical Computer Science•May 30, 2022•9 citations

A Quantum Lower Bound for the Query Complexity of Simon’s Problem

Pascal Koiran, Vincent Nesme, Natacha Portier

arXiv:quant-ph/0501060•Lecture notes in computer science•Jan 1, 2005•25 citations

Simon's problem for linear functions

Joran van Apeldoorn, Sander Gribling

Simon's problem asks the following: determine if a function $f: \{0,1\}^n \rightarrow \{0,1\}^n$ is one-to-one or if there exists a unique $s \in \{0,1\}^n$ such that $f(x) = f(x \oplus s)$ for all $x \in \{0,1\}^n$, given the promise that exactly one of the two holds. A classical algorithm that can solve this problem for every $f$ requires $2^{Ω(n)}$ queries to $f$. Simon showed that there is a quantum algorithm that can solve this promise problem for every $f$ using only $\mathcal O(n)$ quantum queries to $f$. A matching lower bound on the number of quantum queries was given by Koiran et al., even for functions $f: {\mathbb{F}_p^n} \to {\mathbb{F}_p^n}$. We give a short proof that $\mathcal O(n)$ quantum queries is optimal even when we are additionally promised that $f$ is linear. This is somewhat surprising because for linear functions there even exists a classical $n$-query algorithm.

arXiv:1810.12030•Oct 29, 2018•4 citations

Towards Optimal Separations between Quantum and Randomized Query Complexities

Avishay Tal

The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of O(1) vs. √N between quantum and randomized query complexities remain the state-of-the-art (where N is the input length), leaving open the question of whether O(1) vs. N1/2+Ω(1)separations are possible? We answer this question in the affirmative. Our separating problem is a variant of the Aaronson-Ambainis k-fold Forrelation problem. We show that our variant: 1)Can be solved by a quantum algorithm making 2O(k)queries to the inputs. 2)Requires at least ~Ω(N2(k-1)/(3k-1)) queries for any randomized algorithm. For any constant , this gives a O(1) vs. N1/2-εseparation between the quantum and randomized query complexities of partial Boolean functions. Our proof is Fourier analytical and uses new bounds on the Fourier spectrum of classical decision trees, which could be of independent interest. Looking forward, we conjecture that the Fourier bounds could be further improved in a precise manner, and show that such conjectured bounds imply optimal O(1) vs. N1-εseparations between the quantum and randomized query complexities of partial Boolean functions.

arXiv:1912.12561•Annual Symposium on Foundations of Computer Science•Nov 1, 2020•32 citations

A Note on Oracle Separations for BQP

Lijie Chen

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.00619•May 2, 2016•13 citations
Simon's problem asks the following: determine if a function f:{0,1}n→{0,1}nf: \{0,1\}^n \rightarrow \{0,1\}^nf:{0,1}n→{0,1}n is one-to-one or if there exists a unique s∈{0,1}ns \in \{0,1\}^ns∈{0,1}n such that f(x)=f(x⊕s)f(x) = f(x \oplus s)f(x)=f(x⊕s) for all x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n, given the promise that exactly one of the two holds. A classical algorithm that can solve this problem for every fff requires 2Ω(n)2^{Ω(n)}2Ω(n) queries to fff. Simon showed that there is a quantum algorithm that can solve this promise problem for every fff using only O(n)\mathcal O(n)O(n) quantum queries to fff. A matching lower bound on the number of quantum queries was given by Koiran et al., even for functions f:Fpn→Fpnf: {\mathbb{F}_p^n} \to {\mathbb{F}_p^n}f:Fpn​→Fpn​. We give a short proof that O(n)\mathcal O(n)O(n) quantum queries is optimal even when we are additionally promised that fff is linear. This is somewhat surprising because for linear functions there even exists a classical nnn-query algorithm.
The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of O(1) vs. √N between quantum and randomized query complexities remain the state-of-the-art (where N is the input length), leaving open the question of whether O(1) vs. N1/2+Ω(1)separations are possible? We answer this question in the affirmative. Our separating problem is a variant of the Aaronson-Ambainis k-fold Forrelation problem. We show that our variant: 1)Can be solved by a quantum algorithm making 2O(k)queries to the inputs. 2)Requires at least ~Ω(N2(k-1)/(3k-1)) queries for any randomized algorithm. For any constant , this gives a O(1) vs. N1/2-εseparation between the quantum and randomized query complexities of partial Boolean functions. Our proof is Fourier analytical and uses new bounds on the Fourier spectrum of classical decision trees, which could be of independent interest. Looking forward, we conjecture that the Fourier bounds could be further improved in a precise manner, and show that such conjectured bounds imply optimal O(1) vs. N1-εseparations between the quantum and randomized query complexities of partial Boolean functions.
In 2009, using the Fourier Checking\textsf{Fourier Checking}Fourier Checking problem, Aaronson claimed to construct the relativized worlds such that BQP⊄BPPpath\textsf{BQP} \not\subset \mathsf{BPP_{path}}BQP⊂BPPpath​ and BQP⊄SZK\textsf{BQP} \not\subset \textsf{SZK}BQP⊂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 BPPpath\mathsf{BPP_{path}}BPPpath​ and SZK\textsf{SZK}SZK. We give general ways to construct functions which are hard for SZK\textsf{SZK}SZK and BPPpath\mathsf{BPP_{path}}BPPpath​ (in the query complexity sense). Using these techniques, we give alternative construction for the oracle separation BQP⊄SZK\textsf{BQP} \not\subset \textsf{SZK}BQP⊂SZK, using only Simon's problem. We also give new oracle separations for PSZK\textsf{P}^{\textsf{SZK}}PSZK from BPPpath\mathsf{BPP_{path}}BPPpath​ and PSZK\textsf{P}^{\textsf{SZK}}PSZK from QSK\textsf{QSK}QSK. The latter result suggests that PSZK\textsf{P}^{\textsf{SZK}}PSZK might be strictly larger than SZK\textsf{SZK}SZK.