Bug fixes in Solovay Kitaev Decomposition #14217

alexanderivrii · 2025-04-17T11:26:24Z

Summary

This PR fixes a number of bugs we have recently discovered in the Python code for the Solovay-Kitaev decomposition, together with @Cryoris and @anedumla.

Fixes include:

fixed a problem with the rotation axis computation for 180 degree rotations (thanks to @Cryoris for working out the math)
fixed a problem where the global phase of the returned circuit might have been off by $\pi$, due to the underlying algorithm approximating not the original SU(2) matrix, but its projection onto SO(3)
in particular fixed Global phase on Solovay-Kitaev decomposition seems wrong #9552.

Longer-term, we will deprecate the Python code for Solovay-Kitaev decomposition altogether, and switch to the new improved pass written in Rust that also fixes these problems (see #14203), however for backward compatibility we need to temporarily support the Python code as well, and thus it makes sense to fix the problems on the Python side too.

Details and comments

Other changes:

There was a very strange "back door" for returning a circuit with the original unitary matrix if the computed matrix is not close to the identity. This behavior is not consistent with the documented description of the pass and was removed. (Or rather the functions to_circuit and to_dag remain for backwards compatibility but are no longer used by the main pass).
The GateSequence class used to store both the SO(3) matrix as product and the SU(2) matrix as product_su2, however the parameter product_su2 was not updated correctly in various places (and it was not even clear what to do within GateSequence.from_matrix). As product_su2 was almost not used anywhere in the algorithm (with the exception of one place where its usage did not seem to be correct anyway), it was simply removed to avoid confusion and unnecessary computations.

The method used to return [0, 0, 0] for rotation axis when theta is very close to 0 (and yet not within 1e010). This commit fixes this by noting that the rotation axis of an SO(3) matrix is simply the eigenvector of this matrix corresponding to eigenvalue 1.

The implemented algorithm has a global phase uncertainty of +-1, due to approximating not the original SU(2) matrix but its projection onto SO(3). This fixes the global phase of the computed approximation. In addition, the product_su2 matrix in GateSequence was not correctly computed in many cases, leading to incorrect values when using this attribute. Since this is not needed for the actual algorithm (and spends unnecessary effort for computing it), this also completely removes this attribute. Co-authored-by: Almudena Carrera Vazquez <almudenacarreravazquez@hotmail.com>

One of the tests was simply wrong because the reference circuit has the wrong global phase. The tests that check the gates in the final decomposition should not assume that SGate is included and SdgGate is not.

qiskit-bot · 2025-04-17T11:26:30Z

One or more of the following people are relevant to this code:

@Qiskit/terra-core

jakelishman · 2025-04-17T11:39:11Z

This isn't a review, but if the purpose of this is a bugfix to touch the Python code that we're removing in favour of Rust code, should it be targetting as API stable for backport to 1.4 and 2.0?

coveralls · 2025-04-17T11:59:28Z

Pull Request Test Coverage Report for Build 14773444830

Warning: This coverage report may be inaccurate.

This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.

For more information on this, see Tracking coverage changes with pull request builds.
To avoid this issue with future PRs, see these Recommended CI Configurations.
For a quick fix, rebase this PR at GitHub. Your next report should be accurate.

Details

27 of 41 (65.85%) changed or added relevant lines in 4 files are covered.
1220 unchanged lines in 24 files lost coverage.
Overall coverage decreased (-0.3%) to 87.91%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
qiskit/synthesis/discrete_basis/generate_basis_approximations.py	0	1	0.0%
qiskit/synthesis/discrete_basis/commutator_decompose.py	6	19	31.58%

Files with Coverage Reduction	New Missed Lines	%
crates/accelerate/src/two_qubit_decompose.rs	1	91.63%
crates/qasm2/src/lex.rs	2	92.73%
qiskit/synthesis/unitary/qsd.py	2	95.97%
crates/accelerate/src/split_2q_unitaries.rs	4	97.48%
qiskit/qpy/binary_io/value.py	4	82.99%
crates/accelerate/src/commutation_analysis.rs	5	95.24%
crates/accelerate/src/convert_2q_block_matrix.rs	5	93.38%
crates/accelerate/src/euler_one_qubit_decomposer.rs	6	91.33%
qiskit/primitives/containers/observables_array.py	6	94.21%
crates/accelerate/src/uc_gate.rs	7	95.17%

Totals
Change from base Build 14499882025:	-0.3%
Covered Lines:	74582
Relevant Lines:	84839

💛 - Coveralls

alexanderivrii · 2025-04-21T10:01:12Z

@jakelishman, yes, I believe we should. Does this mean that we should change the milestone to 2.0? Or keep it as 2.1 and talk to mergify?

alexanderivrii · 2025-04-21T11:21:01Z

One more problem that I have recently discovered (and fixed in the followup PR #14225) is that the SolovayKitaevSynthesis unitary synthesis plugin caches the computed approximations regardless of the basis set, that is the following code:

circuit = QuantumCircuit(1)
circuit.rx(0.8, 0)
unitary = Operator(circuit).data
plugin = SolovayKitaevSynthesis()

# First, use the ["h", "t", "tdg"] set
out = plugin.run(unitary, basis_gates=["h", "t", "tdg"])
print(out.count_ops())
self.assertLessEqual(set(out.count_ops().keys()), {"h", "t", "tdg"})

# Second, use the ["h", "s"] set
out = plugin.run(unitary, basis_gates=["h", "s", "sdg"])
self.assertLessEqual(set(out.count_ops().keys()), {"h", "s", "sdg"})
print(out.count_ops())

synthesizes both times to the first specified basis set of ["h", "t", "tdg"]. Creating two different SolovayKitaevSynthesis() plugins does not solve this, since the caching is done at a class-level attribute. The fix (many thanks to @eliarbel for the suggestion!) consists of storing a dictionary from the basis sets to cached approximations instead. I am wondering if it would make sense to include this fix in this PR instead?

Cryoris

Thanks for taking care of these! And I agree these should be backported, especially now that we decided we'll do the oxidization in place.

qiskit/synthesis/discrete_basis/gate_sequence.py

qiskit/synthesis/discrete_basis/solovay_kitaev.py

qiskit/synthesis/discrete_basis/gate_sequence.py

qiskit/synthesis/discrete_basis/commutator_decompose.py

…Rodrigues formula, while additionally handling the case of 180-degree rotation

qiskit/synthesis/discrete_basis/commutator_decompose.py

qiskit/synthesis/discrete_basis/gate_sequence.py

qiskit/synthesis/discrete_basis/generate_basis_approximations.py

qiskit/synthesis/discrete_basis/gate_sequence.py

I actually no longer think that these methods would ever return a circuit with unitary gates, so it does not really matter

alexanderivrii · 2025-04-30T09:59:08Z

For the purposes of this PR, I changed back to using the existing to_dag and to_circuit. Indeed, in the discussed S/H-case we just get back the empty circuit, which is the correct answer (for some reason I thought that this is not what would happen). I don't think anymore that the main run method of Solovay-Kitaev can return a circuit with a unitary gate, so this change does not even matter.

For the record: I do think that it would be best to simplify the arguments to different functions (those that need to take matrices should take matrices and not gate sequences), however I agree with you that there is no point to work on this in the Python space, as we are in the process of replacing this code by a much better Rust version.

releasenotes/notes/fix-sk-decomposition-23da3ee4b6a10d62.yaml

…ings

releasenotes/notes/fix-sk-decomposition-23da3ee4b6a10d62.yaml

Co-authored-by: Julien Gacon <gaconju@gmail.com>

Cryoris

LGTM thanks for integrating the fixes!

mtreinish · 2025-05-05T15:48:18Z

@Mergifyio backport stable/1.4

mergify · 2025-05-05T15:48:57Z

backport stable/1.4

✅ Backports have been created

#14294 Bug fixes in Solovay Kitaev Decomposition (backport #14217) has been created for branch stable/1.4 but encountered conflicts

* Fix _compute_rotation_axis method The method used to return [0, 0, 0] for rotation axis when theta is very close to 0 (and yet not within 1e010). This commit fixes this by noting that the rotation axis of an SO(3) matrix is simply the eigenvector of this matrix corresponding to eigenvalue 1. * Fixes related to SU(2) vs. SO(3) The implemented algorithm has a global phase uncertainty of +-1, due to approximating not the original SU(2) matrix but its projection onto SO(3). This fixes the global phase of the computed approximation. In addition, the product_su2 matrix in GateSequence was not correctly computed in many cases, leading to incorrect values when using this attribute. Since this is not needed for the actual algorithm (and spends unnecessary effort for computing it), this also completely removes this attribute. Co-authored-by: Almudena Carrera Vazquez <almudenacarreravazquez@hotmail.com> * Fix the tests. One of the tests was simply wrong because the reference circuit has the wrong global phase. The tests that check the gates in the final decomposition should not assume that SGate is included and SdgGate is not. * reno * fix to the global phase * bug fix (forgetting that gate_matrix_su2 is not SU(2) was a sequence) * adding test * Restoring the previous fast code for _compute_rotation_axis based on Rodrigues formula, while additionally handling the case of 180-degree rotation * removing old code * review comments * switching back to using _to_dag and _to_circuit I actually no longer think that these methods would ever return a circuit with unitary gates, so it does not really matter * Addressing review comments * pass over release notes combining the original and the suggested wordings * Update releasenotes/notes/fix-sk-decomposition-23da3ee4b6a10d62.yaml Co-authored-by: Julien Gacon <gaconju@gmail.com> --------- Co-authored-by: Almudena Carrera Vazquez <almudenacarreravazquez@hotmail.com> Co-authored-by: Julien Gacon <gaconju@gmail.com> (cherry picked from commit 6892608) # Conflicts: # test/python/transpiler/test_solovay_kitaev.py

* Fix _compute_rotation_axis method The method used to return [0, 0, 0] for rotation axis when theta is very close to 0 (and yet not within 1e010). This commit fixes this by noting that the rotation axis of an SO(3) matrix is simply the eigenvector of this matrix corresponding to eigenvalue 1. * Fixes related to SU(2) vs. SO(3) The implemented algorithm has a global phase uncertainty of +-1, due to approximating not the original SU(2) matrix but its projection onto SO(3). This fixes the global phase of the computed approximation. In addition, the product_su2 matrix in GateSequence was not correctly computed in many cases, leading to incorrect values when using this attribute. Since this is not needed for the actual algorithm (and spends unnecessary effort for computing it), this also completely removes this attribute. Co-authored-by: Almudena Carrera Vazquez <almudenacarreravazquez@hotmail.com> * Fix the tests. One of the tests was simply wrong because the reference circuit has the wrong global phase. The tests that check the gates in the final decomposition should not assume that SGate is included and SdgGate is not. * reno * fix to the global phase * bug fix (forgetting that gate_matrix_su2 is not SU(2) was a sequence) * adding test * Restoring the previous fast code for _compute_rotation_axis based on Rodrigues formula, while additionally handling the case of 180-degree rotation * removing old code * review comments * switching back to using _to_dag and _to_circuit I actually no longer think that these methods would ever return a circuit with unitary gates, so it does not really matter * Addressing review comments * pass over release notes combining the original and the suggested wordings * Update releasenotes/notes/fix-sk-decomposition-23da3ee4b6a10d62.yaml Co-authored-by: Julien Gacon <gaconju@gmail.com> --------- Co-authored-by: Almudena Carrera Vazquez <almudenacarreravazquez@hotmail.com> Co-authored-by: Julien Gacon <gaconju@gmail.com> (cherry picked from commit 6892608)

* Bug fixes in Solovay Kitaev Decomposition (#14217) * Fix _compute_rotation_axis method The method used to return [0, 0, 0] for rotation axis when theta is very close to 0 (and yet not within 1e010). This commit fixes this by noting that the rotation axis of an SO(3) matrix is simply the eigenvector of this matrix corresponding to eigenvalue 1. * Fixes related to SU(2) vs. SO(3) The implemented algorithm has a global phase uncertainty of +-1, due to approximating not the original SU(2) matrix but its projection onto SO(3). This fixes the global phase of the computed approximation. In addition, the product_su2 matrix in GateSequence was not correctly computed in many cases, leading to incorrect values when using this attribute. Since this is not needed for the actual algorithm (and spends unnecessary effort for computing it), this also completely removes this attribute. Co-authored-by: Almudena Carrera Vazquez <almudenacarreravazquez@hotmail.com> * Fix the tests. One of the tests was simply wrong because the reference circuit has the wrong global phase. The tests that check the gates in the final decomposition should not assume that SGate is included and SdgGate is not. * reno * fix to the global phase * bug fix (forgetting that gate_matrix_su2 is not SU(2) was a sequence) * adding test * Restoring the previous fast code for _compute_rotation_axis based on Rodrigues formula, while additionally handling the case of 180-degree rotation * removing old code * review comments * switching back to using _to_dag and _to_circuit I actually no longer think that these methods would ever return a circuit with unitary gates, so it does not really matter * Addressing review comments * pass over release notes combining the original and the suggested wordings * Update releasenotes/notes/fix-sk-decomposition-23da3ee4b6a10d62.yaml Co-authored-by: Julien Gacon <gaconju@gmail.com> --------- Co-authored-by: Almudena Carrera Vazquez <almudenacarreravazquez@hotmail.com> Co-authored-by: Julien Gacon <gaconju@gmail.com> (cherry picked from commit 6892608) # Conflicts: # test/python/transpiler/test_solovay_kitaev.py * Removing tests added in PR #13690 that was not backported to 1.4 --------- Co-authored-by: Alexander Ivrii <alexi@il.ibm.com> Co-authored-by: Julien Gacon <jules.gacon@googlemail.com> Co-authored-by: Elena Peña Tapia <57907331+ElePT@users.noreply.github.com>

* Fix _compute_rotation_axis method The method used to return [0, 0, 0] for rotation axis when theta is very close to 0 (and yet not within 1e010). This commit fixes this by noting that the rotation axis of an SO(3) matrix is simply the eigenvector of this matrix corresponding to eigenvalue 1. * Fixes related to SU(2) vs. SO(3) The implemented algorithm has a global phase uncertainty of +-1, due to approximating not the original SU(2) matrix but its projection onto SO(3). This fixes the global phase of the computed approximation. In addition, the product_su2 matrix in GateSequence was not correctly computed in many cases, leading to incorrect values when using this attribute. Since this is not needed for the actual algorithm (and spends unnecessary effort for computing it), this also completely removes this attribute. * Fix the tests. One of the tests was simply wrong because the reference circuit has the wrong global phase. The tests that check the gates in the final decomposition should not assume that SGate is included and SdgGate is not. * reno * fix to the global phase * bug fix (forgetting that gate_matrix_su2 is not SU(2) was a sequence) * adding test * Restoring the previous fast code for _compute_rotation_axis based on Rodrigues formula, while additionally handling the case of 180-degree rotation * removing old code * review comments * switching back to using _to_dag and _to_circuit I actually no longer think that these methods would ever return a circuit with unitary gates, so it does not really matter * Addressing review comments * pass over release notes combining the original and the suggested wordings * Update releasenotes/notes/fix-sk-decomposition-23da3ee4b6a10d62.yaml --------- (cherry picked from commit 6892608) Co-authored-by: Alexander Ivrii <alexi@il.ibm.com> Co-authored-by: Almudena Carrera Vazquez <almudenacarreravazquez@hotmail.com> Co-authored-by: Julien Gacon <gaconju@gmail.com> Co-authored-by: Julien Gacon <jules.gacon@googlemail.com>

alexanderivrii and others added 3 commits April 17, 2025 13:57

Fix the tests.

13103ed

One of the tests was simply wrong because the reference circuit has the wrong global phase. The tests that check the gates in the final decomposition should not assume that SGate is included and SdgGate is not.

alexanderivrii requested a review from a team as a code owner April 17, 2025 11:26

alexanderivrii added this to Transpiler Apr 17, 2025

github-project-automation bot moved this to To do in Transpiler Apr 17, 2025

alexanderivrii added this to the 2.1.0 milestone Apr 17, 2025

alexanderivrii added the Changelog: Bugfix Include in the "Fixed" section of the changelog label Apr 17, 2025

alexanderivrii assigned Cryoris Apr 17, 2025

reno

c740b46

alexanderivrii changed the title ~~Sk bug fixes~~ [WIP] Bug fixes in Solovay Kitaev Decomposition Apr 17, 2025

alexanderivrii added 3 commits April 17, 2025 15:02

fix to the global phase

8f99c8f

bug fix (forgetting that gate_matrix_su2 is not SU(2) was a sequence)

b84c194

adding test

fc51409

alexanderivrii changed the title ~~[WIP] Bug fixes in Solovay Kitaev Decomposition~~ Bug fixes in Solovay Kitaev Decomposition Apr 17, 2025

alexanderivrii mentioned this pull request Apr 20, 2025

Clifford+T transpiler pipeline #14225

Merged

Cryoris reviewed Apr 23, 2025

View reviewed changes

alexanderivrii added 3 commits April 24, 2025 10:16

Restoring the previous fast code for _compute_rotation_axis based on …

a8a1954

…Rodrigues formula, while additionally handling the case of 180-degree rotation

removing old code

fdfcc12

review comments

683f127

alexanderivrii requested a review from Cryoris April 24, 2025 08:27

Cryoris reviewed Apr 30, 2025

View reviewed changes

alexanderivrii added 2 commits April 30, 2025 12:23

switching back to using _to_dag and _to_circuit

998b8e0

I actually no longer think that these methods would ever return a circuit with unitary gates, so it does not really matter

Addressing review comments

c0aa5aa

alexanderivrii requested a review from Cryoris April 30, 2025 09:48

Cryoris reviewed Apr 30, 2025

View reviewed changes

releasenotes/notes/fix-sk-decomposition-23da3ee4b6a10d62.yaml Outdated Show resolved Hide resolved

Cryoris reviewed Apr 30, 2025

View reviewed changes

releasenotes/notes/fix-sk-decomposition-23da3ee4b6a10d62.yaml Outdated Show resolved Hide resolved

pass over release notes combining the original and the suggested word…

056e19a

…ings

alexanderivrii requested a review from Cryoris April 30, 2025 14:59

Cryoris reviewed Apr 30, 2025

View reviewed changes

releasenotes/notes/fix-sk-decomposition-23da3ee4b6a10d62.yaml Outdated Show resolved Hide resolved

Update releasenotes/notes/fix-sk-decomposition-23da3ee4b6a10d62.yaml

cea0a0e

Co-authored-by: Julien Gacon <gaconju@gmail.com>

alexanderivrii requested a review from Cryoris May 1, 2025 09:48

kevinhartman modified the milestones: 2.1.0, 1.4.3 May 1, 2025

Cryoris approved these changes May 5, 2025

View reviewed changes

Cryoris added the stable backport potential The bug might be minimal and/or import enough to be port to stable label May 5, 2025

Cryoris added this pull request to the merge queue May 5, 2025

github-merge-queue bot removed this pull request from the merge queue due to failed status checks May 5, 2025

Cryoris added this pull request to the merge queue May 5, 2025

Merged via the queue into Qiskit:main with commit 6892608 May 5, 2025
25 checks passed

github-project-automation bot moved this from To do to done in Transpiler May 5, 2025

mergify bot mentioned this pull request May 5, 2025

Bug fixes in Solovay Kitaev Decomposition (backport #14217) #14294

Merged

mergify bot mentioned this pull request May 5, 2025

Bug fixes in Solovay Kitaev Decomposition (backport #14217) #14295

Merged

alexanderivrii mentioned this pull request May 6, 2025

Fix caching logic in SolovayKitaevSynthesis plugin #14304

Merged

This was referenced May 7, 2025

Fix caching logic in SolovayKitaevSynthesis plugin (backport #14304) #14311

Merged

Fix caching logic in SolovayKitaevSynthesis plugin (backport #14304) #14312

Merged

ShellyGarion added the fault tolerance related to fault tolerance compilation label Jul 9, 2025

Bug fixes in Solovay Kitaev Decomposition #14217

Bug fixes in Solovay Kitaev Decomposition #14217

Uh oh!

Conversation

alexanderivrii commented Apr 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary

Details and comments

Uh oh!

qiskit-bot commented Apr 17, 2025

Uh oh!

jakelishman commented Apr 17, 2025

Uh oh!

coveralls commented Apr 17, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 14773444830

Warning: This coverage report may be inaccurate.

Details

💛 - Coveralls

Uh oh!

alexanderivrii commented Apr 21, 2025

Uh oh!

alexanderivrii commented Apr 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Cryoris left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

alexanderivrii commented Apr 30, 2025

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Cryoris left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

mtreinish commented May 5, 2025

Uh oh!

mergify bot commented May 5, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

✅ Backports have been created

Uh oh!

Uh oh!

Uh oh!

alexanderivrii commented Apr 17, 2025 •

edited

Loading

coveralls commented Apr 17, 2025 •

edited

Loading

alexanderivrii commented Apr 21, 2025 •

edited

Loading

mergify bot commented May 5, 2025 •

edited

Loading