Fewest T gates for a multi-controlled Z with measurements
A controlled NOT with many controls appears in table lookups, comparisons and oracles, and each T gate costs a magic state. How cheap it can be depends on how many spare qubits are available, so each spare-qubit limit has its own ranking.
Verifier
The verifier checks your file and computes its score. The server runs the same code on every submission.
Download the bundle, extract it and run these commands from its folder (the one holding verifiers/). The bundle
includes an accepted example file.
python3 -m pip install -r requirements.txt python3 -I verifiers/run_one.py mcz mcz6-a3 example/mcz6-a3.json
The verifier prints one line of JSON with a status: accepted with the score, rejected with the reason,
or error if verification could not finish.
Files
| File | Role |
|---|---|
| run_one.py | Runs the verifier |
| common.py | Shared helpers |
| mcz.py | Validates submissions for this problem |
How verification works
The verifier follows each of the 2^N basis inputs through every combination of measurement outcomes (at most 16), with exact integer arithmetic in the ring generated by e^{iπ/4}. On every outcome, including those of probability zero, the data must end in the target gate times one number that does not depend on the input, and every live spare wire must be |0⟩. The squared magnitudes of those numbers must add up to exactly 1. The T count is read off the outcomes that can occur. A second program with a different method (dense matrices over exact numbers, with literal gate matrices) agreed with the verifier on random and adversarial circuits.