0000000000625774
AUTHOR
Aliya Khadieva
Quantum Online Algorithms with Respect to Space Complexity
Online algorithm is a well-known computational model. We introduce quantum online algorithms and investigate them with respect to a competitive ratio in two points of view: space complexity and advice complexity. We start with exploring a model with restricted memory and show that quantum online algorithms can be better than classical ones (deterministic or randomized) for sublogarithmic space (memory), and they can be better than deterministic online algorithms without restriction for memory. Additionally, we consider polylogarithmic space case and show that in this case, quantum online algorithms can be better than deterministic ones as well.
Quantum versus Classical Online Streaming Algorithms with Logarithmic Size of Memory
We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in a case of logarithmic or sublogarithmic size of memory.
Two-way quantum and classical machines with small memory for online minimization problems
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).
Quantum versus Classical Online Streaming Algorithms with Advice
We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in a case of logarithmic or sublogarithmic size of memory, even if classical online algorithms get advice bits. Furthermore, we show that a quantum online algorithm with a constant number of qubits can be better than any deterministic online algorithm with a constant number of advice bits and unlimited computational power.
Affine Automata Verifiers
We initiate the study of the verification power of Affine finite automata (AfA) as a part of Arthur-Merlin (AM) proof systems. We show that every unary language is verified by a real-valued AfA verifier. Then, we focus on the verifiers restricted to have only integer-valued or rational-valued transitions. We observe that rational-valued verifiers can be simulated by integer-valued verifiers, and their protocols can be simulated in nondeterministic polynomial time. We show that this upper bound is tight by presenting an AfA verifier for NP-complete problem SUBSETSUM. We also show that AfAs can verify certain non-affine and non-stochastic unary languages.
Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
We consider Quantum OBDD model. It is restricted version of read-once Quantum Branching Programs, with respect to “width” complexity. It is known that maximal complexity gap between deterministic and quantum model is exponential. But there are few examples of such functions. We present method (called “reordering”), which allows to build Boolean function g from Boolean Function f, such that if for f we have gap between quantum and deterministic OBDD complexity for natural order of variables, then we have almost the same gap for function g, but for any order. Using it we construct the total function REQ which deterministic OBDD complexity is \(2^{\varOmega (n/log n)}\) and present quantum OBD…
Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
We consider Quantum OBDD model. It is restricted version of read-once Quantum Branching Programs, with respect to "width" complexity. It is known that maximal complexity gap between deterministic and quantum model is exponential. But there are few examples of such functions. We present method (called "reordering"), which allows to build Boolean function $g$ from Boolean Function $f$, such that if for $f$ we have gap between quantum and deterministic OBDD complexity for natural order of variables, then we have almost the same gap for function $g$, but for any order. Using it we construct the total function $REQ$ which deterministic OBDD complexity is $2^{\Omega(n/\log n)}$ and present quantu…
Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
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…