In the SEARCH WITH ADVICE problem, a single entry of interest within a database of N entries is to be found assuming that an ordering of the entries, from that with the highest probability of being the entry of interest (as determined by a so-called advice distribution) to that with the lowest, is provided. We present a quantum algorithm that, in the presence of significant levels of quantum noise, solves SEARCH WITH ADVICE for a power law advice distribution with average-case query complexity O(1) as N tends to infinity. Since as we also show the best classical algorithms for this problem exhibit average-case query complexity of order no better than log(N), our quantum algorithm provides a super-exponential reduction in query complexity.
In the SEARCH WITH ADVICE problem, a single entry of interest within a database of N entries is to be found assuming that an ordering of the entries, from that with the highest probability of being the entry of interest (as determined by a so-called advice distribution) to that with the lowest, is provided. We present a quantum algorithm that, in the presence of significant levels of quantum noise, solves SEARCH WITH ADVICE for a power law advice distribution with average-case query complexity O(1) as N tends to infinity. Since as we also show the best classical algorithms for this problem exhibit average-case query complexity of order no better than log(N), our quantum algorithm provides a super-exponential reduction in query complexity.
We consider the problem of search of an unstructured list for a marked element, when one is given advice as to where this element might be located, in the form of a probability distribution. The goal is to minimise the expected number of queries to the list made to find the marked element, with respect to this distribution. We present a quantum algorithm which solves this problem using an optimal number of queries, up to a constant factor. For some distributions on the input, such as certain power law distributions, the algorithm can achieve exponential speed-ups over the best possible classical algorithm. We also give an efficient quantum algorithm for a variant of this task where the distribution is not known in advance, but must be queried at an additional cost. The algorithms are based on the use of Grover's quantum search algorithm and amplitude amplification as subroutines.
We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial. We show that for average-case complexity under the uniform distribution, quantum algorithms can be exponentially faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity.
We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial. We show that for average-case complexity under the uniform distribution, quantum algorithms can be exponentially faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity. A preliminary version of this paper appeared in the Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS'2000) (Lecture Notes in Computer Science vol 1770) (Berlin: Springer).
A quantum computer encodes information in quantum states and runs quantum algorithms to surpass the classical counterparts by exploiting quantum superposition and quantum correlation. Grover's quantum search algorithm is a typical quantum algorithm that proves the superiority of quantum computing over classical computing. It has a quadratic reduction in the query complexity of a database search and is known to be optimal when no a priori information about the elements of the database is provided. In this work we consider a probabilistic Grover search algorithm allowing nonzero probability of failure for a database with a general a priori probability distribution of the elements and minimize the number of oracle calls by optimizing the initial state of the quantum system and the reflection axis of the diffusion operator. The initial state and the reflection axis are allowed to not coincide and thus the quantum search algorithm rotates the quantum system in a three-dimensional subspace spanned by the initial state, the reflection axis, and the search target state in general. The number of oracle calls is minimized by a variational method, and formal results are obtained with the assumption of low failure probability. The results show that for a nonuniform a priori distribution of the database elements, the number of oracle calls can be significantly reduced given a small decrease in the success probability of the quantum search algorithm, leading to a lower average query complexity to find the solution of the search problem. The results are applied to a simple but nontrivial database model with two-value a priori probabilities to show the power of the optimized quantum search algorithm. The paper concludes with a discussion about the generalization to higher-order results that allows for a larger failure probability for the quantum search algorithm.
In its usual form, Grover’s quantum search algorithm uses O( √ N) queries and O( √ N log N) other elementary gates to find a solution in an N-bit database. Grover in 2002 showed how to reduce the number of other gates to O( √ N log log N) for the special case where the database has a unique solution, without significantly increasing the number of queries. We show how to reduce this further to O( √ N log(r) N) gates for every constant r, and sufficiently large N. This means that, on average, the circuits between two queries barely touch more than a constant number of the log N qubits on which the algorithm acts. For a very large N that is a power of 2, we can choose r such that the algorithm uses essentially the minimal number π 4 √ N of queries, and only O( √ N log(log? N)) other gates.
We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism:
- We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is O(1) but is maximally hard for pseudo-deterministic quantum algorithms (Ω(N) query complexity).
- We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms (O(log(N)) vs. Θ(N)), while the randomized query complexity is O(1).
Complementing these separations, we show that for any total problem R, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., D(R)=O~(psQ(R)5).
On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, k-sum, and graph collision.