量子计算了解一下~

本文将在没有量子力学基础基本不涉及量子力学前提下(例如我太菜了搞不懂布洛赫球面)，仅介绍量子计算需要了解的相关知识，并使用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$或者$1$.

一个量子比特可以表示为: $\alpha \vert 0 \rangle + \beta \vert 1 \rangle, \alpha, \beta \in \mathbb C, \vert \alpha \vert ^2 + \vert \beta \vert ^2 = 1$. 其中$\vert 0 \rangle$是一个列向量:

$$\left[\begin{matrix}1 \\ 0\end{matrix}\right]$$

同理$\vert 1 \rangle$是一个列向量:

$$\left[\begin{matrix}0 \\ 1\end{matrix}\right]$$

也就是说任意一个量子比特可以表示为形如:

$$\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$, 表示:

$$\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]$$

为了方便定义记号$\vert \psi \rangle^{\otimes n} = \vert \underbrace{\psi \psi … \psi}_n \rangle$可以看到这就是一个暴力枚举组合。一个有$n$位量子比特的组合: $\vert \psi_1 \psi_2 … \psi_n \rangle$显然是一个有$2^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$$

做一些特定的”基本操作”，复杂度是$O(\text{poly }n)$而不是$O(2^n)$。这一特性(以及其他一些特性)是由量子计算机本身底层物理实现决定的，传统计算机无法模拟。

目前仅定义了$\vert 0 \rangle$和$\vert 1 \rangle$，如果在指定$n$位量子比特的条件下，$\vert x \rangle$表示一个只有第$x$行是$1$其他位置都是$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$，其中每个$\vert x_i \rangle$都是$1$位量子比特。

单个量子比特操作

Hadamard Transform(Hadamard Gate):

$$H = \frac{1}{\sqrt 2} \left[\begin{matrix} 1 & 1 \\ 1 & -1 \end{matrix}\right]$$

Hadamard Transform作用在$\vert 0 \rangle$和$\vert 1 \rangle$的结果会经常用到，不仅要会用矩阵运算，为了以后方便还要记住直接运算的公式，并且为了方便定义了记号$\vert + \rangle$和$\vert - \rangle$:

$$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 \\$$

事实上可以有通式$x \in \lbrace 0, 1 \rbrace$:

$$H \vert x \rangle = \frac{\vert 0 \rangle + (-1)^x \vert 1 \rangle}{\sqrt 2}$$

这不是废话么……真的是废话么？

这里稍微提一下: $\vert - \rangle$是什么啊？如果说$\vert + \rangle$可以理解为$\vert 0 \rangle$和$\vert 1 \rangle$的叠加，那么$\vert - \rangle$和$\vert + \rangle$区别是什么？

我也很疑惑，不过看到一个图标是一个红色的小视频播放器的某外国网站上的视频里将这个$\vert - \rangle$称作Negative Uncertainty。似乎有那么点意思: $\vert + \rangle$大致是2种可能叠加，而$\vert - \rangle$更有一点容斥的味道。

Pauli-X Gate，留意这个操作可以反转一个量子比特:

$$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 \\$$

Pauli-Y Gate:

$$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 \\$$

Pauli-Z Gate:

$$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 \\$$

多个量子比特操作

定义Bell States:

$$\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) \\$$

$n$个量子比特的Hadamard Transform:

$$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} \\$$

多个量子比特的Hadamard Transform是一个非常有意思的操作。对于单个量子比特的Hadamard Transform，$\vert 0 \rangle$在经过操作后，有一半的概率是$0$，一半的概率是$1$。从之前的Bell States中已经可以看出，$n$位量子比特的$2^n$种状态是可以叠加在一起的，那么对$n$个量子比特位分别进行Hadamard Transform以后，将整个$n$位看做一个整体的话，其内部就包含了所有$2^n$种可能，并且等概率出现，数学化地说:

$$\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$$

多个量子比特的Hadamard Transform也有通式:

$$H \vert x \rangle = \frac{1}{\sqrt{2^n}}\sum_{z=0}^{2^n-1} (-1)^{xz} \vert z \rangle$$

CNOT Gate，其作用是对于一个两位量子比特，当且仅当第一位是$1$的情况下反转后一位:

$$U_{CNOT} = \left[\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{matrix}\right] \\$$

SWAP Gate，其作用是对于一个两位量子比特，交换两个量子比特:

$$U_{SWAP} = \left[\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{matrix}\right] \\$$

纠缠(Entanglement)

之前关于量子比特的关联时有: $\vert \psi \rangle \otimes \vert \phi \rangle = \vert \psi \rangle \vert \phi \rangle = \vert \psi \phi \rangle$, 表示:

$$\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]$$

