This challenge required us to design a quantum circuit which detects on a two-qubit system whether a measurement is taking place or not, while making sure a certain state never gets measured. As per the challenge description, this can be used to detect an eavesdropper without them noticing.

The challenge server largely consists of implementing all the usual operations on a two-qubit system; those are:

- the identity,
- the (controlled) Hadamard gate,
- (controlled) Pauli’s X-, Y-, and Z-gate,
- (controlled) arbitrary phase rotation,
- and measurement.

In the beginning, the server sets up an array of `0x70`

`bool`

s, which
are supposed to describe bombs on a field. (Hence the name *minesweeper*.)
Those only difference those “bombs” make is that we are given access to
an operator that performs a measurement if there is a bomb, and does
nothing if there isn’t.
We are then allowed to execute a sequence of almost arbitrary circuits,
with the only restriction that we must never measure a $1$ on any of the
two qubits.
After each circuit sent to the server, we are given a measurement of the
final state (which *may* contain $1$s).
In the end, ~~it doesn’t even matter~~
we have to send the exact indices with bombs to the server to get the flag.

The way we solved this is based on the observation that measurement performs a “projection” on the state matrix, in the sense that with high probability, a state with very low probability has probability zero afterwards, and its weight gets reallocated to the most probable state. For example, if a 1-qubit system is in the state $\sqrt{1-\varepsilon}\cdot\lvert0\rangle+\sqrt\varepsilon\cdot\lvert1\rangle$ with $\varepsilon$ very small, it will most likely be in the pure state $\lvert0\rangle$ afterwards.

Since the four basis states are assigned numbers in the source code, we fix the following mapping:

- state
`0`

is $\lvert00\rangle$; - state
`1`

is $\lvert10\rangle$; - state
`2`

is $\lvert01\rangle$; - state
`3`

is $\lvert11\rangle$.

Let $\mathcal O$ be the operator that is either a measurement of the second qubit (if “there is a bomb”), or the identity (if there isn’t).

One of the core ingredients to our solution is the phase rotation gate
$R_\varphi$:
We use this to repeatedly introduce a small distortion into the state
and apply the “oracle” operator $\mathcal O$ afterwards.
Then *either* the small error is removed by the measurement
(or, with very small probability, the whole thing blows up),
*or* it accumulates to a large distortion over the rounds.

The basic primitive we use is the following operator: \[ \Gamma:=\mathcal O\cdot H\cdot R_\varphi\cdot H \] for a very small angle $\varphi$, such as $0.001$ radians.

Let’s trace the effect of this operator on a state ($\lvert10\rangle$ and $\lvert11\rangle$ are irrelevant for our purposes): \begin{align*} &\alpha\cdot\lvert00\rangle + \beta\cdot\lvert01\rangle \\ \overset H\longmapsto\qquad &\frac{\alpha+\beta}{\sqrt2}\cdot\lvert00\rangle + \frac{\alpha-\beta}{\sqrt2}\cdot\lvert01\rangle \\ \overset{R_\varphi}\longmapsto\qquad &\frac{\alpha+\beta}{\sqrt2}\cdot\lvert00\rangle + \frac{\alpha-\beta}{\sqrt2}e^{i\varphi}\cdot\lvert01\rangle \\ \overset H\longmapsto\qquad &\frac{(1+e^{i\varphi})\alpha+(1-e^{i\varphi})\beta}2\cdot\lvert00\rangle+\frac{(1-e^{i\varphi})\alpha+(1+e^{i\varphi})\beta}2\cdot\lvert01\rangle \\ \overset{\mathcal O}\longmapsto\qquad &\begin{cases} \gamma\cdot\lvert00\rangle & \text{if bomb, with overwhelming probability} \\\delta\cdot\lvert01\rangle & \text{if bomb, with negligible probability} \\\frac{(1+e^{i\varphi})\alpha+(1-e^{i\varphi})\beta}2\cdot\lvert00\rangle+\frac{(1-e^{i\varphi})\alpha+(1+e^{i\varphi})\beta}2\cdot\lvert01\rangle & \text{if no bomb} \text, \end{cases} \end{align*} where $\gamma$ and $\delta$ are complex numbers of norm $1$.

This means:

- If there is a bomb, and if we start in the pure state $\lvert00\rangle$, it is almost certain that we’re still in (a phase-shifted version of) that state after iterating $\Gamma$ a few times. (At some point, it becomes too likely that we hit the second case and we’re dead, but in practice one can balance the reliability and the danger of explosion well enough.)
- If there is
*no*bomb, we see the system (slowly) converge to $\lvert01\rangle$ with repeated applications of $\Gamma$. Note we do not care about the probability of hitting $\lvert01\rangle$ here since $\mathcal O$ does not perform a measurement, and the final measurement does not blow up if it hits $\lvert01\rangle$.

