QOJ.ac

QOJ

Total points: 100 Output Only

# 5172. 序程来未

统计

本题是一道送分题提交答案题。

题目背景

在 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> 二进制下 $2^i$ 位为 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>] EndifM <id><id> 为编号。其中 IfM 为分支结构,若读取到 1 则会执行 IfM 与与它匹配的 Else(若无 Else 则为 Endif)之间的语句,否则若有匹配的 Else 的话,会执行 ElseEndif 之间的语句。如果使用 M 则会记录此时的结果并继续执行。注意:IfM 语句块中不允许使用 M

一个代码块可以有返回值,可以为 $-2^{31}$ 到 $2^{31}-1$ 之间的任意值,默认为 0。可使用 Return <ret>,则会立刻结束这个代码块,并且返回 ret。也可以使用 ReturnFull <ret0> <ret1> ... <ret2^k-1>,共 $2^k$ 个值,其中 $k$ 为这个代码块从 Begin 到目前为止的 M 的个数,若 M 得到的读取结果分别为 $x_0, x_1,\cdots, x_{k-1}$,则会返回第 $\sum_{i=0}^{k-1} 2^ix_i$(从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}$;要求的状态与生成的可以相差一个 $e^{i\theta}$(常数倍),且可以有 $10^{-6}$ 的绝对误差(具体参考 checker.cpp 的实现,但一般实现不回超过);若不为固定的输入,要求生成特定的输出,则要求相差的 $e^{i\theta}$ 对所有输入均为一个常数。

提示:不保证按照难度排序。 一切以 checker 为准。(若遇到题意与 checker 矛盾可在群里反馈。)

样例1

1 个代码块,1 个比特,初始状态为 $|0\rangle$。实现一个随机数生成器,以 $1/2$ 的概率返回 0,$1/2$ 的概率返回 1。
限制:这个代码块中语句个数不超过 3,不允许使用 IfM,至多使用 1 个 M
参考答案为下发文件中 quantum_sample1.out

任务1

1 个代码块,1 个比特,初始状态为 $|0\rangle$。实现一个随机数生成器,以 $14343375/16777216$ 的概率返回 14343375,$1-14343375/16777216$ 的概率返回 0。
限制:这个代码块中语句个数不超过 3,不允许使用 IfM,至多使用 1 个 M

任务2

1 个代码块,1 个比特,初始状态为 $|0\rangle$。实现一个随机数生成器,以 $1/4$ 的概率返回 1,以 $1/4$ 的概率返回 2,以 $1/4$ 的概率返回 3,以 $1/4$ 的概率返回 4。
限制:这个代码块中语句个数不超过 5,不允许使用 Rx Ry Rz IfM,至多使用 2 个 M

任务3

1 个代码块,1 个比特,初始状态为 $|0\rangle$。实现一个随机数生成器,以 $10\%$ 的概率返回 1,以 $20\%$ 的概率返回 2,以 $30\%$ 的概率返回 3,以 $40\%$ 的概率返回 4。
限制:这个代码块中语句个数不超过 20,不允许使用 M,至多使用 3 个 IfM

任务4

1 个代码块,1 个比特,初始状态为 $|0\rangle$。实现一个随机数生成器,以 $10\%$ 的概率返回 1,以 $20\%$ 的概率返回 2,以 $30\%$ 的概率返回 3,以 $40\%$ 的概率返回 4。
限制:这个代码块中语句个数不超过 20,不允许使用 IfM,至多使用 3 个 M

任务5

1 个代码块,1 个比特,初始状态为 $|0\rangle$。生成 $(\sqrt{0.1}+\sqrt{0.2}i)|0\rangle+(\sqrt{0.3}+\sqrt{0.4}i)|1\rangle$。
限制:这个代码块中语句个数不超过 5,不允许使用 IfM M

任务6

