The Future of Programming - 题目

This problem is a submit-answer problem.

Background

In 2042, a computer model moved from theory to reality and achieved large-scale popularity.

You are a candidate in the ION of that year, and you need to implement 20 tasks using this model...

Then you wake up from your dream, only to find yourself in the National Training Team mutual testing, and you need to use this model to implement 20 tasks...

Description

This problem is a submit-answer problem.

Please refer to Appendix 1 below to understand the computational principles of this model. You need to complete 20 tasks on this model, as specified in the task requirements.

Output

To avoid issues such as excessive execution time caused by interaction, your program recording data during runtime, or probabilistic factors affecting results during randomization, this problem uses a submit-answer format. Note that this problem is case-sensitive.

The task requirements specify how many code blocks each point has. Each code block must start with Begin and end with End. Within a code block, only sequential and branching structures are allowed.

Available bits are numbered starting from 0. If performing an operation on a single bit without an angle parameter, you can use <op> <id> <controller ids>, where <op> is one of H, T, X, Y, or Z, <id> is the index of the bit being operated on, and <controller ids> stores whether a bit is a control bit in binary form. Specifically, the $i$-th bit is a control bit if and only if the $2^i$ bit in the binary representation of <controller ids> is 1. Note that the index must not exceed the range, the highest bit of <controller ids> must not exceed the range, and the bit being operated on cannot be a control bit. If there is an angle parameter, you can use <op> <id> <theta> <controller ids>, where <op> is one of Rx, Ry, or Rz, <theta> is the angle parameter in radians, and other parameters are the same as above. To swap two bits, use SWAP <id1> <id2> <controller ids> to swap the bits with indices <id1> and <id2>. Note that these two bits cannot be the same.

To read the value of a bit, you can use IfM <id> <statements> [Else <statements>] Endif or M <id>, where <id> is the index. IfM is a branching structure; if the read result is 1, the statements between IfM and its matching Else (or Endif if no Else exists) are executed. Otherwise, if a matching Else exists, the statements between Else and Endif are executed. If M is used, the result at that moment is recorded and execution continues. Note: M is not allowed within an IfM block.

A code block can have a return value, which can be any value between $-2^{31}$ and $2^{31}-1$, defaulting to 0. You can use Return <ret> to immediately terminate the code block and return ret. You can also use ReturnFull <ret0> <ret1> ... <ret2^k-1>, providing a total of $2^k$ values, where $k$ is the number of M operations performed in the code block from Begin to the current point. If the results of the M operations are $x_0, x_1, \cdots, x_{k-1}$, the value returned will be the one at index $\sum_{i=0}^{k-1} 2^ix_i$ (0-indexed).

Tip: You can modify the provided template.cpp and use quantum::Printer for output (refer to Appendix 2). It needs to be compiled together with quantum.cpp. For example: g++ template.cpp quantum.cpp -o <executable_file> -std=c++11 Running it directly will generate 20 output files. To generate a specific data point, you can use: ./<executable_file> <case_no> [<output_file>] The output for the <case_no>-th data point will be saved to <output_file> (defaulting to quantum<case_no>.out).

Constraints

The number of statements refers to those within a code block, excluding Begin, End, Else, and Endif. For non-relational probabilities, the error must not exceed $10^{-6}$. The required state and the generated state may differ by a factor of $e^{i\theta}$ (a constant multiple) and may have an absolute error of $10^{-6}$ (refer to the implementation of checker.cpp, though typical implementations will not exceed this). If the input is not fixed and a specific output is required, the difference factor $e^{i\theta}$ must be a constant for all inputs.

Tip: The tasks are not necessarily sorted by difficulty.

Examples

Examples 1

1 code block, 1 bit, initial state $|0\rangle$. Implement a random number generator that returns 0 with probability $1/2$ and 1 with probability $1/2$. Constraints: The number of statements in this code block does not exceed 3, IfM is not allowed, and at most 1 M can be used. The reference answer is quantum_sample1.out in the provided files.

Task 1

1 code block, 1 bit, initial state $|0\rangle$. Implement a random number generator that returns 14343375 with probability $14343375/16777216$ and 0 with probability $1-14343375/16777216$. Constraints: The number of statements in this code block does not exceed 3, IfM is not allowed, and at most 1 M can be used.

Task 2

