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.     

The quantum query complexity of the determinant

In this paper we give tight quantum query complexity bounds of some important linear algebra problems. We prove Θ(n²) quantum query bounds for verify the determinant, rank, matrix inverse and the matrix power problem.     

The quantum query complexity of the hidden subgroup problem is polynomial

We present a quantum algorithm which identifies with certainty a hidden subgroup of an arbitrary finite group G in only a polynomial (in log|G|) number of calls to the oracle. This is exponentially better than the best classical algorithm. However our quantum algorithm requires exponential time, as in the classical case. Our algorithm utilizes a new technique for constructing error-free algorithms for non-decision problems on quantum computers.     

Claw finding algorithms using quantum walk

The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, f$f$ and g$g$, with domain sizes N$N$ and M$M$(N≤M)$(N\le M)$, respectively, and the same range, the goal of the problem is to find x$x$ and y$y$ such that f(x)=g(y)$f\left(x\right)=g\left(y\right)$. This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. It can also be generalized to find a claw of k$k$ functions for any constant integer k>1$k>1$, where the domain sizes of the functions may be different.     

A note on the query complexity of the Condorcet winner problem

Given an unknown tournament over {1,…,n}, we show that the query complexity of the question “Is there a vertex with outdegree n−1?” (known as a Condorcet winner in social choice theory) is exactly 2n−⌊log(n)⌋−2. This stands in stark contrast to the evasiveness of this property in general digraphs.     

A characterization of average case communication complexity

It is well known that the average case deterministic communication complexity is bounded below by an entropic quantity, which one would now call deterministic information complexity. In this paper we show a corresponding upper bound. We also improve known lower bounds for the public coin Las Vegas communication complexity by a constant factor.     

An improved lower bound on query complexity for quantum PAC learning

In this paper, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. For a concept class with VC dimension d, the lower bound is for ? accuracy and 1−δ confidence, where e can be an arbitrarily small positive number. The lower bound is very close to the best lower bound known on query complexity for the classical PAC learning model, which is .     

Quantum implicit computational complexity

We introduce a quantum lambda calculus inspired by Lafont’s Soft Linear Logic and capturing the polynomial quantum complexity classes EQP, BQP and ZQP. The calculus is based on the “classical control and quantum data” paradigm. This is the first example of a formal system capturing quantum complexity classes in the spirit of implicit computational complexity — it is machine-free and no explicit bound (e.g., polynomials) appears in its syntax.     

On the complexity of simulating space-bounded quantum computations

This paper studies the space-complexity of predicting the long-term behavior of a class of stochastic processes based on evolutions and measurements of quantum mechanical systems. These processes generalize a wide range of both quantum and classical space-bounded computations, including unbounded error computations given by machines having algebraic number transition amplitudes or probabilities. It is proved that any space s quantum stochastic process from this class can be simulated probabilistically with unbounded error in space O(s), and therefore deterministically in space O(s²).     

Optimal direct sum results for deterministic and randomized decision tree complexity

A Direct Sum Theorem holds in a model of computation, when for every problem solving some k input instances together is k times as expensive as solving one. We show that Direct Sum Theorems hold in the models of deterministic and randomized decision trees for all relations. We also note that a near optimal Direct Sum Theorem holds for quantum decision trees for boolean functions.     

Constructive dimension equals Kolmogorov complexity

We derive the coincidence of Lutz's constructive dimension and Kolmogorov complexity for sets of infinite strings from Levin's early result on the existence of an optimal left computable cylindrical semi-measure M via simple calculations.     

On the query complexity of finding a local maximum point

We calculate the minimal number of queries sufficient to find a local maximum point of a function on a discrete interval, for a model with M parallel queries, M?1. Matching upper and lower bounds are obtained. The bounds are formulated in terms of certain Fibonacci type sequences of numbers.     

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.     

Indexing dynamic encrypted database in cloud for efficient secure k-nearest neighbor query

Secure k-Nearest Neighbor (k-NN) query aims to find k nearest data of a given query from an encrypted database in a cloud server without revealing privacy to the untrusted cloud and has wide applications in many areas, such as privacy-preserving machine learning and secure biometric identification. Several solutions have been put forward to solve this challenging problem. However, the existing schemes still suffer from various limitations in terms of efficiency and flexibility. In this paper, we propose a new encrypt-then-index strategy for the secure k-NN query, which can simultaneously achieve sub-linear search complexity (efficiency) and support dynamical update over the encrypted database (flexibility). Specifically, we propose a novel algorithm to transform the encrypted database and encrypted query points in the cloud. By indexing the transformed database using spatial data structures such as the R-tree index, our strategy enables sub-linear complexity for secure k-NN queries and allows users to dynamically update the encrypted database. To the best of our knowledge, the proposed strategy is the first to simultaneously provide these two properties. Through theoretical analysis and extensive experiments, we formally prove the security and demonstrate the efficiency of our scheme.     

复杂立方体聚集依赖及其查询技术

针对复杂立方体查询中可能存在的3种聚集依赖(完全依赖、部分依赖和互斥依赖),分别提出了3种基于Cache重用技术的解决方法:完全Cache重用、部分Cache重用以及反Cache重用机制,并相应地给出了计算方法和算法.在模拟和真实数据集上的实验结果表明,不同数据集下改进算法均比基本算法的效率有明显提高,特别地,数据量越大,Cache重用技术的优越性越明显.     

On the algebraic complexity of set equality and inclusion

We present a linear-time algorithm in the algebraic computation tree model for checking whether two sets of integers are equal. The significance of this result is in the fact that it shows that set equality testing is computationally easier when the elements of the sets are restricted to be integers. In addition, we show a linear-time algorithm for checking set inclusion in a slightly extended computational model.