Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOpen Problems Related to Quantum Query Complexity
131
0
0.0
(
0
)
Authors
Scott Aaronson
Ask ChatGPT about the research
No Arabic abstract
I offer a case that quantum query complexity still has loads of enticing and fundamental open problems -- from relativized QMA versus QCMA and BQP versus IP, to time/space tradeoffs for collision and element distinctness, to polynomial degree versus quantum query complexity for partial functions, to the Unitary Synthesis Problem and more.
rate research
Read More
The closest pair problem is a fundamental problem of computational geometry: given a set of $n$ points in a $d$-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in $O(nlog n)$ time in constant dimensions (i.e., when $d=O(1)$). This paper asks and answers the question of the problems quantum time complexity. Specifically, we give an $tilde{O}(n^{2/3})$ algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In $mathrm{polylog}(n)$ dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grovers algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grovers algorithm is optimal for CNF-SAT when the clause width is large. We show that the na{i}ve Grover approach to closest pair in higher dimensions is optimal up to an $n^{o(1)}$ factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.
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.
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.
We study quantum algorithms that learn properties of a matrix using queries that return its action on an input vector. We show that for various problems, including computing the trace, determinant, or rank of a matrix or solving a linear system that it specifies, quantum computers do not provide an asymptotic speedup over classical computation. On the other hand, we show that for some problems, such as computing the parities of rows or columns or deciding if there are two identical rows or columns, quantum computers provide exponential speedup. We demonstrate this by showing equivalence between models that provide matrix-vector products, vector-matrix products, and vector-matrix-vector products, whereas the power of these models can vary significantly for classical computation.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
