517 research outputs found
Variable time amplitude amplification and quantum algorithms for linear algebra problems
No full textQuantum amplitude amplification is a method of increasing a success probability of an algorithm from a small epsilon>0 to Theta(1) with less repetitions than classically. In this paper, we generalize quantum amplitude amplification to the case when parts of the algorithm that is being amplified stop at different times.
We then apply the new variable time amplitude amplification to give two new quantum algorithms for linear algebra problems. Our first algorithm is an improvement of Harrow et al. algorithm for solving systems of linear equations. We improve the running time of the algorithm from O(k^2 log N) to O(k log^3 k log N) where k is the condition number of the system of equations. Our second algorithm tests whether a matrix A is singular or far from singular, faster then the previously known algorithms
Quantum search with variable times
No full textSince Grover's seminal work, quantum search has been studied in
great detail. In the usual search problem, we have a collection of
items and we would like to find .
We consider a new variant of this problem in which evaluating
for different may take a different number of time steps.
Let be the number of time steps required to evaluate .
If the numbers are known in advance, we give an algorithm
that solves the problem in O(sqrt{t_1^2+t_2^2+ldots+t_n^2)
steps. This is optimal, as we also show a matching lower bound.
The case, when are not known in advance, can be solved with a
polylogarithmic overhead. We also give an application of our new
search algorithm to computing read-once functions
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
No full textWe show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by epsilon'<1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [Aaronson/Ambainis, STOC 2015]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms.
We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Omega(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms.
Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [Aaronson/Ambainis, STOC 2015], showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^n -> [-1,1] with O(n^{1-1/(2k)) queries
Quantum Algorithms for Computational Geometry Problems
No full textWe study quantum algorithms for problems in computational geometry, such as Point-On-3-Lines problem. In this problem, we are given a set of lines and we are asked to find a point that lies on at least 3 of these lines. Point-On-3-Lines and many other computational geometry problems are known to be 3Sum-Hard. That is, solving them classically requires time Ω(n^{2-o(1)}), unless there is faster algorithm for the well known 3Sum problem (in which we are given a set S of n integers and have to determine if there are a, b, c ∈ S such that a + b + c = 0). Quantumly, 3Sum can be solved in time O(n log n) using Grover’s quantum search algorithm. This leads to a question: can we solve Point-On-3-Lines and other 3Sum-Hard problems in O(n^c) time quantumly, for c<2? We answer this question affirmatively, by constructing a quantum algorithm that solves Point-On-3-Lines in time O(n^{1 + o(1)}). The algorithm combines recursive use of amplitude amplification with geometrical ideas. We show that the same ideas give O(n^{1 + o(1)}) time algorithm for many 3Sum-Hard geometrical problems
Optimal quantum query bounds for almost all Boolean functions
No full textWe show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of Ambainis (A. Ambainis, 1999), and shows that van Dam's oracle interrogation (W. van Dam, 1998) is essentially optimal for almost all functions. Our proof uses the fact that the acceptance probability of a T-query algorithm can be written as the sum of squares of degree-T polynomials
Provable Advantage for Quantum Strategies in Random Symmetric XOR Games
No full textNon-local games are widely studied as a model to investigate the properties of quantum mechanics as opposed to classical mechanics. In this paper, we consider a subset of non-local games: symmetric XOR games of n players with 0-1 valued questions. For this class of games, each player receives an input bit and responds with an output bit without communicating to the other players. The winning condition only depends on XOR of output bits and is constant w.r.t. permutation of players. We prove that for almost any n-player symmetric XOR game the entangled value of the game is Theta((sqrt(ln(n)))/(n^{1/4})) adapting an old result by Salem and Zygmund on the asymptotics of random trigonometric polynomials. Consequently, we show that the classical-quantum gap is Theta(sqrt(ln(n))) for almost any symmetric XOR game
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
No full textWhile it is known that there is at most a polynomial separation between
quantum query complexity and the polynomial degree for total functions, the
precise relationship between the two is not clear for partial functions.
In this paper, we demonstrate an exponential separation between exact
polynomial degree and approximate quantum query complexity for a partial
Boolean function. For an unbounded alphabet size, we have a constant versus
polynomial separation.Comment: 13 pages, minimal changes with v
Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions
No full textWe show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) query complexity and subcube partition complexity, which is also essentially optimal. We also establish a nearly power 1.5 separation between quantum query complexity and subcube partition complexity, the first superlinear separation between the two measures. Lastly, we show a quadratic separation between quantum query complexity and one-sided subcube partition complexity.
Our query complexity separations use the recent cheat sheet framework of Aaronson, Ben-David, and Kothari. Our query functions are built up in stages by alternating function composition with the cheat sheet construction. The communication complexity separation follows from "lifting" the query separation to communication complexity
A Note About Claw Function with a Small Range
No full textIn the claw detection problem we are given two functions f:D → R and g:D → R (|D| = n, |R| = k), and we have to determine if there is exist x,y ∈ D such that f(x) = g(y). We show that the quantum query complexity of this problem is between Ω(n^{1/2}k^{1/6}) and O(n^{1/2+ε}k^{1/4}) when 2 ≤ k < n
Improved Algorithm and Lower Bound for Variable Time Quantum Search
No full textWe study variable time search, a form of quantum search where queries to
different items take different time. Our first result is a new quantum
algorithm that performs variable time search with complexity where with denoting the time to check the
-th item. Our second result is a quantum lower bound of . Both the algorithm and the lower bound improve over previously known
results by a factor of but the algorithm is also substantially
simpler than the previously known quantum algorithms
- …
