Nonadaptive quantum query complexity

We study the power of nonadaptive quantum query algorithms, which are algorithms whose queries to the input do not depend on the result of previous queries. First, we show that any bounded-error nonadaptive quantum query algorithm that computes a total boolean function depending on n variables must make Ω(n) queries to the input in total. Second, we show that, if there exists a quantum algorithm that uses k nonadaptive oracle queries to learn which one of a set of m boolean functions it has been given, there exists a nonadaptive classical algorithm using queries to solve the same problem. Thus, in the nonadaptive setting, quantum algorithms for these tasks can achieve at most a very limited speed-up over classical query algorithms.     

A New Quantum Lower Bound Method,with Applications to Direct Product Theorems and Time-Space Tradeoffs

We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal. A. Ambainis supported by University of Latvia research project Y2-ZP01-100. This work conducted while at University of Waterloo, supported by NSERC, ARO, MITACS, CIFAR, CFI and IQC University Professorship. R. Špalek supported by NSF Grant CCF-0524837 and ARO Grant DAAD 19-03-1-0082. Work conducted while at CWI and the University of Amsterdam, supported by the European Commission under projects RESQ (IST-2001-37559) and QAP (IST-015848). R. de Wolf supported by a Veni grant from the Netherlands Organization for Scientific Research (NWO) and partially supported by the EU projects RESQ and QAP.     

On the uselessness of quantum queries

Given a prior probability distribution over a set of possible oracle functions, we define a number of queries to be useless for determining some property of the function if the probability that the function has the property is unchanged after the oracle responds to the queries. A familiar example is the parity of a uniformly random Boolean-valued function over {1,2,…,N}, for which N−1 classical queries are useless. We prove that if 2k classical queries are useless for some oracle problem, then k quantum queries are also useless. For such problems, which include classical threshold secret sharing schemes, our result also gives a new way to obtain a lower bound on the quantum query complexity, even in cases where neither the function nor the property to be determined is Boolean.     

Sharp Quantum versus Classical Query Complexity Separations

Abstract. We obtain the strongest separation between quantum and classical query complexity known to date—specifically, we define a black-box problem that requires exponentially many queries in the classical bounded-error case, but can be solved exactly in the quantum case with a single query (and a polynomial number of auxiliary operations). The problem is simple to define and the quantum algorithm solving it is also simple when described in terms of certain quantum Fourier transforms (QFTs) that have natural properties with respect to the algebraic structures of finite fields. These QFTs may be of independent interest, and we also investigate generalizations of them to noncommutative finite rings.     

Improved direct product theorems for randomized query complexity

The ??direct product problem?? is a fundamental question in complexity theory which seeks to understand how the difficulty in computing a function on each of k independent inputs scales with k. We prove the following direct product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most ${1 - \varepsilon}$ in computing the Boolean function f on input distribution???, then for ?? ?? 1, every ${\alpha \varepsilon Tk}$ -query algorithm has success probability at most ${(2^{\alpha \varepsilon}(1-\varepsilon))^k}$ in computing the k-fold direct product ${f^{\otimes k}}$ correctly on k independent inputs from???. In light of examples due to Shaltiel, this statement gives an essentially optimal trade-off between the query bound and the error probability. Using this DPT, we show that for an absolute constant ?? > 0, the worst-case success probability of any ?? R ₂(f) k-query randomized algorithm for ${f^{\otimes k}}$ falls exponentially with k. The best previous statement of this type, due to Klauck, ?palek, and de Wolf, required a query bound of O(bs(f) k). Our proof technique involves defining and analyzing a collection of martingales associated with an algorithm attempting to solve ${f^{\otimes k}}$ . Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dynamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.     

Unbounded-error quantum query complexity

This work studies the quantum query complexity of Boolean functions in an unbounded-error scenario where it is only required that the query algorithm succeeds with a probability strictly greater than 1/2. We show that, just as in the communication complexity model, the unbounded-error quantum query complexity is exactly half of its classical counterpart for any (partial or total) Boolean function. Moreover, connecting the query and communication complexity results, we show that the “black-box” approach to convert quantum query algorithms into communication protocols by Buhrman-Cleve—Wigderson [STOC’98] is optimal even in the unbounded-error setting.We also study a related setting, called the weakly unbounded-error setting, where the cost of a query algorithm is given by q+log(1/2(p−1/2)), where q is the number of queries made and p>1/2 is the success probability of the algorithm. In contrast to the case of communication complexity, we show a tight multiplicative Θ(logn) separation between quantum and classical query complexity in this setting for a partial Boolean function. The asymptotic equivalence between them is also shown for some well-studied total Boolean functions.     

