Time-space complexity advantages for quantum computing

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F17%3A00100568" target="_blank" >RIV/00216224:14330/17:00100568 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-71069-3_24" target="_blank" >http://dx.doi.org/10.1007/978-3-319-71069-3_24</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-71069-3_24" target="_blank" >10.1007/978-3-319-71069-3_24</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Time-space complexity advantages for quantum computing

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Time-space complexity advantages for quantum computing

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Lecture Notes in Computer Science, Volume 10687: 6th International Conference on Theory and Practice of Natural Computing, TPNC 2017

ISBN

9783319710686

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

305-317

Název nakladatele

Springer

Místo vydání

Cham, Switzerland

Místo konání akce

Praha

Datum konání akce

1. 1. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000450354700024