但是存在一些$2^n$维列向量状态，不能被表示为$\vert \psi \rangle \otimes \vert \phi \rangle$，这时候就称为这个状态为$n$个量子比特的纠缠态。例如:

$$\left[\begin{matrix}\frac{1}{\sqrt 2} \\ 0 \\ 0 \\ \frac{1}{\sqrt 2} \\\end{matrix}\right]$$

就找不到一组分解$\vert \psi \rangle \otimes \vert \phi \rangle$。这时候，就可以说$\vert \psi \rangle$和$\vert \phi \rangle$发生了纠缠(Entanglement)，这时候这两个量子比特是不可分割的整体。

因为这篇文章是量子计算入门，所以我发现我后面似乎并没有用到纠缠……

观测(Measurement)

对于一个量子比特，进行一次观测并非像传统图灵机模型那样是一个只读操作，而会改变量子比特的状态。对其进行一个观测，会导致其有$\vert \alpha \vert^2$的概率变为$\vert 0 \rangle$，有$\vert \beta \vert^2$的概率变为$\vert 1 \rangle$，即发生了坍缩(Collapse)。

这里有一个扩展的记号: $\langle \varphi \vert$表示一个行向量，且$\langle \varphi \vert = \vert \varphi \rangle^{conj}$，其中$v^{conj}$表示$v$的共轭向量(即先转置然后把每个位置的复数变成其原来的共轭)。为了方便定义$\langle \varphi \vert \phi \rangle = \langle \varphi \vert \times \vert \phi \rangle$。那么就有$\langle \varphi \vert \varphi \rangle = 1$。更一般地，不难验证: 如果$\vert \varphi \rangle$是$\vert \phi \rangle$的一个基本的子状态，那么$\vert \langle \varphi \vert \phi \rangle \vert^2 = \Pr(\vert \phi \rangle \text{ collapse to } \vert \varphi \rangle)$。

对于多个量子比特的观测则比较奇妙: 对于$n$位量子比特，如果存在(不纠缠)独立的量子比特位，那么会随机坍缩一个这样的量子比特到特定的位置上。

这个地方我也搞不太懂求大佬指点。

$$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}$$

量子不可克隆定理(No-Cloning Theorem)

不存在一个变换$U$使得$\forall \phi$可以实现:

$$U \vert \phi 0 \rangle = \vert \phi \phi \rangle = \vert \phi \rangle^{\otimes 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的闭区间，因此循环可以写成:

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

Codeforces 1001A Generate plus state or minus state

题目大意: 输入$\vert 0 \rangle$根据要求构造$\vert + \rangle$或者$\vert - \rangle$。

Codeforces上这个比赛是已经实现好了主程序，只需要Q#实现一个接口就可以了。

这个很简单，根据定义就是一次Hadmard Transform。如果要$\vert - \rangle$就需要反转一个量子比特，而这个操作就是Pauli-X Gate。

namespace Solution{
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;
    operation Solve(q:Qubit, sign:Int):(){
        body{
            if(sign==-1){
                X(q);
            }
            H(q);
        }
    }
}

奇奇怪怪的新语言没有代码高亮没人权

Codeforces 1001B Generate Bell state

题目大意: 输入$\vert 00 \rangle$根据要求构造$\vert B_0 \rangle,\vert B_1 \rangle,\vert B_2 \rangle,\vert B_3 \rangle$。

如何得到$\vert 00 \rangle \pm \vert 11 \rangle$是这道题的一个难点。做完这道题对简单量子计算编程究竟是在干什么就有点了解了: 大致就要通过已经定义的若干位运算实现一些操作，有点类似于传统图灵机模型的底层。

首先用Hadamard Transform可以构造出$\vert 0 \rangle \pm \vert 1 \rangle$。然后关联可以得到$(\vert 0 \rangle \pm \vert 1 \rangle)\vert 0 \rangle = \vert 00 \rangle \pm \vert 10 \rangle$。然后怎么改后一位？CNOT！

对于另外两个状态无非是再反转一下最后一位。

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]);
        }
    }
}

Codeforces 1001C Generate GHZ state

题目大意: 输入$\vert \underbrace{00…0}_N \rangle$构造$GHZ_N = \frac{1}{\sqrt 2}(\vert \underbrace{00…0}_N \rangle + \vert \underbrace{11…1}_N \rangle)$。

有了上一题经验就好办了，不过是上一题$\vert B_0 \rangle$的$N = 2$变成现在的任意$N$。只要先Hadamard Transform然后不停用CNOT就好了。

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]);
            }
        }
    }
}

Codeforces 1001D Distinguish plus state and minus state

题目大意: 输入$\vert + \rangle$或$\vert - \rangle$，请识别出来。