1 code block, 1 bit, initial state $|0\rangle$. Implement a random number generator that returns 1, 2, 3, or 4, each with probability $1/4$. Constraints: The number of statements in this code block does not exceed 5, Rx, Ry, Rz, and IfM are not allowed, and at most 2 Ms can be used.

Task 3

1 code block, 1 bit, initial state $|0\rangle$. Implement a random number generator that returns 1 with probability $10\%$, 2 with $20\%$, 3 with $30\%$, and 4 with $40\%$. Constraints: The number of statements in this code block does not exceed 20, M is not allowed, and at most 3 IfMs can be used.

Task 4

1 code block, 1 bit, initial state $|0\rangle$. Implement a random number generator that returns 1 with probability $10\%$, 2 with $20\%$, 3 with $30\%$, and 4 with $40\%$. Constraints: The number of statements in this code block does not exceed 20, IfM is not allowed, and at most 3 Ms can be used.

Task 5

1 code block, 1 bit, initial state $|0\rangle$. Generate $(\sqrt{0.1}+\sqrt{0.2}i)|0\rangle+(\sqrt{0.3}+\sqrt{0.4}i)|1\rangle$. Constraints: The number of statements in this code block does not exceed 5, IfM and M are not allowed.

Task 6

1 code block, 1 bit, initial state $(|0\rangle+i|1\rangle)/\sqrt2$ or $(|0\rangle-i|1\rangle)/\sqrt2$. If it is $(|0\rangle+i|1\rangle)/\sqrt2$, return 1; otherwise, return 0. Constraints: The number of statements in this code block does not exceed 8, Rx, Ry, and Rz are not allowed, at most 1 M can be used, and at most 1 IfM can be used.

Task 7

Elitzur-Vaidman bomb testing problem. 2 code blocks, 1 bit. Initial state $|0\rangle$. The first code block is executed first, then there are two possibilities: 1. A "bomb" reads the value of this bit; if it is 1, it explodes and execution stops. 2. No operation is performed. Then the second code block is executed, returning 1 or -1, where 1 indicates a "bomb" is definitely present, and -1 indicates uncertainty. Requirements: If there is no "bomb", the probability of returning 1 must not exceed $10^{-6}$; if there is a bomb, the probability of explosion must be less than $60\%$, and the probability of not exploding and returning 1 must be greater than $20\%$. Constraints: The number of statements in the first code block does not exceed 2, IfM and M are not allowed; the number of statements in the second code block does not exceed 5, at most 1 M can be used, and at most 1 IfM can be used.

Task 8

Task 9

1 code block, 2 bits, swap these two bits (i.e., implement SWAP). Constraints: The number of statements in this code block does not exceed 5, SWAP, M, and IfM are not allowed.

Task 10

1 code block, 2 bits, initial state $|00\rangle$, generate $(|10\rangle-|01\rangle)/\sqrt{2}$. Constraints: The number of statements in this code block does not exceed 5, IfM, M, Rx, Ry, and Rz are not allowed.

Task 11

1 code block, 2 bits, initial state $|00\rangle$. Generate $\sqrt{0.1}|00\rangle+\sqrt{0.2}|10\rangle+\sqrt{0.3}|01\rangle+\sqrt{0.4}|11\rangle$. Constraints: The number of statements in this code block does not exceed 5, IfM, M, Rx, Ry, and Rz are not allowed.

Task 12

1 code block, 7 bits, initial state $|0000000\rangle$. Generate $(|1000000\rangle+|0100000\rangle+|0010000\rangle+|0001000\rangle+|0000100\rangle+|0000010\rangle+|0000001\rangle)/\sqrt{7}$. Constraints: The number of statements in this code block does not exceed 15, IfM and M are not allowed.

Task 13

1 code block, 8 bits, initial state $|00000000\rangle$. Generate $(|10000000\rangle+|01000000\rangle+|00100000\rangle+|00010000\rangle+|00001000\rangle+|00000100\rangle+|00000010\rangle+|00000001\rangle)/\sqrt{8}$. Constraints: The number of statements in this code block does not exceed 20, IfM, M, Rx, Ry, and Rz are not allowed.

Task 14

1 code block, 5 bits, initial state $|00000\rangle$. Generate $(|11000\rangle+|10100\rangle+|10010\rangle+|10001\rangle+|01100\rangle+|01010\rangle+|01001\rangle+|00110\rangle+|00101\rangle+|00011\rangle)/\sqrt{10}$. (Contains all states with two 1s.) Constraints: The number of statements in this code block does not exceed 30, IfM and M are not allowed.