This means we can distinguish the two possible cases by repeatedly
applying $\Gamma$ to the initial state $\lvert00\rangle$ and
checking (via the final measurement given to us by the server)
whether we are *definitely* in the “no bomb” case (if we get
$\lvert01\rangle$), or *perhaps* in the “bomb” case (if we get
$\lvert00\rangle$). Since the latter case has some probability
of error, we then iterate the same check a few more times.
If we always get $\lvert00\rangle$, we’re most likely in the “bomb”
case.
Of course, if we happen to measure $\lvert01\rangle$ when applying
$\mathcal O$, we are dead and have to start over, but by tweaking
the angle $\varphi$ and the iteration counts, we could reduce that
probability such that the solver works something like $60\%$ of the
time in practice. (And yes, I *did* run it 100 times to get that
number!)

Here is the solver script:

```
#!/usr/bin/env python3
import socket, struct
host, port = '54.202.194.91', 65535
G_H = 4 # Hadamard gate
G_P = 6 # Rotate phase by an angle specified in radians
def measure_or_not(num, wire):
assert num < 0x70
return bytes([num | wire * 0x80])
def gate(kind, wire, ctrl, param = None):
b = 0x70 | 0x80 * wire | 0x08 * ctrl | kind
return bytes([b]) if param is None else struct.pack('<Bd', b, param)
its, phi = 1000, .001
def detect(num, sock):
gates = []
for _ in range(its):
gates.append(gate(G_H, 1, 0))
gates.append(gate(G_P, 1, 0, phi))
gates.append(gate(G_H, 1, 0))
gates.append(measure_or_not(num, 1))
sock.sendall(struct.pack('!H', len(gates)) + b''.join(gates))
return sock.recv(1)[0] # measure_final
sock = socket.socket()
sock.connect((host, port))
reps = 50
is_bomb = [False] * 0x70
for field in range(112):
for cur_rep in range(reps):
if detect(field, sock):
print('{:3d} is clear'.format(field))
break
else:
print('{:3d} is bomb'.format(field))
is_bomb[field] = True
sock.send(b'\0\0') # no more queries
packed = sum(b << i for i, b in enumerate(reversed(is_bomb)))
packed = int.to_bytes(packed, 14, 'big')
print('bombs @ {}'.format(packed))
sock.sendall(packed)
sock.shutdown(socket.SHUT_WR)
print('--> {}'.format(sock.recv(0x100).decode().strip()))
```

Note the constants `phi`

, `its`

and `reps`

were initially chosen
pretty arbitrarily and tweaked whenever the probability of error
or explosion turned out too large.
I’m confident one could obtain much better results using controlled
quantum gates (NB: we only used one of the qubits!) and by
computing/minimizing the failure probabilities, but the above is
simple and worked well enough to get the flag:

`$ ./pwn.py 0 is clear 1 is clear 2 is bomb 3 is clear 4 is clear 5 is clear 6 is clear 7 is bomb 8 is clear 9 is bomb 10 is bomb 11 is bomb 12 is bomb 13 is clear 14 is bomb 15 is clear 16 is clear 17 is bomb 18 is bomb 19 is clear 20 is clear 21 is clear 22 is bomb 23 is bomb 24 is bomb 25 is clear 26 is clear 27 is clear 28 is bomb 29 is bomb 30 is clear 31 is bomb 32 is clear 33 is bomb 34 is bomb 35 is bomb 36 is bomb 37 is bomb 38 is clear 39 is clear 40 is bomb 41 is bomb 42 is bomb 43 is clear 44 is bomb 45 is clear 46 is clear 47 is bomb 48 is bomb 49 is bomb 50 is clear 51 is bomb 52 is bomb 53 is clear 54 is bomb 55 is clear 56 is bomb 57 is bomb 58 is clear 59 is bomb 60 is bomb 61 is bomb 62 is bomb 63 is bomb 64 is bomb 65 is bomb 66 is bomb 67 is bomb 68 is clear 69 is bomb 70 is clear 71 is bomb 72 is bomb 73 is bomb 74 is clear 75 is clear 76 is bomb 77 is clear 78 is clear 79 is clear 80 is bomb 81 is clear 82 is clear 83 is bomb 84 is clear 85 is bomb 86 is bomb 87 is clear 88 is bomb 89 is clear 90 is clear 91 is bomb 92 is bomb 93 is clear 94 is bomb 95 is bomb 96 is clear 97 is bomb 98 is bomb 99 is clear 100 is bomb 101 is bomb 102 is clear 103 is bomb 104 is bomb 105 is clear 106 is clear 107 is clear 108 is clear 109 is clear 110 is bomb 111 is bomb bombs @ b'!zc\x8d|\xe9\xda\xdf\xf5\xc8\x96\x9bm\x83' --> FLAG{Maybe they exploded in parallel universes}`