共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
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. 相似文献
3.
4.
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. 相似文献
5.
6.
The problem MaxLin2 can be stated as follows. We are given a system S of m equations in variables x 1,…,x n , where each equation $\sum_{i \in I_{j}}x_{i} = b_{j}$ is assigned a positive integral weight w j and $b_{j} \in\mathbb{F}_{2}$ , I j ?{1,2,…,n} for j=1,…,m. We are required to find an assignment of values in $\mathbb{F}_{2}$ to the variables in order to maximize the total weight of the satisfied equations. Let W be the total weight of all equations in S. We consider the following parameterized version of MaxLin2: decide whether there is an assignment satisfying equations of total weight at least W?k, where k is a nonnegative parameter. We prove that this parameterized problem is W[1]-hard even if each equation of S has exactly three variables and every variable appears in exactly three equations and, moreover, each weight w j equals 1 and no two equations have the same left-hand side. We show the tightness of this result by proving that if each equation has at most two variables then the parameterized problem is fixed-parameter tractable. We also prove that if no variable appears in more than two equations then we can maximize the total weight of satisfied equations in polynomial time. 相似文献
7.
8.
Nicholas Pippenger 《Journal of Computer and System Sciences》1981,22(3):454-470
We consider algebraic functions that are rational functions of roots (of various degrees) of rational functions of indeterminates. We associate a cost C(d) with the extraction of a dth root and assume that C satisfies certain natural axioms. We show that the minimum cost of computing a finite set of algebraic functions of the form considered is C(d1) + … + C(dr), where d1…dr are the torsion orders of the Galois group of the extension generated by the functions. 相似文献
9.
10.
11.
Abstract. We study the quantum complexity of the static set membership problem: given a subset S (|S| ≤ n ) of a universe of size m ( >> n ), store it as a table, T: {0,1}
r
--> {0,1} , of bits so that queries of the form ``Is x in S ?' can be answered. The goal is to use a small table and yet answer queries using few bit probes. This problem was considered
recently by Buhrman et al. [BMRV], who showed lower and upper bounds for this problem in the classical deterministic and randomized
models. In this paper we formulate this problem in the ``quantum bit probe model'. We assume that access to the table T is provided by means of a black box (oracle) unitary transform O
T
that takes the basis state | y,b > to the basis state | y,b
T(y) > . The query algorithm is allowed to apply O
T
on any superposition of basis states.
We show tradeoff results between space (defined as 2
r
) and number of probes (oracle calls) in this model. Our results show that the lower bounds shown in [BMRV] for the classical
model also hold (with minor differences) in the quantum bit probe model. These bounds almost match the classical upper bounds.
Our lower bounds are proved using linear algebraic arguments. 相似文献
12.
13.
We consider the problem of testing the commutativity of a black-box group specified by its k generators. The complexity (in
terms of k) of this problem was first considered by Pak, who gave a randomized algorithm involving O(k) group operations.
We construct a quite optimal quantum algorithm for this problem whose complexity is in
. The algorithm uses and highlights the power of the quantization method of
Szegedy. For the lower bound of
, we give a reduction from a special case of Element Distinctness to our problem. Along the way, we prove the optimality of
the algorithm of Pak for the randomized model. 相似文献
14.
Abstract. We describe a quantum black-box network computing the majority of N bits with zero-sided error ɛ using only
queries: the algorithm returns the correct answer with probability at least 1 - ɛ , and ``I don't know' otherwise. Our algorithm is given as a randomized ``XOR decision tree' for which the number of queries
on any input is strongly concentrated around a value of at most 2/3N . We provide a nearly matching lower bound of
on the expected number of queries on a worst-case input in the randomized XOR decision tree model with zero-sided error
o(1) . Any classical randomized decision tree computing the majority on N bits with zero-sided error 1/2 has cost N . 相似文献
15.
John A. Clark Jeremy L. Jacob Subhamoy Maitra Pantelimon Stnic 《Computational Intelligence》2004,20(3):450-462
The design of Boolean functions with properties of cryptographic significance is a hard task. In this paper, we adopt an unorthodox approach to the design of such functions. Our search space is the set of functions that possess the required properties. It is "Boolean-ness" that is evolved. 相似文献
16.
估算查询结果大小的直方图方法之研究 总被引:11,自引:0,他引:11
直方图是许多商用数据库系统中最常用的一种估算查询结果大小的方法.从实用的观点来看,过去已提出的一些直方图方法有局限性,主要是它们不能保证估算值的准确程度.本文将提出两种新的直方图方法,它们不仅使用方便,而且可以保证所有的估算值均在给定的误差范围内.此外,本文还探讨了不同的数据分布对直方图的影响,通过运用一些重要的参数刻画数据分布,用以帮助生成效果较佳的直方图. 相似文献
17.
18.
Leopoldo Bertossi Solmaz Kolahi Laks V. S. Lakshmanan 《Theory of Computing Systems》2013,52(3):441-482
Matching dependencies were recently introduced as declarative rules for data cleaning and entity resolution. Enforcing a matching dependency on a database instance identifies the values of some attributes for two tuples, provided that the values of some other attributes are sufficiently similar. Assuming the existence of matching functions for making two attribute values equal, we formally introduce the process of cleaning an instance using matching dependencies, as a chase-like procedure. We show that matching functions naturally introduce a lattice structure on attribute domains, and a partial order of semantic domination between instances. Using the latter, we define the semantics of clean query answering in terms of certain/possible answers as the greatest lower bound/least upper bound of all possible answers obtained from the clean instances. We show that clean query answering is intractable in general. Then we study queries that behave monotonically w.r.t. semantic domination order, and show that we can provide an under/over approximation for clean answers to monotone queries. Moreover, non-monotone positive queries can be relaxed into monotone queries. 相似文献
19.
有固定波长转换器的全光环网波长分配算法 总被引:2,自引:1,他引:2
采用波分复用技术的全光网是目前宽带网络研究的方向之一,波长分配是其中主要的算法问题,具有重要的理论和应用价值.研究了具有任意固定波长转换器的环形光网上的波长分配问题.首先,提出了两个对环网上的请求集合预处理的算法,这两个算法可以将请求集合分解成一些连续的循环序列;然后,采用置换群来描述具有固定波长转换器的光环网,基于这种数学表示,提出了对环网上的波长信道进行分解的算法;基于这些算法,进一步提出了一个波长分配算法,该算法对于环形光网上的任意固定转换模式都能给出一个较好的波长分配方案. 相似文献
20.
Several results on the monotone circuit complexity and the conjunctive complexity, i.e., the minimal number of AND gates in
monotone circuits, of quadratic Boolean functions are proved. We focus on the comparison between single level circuits, which
have only one level of AND gates, and arbitrary monotone circuits, and show that there is an exponential gap between the conjunctive
complexity of single level circuits and that of general monotone circuits for some explicit quadratic function. Nearly tight
upper bounds on the largest gap between the single level conjunctive complexity and the general conjunctive complexity over
all quadratic functions are also proved. Moreover, we describe the way of lower bounding
the single level circuit complexity and give a set of quadratic functions whose monotone complexity is strictly smaller than
its single level complexity. 相似文献