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:1810.12030

Simon's problem for linear functions

Joran van Apeldoorn, Sander Gribling

Published Oct 29, 2018• 4 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1810.12030

Related papers

The quantum query complexity of AC0

Paul W. Beame, Widad Machmouchi

We show that any quantum algorithm deciding whether an input function $f$ from $[n]$ to $[n]$ is 2-to-1 or almost 2-to-1 requires $\Theta(n)$ queries to $f$. The same lower bound holds for determining whether or not a function $f$ from $[2n-2]$ to $[n]$ is surjective. These results yield a nearly linear $\Omega(n/\log n)$ lower bound on the quantum query complexity of $\cl{AC}^0$. The best previous lower bound known for any $\cl{AC^0}$ function was the $\Omega ((n/\log n)^{2/3})$ bound given by Aaronson and Shi's $\Omega(n^{2/3})$ lower bound for the element distinctness problem.

arXiv:1008.2422•Quantum Information and Computation•Jul 1, 2012•29 citations

Quantum Query Algorithms

Walid E. Gomaa

This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.

•Nov 19, 2025•0 citations

Quantum Lower Bounds for Collision Problems

Pan Peng, Jingyu Wu

We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised $k$-to-one Finding on an exactly $k$-to-one input string $x\in\mathbb Z_q^n$, for every fixed $k\ge2$ and every feasible alphabet size $q\ge n/k$. The lower bounds are $Ω_k(n^{1/2-1/(2(2^k-1))})$ for unrestricted adaptive algorithms and $Ω_k(n^{1-1/k})$ for one-round non-adaptive algorithms. The former matches the adaptive quantum algorithm of Liu and Zhandry [LZ19], whereas the latter matches classical birthday sampling even when the parallel queries are arbitrarily entangled. We also establish the non-adaptive lower bound $Ω_k(\sqrt{n/k})$ for $k$-to-one Testing when $q\ge n$, resolving an open question posed by Koiran, Landes, Portier, and Yao [KLPY10]. Our proofs generate the balanced input from a uniformly random permutation and use compressed permutation oracles to describe the information learned by the algorithm. The adaptive proof bounds the growth of partial collisions through successive queries. The one-round proof instead analyzes the state after the parallel queries directly, bounding the probability that the compressed database contains a full collision. In both proofs, a short verification step accounts for correct outputs that include unrecorded positions. For the decision problem, we also compare one-round states with independent and distinct output labels.

quant-pharXiv:2611.01767•Nov 3, 2026•0 citations

Characterization of exact one-query quantum algorithms (ii): for partial functions

Zekun Ye, Lvzhou Li

The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.

arXiv:2008.11998•Aug 27, 2020•3 citations

A quantum algorithm to approximate the linear structures of Boolean functions

Hongwei Li, Li Yang

