An application of quantum finite automata to interactive proof systems

被引：17

作者：

Nishimura, Harumichi ^{[1
]}

Yamakami, Tomoyuki ^{[1
]}

机构：

[1] Trent Univ, Comp Sci Program, Peterborough, ON K9J 7B8, Canada

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2009年 / 75卷 / 04期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Quantum finite automaton; Quantum interactive proof system; Quantum measurement; Quantum circuit; STATE VERIFIERS; ZERO-KNOWLEDGE; COMPUTATION; COMPUTERS; MACHINES; PSPACE; POWER;

D O I：

10.1016/j.jcss.2008.12.001

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Quantum finite automata have been studied intensively since their introduction in late 1990s as a natural model of a quantum computer working with finite-dimensional quantum memory space. This paper seeks their direct application to interactive proof systems in which a mighty quantum prover communicates with a quantum-automaton verifier through a common communication cell. Our quantum interactive proof systems are juxtaposed to Dwork-Stockmeyer's classical interactive proof systems whose verifiers are two-way probabilistic finite automata. We demonstrate strengths and weaknesses of our systems by studying how various restrictions on the behaviors of quantum-automaton verifiers affect the power of quantum interactive proof systems. (C) 2008 Published by Elsevier Inc.

引用

页码：255 / 269

页数：15

共 43 条

[1] A lattice problem in quantum NP [J].

Aharonov, D ;

Regev, O .

44TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2003, :210-219

[2]

AHARONOV D, ARXIVQUANTPH0210077

[3]

Amano M., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P368, DOI 10.1145/301250.301344

[4]

Ambainis A, 2004, LECT NOTES COMPUT SC, V2996, P93

[5] Two-way finite automata with quantum and classical states [J].

Ambainis, A ;

Watrous, J .

THEORETICAL COMPUTER SCIENCE, 2002, 287 (01) :299-311

[6]

[Anonymous], 1999, Quantum Computing

[7]

Babai Laszlo., 1985, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, STOC'85, P421

[8] THE COMPUTER AS A PHYSICAL SYSTEM - A MICROSCOPIC QUANTUM-MECHANICAL HAMILTONIAN MODEL OF COMPUTERS AS REPRESENTED BY TURING-MACHINES [J].

BENIOFF, P .

JOURNAL OF STATISTICAL PHYSICS, 1980, 22 (05) :563-591

[9] PARALLEL COMPUTATION FOR WELL-ENDOWED RINGS AND SPACE-BOUNDED PROBABILISTIC MACHINES [J].

BORODIN, A ;

COOK, S ;

PIPPENGER, N .

INFORMATION AND CONTROL, 1983, 58 (1-3) :113-136

[10] Characterizations of 1-way quantum finite automata [J].

Brodsky, A ;

Pippenger, N .

SIAM JOURNAL ON COMPUTING, 2002, 31 (05) :1456-1478

← 1 2 3 4 5 →