时间限制： 1.0 秒

空间限制： 512 MB

题目背景

小 P 最近在网上看到了中国的“九章”量子计算机实现了量子优越性（quantum supremacy）的新闻，就向老师请教什么是量子计算和量子计算机。听了老师深入浅出的讲解，小 P 明白了量子计算的原理其实并不复杂，本质上可以等价为他很早就学过的矩阵乘法，只是运算量很大，而量子计算机可以非常快地完成这些运算。好学的小 P 想研究一些量子电路的性质，因此请你帮他实现一个简单的量子电路模拟器。

题目描述

比特是经典计算机中的一个基本概念，量子计算机中也存在“量子比特”（quantum bit，简写为 qubit）。经典计算机中一个比特的取值可以是 $0$ 或 $1$；量子计算机与之类似，一个量子比特可能处于的两个量子态是 $\ket{0}$ 和 $\ket{1}$，其中$\ket{}$ 是物理学家惯用的 Dirac 符号。经典计算机中的比特取值只可能是 $0$ 和 $1$ 中的一个，而量子比特的状态 $\ket{\Psi}$ 除了处于 $\ket{0}$ 和 $\ket{1}$ 以外，还会处于 $\ket{0}$ 和 $\ket{1}$ 的线性叠加态，记为：

$$ \ket{\Psi} = \alpha_0 \ket{0} + \alpha_1 \ket{1} = \left( \begin{matrix} \alpha_0 \\ \alpha_1 \end{matrix} \right),\,\, \alpha_0, \alpha_1 \in \mathbb{C}. $$

该量子比特测量值为 0 和 1 的概率分别为 $|\alpha_0|^2$ 和 $|\alpha_1|^2$，且满足归一化条件:

$$|\alpha_0|^2 + |\alpha_1|^2 = 1.$$

量子状态的操作是通过量子门（quantum gate）来完成的。 作用在一个量子比特上的量子门简称“单比特门”，可以被表示为一个 $2\times 2$ 的酉矩阵^[1]。一些常见的单比特门为（下文中将会直接使用这些记号）：

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

在一个量子比特 $\ket{\Psi}$ 上作用一个单比特门 $U$，将生成新的量子状态 $(\alpha_0', \alpha_1')$：

$$ \left(\begin{matrix} \alpha_0' \\ \alpha_1' \end{matrix} \right) = U\ket{\Psi} = \left[ \begin{matrix} U_{0,0} & U_{0,1} \\ U_{1,0} & U_{1,1} \end{matrix} \right] \left( \begin{matrix} \alpha_0 \\ \alpha_1 \end{matrix} \right) = \left[ \begin{matrix} U_{0,0} \alpha_0 + U_{0,1} \alpha_1 \\ U_{1,0} \alpha_0 + U_{1,1} \alpha_1 \end{matrix} \right] $$