A quantum algorithm to determine approximations of linear structures of Boolean functions is presented and analysed. Similar results have already been published (see Simon's algorithm) but only for some promise versions of the problem, and it has been shown that no exponential quantum speedup can be obtained for the general (no promise) version of the problem. In this paper, no additional promise assumptions are made. The approach presented is based on the method used in the Bernstein–Vazirani algorithm to identify linear Boolean functions and on ideas from Simon's period finding algorithm. A proper combination of these two approaches results here to a polynomial-time approximation to the linear structures set. Specifically, we show how the accuracy of the approximation with high probability changes according to the running time of the algorithm. Moreover, we show that the time required for the linear structure determine problem with high success probability is related to so called relative differential uniformityδfof a Boolean functionf. Smaller differential uniformity is, shorter time is needed.

arXiv:1404.0611•Mathematical Structures in Computer Science•Feb 9, 2016•27 citations

A note on the quantum collision and set equality problems

Mark Zhandry

A collision for a function $f$ is two distinct inputs $x_1\neq x_2$ such that $f$ outputs the same value on both inputs: $f(x_1)=f(x_2)$. The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be $\Theta(N^{1/3})$; however, these results do not apply to random functions. The issues are two-fold. First, the $\Omega(N^{1/3})$ lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to $r$-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of $\Theta(N^{1/3})$ holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal $\Omega(M^{1/3})$ lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.

arXiv:1312.1027•Quantum Information and Computation•May 1, 2015•138 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.
We show that any quantum algorithm deciding whether an input function fff from [n][n][n] to [n][n][n] is 2-to-1 or almost 2-to-1 requires Θ(n)\Theta(n)Θ(n) queries to fff. The same lower bound holds for determining whether or not a function fff from [2n−2][2n-2][2n−2] to [n][n][n] is surjective. These results yield a nearly linear Ω(n/log⁡n)\Omega(n/\log n)Ω(n/logn) lower bound on the quantum query complexity of $\cl{AC}^0$. The best previous lower bound known for any $\cl{AC^0}$ function was the Ω((n/log⁡n)2/3)\Omega ((n/\log n)^{2/3})Ω((n/logn)2/3) bound given by Aaronson and Shi's Ω(n2/3)\Omega(n^{2/3})Ω(n2/3) lower bound for the element distinctness problem.
This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.
We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised kkk-to-one Finding on an exactly kkk-to-one input string x∈Zqnx\in\mathbb Z_q^nx∈Zqn​, for every fixed k≥2k\ge2k≥2 and every feasible alphabet size q≥n/kq\ge n/kq≥n/k. The lower bounds are Ωk(n1/2−1/(2(2k−1)))Ω_k(n^{1/2-1/(2(2^k-1))})Ωk​(n1/2−1/(2(2k−1))) for unrestricted adaptive algorithms and Ωk(n1−1/k)Ω_k(n^{1-1/k})Ωk​(n1−1/k) for one-round non-adaptive algorithms. The former matches the adaptive quantum algorithm of Liu and Zhandry [LZ19], whereas the latter matches classical birthday sampling even when the parallel queries are arbitrarily entangled. We also establish the non-adaptive lower bound Ωk(n/k)Ω_k(\sqrt{n/k})Ωk​(n/k​) for kkk-to-one Testing when q≥nq\ge nq≥n, resolving an open question posed by Koiran, Landes, Portier, and Yao [KLPY10]. Our proofs generate the balanced input from a uniformly random permutation and use compressed permutation oracles to describe the information learned by the algorithm. The adaptive proof bounds the growth of partial collisions through successive queries. The one-round proof instead analyzes the state after the parallel queries directly, bounding the probability that the compressed database contains a full collision. In both proofs, a short verification step accounts for correct outputs that include unrecorded positions. For the decision problem, we also compare one-round states with independent and distinct output labels.
The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.
A quantum algorithm to determine approximations of linear structures of Boolean functions is presented and analysed. Similar results have already been published (see Simon's algorithm) but only for some promise versions of the problem, and it has been shown that no exponential quantum speedup can be obtained for the general (no promise) version of the problem. In this paper, no additional promise assumptions are made. The approach presented is based on the method used in the Bernstein–Vazirani algorithm to identify linear Boolean functions and on ideas from Simon's period finding algorithm. A proper combination of these two approaches results here to a polynomial-time approximation to the linear structures set. Specifically, we show how the accuracy of the approximation with high probability changes according to the running time of the algorithm. Moreover, we show that the time required for the linear structure determine problem with high success probability is related to so called relative differential uniformityδfof a Boolean functionf. Smaller differential uniformity is, shorter time is needed.
A collision for a function fff is two distinct inputs x1≠x2x_1\neq x_2x1​=x2​ such that fff outputs the same value on both inputs: f(x1)=f(x2)f(x_1)=f(x_2)f(x1​)=f(x2​). The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be Θ(N1/3)\Theta(N^{1/3})Θ(N1/3); however, these results do not apply to random functions. The issues are two-fold. First, the Ω(N1/3)\Omega(N^{1/3})Ω(N1/3) lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to rrr-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of Θ(N1/3)\Theta(N^{1/3})Θ(N1/3) holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal Ω(M1/3)\Omega(M^{1/3})Ω(M1/3) lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.