On the exact quantum query complexity of $\text{MOD}_m^n$ and
$\text{EXACT}_{k,l}^n$
- URL: http://arxiv.org/abs/2303.10935v4
- Date: Fri, 12 May 2023 10:12:23 GMT
- Title: On the exact quantum query complexity of $\text{MOD}_m^n$ and
$\text{EXACT}_{k,l}^n$
- Authors: Zekun Ye
- Abstract summary: We present an exact quantum algorithm for computing $textMOD_mn$.
We show exact quantum query complexity of a broad class of symmetric functions that map $0,1n$ to a finite set $X$ is less than $n$.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
Related papers
- Time-Efficient Quantum Entropy Estimator via Samplizer [8.646488471216262]
Estimating the entropy of a quantum state is a basic problem in quantum information.
We introduce a time-efficient quantum approach to estimating the von Neumann entropy $S(rho)$ and R'enyi entropy $S_alpha(rho)$.
arXiv Detail & Related papers (2024-01-18T12:50:20Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$.
Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
arXiv Detail & Related papers (2023-07-13T18:59:28Z) - Basic quantum subroutines: finding multiple marked elements and summing
numbers [1.1265248232450553]
We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(sqrtN k)$ of quantum queries.
arXiv Detail & Related papers (2023-02-20T19:11:44Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$.
We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM)
Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
arXiv Detail & Related papers (2022-06-07T18:00:01Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
We study quantum Ordered Binary Decision Diagrams($OBDD$) model.
We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables.
We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
arXiv Detail & Related papers (2022-04-22T12:37:56Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
We show that a quantum algorithm can be implemented in time $tilde O(sqrtGT)$.
Our algorithm is based on non-binary span programs and their efficient implementation.
arXiv Detail & Related papers (2021-05-18T06:51:11Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
We show a quantum algorithm with complexity $widetilde O(T_Dn)$, where $T_D D+1$.
While the best known classical algorithm is $textpoly(m,n)log n T_Dn$, the time complexity of our quantum algorithm is $textpoly(m,n)log n T_Dn$.
arXiv Detail & Related papers (2021-04-29T14:50:03Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model.
We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z) - Towards Optimal Separations between Quantum and Randomized Query
Complexities [0.30458514384586394]
We show that a quantum algorithm can be solved by making $2O(k)$ queries to the inputs.
For any constant $varepsilon>0$, this gives a $O(1)$ vs. $N2/3-varepsilon$ separation.
arXiv Detail & Related papers (2019-12-29T01:42:31Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.