Tight Bounds on Discrete Approximations of Quantum Gates
Aram W. Harrow, Benjamin Recht, Isaac L. Chuang · arXiv (Cornell University) · 2001
Quantum compiling addresses the problem of approximating an arbitrary quantum gate with a string of gates drawn from a particular finite set. It has been shown that this is possible for almost all choices of base sets and furthermore that the number of gates required for precision is only polynomial in Here we prove that quantum compiling requires a string length that is linear in, a result which matches the lower bound from counting volume up to constant factor. We leave open the problem of efficiently achieving this bound. 1