In standard quantum compilation algorithms (such as the Solovay-Kitaev theorem), one approximates an arbitrary unitary using words from some universal gate set. The "approximation" here is with respect to the operator norm, and it's neat that one only requires words of length $\text{polylog}(1/\epsilon)$ to approximate an arbitrary unitary to error $\epsilon$. But what if one wants to approximate an arbitrary unitary to error $\epsilon$ with respect to some other Shatten $p$-norm? I'm curious if a similar depth bound holds.


1 Answer 1


Yes, you get the same behavior. This is because all norms on finite dimensional spaces are equivalent. That means that for every $p$ there exist constants $c_p, d_p > 0$ such that $$ d_p \|X\|_p \leq \|X\| \leq c_p \|X\|_p $$ and these constants are "universal" in the sense that it holds for all $X$. Thus suppose we want to approximate in the $p$-norm to an accuracy $\epsilon$ then by equivalence of norms we have $$ \|X\|\leq \frac{\epsilon}{d_p} \implies \|X\|_p \leq \epsilon $$ Thus we can use the Solovay-Kitaev theorem to say that we need $\mathrm{polylog}(d_p/\epsilon)$ gates but notice $d_p$ is just some universal constant so this is still $\mathrm{polylog}(1/\epsilon)$.

  • $\begingroup$ As a brief followup to this question, is it generally known how $d_p$ and $c_p$ scale with the dimension of the vector space? $\endgroup$ Nov 6, 2023 at 2:01

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.