Task 15

1 code block, 6 bits, initial state $|000000\rangle$. Generate $(|111000\rangle+|110100\rangle+\cdots+|000111\rangle)/\sqrt{20}$. (Contains all states with three 1s.) Constraints: The number of statements in this code block does not exceed 35, IfM and M are not allowed.

Task 16

1 code block, 4 bits. For a coefficient, if its basis vector has an odd number of 1s in the 0th, 1st, and 2nd positions, flip the 3rd bit (0 becomes 1, 1 becomes 0). That is, change the coefficient of $|x_0x_1x_2x_3\rangle$ to the coefficient of $|x_0x_1x_2(x_3\operatorname{xor} [x_0,x_1,x_2\texttt{ have an odd number of 1s}])\rangle$. Constraints: The number of statements in this code block does not exceed 5, IfM and M are not allowed.

Task 17

1 code block, 5 bits. For a coefficient, if its basis vector has exactly one 1 in the 0th, 1st, 2nd, and 3rd positions, flip the 4th bit (0 becomes 1, 1 becomes 0). That is, change the coefficient of $|x_0x_1x_2x_3x_4\rangle$ to the coefficient of $|x_0x_1x_2x_3(x_4\operatorname{xor} [x_0,x_1,x_2,x_3\texttt{ have exactly one 1}])\rangle$. Constraints: The number of statements in this code block does not exceed 10, IfM and M are not allowed.

Task 18

2 code blocks, 2 bits. Initial state $(|00\rangle-|01\rangle)/\sqrt{2}$. The first code block is executed first, then there are two possibilities: 1. Execute X 1 1, i.e., use the 0th bit as a control bit to perform an operation. 2. No operation is performed. Then the second code block is executed, returning 1 or 0, where 1 indicates X 1 1 was definitely executed, and 0 indicates it was definitely not. Constraints: The number of statements in the first code block does not exceed 2, IfM and M are not allowed; the number of statements in the second code block does not exceed 5, at most 1 M can be used, and at most 1 IfM can be used. Neither code block can use the 1st bit (neither for operations, reading, nor as a control bit).

Task 19

4 code blocks, 3 bits, initial state $|000\rangle$. Execute the 1st code block first, then execute the other three code blocks respectively, implementing three random number generators. The three code blocks return 0 or 1, return an odd number of 1s in total, and the four scenarios are equally probable. Constraints: The number of statements in the 1st code block does not exceed 4, and the number of statements in the other code blocks does not exceed 2. IfM is not allowed in any. The 1st code block cannot use M, and the other code blocks can use at most 1 M. The 2nd code block can only use the 0th bit, the 3rd code block can only use the 1st bit, and the 4th code block can only use the 2nd bit.

Task 20

5 code blocks, 2 bits, initial state $|00\rangle$. Execute the 1st code block first, then execute exactly one of the 2nd or 3rd code blocks to return 0 or 1, and execute exactly one of the 4th or 5th code blocks to return 0 or 1. Requirements: When executing the 2nd and 4th code blocks, the probability of both returning 0 is the same as both returning 1; when executing the 3rd and 5th code blocks, the probabilities of the four outcomes are equal. Constraints: The number of statements in each code block does not exceed 5, and IfM is not allowed in any. The 1st code block cannot use M, and the other code blocks can use at most 1 M. The 2nd and 3rd code blocks can only use the 0th bit, and the 4th and 5th code blocks can only use the 1st bit.

How to Test Your Output

In the terminal, switch to the directory containing the problem files (assuming checker.cpp, testlib.h, and your output files are present), compile checker.cpp using: g++ checker.cpp -o checker -std=c++14 Then use: ./checker <case_no> [<output_file>] to check if output_file (defaulting to quantum<case_no>.out) passes the <case_no>-th test data. For example: ./checker 7 will check if quantum7.out passes the 7th test data. If checking the sample, <case_no> should be -1, and you must specify the output file. This checker also supports the standard testlib.h interaction method: ./checker <input> <output> <answer> where <output> is your output file, the input file <input> should contain a positive integer from 1 to 20 representing the test point number (you can use quantum<case_no>.in from the provided files), and <answer> has no effect on the result. The final evaluation is equivalent to this method.

