量子计算与Microsoft Q#入门笔记

量子计算了解一下~

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

一个传统比特(图灵机模型)可以表示为00或者11.

一个量子比特可以表示为: α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\vert 0 \rangle是一个列向量:

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

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

[01]\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, 表示:

[ψ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]

为了方便定义记号ψn=ψψ...ψn\vert \psi \rangle^{\otimes n} = \vert \underbrace{\psi \psi ... \psi}_n \rangle可以看到这就是一个暴力枚举组合。一个有nn位量子比特的组合: ψ1ψ2...ψn\vert \psi_1 \psi_2 ... \psi_n \rangle显然是一个有2n2^n个元素的列向量。量子计算相较于传统计算的优势一部分就在于,对于:

ψ1ψ2...ψn=i1,i2,...,in{0,1}Ci1,i2,...,ini1i2...in\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(poly n)O(\text{poly }n)而不是O(2n)O(2^n)。这一特性(以及其他一些特性)是由量子计算机本身底层物理实现决定的,传统计算机无法模拟。


目前仅定义了0\vert 0 \rangle1\vert 1 \rangle,如果在指定nn位量子比特的条件下,x\vert x \rangle表示一个只有第xx行是11其他位置都是00的向量。会发现如果将xx的二进制分解为xn1xn2...x0x_{n-1}x_{n-2}...x_0,那么x=xn1xn2...x0\vert x \rangle = \vert x_{n-1} \rangle \vert x_{n-2} \rangle ... \vert x_0 \rangle,其中每个xi\vert x_i \rangle都是11位量子比特。


单个量子比特操作

Hadamard Transform(Hadamard Gate):

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

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

H0=12(0+1)=[1212]=+H1=12(01)=[1212]=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{0,1}x \in \lbrace 0, 1 \rbrace:

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

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


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

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


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

X=[0110]X0=1X1=0X = \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=[0ii0]Y0=i1Y1=i0Y = \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=[1001]Z0=0Z1=1Z = \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:

B0=ϕ+=12(00+11)B1=ϕ=12(0011)B2=ψ+=12(01+10)B3=ψ=12(0110)\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) \\

nn个量子比特的Hadamard Transform:

H0=1Hn=[Hn1Hn1Hn1Hn1]=HnH_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,0\vert 0 \rangle在经过操作后,有一半的概率是00,一半的概率是11。从之前的Bell States中已经可以看出,nn位量子比特的2n2^n种状态是可以叠加在一起的,那么对nn个量子比特位分别进行Hadamard Transform以后,将整个nn位看做一个整体的话,其内部就包含了所有2n2^n种可能,并且等概率出现,数学化地说:

+n=12n[11...1]=12nx=02n1x\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也有通式:

Hx=12nz=02n1(1)xzzH \vert x \rangle = \frac{1}{\sqrt{2^n}}\sum_{z=0}^{2^n-1} (-1)^{xz} \vert z \rangle

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

UCNOT=[1000010000010010]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,其作用是对于一个两位量子比特,交换两个量子比特:

USWAP=[1000001001000001]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, 表示:

[ψ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]

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

[120012]\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)

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

这里有一个扩展的记号: φ\langle \varphi \vert表示一个行向量,且φ=φconj\langle \varphi \vert = \vert \varphi \rangle^{conj},其中vconjv^{conj}表示vv的共轭向量(即先转置然后把每个位置的复数变成其原来的共轭)。为了方便定义φϕ=φ×ϕ\langle \varphi \vert \phi \rangle = \langle \varphi \vert \times \vert \phi \rangle。那么就有φφ=1\langle \varphi \vert \varphi \rangle = 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)


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

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

UPD 2020.09.04: 一年以后回来看发现自己当时写了些什么鬼东西。这里的四个位就是代表四个状态00,01,10,11\vert 00 \rangle, \vert 01 \rangle, \vert 10 \rangle, \vert 11 \rangle的概率振幅。目前四个等概率,那么观测第一位如果看到00,那么剩下的概率只能是00,01\vert 00 \rangle, \vert 01 \rangle各一半而不可能出现10,11\vert 10 \rangle, \vert 11 \rangle

