量子图灵机：部分观测与弱良构性条件及新抽象模型

理论计算机科学电子笔记270（1）（2011）99-111www.elsevier.com/locate/entcs量子图灵机的部分观测和一个弱良构性条件Simon Perdrix西蒙·佩德瑞克斯1，2法国格勒诺布尔大学法国国家科学研究中心摘要量子图灵机（QTM）是由Deutsch提出的量子计算的抽象模型。 QTM的转移函数是线性的，并且必须是幺正的才能成为良构的QTM。这个良构条件确保了机器的演化不会违反量子力学的假设。然而，我们在本文中声称 ， 良 构 性 条 件 太 强 ， 我 们 引 入 了 一 个 较 弱 的 条 件 ， 导 致 一 类 更 大 的 图 灵 机 称 为 可 观 测 量 子 图 灵 机（OQTM）。我们证明了这种OQTM的演化并不违反量子力学的假设，同时为量子计算提供了一个更一般的抽象模型。这种新颖的抽象模型统一了经典计算和量子计算，因为每个良构的QTM和每个确定性的TM都是OQTM，而确定性的TM必须是可逆的才能成为良构的QTM。在本文中，我们介绍了基本的OQTM像一个良好的观察引理和完成引理。引入这种允许经典和量子计算的抽象机器的动机是量子计算的模型，比如单向模型。更一般地说，OQTM旨在成为量子计算实用范式的抽象框架：量子数据，经典控制。此外，该模型允许对需要经典交互的问题进行正式和严格的处理，例如QTM的停止最后，它打开了一个通用的QTM建设的新视角关键词：量子图灵机，经典控制，停止量子比特。1引言如何制作量子版的确定性图灵机（DTM）？概率图灵机（PTM）是通过允许机器配置上的概率分布从DTM获得的，而前量子图灵机（pQTM）是通过允许机器配置的叠加从DTM定义的。此外，PTM必须满足良构性条件，确保概率为正数且总和为1。同样，A[1]我在牛津大学计算实验室工作时，这项工作已经部分实现，在量子信息和计算（QICS）中使用EC-FP 6-STREP2电子邮件：Simon. imag.fr1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.01.009100S. Perdrix/Electronic Notes in Theoretical Computer Science 270（1）（2011）99Σ可逆图灵机（RTM）[1]是DTM的一个实例，它满足确保其可逆性的良构条件类似地，Deutsch [5]介绍了量子图灵机（QTM）作为满足良构性条件的一类pQTM。这个良构条件确保QTM不违反量子力学的假设，也意味着可逆性。因此，QTM是RTM的量子版本。然而，最近量子计算模型的发展，如单向量子计算机[4，16]，指出不可逆量子计算也是有用的。因此，避免不可逆性的良构性条件似乎限制太多。本文的主要贡献在于引入了一个较弱的良形性条件来捕获量子力学的公设，独立于可逆性问题。这个较弱的条件导致了一类量子版本的DTM，称为可观测量子图灵机（OQTM）。在简要介绍了量子计算基础之后（完整介绍见[10]），我们在第4节中介绍了这样一种限制较少的量子图灵机，可观测量子图灵机（OQTM），其中可以在每次跃迁时进行直观的部分观测。给出了OQTM的基本原理，包括一个良好的观测条件，它是量子图灵机良构性条件的推广。介绍了编程OQTM的基本工具：良好观察引理（即转移函数必须满足的条件，以使机器良好观察）;和完成引理（如果部分转移函数满足良好观察引理的条件，它可以扩展到良好观察的pQTM的总转移函数）。在第5.1节中，我们证明了任何QTM都可以被模拟通过OQTM，其中在每个转换处执行部分测量，以便知道计算是否停止。在第5.2节中，我们证明了任何QTM和任何确定性图灵机都是可观测的。因此，OQTM扩展了确定性图灵机的经典模型，包括不可逆机器。此外，良好观测可以被视为允许不可逆计算的较弱良构性条件在第6节中，我们证明了OQTM的计算能力与QTM的计算能力是等价的，因为任何OQTM都可以在二次减速内由QTM模拟2量子计算基础量子计算中信息的基本载体是2能级量子系统（qubit），或者更一般地说是d能级量子系统（qudit）。单个量子点的状态是希尔伯特空间CA的归一化向量，其中A是有限字母表符号的一个标准正交基（o.n.b.）这个希尔伯特空间被描述为：{|τ∈A}。 所以一般情况下|一个单一量子点的A可以写为：ατ|τ，τ∈AS. Perdrix/Electronic Notes in Theoretical Computer Science 270（1）（2011）99101ΣΣΣΣΣΣΣΣ† †然后，|ψ⟩ =5τ∈Aατ<$βτ（其中α<$为复共轭）。左000其中τ∈A|ατ|2 = 1。矢量、内积和外积用Dirac引入的符号表示。向量表示为|两个向量的内积|但是，|ψΣ⟩isdenotedby⟨ϕ|好吧 If|ϕ⟩=τ∈Aατ|τ和|ψ⟩=τ∈Aβτ|τ，手侧式升降机|是一个bra向量，右边是|阿吉是一个ket向量一个bra-向量被定义为对应的ket-向量的伴随：如果|ϕ⟩=τ∈Aατ|你好，你好|为|联系我们τ∈Aαττ|. bra-k et符号也可以用来描述外积：|ϕ⟩⟨ψ|是线性算子，（|ϕ⟩⟨ψ|）|ϵ⟩ = ⟨ψ|ϵ⟩|好吧由两个量子组成的系统的状态|ϕ⟩ ∈ CA and|分别为CB的归一化向量|ϕ⟩ ⊗|<$$> ∈CA<$C B<$>=CA×B，其中re<$是张量积。对于任意的τ∈A，γ∈B，|τ、γ表示|τ⟩ ⊗|是的。CA量子态的概率分布可用密度矩阵ρ∈ D（CA）<$CA×A表示，即迹1的自伴3正半无限4复矩阵.根据量子力学第二公设，孤立系统按照幺正变换6U∈CA×A演化，将状态ρ∈ D（CA）转化为U ρU<$。更一般地说，无论系统是否孤立，状态都按照一个保迹完全正（tpcp）映射F演化，将ρ转化为F（ρ）。根据Kraus表示定理[3]，对于任意的tpcp映射F，存在矩阵集合Mi∈CA×A，满足完备性条件iMiMi=I，使得F（ρ）=iMiρMi.tpcp-映射的一个特殊例子是由投影器集合Pi描述的投影测量。 射影测度将ρ变换为iPiρPi。投射测量产生经典结果i0，概率为pi0（ρ）=Tr（PiρPi） =Tr（Piρ）。7例如，对给定状态的投影|黑猩猩属P0 = |ϕ⟩⟨ϕ|，因此获得与该投影仪相关联的经典结果的概率为|黄菊（|ϕ⟩⟨ϕ|ρ）=Tr（π）|ρ|（掌声）。3量子图灵机为了完整性，给出了确定性图灵机的定义见[13]关于（经典）图灵机的基本原理。定义3.1（确定性图灵机（DTM））确定性图灵机由三元组（ε，Q，δ）定义，其中：ε是具有标识的空白符号#的有限字母表，Q是具有标识的初始状态q0和最终状态qf=q0的有限状态集，δ是确定性转移函数δ，是函数δ：Q×→×Q×{− 1， 0， 1}3M是自伴的（或厄米特的）当且仅当M†=M4M是正半无穷大的，如果M的所有特征值都是非负的。5M的迹（tr（M））是M的对角元素之和6U是酉的当且仅当U<$U=UU<$=I。7，因为Tr（MN）=Tr（NM），并且对于任何投影仪P，P2=P。8.本文假设确定型图灵机的转移函数是全的。102S. Perdrix/Electronic Notes in Theoretical Computer Science 270（1）（2011）99|⟩XXΣDeutsch在[5]中介绍了图灵机的量子版本，伯恩斯坦和Vazirani广泛研究[2]：定义3.2（前量子图灵机（pQTM））前量子图灵机（pQTM）由三元组（，Q，δ）定义，其中：是具有标识的空白符号#的有限字母表，Q是具有标识的状态的有限集合初始状态q0和最终状态qf是一个函数q0和δ，量子跃迁函数，δ：Q×→C ×Q×{−1， 0， 1}（p，τ）›→ <$q∈Q，σ∈ <$，d∈{− 1，0，1}αp，τ，q，σ，d|σ，q，d为方便起见，用δ（p，τ，q，σ，d）表示αp，τ，q，σ，d∈C，即σ，q，d在δ（p，τ）中的振幅。pQTM M的演化由定义在CQ×Z上 的线 性 算子 U M给 出（称为配置的状态空间）：UM=Σδ（p，Tx，q，σ，d）|q，T σ，x + dp，T，x|p，q∈Q，σ∈ N，d∈{−1， 0， 1}，T∈N，x∈Z其中Tσ∈T σ是T，其中位置x上的符号被σ替换。量子图灵机（QTM）是一种形式良好的前量子图灵机：定义3.3（良构条件）pQTM M是良构的当且仅当UM是等距的，即 UM<$UM=I.引理3.4（良构引理[12]）对于给定的pQTMM =（Q，Q，δ），M是良构的当且仅当：（a）<$（τ，p）∈ <$×Q，δ（p，τ）<$δ（p，τ）= 1(b) <$（τ，p），（τJ，pJ）∈<$×Q，其中（p，τ）=（pJ，τJ），δ（p，τ）<$δ（pJ，τJ）= 0(c)<$（τ，p，σ），（τJ，pJ，σJ）∈<$×Q×<$，d∈{0∈，1}，q∈Qδ（p，τ，q，σ，d−1）<$δ（pJ，τJ，q，σJ，d）= 0(d) <$（τ，p，σ），（τJ，pJ，σJ）∈<$×Q×<$，δ（p，τ，q，σ，−1）<$δ（pJ，τJ，q，σJ，1）= 0q∈QS. Perdrix/Electronic Notes in Theoretical Computer Science 270（1）（2011）99103X如果δ是部分量子跃迁函数，则称三元组M=（λ，Q，δ）为部分pQTM。如果这样的δ满足良构引理3.4的四个条件，则M称为部分良构pQTM。引理3.5（完备引理[12]）对于每个具有部分量子跃迁δ的部分良构pQTM M，存在具有相同字母表、相同状态集和在δ的域上等于δ的跃迁函数δJ的QTM M j。QTM M根据UM演化：如果M的初始配置为|c∈CQ× N×Z，则经过n次转移后，机器的配置为（UM）n|c.构形也可以用密度矩阵ρ∈ D（CQ×Z）表示（见[7]）。密度矩阵可以表示量子态的概率分布演化算子则是保迹完全正（tpcp）映射：FM：D（CQ×× Z）→ D（CQ××Z）ρ›→UMρUM<$4可观测量子图灵机由于QTM具有单一演化，因此在机器停止之前不能应用测量。事实证明，在进化过程中观察机器可能是有用的，例如知道机器是否已经停止。这个问题已经解决了[11]，证明可以在每次转换后添加一个可以测量的停止量子位，并且当机器停止时从0切换到1。我们引入了一个正式的和更一般的框架来描述机器在每次转换之前和之后的部分观察定义4.1（观测到的前量子图灵机）对于给定的pQTMM=（λ，Q，δ），和λ×Q的一个划分K={Kλ，λ∈ Λ}，[M]K是观测到的前量子图灵机。[M]K的演化由F[M]K给出：F[M]K ：D（CQ×× Z）→ D（CQ××Z）ρ<$→λ，μ∈Λχλ，μρχ<$λ，μ其中χλ，μ是线性算子，定义如下：χλ，μ=λδ（p，Tx，q，σ，d）|q，T σ，x + dp，T，x|（τ，p）∈K λ，（σ，q）∈K μ，d∈{− 1，0，1}，x∈Z，T∈ Z，s.t.T x= τ注4.2注意χλ，μ=PμUMPλ，其中Pν是定义为任意ν∈Λ如下：Pν=π|p，T，x=p，T，x|p∈Q，x∈Z，T∈Z. （Tx，p）∈Kν104S. Perdrix/Electronic Notes in Theoretical Computer Science 270（1）（2011）99Σ因此，[M]K的演化可以分解为内部态和头部根据可观测量OΛ=λ∈ΛλPλ所指出的单元的投影测量，然后是与M的演化相同的线性跃迁UM因此，在每次转变之前和之后，测量机器的特性。测量的性质由分区{Kλ，λ∈ Λ}描述，由以下组成：|Λ|区域，内部状态和由头部指出的单元的符号。测量包括将机器的内部状态和由头部指出的状态投影到这些区域之一中。这种测量产生了经典结果λ∈ Λ，它是一种部分观测，因为在测量之后，构形可以是K λ区域元素的叠加。从物理的观点来看，[M]K是可实现的，如果F[M]K是一个保迹完全正（tpcp）映射。定义4.3（良好观测条件）一个观测到的pQTM[M]K是良好观测的，当且仅当F[M]K是一个tpcp映射，即：λε，μ∈Λχχλ，μχλ，μ=I这样一个可观测的前量子图灵机是一个可观测的量子图灵机：定义4.4（可观测量子图灵机）可观测量子图灵机（OQTM）是一个可观测的pQTM[M]K。良构引理和完备引理是QTM程序设计的重要工具我们介绍了OQTM的类似物，即，一个良好观测引理和一个完备引理：引理4.5（良观测引理）对于给定的pQTMM=（λ，Q，δ）和给定的K={Kλ，λ∈Λ} λλ×Q， [M]K是良观测的当且仅当：（a）<$（τ，p）∈ <$×Q，δ（p，τ）<$δ（p，τ）= 1(b) <$λ∈Λ，<$（τ，p），（τJ，pJ）∈Kλ，其中（p，τ）/=（pJ，τJ），δ（p，τ）<$δ（pJ，τJ）= 0(c)<$λ∈Λ，<$（τ，p，σ），（τJ，pJ，σJ）∈Kλ×<$，d∈{0∈，1}，q∈Qδ（p，τ，q，σ，d−1）<$δ（pJ，τJ，q，σJ，d）= 0S. Perdrix/Electronic Notes in Theoretical Computer Science 270（1）（2011）99105Σλ，μ∈Λλ，μλ，μΣΣλ∈ΛMμ∈ΛMΣ∈(d) <$λ∈Λ，<$（τ，p，σ），（τJ，pJ，σJ）∈Kλ×<$，δ（p，τ，q，σ，−1）<$δ（pJ，τJ，q，σJ，1）= 0q∈Q证据根据备注4.2，χλ，μ= PμUMPλsoχ<$χ=PλU<$U Pλ，因为Pμ= I。因此，[M] K是良好观测的，当且仅当对于ny基配置，|p，T，x，|pJ， TJ，xj，λΛp，T，x|PλUM<$UMPλ|pJ， TJ，xJ=T，x|pJ，TJ，xJ∈. 由于Pλ|p，T，x = |p，T，x∈如果（Tx，p）∈Kλ且0，否则，当（Tx，p）和d（Txj′，PJ）不位 于 同一块Kλ内时，观测方程成立.如果它们在同一区块中，则井观测条件为|UM†UM|pJ， TJ，xj=p，T，x|pJ， TJ，xJ∈. 因此，[M]K对每个λ ∈ Λ都 是 可 观 测 的 ， UM对C{（p，T，x），s.t. （Tx，p）∈Kλ}是等距的. 为对于UM的这些限制中的每一个，可以应用良构性条件（参见引理3.4），得到方程（a）到（d）。H与QTM的良构引理（见引理3.4）相比，良观测引理指出良观测是比良构条件更弱的条件：方程（a）必须由良构和良观测机器满足，而方程（b）到（d）对于良观测来说是更弱的，因为只有同一块中的元素对必须满足方程。对于一个给定的部分pQTMM =（Q，n，δ）和一个给定的n×Q的划分K，如果δ满足良好观测引理4.5的四个条件，则[M]K称为部分良好观测的pQTM。引理4.6（完备引理）对于每个具有部分量子跃迁δ的部分良好观测的pQTM [M]K，存在具有相同字母表、相同状态集和等于δ的跃迁函数δJ的OQTM [ M j ] K。证据 证明包括在分区K的每个块上应用QTM完备引理。 若K={Kλ，λ∈Λ}，则Mλ=（λ，Q，δλ），其中δλ是δ对Kλ的限制. 根据引理3.4和4.5，Mλ是一个良构的部分QTM，因此Mλ可以扩张为一个良构的QTMMλJ. Letδ（k）是Mk j的转移函数。最后，设δJ满足：对任意y（p，τ），若（τ，p）∈ K λ，则δJ（p，τ）= δ（λ）（p，τ）.因为每个δ（k）满足引理3.4的条件，所以δJ满足引理4.5的条件。此外，δJ扩展了δ。H106S. Perdrix/Electronic Notes in Theoretical Computer Science 270（1）（2011）99x∈Z|qf，T，xqf，T，x|），M和[M] H的计算能力是等价的：5可观测量子图灵机5.1量子图灵机可观测量子图灵机的形式主义扩展了量子图灵机的形式主义：任何QTM都是OQTM，其中执行了非信息部分测量。事实上：命题5.1对任何pQTMM=（M，Q，δ），M是良构的当且仅当[M]{M×Q}是弱线性的。 此外，M和[M]{M×Q}具有相同的演化：F[M]{M×Q}=FM.更一般地，对于任何QTMM及其内部状态的任何分区K，[M]K是很好观察的。然而，机器的进化依赖于分区K，因此机器识别的语言和执行时间依赖于分区K。命题5.1指出，如果K由唯一块组成，则QTMM和OQTM [M]K的演化是相同的。引理5.2给出了K是二分划的另一个例子。 在该示例中，对于给定的QTMM，M和[M]K不具有相同的演化，然而在该特定示例中，M和[M]K的计算能力是相同的。量子图灵机的停止是观察概念缺乏连贯整合的症状QTM的单一演化意味着被视为物理系统的机器不与其环境相互作用。因此，如果不进行测量，就无法知道机器是否停止。此外，如果测量结果显示计算实际上没有完成，则必须重新初始化机器。为了解决这个问题，一个特设机制，包括在机器上添加一个停止量子位。这个量子位可以在任何时候测量，以便知道计算是否停止。这样的机器不再是QTM，因为它的进化不是单一的，但是如果满足某些停止条件，那么ad hoc机器的计算能力就相当于相应的QTM。可观测量子图灵机模型的目标之一是用一种连贯的形式主义来描述这种机制（因为观测可以用这种形式主义来表示），然后给出对量子过程一般停止的更深入的理解因此，在Ozawa [11]关于QTM停止的工作之后，我们证明了任何满足停止条件的QTMM具有与[M]K相同的计算能力，其中在每次转换时，测量机器的内部状态，以便知道机器何时停止。引理5.2设M=（Q，δ，δ）是QTM，则 [M]H是可观测的，其中H={λ ×（Q\{qf}），λ × {qf}}. 此 外 ，如果M满足停止条件，（即，T∈|c = PUMPUt|c，其中P =MMS. Perdrix/Electronic Notes in Theoretical Computer Science 270（1）（2011）99107联系我们ΣMy-d[M]Hn∈N，nρ∈ D（CQ× n×Z），nT∈n，pha lt，T（Fn（ρ））=pha lt，T.Fn（ρ）其中，p停止，T（p）表示机器停止的概率（即，内部状态为qf），如果机器的配置为ρ，则卷尺测量的结果为T。证据 证明是基于[11]中H5.2经典图灵机在本节中，我们证明了[M]K对于某些K可能是很好观察到的，即使pQTMM不是良构的。因此，良好观测条件比良构条件弱。在命题5.3中，通过考虑确定性图灵机，指出了良构机和良观测机之间的分离我们可以通过以下方式描述确定性图灵机M=（Q，θ，δ）：前量子图灵机M∈ =（Q，τ，δ∈），其中δ∈（p，τ） =|δ（p，τ）ITIS我们知道M是well-formed的，如果且如果M是可逆的，图灵机然而，我们证明了对于任何确定性图灵机M，OQTM[M]{{c}，c∈N×Q}，其中对内部状态和头部所指的单元进行了总测量，是良好观察的：命题5.3对于DTMM=（Q，θ，δ），[Mθ]{{a}，a∈θ×Q}是一个弱线性方程，当r eM=（Q，，δ）是一个pQTM使得（p，τ）∈Q×，δ（p，τ）=|δ（p，τ）此外，M和[M∈]{{a}，a∈N×Q}具有相同的演化：对任意c∈Q×N×Z，[001pdf 1st-31files][001pdf1st-31files][001pdf1st-31files]|cc|）=的|M（c）|概率图灵机也是OQTM的特殊实例 概率图灵机是一个三元组M =（Q，τ，δ），其中δ：Q× τ ×Q× τ×{− 1，0，1} →R，使得对于任何（p，τ）∈Q × τ，q∈Q，σ∈ τ，d∈{−1，0，1}δ（p，τ，q，σ，d）= 1。配置是由赋值函数ν描述的概率分布：Q×Z→R+。PTMM的演化算子FM是这样的，对于任何配置ν，FM（v）=（q，T，y）›→（p，τ）∈Q× ψ，d∈{−1， 0， 1}δ（p，τ，q，Ty−d，d）ν（p，Tτ，y−d）命题5.4对于任何概率图灵机M=（θ，Q，δ），[MJ]{{a}，a∈N×Q×{−1，0，1}}是我们已知的，并且具有与M相同的演化，其中[9]注意，一个OQTM[M]K的配置是一个密度矩阵，其中作为一个概率图灵机的配置，M′是一个概率分布，可以表示为赋值函数ν：Q×N×Z→R+。作为一个互补序列，我们认为[M]K和M′的演化是相同的如果Φ<$F[M]K<$ <$F =FM'，其中<$（ν）=c∈Q×Zν（c）|cc|且Φ（ρ）= c<$→c|ρ|c.108S. Perdrix/Electronic Notes in Theoretical Computer Science 270（1）（2011）99. √›→MJ=（，Q×{−1， 0， 1}，δJ）是pQTM，δJ=（p，τ，q，（σ，e），d）δ（p，τ，q，σ，d）如果e=d0否则证据 为了满足良好观测引理的条件（c）和（d），头部移动的副本被添加到机器的内部状态，例如MJ的内部态的总测量避免了任何叠加头部的位置，使可观察的量子图灵机成为没有叠加的概率机器。H因此，观测量子图灵机的模型不仅是演化过程中部分性质观测的形式化，而且是一个统一的模型，因为量子图灵机和确定性图灵机都是可观测的量子图灵机。在下一节中，研究了可观测量子图灵机6可观测量子图灵机在本节中，我们主要展示了任何可观测的量子图灵机都可以在量子图灵机的多项式减速内进行模拟换句话说，即使可观测量子图灵机的模型比量子图灵机的模型更定理6.1对于任意的OQTM [M]K，存在一个 QTMMJ，[M] K在二次减速内。本节的其余部分致力于证明这个定理。为了模拟OQTM[M]Katwo-teQTMM采用了多带量子图灵Ma chines已经在[17]中引入。M的磁带之一用于模拟M的磁带，而第二个磁带是历史，其中存储了根据当前内部状态的K的在计算结束时，测量这个辅助带，模拟可观测的量子图灵机。首先，我们定义了一个这样的双带量子图灵机，并证明了这个机器的良构性，然后我们证明了原来的可观测量子图灵机的模拟与线性减速。最后，这个双磁带量子图灵机可以用一个单磁带量子图灵机在二次减速内模拟对于给定的pQTMM =（Q，λ，δ）和λ×Q的一个划分K ={Kλ，λ∈ Λ}，设M_n =（Q，n×Λ2_n{#}，δ_n）是一个二阶量子图灵机。阿尔法bet第一个磁带的字母是，第二个磁带的字母是Λ2<${ #}。过渡S. Perdrix/Electronic Notes in Theoretical Computer Science 270（1）（2011）99109˜U|p，T，x，w，n<$=<$δ<$（p，Tx，#，q，σ，d，（λ，μ），1）|q，Tσ， x+d，w（λ，μ）， n+1MXMMw∈（Λ）MnMMMMMμ∈Λ，（σ，q）∈Kμ，d∈{−1， 0， 1}w∈（Λ2）n+1M的函数δθ其中，Q是Q，Q是Q，Q是Q。δ（p，τ，#）=δ（p，τ，q，σ，d）|q，σ，d，（[τ，p]，μ），1μμ∈Λ，（σ，q）∈Kμ，d∈{−1， 0， 1}其中[τ，p]∈ Λ使得（τ，p）∈K[τ，p]。请注意，第二个头总是向右移动，显示必要的空白符号。这就是为什么过渡函数是部分定义的。人能证明δe表示统一性、正交性和独立性的良好形成条件对于1-带QTM的良构引理参见[2]中的定理5.2.2，对于多带QTM参见 [17因此，根据[ 17 ]中的完备引理--引理2，可以推广到使得相应的pQTM是well-formed的.关于我们（Λ2）n−1，关于M是这样的，对于任何p∈Q，x∈Z，n∈N<$，T∈N<$，w∈M因此，在本发明中，Xq∈Q，σ∈ λ，μ∈Λ，d∈{−1， 0， 1}U|p，T，x，w，n<$=<$δ（p，Tx，q，σ，d）|q，T σ，x + d，w（[τ，p]，μ），n +1用二阶量子图灵机M_n对M_n的模拟如下：对M_n的任意初始构形ρ ∈ D（C_Q×Z），M_n的初始构形为ρ ∈ D（C_Q × Z）|#你好#| ⊗ |0⟩⟨0|.这意味着第一个磁带的内部状态和状态与M相同，而第二个磁带是空的，第二个磁带的头指向索引为0的单元在n次转换之后，的M_n =U_n（ρ_n|#你好#| ⊗|0⟩⟨0|）U？n. 就在这时，第二个脑袋从索引为n的单元，并且第二磁带的所有单元都具有空符号，除了0和n-1之间的单元然后，第二带的这些非空白单元格被测量，导致配置为|U n（ρ）|#你好#|⊗ |0⟩⟨0|）U<$n|w。我们通过n的归纳法证明，这个结果的构形等于F[M]K（ρ）|⊗ |n n|.|.为了初始化归纳，请注意在n= 0转换后该属性为真。对于任何n >0，在n+1次跃迁和第二个磁带的测量之后，M的配置为：ρJ= ρw|U n+1（ρ |#你好#|⊗ |0⟩⟨0|）U +1|w= w| λ（λ，μ）|n+1Un+1（ρ|#你好#|⊗ |0⟩⟨0|）U+1|w|（λ，μ）n+1其中，<$（λ，μ）|n表示<$（λ，μ）|施加在第二带上由n索引的单元上。由于第二磁头总是向右移动，所以转变数n+1不作用于第二磁带的索引在0和λ，μ∈Λ，w∈（Λ2）n110S. Perdrix/Electronic Notes in Theoretical Computer Science 270（1）（2011）99n-1之间的单元，并且因此换向S. Perdrix/Electronic Notes in Theoretical Computer Science 270（1）（2011）99111M∈XΣΣ=X'xΣρJ= （λ，μ）|nUw|Un（ρ）|#你好#|⊗ |0⟩⟨0|）U+1|wU†|（λ，μ）n[M]KM[M]KMX'X任何作用于这些细胞的操作：MMλ，μ∈Λ，w∈（Λ2）n通过归纳，ρJ=π（λ，μ）|nU（Fnλ，μ∈ΛMM（ρ）|#你好#| ⊗ |nn|）U†|（λ，μ）n对任意p，pJ∈Q，任意T，TJ∈Q，任意x，xJ∈Z，（λ，μ）|nUM|p，T，x，#，n表示p′， T′，x，#，n|U|（λ，μ）nλ，μ Λλ（λ，μ）|n δ（p，Tx，q，σ，d）δ†（p′，Tx″，q′，σ′，d′）|q，Tσ， x+d，（[Tx，p]，μ0）， n+1λ，μ∈Λμ0，μ′0∈Λ，（σ，q）∈Kμ0，（σ′，q′）∈Kμ′0，d，d′∈{−1，0，1}<$q′， T′σ′，x′+d′，（[T′′，p′]，μ′0）， n+1||（λ，μ）n=10000|[Tx，p][Tx′'，p′]|λδ（p，Tx，q，σ，d）δ†（p′，Tx′'，q′，σ′，d′）|q，Tσ， x+d，#，n+1λ，μ∈Λ（σ，q）∈Kμ，d，d′∈{−1， 0， 1}q′，T ′σ′，x′+ d′，#，n +1|=χλ，μ|p，T，x=p′， T′，x′|χ†λ，μ|#你好#|⊗|n+1n+1|λ，μ∈Λ[001 pdf 1st-31files]=F[M]K（|p，T，xpJ，T J，xJ|）|#你好#|⊗ |n +1n +1|因此，在本发明中，ThusMρJ= F n+1（ρ）<$|#你好#|⊗ |n +1n +1|在线性减速范围内模拟M因为任何双磁带量子图灵机可以通过二次减速内的单磁带QTM来模拟[17]，M可以通过二次减速内的单磁带QTM来模拟Q7结论和展望本文介绍了可观测量子图灵机（OQTM）作为量子图灵机（QTM）的推广，允许在计算过程中部分观察机器。 OQTM提供了一个形式化的模型来处理需要对机器进行部分观测的应用程序，例如使用观测来了解计算是否停止的停机问题。OQTM是图灵机的一个统一模型，因为任何QTM和任何确定性TM都是OQTM的特殊实例，而众所周知，不可逆确定性TM不能表示为QTM的形式化。但是，OQTM的计算能力与QTM的能力相当。因此，良好观察条件（由OQTM验证的条件）比良构条件（由QTM验证的条件）弱，并且是满足图灵机成为有效量子设备的必要和充分条件的良好候选者由于观测是在OQTM中形式化的112S. Perdrix/Electronic Notes in Theoretical Computer Science 270（1）（2011）99一个观点是研究OQTM与基于测量的量子计算的最新模型（基于传送的模型[9，14]，单向模型[4，16]）和经典控制的量子图灵机的形式框架之间的联系[15]。事实上，OQTM的结构是从范例量子数据，经典控制的启发：量子数据存储在机器的磁带上，而控制，由于内部状态的部分观察和细胞指出的细胞，是混合的。一个观点是描述一个有效的量子器件所需的量子控制量：任何OQTM [M]K都可以用一个OQTM [MJ]K′有效地模拟的最小k是多少，其中KJ的所有块的大小都小于k？另一个悬而未决的问题是存在一个普遍的OQTM。最近在寻求通用QTM [6，8]方面的发展指出，经典控制的存在可能有助于通用机器的设计引用[1] C. H. 计 算 的 逻辑可逆性。 和Dev.，17：6 525，1973.[2] E. Bernstein和U. 瓦齐拉尼 量子复杂性理论 SIAM J. Comput. ，26：1411[3] M. D.崔复矩阵上的完全正线性映射。Linear Algebra and Applications，1975.[4] V. Danos，E. Kashe fi，P. Panangelo and S. 佩德里克斯扩展测量演算。篇章Semantic Techniques in Quantum Computation，Cambridge University Press，2010.[5] D. 德语量子理论，丘奇-图灵原理和通用量子计算机。程序R长索克A，400：97 -117，1985.[6] W. 去你的，J。Heidema，G. Jones和P. H. 波特吉特。通用计算机的统一性和可编程性。理论计算机科学卷。403，第121-129页，2008。[7] S. Iriyama，M.奥希亚，我。沃洛维奇 广义量子图灵机及其在量子力学中的应用 SAT混沌算法信息理论及其应用研讨会论文集，第779-781页，2006年[8] M. 穆勒 强单变量图灵机和Kolmogor复杂度的变化。IEEE Transactions on Information Theory，54（2），2008.[9] M. A.尼尔森仅使用投影测量、量子存储和0态制备的 Phys. Rev. A，308：96 -100，2003.[10] M. A.尼尔森和我。L.创. 量子计算与量子信息剑桥大学出版社，2000年。[11] M.小泽停止量子图灵机。在Unconventional Models of Computation UMC，LNCS 2509第58[12] M. Ozawa和H.西村量子图灵机的局部转移函数。理论信息学与应用，34：379，2000。[13] C. M. 帕帕迪米特里乌计算复杂性，Addison-Wesley出版公司，1994年。[14] S. 珀德里克斯 基于测量的量子计算中的态转移代替隐形传态International Journal of Quantum Information，3（1）：219[15] S. Perdrix和Ph. Jorrand.经典控制的量子计算Math. Struct. in Comp. Science，16：601[16] R. Raussendorf，D. E. Browne和H. J·布里格尔 单向量子计算机-量子计算的非网络模型。Journal ofModern Optics，49：1299，2002.[17] T.山上多带量子图灵机编程的基础。在MFCS史普林格出版社