确定性量子图灵机子类的理论研究与应用

178 浏览量更新于2024-08-29 收藏 491KB PDF 举报

本文探讨了一类名为"Stationary Rotational Quantum Turing Machine" (SR-QTM) 的量子图灵机的特殊性质。SR-QTM 是量子图灵机的一个子集，它具有独特的特征，即在执行计算过程中能确保确定性地停止，并且其磁头位置也是确定性的。这一设计使得SR-QTM 在处理问题时展现出与经典图灵机不同的特性。作者提出了一种新的工具——量子状态转换图（Quantum State Transition Diagram, QSTD），用于精确地描述SR-QTM 的工作流程。通过利用QSTD，研究者构建了一个通用的SR-QTM，它能够执行所有近似简单的变换。这意味着存在至少一个量子图灵机对于SR-QTM 的子类是通用的，能够模拟这个子类中的所有计算任务。文章的核心贡献在于证明了SR-QTM 在有界误差设置下的计算等价性。这意味着尽管SR-QTM 的确定性停机和磁头位置限制了其灵活性，但它在有限错误容限下，其计算能力与标准量子图灵机（Ordinary QTM）并无本质区别。这进一步扩展了我们对量子计算复杂性的理解，特别是关于如何在特定条件下实现量子计算的效率和确定性。总结来说，这篇论文深入研究了量子计算中的一个独特模型，展示了SR-QTM 的理论价值和可能的应用场景。通过构建一个通用的SR-QTM 并证明其与普通量子图灵机的等价性，文章不仅提供了对量子计算的新视角，也为量子算法设计和量子计算机硬件实现提供了潜在的理论基础。此外，对于量子计算机的稳定性研究以及确定性计算在量子世界中的角色，这篇文章都做出了重要的贡献。

Article

SCIENCE CHINA

Physics, Mechanics & Astronomy

May 2013 Vol. 56 No. 5: 941–946

doi: 10.1007/s11433-013-5048-y

 Science China Press and Springer-Verlag Berlin Heidelberg 2013

phys.scichina.com www.springerlink.com

On a class of quantum Turing machine halting deterministically

LIANG Min & YANG Li

State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China

Received May 10, 2012; accepted October 23, 2012; published online April 15, 2013

We consider a subclass of quantum Turing machines (QTM), named stationary rotational quantum Turing machine (SR-QTM),

which halts deterministically and has deterministic tape head position. A quantum state transition diagram (QSTD) is proposed to

describe SR-QTM. With QSTD, we construct a SR-QTM which is universal for all near-trivial transformations. This indicates there

exists a QTM which is universal for the above subclass. Finally we show that SR-QTM is computational equivalent with ordinary

QTM in the bounded error setting. It can be seen that SR-QTMs have deterministic tape head position and halt deterministically,

and thus the halting scheme problem will not exist for this class of QTMs.

quantum Turing machine, quantum circuit, halting scheme, quantum computational complexity

PACS number(s): 03.67.Lx, 03.65.-w, 02.70.-c

Citation: Liang M, Yang L. On a class of quantum Turing machine halting deterministically. Sci China-Phys Mech Astron, 2013, 56: 941–946, doi:

10.1007/s11433-013-5048-y

Deutsch [1] formulated the model of quantum computer

which is referred to as quantum Turing machine (QTM).

Then it was pointed out that there exists a halting scheme

problem when a QTM takes diﬀerent time steps for diﬀerent

branches of computation [2]. In this case, a measurement of

the halt qubit can spoil the computation.

Ozawa [3] showed that the halting scheme is equivalent to

the quantum nondemolition (QND) monitoring of the output

observable. Linden and Popescu [4] argued that the halting

scheme proposed by Ozawa [3] is not consistent with the uni-

tarity of the evolution operator and the halting scheme prob-

lem is still unsolved. Ozawa [5] proposed QTM with well-

behaved halt ﬂags, and arbitrary QTM can be simulated by

this kind of QTM. Moreover, this kind of QTMs obeys a halt-

ing protocol, which requires one measurement of the halt ﬂag

after one time step. He showed that the halting protocol does

not aﬀect the computational result of QTM. This indicates

the probability distribution of the output is not aﬀected by

monitoring the halt ﬂag. Thus the halt scheme problem is

*Corresponding author (email: yangli@iie.ac.cn)

solved though the QTM may halt probabilistically. There are

also some discussions about halting scheme problem [6–8].

This halting scheme problem was avoided by Bernstein

and Vazirani [9] who considered a simpler QTM that has the

same time step for all diﬀerent branches. This kind of QTMs

can halt deterministically and the universal QTM was con-

structed in this sense. In quantum computing, this kind of

QTMs is usually the central model of the research in recent

times. Does there exist more simpler QTM? In this paper, we

propose a simpler class of QTMs (called SR-QTM), which

halt deterministically and have deterministic tape head posi-

tion.

Miyadera and Ohya [10] showed it is not possible to ef-

ﬁciently distinguish between those QTMs which halt deter-

ministically and those which halts probabilistically. They

suggested it is natural for QTM to halt probabilistically and it

is meaningless to deﬁne non-probabilistically halting QTM.

However, their proof necessarily indicates there does not ex-

ist a universal algorithm to decide whether arbitrary QTM of

the whole QTMs has the same time step of diﬀerent branches,

thus it does not exclude the possibility that there exists a uni-

下载后可阅读完整内容，剩余5页未读，立即下载

weixin_38677806

粉丝: 5
资源: 938

确定性量子图灵机子类的理论研究与应用

BURAI 1.2 – a GUI for Quantum Espresso

The Principles of Quantum Mechanics_4th_Dirac

A class of algebraic quantum hypergroups

On the Existence of Quantum Signature for Quantum Messages

Turing Machine Simulator

On the obfuscatability of quantum point functions

Research on the model of quantum satellite communications based on the distribution of entangled three-photon pairs and simulation

quantum_machine_learning

Quantum-Machine-Learning-Projects

Construction of a quantum repeater based on quantum-dot in an optical microcavity system

最新资源