guppyalgos.primitives.gate_decompositions.cnx.cnx_cca

Multi-controlled X gate in log depth using conditionally clean ancillas.

This implements the logarithmic-depth CCA construction described in Section 5.3 of

Tanuj Khattar, Craig Gidney, “Rise of conditionally clean ancillae for efficient quantum circuit constructions”, https://arxiv.org/abs/2407.17966

This uses 2 * n_controls - 3 Toffoli gates (some of these are temporary AND and uncompute gates) and either 1 or 2 clean ancilla qubits, depending on the number of controls.

The dirty variant (Section 5.5) uses two dirty ancillae and 4n - 6 Toffoli gates.

Functions

cat_cca(q0, q1, target)

Catalyze a conditionally clean ancilla.

cnx_cca_logdepth(controls, target)

Apply a logarithmic-depth CCA-based cnx.

cnx_cca_logdepth_dirty(controls, target, ...)

Apply a logarithmic-depth CCA-based cnx using 2 dirty ancillae.
guppyalgos.primitives.gate_decompositions.cnx.cnx_cca.cat_cca(q0, q1, target)

Catalyze a conditionally clean ancilla.

This uses one conditionally clean ancilla (target) to catalyze the generation of two more conditionally clean ancillae (q0 and q1).

The two operations X(target) and CCX(q0, q1, target) commute, making this self-inverse.

guppyalgos.primitives.gate_decompositions.cnx.cnx_cca.cnx_cca_logdepth(controls, target)

Apply a logarithmic-depth CCA-based cnx.

Based on https://arxiv.org/abs/2407.17966, given \(n\) control qubits and the target, uses 1 or 2 clean ancilla qubits to apply the multicontrolled-x gate on the target using \(2n -3\) Toffoli gates.

Parameters:

  • controls (array[qubit, n_controls]) – register of control qubits.

  • target (qubit) – target qubit.

guppyalgos.primitives.gate_decompositions.cnx.cnx_cca.cnx_cca_logdepth_dirty(controls, target, borrowed_a, borrowed_b)

Apply a logarithmic-depth CCA-based cnx using 2 dirty ancillae.

Based on Section 5.5 of https://arxiv.org/abs/2407.17966

Parameters:

  • controls (array[qubit, n_controls]) – register of control qubits.

  • target (qubit) – target qubit.

  • borrowed_a (qubit) – first borrowed ancilla.

  • borrowed_b (qubit) – second borrowed ancilla.