Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExact quantum query complexity of $rm{EXACT}_{k,l}^n$
70
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly $k$ or $l$ of the $n$ input bits given by an oracle are 1. We find an optimal algorithm (for some cases), and a nontrivial general lower and upper bound on the minimum number of queries to the black box.
rate research
Read More
We combine the classical notions and techniques for bounded query classes with those developed in quantum computing. We give strong evidence that quantum queries to an oracle in the class NP does indeed reduce the query complexity of decision problems. Under traditional complexity assumptions, we obtain an exponential speedup between the quantum and the classical query complexity of function classes. For decision problems and function classes we obtain the following results: o P_||^NP[2k] is included in EQP_||^NP[k] o P_||^NP[2^(k+1)-2] is included in EQP^NP[k] o FP_||^NP[2^(k+1)-2] is included in FEQP^NP[2k] o FP_||^NP is included in FEQP^NP[O(log n)] For sets A that are many-one complete for PSPACE or EXP we show that FP^A is included in FEQP^A[1]. Sets A that are many-one complete for PP have the property that FP_||^A is included in FEQP^A[1]. In general we prove that for any set A there is a set X such that FP^A is included in FEQP^X[1], establishing that no set is superterse in the quantum setting.
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.
Simons problem is one of the most important problems demonstrating the power of quantum computers, which achieves a large separation between quantum and classical query complexities. However, Simons discussion on his problem was limited to bounded-error setting, which means his algorithm can not always get the correct answer. Exact quantum algorithms for Simons problem have also been proposed, which deterministically solve the problem with O(n) queries. Also the quantum lower bound Omega(n) for Simons problem is known. Although these algorithms are either complicated or specialized, their results give an O(n) versus Omega(sqrt{2^{n}}) separation in exact query complexities for Simons problem (Omega(sqrt{2^{n}}) is the lower bound for classical probabilistic algorithms), but it has not been proved whether this separation is optimal. In this paper, we propose another exact quantum algorithm for solving Simons problem with O(n) queries, which is simple, concrete and does not rely on special query oracles. Our algorithm combines Simons algorithm with the quantum amplitude amplification technique to ensure its determinism. In particular, we show that Simons problem can be solved by a classical deterministic algorithm with O(sqrt{2^{n}}) queries (as we are aware, there were no classical deterministic algorithms for solving Simons problem with O(sqrt{2^{n}}) queries). Combining some previous results, we obtain the optimal separation in exact query complexities for Simons problem: Theta({n}) versus Theta({sqrt{2^{n}}}).
We present three new quantum algorithms in the quantum query model for textsc{graph-collision} problem: begin{itemize} item an algorithm based on tree decomposition that uses $Oleft(sqrt{n}t^{sfrac{1}{6}}right)$ queries where $t$ is the treewidth of the graph; item an algorithm constructed on a span program that improves a result by Gavinsky and Ito. The algorithm uses $O(sqrt{n}+sqrt{alpha^{**}})$ queries, where $alpha^{**}(G)$ is a graph parameter defined by [alpha^{**}(G):=min_{VCtext{-- vertex cover of}G}{max_{substack{Isubseteq VCItext{-- independent set}}}{sum_{vin I}{deg{v}}}};] item an algorithm for a subclass of circulant graphs that uses $O(sqrt{n})$ queries. end{itemize} We also present an example of a possibly difficult graph $G$ for which all the known graphs fail to solve graph collision in $O(sqrt{n} log^c n)$ queries.
The quantum query models is one of the most important models in quantum computing. Several well-known quantum algorithms are captured by this model, including the Deutsch-Jozsa algorithm, the Simon algorithm, the Grover algorithm and others. In this paper, we characterize the computational power of exact one-query quantum algorithms. It is proved that a total Boolean function $f:{0,1}^n rightarrow {0,1}$ can be exactly computed by a one-query quantum algorithm if and only if $f(x)=x_{i_1}$ or ${x_{i_1} oplus x_{i_2} }$ (up to isomorphism). Note that unlike most work in the literature based on the polynomial method, our proof does not resort to any knowledge about the polynomial degree of $f$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
