-
Notifications
You must be signed in to change notification settings - Fork 2.6k
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
Clifford+T transpiler pipeline #14225
Conversation
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.
One or more of the following people are relevant to this code:
|
…or unitary gates that are Clifford may produce other gates
Pull Request Test Coverage Report for Build 15139959656Warning: 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
💛 - Coveralls |
…ionary from the basis set to the SolovayKitaevDecomposition
This is ready for review. |
There was a problem hiding this 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
intoT Tdg S Sdg H
could give the Clifford-decomp of the basis translatorSdg H Sdg
but it yieldsH T T H
right now
"t", | ||
"tdg", |
There was a problem hiding this comment.
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 😛
"t", | |
"tdg", |
There was a problem hiding this comment.
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:
clifford_gate_names = ( |
and if we decide to have _CLIFFORD_GATE_NAMES
then we should use them in CollectCliffords as well.
There was a problem hiding this comment.
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?
There was a problem hiding this comment.
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!
There was a problem hiding this comment.
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
qiskit/transpiler/__init__.py
Outdated
@@ -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. |
There was a problem hiding this comment.
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? 🙂
releasenotes/notes/add-clifford-t-transpiler-pipeline-e640b5ba64eab13a.yaml
Outdated
Show resolved
Hide resolved
There was a problem hiding this 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 |
There was a problem hiding this comment.
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 ?
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
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.
"t", | ||
"tdg", |
There was a problem hiding this comment.
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:
clifford_gate_names = ( |
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")] |
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
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.
"t", | ||
"tdg", |
There was a problem hiding this comment.
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"] |
There was a problem hiding this comment.
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]
There was a problem hiding this comment.
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)?
There was a problem hiding this comment.
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)) | ||
|
There was a problem hiding this comment.
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?
There was a problem hiding this comment.
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): |
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
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)) |
There was a problem hiding this comment.
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?
There was a problem hiding this comment.
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) |
There was a problem hiding this comment.
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?
There was a problem hiding this comment.
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}) | ||
|
There was a problem hiding this comment.
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?
There was a problem hiding this comment.
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.
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.
I am planning to submit a follow-up PR shortly.
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?
This is exactly how I have implemented this at first, before I have found out that some of the gate names in
I can do this, if you want me to, though I feel that this change is somewhat unrelated to this PR.
Yes. Or the future Clifford resynthesis plugin I mentioned earlier. |
@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. |
There was a problem hiding this 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:: |
There was a problem hiding this comment.
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)
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
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 😄
* 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>
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:
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
andoptimization
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.
Target
class to supportCliffords
nativelyapproximation_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!