量子计算了解一下~
本文将在没有量子力学基础基本不涉及量子力学前提下 (例如我太菜了搞不懂 布洛赫球面),仅介绍量子计算需要了解的相关知识,并使用Microsof Q#语言完成比赛Microsoft Q# Coding Contest - Summer 2018 - Warmup .
本文非常入门(我太菜了.jpg),有错误也欢迎大佬指正。
文档入口
Microsoft Q#官方文档(英文版) 。
Microsoft Q# Coding Contest - Summer 2018 - Warmup 比赛 Announcement
Microsoft Q# Coding Contest - Summer 2018 - Warmup 题解 Tutorial
量子计算入门
量子比特(Qubit)
一个传统比特(图灵机模型)可以表示为0 0 0 或者1 1 1 .
一个量子比特可以表示为: α ∣ 0 ⟩ + β ∣ 1 ⟩ , α , β ∈ C , ∣ α ∣ 2 + ∣ β ∣ 2 = 1 \alpha \vert 0 \rangle + \beta \vert 1 \rangle, \alpha, \beta \in \mathbb C, \vert \alpha \vert ^2 + \vert \beta \vert ^2 = 1 α ∣ 0 ⟩ + β ∣ 1 ⟩ , α , β ∈ C , ∣ α ∣ 2 + ∣ β ∣ 2 = 1 . 其中∣ 0 ⟩ \vert 0 \rangle ∣ 0 ⟩ 是一个列向量:
[ 1 0 ] \left[\begin{matrix}1 \\ 0\end{matrix}\right]
[ 1 0 ]
同理∣ 1 ⟩ \vert 1 \rangle ∣ 1 ⟩ 是一个列向量:
[ 0 1 ] \left[\begin{matrix}0 \\ 1\end{matrix}\right]
[ 0 1 ]
也就是说任意一个量子比特可以表示为形如:
[ α β ] \left[\begin{matrix}\alpha \\ \beta\end{matrix}\right]
[ α β ]
这里α \alpha α 和β \beta β 是概率振幅,是一个复平面内的向量,其模长的平方表示概率。
唔…似乎,传统计算机完全可以模拟量子比特啊?
并不是。首先定义量子比特的关联: ∣ ψ ⟩ ⊗ ∣ ϕ ⟩ = ∣ ψ ⟩ ∣ ϕ ⟩ = ∣ ψ ϕ ⟩ \vert \psi \rangle \otimes \vert \phi \rangle = \vert \psi \rangle \vert \phi \rangle = \vert \psi \phi \rangle ∣ ψ ⟩ ⊗ ∣ ϕ ⟩ = ∣ ψ ⟩ ∣ ϕ ⟩ = ∣ ψ ϕ ⟩ , 表示:
[ ψ 0 ψ 1 ] ⊗ [ ϕ 0 ϕ 1 ] = [ ψ 0 ϕ 0 ψ 0 ϕ 1 ψ 1 ϕ 0 ψ 1 ϕ 1 ] \left[\begin{matrix}\psi_0 \\ \psi_1 \\\end{matrix}\right] \otimes \left[\begin{matrix}\phi_0 \\ \phi_1 \\\end{matrix}\right] = \left[\begin{matrix}\psi_0\phi_0 \\ \psi_0\phi_1 \\ \psi_1\phi_0 \\ \psi_1\phi_1 \\\end{matrix}\right]
[ ψ 0 ψ 1 ] ⊗ [ ϕ 0 ϕ 1 ] = ⎣ ⎢ ⎢ ⎡ ψ 0 ϕ 0 ψ 0 ϕ 1 ψ 1 ϕ 0 ψ 1 ϕ 1 ⎦ ⎥ ⎥ ⎤
为了方便定义记号∣ ψ ⟩ ⊗ n = ∣ ψ ψ . . . ψ ⏟ n ⟩ \vert \psi \rangle^{\otimes n} = \vert \underbrace{\psi \psi ... \psi}_n \rangle ∣ ψ ⟩ ⊗ n = ∣ n ψ ψ . . . ψ ⟩ 可以看到这就是一个暴力枚举组合。一个有n n n 位量子比特的组合: ∣ ψ 1 ψ 2 . . . ψ n ⟩ \vert \psi_1 \psi_2 ... \psi_n \rangle ∣ ψ 1 ψ 2 . . . ψ n ⟩ 显然是一个有2 n 2^n 2 n 个元素的列向量。量子计算相较于传统计算的优势一部分就在于,对于:
∣ ψ 1 ψ 2 . . . ψ n ⟩ = ∑ i 1 , i 2 , . . . , i n ∈ { 0 , 1 } C i 1 , i 2 , . . . , i n ∣ i 1 i 2 . . . i n ⟩ \vert \psi_1 \psi_2 ... \psi_n \rangle = \sum_{i_1,i_2,...,i_n \in \lbrace 0,1 \rbrace} C_{i_1,i_2,...,i_n} \vert i_1 i_2 ... i_n \rangle
∣ ψ 1 ψ 2 . . . ψ n ⟩ = i 1 , i 2 , . . . , i n ∈ { 0 , 1 } ∑ C i 1 , i 2 , . . . , i n ∣ i 1 i 2 . . . i n ⟩
做一些特定的"基本操作",复杂度是O ( poly n ) O(\text{poly }n) O ( poly n ) 而不是O ( 2 n ) O(2^n) O ( 2 n ) 。这一特性(以及其他一些特性)是由量子计算机本身底层物理实现决定的,传统计算机无法模拟。
目前仅定义了∣ 0 ⟩ \vert 0 \rangle ∣ 0 ⟩ 和∣ 1 ⟩ \vert 1 \rangle ∣ 1 ⟩ ,如果在指定n n n 位量子比特的条件下,∣ x ⟩ \vert x \rangle ∣ x ⟩ 表示一个只有第x x x 行是1 1 1 其他位置都是0 0 0 的向量。会发现如果将x x x 的二进制分解为x n − 1 x n − 2 . . . x 0 x_{n-1}x_{n-2}...x_0 x n − 1 x n − 2 . . . x 0 ,那么∣ x ⟩ = ∣ x n − 1 ⟩ ∣ x n − 2 ⟩ . . . ∣ x 0 ⟩ \vert x \rangle = \vert x_{n-1} \rangle \vert x_{n-2} \rangle ... \vert x_0 \rangle ∣ x ⟩ = ∣ x n − 1 ⟩ ∣ x n − 2 ⟩ . . . ∣ x 0 ⟩ ,其中每个∣ x i ⟩ \vert x_i \rangle ∣ x i ⟩ 都是1 1 1 位量子比特。
单个量子比特操作
Hadamard Transform(Hadamard Gate):
H = 1 2 [ 1 1 1 − 1 ] H = \frac{1}{\sqrt 2}
\left[\begin{matrix}
1 & 1 \\
1 & -1
\end{matrix}\right]
H = 2 1 [ 1 1 1 − 1 ]
Hadamard Transform作用在∣ 0 ⟩ \vert 0 \rangle ∣ 0 ⟩ 和∣ 1 ⟩ \vert 1 \rangle ∣ 1 ⟩ 的结果会经常用到,不仅要会用矩阵运算,为了以后方便还要记住直接运算的公式,并且为了方便定义了记号∣ + ⟩ \vert + \rangle ∣ + ⟩ 和∣ − ⟩ \vert - \rangle ∣ − ⟩ :
H ∣ 0 ⟩ = 1 2 ( ∣ 0 ⟩ + ∣ 1 ⟩ ) = [ 1 2 1 2 ] = ∣ + ⟩ H ∣ 1 ⟩ = 1 2 ( ∣ 0 ⟩ − ∣ 1 ⟩ ) = [ 1 2 − 1 2 ] = ∣ − ⟩ H \vert 0 \rangle = \frac{1}{\sqrt 2}(\vert 0 \rangle + \vert 1 \rangle) = \left[\begin{matrix}\frac{1}{\sqrt 2} \\ \frac{1}{\sqrt 2} \\\end{matrix}\right] = \vert + \rangle \\
H \vert 1 \rangle = \frac{1}{\sqrt 2}(\vert 0 \rangle - \vert 1 \rangle) = \left[\begin{matrix}\frac{1}{\sqrt 2} \\ -\frac{1}{\sqrt 2} \\\end{matrix}\right] = \vert - \rangle \\
H ∣ 0 ⟩ = 2 1 ( ∣ 0 ⟩ + ∣ 1 ⟩ ) = [ 2 1 2 1 ] = ∣ + ⟩ H ∣ 1 ⟩ = 2 1 ( ∣ 0 ⟩ − ∣ 1 ⟩ ) = [ 2 1 − 2 1 ] = ∣ − ⟩
事实上可以有通式x ∈ { 0 , 1 } x \in \lbrace 0, 1 \rbrace x ∈ { 0 , 1 } :
H ∣ x ⟩ = ∣ 0 ⟩ + ( − 1 ) x ∣ 1 ⟩ 2 H \vert x \rangle = \frac{\vert 0 \rangle + (-1)^x \vert 1 \rangle}{\sqrt 2}
H ∣ x ⟩ = 2 ∣ 0 ⟩ + ( − 1 ) x ∣ 1 ⟩
这不是废话么…真的是废话么?
这里稍微提一下: ∣ − ⟩ \vert - \rangle ∣ − ⟩ 是什么啊?如果说∣ + ⟩ \vert + \rangle ∣ + ⟩ 可以理解为∣ 0 ⟩ \vert 0 \rangle ∣ 0 ⟩ 和∣ 1 ⟩ \vert 1 \rangle ∣ 1 ⟩ 的叠加,那么∣ − ⟩ \vert - \rangle ∣ − ⟩ 和∣ + ⟩ \vert + \rangle ∣ + ⟩ 区别是什么?
我也很疑惑,不过看到一个图标是一个红色的小视频播放器的某外国网站上的 视频里将这个∣ − ⟩ \vert - \rangle ∣ − ⟩ 称作Negative Uncertainty。似乎有那么点意思: ∣ + ⟩ \vert + \rangle ∣ + ⟩ 大致是2种可能叠加,而∣ − ⟩ \vert - \rangle ∣ − ⟩ 更有一点容斥的味道。
Pauli-X Gate,留意这个操作可以反转一个量子比特:
X = [ 0 1 1 0 ] X ∣ 0 ⟩ = ∣ 1 ⟩ X ∣ 1 ⟩ = ∣ 0 ⟩ X =
\left[\begin{matrix}
0 & 1 \\
1 & 0 \\
\end{matrix}\right] \\
X \vert 0 \rangle = \vert 1 \rangle \\
X \vert 1 \rangle = \vert 0 \rangle \\
X = [ 0 1 1 0 ] X ∣ 0 ⟩ = ∣ 1 ⟩ X ∣ 1 ⟩ = ∣ 0 ⟩
Pauli-Y Gate:
Y = [ 0 − i i 0 ] Y ∣ 0 ⟩ = i ∣ 1 ⟩ Y ∣ 1 ⟩ = − i ∣ 0 ⟩ Y =
\left[\begin{matrix}
0 & -i \\
i & 0 \\
\end{matrix}\right] \\
Y \vert 0 \rangle = i \vert 1 \rangle \\
Y \vert 1 \rangle = -i\vert 0 \rangle \\
Y = [ 0 i − i 0 ] Y ∣ 0 ⟩ = i ∣ 1 ⟩ Y ∣ 1 ⟩ = − i ∣ 0 ⟩
Pauli-Z Gate:
Z = [ 1 0 0 − 1 ] Z ∣ 0 ⟩ = ∣ 0 ⟩ Z ∣ 1 ⟩ = − ∣ 1 ⟩ Z =
\left[\begin{matrix}
1 & 0 \\
0 & -1 \\
\end{matrix}\right] \\
Z \vert 0 \rangle = \vert 0 \rangle \\
Z \vert 1 \rangle = -\vert 1 \rangle \\
Z = [ 1 0 0 − 1 ] Z ∣ 0 ⟩ = ∣ 0 ⟩ Z ∣ 1 ⟩ = − ∣ 1 ⟩
多个量子比特操作
定义Bell States:
∣ B 0 ⟩ = ∣ ϕ + ⟩ = 1 2 ( ∣ 00 ⟩ + ∣ 11 ⟩ ) ∣ B 1 ⟩ = ∣ ϕ − ⟩ = 1 2 ( ∣ 00 ⟩ − ∣ 11 ⟩ ) ∣ B 2 ⟩ = ∣ ψ + ⟩ = 1 2 ( ∣ 01 ⟩ + ∣ 10 ⟩ ) ∣ B 3 ⟩ = ∣ ψ − ⟩ = 1 2 ( ∣ 01 ⟩ − ∣ 10 ⟩ ) \vert B_0 \rangle = \vert \phi^+ \rangle = \frac{1}{\sqrt 2}(\vert 00 \rangle + \vert 11 \rangle) \\
\vert B_1 \rangle = \vert \phi^- \rangle = \frac{1}{\sqrt 2}(\vert 00 \rangle - \vert 11 \rangle) \\
\vert B_2 \rangle = \vert \psi^+ \rangle = \frac{1}{\sqrt 2}(\vert 01 \rangle + \vert 10 \rangle) \\
\vert B_3 \rangle = \vert \psi^- \rangle = \frac{1}{\sqrt 2}(\vert 01 \rangle - \vert 10 \rangle) \\
∣ B 0 ⟩ = ∣ ϕ + ⟩ = 2 1 ( ∣ 0 0 ⟩ + ∣ 1 1 ⟩ ) ∣ B 1 ⟩ = ∣ ϕ − ⟩ = 2 1 ( ∣ 0 0 ⟩ − ∣ 1 1 ⟩ ) ∣ B 2 ⟩ = ∣ ψ + ⟩ = 2 1 ( ∣ 0 1 ⟩ + ∣ 1 0 ⟩ ) ∣ B 3 ⟩ = ∣ ψ − ⟩ = 2 1 ( ∣ 0 1 ⟩ − ∣ 1 0 ⟩ )
n n n 个量子比特的Hadamard Transform:
H 0 = 1 H n = [ H n − 1 H n − 1 H n − 1 − H n − 1 ] = H ⊗ n H_0 = 1 \\
H_n =
\left[\begin{matrix}
H_{n-1} & H_{n-1} \\
H_{n-1} & -H_{n-1} \\
\end{matrix}\right] = H^{\otimes n} \\
H 0 = 1 H n = [ H n − 1 H n − 1 H n − 1 − H n − 1 ] = H ⊗ n
多个量子比特的Hadamard Transform是一个非常有意思的操作。对于单个量子比特的Hadamard Transform,∣ 0 ⟩ \vert 0 \rangle ∣ 0 ⟩ 在经过操作后,有一半的概率是0 0 0 ,一半的概率是1 1 1 。从之前的Bell States中已经可以看出,n n n 位量子比特的2 n 2^n 2 n 种状态是可以叠加在一起的,那么对n n n 个量子比特位分别进行Hadamard Transform以后,将整个n n n 位看做一个整体的话,其内部就包含了所有2 n 2^n 2 n 种可能,并且等概率出现,数学化地说:
∣ + ⟩ ⊗ n = 1 2 n [ 1 1 . . . 1 ] = 1 2 n ∑ x = 0 2 n − 1 ∣ x ⟩ \vert + \rangle^{\otimes n} = \frac{1}{\sqrt{2^n}}\left[\begin{matrix}1 \\ 1 \\ ... \\ 1\end{matrix}\right] = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\vert x \rangle
∣ + ⟩ ⊗ n = 2 n 1 ⎣ ⎢ ⎢ ⎡ 1 1 . . . 1 ⎦ ⎥ ⎥ ⎤ = 2 n 1 x = 0 ∑ 2 n − 1 ∣ x ⟩
多个量子比特的Hadamard Transform也有通式:
H ∣ x ⟩ = 1 2 n ∑ z = 0 2 n − 1 ( − 1 ) x z ∣ z ⟩ H \vert x \rangle = \frac{1}{\sqrt{2^n}}\sum_{z=0}^{2^n-1} (-1)^{xz} \vert z \rangle
H ∣ x ⟩ = 2 n 1 z = 0 ∑ 2 n − 1 ( − 1 ) x z ∣ z ⟩
CNOT Gate,其作用是对于一个两位量子比特,当且仅当第一位是1 1 1 的情况下反转后一位:
U C N O T = [ 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 ] U_{CNOT} =
\left[\begin{matrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{matrix}\right] \\
U C N O T = ⎣ ⎢ ⎢ ⎡ 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 ⎦ ⎥ ⎥ ⎤
SWAP Gate,其作用是对于一个两位量子比特,交换两个量子比特:
U S W A P = [ 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 ] U_{SWAP} =
\left[\begin{matrix}
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
\end{matrix}\right] \\
U S W A P = ⎣ ⎢ ⎢ ⎡ 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 ⎦ ⎥ ⎥ ⎤
纠缠(Entanglement)
之前关于量子比特的关联时有: ∣ ψ ⟩ ⊗ ∣ ϕ ⟩ = ∣ ψ ⟩ ∣ ϕ ⟩ = ∣ ψ ϕ ⟩ \vert \psi \rangle \otimes \vert \phi \rangle = \vert \psi \rangle \vert \phi \rangle = \vert \psi \phi \rangle ∣ ψ ⟩ ⊗ ∣ ϕ ⟩ = ∣ ψ ⟩ ∣ ϕ ⟩ = ∣ ψ ϕ ⟩ , 表示:
[ ψ 0 ψ 1 ] ⊗ [ ϕ 0 ϕ 1 ] = [ ψ 0 ϕ 0 ψ 0 ϕ 1 ψ 1 ϕ 0 ψ 1 ϕ 1 ] \left[\begin{matrix}\psi_0 \\ \psi_1 \\\end{matrix}\right] \otimes \left[\begin{matrix}\phi_0 \\ \phi_1 \\\end{matrix}\right] = \left[\begin{matrix}\psi_0\phi_0 \\ \psi_0\phi_1 \\ \psi_1\phi_0 \\ \psi_1\phi_1 \\\end{matrix}\right]
[ ψ 0 ψ 1 ] ⊗ [ ϕ 0 ϕ 1 ] = ⎣ ⎢ ⎢ ⎡ ψ 0 ϕ 0 ψ 0 ϕ 1 ψ 1 ϕ 0 ψ 1 ϕ 1 ⎦ ⎥ ⎥ ⎤
但是存在一些2 n 2^n 2 n 维列向量状态,不能被表示为∣ ψ ⟩ ⊗ ∣ ϕ ⟩ \vert \psi \rangle \otimes \vert \phi \rangle ∣ ψ ⟩ ⊗ ∣ ϕ ⟩ ,这时候就称为这个状态为n n n 个量子比特的纠缠态。例如:
[ 1 2 0 0 1 2 ] \left[\begin{matrix}\frac{1}{\sqrt 2} \\ 0 \\ 0 \\ \frac{1}{\sqrt 2} \\\end{matrix}\right]
⎣ ⎢ ⎢ ⎡ 2 1 0 0 2 1 ⎦ ⎥ ⎥ ⎤
就找不到一组分解∣ ψ ⟩ ⊗ ∣ ϕ ⟩ \vert \psi \rangle \otimes \vert \phi \rangle ∣ ψ ⟩ ⊗ ∣ ϕ ⟩ 。这时候,就可以说∣ ψ ⟩ \vert \psi \rangle ∣ ψ ⟩ 和∣ ϕ ⟩ \vert \phi \rangle ∣ ϕ ⟩ 发生了纠缠(Entanglement),这时候这两个量子比特是不可分割的整体。
因为这篇文章是量子计算入门,所以我发现我后面似乎并没有用到纠缠…
观测(Measurement)
对于一个量子比特,进行一次观测并非像传统图灵机模型那样是一个只读操作,而会改变量子比特的状态 。对其进行一个观测,会导致其有∣ α ∣ 2 \vert \alpha \vert^2 ∣ α ∣ 2 的概率变为∣ 0 ⟩ \vert 0 \rangle ∣ 0 ⟩ ,有∣ β ∣ 2 \vert \beta \vert^2 ∣ β ∣ 2 的概率变为∣ 1 ⟩ \vert 1 \rangle ∣ 1 ⟩ ,即发生了坍缩(Collapse)。
这里有一个扩展的记号: ⟨ φ ∣ \langle \varphi \vert ⟨ φ ∣ 表示一个行向量,且⟨ φ ∣ = ∣ φ ⟩ c o n j \langle \varphi \vert = \vert \varphi \rangle^{conj} ⟨ φ ∣ = ∣ φ ⟩ c o n j ,其中v c o n j v^{conj} v c o n j 表示v v v 的共轭向量(即先转置然后把每个位置的复数变成其原来的共轭)。为了方便定义⟨ φ ∣ ϕ ⟩ = ⟨ φ ∣ × ∣ ϕ ⟩ \langle \varphi \vert \phi \rangle = \langle \varphi \vert \times \vert \phi \rangle ⟨ φ ∣ ϕ ⟩ = ⟨ φ ∣ × ∣ ϕ ⟩ 。那么就有⟨ φ ∣ φ ⟩ = 1 \langle \varphi \vert \varphi \rangle = 1 ⟨ φ ∣ φ ⟩ = 1 。更一般地,不难验证: 如果∣ φ ⟩ \vert \varphi \rangle ∣ φ ⟩ 是∣ ϕ ⟩ \vert \phi \rangle ∣ ϕ ⟩ 的一个基本的子状态,那么∣ ⟨ φ ∣ ϕ ⟩ ∣ 2 = Pr ( ∣ ϕ ⟩ collapse to ∣ φ ⟩ ) \vert \langle \varphi \vert \phi \rangle \vert^2 = \Pr(\vert \phi \rangle \text{ collapse to } \vert \varphi \rangle) ∣ ⟨ φ ∣ ϕ ⟩ ∣ 2 = Pr ( ∣ ϕ ⟩ collapse to ∣ φ ⟩ ) 。
对于多个量子比特的观测则比较奇妙: 对于n n n 位量子比特,如果存在(不纠缠)独立的量子比特位,那么会随机坍缩一个这样的量子比特到特定的位置上。
这个地方我也搞不太懂求大佬指点。
UPD 2020.09.04: 一年以后回来看发现自己当时写了些什么鬼东西。这里的四个位就是代表四个状态∣ 00 ⟩ , ∣ 01 ⟩ , ∣ 10 ⟩ , ∣ 11 ⟩ \vert 00 \rangle, \vert 01 \rangle, \vert 10 \rangle, \vert 11 \rangle ∣ 0 0 ⟩ , ∣ 0 1 ⟩ , ∣ 1 0 ⟩ , ∣ 1 1 ⟩ 的概率振幅。目前四个等概率,那么观测第一位如果看到0 0 0 ,那么剩下的概率只能是∣ 00 ⟩ , ∣ 01 ⟩ \vert 00 \rangle, \vert 01 \rangle ∣ 0 0 ⟩ , ∣ 0 1 ⟩ 各一半而不可能出现∣ 10 ⟩ , ∣ 11 ⟩ \vert 10 \rangle, \vert 11 \rangle ∣ 1 0 ⟩ , ∣ 1 1 ⟩ 。
H ⊗ 2 ( [ 1 0 ] ⊗ [ 1 0 ] ) = 1 2 [ 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ] [ 1 0 0 0 ] = 1 2 [ 1 1 1 1 ] ⇒ { outcome = 0 1 2 [ 1 1 0 0 ] outcome = 1 1 2 [ 0 0 1 1 ] H^{\otimes 2}\left(\left[\begin{array}{l}{1} \\ {0}\end{array}\right] \otimes\left[\begin{array}{l}{1} \\ {0}\end{array}\right]\right)=\frac{1}{2}\left[\begin{array}{cccc}{1} & {1} & {1} & {1} \\ {1} & {-1} & {1} & {-1} \\ {1} & {1} & {-1} & {-1} \\ {1} & {-1} & {-1} & {1}\end{array}\right]\left[\begin{array}{l}{1} \\ {0} \\ {0} \\ {0}\end{array}\right]=\frac{1}{2}\left[\begin{array}{l}{1} \\ {1} \\ {1} \\ {1}\end{array}\right] \Rightarrow\begin{cases}\text { outcome }=0 \quad \frac{1}{\sqrt{2}} \left[\begin{matrix}1 \\ 1 \\ 0 \\ 0 \\\end{matrix}\right] \\ \text { outcome }=1 \quad \frac{1}{\sqrt{2}} \left[\begin{matrix}0 \\ 0 \\ 1 \\ 1 \\\end{matrix}\right] \\\end{cases}
H ⊗ 2 ( [ 1 0 ] ⊗ [ 1 0 ] ) = 2 1 ⎣ ⎢ ⎢ ⎡ 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ⎦ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎡ 1 0 0 0 ⎦ ⎥ ⎥ ⎤ = 2 1 ⎣ ⎢ ⎢ ⎡ 1 1 1 1 ⎦ ⎥ ⎥ ⎤ ⇒ ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ outcome = 0 2 1 ⎣ ⎢ ⎢ ⎡ 1 1 0 0 ⎦ ⎥ ⎥ ⎤ outcome = 1 2 1 ⎣ ⎢ ⎢ ⎡ 0 0 1 1 ⎦ ⎥ ⎥ ⎤
量子不可克隆定理(No-Cloning Theorem)
不存在一个变换U U U 使得∀ ϕ \forall \phi ∀ ϕ 可以实现:
U ∣ ϕ 0 ⟩ = ∣ ϕ ϕ ⟩ = ∣ ϕ ⟩ ⊗ 2 U \vert \phi 0 \rangle = \vert \phi \phi \rangle = \vert \phi \rangle^{\otimes 2}
U ∣ ϕ 0 ⟩ = ∣ ϕ ϕ ⟩ = ∣ ϕ ⟩ ⊗ 2
所以不要妄想先备份再观测来防止坍缩了…
Microsoft Q#入门
唔…是入门,因此只包含一些基本常识性问题。
最最基本的常识都可以在这里找到: Microsoft Q#官方文档(英文版): Language 。
用let
定义变量表示将变量定义为一个常量,例如let n = Length(A)
表示记C/C++中的const int n = A.size()
;用mutable
定义真正的变量,用set
表示赋值来修改一个mutable
类型的值。
Bool
类型和Int
类型不能混用。
结构以C/C++为基准,语句以;
表示结束。
注意每个结构语句后面都必须用大括号。
使用a .. b
来表示一个a
到b
的闭区间,因此循环可以写成:
1 2 3 for(i in 0 .. N-1){ OPERATION; }
量子比特的观测返回值不是坍缩后的量子比特位,而是一个Result
类型,其中只有两个常量One
和Zero
,字面意思。
调用各种变换: H(x)
表示Hadamard Transform;X(x)
表示Pauli-X Gate,Y和Z同理;CNOT(x,y)
表示x
是1
的情况下反转y
。
因为Qubit
是静态的,新建要用using
语法,具体见Codeforces 1001I
。
Microsoft Q# Coding Contest - Summer 2018 - Warmup
题目大意: 输入∣ 0 ⟩ \vert 0 \rangle ∣ 0 ⟩ 根据要求构造∣ + ⟩ \vert + \rangle ∣ + ⟩ 或者∣ − ⟩ \vert - \rangle ∣ − ⟩ 。
Codeforces上这个比赛是已经实现好了主程序,只需要Q#实现一个接口就可以了。
这个很简单,根据定义就是一次Hadmard Transform。如果要∣ − ⟩ \vert - \rangle ∣ − ⟩ 就需要反转一个量子比特,而这个操作就是Pauli-X Gate。
1 2 3 4 5 6 7 8 9 10 11 12 namespace Solution{ open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve(q:Qubit, sign:Int):(){ body{ if(sign==-1){ X(q); } H(q); } } }
奇奇怪怪的新语言没有代码高亮没人权
题目大意: 输入∣ 00 ⟩ \vert 00 \rangle ∣ 0 0 ⟩ 根据要求构造∣ B 0 ⟩ , ∣ B 1 ⟩ , ∣ B 2 ⟩ , ∣ B 3 ⟩ \vert B_0 \rangle,\vert B_1 \rangle,\vert B_2 \rangle,\vert B_3 \rangle ∣ B 0 ⟩ , ∣ B 1 ⟩ , ∣ B 2 ⟩ , ∣ B 3 ⟩ 。
如何得到∣ 00 ⟩ ± ∣ 11 ⟩ \vert 00 \rangle \pm \vert 11 \rangle ∣ 0 0 ⟩ ± ∣ 1 1 ⟩ 是这道题的一个难点。做完这道题对简单量子计算编程究竟是在干什么就有点了解了: 大致就要通过已经定义的若干位运算实现一些操作,有点类似于传统图灵机模型的底层。
首先用Hadamard Transform可以构造出∣ 0 ⟩ ± ∣ 1 ⟩ \vert 0 \rangle \pm \vert 1 \rangle ∣ 0 ⟩ ± ∣ 1 ⟩ 。然后关联可以得到( ∣ 0 ⟩ ± ∣ 1 ⟩ ) ∣ 0 ⟩ = ∣ 00 ⟩ ± ∣ 10 ⟩ (\vert 0 \rangle \pm \vert 1 \rangle)\vert 0 \rangle = \vert 00 \rangle \pm \vert 10 \rangle ( ∣ 0 ⟩ ± ∣ 1 ⟩ ) ∣ 0 ⟩ = ∣ 0 0 ⟩ ± ∣ 1 0 ⟩ 。然后怎么改后一位?CNOT!
对于另外两个状态无非是再反转一下最后一位。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 namespace Solution{ open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve(qs:Qubit[], index:Int):(){ body{ if(index%2==1){ X(qs[0]); } H(qs[0]); if(index>1){ X(qs[1]); } CNOT(qs[0],qs[1]); } } }
题目大意: 输入∣ 00...0 ⏟ N ⟩ \vert \underbrace{00...0}_N \rangle ∣ N 0 0 . . . 0 ⟩ 构造G H Z N = 1 2 ( ∣ 00...0 ⏟ N ⟩ + ∣ 11...1 ⏟ N ⟩ ) GHZ_N = \frac{1}{\sqrt 2}(\vert \underbrace{00...0}_N \rangle + \vert \underbrace{11...1}_N \rangle) G H Z N = 2 1 ( ∣ N 0 0 . . . 0 ⟩ + ∣ N 1 1 . . . 1 ⟩ ) 。
有了上一题经验就好办了,不过是上一题∣ B 0 ⟩ \vert B_0 \rangle ∣ B 0 ⟩ 的N = 2 N = 2 N = 2 变成现在的任意N N N 。只要先Hadamard Transform然后不停用CNOT就好了。
1 2 3 4 5 6 7 8 9 10 11 12 13 namespace Solution{ open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve(qs:Qubit[]):(){ body{ let n = Length(qs); H(qs[0]); for(i in 1 .. n-1){ CNOT(qs[i-1],qs[i]); } } } }
题目大意: 输入∣ + ⟩ \vert + \rangle ∣ + ⟩ 或∣ − ⟩ \vert - \rangle ∣ − ⟩ ,请识别出来。
注意Hadamard Transform一个特别神奇的性质: H − 1 = H H^{-1} = H H − 1 = H 。因此再做一个Hadamard Transform就等价于逆运算,因此就可以还原出∣ 0 ⟩ \vert 0 \rangle ∣ 0 ⟩ 和∣ 1 ⟩ \vert 1 \rangle ∣ 1 ⟩ ,这样再观测就是肯定正确了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 namespace Solution{ open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve(q:Qubit):Int{ body{ H(q); if(M(q)==Zero){ return 1; }else{ return -1; } } } }
题目大意: 输入∣ B 0 ⟩ , ∣ B 1 ⟩ , ∣ B 2 ⟩ , ∣ B 3 ⟩ \vert B_0 \rangle,\vert B_1 \rangle,\vert B_2 \rangle,\vert B_3 \rangle ∣ B 0 ⟩ , ∣ B 1 ⟩ , ∣ B 2 ⟩ , ∣ B 3 ⟩ ,请识别出来。
把B题的程序反过来写就好了,同样利用CNOT Gate和Hadamard Transform的可逆性。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 namespace Solution{ open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve(qs:Qubit[]):Int{ body{ CNOT(qs[0],qs[1]); H(qs[0]); if(M(qs[1])==Zero){ if(M(qs[0])==Zero){ return 0; }else{ return 1; } }else{ if(M(qs[0])==Zero){ return 2; }else{ return 3; } } } } }
题目大意: 判断一个每一位都是∣ 0 ⟩ \vert 0 \rangle ∣ 0 ⟩ 或∣ 1 ⟩ \vert 1 \rangle ∣ 1 ⟩ 的N N N 位量子比特是否是二进制序列S 1 S_1 S 1 所描述的,或者是否是二进制序列S 2 S_2 S 2 所描述的。
没看出来这题的考点是啥?直接观测就好了吧?不过题解似乎给出了一种只观测一次的方法: 先比较S 1 S_1 S 1 和S 2 S_2 S 2 ,然后观测不一样的位。可是这种量子计算时间复杂度肯定不构成瓶颈,少观测一次有啥意义呢?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 namespace Solution{ open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve(qs:Qubit[], bits0:Bool[], bits1:Bool[]):Int{ body{ let n = Length(qs); for(i in 0 .. n-1){ if((M(qs[i])==One)!=bits0[i]){ return 1; } } return 0; } } }
题目大意: 这里引入一个量子预言机(Quantum Oracle,Oracle翻译有待争议: 预言机/神谕/黑箱/专家…)的定义: 一个量子预言机是一个函数f : { 0 , 1 } n → { 0 , 1 } f: \lbrace 0,1 \rbrace^n \rightarrow \lbrace 0,1 \rbrace f : { 0 , 1 } n → { 0 , 1 } 。而为了方便,其有一种特殊的输出方式,就是调用f ( ∣ x ⟩ , ∣ y ⟩ ) f(\vert x \rangle, \vert y \rangle) f ( ∣ x ⟩ , ∣ y ⟩ ) 以后将f ( x ) f(x) f ( x ) 输出到∣ y ⟩ \vert y \rangle ∣ y ⟩ ,而且输出结果不是覆盖y y y 而是叠加在y y y 上,记作f ( x ) ⊕ y f(x) \oplus y f ( x ) ⊕ y 。即:
f ∣ x ⟩ ∣ y ⟩ = ∣ x ⟩ ∣ f ( x ) ⊕ y ⟩ f \vert x \rangle \vert y \rangle = \vert x \rangle \vert f(x) \oplus y \rangle
f ∣ x ⟩ ∣ y ⟩ = ∣ x ⟩ ∣ f ( x ) ⊕ y ⟩
现在给定常数k k k ,需要实现一个量子预言机: f ( x ) = x k f(x) = x_k f ( x ) = x k 。默认∣ y ⟩ = ∣ 0 ⟩ \vert y \rangle = \vert 0 \rangle ∣ y ⟩ = ∣ 0 ⟩
那就让y = x k y = x_k y = x k 即可,一个CNOT Gate就完事了。
1 2 3 4 5 6 7 8 9 namespace Solution{ open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve (x:Qubit[], y:Qubit, k:Int):(){ body{ CNOT(x[k],y); } } }
题目大意: 上一题已经定义了量子预言机。这道题题面就是题目,需要实现一个量子预言机: f ( x ) = x 1 ⊕ x 2 ⊕ . . . ⊕ x n f(x) = x_1 \oplus x_2 \oplus ... \oplus x_n f ( x ) = x 1 ⊕ x 2 ⊕ . . . ⊕ x n ,这里⊕ \oplus ⊕ 是异或.
注意CNOT的可逆性。对每个1 1 1 都把输出CNOT一下,那么最后奇数个1 1 1 就得到∣ 1 ⟩ \vert 1 \rangle ∣ 1 ⟩ ,否则得到∣ 0 ⟩ \vert 0 \rangle ∣ 0 ⟩ 。
1 2 3 4 5 6 7 8 9 10 11 12 namespace Solution{ open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve(x:Qubit[], y:Qubit):(){ body{ let n = Length(x); for(i in 0 .. n-1){ CNOT(x[i],y); } } } }
题目大意: 给定一个量子预言机f f f ,只能调用一次: 判断f f f 是否是一个常函数。这里如果f f f 不是常函数,保证f f f 是平衡的: 在f f f 的定义域内有恰好一半的值映射到0 0 0 ,恰好一半的值映射到1 1 1 。
这是最妙的一道题了。
解法就是题目名: Deutsch-Jozsa algorithm。
一个key idea就是:
∣ 1 2 n ∑ x = 0 2 n − 1 ( − 1 ) f ( x ) ∣ \left \vert \frac{1}{2^n} \sum_{x=0}^{2^n-1}(-1)^{f(x)} \right \vert
∣ ∣ ∣ ∣ ∣ 2 n 1 x = 0 ∑ 2 n − 1 ( − 1 ) f ( x ) ∣ ∣ ∣ ∣ ∣
对于常函数是1 1 1 ,对于平衡函数是0 0 0 。而怎么构造( − 1 ) f ( x ) (-1)^{f(x)} ( − 1 ) f ( x ) 呢?
( − 1 ) f ( x ) = ∣ f ( x ) ⟩ − ∣ 1 ⊕ f ( x ) ⟩ ∣ 0 ⟩ − ∣ 1 ⟩ (-1)^{f(x)} = \frac{\vert f(x) \rangle - \vert 1 \oplus f(x) \rangle}{\vert 0 \rangle - \vert 1 \rangle}
( − 1 ) f ( x ) = ∣ 0 ⟩ − ∣ 1 ⟩ ∣ f ( x ) ⟩ − ∣ 1 ⊕ f ( x ) ⟩
看到了⊕ \oplus ⊕ 就令人想起量子预言机…
那怎么把x x x 搞出来呢?回忆:
∣ + ⟩ ⊗ n = 1 2 n [ 1 1 . . . 1 ] = 1 2 n ∑ x = 0 2 n − 1 ∣ x ⟩ \vert + \rangle^{\otimes n} = \frac{1}{\sqrt{2^n}}\left[\begin{matrix}1 \\ 1 \\ ... \\ 1\end{matrix}\right] = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\vert x \rangle
∣ + ⟩ ⊗ n = 2 n 1 ⎣ ⎢ ⎢ ⎡ 1 1 . . . 1 ⎦ ⎥ ⎥ ⎤ = 2 n 1 x = 0 ∑ 2 n − 1 ∣ x ⟩
于是:
f ∣ + ⟩ ⊗ n ∣ − ⟩ = 1 2 n + 1 ∑ x = 0 2 n − 1 ∣ x ⟩ ( ∣ f ( x ) ⟩ − ∣ 1 ⊕ f ( x ) ⟩ ) = 1 2 n + 1 ∑ x = 0 2 n − 1 ( − 1 ) f ( x ) ∣ x ⟩ ( ∣ 0 ⟩ − ∣ 1 ⟩ ) = 1 2 n ( ∑ x = 0 2 n − 1 ( − 1 ) f ( x ) ∣ x ⟩ ) ∣ − ⟩ \begin{aligned}
& f \vert + \rangle^{\otimes n} \vert - \rangle \\
= & \frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1}\vert x \rangle(\vert f(x) \rangle - \vert 1 \oplus f(x) \rangle) \\
= & \frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1}(-1)^{f(x)}\vert x \rangle(\vert 0 \rangle - \vert 1 \rangle) \\
= & \frac{1}{\sqrt{2^n}} \left(\sum_{x=0}^{2^n-1}(-1)^{f(x)}\vert x \rangle \right) \vert - \rangle \\
\end{aligned}
= = = f ∣ + ⟩ ⊗ n ∣ − ⟩ 2 n + 1 1 x = 0 ∑ 2 n − 1 ∣ x ⟩ ( ∣ f ( x ) ⟩ − ∣ 1 ⊕ f ( x ) ⟩ ) 2 n + 1 1 x = 0 ∑ 2 n − 1 ( − 1 ) f ( x ) ∣ x ⟩ ( ∣ 0 ⟩ − ∣ 1 ⟩ ) 2 n 1 ( x = 0 ∑ 2 n − 1 ( − 1 ) f ( x ) ∣ x ⟩ ) ∣ − ⟩
将式子前半部分用向量表示出来,发现就是第i i i 行是( − 1 ) f ( i ) (-1)^{f(i)} ( − 1 ) f ( i ) 的列向量,只要加起来就好了!怎么加起来呢,考虑H n = H ⊗ n H_n = H^{\otimes n} H n = H ⊗ n ,手动递归下会发现第一行全都是1 / 2 n 1/\sqrt{2^n} 1 / 2 n 。也就是说Hadamard Transform作用于这个列向量(不包括∣ − ⟩ \vert - \rangle ∣ − ⟩ )以后的第一个量子比特就是1 2 n ∑ x ( − 1 ) f ( x ) \frac{1}{2^n}\sum_x {(-1)}^{f(x)} 2 n 1 ∑ x ( − 1 ) f ( x ) 。
但是注意,并不是Hadamard Transform以后观测第一个量子比特就行了。因为多个比特系统的观测,坍缩是随机的。必须检验每个位置是不是都有可能被坍缩到。
也许是这样?求大佬指点
UPD 2020.09.04: 作用以后第一个值是1 2 n ∑ x ( − 1 ) f ( x ) \frac{1}{2^n}\sum_x {(-1)}^{f(x)} 2 n 1 ∑ x ( − 1 ) f ( x ) , 如果该值为1 1 1 则意味着100 100% 1 0 0 的概率出现\vertt 0 \rangle^{\otimes n}, 故检查每一位如果存在1 1 1 就说明不是常函数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 namespace Solution{ open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve(N:Int, Uf:((Qubit[],Qubit)=>())):Bool{ body{ mutable f = true; using(qs=Qubit[N+1]){ X(qs[N]); for(i in 0 .. N){ H(qs[i]); } Uf(qs[0 .. N-1], qs[N]); for(i in 0 .. N){ H(qs[i]); } for(i in 0 .. N-1){ if(M(qs[i])==One){ set f = false; } } ResetAll(qs); } return f; } } }
这么鬼畜的公式推导怎么想到的啊?给跪了。
扫描二维码即可在手机上查看这篇文章,或者转发二维码来分享这篇文章: