gray_synth_toffoli#

gray_synth_toffoli(qc: QuantumCircuit) → QuantumCircuit[source]#

Replace Toffoli gates with a gray-synthesis decomposition.

Qrisp’s default Toffoli implementation is optimised for T-depth, since the majority of Qrisp algorithms target fault-tolerant execution where T gates dominate cost. The default decomposition does not have a higher CNOT count than the gray-synthesis variant, but it requires more SWAP gates when routed onto linear nearest-neighbour connectivity.

The gray-synthesis decomposition uses 6 CNOT gates and does not inherently satisfy linear connectivity either, but the router consistently resolves the gap with a single SWAP whose constituent CNOTs partially cancel with a Toffoli CNOT — resulting in 7 physical CNOTs and a displaced target qubit.

Parameters:

qcQuantumCircuit: The input quantum circuit.

Returns:

QuantumCircuit: A new circuit with every Toffoli replaced by the gray-synthesis decomposition.

Examples

We showcase the distinction in Toffoli decompositions.

>>> from qrisp import QuantumCircuit, PassManager
>>> from qrisp import gray_synth_toffoli, decompose
>>> qc = QuantumCircuit(3)
>>> qc.ccx(0, 1, 2)
>>> print(qc)

qb_95: ──■──
         │
qb_96: ──■──
       ┌─┴─┐
qb_97: ┤ X ├
       └───┘

>>> pm_0 = PassManager()
>>> pm_0 += decompose()
>>> decomposed_qc = pm_0.run(qc)
>>> print(decomposed_qc)
       ┌─────┐
qb_95: ┤ Tdg ├───────■─────────■────■───────────────────────■──
       ├─────┤┌───┐  │  ┌───┐┌─┴─┐  │  ┌─────┐┌───┐ ┌───┐ ┌─┴─┐
qb_96: ┤ Tdg ├┤ X ├──┼──┤ T ├┤ X ├──┼──┤ Tdg ├┤ X ├─┤ T ├─┤ X ├
       └┬───┬┘└─┬─┘┌─┴─┐├───┤└───┘┌─┴─┐└─────┘└─┬─┘┌┴───┴┐├───┤
qb_97: ─┤ H ├───■──┤ X ├┤ T ├─────┤ X ├─────────■──┤ Tdg ├┤ H ├
        └───┘      └───┘└───┘     └───┘            └─────┘└───┘

While this implementation has only a T-depth of 4, the CX gates essentially “cycle” through the connectivity requirements. On a linear chain connectivity, several swaps would be required.

>>> pm_1 = PassManager()
>>> pm_1 += gray_synth_toffoli
>>> pm_1 += decompose()
>>> optimized_qc = pm_1.run(qc)
>>> print(optimized_qc)
       ┌───┐                                                  ┌────────┐
qb_95: ┤ T ├───────────────────■─────────────────────■────■───┤ gphase ├──■──
       ├───┤                   │                     │  ┌─┴─┐┌┴────────┤┌─┴─┐
qb_96: ┤ T ├───────■───────────┼─────────■───────────┼──┤ X ├┤ P(-π/4) ├┤ X ├
       ├───┤┌───┐┌─┴─┐┌─────┐┌─┴─┐┌───┐┌─┴─┐┌─────┐┌─┴─┐├───┤└─────────┘└───┘
qb_97: ┤ H ├┤ T ├┤ X ├┤ Tdg ├┤ X ├┤ T ├┤ X ├┤ Tdg ├┤ X ├┤ H ├────────────────
       └───┘└───┘└───┘└─────┘└───┘└───┘└───┘└─────┘└───┘└───┘

This implementation has T-depth 5 but the first 4 CX gates can be implemented swap-free on a linear chain connectivity. After this, a single SWAP (that can be fused with one of the CX) is suffificient to execute the remaining CX.