Decomposition of the Toffoli gate into the Clifford+T base, from Nielsen and Chuang (Figure 4.9). The first argument is the target, and the other two are the controls. The controls can be positive or negative.

Decomposition of the Toffoli gate into the Clifford+T base, from Amy et al. (http://arxiv.org/abs/1206.0758v3, Figure 13). The first argument is the target, and the other two are the controls. The controls can be positive or negative.

Decomposition of the Toffoli gate using controlled Clifford operators, from Nielsen and Chuang (Figure 4.8). The controls can be positive or negative.

Decomposition of the Toffoli gate into the Clifford+T base, using T-depth 1 and four ancillas. From http://arxiv.org/abs/1210.0974 (Figure 1). The first argument is the target, and the other two are the controls. The controls can be positive or negative.

Decomposition of the doubly-controlled iX-gate into the Clifford+T base, using T-count 4 and T-depth 2. Adapted from (http://arxiv.org/abs/1210.0974, Figure 10). The first argument is the target, and the other two are the controls. The controls can be positive or negative.

Decomposition of the doubly-controlled iX-gate into the Clifford+T base, using T-count 4, and using the control qubits only as controls. Derived from Nielsen and Chuang (Figure 4.9). The controls can be positive or negative.

Decomposition of the doubly-controlled iX-gate into the Clifford+T base, using T-depth 1 and one ancilla. Adapted from (http://arxiv.org/abs/1210.0974, Figure 9). The first argument is the target, and the other two are the controls. The controls can be positive or negative.

Decomposition of the doubly-controlled Z-gate into the Clifford+T base. Adapted from Amy et al. (http://arxiv.org/abs/1206.0758v3, Figure 13). The controls can be positive or negative.

Decomposition of the doubly-controlled Z-gate into the Clifford+T base, using T-depth 1 and four ancillas. From Selinger (http://arxiv.org/abs/1210.0974, Figure 1). The controls can be positive or negative.

Decomposition of the Fredkin (controlled-Swap) gate into the Clifford+T base. The first two arguments are the targets, and the last one the control. The controls can be positive or negative.

Decomposition of a controlled H-gate into the Clifford+T base. From Amy et al. (http://arxiv.org/abs/1206.0758v3, Figure 5(a)). The first argument is the target and the second one the control. The control can be positive or negative.

Decomposition of a controlled W-gate into the Clifford+T base. The first two arguments are the targets, and the last argument is the control. The control can be positive or negative.

Decomposition of a W-gate into the Clifford+T base.

Decomposition of a controlled iX-gate into the Clifford+T base. The first argument is the target, and the second one is the control. The control can be positive or negative.

Decomposition of a controlled S-gate into the Clifford+T base. From Amy et al. (http://arxiv.org/abs/1206.0758v3, Figure 5(b)). The first argument is the target, and the second one is the control. The control can be positive or negative.

Decomposition of a controlled T-gate into the Clifford+T base. The first argument is the target, and the second one is the control. The control can be positive or negative.

Decomposition of a controlled V-gate into the Clifford+T base. Adapted from Amy et al. (http://arxiv.org/abs/1206.0758v3, Figure 5(c)). Our V-gate is HS^†H as in Nielsen and Chuang. The first argument is the target, and the second one is the control. The control can be positive or negative.

Decomposition of a controlled E-gate into the Clifford+T base. The first argument is the target, and the second one is the control. The control can be positive or negative.

Decomposition of a controlled Y-gate into the Clifford+T base. The gate is from the Ground State Estimation algorithm and is defined as Y = SHS, or equivalently,

It should not be confused with the Pauli Y gate. The first argument is the target, and the second one is the control. The control can be positive or negative.

A "plain" Toffoli gate, not decomposed. This is provided for convenience, for example to use with with_combined_controls.

A "plain" doubly-controlled iX-gate, not decomposed. This is provided for convenience, for example to use with with_combined_controls.

Decomposition of an m-times controlled not-gate, using m−2 ancillas that do not need be initialized in a particular state. Adapted from Barenco et al. (http://arxiv.org/abs/quantph/9503016, Lemma 7.2).

In addition to what is shown in Barenco et al., this function permits some Toffoli gates to be replaced by doubly-controlled iX-gates. This may be beneficial in gate bases, such as Clifford+T, where a doubly-controlled iX-gate has a simpler representation than a Toffoli gate.

The first argument is a Toffoli gate to use in the decomposition. The second argument may be either a Toffoli gate or a doubly-controlled iX gate. The third argument is the target, the fourth argument is a list of qubits to be used as ancillas, and the fifth argument is a list of signed controls. The ancillas need not be initialized, and are returned in their original state.

The size of this circuit is linear in the number of controls; the decomposition uses 4m−8 doubly-controlled gates for m ≥ 3.

Decomposition of a multiply-controlled iX-gate, using no ancillas. Adapted from Giles and Selinger (http://arxiv.org/abs/1212.0506, Section 5.2).

The first argument is a Toffoli gate or a doubly-controlled iX-gate. The third argument is the target, and the fourth argument is a list of signed controls.

The size of this circuit is linear in the number of controls; the decomposition uses 8m−32 doubly-controlled gates, 4 T-gates, and 2 H-gates, for m ≥ 6.

Partition a list of controls into quantum and classical.

Given a function that expects a qubit (typically as a control), turn it into a function that can handle a signed (positive or negative) qubit. This is done by conjugating the circuit with negations on both sides, if the sign is negative. Usage:

with_signed_qubit c $ \q -> do
  <<<code using q>>>

Decompose quantum controls recursively until at most n remain, and then pass these reduced controls to the given circuit. Precondition: n ≥ 1.

The decomposition is done using a Toffoli-like gate that is given as the first argument. This should be either a Toffoli gate, a doubly-controlled iX-gate, a decomposition thereof, or any other reversible ternary gate with the behavior

• |000〉 ↦ |0〉|φ₀〉
• |001〉 ↦ |0〉|φ₁〉
• |010〉 ↦ |0〉|φ₂〉
• |011〉 ↦ |1〉|φ₃〉,

where the states |φ₀〉, …, |φ₃〉 are arbitrary.

For example, when n=2, this typically yields a circuit such as the following (here shown using the doubly-controlled iX-gate):

And for n=1, the circuit typically looks like this:

Classical controls are not decomposed, but are applied to the resulting circuit directly.