| Identifikační kód | RIV/00216224:14330/15:00084456 |
|---|
| Název v anglickém jazyce | Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2015 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 1 |
|---|
| Počet tvůrců celkem | 3 |
|---|
| Počet domácích tvůrců | 2 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Shenggen Zheng (státní příslušnost: CN - Čínská lidová republika, domácí tvůrce: A)
Daowen QIU (státní příslušnost: CN - Čínská lidová republika)
Jozef Gruska (státní příslušnost: SK - Slovenská republika, domácí tvůrce: A, vedidk: 9594744) |
|---|
| Popis výsledku v anglickém jazyce | Interactive proof systems (IP) are very powerful - languages they can accept form exactly PSPACE. They represent also one of the very fundamental concepts of theoretical computing and a model of computation by interactions. One of the key players in IP is verifier. In the original model of IP whose power is that of PSPACE, the only restriction on verifiers is that they work in randomized polynomial time. Because of such key importance of IP, it is of large interest to find out how powerful will IP be when verifiers are more restricted. So far this was explored for the case that verifiers are two-way probabilistic finite automata (Dwork and Stockmeyer, 1990) and one-way quantum finite automata as well as two-way quantum finite automata (Nishimura and Yamakami, 2009). IP in which verifiers use public randomization is called Arthur-Merlin proof systems (AM). AM with verifiers modeled by Turing Machines augmented with a fixed-size quantum register (qAM) were studied also by Yakaryilmaz (20 |
|---|
| Klíčová slova oddělená středníkem | Quantum computing; Quantum finite automata; Quantum Arthur?Merlin proof systems; Two-way finite automata with quantum and classical states |
|---|
| Stránka www, na které se nachází výsledek | http://www.sciencedirect.com/science/article/pii/S0890540115000140 |
|---|
| DOI výsledku | 10.1016/j.ic.2015.02.003 |
|---|