Skip to content

Clifford+T transpiler pipeline #14225

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 53 commits into from
May 21, 2025

Conversation

alexanderivrii
Copy link
Member

@alexanderivrii alexanderivrii commented Apr 20, 2025

Summary

This PR (based on many discussion with @ShellyGarion and many-many-many discussion with @Cryoris) addresses #13695 by providing a transpiler pipeline for transpiling circuits into the discrete basis set of Clifford+T gates.

In many ways this is still a naive approach which misses many potential optimizations that we will consider in follows-ups. However, two goals that this aims to achieve already are:

  1. Approximate non-Clifford single-qubit unitary gates using Solovay-Kitaev decomposition. This step usually requires adding many T/Tdg gates.
  2. If the circuit is already a Clifford or a Clifford+T circuit, do not let the transpiler make it significantly worse.

Related to the first item, this PR is implemented on top of #14217 which provides several fixes to the Solovay-Kitaev decomposition (without which the pass very often raises an exception). Alternatively, the PR could be rebased on top of #14203 instead.

Related to the second item, the two-qubit unitary resynthesis is not currently used (in any of the transpiler stages) as it tends to replace "nice" gate sequences (consisting of few Clifford+T gates) by "very bad" gate sequences (consisting of CX and general-angle rotation gates, that, after applying Solovay-Kitaev decomposition, end up using tons of single-qubit gates). As we have just checked with @ShellyGarion, addressing #14170 does not solve the problem, and as already promised, we will explore potential improvements as follow-up.

This transpiler pipeline would also benefit from #14180 (where the definitions of standard gates with efficient Clifford+T decompositions are updated to use these decompositions), but is not based on top of that.

Functionality-wise, the default plugins for init, translation and optimization stages of the transpiler pipeline now detect whether the given basis set is Clifford+T, in which case the dedicated Clifford+T plugins are used instead.