例如，上面提到的 $X$ 被称为“非门”，它会翻转其作用的量子比特 $\ket{\Psi}=\alpha_0 \ket{0} + \alpha_1 \ket{1}$，生成新的量子状态 $\ket{\Psi'} = \alpha_1 \ket{0} + \alpha_0 \ket{1}$。

类似地，一个包含两个量子比特的量子状态 $\ket{\Psi}$ 有四种可能的状态 $\ket{00}$、$\ket{01}$、$\ket{10}$、$\ket{11}$， 其中 $\ket{\color{blue}p\color{orange}q}$ 表示第 $0$ 个量子比特处于状态 $\ket{q}$ 且第 $1$ 个量子比特处于状态 $\ket{p}$ ($p,q \in {\{0, 1\}}$)。 该双量子比特的状态也可以处于上述四种状态的线性叠加态：

$$ \ket{\Psi} = \alpha_{00} \ket{00} + \alpha_{01} \ket{01} + \alpha_{10} \ket{10} + \alpha_{11} \ket{11} = \left( \begin{matrix} \alpha_{00} \\ \alpha_{01} \\ \alpha_{10} \\ \alpha_{11} \end{matrix} \right) $$

与单比特系统相似，$|\alpha_{ij}|^2$ 是该量子状态的四种测量结果的概率分布，且满足：

$$|\alpha_{00}|^2 + |\alpha_{01}|^2 + |\alpha_{10}|^2 + |\alpha_{11}|^2= 1 $$

类似地，一个作用在两个量子比特上的双比特门可以由一个 $4 \times 4$ 的酉矩阵表示。 一种重要的双比特门称为“受控量子门”（controlled gate），它的表示形如：

$$CU = \begin{bmatrix} 1 & & & \\ & 1 & & \\ & & U_{0,0} & U_{0,1} \\ & & U_{1,0} & U_{1,1} \end{bmatrix} $$

其中 $U = \left[ \begin{matrix} U_{0,0} & U_{0,1} \\ U_{1,0} & U_{1,1} \end{matrix} \right]$ 是一个 $2 \times 2$ 的酉矩阵。

受控量子门中的两个量子比特分别被称为“控制比特”和“目标比特”。 作用一个受控量子门 $CU$ 等价于仅在下标的控制比特所在位为 $1$ 时，在目标比特所在位分别为$0$、$1$的一个数据对上作用对应的单比特门 $U$。 例如，在一个双量子比特系统上作用一个控制比特为第 $1$ 个比特、目标比特为第 $0$ 个比特的受控非门 $CX$，相当于将单比特门 $X$ 作用在数据对 $(\alpha_{ {\color{blue}1} {\color{red}0}}, \alpha_{ {\color{blue}1} {\color{red}1}})$ 上，从而交换二者的值，并保持 $\alpha_{ {\color{blue}0} {\color{red}0}}$ 和 $\alpha_{ {\color{blue}0} {\color{red}1}}$ 的取值不变：

$$ \left( \begin{matrix} \alpha_{00}' \\ \alpha_{01}' \\ \alpha_{10}' \\ \alpha_{11}' \end{matrix} \right) = CX \cdot \left( \begin{matrix} \alpha_{00} \\ \alpha_{01} \\ \alpha_{10} \\ \alpha_{11} \end{matrix} \right) = \left[ \begin{matrix} 1 & & & \\ & 1 & & \\ & & & 1 \\ & & 1 & \end{matrix} \right] \cdot \left( \begin{matrix} \alpha_{00} \\ \alpha_{01} \\ \alpha_{10} \\ \alpha_{11} \end{matrix} \right) = \left( \begin{matrix} \alpha_{00} \\ \alpha_{01} \\ \alpha_{11} \\ \alpha_{10} \end{matrix} \right) $$

也可简写为：

$$\left( \begin{matrix} \alpha_{10}' \\ \alpha_{11}' \end{matrix} \right) = X \cdot \left( \begin{matrix} \alpha_{10} \\ \alpha_{11} \end{matrix} \right) = \left[ \begin{matrix} & 1 \\ 1 & \end{matrix} \right] \cdot \left( \begin{matrix} \alpha_{10} \\ \alpha_{11} \end{matrix} \right) = \left( \begin{matrix} \alpha_{11} \\ \alpha_{10} \end{matrix} \right) $$

在一个双量子比特的系统上也可以作用单比特门。它等价于将矩阵 $U$ 分别乘到两个数据对中，每个数据对的两个下标仅有一位不同（即该比特门的作用位）。 作用在第 $0$ 个量子比特上的门相当于将矩阵分别与 $(\alpha_{0{\color{orange}0}}, \alpha_{0{\color{orange}1}})$ 和 $(\alpha_{1{\color{orange}0}}, \alpha_{1{\color{orange}1}})$相乘， 作用在第 $1$ 个量子比特上的门相当于将矩阵分别与 $(\alpha_{ {\color{orange}0}0}, \alpha_{ {\color{orange}1}0})$ 和 $(\alpha_{ {\color{orange}0}1}, \alpha_{ {\color{orange}1}1})$ 相乘。 例如，将非门作用在第 $1$ 个量子比特上，会分别导致 $\alpha_{ {\color{orange}0}0}$ 与 $\alpha_{ {\color{orange}1}0}$ 的取值交换和 $\alpha_{ {\color{orange}0}1}$ 与 $\alpha_{ {\color{orange}1}1}$ 的取值交换。

本题需要处理的是由 $n$ 个量子比特构成的系统，其状态可由 $2^n$ 个基本状态（或称为“本征态”）$\ket{0\dots00}, \ket{0\dots01}, \dots, \ket{1\dots11}$ 的线性组合表示，记为：

$$ \ket{\Psi}=\alpha_{0\dots00}\ket{0\dots00} + \alpha_{0\dots01}\ket{0\dots01} + \dots +\alpha_{1\dots11}\ket{1..11} $$

为简单起见，下文中将量子系统的状态统一记为向量 $\ket{\Psi}=(\alpha_{0\dots00}, \alpha_{0\dots01}, \dots, \alpha_{1\dots11})$，也可理解为一个包含 $2^n$ 个复数的有序数组。该数组的下标也可等价地使用十进制表示，即可将状态等价地记为$\ket{\Psi}=(\alpha_{0}, \alpha_{1}, \dots, \alpha_{2^n-1})$。 需要注意，$\alpha_i$ 下标 $i$ 的二进制展开中，最低位位于最右端，如 $\alpha_{0\dots011}$的下标的第 $0$ 位和第 $1$ 位为 $1$，其余位为 $0$，对应十进制表示的$\alpha_3$；而在 $\{\alpha_i\}$ 数组的展开 $(\alpha_{0\dots00}, \alpha_{0\dots01}, \dots, \alpha_{1\dots11})$ 中，下标最小的数据位于最左端。

本题需要处理的量子门包括上文提及的单比特门和双比特受控量子门。每个门可由其作用的（一个或两个）量子比特和一个大小为 $2\times 2$ 的酉矩阵 $U$ 表示。

将一个单比特门 $U$ 作用在一个有 $n$ 个量子比特的系统的第 $t$ 个量子比特上，等价于进行 $2^{n-1}$ 个矩阵乘法。 每个矩阵乘法更新下标仅第 $t$ 位不同的一对位置上的数据：

$$ \left( \begin{matrix} \alpha'_{b_{n-1},\dots,b_{t+1},0,b_{t-1},\dots,b_0} \\ \alpha'_{b_{n-1},\dots,b_{t+1},1,b_{t-1},\dots,b_0} \end{matrix} \right) = \left[ \begin{matrix} U_{0,0} & U_{0,1} \\ U_{1,0} & U_{1,1} \end{matrix} \right] \left( \begin{matrix} \alpha_{b_{n-1},\dots,b_{t+1},0,b_{t-1},\dots,b_{0}} \\ \alpha_{b_{n-1},\dots,b_{t+1},1,b_{t-1},\dots,b_{0}} \end{matrix} \right) $$

类似地，将一个控制比特为第 $c$ 个比特，目标比特为第 $t$ 个比特（$c \neq t$）的受控量子门 $CU$ 作用到一个有 $n$ 个量子比特的系统，等价于进行 $2^{n-2}$ 个矩阵乘法。 每个矩阵乘法更新两个特定位置上的数据，这两个特定位置的下标满足控制比特所在的位都是 $1$，且仅有目标比特所在的位不同：

$$ \left( \begin{matrix} \alpha'_{b_{n-1},\dots,b_{c+1},1,b_{c-1},\dots,b_{t+1},0,b_{t-1},\dots,b_{0}} \\ \alpha'_{b_{n-1},\dots,b_{c+1},1,b_{c-1},\dots,b_{t+1},1,b_{t-1},\dots,b_{0}} \\ \end{matrix} \right) = \left[ \begin{matrix} U_{0,0} & U_{0,1} \\ U_{1,0} & U_{1,1} \end{matrix} \right] \left( \begin{matrix} \alpha_{b_{n-1},\dots,b_{c+1},1,b_{c-1},\dots,b_{t+1},0,b_{t-1},\dots,b_{0}} \\ \alpha_{b_{n-1},\dots,b_{c+1},1,b_{c-1},\dots,b_{t+1},1,b_{t-1},\dots,b_{0}} \\ \end{matrix} \right) $$

例如，$\ket{\psi_0} = (1,0,0,0,0,0,0,0)$ 是一个三量子比特的初始状态，在此状态上依次进行下述演化：

1. 在第 $0$ 个量子比特上作用单比特门 $H$，即将 $H$ 的表示矩阵分别与状态向量中，下标只有第 $0$ 位不同的数据对 $(\alpha_{00 {\color{orange}0}}, \alpha_{00 {\color{orange}1}})$、$(\alpha_{01 {\color{orange}0}}, \alpha_{01 {\color{orange}1}})$、$(\alpha_{10 {\color{orange}0}}, \alpha_{10 {\color{orange}1}})$、$(\alpha_{11 {\color{orange}0}}, \alpha_{11 {\color{orange}1}})$ 相乘，得到状态：

$$\ket{\psi_1} = \left(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}, 0, 0, 0, 0, 0, 0 \right) $$

