Approximate MCX

[clerusch]

Priority

Low

Responsible

Clemens Schumann

Short Description

Implement an approximate synthesis backend for MCX gates using the approximate multi-qubit Toffolis from Gosset et al. to reduce T count.

Long Description

Approximate Multi-Controlled X

Summary

Add a new approximate synthesis backend for multi-controlled X gates to Qrisp:

mcx(controls, target, method="approx", epsilon=...)

The backend should implement the mixed-unitary approximate MCX construction from:

• David Gosset, Robin Kothari, and Chenyi Zhang, “Multi-qubit Toffoli with exponentially fewer T gates”

The main idea is to replace a large exact MCX by:

• a small number of sampled parity checks,
• followed by one much smaller exact MCX,
• with one-sided error bounded by epsilon.

This gives a user-facing way to trade exactness for substantially lower non-Clifford cost.

Motivation

Qrisp currently offers several exact MCX synthesis methods, but it does not expose an approximate MCX backend for users who are willing to trade correctness guarantees for lower T-cost.

This makes particular sense for circuits with a few large MCX gates, common in arithmetic gates and oracles.

Proposed Feature

Introduce a new mcx synthesis method:

mcx(
    controls,
    target,
    method="approx",
    epsilon=1e-3,
)

with the following API shape:

mcx(
    controls,
    target,
    method="approx",
    ctrl_state=-1,
    epsilon=None,
    k=None,
    seed=None,
    inner_method="auto",
)

Parameter intent

• epsilon: target error bound.
• k: explicit number of sampled parity checks.
• seed: deterministic sampling seed.
• inner_method: exact MCX method used for the reduced inner gate.

Intended semantics

• the target always flips on the requested control state. On other basis states the gate may flip erronuously, permitting false positives but not false-negatives
• that false-positive probability is bounded by 2^-k
• if epsilon is given, use k = ceil(log2(1 / epsilon)).

High-Level Design

For controls x and desired control state s:

1. Form mismatch bits conceptually as:

y_i = x_i xor s_i

2. Sample k random subsets of the control positions.
3. Compute one parity ancilla for each sampled subset.
4. Apply one exact k-control MCX to those parity ancillas with negative controls.
5. Uncompute the parity ancillas.

Thus, the expensive exact gate is moved from the original control count down to k
which grows only logarithmically with 1 / epsilon.

Proposed Scope

Phase 1: Base MCX feature

Deliver:

• method="approx" in qrisp.mcx(...)
• support for epsilon, k, seed, and inner_method
• support for arbitrary ctrl_state
• focused gate-level tests that verify the sampled truth table.

Phase 2: Targeted arithmetic integrations

Potential follow-on integrations:

• remaud_adder(...) as a first algorithm-level use case
• selected QCLA carry-tree sites where wide MCX gates dominate

Limitations

The construction is sampled.
That means users should understand that:

• one call instance corresponds to one sampled circuit,
• repeated internal uses may need careful seed handling,
• deterministic replay matters in algorithms that explicitly invert or replay carry logic. (e.g. an uncomputing would require access to the same seed used)

References

• David Gosset, Robin Kothari, and Chenyi Zhang, “Multi-qubit Toffoli with exponentially fewer T gates”
• QCLA reference used in Qrisp, arXiv:2304.02921
• Remaud adder reference used in Qrisp, arXiv:2501.16802

Means of Verification

Test-ID	Type	Description	Expected Result
T-001	Positive	Call mcx(controls, target, method="approx", k=3, seed=7, ctrl_state="10110") and compare against the sampled predicate induced by the same masks.	The generated circuit matches the sampled truth table exactly, and the target flips on the requested control state.
T-002	Negative	Call mcx(..., method="approx") without providing either epsilon or k.	An exception is raised stating that either epsilon or k is required.
T-003	Boundary	Call mcx(..., method="approx", epsilon=0.2, seed=11) without explicitly setting k.	The implementation resolves k = ceil(log2(1/epsilon)) and produces the same sampled behavior as using that explicit k.
T-004	Boundary	Call mcx(..., method="approx", k=1, ctrl_state="010101") to exercise the smallest valid sample count and a non-default control state.	The target still always flips on the requested control state while other basis states may only produce bounded false positives.