How does adiabatic quantum computation fit into quantum automata theory?
How does adiabatic quantum computation fit into quantum automata theory?
复制标题
绝热量子计算如何适应量子自动机理论？
DOI：
10.1007/978-3-030-23247-4_22
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Tomoyuki Yamakami
中科院分区：
文献类型：
--
作者：
Henning Fernau;Petra Wolf;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami
量子计算已经成为我们这个时代强大的计算媒介，已经证明了在分解正整数和搜索数据库方面的显着效率比任何当前已知的经典计算算法都要快。量子系统的绝热演化是物理实现量子计算的一种潜在手段。到目前为止，所有的绝热量子系统的研究都是处理多项式时间有界计算，很少有人注意到，例如，绝热量子系统只消耗常数存储空间。这样的量子系统可以以类似于量子有限自动机的形式建模。这篇论文大胆地提出了一个问题，即如何使绝热量子计算适应快速发展的量子自动机理论框架。作为我们对这个突出但深刻的问题的回答，我们首先设计了一个基本平台，以有限的计算资源（大小，能量，光谱间隙等）实现绝热演化量子系统（AEQS）。然后演示如何通过操作合适的量子有限自动机族来构造这样的AEQS。我们进一步探讨了决策问题（以及承诺问题）的基本结构特性，通过适当构造的AEQS快速解决。
Quantum computation has emerged as a powerful computational medium of our time, having demonstrated the remarkable efficiency in factoring a positive integer and searching databases faster than any currently known classical computing algorithm. Adiabatic evolution of quantum systems has been studied as a potential means that physically realizes quantum computation. Up to now, all the research on adiabatic quantum systems has dealt with polynomial time-bounded computation and little attention has been paid to, for instance, adiabatic quantum systems consuming only constant memory space. Such quantum systems can be modeled in a form similar to quantum finite automata. This exposition dares to ask a bold question of how to make adiabatic quantum computation fit into the rapidly progressing framework of quantum automata theory. As our answer to this eminent but profound question, we first lay out a fundamental platform to carry out adiabatic evolutionary quantum systems (AEQSs) with limited computational resources (in size, energy, spectral gap, etc.) and then demonstrate how to construct such AEQSs by operating suitable families of quantum finite automata. We further explore fundamental structural properties of decision problems (as well as promise problems) solved quickly by the appropriately constructed AEQSs.