Quantum Online Streaming Algorithms with Logarithmic Memory

Kamil Khadiev; Aliya Khadieva

doi:10.1007/s10773-019-04209-1

Quantum Online Streaming Algorithms with Logarithmic Memory

Kamil Khadiev
, Aliya Khadieva

Kazan Volga Region Federal University

Research output: Contribution to journal › Article › peer-review

19 Citations (Scopus)

Abstract

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

Original language	English
Pages (from-to)	608-616
Number of pages	9
Journal	International Journal of Theoretical Physics
Volume	60
Issue number	2
DOIs	https://doi.org/10.1007/s10773-019-04209-1
Publication status	Published - Feb 2021

Keywords

Computational complexity
Logarithmic space
OBDD
Online algorithms
Online minimization problems
Quantum computation
Streaming algorithms

OECD Field of Science

1.2 Computer and Information Sciences

Access to Document

10.1007/s10773-019-04209-1

Cite this

@article{118a632ae00644809310b02c75a65b8b,

title = "Quantum Online Streaming Algorithms with Logarithmic Memory",

abstract = "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).",

keywords = "Computational complexity, Logarithmic space, OBDD, Online algorithms, Online minimization problems, Quantum computation, Streaming algorithms",

author = "Kamil Khadiev and Aliya Khadieva",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2021",

month = feb,

doi = "10.1007/s10773-019-04209-1",

language = "English",

volume = "60",

pages = "608--616",

journal = "International Journal of Theoretical Physics",

issn = "0020-7748",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Quantum Online Streaming Algorithms with Logarithmic Memory

AU - Khadiev, Kamil

AU - Khadieva, Aliya

PY - 2021/2

Y1 - 2021/2

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

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

KW - Computational complexity

KW - Logarithmic space

KW - OBDD

KW - Online algorithms

KW - Online minimization problems

KW - Quantum computation

KW - Streaming algorithms

UR - https://link.springer.com/article/10.1007%252Fs10773-019-04209-1

UR - https://www.scopus.com/pages/publications/85069145774

U2 - 10.1007/s10773-019-04209-1

DO - 10.1007/s10773-019-04209-1

M3 - Article

SN - 0020-7748

VL - 60

SP - 608

EP - 616

JO - International Journal of Theoretical Physics

JF - International Journal of Theoretical Physics

IS - 2

ER -

Quantum Online Streaming Algorithms with Logarithmic Memory

Abstract

Keywords

OECD Field of Science

Access to Document

Other files and links

Fingerprint

Cite this