Solovay Kitaev Algorithm

[Dhulfiqar14]

URL to the relevant documentation

https://docs.quantum.ibm.com/api/qiskit/qiskit.transpiler.passes.SolovayKitaev

Select all that apply

• [ ] typo
• [X] code bug
• [ ] out-of-date content
• [ ] broken link
• [ ] other

Describe the fix.

Using the code "import numpy as np from qiskit.circuit import QuantumCircuit from qiskit.transpiler.passes.synthesis import SolovayKitaev from qiskit.quantum_info import Operator

circuit = QuantumCircuit(1) circuit.rx(0.8, 0)

print("Original circuit:") print(circuit.draw())

skd = SolovayKitaev(recursion_degree=2)

discretized = skd(circuit)

print("Discretized circuit:") print(discretized.draw())

print("Error:", np.linalg.norm(Operator(circuit).data - Operator(discretized).data))"

that generates the basic approximations H T H as in the example for Rx(0.8), taking into account a global phase of 7π/8.

Furthermore, it is seen that the algorithm generates the same approximation for Rx(0.8129) as for Rx(0.8) with almost the same error.

But how is it possible that for Rx(0.8130) a completely different and more complex approximation is generated with almost the same error as in the previous examples. Please check this.

[jakelishman]

Without having run the maths right now, this sounds about what I'd expect? 0.8 is close to pi/4, so having a depth-1 approximation is expected. As the angle diverges from pi/4, at some point a more complex expansion at depth 2 will have a slightly better error rate, but close to the crossover value of the angle, the error rates between the two different expansions won't be much different.

Are you expecting something different here?

[Dhulfiqar14]

Hallo, considering the output of: 1) Rx(0.8129) {where 0.8129 rad is 46.57573917°}: Discretized circuit: global phase: 7π/8 (Error: 2.828360272392952)

q: H T H (Same approximation result for phi=[0.800|0.8129])

2) Rx(0.813) {where 0.813 rad is 46.58146874°}: Discretized circuit: global phase: 7π/8 (Error: 2.8282505386066616)

q: H T H Tdg H Tdg H Tdg H Tdg H Tdg H T H T H T H T H T H Tdg Tdg H Tdg H T H T H T T H Tdg H Tdg H T H Tdg H Tdg H Tdg H T H T T H Tdg H T H T H Tdg H Tdg H Tdg H Tdg H Tdg H Tdg H T H T H T H T H T T H Tdg H Tdg H T H Tdg Tdg H Tdg H T H T H T H Tdg H T H T H Tdg Tdg H Tdg H Tdg H T H T T

the user expects an optimized output that the implementation of the algorithm with small angle interval change (which was actually here with Rx(phi) only an example of a non-universal gate) provides the most continuous approximation possible and does not diverge discontinuously, secondly, the optimization should avoid any form of redundancy.

I consider Qiskit to be a powerful software development kit for quantum computing, and look forward to any new functionality from you, so please do not consider my report as criticism. Perhaps the code can be looked at in more detail

Thank you very much

[jakelishman]

A discrete algorithm will have a discrete cutoff at which a higher depth approximation will suddenly become slightly better. At such low depths, the critical region around $\pi/4$ (which has a very low-depth best decompoisition) will be relatively large. This seems entirely in line with the intuitive understanding of the mathematics. You should find the same thing around other special angles, like $0$, $\pi/2$ and so on.

If there's an actual problem in the decomposition and there's a better appromxation at the given depth of the SK algorithm that we should be finding (I haven't written out the maths by hand myself, so if you can prove that, then sure), then that would be a bug, but a discontinuity in the output of a discrete approximation algorithm is to be expected in general.

[Cryoris]

It seems that indeed the second, long approximation found for Rx(0.813) has a lower error for Rx(0.8129) than what the algorithm outputs:

Error for Rx(0.8129) w/ decomposition of Rx(0.8129): 2.828360272392952
Error for Rx(0.8129) w/ decomposition of Rx(0.83): 2.8282497533341915

I'm not quite sure if that's something that can happen in the algorithm generally or if that's an artifact due to roundoff errors in the recursion step (where we do quite some matrix operations). It would be interesting to dive deeper into what matrices are computed in the recursion steps and what basic approximations are finally chosen, but I do agree with @jakelishman that with a discrete decomposition I'm expecting a particular point where the result suddenly changes.

Edit: it looks like in the final recursion step a different basic approximation is found, i vs tdg. The former allows to cancel a lot of gates, leading to the short sequence, which is not possible for the latter. We could discuss inserting debug statements into the algorithm if that would help clarify things for the users.