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:1907.07367 · Information and Computation

Query complexity of generalized Simon's problem

Zekun Ye, Yunqi Huang, Lvzhou Li, Yuyi Wang

Published Aug 27, 2021• 9 citations
arXivHTMLPDF
DOI
10.1016/j.ic.2021.104790

Related papers

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

Optimal separation in exact query complexities for Simon's problem

Guangya Cai, Daowen Qiu

arXiv:1610.01920•Journal of Computer and System Sciences•Jun 4, 2018•24 citations

Tight Bounds for Simon’s Algorithm

Xavier Bonnetain

Lecture notes in computer science•Jan 1, 2021•18 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

The non-injective hidden shift problem

Mirmojtaba Gharibi

In this work, we mostly concentrate on the hidden shift problem for non-injective functions. It is worthwhile to know that the query complexity of the non-injective hidden shift problem is exponential in the worst case by the well known bounds on the unstructured search problem. Hence, we can make this problem more tractable by imposing additional constraints on the problem. Perhaps the first constraint that comes to mind is to address the average case problem. In this work, we show that the average case non-injective hidden shift problem can be reduced to the injective hidden shift problem by giving one such reduction. The reduction is based on a tool we developed called injectivization. The result is strong in the sense that the underlying group can be any finite group and that the non-injective functions for which we have defined the hidden shift problem can have range in an arbitrary finite set. Using this tool, we simplify the main result of a recent paper by about the hidden shift problem for Boolean-valued functions by reducing that problem to Simon's problem. They also posed an open question which is subject to personal interpretation. We answer the seemingly most general interpretation of the question. However, we use our own techniques in doing so (the authors ask if their techniques can be used for addressing that problem). Another constraint that one can consider is to have a promise on the structure of the functions. In this work we consider the hidden shift problem for c-almost generalized bent functions. A class of functions which we defined that includes the generalized bent functions. Then we turn our attention toward the generalized hidden shift problem which is easier than injective hidden shift problem and hence more tractable. We state some of our observations about this problem. Finally we show that the average classical query complexity of the non-injective hidden shift problem over groups of form (Z/mZ)^n when m is a constant is exponential, which also immediately implies that the classical average query complexity of the non-injective hidden shift problem is exponential. We also show that the worst-case classical query complexity of the generalized injective hidden shift problem over the same group is high, which implies that the classical query complexity of the hidden shift problem is high.

•Jan 19, 2012•2 citations
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.
In this work, we mostly concentrate on the hidden shift problem for non-injective functions. It is worthwhile to know that the query complexity of the non-injective hidden shift problem is exponential in the worst case by the well known bounds on the unstructured search problem. Hence, we can make this problem more tractable by imposing additional constraints on the problem. Perhaps the first constraint that comes to mind is to address the average case problem. In this work, we show that the average case non-injective hidden shift problem can be reduced to the injective hidden shift problem by giving one such reduction. The reduction is based on a tool we developed called injectivization. The result is strong in the sense that the underlying group can be any finite group and that the non-injective functions for which we have defined the hidden shift problem can have range in an arbitrary finite set. Using this tool, we simplify the main result of a recent paper by about the hidden shift problem for Boolean-valued functions by reducing that problem to Simon's problem. They also posed an open question which is subject to personal interpretation. We answer the seemingly most general interpretation of the question. However, we use our own techniques in doing so (the authors ask if their techniques can be used for addressing that problem). Another constraint that one can consider is to have a promise on the structure of the functions. In this work we consider the hidden shift problem for c-almost generalized bent functions. A class of functions which we defined that includes the generalized bent functions. Then we turn our attention toward the generalized hidden shift problem which is easier than injective hidden shift problem and hence more tractable. We state some of our observations about this problem. Finally we show that the average classical query complexity of the non-injective hidden shift problem over groups of form (Z/mZ)^n when m is a constant is exponential, which also immediately implies that the classical average query complexity of the non-injective hidden shift problem is exponential. We also show that the worst-case classical query complexity of the generalized injective hidden shift problem over the same group is high, which implies that the classical query complexity of the hidden shift problem is high.