Efficient discrete approximations of quantum gates
Aram W. Harrow, Benjamin Recht, Isaac L. Chuang · Journal of Mathematical Physics · 2002
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 log 1/ε. Here we prove that using certain sets of base gates quantum compiling requires a string length that is linear in log 1/ε, a result which matches the lower bound from counting volume up to constant factor.