Expressing Power of Elementary Quantum Recursion Schemes for Quantum Logarithmic-Time Computability
Expressing Power of Elementary Quantum Recursion Schemes for Quantum Logarithmic-Time Computability
复制标题
表达量子对数时间可计算性的基本量子递归方案的能力
DOI：
10.1007/978-3-031-15298-6_6
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tomoyuki Yamakami
中科院分区：
文献类型：
--
作者：
Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami
在过去的四十年里，量子计算已经基于量子电路和量子图灵机的两种计算模型进行了研究。为了捕获量子多项式时间的可计算性，Yamakami最近采取了一种新的递归理论方法[J. Symb.逻辑80，pp. 1546-1587，2020]通过示意性定义的方式，其构成了一些初始量子函数和一些构造方案，包括组合、分支和多量子比特量子递归。通过采取类似的步骤，我们研究量子时间的可计算性，并进一步探索为这种量子计算设计的基本方案的表达能力。特别是，我们介绍了量子递归的一种基本形式，称为快速量子递归，这有助于我们捕获量子时间可计算性。
Quantum computing has been studied over the past four decades based on two computational models of quantum circuits and quantum Turing machines. To capture quantum polynomial-time computability, a new recursion-theoretic approach was taken lately by Yamakami [J. Symb. Logic 80, pp. 1546–1587, 2020] by way of schematic definitions, which constitute a few initial quantum functions and a few construction schemes, including composition, branching, and multi-qubit quantum recursion. By taking a similar step, we look into quantum logarithmic-time computability and further explore the expressing power of elementary schemes designed for such quantum computation. In particular, we introduce an elementary form of the quantum recursion, called the fast quantum recursion, which helps us capture quantum logarithmic-time computability.