A method of synthesis of modulo-three adders for the case of data representation in positional codes is presented. The method is oriented to the construction of two-level circuits consisting of OR elements and exclusi...
详细信息
A method of synthesis of modulo-three adders for the case of data representation in positional codes is presented. The method is oriented to the construction of two-level circuits consisting of OR elements and exclusive OR elements with given thresholds. The method is generalized to the realization of the operation +/- X-1 +/- X-2 ... +/- X-n = S (mod 3). A logical circuit of an adder with a controlled input is suggested such that the value of one of the digits of the result of the summation is realized on its single output.
Many data-intensive applications have to query a database that involves sequences of sets of objects. It is not uncommon that the order of the sets in such a sequence does not affect the result of the query. Such quer...
详细信息
Many data-intensive applications have to query a database that involves sequences of sets of objects. It is not uncommon that the order of the sets in such a sequence does not affect the result of the query. Such queries are called symmetric. In this paper, the authors wish to initiate research on symmetric queries. Thereto, a data model is proposed in which a binary relation between objects and set names encodes set membership. On this data model, two query languages are introduced, QuineCALC and SyCALC. They are correlated in a manner that is made precise with the symmetric boolean functions of Quine, respectively symmetric relational functions, on sequences of sets of given length. The latter do not only involve the boolean operations union, intersection, and complement, but also projection and Cartesian product. Quine's characterization of symmetric boolean functions in terms of incidence information is generalized to QuineCALC queries. In the process, an incidence-based normal form for QuineCALC queries is proposed. Inspired by these desirable incidence-related properties of QuineCALC queries, counting-only queries are introduced as SyCALC queries for which the result only depends on incidence information. Counting-only queries are then characterized as quantified boolean combinations of QuineCALC queries, and a normal form is proposed for them as well. Finally, it is shown that, while it is undecidable whether a SyCALC query is counting-only, it is decidable whether a counting-only query is a QuineCALC query.
The Deutsch-Jozsa algorithm is essentially faster than any possible deterministic classical algorithm for solving a promise problem that is in fact a symmetric partial boolean function, named as the Deutsch-Jozsa prob...
详细信息
The Deutsch-Jozsa algorithm is essentially faster than any possible deterministic classical algorithm for solving a promise problem that is in fact a symmetric partial boolean function, named as the Deutsch-Jozsa problem. The Deutsch-Jozsa problem can be equivalently described as a partial function DJ(n)(0):{0, 1}(n)->{0, 1} defined as: DJ(n)(0)(x) = 1 for vertical bar x vertical bar = n/2, DJ(n)(0)(x) = 0 for vertical bar x vertical bar = 0,n, and it is undefined for the remaining cases, where n is even, and vertical bar x vertical bar is the Hamming weight of x. The Deutsch-Jozsa algorithm needs only one query to compute DJ(n)(0) but the classical deterministic algorithm requires n/2 + 1 queries to compute it in the worse case. We present all symmetric partial booleanfunctions with degree 1 and 2;We prove the exact quantum query complexity of all symmetric partial booleanfunctions with degree 1 and 2. We prove Deutsch-Jozsa algorithm can compute any symmetric partial boolean function f with exact quantum 1-query complexity. (C) 2020 Elsevier Inc. All rights reserved.
A network which sorts n numbers, when used to sort numbers of only two sizes, 0 and 1, can be regarded as forming the n frontal (unite) symmetric boolean functions of n arguments When sorting networks are constructed ...
详细信息
暂无评论