Quantum online algorithms with respect to space and advice complexity
From MaRDI portal
Publication:669542
DOI10.1134/S1995080218090421zbMath1431.68039OpenAlexW2910965761WikidataQ128683567 ScholiaQ128683567MaRDI QIDQ669542
Aliya Khadieva, Kamil Khadiev, Ilnaz Mannapov
Publication date: 15 March 2019
Published in: Lobachevskii Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1134/s1995080218090421
computational complexityonline algorithmsquantum computingadvice complexityquantum modelsquantum vs classical
Quantum computation (81P68) Online algorithms; streaming algorithms (68W27) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items
Two-way and one-way quantum and classical automata with advice for online minimization problems, Online \(L(2,1)\)-coloring problem on paths with restricted size of memory, Quantum versus classical online streaming algorithms with logarithmic size of memory, Quantum algorithm for dynamic programming approach for DAGs and applications, Quantum online streaming algorithms with logarithmic memory, The fast algorithm for online \(k\)-server problem on trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Extension of the hierarchy for \(k\)-OBDDs of small width
- Superiority of exact quantum automata for promise problems
- Competitive analysis of maintaining frequent items of a stream
- A comparison of performance measures for online algorithms
- Width hierarchy for \(k\)-OBDD of small width
- Error-free affine, unitary, and probabilistic OBDDs
- Comparative complexity of quantum and classical OBDDs for total and partial functions
- Improved constructions of quantum automata
- The advice complexity of a class of hard online problems
- Design and analysis of randomized algorithms. Introduction to design paradigms.
- Quantum branching programs and space-bounded nonuniform quantum complexity
- New size hierarchies for two way automata
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
- Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
- On the computational power of probabilistic and quantum branching program
- Weighted Online Problems with Advice
- The Frequent Items Problem in Online Streaming Under Various Performance Measures
- On quantum realisation of Boolean functions by the fingerprinting technique
- Competitive Analysis of Aggregate Max in Windowed Streaming
- Branching Programs and Binary Decision Diagrams
- Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
- Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
- Measuring the problem-relevant information in input
- Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs
- Improved Constructions of Quantum Automata
- Classical and Quantum Computations with Restricted Memory