List of potential follow-ups.

  • Resynthesize sequences of Clifford gates only using Clifford gates. Also resynthesize unitary gates that happen to be Cliffords only using Clifford gates. Maybe a dedicated Clifford resynthesis pass.
  • Reduce sizes of circuits produced in the Solovay-Kitaev decomposition (SKD). There might be an opportunity to modify the SKD algorithm itself to produce shorter sequences (e.g. when a recursive approximation already satisfies the required tolerance). There seem to be opportunities to significantly simplify sequences of Clifford+T gates produced by SKD (maybe using template optimization? maybe using Rustiq? maybe a dedicated transpiler pass?).
  • Implement a Clifford+T optimization transpiler pass for 1q gates.
  • Investigate unitary synthesis algorithms into Clifford+T for two-qubit unitaries
  • Implement other unitary synthesis algorithms (see Implement Ross-Selinger algorithm for Z rotation synthesis #3212 for example)
  • implement a general Clifford+T optimization transpiler pass
  • switch to T-count metric during optimization
  • produce efficient Clifford+T circuits for MCX and Adder gates when the basis set is Clifford+T
  • extending the Target class to support Cliffords natively
  • translate approximation_degree to tolerance for the Solovay-Kitaev decomposition. Adapt SKD to synthesize wrt a given tolerance.

Others ideas and pointers to relevant literature are highly welcome!

alexanderivrii and others added 22 commits April 9, 2025 17:03
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.
@alexanderivrii alexanderivrii added this to the 2.1.0 milestone Apr 20, 2025
@alexanderivrii alexanderivrii requested a review from a team as a code owner April 20, 2025 12:26
@qiskit-bot
Copy link
Collaborator

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

  • @Qiskit/terra-core

…or unitary gates that are Clifford may produce other gates
@coveralls
Copy link

coveralls commented Apr 20, 2025

Pull Request Test Coverage Report for Build 15139959656

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.

Details

  • 67 of 71 (94.37%) changed or added relevant lines in 7 files are covered.
  • 32 unchanged lines in 5 files lost coverage.
  • Overall coverage decreased (-0.007%) to 88.295%

Changes Missing Coverage Covered Lines Changed/Added Lines %
qiskit/transpiler/preset_passmanagers/builtin_plugins.py 27 28 96.43%
qiskit/transpiler/preset_passmanagers/common.py 13 16 81.25%
Files with Coverage Reduction New Missed Lines %
crates/circuit/src/symbol_expr.rs 1 75.31%
crates/qasm2/src/expr.rs 1 94.23%
crates/qasm2/src/lex.rs 3 92.48%
crates/qasm2/src/parse.rs 12 96.68%
qiskit/transpiler/preset_passmanagers/builtin_plugins.py 15 95.22%
Totals Coverage Status
Change from base Build 15094029635: -0.007%
Covered Lines: 78395
Relevant Lines: 88788

💛 - Coveralls

@alexanderivrii
Copy link
Member Author

This is ready for review.

Copy link
Contributor

@Cryoris Cryoris left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks and feels already quite nice (I might be biased lol). I left some comments below, and also:

  • I think it would be really good if we can add optimizations that merge consecutive T gates into S or Z into 2.1 as well, since it looks like it could reduce T count quite a bit
  • Right now SK seems to take precedence over possible basis translations: e.g. transpiling SX into T Tdg S Sdg H could give the Clifford-decomp of the basis translator Sdg H Sdg but it yields H T T H right now

Comment on lines 576 to 577
"t",
"tdg",
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

That would simplify quantum computing quite a bit 😛

Suggested change
"t",
"tdg",

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think that we should have a single place with hard-coded clifford gate names.

perhaps we should use _BASIS_1Q and _BASIS_2Q keys like is done here:

and if we decide to have _CLIFFORD_GATE_NAMES then we should use them in CollectCliffords as well.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

BTW, do we identify RZ gates with certain angles as Clifford? (and similarly other gates). Or do we expect SK to handle this?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Haha, thanks for spotting this!

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

SolovayKitaev should handle that case -- though I think ideally some kind of basis translator would be able to figure this out, which should be less costly than SK

@@ -673,6 +673,9 @@
given :class:`.EquivalenceLibrary` (typically the :data:`.SessionEquivalenceLibrary`) to move
towards the ISA.

For a Clifford+T basis set, the single-qubit rotation gates are approximated using the
Solovay-Kitaev algorithm.
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Maybe add a hyperref to the SolovayKitaev class used for this? 🙂

Copy link
Member

@ShellyGarion ShellyGarion left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for this important work. I have a few comments and questions.

@@ -797,6 +797,17 @@ def _cnot_rxx_decompose(plus_ry: bool = True, plus_rxx: bool = True):
def_s.append(U1Gate(pi / 2), [q[0]], [])
_sel.add_equivalence(SGate(), def_s)

# SGate
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think that for ZGate we already have the identity: Z = S S but we don't have Z = Sdg Sdg. Is it worth to add it?

Will these identities imply that T T T T (or Tdg Tdg Tdg Tdg) will be replaced by Z ?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

That's a good point. For now, I have added the minimal amount of equivalences to make this PR work, but we are definitely missing some of the important equivalences. Going forward, I think that by far the best strategy is to include @jakelishman's BasisConstructor pass (together with the corresponding library), Jake did a really nice job at thinking through the hierarchy of equivalences that we should add to the circuit library.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't think these identities enable T T T T -> Z since the basis translator only contains 1 -> N relations and cannot merge gates. Merging T sequences is planned as follow up (@alexanderivrii already has a draft), hopefully for 2.1.

Comment on lines 576 to 577
"t",
"tdg",
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think that we should have a single place with hard-coded clifford gate names.

perhaps we should use _BASIS_1Q and _BASIS_2Q keys like is done here:

and if we decide to have _CLIFFORD_GATE_NAMES then we should use them in CollectCliffords as well.

optimization = PassManager()
if optimization_level != 0:
_depth_check = [Depth(recurse=True), FixedPoint("depth")]
_size_check = [Size(recurse=True), FixedPoint("size")]
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

is there an optimization for specific gate of type of gates?
I thought that usually we aim to optimize 2q gates (CX, CZ, RZZ). and in this case we should optimize non-clifford (T, Tdg) gates.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I agree, but again I think it's something we should pursue in a follow-up. Anyhow, for the current set of Clifford+T optimization passes, all of the metrics are the same.

Comment on lines 576 to 577
"t",
"tdg",
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

BTW, do we identify RZ gates with certain angles as Clifford? (and similarly other gates). Or do we expect SK to handle this?

from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit.quantum_info import get_clifford_gate_names

basis_gates = get_clifford_gate_names() + ["t", "tdg"]
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

perhaps in the example we would like to fix the basis gates, e.g. [cx, h, t, tdg]

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

btw, do we assume that the clifford gates are hard-coded? can the user define their own clifford gate and provide it (say as clifford tableaux)?

Copy link
Member Author

@alexanderivrii alexanderivrii May 20, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

One of the points of the example is to use get_clifford_gate_names to get the list of all standard Clifford gate names in Qiskit. Most users will probably want to include as many Clifford gates as possible, and this example illustrates how this can be done. Of course, the users can specify their own gate lists, such as ["h", "t", "tdg"]or even ["h", "t"], please see the last paragraph in the release notes.

So far in all of the transpiler passes basis_gates is a list of strings, and we probably do not want to generalize this. However, your comment is very relevant for extending the Target class for supporting Clifford+T gates in a form that is hopefully better than just listing all the Clifford gate names.

)
transpiled = pm.run(qc)
self.assertLessEqual(set(transpiled.count_ops()), set(basis_gates))

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

