标题： 量子一阶逻辑捕获对数时间/空间的量子可计算性 显示英文标题

标题： Quantum First-Order Logics That Capture Logarithmic-Time/Space Quantum Computability

摘要： 我们引入了经典一阶逻辑（FO）的量子类比，并发展了量子一阶逻辑的理论，作为对量子计算中逻辑表达能力的生产性讨论的基础。 这项工作的目的是通过引入具有特殊功能的量子连接词和量化固定维量子态的量子量词，以逻辑方式表达“量子计算”。 我们的方法建立在最近引入的有时间限制的量子函数的递归理论模式定义基础上，这些函数将有限维希尔伯特空间映射到自身。 因此，本文中的量子一阶逻辑（QFO）与基于格论的已知旧的量子逻辑概念有很大不同。 我们证明，通过使用新的“功能性”量子变量，量子一阶逻辑具备表达有界误差量子对数时间可计算性的能力。 相反，额外包含量子传递闭包算子有助于我们表征量子对数空间可计算性。 同样的可计算性可以通过使用不同的“功能性”量子变量来实现。 显示英文摘要

摘要： We introduce a quantum analogue of classical first-order logic (FO) and develop a theory of quantum first-order logic as a basis of the productive discussions on the power of logical expressiveness toward quantum computing. The purpose of this work is to logically express "quantum computation" by introducing specially-featured quantum connectives and quantum quantifiers that quantify fixed-dimensional quantum states. Our approach is founded on the recently introduced recursion-theoretical schematic definitions of time-bounded quantum functions, which map finite-dimensional Hilbert spaces to themselves. The quantum first-order logic (QFO) in this work therefore looks quite different from the well-known old concept of quantum logic based on lattice theory. We demonstrate that quantum first-order logics possess an ability of expressing bounded-error quantum logarithmic-time computability by the use of new "functional" quantum variables. In contrast, an extra inclusion of quantum transitive closure operator helps us characterize quantum logarithmic-space computability. The same computability can be achieved by the use of different "functional" quantum variables.