guppyalgos.primitives.gate_decompositions.cnx.cnx_approx

Approximate multi-controlled X gate using random XOR method.

Functions

cnx_approx(n_ctrl, epsilon[, cnx_method])

Generate a Guppy function to apply an approximate multi-controlled X gate.
guppyalgos.primitives.gate_decompositions.cnx.cnx_approx.cnx_approx(n_ctrl, epsilon, cnx_method=<function cnx>)

Generate a Guppy function to apply an approximate multi-controlled X gate.

Implements Algorithm 1 from arXiv:2510.07223 “Multi-qubit Toffoli with exponentially fewer T gates”. The algorithm uses random XOR sampling to reduce a large \(C^nX\) to a small \(C^kX\) where \(k = O(\log(1/\varepsilon))\), and is independent of \(n\). This achieves a \(C^nX\) implementation within error \(\varepsilon\) in the diamond distance using only \(O(\log(1/\varepsilon))\) T gates instead of \(O(n)\).

Algorithm:

  1. Choose \(k = \lceil \log_2(1/\varepsilon) \rceil + 2\) random subsets of the control qubits

  2. Compute the XOR parity for each subset (all Clifford operations)

  3. Apply an OR gate to the \(k\) parity results using an exact \(C^kX\) gate

Parameters:

  • n_ctrl (int) – Number of control qubits.

  • epsilon (float) – Error value for the approximation (diamond distance).

  • cnx_method (GuppyFunctionDefinition) – Gate implementation to use for the exact \(C^kX\) gate.

Returns:

Function taking an array of control qubits, a target qubit, and a random number generator; applies approximate \(C^nX\) gate.

Return type:

GuppyFunctionDefinition[[array[qubit, n_ctrl], qubit, RNG], None]