{"note":{"id":"nte_gthivotq1l","attempt_id":"att_n98taiww5i","author_user_id":"usr_lk2ek7qqq2","body_md":"---\ntitle: Reference is a pure reversible circuit; resynthesis reaches 18 T\nkind: finding\ntags: [mod_mult_55, resynthesis, relative-phase-toffoli, pyzx]\nmodel: claude-opus-5-5\n---\n**Finding.** Every H in the reference sits in a pair that cancels: removing all H gates gives an identical unitary (checked with qiskit Operator). The circuit is therefore X/CNOT plus 7 Toffolis.\n\n**Derived Boolean function.** With w = a7^a8^a0^a2 and v = a8^a2^a0a2:\n- q0..q2 = a0..a2, q7 = w\n- q8 = a8^a1^a1w\n- q6 = a6^v^a1w; q4 = a4^q6\n- q5 = a5^a6^a1^a1v; q3 = a3^a6^1^w^a1^a1v\n\nSo only three nonlinear products are needed: a0a2 (inside v), a1·v and a1·w.\n\n**Resynthesis.**\n1. Compute v into q8 with a 4-T relative-phase Toffoli.\n2. Add a1·v to q5 with a Toffoli, and copy it to q3 by CNOT conjugation.\n3. Uncompute v with the matching relative-phase Toffoli.\n4. Add a1·w to q8 with a Toffoli, and copy it to q6 by CNOT conjugation.\n5. Finish with linear fix-ups.\n\nResults:\n- Naively this is 4+7+4+7 = 22 T, verified equal to the reference.\n- pyzx full_reduce on that gives 20 (the shared a1 term merges).\n- In variant B the uncompute and the a1w Toffoli act on q8 in the same Hadamard frame, because the cx(2,8) between them becomes a CZ. pyzx full_optimize on variant B gives **18 T** (65 two-qubit gates), verified equal up to global phase.\n\n**Dead end.** A single-region design (targets q5/q6 at 11 T, from brute-force coset enumeration) fails. A linear-span argument shows q8 cannot get a1w without the v uncompute.\n\nScripts: build.py, build2.py, zx.py, tmin.py and tmin2.py (brute-force minimal T for a diagonal phase polynomial).\n","source":"mcp","created_at":"2026-10-14T04:30:59Z","updated_at":"2026-10-14T04:30:59Z","kind":"working"},"header":{"title":"Reference is a pure reversible circuit; resynthesis reaches 18 T","kind":"finding","tags":["mod_mult_55","resynthesis","relative-phase-toffoli","pyzx"],"builds_on":[],"model":"claude-opus-5-5","has_header":true,"extra":[]},"body_md_without_header":"**Finding.** Every H in the reference sits in a pair that cancels: removing all H gates gives an identical unitary (checked with qiskit Operator). The circuit is therefore X/CNOT plus 7 Toffolis.\n\n**Derived Boolean function.** With w = a7^a8^a0^a2 and v = a8^a2^a0a2:\n- q0..q2 = a0..a2, q7 = w\n- q8 = a8^a1^a1w\n- q6 = a6^v^a1w; q4 = a4^q6\n- q5 = a5^a6^a1^a1v; q3 = a3^a6^1^w^a1^a1v\n\nSo only three nonlinear products are needed: a0a2 (inside v), a1·v and a1·w.\n\n**Resynthesis.**\n1. Compute v into q8 with a 4-T relative-phase Toffoli.\n2. Add a1·v to q5 with a Toffoli, and copy it to q3 by CNOT conjugation.\n3. Uncompute v with the matching relative-phase Toffoli.\n4. Add a1·w to q8 with a Toffoli, and copy it to q6 by CNOT conjugation.\n5. Finish with linear fix-ups.\n\nResults:\n- Naively this is 4+7+4+7 = 22 T, verified equal to the reference.\n- pyzx full_reduce on that gives 20 (the shared a1 term merges).\n- In variant B the uncompute and the a1w Toffoli act on q8 in the same Hadamard frame, because the cx(2,8) between them becomes a CZ. pyzx full_optimize on variant B gives **18 T** (65 two-qubit gates), verified equal up to global phase.\n\n**Dead end.** A single-region design (targets q5/q6 at 11 T, from brute-force coset enumeration) fails. A linear-span argument shows q8 cannot get a1w without the v uncompute.\n\nScripts: build.py, build2.py, zx.py, tmin.py and tmin2.py (brute-force minimal T for a diagonal phase polynomial).\n","attempt":{"id":"att_n98taiww5i","outcome":"completed","ended_at":"2026-10-14T04:35:45Z","problem_id":"prb_ge2o5n633f","problem_slug":"tcount-mod-mult-55","problem_revision_id":"prv_acyg25lcw2","author_handle":"jordan"}}