1 个代码块,1 个比特,初始状态为 $(|0\rangle+i|1\rangle)/\sqrt2$ 或 $(|0\rangle-i|1\rangle)/\sqrt2$。若为 $(|0\rangle+i|1\rangle)/\sqrt2$ 则返回 1,否则返回 0. 限制:这个代码块中语句个数不超过 8,不允许使用 Rx Ry Rz,至多使用 1 个 M,至多使用 1 个 IfM

任务7

伊利泽-威德曼炸弹测试问题。
2 个代码块,1 个比特。初始状态为 $|0\rangle$,会先执行第一个代码块,然后会有两种情况:

  1. 有“炸弹”读取这个比特的值,如果为 1 则爆炸,不会继续执行;
  2. 不会进行任何操作。 然后执行第二个代码块,得到返回值 1 或 -1,其中 1 表示一定有“炸弹”,-1 表示不确定。要求:若没有“炸弹”则返回值为 1 的概率不超过 $10^{-6}$;若有炸弹,则爆炸的概率要小于 $60\%$,且不爆炸且返回 1 的概率要大于 $20\%$。
    限制:第一个代码块中语句个数不超过 2,不允许使用 IfM M;第二个代码块中语句个数不超过 5,至多使用 1 个 M,至多使用 1 个 IfM

任务8

1 个代码块,2 个比特,初始状态为 $|00\rangle$。生成 $(|00\rangle+i|10\rangle+i|01\rangle-|11\rangle)/2$。
限制:这个代码块中语句个数不超过 2,不允许使用 IfM M

任务9

1 个代码块,2 个比特,交换这两个比特(即实现 SWAP)。
限制:这个代码块中语句个数不超过 5,不允许使用 SWAP M IfM

任务10

1 个代码块,2 个比特,初始状态为 $|00\rangle$,生成 $(|10\rangle-|01\rangle)/\sqrt{2}$。
限制:这个代码块中语句个数不超过 5,不允许使用 IfM M Rx Ry Rz

任务11

1 个代码块,2 个比特,初始状态为 $|00\rangle$。生成 $\sqrt{0.1}|00\rangle+\sqrt{0.2}|10\rangle+\sqrt{0.3}|01\rangle+\sqrt{0.4}|11\rangle$。
限制:这个代码块中语句个数不超过 5,不允许使用 IfM M Rx Ry Rz

任务12

1 个代码块,7 个比特,初始状态为 $|0000000\rangle$。生成 $(|1000000\rangle+|0100000\rangle+|0010000\rangle+|0001000\rangle+|0000100\rangle+|0000010\rangle+|0000001\rangle)/\sqrt{7}$。
限制:这个代码块中语句个数不超过 15,不允许使用 IfM M

任务13

1 个代码块,8 个比特,初始状态为 $|00000000\rangle$。生成 $(|10000000\rangle+|01000000\rangle+|00100000\rangle+|00010000\rangle+|00001000\rangle+|00000100\rangle+|00000010\rangle+|00000001\rangle)/\sqrt{8}$。
限制:这个代码块中语句个数不超过 20,不允许使用 IfM M Rx Ry Rz

任务14

1 个代码块,5 个比特,初始状态为 $|00000\rangle$。生成 $(|11000\rangle+|10100\rangle+|10010\rangle+|10001\rangle+|01100\rangle+|01010\rangle+|01001\rangle+|00110\rangle+|00101\rangle+|00011\rangle)/\sqrt{10}$。(含有所有含两个1的。)
限制:这个代码块中语句个数不超过 30,不允许使用 IfM M

任务15

1 个代码块,6 个比特,初始状态为 $|000000\rangle$。生成 $(|111000\rangle+|110100\rangle+\cdots+|000111\rangle)/\sqrt{20}$。(含有所有含 3 个 1 的。)
限制:这个代码块中语句个数不超过 35,不允许使用 IfM M

任务16

1 个代码块,4 个比特,要求对一个系数,如果它的基向量的第0、1、2位有奇数个比特为1,则将第3位取反(0变1,1变0)。即把 $|x_0x_1x_2x_3\rangle$ 的系数变为 $|x_0x_1x_2(x_3\operatorname{xor} [x_0,x_1,x_2\texttt{中有奇数个}1])\rangle$ 的系数。
限制:这个代码块中语句个数不超过 5,不允许使用 IfM M

