Deutsch–Jozsa problem (D–J) has exact quantum 1-query complexity (“exact” means no error), but requires super-exponential queries for the optimal classical deterministic decision trees. D–J problem is equivalent to a symmetric partial Boolean function, and in fact, all symmetric partial Boolean functions having exact quantum 1-query complexity have been found out and these functions can be computed by D–J algorithm. A special case is that all symmetric Boolean functions with exact quantum 1-query complexity follow directly and these functions are also all total Boolean functions with exact quantum 1-query complexity obviously. Then there are pending problems concerning partial Boolean functions having exact quantum 1-query complexity and new results have been found, but some problems are still open. In this paper, we review these results regarding exact quantum 1-query complexity and in particular, we also obtain a new result that a partial Boolean function with exact quantum 1-query complexity is constructed and it cannot be computed by D–J algorithm. Further problems are pointed out for future study.Deutsch–Jozsa problem (D–J) has exact quantum 1-query complexity (“exact” means no error), but requires super-exponential queries for the optimal classical deterministic decision trees. D–J problem is equivalent to a symmetric partial Boolean function, and in fact, all symmetric partial Boolean functions having exact quantum 1-query complexity have been found out and these functions can be computed by D–J algorithm. A special case is that all symmetric Boolean functions with exact quantum 1-query complexity follow directly and these functions are also all total Boolean functions with exact quantum 1-query complexity obviously. Then there are pending problems concerning partial Boolean functions having exact quantum 1-query complexity and new results have been found, but some problems are still open. In this paper, we review these results regarding exact quantum 1-query complexity and in particular, we also obtain a new result that a partial Boolean function with exact quantum 1-query complexity is constructed and it cannot be computed by D–J algorithm. Further problems are pointed out for future study.

SPINAug 12, 20213 citations

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ 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.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.10935Mar 20, 20230 citations

Parameterized query complexity in quantum computation

Parijat Prashun Purohit

Jan 1, 20170 citations

On the exact quantum query complexity of

\text{MOD}_m^n

and

\text{EXACT}_{k,l}^n

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

k=1,l=n-1

. This resolves the conjecture proposed by Ambainis, Iraids and Nagaj (2017) partially.