Two-Way Quantum and Classical Machines with Small Memory for Online Minimization Problems

被引：10

作者：

Khadiev, Kamil ^{[1
,2
]}

Khadieva, Aliya ^{[2
,3
]}

机构：

[1] Smart Quantum Technol Ltd, K Marks 5-36, Kazan, Russia

[2] Kazan Fed Univ, Kremlevskaya 18, Kazan, Russia

[3] Univ Latvia, Raina 19, Riga, Latvia

来源：

INTERNATIONAL CONFERENCE ON MICRO- AND NANO-ELECTRONICS 2018 | 2019年 / 11022卷

基金：

俄罗斯科学基金会;

关键词：

quantum computation; online algorithms; two-way automata; online minimization problems; OBDD; automata; computational complexity; COMPETITIVE ANALYSIS; FINITE AUTOMATA; COMPLEXITY; FREQUENT;

D O I：

10.1117/12.2522462

中图分类号：

TB3 [工程材料学];

学科分类号：

0805 ; 080502 ;

摘要：

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).

引用

页数：9

共 36 条

[1] On the computational power of probabilistic and quantum branching program [J].

Ablayev, F ;

Gainutdinova, A ;

Karpinski, M ;

Moore, C ;

Pollett, C .

INFORMATION AND COMPUTATION, 2005, 203 (02) :145-162

[2]

Ablayev Farid, 2018, Adventures Between Lower Bounds and Higher Altitudes. Essays Dedicated to Juraj Hromkovic on the Occasion of His 60th Birthday. Lecture Notes in Computer Science (LNCS 11011), P129, DOI 10.1007/978-3-319-98355-4_9

[3] Extension of the Hierarchy for k-OBDDs of Small Width [J].

Ablayev, F. M. ;

Khadiev, K. R. .

RUSSIAN MATHEMATICS, 2013, 57 (03) :46-50

[4] Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test [J].

Ablayev, Farid ;

Ambainis, Andris ;

Khadiev, Kamil ;

Khadieva, Aliya .

SOFSEM 2018: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2018, 10706 :197-211

[5]

Ablayev F, 2014, LECT NOTES COMPUT SC, V8614, P53, DOI 10.1007/978-3-319-09704-6_6

[6]

Albers S., 1996, BRICS MINICOURSE COM

[7] Two-way finite automata with quantum and classical states [J].

Ambainis, A ;

Watrous, J .

THEORETICAL COMPUTER SCIENCE, 2002, 287 (01) :299-311

[8] Superiority of exact quantum automata for promise problems [J].

Ambainis, Andris ;

Yakaryilmaz, Abuzer .

INFORMATION PROCESSING LETTERS, 2012, 112 (07) :289-291

[9]

[Anonymous], 2015, AUTOMATA QUANTUM COM

[10]

Becchetti L, 2009, LECT NOTES COMPUT SC, V5555, P156, DOI 10.1007/978-3-642-02927-1_15

← 1 2 3 4 →