in this case, one should use only clifford gates for the transpilation?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

That would be true with the Clifford plugin I mentioned somewhere, but not yet. For efficiency, we are currently running the Solovay-Kitaev synthesis algorithm with the basis set ["h", "t", "tdg"], so even pure Clifford gates would be transpiled into this basis. Note that you could run the SK algorithm with a much larger set of basis gates, like all Clifford gates + T/Tdg, however at least the python implementation becomes significantly slower. This is something to revisit when the SK algorithm is ported to Rust.

@@ -1003,3 +1021,63 @@ def _get_trial_count(default_trials=5):
if CONFIG.get("sabre_all_threads", None) or os.getenv("QISKIT_SABRE_ALL_THREADS"):
return max(default_num_processes(), default_trials)
return default_trials


class CliffordTOptimizationPassManager(PassManagerStagePlugin):
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Do you use somewhere the CollectClliffords transpiler pass? I think it can collect parametrized gates that are clifford only for certain parameters.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Good point. I am not using this yet. Again this relates to the point that in the future we want to have Clifford and Clifford+T circuit resynthesis methods.

basis_gates=basis_gates, optimization_level=optimization_level
)
transpiled = pm.run(qc)
self.assertLessEqual(set(transpiled.count_ops()), set(basis_gates))
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

in this case, one should use only clifford gates for the transpilation?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Same answer as before. :)

