Search results for " Complexity"
showing 10 items of 623 documents
Quadratically Tight Relations for Randomized Query Complexity
2020
In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity R0(f): C(f) ≤R0(f) ≤C(f)2. In the first part of the paper we introduce a new complexity measure, expectational certificate complexity EC(f), which is also a quadratically tight bound on R0(f): EC(f) ≤R0(f) = O(EC(f)2). For R(f), we prove that EC2/3 ≤R(f). We then prove that EC(f) ≤C(f) ≤EC(f)2 and show that there is a quadratic separation between the two, thus EC(f) gives a tighter upper bound for R0(f). The measure is also related to the fractional…
On the class of languages recognizable by 1-way quantum finite automata
2000
It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.
Local softening of information geometric indicators of chaos in statistical modeling in the presence of quantum-like considerations
2013
In a previous paper (C. Cafaro et al., 2012), we compared an uncorrelated 3D Gaussian statistical model to an uncorrelated 2D Gaussian statistical model obtained from the former model by introducing a constraint that resembles the quantum mechanical canonical minimum uncertainty relation. Analysis was completed by way of the information geometry and the entropic dynamics of each system. This analysis revealed that the chaoticity of the 2D Gaussian statistical model, quantified by means of the Information Geometric Entropy (IGE), is softened or weakened with respect to the chaoticity of the 3D Gaussian statistical model due to the accessibility of more information. In this companion work, we…
The class of languages recognizable by 1-way quantum finite automata is not closed under union
2000
In this paper we develop little further the theory of quantum finite automata (QFA). There are already few properties of QFA known, that deterministic and probabilistic finite automata do not have e.g. they cannot recognize all regular languages. In this paper we show, that class of languages recognizable by QFA is not closed under union, even not under any Boolean operation, where both arguments are significant.
Grover’s Search with Faults on Some Marked Elements
2018
Grover’s algorithm is a quantum query algorithm solving the unstructured search problem of size [Formula: see text] using [Formula: see text] queries. It provides a significant speed-up over any classical algorithm [3]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [2, 6]. We study the behavior of Grover’s algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of marked elements in [Formula: see text] queries. We also analyze…
Quantum Lower Bound for Graph Collision Implies Lower Bound for Triangle Detection
2015
We show that an improvement to the best known quantum lower bound for GRAPH-COLLISION problem implies an improvement to the best known lower bound for TRIANGLE problem in the quantum query complexity model. In GRAPH-COLLISION we are given free access to a graph $(V,E)$ and access to a function $f:V\rightarrow \{0,1\}$ as a black box. We are asked to determine if there exist $(u,v) \in E$, such that $f(u)=f(v)=1$. In TRIANGLE we have a black box access to an adjacency matrix of a graph and we have to determine if the graph contains a triangle. For both of these problems the known lower bounds are trivial ($\Omega(\sqrt{n})$ and $\Omega(n)$, respectively) and there is no known matching upper …
Quantum versus classical query complexity of relation
2011
This paper investigates the computability of mathematical relations in a quantum query model. The important task in complexity theory is to find examples with a large gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design that allow achieving a large separation between classical and quantum query complexity of a specific relation. We demonstrate an example where quantum query algorithm for a finite relation needs more than two times fewer queries than the best possible classical analogue. We also show that relation can be extended to infinite family of relations with an input of general size N.
Adequate number of consumers in a liking test. Insights from resampling in seven studies
2014
The recommended number of consumers to be enrolled in a hedonic test comparing several products usually ranges from 50 to 100, at least if no liking segmentation is sought. This paper seeks to examine whether such a panel size range is adequate, by means of 7 trials with different levels of product space complexity. Five types of products were tested: Two varied in fattiness and sweetness and were tested under the same conditions in two separate laboratories (4 trials); the remaining three, varying in taste and texture, were each tested in a different laboratory (3 trials). Each of the 7 trials was run by a different laboratory. Each of the seven laboratories enrolled in its trial 150 consu…
Cracking the Code : The Impact of Orthographic Transparency and Morphological-Syllabic Complexity on Reading and Developmental Dyslexia
2019
Reading is an essential skill in modern societies, yet not all learners necessarily become proficient readers. Theoretical concepts (e.g., the orthographic depth hypothesis; the grain size theory) as well as empirical evidence suggest that certain orthographies are easier to learn than others. The present paper reviews the literature on orthographic transparency, morphological complexity, and syllabic complexity of alphabetic languages. These notions are elaborated to show that differences in reading acquisition reflect fundamental differences in the nature of the phonological recoding and reading strategies developing in response to the specific orthography to be learned. The present paper…
Flanking regions determine the structure of the poly-glutamine homo- repeat in huntingtin through mechanisms common among glutamine-rich human protei…
2020
International audience; The causative agent of Huntington's disease, the poly-Q homo-repeat in the N-terminal region of huntingtin (httex1), is flanked by a 17-residue-long fragment (N17) and a proline-rich region (PRR), which promote and inhibit the aggregation propensity of the protein, respectively, by poorly understood mechanisms. Based on experimental data obtained from site-specifically labeled NMR samples, we derived an ensemble model of httex1 that identified both flanking regions as opposing poly-Q secondary structure promoters. While N17 triggers helicity through a promiscuous hydrogen bond network involving the side chains of the first glutamines in the poly-Q tract, the PRR prom…