5、量子信息与计算：从基础概念到计算复杂性

量子信息与计算：从基础概念到计算复杂性

1. 量子计算的起源与基本概念

将计算机视为物理对象，把计算视为物理过程，这一理念具有革命性，由多位科学家提出，其中理查德·费曼（Richard Feynman，1918 - 1988）和大卫·多伊奇（David Deutsch，生于1953年）最为著名。费曼在1996年出版的《费曼计算讲义》中详细介绍了可逆计算理论、量子力学计算机以及计算的量子方面；多伊奇在1985年发表的论文中阐述了量子图灵机和通用量子计算机的基本思想。

传统数字计算机使用比特（我们可以称之为香农比特，因为香农是第一个使用比特来表示信息的人）进行操作，即布尔状态0和1，每个计算步骤后计算机都有一个确定的、可精确测量的状态，所有比特都以0或1的形式存在，但不会同时为两者。而量子计算机作为数字计算机的量子模拟，使用涉及量子态的量子比特（香农比特的量子版本）进行操作。

量子计算机的状态被描述为希尔伯特空间中的基向量。希尔伯特空间以德国数学家大卫·希尔伯特（David Hilbert，1862 - 1943）命名，是一个完备的内积空间。更正式地，我们有如下定义：
定义：一个量子比特是形式为 $\vert \psi \rangle = \alpha \vert 0 \rangle + \beta \vert 1 \rangle$ 的量子态，其中振幅 $\alpha, \beta \in \mathbb{C}$，且 $\vert\vert\alpha\vert\vert^2 + \vert\vert\beta\vert\vert^2 = 1$，$\vert 0 \rangle$ 和 $\vert 1 \rangle$ 是希尔伯特空间的基向量。

在量子计