I have read a paper about "approximated decomposition" of a unitary single gate (Solovay-Kitaev algorithm) which told us a any unitary single gate can be decomposed into {Hadamard, Phase} with any accuracy $\epsilon$ . The number of {Hadamard, Phase} grows exponentially as the $\epsilon$ becomes lower and the result is a better approximation of the gate. However, in simulator or emulator such as project Q and Qiskit, the $U3$ gate seems exacted decomposition which means only one parameterized $U3$ gate can realize any unitary single gate.

So if we can realize "exact unitary single gate" in quantum computer, why still so many people focus on the "approximated one" and try to optimized the sequence after decomposition?


The restricted gate set of, for example, $\{H,T\}$, is more relevant when you start talking about error corrected quantum computation. It may be that when you act on individual, physical, qubits, you can implement and arbitrary single-qubit rotation.

However, when you encode in an error correcting code, and you want to implement a gate directly on the logical qubit, the set of logical gates that you can enact may be restricted. For example, it is common to restrict to a set of gates comprising the Clifford gates + $T$. This is because, for many codes, the Clifford gates can be implemented with relatively low cost. The fault-tolerant threshold (the limit of error rate that you need to be under in order to have properly managed errors) is primarily dependent on the implementation of any other gates. So, we keep things as simple as possible and implement a single extra gate that we try to do as well as possible. Typically, that's the $T$ gate.

Yes, it is possible to implement other logical gates, and it might be in practice that this is what you'd do, but it's still going to be a finite set of gates and you have to trade off between the complications and added overheads of extending the gate set versus the reduction in sequence length.

  • $\begingroup$ So is that means the quantum compiler in simulator like qiskit firstly use algorithms to decompose the gates into sequences of one arbitrary single-qubit rotation.and then decompose each of the one-qubit-sequence into {H, T} or other universal quantum gate? If so, is there a commonly-used decomposition strategy in the procedure of decomposition into universal quantum gate? in other world, I know a parameterized gate, U3 existed in Qiskit, and how do simulator like qiskit to decompose the one-qubit-sequence into {H,T}, is there any popular strategy? $\endgroup$ – Henry_Fordham Jun 10 '20 at 7:10
  • $\begingroup$ I assume (I don't actively use these things myself) that qiskit and the like are assuming they're working on physical qubits. You'd have to build any error correction into the system yourself. $\endgroup$ – DaftWullie Jun 10 '20 at 7:12
  • $\begingroup$ In terms of how to perform the decomposition, many people will just refer you to the Solovay-Kitaev algorithm, although the material that you cite is better. $\endgroup$ – DaftWullie Jun 10 '20 at 7:13
  • $\begingroup$ OK, we have to trade off between the finite decomposition and approximated decomposition. So the procedure to do the quantum computing need both finite decomposition and approximated decomposition.Is that what you mean? $\endgroup$ – Henry_Fordham Jun 10 '20 at 8:25
  • $\begingroup$ The two decompositions that you're referring to are very different things and the terminology you've just invented for them is perhaps a bit too crude to encapsulate that (although your understand may be accurate). There are arbitrary single-qubit rotations, for which you need a continuously parametrised set of gates to recreate perfectly. You can replace that with a sequence of a finite set of gates to get within some error threshold of the unitary you want. The larger that finite gate set, the shorter the sequence (on average), but your error threshold may suffer. $\endgroup$ – DaftWullie Jun 11 '20 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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