Continuous aggregate nearest neighbor queries

This paper addresses the problem of continuous aggregate nearest-neighbor (CANN) queries for moving objects in spatio-temporal data stream management systems. A CANN query specifies a set of landmarks, an integer k, and an aggregate distance function f (e.g., min, max, or sum), where f computes the aggregate distance between a moving object and each of the landmarks. The answer to this continuous query is the set of k moving objects that have the smallest aggregate distance f. A CANN query may also be viewed as a combined set of nearest neighbor queries. We introduce several algorithms to continuously and incrementally answer CANN queries. Extensive experimentation shows that the proposed operators outperform the state-of-the-art algorithms by up to a factor of 3 and incur low memory overhead.     

Querying Probabilistic Business Processes for Sub-Flows

A Business Process (BP for short) consists of a set of activities which, combined in a flow, achieve some business goal. A given BP may have a large, possibly infinite, number of possible execution flows (EX-flows for short), each having some probability to occur at run time. This paper studies query evaluation over such probabilistic BPs. We focus on two important classes of queries, namely boolean queries that compute the probability that a random EX-flow of a BP satisfies a given property, and projection queries focusing on portions of EX-flows that are of interest to the user. For the latter queries the answer consists of the top-k instances of these portions that are most likely to occur at run-time. We study the complexity of query evaluation for both kinds of queries, showing in particular that projection queries may be harder to evaluate than boolean queries. We present a picture of which combinations of BP classes and query features lead to PTIME algorithms and which to NP-hard or infeasible problems.     

Partition arguments in multiparty communication complexity

Consider the “Number in Hand” multiparty communication complexity model, where k players holding inputs x₁,…,x_k∈{0,1}ⁿ communicate to compute the value f(x₁,…,x_k) of a function f known to all of them. The main lower bound technique for the communication complexity of such problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem.In this paper, we study the power of partition arguments. Our two main results are very different in nature:

(i)

For randomized communication complexity, we show that partition arguments may yield bounds that are exponentially far from the true communication complexity. Specifically, we prove that there exists a 3-argument function f whose communication complexity is Ω(n), while partition arguments can only yield an Ω(logn) lower bound. The same holds for nondeterministiccommunication complexity.

(ii)

For deterministic communication complexity, we prove that finding significant gaps between the true communication complexity and the best lower bound that can be obtained via partition arguments, would imply progress on a generalized version of the “log-rank conjecture” in communication complexity. We also observe that, in the case of computing relations (search problems), very large gaps do exist.

We conclude with two results on the multiparty “fooling set technique”, another method for obtaining communication complexity lower bounds.     

Comparing the strength of query types in property testing: The case of k-colorability

We study the power of four query models in the context of property testing in general graphs, where our main case study is the problem of testing k-colorability. Two query types, which have been studied extensively in the past, are pair queries and neighbor queries. The former corresponds to asking whether there is an edge between any particular pair of vertices, and the latter to asking for the i ^th neighbor of a particular vertex. We show that while for pair queries testing k-colorability requires a number of queries that is a monotone decreasing function in the average degree d, the query complexity in the case of neighbor queries remains roughly the same for every density and for large values of k. We also consider a combined model that allows both types of queries, and we propose a new, stronger, query model, related to the field of Group Testing. We give upper and lower bounds on the query complexity for one-sided error in all the models, where the bounds are nearly tight for three of the models. In some of the cases, our lower bounds extend to two-sided error algorithms. The problem of testing k-colorability was previously studied in the contexts of dense graphs and of sparse graphs, and in our proofs we unify approaches from those cases, and also provide some new tools and techniques that may be of independent interest.     

Information theory in property testing and monotonicity testing in higher dimension

