CNOT quasiprobability decomposition with $\gamma = 3$

Question

In this paper of Christophe Piveteau and David Sutter, they prove that the $\gamma$-factor of the quasiprobability decomposition of the CNOT gate is equal to $3$ (if we don't allow classical comunication between subcircuits).

But I can't find any paper where I can get a quasiprobability decomposition with $\gamma = 3$.

I've only found this one, but in my opinion the factor there is equal to $5$ since I have 10 terms in the summation, but maybe I'm wrong.

Do you know any explicit decomposition of the CNOT gate with $\gamma = 3$? Or maybe the paper above is the answer, but I can't understand why $\gamma$ should be $3$ in that case.

Answer 1

Just for reference, this question is a follow-up of this earlier question.

Mitarai and Fujii's paper does provide with an explicit probabilistic decomposition of the CZ gate with $\gamma = 3$, which is then easy to adapt to the case of the CNOT gate, as addressed in the earlier question. For the sake of clarity, the probabilistic decomposition of the CNOT is shown below.

The $\gamma$-factor is basically a measure of the sampling overhead associated with a given probabilistic scheme (cf., e.g., the parameter $C$ defined in Section IV of this paper by Endo, Benjamin and Li). If some observable for which we want to compute the expectation value is given as a linear combination of quantum circuits, $\gamma$ simply corresponds to the sum of the absolute value of the prefactors of all such quantum circuits. In the case of the probabilistic decomposition of the CNOT shown above, denoting the projective measurement on the $A$ basis ($A \in \{ X, Y, Z \}$) as $\mathcal{M}_{A}$, we have six different quantum circuits:

1. The circuit $e^{i \pi Z/4} \otimes e^{i \pi X/4}$, corresponding to the first term.
2. The circuit $e^{-i \pi Z/4} \otimes e^{-i \pi X/4}$, corresponding to the second term.
3. The circuit $\mathcal{M}_{Z} \otimes e^{i \pi X/2}$, corresponding to the third term with $\alpha_{2} = +1$.
4. The circuit $\mathcal{M}_{Z} \otimes I$, corresponding to the third term with $\alpha_{2} = -1$.
5. The circuit $e^{i \pi Z/2} \otimes \mathcal{M}_{X}$, corresponding to the fourth term with $\alpha_{1} = +1$.
6. The circuit $I \otimes \mathcal{M}_{X}$, corresponding to the fourth term with $\alpha_{1} = -1$.

Each of these six circuits has a prefactor with absolute value $\frac{1}{2}$, so $\gamma = 6 \times \frac{1}{2} = 3$.

The key point to note is that, e.g., $\Big( \frac{I + Z}{2} \Big) \otimes e^{i \pi X /2}$ and $\Big( \frac{I - Z}{2} \Big) \otimes e^{i \pi X /2}$ correspond to the same circuit, because in both cases we are measuring the top qubit in the Z basis. It is just that, in the former case we obtain the measurement outcome $+1$ and project the top qubit onto state $|0 \rangle$, while in the latter we obtain the measurement outcome $-1$ and project the top qubit onto state $|1 \rangle$. Hence, from the third and fourth terms within the sum over $\alpha_1$ and $\alpha_2$ we only obtain four rather than eight different quantum circuits.