quant? — UMDCTF

Description

quant? it's all math anyways. I heard predicting the future has been in vogue recently, so I hid the flag in a black-box oracle.

Connect to a "qisket" (misspelled qiskit) oracle service at nc challs.umdctf.io 30309. The service accepts OpenQASM-like circuit descriptions with:

• 16 input qubits q[0] through q[15]
• 1 ancilla qubit q[16]
• 16-bit classical register c[0] through c[15]

Supported gates: h, x, z, mcx, oracle, diffuse, measure

Limits: 250 oracle calls, 200000 bytes input, 512 shots.

Analysis

This is a classic Grover's Algorithm challenge. The service has a black-box oracle that marks exactly one 16-bit state. The goal is to find this marked state using quantum amplitude amplification.

Key Parameters

• Search space: N = 2^16 = 65536 states
• Marked states: M = 1
• Optimal iterations: k = floor(π/4 × √(N/M)) ≈ 201

The optimal number of Grover iterations can be computed precisely:

import math

def grover_iterations(n_qubits: int) -> int:
    theta = math.asin(1 / math.sqrt(1 << n_qubits))
    return max(range(250), key=lambda k: math.sin((2 * k + 1) * theta) ** 2)

# For 16 qubits: returns 200

Circuit Structure

Standard Grover's algorithm requires:

1. Initialization: Put all input qubits in superposition with Hadamard gates
2. Ancilla preparation: Prepare ancilla in |-> state for phase kickback
3. Grover iterations: Repeat (oracle + diffusion) ~200 times
4. Measurement: Measure all input qubits

Solution

#!/usr/bin/python3
import math
import os
import re
import socket
import subprocess

HOST = "challs.umdctf.io"
PORT = 30309
N = 16
CACHE = "/tmp/umdctf_pow"
TOKEN_RE = re.compile(rb"sh -s ([^\n]+)\nsolution: ")
BANNER_END = b"measure every input qubit as q[i] -> c[i]\n\n"
FLAG_RE = re.compile(r"UMDCTF\{[^\n}]*\}")

ORACLE_ARGS = ",".join(f"q[{i}]" for i in range(17))
DIFFUSE_ARGS = ",".join(f"q[{i}]" for i in range(16))

...