量子计算了解一下~
本文将在没有量子力学基础基本不涉及量子力学前提下 (例如我太菜了搞不懂 布洛赫球面)，仅介绍量子计算需要了解的相关知识，并使用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
一个传统比特(图灵机模型)可以表示为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 ∣ − ⟩ ∣ + ⟩ \vert + \rangle ∣ + ⟩ ∣ − ⟩ \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
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 n n n 2 n 2^n 2 n n n n 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 ⎦ ⎥ ⎥ ⎤
之前关于量子比特的关联时有: ∣ ψ ⟩ ⊗ ∣ ϕ ⟩ = ∣ ψ ⟩ ∣ ϕ ⟩ = ∣ ψ ϕ ⟩ \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 ∣ ϕ ⟩
因为这篇文章是量子计算入门，所以我发现我后面似乎并没有用到纠缠…
对于一个量子比特，进行一次观测并非像传统图灵机模型那样是一个只读操作，而会改变量子比特的状态 。对其进行一个观测，会导致其有∣ α ∣ 2 \vert \alpha \vert^2 ∣ α ∣ 2 ∣ 0 ⟩ \vert 0 \rangle ∣ 0 ⟩ ∣ β ∣ 2 \vert \beta \vert^2 ∣ β ∣ 2 ∣ 1 ⟩ \vert 1 \rangle ∣ 1 ⟩
这里有一个扩展的记号: ⟨ φ ∣ \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 ⎦ ⎥ ⎥ ⎤
不存在一个变换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#官方文档(英文版): 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。
题目大意: 输入∣ 0 ⟩ \vert 0 \rangle ∣ 0 ⟩ ∣ + ⟩ \vert + \rangle ∣ + ⟩ ∣ − ⟩ \vert - \rangle ∣ − ⟩
Codeforces上这个比赛是已经实现好了主程序，只需要Q#实现一个接口就可以了。
这个很简单，根据定义就是一次Hadmard Transform。如果要∣ − ⟩ \vert - \rangle ∣ − ⟩
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 ⟩
对于另外两个状态无非是再反转一下最后一位。
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
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 ∣ 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
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 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 ∣ − ⟩ \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 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; } } }
这么鬼畜的公式推导怎么想到的啊？给跪了。
扫描二维码即可在手机上查看这篇文章，或者转发二维码来分享这篇文章:
