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

Zinātniskās darbības rezultāts: Devums žurnālam › Zinātniskais raksts (žurnālā) › koleģiāli recenzēts

19 Atsauces (Scopus)

Kopsavilkums

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

Oriģinālvaloda	Angļu
Lapas (no-līdz)	608-616
Lapu skaits	9
Žurnāls	International Journal of Theoretical Physics
Sējums	60
Izdevuma numurs	2
DOIs	https://doi.org/10.1007/s10773-019-04209-1
Publikācijas statuss	Publicēts - febr. 2021

OECD Zinātnes nozare

1.2 Datorzinātne un informātika

Piekļuve Dokumentiem

10.1007/s10773-019-04209-1

Citi faili un saites

Citēt šo

@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

Kopsavilkums

OECD Zinātnes nozare

Piekļuve Dokumentiem

Citi faili un saites

Nospiedums

Citēt šo