2. 在第 $1$ 个量子比特上作用单比特门 $H$，得到状态：

$$\ket{\psi_2} = \left(\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, 0, 0, 0, 0 \right) $$

3. 在第 $1$ 个量子比特上作用单比特门 $Z$，得到状态：

$$\ket{\psi_3} = \left(\frac{1}{2}, \frac{1}{2}, -\frac{1}{2}, -\frac{1}{2}, 0, 0, 0, 0 \right) $$

4. 在第 $2$ 个量子比特上作用单比特门 $H$，得到状态：

$$\ket{\psi_4} = \left(\frac{1}{2\sqrt{2}}, \frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, \frac{1}{2\sqrt{2}}, \frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}} \right) $$

5. 作用一个控制比特为第 $0$ 个量子比特、 目标比特为第 $1$ 个量子比特、矩阵为 $Z$ 的受控量子门， 即分别将矩阵与下标的第 $0$ 位为 $1$ 且仅第 $1$ 位不同的数据对 $(\alpha_{0 {\color{red}0} {\color{blue}1}},\alpha_{0 {\color{red}1} {\color{blue}1}})$ 和 $(\alpha_{1 {\color{red}0} {\color{blue}1}}, \alpha_{1 {\color{red}1} {\color{blue}1}})$ 相乘， 得到状态：