H2([10][10])=12[1111111111111111][1000]=12[1111]{ outcome =012[1100] outcome =112[0011]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)

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

Uϕ0=ϕϕ=ϕ2U \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来表示一个ab的闭区间,因此循环可以写成:

1
2
3
for(i in 0 .. N-1){
OPERATION;
}

量子比特的观测返回值不是坍缩后的量子比特位,而是一个Result类型,其中只有两个常量OneZero,字面意思。

调用各种变换: H(x)表示Hadamard Transform;X(x)表示Pauli-X Gate,Y和Z同理;CNOT(x,y)表示x1的情况下反转y

因为Qubit是静态的,新建要用using语法,具体见Codeforces 1001I


Microsoft Q# Coding Contest - Summer 2018 - Warmup

Codeforces 1001A Generate plus state or minus state

题目大意: 输入0\vert 0 \rangle根据要求构造+\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);
}
}
}

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


Codeforces 1001B Generate Bell state

题目大意: 输入00\vert 00 \rangle根据要求构造B0,B1,B2,B3\vert B_0 \rangle,\vert B_1 \rangle,\vert B_2 \rangle,\vert B_3 \rangle


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

首先用Hadamard Transform可以构造出0±1\vert 0 \rangle \pm \vert 1 \rangle。然后关联可以得到(0±1)0=00±10(\vert 0 \rangle \pm \vert 1 \rangle)\vert 0 \rangle = \vert 00 \rangle \pm \vert 10 \rangle。然后怎么改后一位?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]);
}
}
}

Codeforces 1001C Generate GHZ state

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


有了上一题经验就好办了,不过是上一题B0\vert B_0 \rangleN=2N = 2变成现在的任意NN。只要先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]);
}
}
}
}

Codeforces 1001D Distinguish plus state and minus state

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


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

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

Codeforces 1001E Distinguish plus state and minus state

题目大意: 输入B0,B1,B2,B3\vert B_0 \rangle,\vert B_1 \rangle,\vert B_2 \rangle,\vert B_3 \rangle,请识别出来。


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

Codeforces 1001F Distinguish plus state and minus state

题目大意: 判断一个每一位都是0\vert 0 \rangle1\vert 1 \rangleNN位量子比特是否是二进制序列S1S_1所描述的,或者是否是二进制序列S2S_2所描述的。


没看出来这题的考点是啥?直接观测就好了吧?不过题解似乎给出了一种只观测一次的方法: 先比较S1S_1S2S_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;
}
}
}

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

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

fxy=xf(x)yf \vert x \rangle \vert y \rangle = \vert x \rangle \vert f(x) \oplus y \rangle

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


那就让y=xky = 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);
}
}
}

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

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


注意CNOT的可逆性。对每个11都把输出CNOT一下,那么最后奇数个11就得到1\vert 1 \rangle,否则得到0\vert 0 \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(x:Qubit[], y:Qubit):(){
body{
let n = Length(x);
for(i in 0 .. n-1){
CNOT(x[i],y);
}
}
}
}

Codeforces 1001I Deutsch-Jozsa algorithm

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


这是最妙的一道题了。

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

一个key idea就是:

12nx=02n1(1)f(x)\left \vert \frac{1}{2^n} \sum_{x=0}^{2^n-1}(-1)^{f(x)} \right \vert

对于常函数是11,对于平衡函数是00。而怎么构造(1)f(x)(-1)^{f(x)}呢?

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

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

那怎么把xx搞出来呢?回忆:

+n=12n[11...1]=12nx=02n1x\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

于是:

f+n=12n+1x=02n1x(f(x)1f(x))=12n+1x=02n1(1)f(x)x(01)=12n(x=02n1(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}

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

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

也许是这样?求大佬指点

UPD 2020.09.04: 作用以后第一个值是12nx(1)f(x)\frac{1}{2^n}\sum_x {(-1)}^{f(x)}, 如果该值为11则意味着100100%的概率出现\vertt 0 \rangle^{\otimes n}, 故检查每一位如果存在11就说明不是常函数。

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

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


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


文章作者: Magolor
文章链接: https://magolor.cn/2019/09/24/2019-09-24-blog-01/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Magolor
扫描二维码在手机上查看或转发二维码以分享Magolor的博客