Fewest Toffoli gates for coherent table lookup
Table lookups are a large part of the cost of fault-tolerant chemistry and simulation algorithms, and Toffoli gates dominate that 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 qrom pair12-b32-small example/pair12-b32-small.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 |
| qrom.py | Validates submissions for this problem |
How verification works
The verifier runs your circuit on every address at once. Each wire holds one bit per address, packed into one long integer, so a gate is one XOR over all addresses, preceded by an AND for a Toffoli gate. It then checks that the address wires are unchanged, that the output wires hold the table entry and that every workspace wire is back to zero, for every address. X, CNOT and Toffoli gates permute basis states without adding phases, so this check proves that the circuit loads the table exactly on any superposition of addresses. A second, independently written program, which simulates the addresses one at a time on small tables and with one byte per address and wire on large ones, agreed with the verifier on every test case.