1

Given a single-qubit unitary matrix, can we find the shortest sequence of Clifford + T gates that correspond to that unitary?

According to Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates , which is Solovay-Kitaev decomposition, I learned single-qubit decomposition may need $O(\log^{3.97} (1/\delta))$ clifford+T gates with the accuracy $\delta$.

And later many optimization is worked on it. For example: Synthesis of unitaries with Clifford+T circuits

So I want to know if there exists a shortest sequence of Clifford + T gates that correspond to decompose any single-qubit unitary into Clifford+T? If it existed, what is commonly used in current compiler?

glS
  • 24,708
  • 5
  • 34
  • 108
Henry_Fordham
  • 457
  • 2
  • 9
  • 1
    See link to paper in the answer to this: https://quantumcomputing.stackexchange.com/questions/11861/how-to-approximate-rx-ry-and-rz-gates It may be interesting for you. – Martin Vesely Jun 22 '20 at 10:10

1 Answers1

4

In the abstract of the first paper you cite (which, incidentally, is not Solovay-Kitaev, it's an improvement), they say

We report an efficient synthesis algorithm, with an exact optimality guarantee on the number of Hadamard and T gates used

In other words, this is the best that can be done. It yields the shortest possible sequence. This best is $O(\log\frac{1}{\delta})$ Hadamard + T.

DaftWullie
  • 57,689
  • 3
  • 46
  • 124