2
$\begingroup$

In this answer it is explained how adding any non-Clifford gate $G$ to the Clifford gate set gives a universal gate set. However, that defines the gate set as the group generated by $G$ and the Cliffords, and hence also contains the inverse of $G$. Does the result continue to hold if we don't add $G^{-1}$ to our gate set?

For the Solovay-Kitaev theorem we now also know that inverses are not necessary, so that would be quite nice.

EDIT: clarification based on comments below. In the answer, they are looking at the group generated by Cliffords and $G$. This means — by definition of generating set — that Cliffords are augmented with both $G$ and $G^{-1}$. I'm asking whether the monoid generated by the Cliffords and $G$ (i.e. without inclusion of $G^{-1}$) is already enough to get a universal set of gates.

$\endgroup$
4
  • 2
    $\begingroup$ Isn't the implication the other way around: that if you add $G$ to the Clifford gates, you generate a group, and therefore $G^{-1}$ is contained within that group, so you can always create $G^{-1}$? It doesn't say you need $G^{-1}$ to start with? $\endgroup$
    – DaftWullie
    Commented May 2 at 15:07
  • $\begingroup$ I think that you answered yourself already with the Solovay-Kitaev algorithm. H, T and CNOT compose a universal set and neither of the gates is inverse of T. However, with SK algorithm you can use these gates to construct inverse of T. $\endgroup$ Commented May 2 at 16:52
  • 2
    $\begingroup$ $T^{-1} = T^7$, so just using $T$ you can make the inverse. So there 'just' adding $T$ is enough to get a group. However, a priori there is no reason to believe that adding some gate $G$ to the Cliffords allows you to (exactly or approximately) construct $G^{-1}$. $\endgroup$
    – John
    Commented May 3 at 9:38
  • 1
    $\begingroup$ @DaftWullie, if you give a generating set of a group, it is also implicit that you require inverses of those generators. I'm asking whether in this specific case that is needed or not. I.e. the group operations are composition AND inversion, so saying <A,B> is a group, means the elements will look like products of A, B and $A^{-1}$ and $B^{-1}$. Otherwise you are just generating the monoid of A and B. $\endgroup$
    – John
    Commented May 3 at 9:39

2 Answers 2

1
$\begingroup$

TL;DR: Yes, in a finite dimensional Hilbert space, $G^{-1}$ can be approximated to arbitrary accuracy as a finite power of $G$. If $G$ has finite order $r$, this follows from $G^{-1}=G^{r-1}$. The general case can be proven using the simultaneous version of Dirichlet's approximation theorem. Consequently, for any set of gates $C$, if $C\cup\{G,G^{-1}\}$ is universal$^1$, then so is $C\cup\{G\}$.


It is sufficient to show that the set $\{G^n\,|\,n=1,2,\dots\}$ contains a sequence $G_i$ with $i=1,2,\dots$ such that $\lim_{i\to\infty}G_i=I$.

Suppose that $G=\sum_{j=1}^d e^{2\pi i\alpha_j}|\psi_j\rangle\langle\psi_j|$ for some $\alpha_j\in[0,1)$ and some orthonormal basis $|\psi_j\rangle$. The simultaneous version of Dirichlet's approximation theorem asserts that for every positive integer $k=1,2,\dots$, there are integers $p_{k,1},\dots,p_{k,d}$ and $q_k$ such that $1\leqslant q_k\leqslant k$ and $\Delta_{k,j}:=q_k\alpha_j-p_{k,j}\in\left[-\frac{1}{k^{1/d}},\frac{1}{k^{1/d}}\right]$. Consequently, $\lim_{k\to\infty}\Delta_{k,j}=0$ for every $j$.

Define $G_k:=G^{q_k}$. I will use entanglement fidelity $F_e$ as a measure of closeness between $G_k$ and $I$. For a general quantum channel $\mathcal{E}$, it is defined as \begin{align} F_e(\mathcal{E}):=\langle\psi|(\mathcal{E}\otimes\mathcal{I})(|\psi\rangle\langle\psi|)|\psi\rangle\tag1 \end{align} where $\mathcal{I}$ is the identity channel and $|\psi\rangle:=\frac{1}{\sqrt{d}}\sum_k|k\rangle|k\rangle$ is the a maximally entangled state. For a unitary channel $\mathcal{U}(\rho)=U\rho U^\dagger$ we have $F_e(U):=F_e(\mathcal{U})=\frac{1}{d^2}|\mathrm{tr}(U)|^2$, so \begin{align} \lim_{k\to\infty}F_e(G_k)&=\frac{1}{d^2}\lim_{k\to\infty}|\mathrm{tr}(G^{q_k})|^2\tag2\\ &=\frac{1}{d^2}\lim_{k\to\infty}\left|\sum_j e^{2\pi iq_k\alpha_j}\right|^2\tag3\\ &=\frac{1}{d^2}\lim_{k\to\infty}\left|\sum_j e^{2\pi i\Delta_{k,j}}\right|^2\tag4\\ &=\frac{1}{d^2}d^2=1\tag5 \end{align} where the penultimate equality follows from the continuity of the exponential function and the fact that $\lim_{k\to\infty}\Delta_{k,j}=0$ for every $j$. Finally, unitary group is compact, so $G_k$ has a convergent subsequence $G_i$. Let $G':=\lim_{i\to\infty} G_i$. Entanglement fidelity $F_e(U)$ is a continuous function of $U$, so by calculation above $F_e(G')=1$. But this implies that $G'=I$, so $\lim_{i\to\infty}G_i=I$.


$^1$ I assume that universal means "generates a dense subset of the unitary group". A weaker, but perhaps more important, concept of universality is the computational universality which means "able to realize arbitrary quantum computations". An example of a computationally universal set of unitaries that fails to be universal is the Hadamard and Toffoli.

$\endgroup$
1
$\begingroup$

Note that there are non-Clifford gates with no inverse. For example: measurement in a non-Pauli basis.

Consider $M_{X+Y}$, which measures if a single qubit state is in the positive or negative eigenspace of $X+Y$. It projects the qubit into a $|T\rangle$ state or a $Z|T\rangle$ state. Either of these states can be consumed with stabilizer gates to perform a T gate by gate teleportation, giving access to universal computation. But $M_{X+Y}$ has no inverse because it is a measurement gate.

$\endgroup$
1
  • $\begingroup$ That makes sense, but my question was more on the mathematical side of things, i.e. if a certain set of unitaries lies dense in the set of all unitaries. I would imagine the question becomes more complicated once we start considering whether a set of linear maps (like the measurement operation you mention) generates a dense set of unitaries. $\endgroup$
    – John
    Commented May 10 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.