Search results for "abstract"
showing 10 items of 1959 documents
Implications of quantum automata for contextuality
2014
We construct zero error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded error probabilistic finite automata (PFAs). Here is a summary of our results: There is a promise problem solvable by an exact two way QFA in exponential expected time but not by any bounded error sublogarithmic space probabilistic Turing machine (PTM). There is a promise problem solvable by an exact two way QFA in quadratic expected time but not by any bounded error o(loglogn) space PTMs in polynomial expected time. The same problem can be solvable by a one way Las Vegas (or exact two way) QFA with quantum head in linear (expected) time. There is a promise problem solvable by a Las …
A Newman property for BLD-mappings
2019
We define a Newman property for BLD-mappings and prove that for a BLD-mapping between generalized manifolds equipped with complete path-metrics, this property is equivalent to the branch set being porous when the codomain is LLC. peerReviewed
Positive definite functions of finitary isometry groups over fields of odd characteristic
2007
Abstract This paper is part of a programme to describe the lattice of all two-sided ideals in complex group algebras of simple locally finite groups. Here we determine the extremal normalized positive definite functions for finitary groups of isometries, defined over fields of odd characteristic.
On the regularity of the partial {$O\sp *$}-algebras generated by a closed symmetric operator
1992
Let be given a dense domain D in a Hilbert space and a closed symmetric operator T with domain containing D. Then the restriction of T to D generates (algebraically) two partial *-algebras of closable operators (called weak and strong), possibly nonabelian and nonassociative. We characterize them completely. In particular, we examine under what conditions they are regular, that is, consist of polynomials only, and standard. Simple differential operators provide concrete examples of all the pathologies allowed by the abstract theory.
Identities of *-superalgebras and almost polynomial growth
2015
We study the growth of the codimensions of a *-superalgebra over a field of characteristic zero. We classify the ideals of identities of finite dimensional algebras whose corresponding codimensions are of almost polynomial growth. It turns out that these are the ideals of identities of two algebras with distinct involutions and gradings. Along the way, we also classify the finite dimensional simple *-superalgebras over an algebraically closed field of characteristic zero.
Generalized ``transition probability''
1975
An operationally meaningful symmetric function defined on pairs of states of an arbitrary physical system is constructed and is shown to coincide with the usual “transition probability” in the special case of systems admitting a quantum-mechanical description. It can be used to define a metric in the set of physical states. Conceivable applications to the analysis of certain aspects of Quantum Mechanics and to its possible modifications are mentioned.
A simple algorithm for generating neuronal dendritic trees
1990
Abstract A simple, efficient algorithm is presented for generating the codewords of all neuronal dendritic trees with a given number of terminal nodes. Furthermore, a procedure is developed for deciding if different codewords correspond to topologically equivalent trees.
Quantum walks on two-dimensional grids with multiple marked locations
2015
The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration (the placement and the number) of marked locations. While the first dependence has been studied in a number of papers, the second dependence remains mostly unstudied.We study search by quantum walks on the two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [3]. The original paper analyses one and two marked locations only. We move beyond two marked locations and study the behaviour of the algorithm for several configurations of multiple marked locations.In this paper, we prove two results showing the importance of how the marked locations ar…
Improved constructions of quantum automata
2008
We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use \frac{4}{\epsilon} \log 2p + O(1) states to recognize a language that requires p states classically. The construction is both substantially simpler and achieves a better constant in the front of \log p than the previously known construction of Ambainis and Freivalds (quant-ph/9802062). Similarly to Ambainis and Freivalds, our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some results in this direction.
Logics for context-free languages
1995
We define matchings, and show that they capture the essence of context-freeness. More precisely, we show that the class of context-free languages coincides with the class of those sets of strings which can be defined by sentences of the form ∃ bϕ, where ϕ is first order, b is a binary predicate symbol, and the range of the second order quantifier is restricted to the class of matchings. Several variations and extensions are discussed.