任务17

1 个代码块,5 个比特,要求对一个系数,如果它的基向量的第0、1、2、3位恰有1个比特为1,则将第4位取反(0变1,1变0)。即把 $|x_0x_1x_2x_3x_4\rangle$ 的系数变为 $|x_0x_1x_2x_3(x_4\operatorname{xor} [x_0,x_1,x_2,x_3\texttt{中恰有一个}1])\rangle$ 的系数。
限制:这个代码块中语句个数不超过 10,不允许使用 IfM M

任务18

2 个代码块,2 个比特。初始状态为 $(|00\rangle-|01\rangle)/\sqrt{2}$,会先执行第一个代码块,然后会有两种情况:

  1. 执行 X 1 1,即以第0个比特为控制比特,进行
  2. 不会进行任何操作。
    然后执行第二个代码块,得到返回值 1 或 0,其中 1 表示一定有执行 X 1 1,0 表示一定没有执行。
    限制:第一个代码块中语句个数不超过 2,不允许使用 IfM M;第二个代码块中语句个数不超过 5,至多使用 1 个 M,至多使用 1 个 IfM。两个代码块中均不能使用第1个比特。(无论是操作、读取还是作为控制比特。)

任务19

4 个代码块,3 个比特,初始状态为 $|000\rangle$。先执行第1个代码块,然后分别执行三个代码块,实现三个随机数生成器,三个代码块返回值为 0 或 1,且一共返回奇数个 1,且四种情况等概率。
限制:第1个代码块中语句个数不超过 4,其余代码块中语句个数不超过 2,均不允许使用 IfM;第1个代码块不允许使用 M,其余代码块至多使用 1 个 M。第2个代码块只能使用第0个比特,第3个代码块只能使用第1个比特,第4个代码块只能使用第2个比特。

任务20

5 个代码块,2 个比特,初始状态为 $|00\rangle$。先执行第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 的输入检测,所以可能这里能过,但不能通过上面的测试。通常只要输出中整数不会造成读入时溢出、小数按正常写法(不按科学计数法、无 naninf)就不会造成误判。

附录1:非传统的计算机模型

(遇到难以理解的地方可以在群里提问或根据下方参考资料自行搜索。)

在这个模型当中,若它有 $n$ 个比特,则(可以看作)它的内部有 $2^n$ 个复数参数 $w_0, w_1, \cdots w_{2^n-1}$,可以表示这个模型的一个状态。为了方便,可以把这 $2^n$ 个参数写成一个列向量,而这个列向量的第 $i$ 个(标准)基向量通常记作 $|x_0\cdots x_{n-1}\rangle$,其中 $i=\sum_{k=0}^{n-1}2^kx_k$。

对单个比特的操作:一种操作对应一种酉矩阵$U$(它的共轭转置是它的逆),其中 $$H=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix},T=\begin{bmatrix}1&0\\0&e^{i\pi/4}\end{bmatrix},X=\begin{bmatrix}0&1\\1&0\end{bmatrix},Y=\begin{bmatrix}0&-i\\ i&0\end{bmatrix},Z=\begin{bmatrix}1&0\\0&-1\end{bmatrix},$$ $$Rx(\theta)=\begin{bmatrix}\cos(\theta/2)&-i\sin(\theta/2)\\-i\sin(\theta/2)&\cos(\theta/2)\end{bmatrix},Ry(\theta)=\begin{bmatrix}\cos(\theta/2)&-\sin(\theta/2)\\\sin(\theta/2)&\cos(\theta/2)\end{bmatrix},Rz(\theta)=\begin{bmatrix}e^{-i\theta/2}&0\\0&e^{i\theta/2}\end{bmatrix}.$$

