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 bools, 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}