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• 2 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 $Θ(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 $Ω(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 $Ω((n/\log n)^{2/3})$ bound given by Aaronson and Shi's $Ω(n^{2/3})$ lower bound for the element distinctness problem.

arXiv:1008.2422•Aug 14, 2010•5 citations

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.

Quantum Information and Computation•Jul 1, 2012•21 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

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$

Yao, Penghui, Ye, Zekun

The query model has generated considerable interest in both classical and quantum computing communities. Typically, quantum advantages are demonstrated by showcasing a quantum algorithm with a better query complexity compared to its classical counterpart. Exact quantum query algorithms play a pivotal role in developing quantum algorithms. For example, the Deutsch-Jozsa algorithm demonstrated exponential quantum advantages over classical deterministic algorithms. As an important complexity measure, exact quantum query complexity describes the minimum number of queries required to solve a specific problem exactly using a quantum algorithm. In this paper, we consider the exact quantum query complexity of the following two $n$-bit symmetric functions $\text{MOD}_m^n:\{0,1\}^n \rightarrow \{0,...,m-1\}$ and $\text{EXACT}_{k,l}^n:\{0,1\}^n \rightarrow \{0,1\}$, which are defined as $\text{MOD}_m^n(x) = |x| \bmod m$ and $ \text{EXACT}_{k,l}^n(x) = 1$ iff $|x| \in \{k,l\}$, where $|x|$ is the number of $1$'s in $x$. Our results are as follows: i) We present an optimal quantum algorithm for computing $\text{MOD}_m^n$, achieving a query complexity of $\lceil n(1-\frac{1}{m}) \rceil$ for $1 < m \le n$. This settles a conjecture proposed by Cornelissen, Mande, Ozols and de Wolf (2021). Based on this algorithm, we show the exact quantum query complexity of a broad class of symmetric functions that map $\{0,1\}^n$ to a finite set $X$ is less than $n$. ii) When $l-k \ge 2$, we give an optimal exact quantum query algorithm to compute $\text{EXACT}_{k,l}^n$ for the case $k=0$ or $k=1,l=n-1$. This resolves the conjecture proposed by Ambainis, Iraids and Nagaj (2017) partially.

arXiv:2303.10935•Mar 20, 2023•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•1 citation

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•23 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)Θ(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)Ω(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)Ω((n/\log n)^{2/3})Ω((n/logn)2/3) bound given by Aaronson and Shi's Ω(n2/3)Ω(n^{2/3})Ω(n2/3) lower bound for the element distinctness problem.
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.
On the exact quantum query complexity of MODmn\text{MOD}_m^nMODmn​ and EXACTk,ln\text{EXACT}_{k,l}^nEXACTk,ln​
The query model has generated considerable interest in both classical and quantum computing communities. Typically, quantum advantages are demonstrated by showcasing a quantum algorithm with a better query complexity compared to its classical counterpart. Exact quantum query algorithms play a pivotal role in developing quantum algorithms. For example, the Deutsch-Jozsa algorithm demonstrated exponential quantum advantages over classical deterministic algorithms. As an important complexity measure, exact quantum query complexity describes the minimum number of queries required to solve a specific problem exactly using a quantum algorithm. In this paper, we consider the exact quantum query complexity of the following two nnn-bit symmetric functions MODmn:{0,1}n→{0,...,m−1}\text{MOD}_m^n:\{0,1\}^n \rightarrow \{0,...,m-1\}MODmn​:{0,1}n→{0,...,m−1} and EXACTk,ln:{0,1}n→{0,1}\text{EXACT}_{k,l}^n:\{0,1\}^n \rightarrow \{0,1\}EXACTk,ln​:{0,1}n→{0,1}, which are defined as MODmn(x)=∣x∣ mod m\text{MOD}_m^n(x) = |x| \bmod mMODmn​(x)=∣x∣modm and $ \text{EXACT}_{k,l}^n(x) = 1$ iff ∣x∣∈{k,l}|x| \in \{k,l\}∣x∣∈{k,l}, where ∣x∣|x|∣x∣ is the number of 111's in xxx. Our results are as follows: i) We present an optimal quantum algorithm for computing MODmn\text{MOD}_m^nMODmn​, achieving a query complexity of ⌈n(1−1m)⌉\lceil n(1-\frac{1}{m}) \rceil⌈n(1−m1​)⌉ for 1<m≤n1 < m \le n1<m≤n. This settles a conjecture proposed by Cornelissen, Mande, Ozols and de Wolf (2021). Based on this algorithm, we show the exact quantum query complexity of a broad class of symmetric functions that map {0,1}n\{0,1\}^n{0,1}n to a finite set XXX is less than nnn. ii) When l−k≥2l-k \ge 2l−k≥2, we give an optimal exact quantum query algorithm to compute EXACTk,ln\text{EXACT}_{k,l}^nEXACTk,ln​ for the case k=0k=0k=0 or k=1,l=n−1k=1,l=n-1k=1,l=n−1. This resolves the conjecture proposed by Ambainis, Iraids and Nagaj (2017) partially.
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.