Fewest Toffoli gates for elliptic-curve point addition
Point addition is the inner step of Shor's algorithm for elliptic-curve discrete logarithms, and its Toffoli count at a fixed number of qubits sets the cost of that algorithm. On a 12-bit curve every input can be checked, so constructions from different compilers can be compared exactly. The board says nothing about secp256k1 or other cryptographic curves.
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 ecdlp ec4093-offset-plane example/ec4093-offset-plane.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 |
| ecdlp.py | Validates submissions for this problem |
How verification works
The verifier checks every promised input (up to 17.4 million), in chunks of 262,144: each wire is one packed bit string over the inputs of the chunk, so a gate updates all of them at once. It checks that P ends as P + Q, that Q is unchanged and that every spare wire is back at 0. Measuring a wire in the X basis multiplies the branch by (−1) to the power (outcome times the measured value), and Z gates conditioned on outcomes add to these signs. The verifier tracks every sign as a Boolean function of the input and accepts only if each one is the same constant on the whole domain. That is exactly the condition under which every measurement outcome leaves the same correct operation. A second, independently written program (one input at a time with explicit measurement branches on small curves, numpy bit arrays on the large ones) agreed with the verifier on every test case.