# 0CTF 2019 Final - Quantum Measure (Crypto, 428)

### Challenge

The unzip password is sha256 of flag in Quantum game.

This challenge has two programs sharing 8 qubits (as q0 ~ q7).

The flag is 4 bytes long (8 hex), each hex can be expressed as the probability of qubit’s outcome.

##### e.g. the flag is “01234567” :
• $q_0 = \frac{0}{16}|1\rangle + \frac{16}{16}|0\rangle$

• $q_1 = \frac{1}{16}|1\rangle + \frac{15}{16}|0\rangle$

• $q_2 = \frac{2}{16}|1\rangle + \frac{14}{16}|0\rangle$

• $q_3 = \frac{3}{16}|1\rangle + \frac{13}{16}|0\rangle$

• $q_4 = \frac{4}{16}|1\rangle + \frac{12}{16}|0\rangle$

• $q_5 = \frac{5}{16}|1\rangle + \frac{11}{16}|0\rangle$

• $q_6 = \frac{6}{16}|1\rangle + \frac{10}{16}|0\rangle$

• $q_7 = \frac{7}{16}|1\rangle + \frac{9}{16}|0\rangle$

##### program1 :
• measure q4 ~ q7 as input.
• Some gates (Swap,Cnot,X gate) will act on q0 ~ q3 (depends on result of q4 ~ q7 measurement).
• the output will be the first four bits in result.
##### program2 :
• measure q0 ~ q3 as input.
• Some gates (Swap,Cnot,X gate) will act on q4 ~ q7 (depends on result of q0 ~ q3 measurement).
• the output will be the last four bits in result.

### Solution

#### 1. Consider the qubits (q4~q7), there are only 16 conditions. Parse the program to 16 subprograms.

Origin Program (here is program1) :

convert into :

#### 2. Consider the qubits (q0~q3), there are also only 16 conditions.

Match those inputs and corresponding outputs

#### 3. Convert to formula.

Assume the probabilty of q0 ~ q7 outcome $1$ is, a,b,c,d,e,f,g,h

If the measurment of q4 ~ q7 is $|0000\rangle$ (this probability is $(1-e)(1-f)(1-g)(1-h)$ ),

and the probability of first four bits in result become $|1000\rangle$ will equal to the probability of q0 ~ q3 getting $|0000\rangle$ (Here, the probability is $(1-a)(1-b)(1-c)(1-d)$),

$\Rightarrow$ The probability of output $|1000\rangle$ will be $(1-e)(1-f)(1-g)(1-h) * (1-a)(1-b)(1-c)(1-d)$

Consider all possible in q4 ~ q7

The probability of output $p0 : |0000\rangle$ will be the sum of below :

• The probability of q0~q3 = $|1000\rangle$ with q4 ~ q7 = $|0000\rangle$
• The probability of q0~q3 = $|1000\rangle$ with q4 ~ q7 = $|0001\rangle$
• The probability of q0~q3 = $|0000\rangle$ with q4 ~ q7 = $|0010\rangle$
• The probability of q0~q3 = $|0000\rangle$ with q4 ~ q7 = $|0011\rangle$
• The probability of q0~q3 = $|1000\rangle$ with q4 ~ q7 = $|0100\rangle$
• The probability of q0~q3 = $|1000\rangle$ with q4 ~ q7 = $|0101\rangle$
• The probability of q0~q3 = $|0000\rangle$ with q4 ~ q7 = $|0110\rangle$
• The probability of q0~q3 = $|0000\rangle$ with q4 ~ q7 = $|0111\rangle$
• The probability of q0~q3 = $|1100\rangle$ with q4 ~ q7 = $|1000\rangle$
• The probability of q0~q3 = $|1100\rangle$ with q4 ~ q7 = $|1001\rangle$
• The probability of q0~q3 = $|1000\rangle$ with q4 ~ q7 = $|1010\rangle$
• The probability of q0~q3 = $|1000\rangle$ with q4 ~ q7 = $|1011\rangle$
• The probability of q0~q3 = $|1100\rangle$ with q4 ~ q7 = $|1100\rangle$
• The probability of q0~q3 = $|1100\rangle$ with q4 ~ q7 = $|1101\rangle$
• The probability of q0~q3 = $|1000\rangle$ with q4 ~ q7 = $|1110\rangle$
• The probability of q0~q3 = $|1000\rangle$ with q4 ~ q7 = $|1111\rangle$

In the same way, we can write down all outputs’ probability to formula.

#### 4. Brute force to get flag.

the smallest diff with the file result will be the flag.