Search results for "information science"
showing 10 items of 3627 documents
Symmetry-assisted adversaries for quantum state generation
2011
We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum state generation might be a route to tackle the $backslash$sc Graph Isomorphism problem. We show that for the related problem of $backslash$sc Index Erasure our method leads to a lower bound of $backslash Omega(backslash sqrt N)$ which matches an upper bound obtained via reduction to quantum search on $N$ elements. This closes an open problem first raised by Shi [FOCS'02]. Our approach is …
Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
2007
Consider the problem of evaluating an AND-OR formula on an $N$-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.
Burrows-Wheeler transform and Run-Length Enconding
2017
In this paper we study the clustering effect of the Burrows-Wheeler Transform (BWT) from a combinatorial viewpoint. In particular, given a word w we define the BWT-clustering ratio of w as the ratio between the number of clusters produced by BWT and the number of the clusters of w. The number of clusters of a word is measured by its Run-Length Encoding. We show that the BWT-clustering ratio ranges in ]0, 2]. Moreover, given a rational number \(r\,\in \,]0,2]\), it is possible to find infinitely many words having BWT-clustering ratio equal to r. Finally, we show how the words can be classified according to their BWT-clustering ratio. The behavior of such a parameter is studied for very well-…
Generalized probabilistic modus ponens
2017
Modus ponens (from A and “if A then C” infer C) is one of the most basic inference rules. The probabilistic modus ponens allows for managing uncertainty by transmitting assigned uncertainties from the premises to the conclusion (i.e., from P(A) and P(C|A) infer P(C)). In this paper, we generalize the probabilistic modus ponens by replacing A by the conditional event A|H. The resulting inference rule involves iterated conditionals (formalized by conditional random quantities) and propagates previsions from the premises to the conclusion. Interestingly, the propagation rules for the lower and the upper bounds on the conclusion of the generalized probabilistic modus ponens coincide with the re…
Partial Finitely Generated Bi-Ideals
2016
Partial words have been studied by Blanchet-Sadri et al., but bi-ideals or reccurrent words have been studied for centuries by many researchers. This paper gives a solution for some problems for partial reccurrent words. This paper gives an algorithm for a given finitely generated bi-ideal, how to construct a new basis of ultimately finitely generated bi-ideal, which generates the same given bi-ideal. The paper states that it is always possible to find a basis for a given finitely generated bi-ideal. The main results of this paper are presented in third section. At first, we show that if two irreduciable bi-ideals are different, they will differ in infinitely many places. This led to the st…
Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
2017
We explore multi-round quantum memoryless communication protocols. These are restricted version of multi-round quantum communication protocols. The “memoryless” term means that players forget history from previous rounds, and their behavior is obtained only by input and message from the opposite player. The model is interesting because this allows us to get lower bounds for models like automata, Ordered Binary Decision Diagrams and streaming algorithms. At the same time, we can prove stronger results with this restriction. We present a lower bound for quantum memoryless protocols. Additionally, we show a lower bound for Disjointness function for this model. As an application of communicatio…
The Descriptive Complexity Approach to LOGCFL
1999
Building upon the known generalized-quantifier-based firstorder characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's "hardest contextfree language" is LOGCFL-complete under quantifier-free BIT-free interpre…
Uncountable classical and quantum complexity classes
2018
It is known that poly-time constant-space quantum Turing machines (QTMs) and logarithmic-space probabilistic Turing machines (PTMs) recognize uncountably many languages with bounded error (A.C. Cem Say and A. Yakaryılmaz, Magic coins are useful for small-space quantum machines. Quant. Inf. Comput. 17 (2017) 1027–1043). In this paper, we investigate more restricted cases for both models to recognize uncountably many languages with bounded error. We show that double logarithmic space is enough for PTMs on unary languages in sweeping reading mode or logarithmic space for one-way head. On unary languages, for quantum models, we obtain middle logarithmic space for counter machines. For binary la…
Uncountable Realtime Probabilistic Classes
2018
We investigate the minimal cases for realtime probabilistic machines that can define uncountably many languages with bounded error. We show that logarithmic space is enough for realtime PTMs on unary languages. On non-unary case, we obtain the same result for double logarithmic space, which is also tight. When replacing the work tape with a few counters, we can still achieve similar results for unary linear-space two-counter automata, unary sublinear-space three-counter automata, and non-unary sublinear-space two-counter automata. We also show how to slightly improve the sublinear-space constructions by using more counters.
Theory of tailor automata
2019
Abstract In the paper, a fragment of the new theory of tailor automata is presented, within which a deterministic finite automaton was defined. The proposed automaton provides a theoretical model of an informally characterized biomolecular automaton. The idea of working of which is founded on the concept of alternating cut of some double-stranded fragments of DNA, with the use of a restriction enzyme and ligations of some double-stranded fragments of DNA, with the use of the ligase enzyme.