Fewest Toffoli gates for adding a constant
Adding a known constant modulo 2^n is the inner step of modular exponentiation in Shor's algorithm and of many other arithmetic circuits, and spare qubits are expensive, so the Toffoli count at a fixed number of spare qubits decides the cost.
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 constadd add20-d6b5b-a3 example/add20-d6b5b-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 |
| constadd.py | Validates submissions for this problem |
How verification works
The verifier stores the value of every wire on all 2^n inputs (2^(n+1) with the control) as one packed bit string, so one gate updates every input at once. It checks that the data wires end at x + c mod 2^n (x + q·c on controlled instances, where q is the control bit), that the control is unchanged and that every spare wire is back at 0. Measuring a wire in the X basis removes it and multiplies the state by (-1) to the power (outcome times the measured value); a Z gate conditioned on outcomes adds to these signs. The verifier tracks every sign as a Boolean function of the input and accepts only if each one is constant. That is exactly the condition under which every possible measurement outcome leaves the same correct operation on the register. A second, independently written program checks small cases by following every measurement outcome explicitly.