How to know if your gate set is "complete"

Question

In Daniel Greenbaum's paper, "Introduction to Gate Set Tomography", in page 20, he claims the gate sets $G = \{\{\}, X_{\pi/2}, Y_{\pi/2}\}$ and $G' = \{ \{\}, X_{\pi/2}, Y_{\pi/2}, X_{\pi}\}$ with $F_k \in G$, $F_k |\rho\rangle\rangle$ are able to "span the bloch sphere". He clarifies this with, measurements $\langle\langle E | F_k |\rho \rangle \rangle$ spans the Bloch sphere. Certainly, $G$and $G'$ cannot "hit" every element in $\mathcal{H}^2$. Taking $\{\langle\langle E_k |\} = \{|x\rangle\langle x|, x \in \{0, 1\}^n\}$, does "span the bloch sphere", just mean you are able to "hit" all states in $\{\langle\langle E_k |\}$.

In general how do you determine if a gate set has this property? Are there other measurement bases that are ever used? What does a complete set of gates look like for 2 qubits? What are some other examples of "spanning" gate sets on 1 qubit? What happens with the CNOT gate? It doesn't seem to be addressed in any literature I've seen implementing GST.

Answer 1

The original question slightly mischaracterizes Greenbaum's description. On page 20, Greenbaum states (Eq. 3.10) that the $F_k$ correspond to products of elements from $\mathcal{G}$. They are not necessarily themselves elements of $\mathcal{G}$. This is important. In the two examples that Greenbaum gives (which the original question mentions), only the second one actually uses a set $\{F_k\}$ that is in 1:1 correspondence with $\mathcal{G}$. The first example has a smaller set of native gates in $\mathcal{G}$, and requires at least one $F$ that is a product of gates from $\mathcal{G}$.

In general, a gate set $\mathcal{G} = \{\rho,M,G_1\ldots G_k\}$ is "complete" if and only if:

1. A set of density matrices that span the space of $d\times d$ matrices can be produced by applying products of gates from $\mathcal{G}$ to the initial state $\rho$.
2. A set of POVM effects that span the space of $d\times d$ matrices can be produced by applying products of gates from $\mathcal{G}$ to the effects $E_j$ in the POVM $M = \{E_j\}$.

When viewed as a condition on the states and effects that can be constructed, this is the requirement of informational completeness that appears throughout the literature on tomography. But as a condition on gate sets, it is a little nontrivial and does not have a simple mathematical definition in the literature. For example, it's worth observing that this is not strictly a condition on the gates $\{G_k\}$! The gate set contains $\rho$ and $M$ too. If the gates act on a single qubit and generate a dihedral group, then it's possible to generate informationally complete input states and final measurements unless $\rho$ and $M$ commute with $\sigma_z$.

Most single-qubit gate sets are sufficient to generate spanning SPAM sets. If your gate set generates any unitary 2-design (e.g. the Cliffords), then it's guaranteed to be complete. It's pretty hard not to generate the Cliffords, so this is a useful rule of thumb. If your gate set doesn't generate the Cliffords, caveat emptor and you may have to do some math.

Answer 2

Assuming we have the matrix representation of each gate in the set, determining if the set spans the Bloch sphere is mathematically equivalent to checking if the matrices are linearly independent and form a basis of $M_2(\rm I\!R)$. For a set of three $2 \times 2$ matrices $\{ A$, $B$, $C \}$, we can just think of the matrices as being vectors of length 4:

$$ \begin{pmatrix} a & b \\ c & d \end{pmatrix} \mapsto (a, b, c, d)$$

We can then follow the usual procedure for checking the linear independence of vectors

$$ c_1 A + c_2 B + c_3 C = 0 $$

and have to prove that $c_1 = c_2 = c_3 = 0$ is the only solution.

Let me know if that answers your question