$$\ket{\psi_5} = \left(\frac{1}{2\sqrt{2}}, \frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, \frac{1}{2\sqrt{2}}, \frac{1}{2\sqrt{2}}, \frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, \frac{1}{2\sqrt{2}} \right) $$

6. 在第 $0$ 个量子比特上作用单比特门 $Z$，得到状态：

$$\ket{\psi_6} = \left(\frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, \frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}} \right) $$

7. 作用一个控制比特为第 $1$ 个量子比特、目标比特为第 $2$ 个量子比特、矩阵为 $Z$ 的受控量子门， 即分别将矩阵与数据对 $(\alpha_{ {\color{red}0} {\color{blue}1}0}, \alpha_{ {\color{red}1} {\color{blue}1}0})$ 和 $(\alpha_{ {\color{red}0} {\color{blue}1}1}, \alpha_{ {\color{red}1} {\color{blue}1}1})$ 相乘， 得到最终状态：

$$\ket{\psi_7} = \left(\frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, \frac{1}{2\sqrt{2}}, -\frac{1}{2\sqrt{2}}, \frac{1}{2\sqrt{2}}, \frac{1}{2\sqrt{2}} \right) $$

任务一（子任务 1，30 分）：根据上述定义，从初态

$$\alpha_i=\left\{ \begin{aligned} 1 &\ & i = 0 \\ 0 &\ & i \ne 0 \\ \end{aligned} \right. \ \ \ \ 0 \le i \le 2^n-1 $$

开始实现 $n$ 个量子比特的量子状态上单比特门和双比特受控量子门的模拟。

你或许已经发现，对于作用在类似 $(1,0,0,0 \dots)$ 的初始状态上的一系列量子门，若其作用的量子比特编号都小于$x$，则仅需要更新状态的前$2^x$个位置上的数据，并保持剩余位置上的数据取值为零不变。

更进一步，在保持每个量子比特上的量子门都按原来顺序执行的前提下，可以对量子门的执行顺序进行调换，以达到更少的运算次数。 图 1 (1) 绘制了上述示例中的量子电路，其每一行代表一个量子比特，横线上的方框代表要在这个比特上执行的量子门，黑色圆圈对应于受控量子门的控制比特。分别考虑每个量子比特的运算顺序，发现该图的依赖有且仅有 $(1 \rightarrow 5 \rightarrow 6)$、$(2 \rightarrow 3 \rightarrow 5 \rightarrow 7)$、$(4 \rightarrow 7)$，其中 $(a \rightarrow b)$ 表示量子门 $a$ 必须在量子门 $b$ 之前执行。因此，可以将示例中量子门的执行顺序调换为如图 1 (2) 所示的 $(1,2,3,5,4,6,7)$ ，以将需要更新的值的数量从 $2+4+4+8+8+8+8=42$ 降低至 $2+4+4+4+8+8+8=38$。

除此之外，还可以对量子比特进行重新编号，以使量子门作用的最大量子比特编号的增长尽可能慢。如图 1 (3) 所示，将量子比特 $\{0,1,2\}$ 重编号为 $\{1,0,2\}$后，需要更新的值的数量可进一步减少至 $2+2+4+4+4+8+8=32$。

一种基于贪心算法的重编号策略为：进行 $n$ 轮循环，第 $i$ 轮循环挑选出一个量子比特 $q_i$，使得在满足电路的依赖条件的前提下，可直接作用在量子比特集合$\{q_1, q_2, \dots, q_{i}\}$上的门（下文简称为“可执行门”）的数量最大。例如，对图 1 (1) 所示电路进行分析的过程为：

• 第 $1$ 轮循环：在分析开始时，作用在第 $0$ 个量子比特上的可执行门只有量子门 $1$。量子门 $\{2, 3, 4, 5, 7\}$ 违背了“仅作用在量子比特 $0$ 上”的限制，而尽管量子门 $6$ 仅作用在第 $0$ 个量子比特上，但根据电路的依赖条件，它必须在不可执行的量子门 $5$ 之后执行，因此也不可执行。同理，第 $1$ 个量子比特对应的可执行门集合为 $\{2, 3\}$，第 $2$ 个量子比特对应的可执行门集合为 $\{4\}$。因此，本轮选取 $q_1=1$。
• 第 $2$ 轮循环：在 $q_1=1$的前提下，若再选取 $q_2=0$，则可执行门为 $\{1,2,3,5,6\}$；若再选取 $q_2=2$，则可执行门为 $\{2, 3, 4\}$，因此选取 $q_2=0$。
• 第三轮循环：选取 $q_3=2$，此时可执行所有门。

此贪心算法无法保证求出的解是最优的，但在大部分情况下可以获得比较好的解。

任务二（27 分）：实现上述的优化（减少更新数值的数量）。该任务分为三个子任务，子任务 2（5 分）在仅实现部分位置更新后即可通过，子任务 3（10 分）还需要实现量子门的顺序调换，子任务 4（12 分）需要在子任务 3 的基础上进一步实现量子比特的重新编号。

虽然上述优化可以在一定程度上减小运算量，但是最坏时间复杂度依旧是 $O(2^n\times g)$，其中 $n$ 为量子比特数量， $g$ 为量子门的数量。对于某些特殊电路，可以专门设计模拟算法以加快运算。

例如，图 2 (1) 中的量子电路可以被直接切分由为虚线分隔的两部分，因此可以从初态 $(1,0,0,0)$ 开始分别对上下两电路进行模拟。假设量子门 $\{1,2,3,4\}$ 的表示矩阵为 $H$，量子门 $\{5,6,8\}$ 的表示矩阵为 $Z$，量子门 $7$ 的表示矩阵为 $X$，则上半部分的两个量子比特的模拟结果为 $\ket{\psi}=(\frac12, \frac12, -\frac12, \frac12)$，下半部分的两个量子比特的模拟结果为 $\ket{\phi}=(\frac12, \frac12, \frac12, \frac12)$。得到两个子量子状态后，可进一步求出这四个量子比特组成的完整量子状态：对于位置 $\overline{b_3b_2b_1b_0}, b_{0\dots3} \in \{0,1\}$，有 $\ket{\alpha}[\overline{b_3b_2b_1b_0}]=\ket{\psi}[\overline{b_1b_0}]\times\ket{\phi}[\overline{b_3b_2}]$。例如状态的第 $14=\overline{1110}$ 个位置（即低位为 $\overline{10}=2$，高位为 $\overline{11}=3$）的取值为 $\ket{\alpha}[14]=\ket{\psi}[2]\times \ket{\phi}[3] = -\frac14$。

从量子计算视角看，可将量子比特直接切分的电路并不能充分发挥其计算能力。一种更复杂的电路如图 2 (2) 所示，其中的量子电路仍旧被切分为虚线分隔的两部分，但两部分之间有较少的受控量子门相连。为处理这类电路，我们可以用和模拟图 2 (1) 中的电路相似的方法分别单独模拟上下两个电路，并特殊处理跨过两部分的量子门。

对图 2 (2) 中的电路，假设量子门 $\{1,2,3,4\}$ 的表示矩阵为 $H$，量子门 $\{5,6,7,9\}$ 的表示矩阵为 $Z$，量子门 $8$ 的表示矩阵为 $X$。则可以按如下步骤模拟该电路：

1. 从初态 $\ket{\psi_0}=\{1,0,0,0\}$ 开始，在第 $0$、$1$ 个量子比特组成的子状态中模拟量子门 $1$、$2$、$5$，得到状态 $\ket{\psi_1}=\{\frac12, \frac12, \frac12, -\frac12\}$；从初态 $\ket{\phi_0}=\{1,0,0,0\}$ 开始，在第 $2$、$3$ 个量子比特组成的子状态中模拟量子门 $3$、$4$、$6$，得到状态 $\ket{\phi_1}=\{\frac12, \frac12, \frac12, -\frac12\}$。

2. 对于量子门 $7$ 这类跨上下两部分量子比特的受控量子门，需要根据上一步得到的量子状态 $\{\ket{\psi_1, \phi_1}\}$ 中控制比特的情况，分别计算控制比特处于状态 $\ket{0}$ 的量子状态通过此受控量子门后的量子状态 $\{ \ket{\psi_2^0}, \ket{\phi_2^0} \}$ 和控制比特处于状态 $\ket{1}$ 的量子状态通过此受控量子门后的量子状态 $\{ \ket{\psi_2^1}, \ket{\phi_2^1} \}$：

   • 处理控制比特所在的子状态 $\ket{\psi_1}$。将其分裂为下标第 $c$（控制比特）位取 0 的状态和取 1 的状态，并将剩余位补零即可：
   $$\ket{\psi_2^0}[i]= \begin{cases} \ket{\psi_1}[i]& \text{i 的第 c 位为 0}\\ 0 & \text{i 的第 c 位为 1} \end{cases} \quad\text{且}\quad \ket{\psi_2^1}[i]= \begin{cases} 0 & \text{i 的第 c 位为 0}\\ \ket{\psi_1}[i] & \text{i 的第 c 位为 1} \end{cases} $$

   其中 $i \in \{0, 1, \dots, 2^{\frac n2}\}$。 具体到本例子，即 $\ket{\psi_2^0}=\{\frac12, \frac12, 0, 0\}$ 和 $\ket{\psi_2^1}=\{0, 0, \frac12, -\frac12\}$ 分别表示第 $1$ 个量子比特取 $0$ 和取 $1$ 时第 $0$、$1$ 个量子比特组成的子状态。

   • 处理目标比特所在的子状态 $\ket{\phi_1}$。根据受控量子门的定义可知，受控量子门相当于在下标的第 $c$ 位取 $1$ 时执行该量子门，在下标的第 $c$ 位取 $0$ 时跳过该量子门。因此，处理方式为将状态 $\ket{\phi_2^0}$ 置为状态 $\ket{\phi_1}$，将状态 $\ket{\phi_2^1}$ 置为在状态 $\ket{\phi_1}$ 的第 $t$ （目标比特）个量子比特上作用与该量子门对应的酉矩阵 $U$ 相同的单比特门后得到的状态。 具体到本例子中，下半部分的第 $2$、$3$ 个量子比特更新后的状态分别为跳过该量子门的状态 $\ket{\phi_2^0}=\{\frac12, \frac12, \frac12, -\frac12\}$ 和作用该量子门的状态 $\ket{\phi_2^1}=\{\frac12, -\frac12, \frac12, \frac12\}$。

3. 对状态 $\ket{\psi_2^0}$、$\ket{\psi_2^1}$ 分别作用量子门 8，得到 $\ket{\psi_3^0}=\{\frac12, 0, 0, \frac12 \}$ 和 $\ket{\psi_3^1}=\{0, -\frac12, \frac12\, 0\}$。对状态 $\ket{\phi_2^0}$、$\ket{\phi_2^1}$ 分别作用量子门 $9$，得到 $\ket{\phi_3^0}=\{\frac12, \frac12, \frac12, \frac12\}$ 和 $\ket{\phi_3^1}=\{\frac12, -\frac12, \frac12, -\frac12\}$。

4. 若电路中存在 $2$ 个跨上下两部分量子比特的受控量子门，可按第 2 步所述方法对 $\{\ket{\psi_2^0}, \ket{\phi_2^0}\}$ 和 $\{\ket{\psi_2^1}, \ket{\phi_2^1}\}$ 分别进行分离操作，得到 $\{\ket{\psi^{00}}, \ket{\phi^{00}}\}$、 $\{\ket{\psi^{01}}, \ket{\phi^{01}}\}$、 $\{\ket{\psi^{10}}, \ket{\phi^{10}}\}$ 和 $\{\ket{\psi^{11}}, \ket{\phi^{11}}\}$。如果有更多跨两部分的量子门，也可以进行类似的处理：设共有 $g_c$ 个跨上下两部分的量子门，则应计算出 $2^{g_c}$ 个状态对 $\{\ket{\psi^i},\ket{\phi^i}\}, i \in \{ 0, 1, \dots, 2^{g_c}-1\}$。

5. 状态的合并：设 $\mathrm{low}$、$\mathrm{high}$ 分别表示状态的第 $p$ 个位置对应的低 $\frac n2$ 位和高 $\frac n2$ 位，则该位置的实际取值 $\displaystyle\alpha_p=\sum_{i=0}^{2^{g_c}-1} \ket{\psi^{i}}[\mathrm{low}] \times \ket{\phi^{i}}[\mathrm{high}]$。例如，第 $11=\overline{1011}$ 个数据（即低位为 $\overline{11}=3$，高位为 $\overline{10}=2$）的取值为 $\ket{\psi^0}[3]\times \ket{\phi^0}[2] + \ket{\psi^1}[3]\times \ket{\phi^1}[2] = \frac14$。

任务三（子任务 5，20 分）：实现上述基于电路切分的优化，以模拟可分为连接较少的两部分的量子电路。切分后的两个子电路分别包含量子比特$\{q,0\le q \le \frac n2-1\}$和量子比特$\{q,\frac n2\le q \le n-1\}$（$n$ 为偶数）。

在进行“基于切分的优化”时，上下两部分状态的模拟均可使用任务二中描述的优化，以进一步提升性能。

任务四（23 分）：实现上述混合优化。与任务二类似，该任务也分为三个子任务。子任务 6（3 分）仅需要在上下两部分电路中实现部分位置更新，子任务 7（8 分）需要分别对上下两部分电路进行量子门的顺序调换，子任务 8（12 分）需要分别在上下两部分电路内部进行量子比特的重新编号（仍保证上下两部分电路分别包含量子比特$\{q,0\le q \le \frac n2-1\}$和量子比特$\{q,\frac n2\le q \le n-1\}$）。

输入格式

从标准输入读入数据。

第一行四个整数 $n,g,q,s$，表示需要模拟有 $n$ 个量子比特的电路，电路中共有 $g$ 个量子门，需要查询模拟完成后 $q$ 个位置的状态取值，此测例属于子任务 $s$。

之后 $g$ 行，每行表示一个量子门。量子门输入格式分为两种：

• $\texttt{s}$ $t$ $r_{00}$ $i_{00}$ $r_{01}$ $i_{01}$ $r_{10}$ $i_{10}$ $r_{11}$ $i_{11}$：表示作用在量子比特 $t$ 上的单比特门；
• $\texttt{c}$ $a$ $t$ $r_{00}$ $i_{00}$ $r_{01}$ $i_{01}$ $r_{10}$ $i_{10}$ $r_{11}$ $i_{11}$：表示控制比特为 $a$、目标比特为 $t$ （$a\neq t$）的双比特受控量子门。

每一行的数字之间用空格分隔。$a$、$t$ 都是 $0$ 到 $n-1$ 的整数，后面均为浮点数。两种情况下，对应门的表示矩阵均为

$$U = \left[ \begin{matrix} r_{00}+i_{00}\mathbf{j} & r_{01}+i_{01}\mathbf{j} \\ r_{10}+i_{10}\mathbf{j} & r_{11}+i_{11}\mathbf{j} \end{matrix} \right] $$

其中 $x+y\mathbf{j}$ 表示实部为 $x$、虚部为 $y$ 的复数。

输入顺序即为 $g$ 个量子门的默认执行顺序，选手亦可按题面中介绍的规则对电路中的量子门进行等价变换，以减少完成模拟需要更新的位置的数量。

接下来 $q$ 行，每行一个整数 $p$，表示询问模拟完成后状态向量上位置 $p$ 的值，其中 $p \in \{0, 1, \dots, 2^n - 1\}$。

输出格式

输出到标准输出。

输出共有 $q$ 行，每行两个浮点数 $x$、$y$，表示从初态 $\ket{\psi_0} = \{1, 0, 0, \dots, 0\}$ 开始，作用输入中给定的全部量子门后，位置向量上位置 $p$ 的状态的取值 $\alpha_p$的实部和虚部。如果你输出的每个浮点数与参考结果相比，均满足绝对误差不大于 $10^{-10}$ 或相对误差不大于 $10^{-6}$，则该测试点满分，否则不得分。建议使用双精度浮点数并至少输出 $10$ 位有效数字。各种语言中输出 $10$ 位有效数字的做法如下：

• C/C++：printf("%.10lg", ans);（需要引入 stdio.h 或 cstdio 文件）
• Java：System.out.printf("%.10g", ans);
• Python："{:.10g}.format(ans)"

3 7 8 1
s 0 0.707106 0 0.707106 0 0.707106 0 -0.707106 0
s 1 0.707106 0 0.707106 0 0.707106 0 -0.707106 0
s 1 1 0 0 0 0 0 -1 0
s 2 0.707106 0 0.707106 0 0.707106 0 -0.707106 0
c 0 1 1 0 0 0 0 0 -1 0
s 0 1 0 0 0 0 0 -1 0
c 1 2 1 0 0 0 0 0 -1 0
0
1
2
3
4
5
6
7

0.3535522188 0
-0.3535522188 0
-0.3535522188 0
-0.3535522188 0
0.3535522188 0
-0.3535522188 0
0.3535522188 0
0.3535522188 0

样例 1 解释

此电路为题面中图 1 (1) 所示的量子电路。

4 9 16 5
s 0 0.707106 0 0.707106 0 0.707106 0 -0.707106 0
s 1 0.707106 0 0.707106 0 0.707106 0 -0.707106 0
s 2 0.707106 0 0.707106 0 0.707106 0 -0.707106 0
s 3 0.707106 0 0.707106 0 0.707106 0 -0.707106 0
c 0 1 1 0 0 0 0 0 -1 0
c 3 2 1 0 0 0 0 0 -1 0
c 1 2 1 0 0 0 0 0 -1 0
c 0 1 0 0 1 0 1 0 0 0
c 2 3 1 0 0 0 0 0 -1 0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

0.2499988952 0
-0.2499988952 0
0.2499988952 0
0.2499988952 0
0.2499988952 0
0.2499988952 0
-0.2499988952 0
0.2499988952 0
0.2499988952 0
-0.2499988952 0
0.2499988952 0
0.2499988952 0
0.2499988952 0
0.2499988952 0
-0.2499988952 0
0.2499988952 0

样例 2 解释

此电路为题面中图 2 (2) 所示的量子电路。

样例 3

见题目文件区的 3.in 和 3.ans。

样例 3 解释

一个属于子任务 1 的量子电路。

样例 3

见题目文件区的 4.in 和 4.ans。

样例 4 解释

一个属于子任务 5 的量子电路。

子任务

所有数据保证 $0<q\le 10^3$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n\le$	$g\le$	特殊性质
1	30	$20$	$100$	无
2	5		$10^4$	$v\le 10^8$
3	10			门重排后 $v\le 10^8$
4	12			门重排且比特重号后 $v\le 10^8$
5	20	$32$	$500$	$n$ 为偶数，$g_c\le 3$
6	3	$34$	$10^4$	$n$ 为偶数，$g_c\le 3,v\le 10^8$
7	8			$n$ 为偶数，$g_c\le 3$，门重排后 $v\le 10^8$
8	12			$n$ 为偶数，$g_c\le 3$，门重排且比特重号后 $v\le 10^8$

其中 $g_c$ 表示子任务 $5\sim 8$ 中横跨上下两部分电路的门的数量，$v$ 表示完成模拟需要更新的位置的数量。

---

1. 酉矩阵是指满足 $UU^*=U^*U=I$ 的复矩阵，其中 $U^*$ 表示 $U$ 的共轭转置。此性质对于本题没有实际影响。 ↩︎