Quantum Online Streaming Algorithms with Logarithmic Memory

被引：13

作者：

Khadiev, Kamil ^{[1
,2
]}

Khadieva, Aliya ^{[2
,3
]}

机构：

[1] Smart Quantum Technol Ltd, Kazan, Russia

[2] Kazan Fed Univ, Kazan, Russia

[3] Univ Latvia, Fac Comp, Riga, Latvia

来源：

INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS | 2021年 / 60卷 / 02期

关键词：

Quantum computation; Online algorithms; Logarithmic space; Streaming algorithms; Online minimization problems; OBDD; Computational complexity; COMPETITIVE ANALYSIS; AUTOMATA; FREQUENT;

D O I：

10.1007/s10773-019-04209-1

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

We consider quantum and classical (deterministic or randomize) streaming online algorithms with respect to competitive ratio. We show that there is a problem that can be solved by a quantum online streaming algorithm better than by classical ones in the case of logarithmic memory. The problem is an online version of the Disjointness problem (Checking weather two sets are disjoint or not).

引用

页码：608 / 616

页数：9

共 37 条

[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] Very narrow quantum OBDDs and width hierarchies for classical OBDDs [J].

Ablayev F. ;

Gainutdinova A. ;

Khadiev K. ;

Yakaryılmaz A. .

Lobachevskii Journal of Mathematics, 2016, 37 (6) :670-682

[4] On quantum realisation of Boolean functions by the fingerprinting technique [J].

Ablayev, F. M. ;

Vasilyev, A. V. .

DISCRETE MATHEMATICS AND APPLICATIONS, 2009, 19 (06) :555-572

[5] 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

[6]

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

[7]

Aggarwal CC, 2014, CH CRC DATA MIN KNOW, P1

[8]

Ambainis A., ARXIV150701988

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

Ambainis, Andris ;

Yakaryilmaz, Abuzer .

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

[10]

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

← 1 2 3 4 →