当它作用于第 $i$ 个比特时,状态会发生变化 $w\to w'$,具体地, $$\begin{bmatrix}w'_{|x_0\cdots x_{i-1}0 x_{i+1}\cdots x_{n-1}\rangle}\\ w'_{|x_0\cdots x_{i-1}1 x_{i+1}\cdots x_{n-1}\rangle}\end{bmatrix}=U\begin{bmatrix}w_{|x_0\cdots x_{i-1}0 x_{i+1}\cdots x_{n-1}\rangle}\\ w_{|x_0\cdots x_{i-1}1 x_{i+1}\cdots x_{n-1}\rangle}\end{bmatrix}$$

如 $X|0\rangle=|1\rangle,X|1\rangle=|0\rangle,H|0\rangle=(|0\rangle+|1\rangle)/\sqrt2,H|1\rangle=(|0\rangle-|1\rangle)/\sqrt2,H((|0\rangle+|1\rangle)/\sqrt2)=|0\rangle,H((|0\rangle-|1\rangle)/\sqrt2)=|1\rangle$。如果有多个比特,则相当于对其他比特相同、将第 $i$ 个比特为0与1的两个系数进行变换。

对于交换,可看成 $$SWAP_{ij}=\begin{bmatrix}1&0&0&0\\0&0&1&0\\0&1&0&0\\0&0&0&1\end{bmatrix}$$

关于控制比特:当有控制比特时,我们会只对控制比特全为1的那些基向量所对应的系数进行操作。其中被操作的比特不能是控制比特。例如当一共 2 个比特时,直接对0比特操作 X 可以看作 $$\begin{bmatrix}0&1&0&0\\1&0&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}$$ 若第1个比特是控制比特,则矩阵可以看作 $$\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}$$

关于读取比特。读取第 $i$ 个比特时,结果为 0 的概率为状态中第 $i$ 个比特为 0 的所有系数的模长的平方和,结果为 1 的概率为状态中第 $i$ 个比特为 1 的所有系数的模长的平方和。可以证明在所有非读取操作前后,所有系数模长的平方和保持不变,始终为 $1$。(初始为 $|0\cdots0\rangle$。)若读取结果为 0,则会把对应第 $i$ 个比特为1的所有系数设为0,且其余系数同时乘以一个常数,使得所有系数的模长的平方和仍为1。读取结果为 1 同理。

例如:初始为 $|00\rangle$,对第0个比特进行 H后得到 $(|00\rangle+|10\rangle)/\sqrt{2}$,再以第0个比特为控制比特,对第1个比特进行 X 可以得到 $(|00\rangle+|11\rangle)/\sqrt{2}$,之后读取第一个比特,有 $1/2$ 的概率得到 0,且此时为 $|00\rangle$;有 $1/2$ 的概率得到 1,且此时为 $|11\rangle$;则此时再读取第1个比特,得到的结果必和前一次读取结果一样。

附录2:下发文件说明

注:若需更改,更改前建议备份。

checker.cpp 为检验器。与最终测试的 checker 相同。

template.cpp 为方便您得到输出文件的模板。只需要使用 ot 的输出功能即可,不需要自己开文件。

examples.cpp 为一个例子和一个样例(以五五开的概率生成 01 的生成器)。需要和 quantum.cpp 一起编译。如
g++ examples.cpp quantum.cpp -o examples -std=c++11

quantum.cppquantum.h 为库文件。里面包含模拟器 Simulator,执行器 Evaluator,以及打印输出文件的工具 Printer,均为命名空间 namespace quantum 中的类,以及其中的一个结构体 complex 表示复数。
Evaluator 的使用请参考checker。
Printer 的使用:可以使用带文件指针进行初始化,或者使用 set_file(FILE *file) 指定输出文件。关于输出格式中提到的所有操作,可以直接用 <对象>.<操作名> 这个函数,参数为提到的参数,控制比特默认为 0,即没有。ReturnFull 需传入正确长度的 std::vector。注意该类不会进行输出合法性检查。
Simulator 的使用:创建对象时需传入需要用到比特的个数(不能超过16,但可以自行修改maxn)。初始状态为 $|0\dots0\rangle$ ,可以进行 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 的课件。这道题其实没有涉及到算法,是一道送分题。


或者逐个上传: