本题是一道送分题提交答案题。
题目背景
在 2042 年,一个计算机计算模型从理论走到了现实,实现大规模普及。
您是当年 ION 的考生,需要用这个模型实现 20 个任务……
这时您从梦中惊醒,发现自己在做国家集训队互测,需要用这个模型去实现 20 个任务……
题目描述
本题是一道提交答案题。
最简题意:给您一个checker.cpp,请生成可以通过的20个输出文件quantum1.out, quantum2.out, ..., quantum20.out。
请参考下方附录1了解该模型的计算原理。您需要在这个模型上完成 20 个任务,见下方任务要求。
输出格式
为了避免交互可能导致的用时过长、您的程序在运行时记录一些东西、随机的时候有概率因素影响结果等问题,本题采用提交答案。注意,本题区分大小写。
任务要求中具体指出每个点有几个代码块,每个代码块需要由 Begin
开始,End
结束,在代码块中,只有顺序结构和分支结构。
可用的比特从 0 开始编号。如果对单个比特进行操作,若无角度参数,可以使用 <op> <id> <controller ids>
,其中 <op>
为 H
T
X
Y
Z
中的一个,<id>
为操作比特的编号,<controller ids>
以二进制形式存储某个比特是否为控制比特。具体地,第 i 个比特为控制比特当且仅当 <controller ids>
二进制下 2i 位为 1。注意,不允许编号超过范围,<controller ids>
的最高位也不能超过范围,同时被操作的比特不允许是控制比特;若有角度参数,可以使用 <op> <id> <theta> <controller ids>
,其中 <op>
为 Rx
Ry
Rz
中的一个,<theta>
为角度参数,以弧度为单位,其余参数同上。若要交换两个比特,可使用 SWAP <id1> <id2> <controller ids>
交换两个编号为 <id1>
和 <id2>
的比特,注意这两个比特不允许相同。
若要读取一个比特的值,可以使用 IfM <id> <statements> [Else <statements>] Endif
或 M <id>
,<id>
为编号。其中 IfM
为分支结构,若读取到 1 则会执行 IfM
与与它匹配的 Else
(若无 Else
则为 Endif
)之间的语句,否则若有匹配的 Else
的话,会执行 Else
与 Endif
之间的语句。如果使用 M
则会记录此时的结果并继续执行。注意:IfM
语句块中不允许使用 M
。
一个代码块可以有返回值,可以为 −231 到 231−1 之间的任意值,默认为 0。可使用 Return <ret>
,则会立刻结束这个代码块,并且返回 ret
。也可以使用 ReturnFull <ret0> <ret1> ... <ret2^k-1>
,共 2k 个值,其中 k 为这个代码块从 Begin
到目前为止的 M
的个数,若 M
得到的读取结果分别为 x0,x1,⋯,xk−1,则会返回第 ∑k−1i=02ixi(从0开始编号)个值。
提示:可在下发的 template.cpp
上更改,并使用 quantum::Printer
进行输出(可参考附录2)。需和 quantum.cpp
一起编译。如g++ template.cpp quantum.cpp -o <生成的可执行文件> -std=c++11
直接运行可生成 20 个输出。若想生成特定数据点,可使用./<生成的可执行文件> <case_no> [<output_file>]
得到第 <case_no>
个数据点的输出在 <output_file>
(默认为quantum<case_no>.out
)。
任务要求
以下语句个数指的是一个代码块中的,不包括Begin
End
Else
Endif
。以下非大小关系的概率误差不允许超过 10−6;要求的状态与生成的可以相差一个 eiθ(常数倍),且可以有 10−6 的绝对误差(具体参考 checker.cpp
的实现,但一般实现不回超过);若不为固定的输入,要求生成特定的输出,则要求相差的 eiθ 对所有输入均为一个常数。
提示:不保证按照难度排序。
一切以 checker 为准。(若遇到题意与 checker 矛盾可在群里反馈。)
样例1
1 个代码块,1 个比特,初始状态为 |0⟩。实现一个随机数生成器,以 1/2 的概率返回 0,1/2 的概率返回 1。
限制:这个代码块中语句个数不超过 3,不允许使用 IfM
,至多使用 1 个 M
。
参考答案为下发文件中 quantum_sample1.out
。
任务1
1 个代码块,1 个比特,初始状态为 |0⟩。实现一个随机数生成器,以 14343375/16777216 的概率返回 14343375,1−14343375/16777216 的概率返回 0。
限制:这个代码块中语句个数不超过 3,不允许使用 IfM
,至多使用 1 个 M
。
任务2
1 个代码块,1 个比特,初始状态为 |0⟩。实现一个随机数生成器,以 1/4 的概率返回 1,以 1/4 的概率返回 2,以 1/4 的概率返回 3,以 1/4 的概率返回 4。
限制:这个代码块中语句个数不超过 5,不允许使用 Rx
Ry
Rz
IfM
,至多使用 2 个 M
。
任务3
1 个代码块,1 个比特,初始状态为 |0⟩。实现一个随机数生成器,以 10% 的概率返回 1,以 20% 的概率返回 2,以 30% 的概率返回 3,以 40% 的概率返回 4。
限制:这个代码块中语句个数不超过 20,不允许使用 M
,至多使用 3 个 IfM
。
任务4
1 个代码块,1 个比特,初始状态为 |0⟩。实现一个随机数生成器,以 10% 的概率返回 1,以 20% 的概率返回 2,以 30% 的概率返回 3,以 40% 的概率返回 4。
限制:这个代码块中语句个数不超过 20,不允许使用 IfM
,至多使用 3 个 M
。
任务5
1 个代码块,1 个比特,初始状态为 |0⟩。生成 (√0.1+√0.2i)|0⟩+(√0.3+√0.4i)|1⟩。
限制:这个代码块中语句个数不超过 5,不允许使用 IfM
M
。
任务6
1 个代码块,1 个比特,初始状态为 (|0⟩+i|1⟩)/√2 或 (|0⟩−i|1⟩)/√2。若为 (|0⟩+i|1⟩)/√2 则返回 1,否则返回 0.
限制:这个代码块中语句个数不超过 8,不允许使用 Rx
Ry
Rz
,至多使用 1 个 M
,至多使用 1 个 IfM
。
任务7
伊利泽-威德曼炸弹测试问题。
2 个代码块,1 个比特。初始状态为 |0⟩,会先执行第一个代码块,然后会有两种情况:
- 有“炸弹”读取这个比特的值,如果为 1 则爆炸,不会继续执行;
- 不会进行任何操作。
然后执行第二个代码块,得到返回值 1 或 -1,其中 1 表示一定有“炸弹”,-1 表示不确定。要求:若没有“炸弹”则返回值为 1 的概率不超过 10−6;若有炸弹,则爆炸的概率要小于 60%,且不爆炸且返回 1 的概率要大于 20%。
限制:第一个代码块中语句个数不超过 2,不允许使用IfM
M
;第二个代码块中语句个数不超过 5,至多使用 1 个M
,至多使用 1 个IfM
。
任务8
1 个代码块,2 个比特,初始状态为 |00⟩。生成 (|00⟩+i|10⟩+i|01⟩−|11⟩)/2。
限制:这个代码块中语句个数不超过 2,不允许使用 IfM
M
。
任务9
1 个代码块,2 个比特,交换这两个比特(即实现 SWAP
)。
限制:这个代码块中语句个数不超过 5,不允许使用 SWAP
M
IfM
。
任务10
1 个代码块,2 个比特,初始状态为 |00⟩,生成 (|10⟩−|01⟩)/√2。
限制:这个代码块中语句个数不超过 5,不允许使用 IfM
M
Rx
Ry
Rz
。
任务11
1 个代码块,2 个比特,初始状态为 |00⟩。生成 √0.1|00⟩+√0.2|10⟩+√0.3|01⟩+√0.4|11⟩。
限制:这个代码块中语句个数不超过 5,不允许使用 IfM
M
Rx
Ry
Rz
。
任务12
1 个代码块,7 个比特,初始状态为 |0000000⟩。生成 (|1000000⟩+|0100000⟩+|0010000⟩+|0001000⟩+|0000100⟩+|0000010⟩+|0000001⟩)/√7。
限制:这个代码块中语句个数不超过 15,不允许使用 IfM
M
。
任务13
1 个代码块,8 个比特,初始状态为 |00000000⟩。生成 (|10000000⟩+|01000000⟩+|00100000⟩+|00010000⟩+|00001000⟩+|00000100⟩+|00000010⟩+|00000001⟩)/√8。
限制:这个代码块中语句个数不超过 20,不允许使用 IfM
M
Rx
Ry
Rz
。
任务14
1 个代码块,5 个比特,初始状态为 |00000⟩。生成 (|11000⟩+|10100⟩+|10010⟩+|10001⟩+|01100⟩+|01010⟩+|01001⟩+|00110⟩+|00101⟩+|00011⟩)/√10。(含有所有含两个1的。)
限制:这个代码块中语句个数不超过 30,不允许使用 IfM
M
。
任务15
1 个代码块,6 个比特,初始状态为 |000000⟩。生成 (|111000⟩+|110100⟩+⋯+|000111⟩)/√20。(含有所有含 3 个 1 的。)
限制:这个代码块中语句个数不超过 35,不允许使用 IfM
M
。
任务16
1 个代码块,4 个比特,要求对一个系数,如果它的基向量的第0、1、2位有奇数个比特为1,则将第3位取反(0变1,1变0)。即把 |x0x1x2x3⟩ 的系数变为 |x0x1x2(x3xor[x0,x1,x2中有奇数个1])⟩ 的系数。
限制:这个代码块中语句个数不超过 5,不允许使用 IfM
M
。
任务17
1 个代码块,5 个比特,要求对一个系数,如果它的基向量的第0、1、2、3位恰有1个比特为1,则将第4位取反(0变1,1变0)。即把 |x0x1x2x3x4⟩ 的系数变为 |x0x1x2x3(x4xor[x0,x1,x2,x3中恰有一个1])⟩ 的系数。
限制:这个代码块中语句个数不超过 10,不允许使用 IfM
M
。
任务18
2 个代码块,2 个比特。初始状态为 (|00⟩−|01⟩)/√2,会先执行第一个代码块,然后会有两种情况:
- 执行
X 1 1
,即以第0个比特为控制比特,进行 - 不会进行任何操作。
然后执行第二个代码块,得到返回值 1 或 0,其中 1 表示一定有执行X 1 1
,0 表示一定没有执行。
限制:第一个代码块中语句个数不超过 2,不允许使用IfM
M
;第二个代码块中语句个数不超过 5,至多使用 1 个M
,至多使用 1 个IfM
。两个代码块中均不能使用第1个比特。(无论是操作、读取还是作为控制比特。)
任务19
4 个代码块,3 个比特,初始状态为 |000⟩。先执行第1个代码块,然后分别执行三个代码块,实现三个随机数生成器,三个代码块返回值为 0 或 1,且一共返回奇数个 1,且四种情况等概率。
限制:第1个代码块中语句个数不超过 4,其余代码块中语句个数不超过 2,均不允许使用 IfM
;第1个代码块不允许使用 M
,其余代码块至多使用 1 个 M
。第2个代码块只能使用第0个比特,第3个代码块只能使用第1个比特,第4个代码块只能使用第2个比特。
任务20
5 个代码块,2 个比特,初始状态为 |00⟩。先执行第1个代码块,然后第2、3个代码块中恰执行一个,返回一个 0 或 1,第4、5个代码块中恰执行一个, 返回一个 0 或 1。要求:当执行第2、4个代码块时,两个返回值相同且均为0与均为1概率相同;执行第3、5个代码块时,两个返回值在四种情况中概率相同。
限制:所有代码块中语句个数各不超过 5,均不允许使用 IfM
;第1个代码块不允许使用 M
,其余代码块至多使用 1 个 M
。第2、3个代码块只能使用第0个比特,第4、5个代码块只能使用第1个比特。
如何测试你的输出
在终端中先切换到存放该试题的目录下(假设该目录下已经有 checker.cpp、 testlib.h 以及你的输出文件),使用g++ checker.cpp -o checker -std=c++14
编译 checker.cpp,再使用./checker <case_no> [<output_file>]
命令检测 output_file
(默认为quantum<case_no>.out
)能否通过第 <case_no>
个测试数据。如./checker 7
将检测 quantum7.out
能否通过第 7 个测试数据。若检测样例则 <case_no>
为 -1,此时须指定输出文件。同时,该 checker 支持一般的使用 testlib.h 的交互方式,即
./checker <input> <output> <answer>
,<output>
为您的输出文件,输入文件 <input>
中应有一个1~20的正整数,表示测试点编号(可直接使用下发文件中quantum<case_no>.in
), <answer>
对结果没有影响,最终评测与该评测方式等价。
此外,您还可以通过运行 ./checker
检测全部 20 个点。但这个检测没有使用 testlib 的输入检测,所以可能这里能过,但不能通过上面的测试。通常只要输出中整数不会造成读入时溢出、小数按正常写法(不按科学计数法、无 nan
,inf
)就不会造成误判。
附录1:非传统的计算机模型
(遇到难以理解的地方可以在群里提问或根据下方参考资料自行搜索。)
在这个模型当中,若它有 n 个比特,则(可以看作)它的内部有 2n 个复数参数 w0,w1,⋯w2n−1,可以表示这个模型的一个状态。为了方便,可以把这 2n 个参数写成一个列向量,而这个列向量的第 i 个(标准)基向量通常记作 |x0⋯xn−1⟩,其中 i=∑n−1k=02kxk。
对单个比特的操作:一种操作对应一种酉矩阵U(它的共轭转置是它的逆),其中 H=1√2[111−1],T=[100eiπ/4],X=[0110],Y=[0−ii0],Z=[100−1], Rx(θ)=[cos(θ/2)−isin(θ/2)−isin(θ/2)cos(θ/2)],Ry(θ)=[cos(θ/2)−sin(θ/2)sin(θ/2)cos(θ/2)],Rz(θ)=[e−iθ/200eiθ/2].
当它作用于第 i 个比特时,状态会发生变化 w→w′,具体地, [w′|x0⋯xi−10xi+1⋯xn−1⟩w′|x0⋯xi−11xi+1⋯xn−1⟩]=U[w|x0⋯xi−10xi+1⋯xn−1⟩w|x0⋯xi−11xi+1⋯xn−1⟩]
如 X|0⟩=|1⟩,X|1⟩=|0⟩,H|0⟩=(|0⟩+|1⟩)/√2,H|1⟩=(|0⟩−|1⟩)/√2,H((|0⟩+|1⟩)/√2)=|0⟩,H((|0⟩−|1⟩)/√2)=|1⟩。如果有多个比特,则相当于对其他比特相同、将第 i 个比特为0与1的两个系数进行变换。
对于交换,可看成 SWAPij=[1000001001000001]
关于控制比特:当有控制比特时,我们会只对控制比特全为1的那些基向量所对应的系数进行操作。其中被操作的比特不能是控制比特。例如当一共 2 个比特时,直接对0比特操作 X 可以看作 [0100100000010010] 若第1个比特是控制比特,则矩阵可以看作 [1000010000010010]
关于读取比特。读取第 i 个比特时,结果为 0 的概率为状态中第 i 个比特为 0 的所有系数的模长的平方和,结果为 1 的概率为状态中第 i 个比特为 1 的所有系数的模长的平方和。可以证明在所有非读取操作前后,所有系数模长的平方和保持不变,始终为 1。(初始为 |0⋯0⟩。)若读取结果为 0,则会把对应第 i 个比特为1的所有系数设为0,且其余系数同时乘以一个常数,使得所有系数的模长的平方和仍为1。读取结果为 1 同理。
例如:初始为 |00⟩,对第0个比特进行 H
后得到 (|00⟩+|10⟩)/√2,再以第0个比特为控制比特,对第1个比特进行 X
可以得到 (|00⟩+|11⟩)/√2,之后读取第一个比特,有 1/2 的概率得到 0,且此时为 |00⟩;有 1/2 的概率得到 1,且此时为 |11⟩;则此时再读取第1个比特,得到的结果必和前一次读取结果一样。
附录2:下发文件说明
注:若需更改,更改前建议备份。
checker.cpp
为检验器。与最终测试的 checker
相同。
template.cpp
为方便您得到输出文件的模板。只需要使用 ot
的输出功能即可,不需要自己开文件。
examples.cpp
为一个例子和一个样例(以五五开的概率生成 01 的生成器)。需要和 quantum.cpp
一起编译。如g++ examples.cpp quantum.cpp -o examples -std=c++11
quantum.cpp
和 quantum.h
为库文件。里面包含模拟器 Simulator
,执行器 Evaluator
,以及打印输出文件的工具 Printer
,均为命名空间 namespace quantum
中的类,以及其中的一个结构体 complex
表示复数。Evaluator
的使用请参考checker。Printer
的使用:可以使用带文件指针进行初始化,或者使用 set_file(FILE *file)
指定输出文件。关于输出格式中提到的所有操作,可以直接用 <对象>.<操作名>
这个函数,参数为提到的参数,控制比特默认为 0,即没有。ReturnFull
需传入正确长度的 std::vector
。注意该类不会进行输出合法性检查。Simulator
的使用:创建对象时需传入需要用到比特的个数(不能超过16,但可以自行修改maxn)。初始状态为 |0…0⟩ ,可以进行 reset()
回到该状态(或者自行修改状态。可以使用所有对比特的操作,与 w
)Printer
传参要求相同。M(uint8_t id)
会读取比特的信息,返回true
代表1,或 false
代表0,用std::mt19937
实现随机。M(uint8_t id, bool res)
会强制读取结果是 res
,同时更新当前状态的概率,若成功则返回 true
,否则(即概率为0)返回 false
;可通过 get_probability()
读取当前概率,以及 reset_p()
将概率重置为1。
参考资料
对这些东西感兴趣的可以去看看 codeforces 上以前的一些 Q# coding contest 的比赛,或者以前 WC 的课件。这道题其实没有涉及到算法,是一道送分题。