首页    期刊浏览 2024年11月25日 星期一
登录注册

文章基本信息

  • 标题:The Power of a Single Qubit: Two-way Quantum/Classical Finite Automata and the Word Problem for Linear Groups
  • 本地全文:下载
  • 作者:Zachary Remscrim
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-50
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The two-way quantum/classical finite automaton (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA, with a single qubit, can recognize, with one-sided bounded-error, the language L e q = a m b m m N in expected polynomial time and the language L pa l = w a b w is a palindrome in expected exponential time.

    We further demonstrate the power of 2QCFA by showing that they can recognize the word problems of a broad class of groups. In particular, we first restrict our attention to 2QCFA that: (1) have a single qubit, (2) recognize their language with one-sided bounded-error, and (3) have transition amplitudes which are algebraic numbers. We show that such 2QCFA can recognize the word problem of any finitely-generated virtually abelian group in expected polynomial time, as well as the word problem of a large class of linear groups in expected exponential time. This latter class includes all groups whose word problem is a context-free language as well as all groups whose word problem is known to be the intersection of finitely many context-free languages. As a corollary, we obtain a direct improvement on the original Ambainis and Watrous result by showing that L e q can be recognized by a 2QCFA with better parameters.

    We also consider those word problems which a 2QCFA can recognize with one-sided unbounded-error, and show that this class includes the word problem of more exotic groups such as the free product of any finite collection of finitely-generated free abelian groups. As a corollary of this result, we demonstrate that a new class of group word problems are co-stochastic languages. Lastly, we exhibit analogous results for 2QCFA with any finite number of qubits or with more general transition amplitudes, as well as results for other classic QFA models.

  • 关键词:finite automata ; quantum ; word problem
国家哲学社会科学文献中心版权所有