Search results for "Quantum"
showing 10 items of 9714 documents
High precision quantum query algorithm for computing AND-based boolean functions
2010
Quantum algorithms can be analyzed in a query model to compute Boolean functions. Function input is provided in a black box, and the aim is to compute the function value using as few queries to the black box as possible. The complexity of the algorithm is measured by the number of queries on the worst-case input. In this paper we consider computing AND Boolean function. First, we present a quantum algorithm for AND of two bits. Our algorithm uses one quantum query and correct result is obtained with a probability p=4/5, that improves previous results. The main result is generalization of our approach to design efficient quantum algorithms for computing composite function AND(f1,f2) where fi…
Two-way quantum and classical machines with small memory for online minimization problems
2019
We consider online algorithms. Typically the model is investigated with respect to competitive ratio. In this paper, we explore algorithms with small memory. We investigate two-way automata as a model for online algorithms with restricted memory. We focus on quantum and classical online algorithms. We show that there are problems that can be better solved by two-way automata with quantum and classical states than classical two-way automata in the case of sublogarithmic memory (sublinear size).
An improved quantum query algorithm for computing AND Boolean function
2010
We consider the quantum query model for computing Boolean functions. The definition of the function is known, but a black box contains the input X = (x 1 , x 2 , …, x n ). Black box can be accessed by querying x i values. The goal is to develop an algorithm, which would compute the function value for arbitrary input using as few queries to the black box as possible. We present two different quantum query algorithms for computing the basic Boolean function — logical AND of two bits. Both algorithms use only one query to determine the function value. Correct answer probability for the first algorithm is 80%, but for the second algorithm it is 90%. To compute this function with the same probab…
Classical and Quantum Computations with Restricted Memory
2018
Automata and branching programs are known models of computation with restricted memory. These models of computation were in focus of a large number of researchers during the last decades. Streaming algorithms are a modern model of computation with restricted memory. In this paper, we present recent results on the comparative computational power of quantum and classical models of branching programs and streaming algorithms.
Universal multipartite d-level entanglement witnesses for realistic measurement settings
2019
Entanglement is an essential resource in quantum information science [1] and its presence in any quantum system can be experimentally detected through entanglement witness operators [2]. In particular, measuring a negative expectation value of a witness with high statistical confidence provides a necessary and sufficient condition to confirm the generation of a genuine multipartite [3] and/or d-level entangled state [4]. In recent years, the experimental generation of complex quantum states has intensified the need for witnesses that are capable of detecting such systems and are experimentally optimal at the same time. This means that the witness should require the least measurement effort …
A model of adaptive decision-making from representation of information environment by quantum fields
2017
We present the mathematical model of decision making (DM) of agents acting in a complex and uncertain environment (combining huge variety of economical, financial, behavioral, and geo-political factors). To describe interaction of agents with it, we apply the formalism of quantum field theory (QTF). Quantum fields are of the purely informational nature. The QFT-model can be treated as a far relative of the expected utility theory, where the role of utility is played by adaptivity to an environment (bath). However, this sort of utility-adaptivity cannot be represented simply as a numerical function. The operator representation in Hilbert space is used and adaptivity is described as in quantu…
A Tool for Implementing and Exploring SBM Models: Universal 1D Invertible Cellular Automata
2005
The easiest form of designing Cellular Automata rules with features such as invertibility or particle conserving is to rely on a partitioning scheme, the most important of which is the 2D Margolus neighborhood. In this paper we introduce a 1D Margolus-like neighborhood that gives support to a complete set of Cellular Automata models. We present a set of models called Sliding Ball Models based on this neighborhood and capable of universal computation. We show the way of designing logic gates with these models, propose a digital structure to implement them and finally we present SBMTool, a software development system capable of working with the new models.
Supervised learning of time-independent Hamiltonians for gate design
2018
We present a general framework to tackle the problem of finding time-independent dynamics generating target unitary evolutions. We show that this problem is equivalently stated as a set of conditions over the spectrum of the time-independent gate generator, thus transforming the task to an inverse eigenvalue problem. We illustrate our methodology by identifying suitable time-independent generators implementing Toffoli and Fredkin gates without the need for ancillae or effective evolutions. We show how the same conditions can be used to solve the problem numerically, via supervised learning techniques. In turn, this allows us to solve problems that are not amenable, in general, to direct ana…
Shrinking language models by robust approximation
2002
We study the problem of reducing the size of a language model while preserving recognition performance (accuracy and speed). A successful approach has been to represent language models by weighted finite-state automata (WFAs). Analogues of classical automata determinization and minimization algorithms then provide a general method to produce smaller but equivalent WFAs. We extend this approach by introducing the notion of approximate determinization. We provide an algorithm that, when applied to language models for the North American Business task, achieves 25-35% size reduction compared to previous techniques, with negligible effects on recognition time and accuracy.
Quantum Computers and Quantum Automata
2000
Quantum computation is a most challenging project involving research both by physicists and computer scientists. The principles of quantum computation differ from the principles of classical computation very much. When quantum computers become available, the public-key cryptography will change radically. It is no exaggeration to assert that building a quantum computer means building a universal code-breaking machine. Quantum finite automata are expected to appear much sooner. They do not generalize deterministic finite automata. Their capabilities are incomparable.