In property testing, we are given oracle access to a function f, and we wish to test if the function satisfies a given property P, or it is ϵ-far from having that property. In a more general setting, the domain on which the function is defined is equipped with a probability distribution, which assigns different weight to different elements in the domain. This paper relates the complexity of testing the monotonicity of a function over the d-dimensional cube to the Shannon entropy of the underlying distribution. We provide an improved upper bound on the query complexity of the property tester.     

Property Testing Lower Bounds via Communication Complexity

We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in testing. This scheme is general and implies a number of new testing bounds, as well as simpler proofs of several known bounds. For the problem of testing whether a Boolean function is k-linear (a parity function on k variables), we achieve a lower bound of ??(k) queries, even for adaptive algorithms with two-sided error, thus confirming a conjecture of Goldreich (2010a). The same argument behind this lower bound also implies a new proof of known lower bounds for testing related classes such as k-juntas. For some classes, such as the class of monotone functions and the class of s-sparse GF(2) polynomials, we significantly strengthen the best known bounds.     

On the Power of Non-adaptive Learning Graphs

We introduce a notion of the quantum query complexity of a certificate structure. This is a formalization of a well-known observation that many quantum query algorithms only require the knowledge of the position of possible certificates in the input string, not the precise values therein. Next, we derive a dual formulation of the complexity of a non-adaptive learning graph and use it to show that non-adaptive learning graphs are tight for all certificate structures. By this, we mean that there exists a function possessing the certificate structure such that a learning graph gives an optimal quantum query algorithm for it. For a special case of certificate structures generated by certificates of bounded size, we construct a relatively general class of functions having this property. The construction is based on orthogonal arrays and generalizes the quantum query lower bound for the k-sum problem derived recently by Belovs and ?palek (Proceeding of 4th ACM ITCS, 323–328, 2013). Finally, we use these results to show that the learning graph for the triangle problem by Lee et al. (Proceeding of 24th ACM-SIAM SODA, 1486–1502, 2013) is almost optimal in the above settings. This also gives a quantum query lower bound for the triangle sum problem.     

How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?

It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Ω(log n), and that this bound is achieved for some functions. In this paper, we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures, the correct lower bound is Ω(log n/ log  log n), and we exhibit quantum algorithms for two functions where this bound is achieved.     

Comparison of methods for logic-query implementation

A logic query Q is a triple < G, LP, D, where G is the query goal, LP is a logic program without function symbols, and D is a set of facts, possibly stored as tuples of a relational database. The answers of Q are all facts that can be inferred from LP ∪ D and unify with G. A logic query is bound if some argument of the query goal is a constant; it is canonical strongly linear (a CSL query) if LP contains exactly one recursive rule and this rule is linear, i.e., only one recursive predicate occurs in its body. In this paper, the problem of finding the answers of a bound CSL query is studied with the aim of comparing for efficiency some well-known methods for implementing logic queries: the eager method, the counting method, and the magic-set method. It is shown that the above methods can be expressed as algorithms for finding particular paths in a directed graph associated to the query. Within this graphical formalism, a worst-case complexity analysis of the three methods is performed. It turns out that the counting method has the best upper bound for noncyclic queries. On the other hand, since the counting method is not safe if queries are cyclic, the method is extended to safely implement this kind of queries as well.     

A note on the search for k elements via quantum walk

In this paper we use the quantum walk search scheme by Magniez et al. (2007) [13] to find k solutions of a search problem. We show that the quantum query complexity is at most of order times the number of queries to find one solution.     

Threshold-based declustering

Declustering techniques reduce query response time through parallel I/O by distributing data among multiple devices. Except for a few cases it is not possible to find declustering schemes that are optimal for all spatial range queries. As a result of this, most of the research on declustering has focused on finding schemes with low worst case additive error. However, additive error based schemes have many limitations including lack of progressive guarantees and existence of small non-optimal queries. In this paper, we take a different approach and propose threshold-based declustering. We investigate the threshold k such that all spatial range queries with ?k buckets are optimal. Upper bound on threshold is analyzed using bound diagrams and a number theoretic algorithm is proposed to find schemes with high threshold value. Threshold-based schemes have many advantages: they have low worst-case additive error, provide progressive guarantees by dividing larger queries into subqueries with ?k buckets, can be used to compare replicated declustering schemes and render many large complementary queries optimal.