requiring the usage of the Solovay-Kitaev decomposition.
"""
qc = QuantumCircuit(1)
qc.rx(0.8, 0)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

if the angle is a multiplication of pi/2, does it know to use only clifford gates?
if the angle is a multiplication of pi/4, does it know to use only clifford and t/tdg gates?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

For the pi/4 angle, if the basis set is Clifford+T, the flow by definition will only use Clifford+T/Tdg gates. But you are correct, the SK algorithm will be exact and produce a very short sequence of gates. I am adding a test for that. I don't want to add a similar test for pi/2 angle before we can guarantee (again using the future Clifford resynthesis plugin) that there will be only Clifford gates in the result.


# Should get the efficient decomposition of the Toffoli gates into Clifford+T.
self.assertEqual(transpiled.count_ops(), {"cx": 6, "t": 4, "tdg": 3, "h": 2})

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

these are very nice examples! perhaps we can consider adding more advanced ones, like c3x, c4x, mcx or certain adders?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

As I have already mentioned somewhere, producing efficient circuits is something we want to do, but this requires a bit more work that we want to do in a follow-up. First, we need to make sure that all the standard definitions for gates like c3x, c4x only use Clifford+T gates (I have an open PR on that somewhere), and then we need to update HighLevelSynthesis plugins to always choose Clifford+T synthesis algorithms when available.

@alexanderivrii
Copy link
Member Author

For some reason there are comments to which I can't seem to comment back, so I will include my replies here as I go through them.

@Cryoris:

I think it would be really good if we can add optimizations that merge consecutive T gates into S or Z into 2.1 as well, since it looks like it could reduce T count quite a bit

I am planning to submit a follow-up PR shortly.

Right now SK seems to take precedence over possible basis translations: e.g. transpiling SX into T Tdg S Sdg H could give the Clifford-decomp of the basis translator Sdg H Sdg but it yields H T T H right now

I agree and this is something I definitely want to improve in the future. In fact, in the previous version of this PR I have modified the Solovay-Kitaev unitary synthesis plugin to detect when a 1q-gate is Clifford, in which case to use a Clifford resynthesis algorithm rather than Solovay-Kitaev. However, I have later removed this optimization since the resynthesized circuit did not adhere to the basis set passed to Solovay-Kitaev. We should think what is the best way to include this optimization (but in a follow-up): another unitary synthesis plugin? standalone pass?

@ShellyGarion:

perhaps we should use _BASIS_1Q and _BASIS_2Q keys like is done here:

This is exactly how I have implemented this at first, before I have found out that some of the gate names in _BASIS_1Q and _BASIS_2Q are not standard gate names, e.g., i, iden, v, w.

and if we decide to have _CLIFFORD_GATE_NAMES then we should use them in CollectCliffords as well.

I can do this, if you want me to, though I feel that this change is somewhat unrelated to this PR.

BTW, do we identify RZ gates with certain angles as Clifford? (and similarly other gates). Or do we expect SK to handle this?

Yes. Or the future Clifford resynthesis plugin I mentioned earlier.

@alexanderivrii
Copy link
Member Author

alexanderivrii commented May 20, 2025

@ShellyGarion, I have added your comments on potential followups in the PR's description. If you think that some ideas are missing, please update the description as you see fit.

Copy link
Member

@ShellyGarion ShellyGarion left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM :)

``["h", "t", "tdg"]``or even ``["h", "t"]`` is sufficient for universality,
it is recommended to add more Clifford gates to the set if possible, as
otherwise the translation might be less efficient. For example, not including
S-gate might trigger decomposing S-gates into pairs of T-gates (that is,
decomposing Clifford gates into non-Clifford gates, which might not be the
desired behavior).

Here is an additional slightly larger example::
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

2 examples are a bit overkill IMO, I think the top one is good enough (you could add a second gate there if you wanted or something)

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Shelly was specifically asking for an example over multiple qubits 😄. But actually the two examples are slightly different: the first uses get_clifford_get_names, and the second a custom Clifford+T basis.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The release manager shall rule 😄

@Cryoris Cryoris added this pull request to the merge queue May 21, 2025
@Cryoris Cryoris added the Changelog: New Feature Include in the "Added" section of the changelog label May 21, 2025
Merged via the queue into Qiskit:main with commit 99aa39e May 21, 2025
25 checks passed
rahaman-quantum pushed a commit to rahaman-quantum/qiskit that referenced this pull request Jun 20, 2025
* experiments

* experiment

* clifford plugin

* optimization

* optimization loop

* remove consolidate

* 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

* Undoing changes to SK

* cleanup

* Adding tests for discrete pass manager pipeline

* adding generate_discrete_passmanager to init files

* simplifying import

* another test

* release note

* Fixing tests: with the change to SK plugin, the synthesis algorithm for unitary gates that are Clifford may produce other gates

* In SolovayKitaevSynthesis unitary synthesis plugin now storing a dictionary from the basis set to the SolovayKitaevDecomposition

* adding explicit test

* lint

* remove prints

* renaming

* modifying the default init/translation/optimization pass manager stage plugins to detect whether we are transpiling into a Clifford+T basis, in which we call the dedicated stage plugins. In addition, removing the function generate_clifford_t_pass_manager

* deleting blank line (randomly introduced at some point)

* change to function that checks if basis is Clifford+T

* make Clifford synthesis inside SolovayKitaevSynthesis plugin respect basis gates; fix tests

* pass over tests

* removing the Clifford synthesis part for now

* Improving is_clifford_t_basis check

* makung sure GateDirection pass is implied

* unused imports

* cleanup

* Adding Julien as co-author (and fixing a small typo)

Co-authored-by: Julien Gacon <jules.gacon@googlemail.com>

* lint and is_clifford_t

* fixing pipeline to support more general Clifford+T bases; adding tests

* fix tests; add test with Target

* computing whether the basis set is clifford_t only once; caching the result

* cleanup; improving release notes; varying optimization_level in tests

* restoring ccx test

* removing code duplication

* simplifying how Clifford+T code is called

* updating transpiler documentation

* addressing review comments

* adding a larger example to releasenotes

---------

Co-authored-by: Almudena Carrera Vazquez <almudenacarreravazquez@hotmail.com>
Co-authored-by: Julien Gacon <jules.gacon@googlemail.com>
@ShellyGarion ShellyGarion added the fault tolerance related to fault tolerance compilation label Jul 9, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Changelog: New Feature Include in the "Added" section of the changelog fault tolerance related to fault tolerance compilation
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Easier compilation to discrete basis sets
5 participants