注意Hadamard Transform一个特别神奇的性质: $H^{-1} = H$。因此再做一个Hadamard Transform就等价于逆运算，因此就可以还原出$\vert 0 \rangle$和$\vert 1 \rangle$，这样再观测就是肯定正确了。

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;
            }
        }
    }
}

Codeforces 1001E Distinguish plus state and minus state

题目大意: 输入$\vert B_0 \rangle,\vert B_1 \rangle,\vert B_2 \rangle,\vert B_3 \rangle$，请识别出来。

把B题的程序反过来写就好了，同样利用CNOT Gate和Hadamard Transform的可逆性。

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;
                }
            }
        }
    }
}

Codeforces 1001F Distinguish plus state and minus state

题目大意: 判断一个每一位都是$\vert 0 \rangle$或$\vert 1 \rangle$的$N$位量子比特是否是二进制序列$S_1$所描述的，或者是否是二进制序列$S_2$所描述的。

没看出来这题的考点是啥？直接观测就好了吧？不过题解似乎给出了一种只观测一次的方法: 先比较$S_1$和$S_2$，然后观测不一样的位。可是这种量子计算时间复杂度肯定不构成瓶颈，少观测一次有啥意义呢？

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;
        }
    }
}

Codeforces 1001G Oracle for $f(x) = k-\text{th}$ element of $x$

题目大意: 这里引入一个量子预言机(Quantum Oracle，Oracle翻译有待争议: 预言机/神谕/黑箱/专家……)的定义: 一个量子预言机是一个函数$f: \lbrace 0,1 \rbrace^n \rightarrow \lbrace 0,1 \rbrace$。而为了方便，其有一种特殊的输出方式，就是调用$f(\vert x \rangle, \vert y \rangle)$以后将$f(x)$输出到$\vert y \rangle$，而且输出结果不是覆盖$y$而是叠加在$y$上，记作$f(x) \oplus y$。即:

$$f \vert x \rangle \vert y \rangle = \vert x \rangle \vert f(x) \oplus y \rangle$$

现在给定常数$k$，需要实现一个量子预言机: $f(x) = x_k$。默认$\vert y \rangle = \vert 0 \rangle$

那就让$y = x_k$即可，一个CNOT Gate就完事了。

namespace Solution{
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;
    operation Solve (x:Qubit[], y:Qubit, k:Int):(){
        body{
            CNOT(x[k],y);
        }
    }
}

Codeforces 1001H Oracle for $f(x) = \text{parity of the number of 1s in } x$

题目大意: 上一题已经定义了量子预言机。这道题题面就是题目，需要实现一个量子预言机: $f(x) = x_1 \oplus x_2 \oplus … \oplus x_n$，这里$\oplus$是异或.

注意CNOT的可逆性。对每个$1$都把输出CNOT一下，那么最后奇数个$1$就得到$\vert 1 \rangle$，否则得到$\vert 0 \rangle$。

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);
            }
        }
    }
}

Codeforces 1001I Deutsch-Jozsa algorithm

题目大意: 给定一个量子预言机$f$，只能调用一次: 判断$f$是否是一个常函数。这里如果$f$不是常函数，保证$f$是平衡的: 在$f$的定义域内有恰好一半的值映射到$0$，恰好一半的值映射到$1$。

这是最妙的一道题了。

解法就是题目名: Deutsch-Jozsa algorithm。

一个key idea就是:

$$\left \vert \frac{1}{2^n} \sum_{x=0}^{2^n-1}(-1)^{f(x)} \right \vert$$

对于常函数是$1$，对于平衡函数是$0$。而怎么构造$(-1)^{f(x)}$呢？

$$(-1)^{f(x)} = \frac{\vert f(x) \rangle - \vert 1 \oplus f(x) \rangle}{\vert 0 \rangle - \vert 1 \rangle}$$

看到了$\oplus$就令人想起量子预言机……

那怎么把$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$$

于是:

$$\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}$$

将式子前半部分用向量表示出来，发现就是第$i$行是$(-1)^{f(i)}$的列向量，只要加起来就好了！怎么加起来呢，考虑$H_n = H^{\otimes n}$，手动递归下会发现第一行全都是$1/\sqrt{2^n}$。也就是说Hadamard Transform作用于这个列向量(不包括$\vert - \rangle$)以后的第一个量子比特就是$\frac{1}{2^n}\sum_x {(-1)}^{f(x)}$。

但是注意，并不是Hadamard Transform以后观测第一个量子比特就行了。因为多个比特系统的观测，坍缩是随机的。必须检验每个位置是不是都有可能被坍缩到。

也许是这样？求大佬指点

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;
        }
    }
}

这么鬼畜的公式推导怎么想到的啊？给跪了。

扫描二维码即可在手机上查看这篇文章，或者转发二维码来分享这篇文章: