近日在学习计算理论，顺道去看了些量子计算方面的paper，记录于此。

另推荐几篇很好的相关文章：

一些超计算（超越图灵机）方面的内容：

一、发展历史

1936年，图灵在他的硕士论文《论可计算数及其在判定性问题上的应用》中提出了图灵机模型。1949年，冯诺伊曼基于此模型造出了世界上第一台通用电子计算机，而后计算机行业开始迅速发展。

与此同时，随着量子力学的发展，人们发现一些量子特性也可以被运用在计算机上。经典计算机的操作核心是bit，也就是0/1二进制，而基于量子特性的qubit可以处于0/1之间的量子叠加态，这为计算提供了更多的可能。

1985年，量子计算祖师爷级别的科学家Deutsch仿照图灵机，提出了量子图灵机模型，奠定了量子计算理论的基础。但这个模型本身存在一定问题，不易于分析，因此Deutsch在1989年提出了更底层的量子电路模型。1993年，姚期智老师又证明了每一个量子图灵机都可以用量子电路模拟出来。于是，本世纪以来，量子图灵机逐渐过时，大家提到量子计算时基本默认是量子电路模型，并基于此提出了多种复杂度理论。

二、图灵机

1. 组成结构

A Turing machine is a 7-tuple, \left(Q, \Sigma, \Gamma, \delta, q_0, q_{\text {accept }}, q_{\text {reject }}\right), where Q, \Sigma, \Gamma are all finite sets and

1. Q is the set of states,
2. \Sigma is the input alphabet not containing the blank symbol \sqcup,
3. \Gamma is the tape alphabet, where \sqcup \in \Gamma and \Sigma \subseteq \Gamma,
4. \delta: Q \times \Gamma \longrightarrow Q \times \Gamma \times\{\mathrm{L}, \mathrm{R}\} is the transition function,
5. q_0 \in Q is the start state,
6. q_{\text {accept }} \in Q is the accept state, and
7. q_{\text {reject }} \in Q is the reject state, where q_{\text {reject }} \neq q_{\text {accept }}.

（1）一条无限长的纸带： 图灵机只是一个理想的设备，图灵认为它能模拟人类所能进行的任何计算过程。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。每个方格里存储着所需的一个字符（0 或者 1）。

（2）一个读写头（HEAD）： 该读写头可以在纸带上左右移动，它能读出当前所指格子上的符号，并能改变当前格子上的符号。

（3）一个状态寄存器。 它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。

（4）一套控制规则（我们可以理解为程序）： 它根据当前机器所处的状态以及当前读写头所指格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。

说明：一开始纸带上的字符称作输入，而达到停机状态后，纸带上改写后的字符就是输出。若不能达到停机状态，则这是一个不可计算问题。依据达到停机状态时间的长短，划分时间复杂度类型。

2. 与计算机对比

工作带类似于今天的硬盘，所有的数据都存储于此。读写器则类似于硬盘中的磁头，读写硬盘中的内容。而控制器的功能比较多，不仅包含 CPU 的运算能力，还包括了一定的程序算法。在解决不同的问题时，只需要改变控制器中的算法，即可实现图灵机功能的改变，因此，可以说图灵机是一种“通用型的计算机”。

3. 与人类对比

以考试为例，我们也是从存储器（试卷）上获取问题，然后我们的信息收集器官（眼睛或耳朵）选出有用的信息传递给控制器（大脑），在大脑计算处理之后，再写在答题卡上（此时我们的视觉听觉及手臂构成了读写头）。

三、量子图灵机

1. 组成

• 字符集 \Sigma=\left\{B, b_1, b_2 \ldots\right\} 。其中 B 是代表空字符。和图灵机一样，只要可数，字符集的元素 个数完全不影响。于是我们和经典计算机一样，一般都取0，1，空字符的集合。
• 探针状态 Q=\left\{q_0, q_1, \ldots, q_f\right\} 。其中 q_0 为初始探针状态， q_f 为末态探针状态。
• 内存(纸带)空间。意思为纸带空间是具体的纸带配置(configuration)的集合。一个纸带配置是一个把纸带用字符涂满的方式 (可以用空字符)。我 们还用字母 d 来表示当时QTM的探头(probe)位置。探头位置表示内存纸带上被探头指向并且将改写的格子位置。
• 状态转移函数 \sigma=Q \times M \times Q \times M \times[-1,1]_{\mathbb{Z}} \rightarrow \mathbb{C} 。这个可以理解为给定图灵机状态 \left(q_1, m_1\right) \in Q \times M 和任意另一状态 \left(q_2, m_2\right) \in Q \times M ， \sigma 可以给出一个复数，而这个复数 的共扼平方(模平方)就是从 \left(q_1, m_1\right) 转移到 \left(q_2, m_2\right) 的概率。然后探头位置可以左移或者右移一位。

2. 与图灵机对比

基本上类似，区别在于将纸带上的字符与寄存的状态均改为了叠加态的量子比特。但这也造成了两个问题：

1. 每一步操作对应的酉矩阵U需要保证：仅更改探针位置上量子比特的概率比例、探针位置只能变化一个单位以内。这样对量子操作的酉矩阵U的设计就变得很困难。
2. halt问题。在图灵机中，我们可以设置一个停机状态，达到此状态则计算结束。但量子图灵机一直处于叠加态，不知道什么时候结束。直到量子图灵机过时前，人们都一直在讨论这个问题，并未完全解决。

构造量子图灵机这一模型，我们肯定是希望能找到一些场景，在这些场景下QTM的计算速度要比图灵机更快。但正是由于这些问题，只能证明QTM不会比TM差，但很难找出一个实际场景，说明QTM优于TM。因此，在姚期智老师证明了任何一个QTM都可以被量子电路模拟后，就很少有人再提及这一模型了。

Let M be a quantum Turing machine and n, t be positive integers. There exists a quantum Boolean circuit K of size \operatorname{poly}(n, t) that (n, t)-simulates Q.

四、量子计算复杂度

量子计算的应用场景较多，例如量子通信、密码破译等等，在不同领域，根据需求我们会考虑不同类型的复杂度。

1. Computational complexity

考虑在量子电路中用到的量子门数量。

在一些经典计算任务中，引入量子性可以大幅度提升算法效率，例如用于搜索任务的Grover算法。

2. Communication complexity

在分布式计算中，一般认为通讯的延迟和/或成本很高。一种常用的抽象是假设节点内部的计算没有成本，算法的复杂度用节点之间的通讯量来衡量，节点之间的总通讯量被称为通讯复杂度。这一概念由姚期智老师提出并发扬。

通信复杂度（communication complexity）主要研究这么一类问题： A 持有数据 x ， B 持有数据 y ，他们想要合作计算某个关于 x 和 y 的二元函数值 f(x,y)，两人至少需要传输多少 bit 的数据才能算出 f(x, y) 的值？

参考文献：

1. Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer
2. Quantum circuit complexity
3. An Introduction to Quantum Complexity Theory

本文使用 Zhihu On VSCode 创作并发布