Margolus Gate (Relative-Phase Toffoli)

A simplified Toffoli that flips the target correctly but allows one extra sign, cheaper to build and safe when uncomputed.

Definition

The Margolus gate is a relative-phase Toffoli: it performs the same |11⟩-controlled NOT on the target as a true Toffoli, but introduces an extra minus sign on one of the computational basis states. That deviation is invisible in many contexts and lets the gate be built with fewer entangling operations.

Matrix

The permutation part matches Toffoli exactly; the -1 is a relative phase attached to one control pattern. If that pattern is guaranteed to be uncomputed later, the phase cancels and the gate behaves indistinguishably from a full Toffoli.

The cost saving

A true Toffoli requires six CNOTs. The Margolus gate needs only three CNOTs plus single-qubit rotations. In constructions where a Toffoli is applied and then reversed — such as the compute-uncompute pattern of multi-controlled gates — swapping in Margolus gates cuts the two-qubit gate count roughly in half with no observable effect.

# Margolus: ~3 CNOTs + Ry rotations vs 6 CNOTs for Toffoli
def cnot_savings():
    return {'toffoli': 6, 'margolus': 3}

Uses

Margolus gates are standard inside compiled multi-controlled X constructions, where the extra phases from a compute-uncompute pair cancel exactly. Compilers automatically substitute them whenever the surrounding structure guarantees the relative phase is harmless. See C3X and C4X and multi-controlled X.