QArena · Fault-tolerant arithmetic
Submit
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.
Instance files
Each JSON file defines one instance of this problem. Instances differ by prime, kind of addend and input domain. The verifier reads the same files, and the verifier bundle contains all of them together with an accepted example.
| File | Instance | Parameters | Size |
|---|---|---|---|
| ec11-offset.json | p = 11, classical Q | Q = (2, 2); 8 curve points; debug instance | 0.4 KB |
| ec11-quantum.json | p = 11, quantum Q | 92 pairs of curve points; debug instance | 0.4 KB |
| ec11-offset-plane.json | p = 11, classical Q, plane | Q = (2, 2); 99 pairs (x, y); debug instance | 0.3 KB |
| ec251-offset.json | p = 251, classical Q | Q = (0, 42); 249 curve points; debug instance | 2.6 KB |
| ec251-quantum.json | p = 251, quantum Q | 62,252 pairs of curve points; debug instance | 2.6 KB |
| ec251-offset-plane.json | p = 251, classical Q, plane | Q = (0, 42); 62,500 pairs (x, y); debug instance | 0.3 KB |
| ec4093-offset.json | p = 4093, classical Q | Q = (5, 65); 4,167 curve points; tables of the group allowed | 47.1 KB |
| ec4093-quantum.json | p = 4093, quantum Q | 17,376,390 pairs of curve points; Q read-only | 47.1 KB |
| ec4093-offset-plane.json | p = 4093, classical Q, plane | Q = (5, 65); 16,744,463 pairs (x, y), on the curve or not | 0.3 KB |