Additionally, you can run ./checker to check all 20 points. However, this check does not use testlib's input validation, so it might pass here but fail the official test. Generally, as long as the integers in the output do not cause overflow during reading and decimals are written in standard format (not scientific notation, no nan, no inf), it will not cause misjudgment.

Appendix 1: Non-Traditional Computer Model

In this model, if it has $n$ bits, it (can be viewed as) having $2^n$ complex parameters $w_0, w_1, \cdots w_{2^n-1}$ internally, representing a state of the model. For convenience, these $2^n$ parameters can be written as a column vector, and the $i$-th (standard) basis vector of this column vector is usually denoted as $|x_0\cdots x_{n-1}\rangle$, where $i=\sum_{k=0}^{n-1}2^kx_k$.

Operations on a single bit: An operation corresponds to a unitary matrix $U$ (its conjugate transpose is its inverse), where: $$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}.$$

When acting on the $i$-th bit, the state changes $w\to w'$, specifically: $$\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}$$

For swapping, it can be viewed as: $$SWAP_{ij}=\begin{bmatrix}1&0&0&0\\0&0&1&0\\0&1&0&0\\0&0&0&1\end{bmatrix}$$

Regarding control bits: When there are control bits, we only perform operations on the coefficients corresponding to basis vectors where all control bits are 1. The bit being operated on cannot be a control bit. For example, with 2 bits, performing X directly on bit 0 can be viewed as: $$\begin{bmatrix}0&1&0&0\\1&0&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}$$ If the 1st bit is a control bit, the matrix can be viewed as: $$\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}$$

Regarding reading a bit: When reading the $i$-th bit, the probability of the result being 0 is the sum of the squares of the magnitudes of all coefficients where the $i$-th bit is 0, and the probability of the result being 1 is the sum of the squares of the magnitudes of all coefficients where the $i$-th bit is 1. It can be proven that before and after all non-reading operations, the sum of the squares of the magnitudes of all coefficients remains constant at 1 (initially $|0\cdots0\rangle$). If the read result is 0, all coefficients where the $i$-th bit is 1 are set to 0, and the remaining coefficients are multiplied by a constant such that the sum of the squares of the magnitudes of all coefficients remains 1. The same applies if the result is 1.

For example: Initially $|00\rangle$, performing H on the 0th bit yields $(|00\rangle+|10\rangle)/\sqrt{2}$. Then, using the 0th bit as a control bit, performing X on the 1st bit yields $(|00\rangle+|11\rangle)/\sqrt{2}$. Reading the first bit gives 0 with probability $1/2$ (state becomes $|00\rangle$) or 1 with probability $1/2$ (state becomes $|11\rangle$). Reading the 1st bit afterwards will necessarily yield the same result as the first read.

Appendix 2: Provided Files Description

Note: If you need to modify them, it is recommended to back them up first.

checker.cpp is the validator, identical to the one used for final testing.

template.cpp is a template to help you obtain output files. You only need to use the output functionality of ot; you do not need to open files yourself.

examples.cpp contains an example and a sample (a generator that produces 0 or 1 with 50/50 probability). It needs to be compiled with quantum.cpp. For example: g++ examples.cpp quantum.cpp -o examples -std=c++11

quantum.cpp and quantum.h are library files. They contain the simulator Simulator, evaluator Evaluator, and the tool Printer for printing output files, all of which are classes within the namespace quantum, along with a struct complex representing complex numbers. Printer usage: You can initialize it with a file pointer or use set_file(FILE *file) to specify the output file. For all operations mentioned in the output format, you can directly use <object>.<operation_name> with the mentioned parameters; control bits default to 0 (i.e., none). ReturnFull requires passing a std::vector of the correct length. Note that this class does not perform output validity checks. Simulator usage: When creating an object, you must pass the number of bits required (cannot exceed 16, though you can modify maxn yourself). The initial state is $|0\dots0\rangle$, and you can use reset() to return to this state. You can use all bit operations with the same parameter requirements as Printer. M(uint8_t id) reads bit information, returning true for 1 or false for 0, implemented using std::mt19937. M(uint8_t id, bool res) forces the read result to be res and updates the probability of the current state; it returns true if successful, or false otherwise (i.e., if the probability is 0). You can use get_probability() to read the current probability and reset_p() to reset the probability to 1.

QOJ.ac

QOJ

#5172. The Future of Programming