Time-space complexity advantages for quantum computing

D 2017

Time-space complexity advantages for quantum computing

GRUSKA, Jozef

Základní údaje

Originální název

Time-space complexity advantages for quantum computing

Autoři

GRUSKA, Jozef (703 Slovensko, garant, domácí)

Vydání

Cham, Switzerland, Lecture Notes in Computer Science, Volume 10687: 6th International Conference on Theory and Practice of Natural Computing, TPNC 2017, od s. 305-317, 13 s. 2017

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/17:00100568

Organizační jednotka

Fakulta informatiky

ISBN

978-3-319-71068-6

ISSN

DOI

http://dx.doi.org/10.1007/978-3-319-71069-3_24

UT WoS

000450354700024

Klíčová slova anglicky

Quantum computing; Time-space complexity

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 5. 11. 2021 12:52, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

It has been proved that quantum computing has advantages in query complexity, communication complexity and also other computing models. However, it is hard to prove strictly that quantum computing has advantage in the Turing machine models in time complexity. For example, we do not know how to prove that Shor’s algorithm is strictly better than any classical algorithm, since we do not know the lower bound of time complexity of the factoring problem in Turing machine. In this paper, we consider the time-space complexity and prove strictly that quantum computing has advantages compared to their classical counterparts. We prove: (1) a time-space upper bound for recognition of the languages LI N T(n) on two-way finite automata with quantum and classical states (2QCFA): TS= O(n3/2log n), whereas a lower bound on probabilistic Turing machine is TS= Omega(n2); (2) a time-space upper bound for recognition of the languages LN E(n) on exact 2QCFA: TS= O(n1.87log n), whereas a lower bound on probabilistic Turing machine is TS= Omega(n2). It has been proved (Klauck, STOC’00) that the exact one-way quantum finite automata have no advantage comparing to classical finite automata in recognizing languages. However, the result (2) shows that the exact 2QCFA do have an advantage in comparison with their classical counterparts, which is the first example showing that the exact quantum computing has advantage in time-space complexity comparing to classical computing.

Citovat

GRUSKA, Jozef. Time-space complexity advantages for quantum computing. In Carlos Martín-Vide, Roman Neruda, Miguel A. Vega-Rodríguez. Lecture Notes in Computer Science, Volume 10687: 6th International Conference on Theory and Practice of Natural Computing, TPNC 2017. Cham, Switzerland: Springer, 2017, s. 305-317. ISBN 978-3-319-71068-6. Dostupné z: https://dx.doi.org/10.1007/978-3-319-71069-3_24.

@inproceedings{1414967,
   author = {Gruska, Jozef},
   address = {Cham, Switzerland},
   booktitle = {Lecture Notes in Computer Science, Volume 10687: 6th International Conference on Theory and Practice of Natural Computing, TPNC 2017},
   doi = {http://dx.doi.org/10.1007/978-3-319-71069-3_24},
   editor = {Carlos Martín-Vide, Roman Neruda, Miguel A. Vega-Rodríguez},
   keywords = {Quantum computing; Time-space complexity},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham, Switzerland},
   isbn = {978-3-319-71068-6},
   pages = {305-317},
   publisher = {Springer},
   title = {Time-space complexity advantages for quantum computing},
   year = {2017}
}

TY  - JOUR
ID  - 1414967
AU  - Gruska, Jozef
PY  - 2017
TI  - Time-space complexity advantages for quantum computing
PB  - Springer
CY  - Cham, Switzerland
SN  - 9783319710686
KW  - Quantum computing
KW  - Time-space complexity
N2  - It has been proved that quantum computing has advantages in query complexity, communication complexity and also other computing models. However, it is hard to prove strictly that quantum computing has advantage in the Turing machine models in time complexity. For example, we do not know how to prove that Shor’s algorithm is strictly better than any classical algorithm, since we do not know the lower bound of time complexity of the factoring problem in Turing machine. In this paper, we consider the time-space complexity and prove strictly that quantum computing has advantages compared to their classical counterparts. We prove: (1) a time-space upper bound for recognition of the languages LI N T(n) on two-way finite automata with quantum and classical states (2QCFA): TS= O(n3/2log n), whereas a lower bound on probabilistic Turing machine is TS= Omega(n2); (2) a time-space upper bound for recognition of the languages LN E(n) on exact 2QCFA: TS= O(n1.87log n), whereas a lower bound on probabilistic Turing machine is TS= Omega(n2). It has been proved (Klauck, STOC’00) that the exact one-way quantum finite automata have no advantage comparing to classical finite automata in recognizing languages. However, the result (2) shows that the exact 2QCFA do have an advantage in comparison with their classical counterparts, which is the first example showing that the exact quantum computing has advantage in time-space complexity comparing to classical computing.
ER  -

GRUSKA, Jozef. Time-space complexity advantages for quantum computing. In Carlos Martín-Vide, Roman Neruda, Miguel A. Vega-Rodríguez. \textit{Lecture Notes in Computer Science, Volume 10687: 6th International Conference on Theory and Practice of Natural Computing, TPNC 2017}. Cham, Switzerland: Springer, 2017, s.~305-317. ISBN~978-3-319-71068-6. Dostupné z: https://dx.doi.org/10.1007/978-3-319-71069-3\_{}24.

Podrobný výpis o publikaci