tsimpl 0.1.0

E-graph T-count optimizer for Clifford+T (Python bindings)

tsimpl

Python bindings for a Rust e-graph optimizer that minimizes T-count in Clifford+T circuits. Stack: Rust · egg e-graphs · cost-based extraction · PyO3 (abi3) · maturin.

---

Highlights

• T-count minimization with rewrite sets: T-parity cancel, Clifford normalize, RZ commutation, CNOT identities.
• Cost model: minimize T-count → tie-break by depth → then gate count.
• Two-liner API + CLI for batch use; emits OpenQASM 2.0.
• Wheels built with abi3 (Python 3.9+); works on Apple Silicon/macOS and Linux (when wheels are provided).

---

Install (local dev)

pip install maturin
maturin develop

After publishing to PyPI you’ll be able to do:

pip install tsimpl

---

Quickstart

Python API

import tsimpl as ts

qasm = """OPENQASM 2.0;
include "qelib1.inc";
qreg q[1];
t q[0];
t q[0];
h q[0];
z q[0];
h q[0];
"""

opt_qasm, stats = ts.optimize_qasm(qasm)
print(stats)
print(opt_qasm)

Example output:

{'t_before': 2, 't_after': 0, 'depth_before': 5, 'depth_after': 2, 'gates_before': 5, 'gates_after': 2}

OPENQASM 2.0;
include "qelib1.inc";
qreg q[1];
s q[0];
x q[0];

CLI

tsimpl --in input.qasm --out output.qasm --stats

Example:

tsimpl --in examples/qft3.qasm --stats
# {'t_before': 2, 't_after': 0, 'depth_before': 6, 'depth_after': 3, 'gates_before': 6, 'gates_after': 3}
# (optimized OpenQASM printed to stdout)

---

What it does (under the hood)

• Language/AST: H, S, T, X, Z, CNOT, RZ(π/2^k), Seq(...).

• Rewrite rules (subset):

  • T-parity: T · T ⇒ S
  • Clifford norms: H·Z·H ⇒ X, H·X·H ⇒ Z, S·S ⇒ Z, etc.
  • Commutation: move RZ(π/2^k) past gates when legal to expose cancellations.
  • CNOT identities: CNOT(a,b); CNOT(a,b) ⇒ I and adjacent cleanups.

• Extractor: custom cost function prioritizes T-count → depth → gate count.

---

When to use

• Reducing non-Clifford budget before synthesis/mapping.
• Cleaning small/medium building blocks (QFT slices, QAOA layers, adders) before backend passes.
• Teaching/demo for e-graphs in quantum compilers.

---

Development

# create/edit Rust bindings
cargo build

# run Python-side install in editable mode
maturin develop

# quick Python API test
python - <<'PY'
import tsimpl as ts, sys
opt, s = ts.optimize_qasm("OPENQASM 2.0;\ninclude \"qelib1.inc\";\nqreg q[1];\nt q[0];\nt q[0];")
print(s); print(opt)
PY

Tests & examples

• Keep small QASM samples in examples/ (e.g., qft3.qasm, qaoa_p1.qasm, adder2.qasm).
• Add property tests (semantic equality via external simulators) in future versions.

Benchmarks (optional)

• Use criterion on the Rust core crate for: time to fixpoint, rule fire counts, success rate on blocks.

---

Roadmap

• More phase-polynomial/phase-gadget rules.
• Equivalence checks vs simulators (Qiskit Aer/statevector) in CI.
• Manylinux/macOS wheels via GitHub Actions + maturin build.
• QASM3/JSON IR I/O, multi-qubit RZ patterns, light peephole mapping.

---

License

MIT © 2025 Harshit Lakum

---

Citation

If this tool helps your research, please cite:

Harshit Lakum, "tsimpl: E-graph T-count Optimizer for Clifford+T", 2025. 

---

Acknowledgements

• egg e-graph framework and the broader equality saturation community.
• OpenQASM community tooling inspiring the simple I/O used here.