Support any two qubit gates

[JoachimMarin]

Description

These changes aim to better support arbitrary two qubit gates in the mapping process. This is done by generalizing from cnot gates to any controlled gates:

1. Remove the assertion in countGates that ensures all controlled gates are cnot gates
2. When writing two qubit gates in the mapped circuit, use the operation type of the original circuit instead of always inserting cnot
3. Adjust messages and variable naming to reflect the change from cnot to arbitrary controlled gates

In bindings.cpp, I also renamed cnots to two_qubit_gates. I guess this would be a breaking change with python projects using qmap. I think the best course of action would be to keep both and mark cnots as deprecated.

Until qfr is updated some gates like controlled u gates will produce incorrect OpenQASM code resulting in Qiskit failing to read the mapped circuit and throwing exceptions in Python.

I'm not sure, if any further changes are required to support any two qubit gates, but I hope this serves as a good starting point.

Checklist:

• [x] The pull request only contains commits that are related to it.
• [ ] I have added appropriate tests and documentation.
• [ ] I have made sure that all CI jobs on GitHub pass.
• [x] The pull request introduces no new warnings and follows the project's style guidelines.

[codecov[bot]]

Codecov Report

Merging #235 (34cc4bd) into main (b63c2c8) will increase coverage by 0.3%. The diff coverage is 85.5%.

@@           Coverage Diff           @@
##            main    #235     +/-   ##
=======================================
+ Coverage   91.9%   92.2%   +0.3%     
=======================================
  Files         44      44             
  Lines       3744    3825     +81     
  Branches     621     628      +7     
=======================================
+ Hits        3444    3530     +86     
+ Misses       300     295      -5     

Flag	Coverage Δ
cpp	91.8% <85.5%> (+0.3%)	:arrow_up:
python	95.9% <ø> (ø)

Flags with carried forward coverage won't be shown. Click here to find out more.

Impacted Files	Coverage Δ
include/utils.hpp	80.0% <ø> (ø)
include/MappingResults.hpp	74.5% <28.5%> (ø)
src/Architecture.cpp	93.2% <83.6%> (-1.8%)	:arrow_down:
src/heuristic/HeuristicMapper.cpp	94.6% <84.2%> (+1.4%)	:arrow_up:
src/exact/ExactMapper.cpp	98.0% <85.3%> (-0.4%)	:arrow_down:
src/Mapper.cpp	88.7% <88.0%> (-0.4%)	:arrow_down:
include/Architecture.hpp	88.7% <100.0%> (+0.7%)	:arrow_up:
include/Mapper.hpp	84.6% <100.0%> (+22.1%)	:arrow_up:
include/heuristic/HeuristicMapper.hpp	87.0% <100.0%> (+0.6%)	:arrow_up:
src/utils.cpp	90.0% <100.0%> (+<0.1%)	:arrow_up:

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.

[burgholzer]

Just a few comments at the end of the day:

Many thanks for this addition. I think this is a great step into the right direction. One of the bigger questions that popped up is already summarised in the comment above.

In addition, I was thinking that it shouldn't be that hard to get arbitrary two-qubit gates to work (i.e., not only controlled gates, but maybe also something like an iSWAP gate or Google's fsim gate). Essentially, one has to look for places where a control and a target are expected and add some extra case handling if the considered operation has two targets and no controls.

I was also wondering whether it would make sense to switch to a dictionary or separate counts for the individual two-qubit gates. Some devices, e.g., those offered by Rigetti offer multiple two-qubit gates (cz, cp, xy). These gates frequently have different error rates and, hence, contribute differently to the overall quality of the circuit. That would also somewhat avoid the need for deprecations. Maybe this is the point where it would be worth to really add "basis_gates" to the Architectures in QMAP (similar to how Qiskit does this) and keep track of their counts.

Last but not least, it would be great to add some tests on the C++ side, that do try to map circuits with two-qubit gates that are not CNOTs and assert that the produced results make sense.

These are all just rather general thoughts. Let me know if they make sense. I'd also be happy if this were done step by step in a series of PRs; taking this one here as the first step.

[JoachimMarin]

In addition, I was thinking that it shouldn't be that hard to get arbitrary two-qubit gates to work (i.e., not only controlled gates, but maybe also something like an iSWAP gate or Google's fsim gate). Essentially, one has to look for places where a control and a target are expected and add some extra case handling if the considered operation has two targets and no controls.

I haven't looked that deep into qmap yet, so it's hard for me to comment on this. I would guess that the mapping algorithm doesn't care much about the semantics of the gates, so whether there are two targets or one target and one control shouldn't matter too much.

I was also wondering whether it would make sense to switch to a dictionary or separate counts for the individual two-qubit gates. Some devices, e.g., those offered by Rigetti offer multiple two-qubit gates (cz, cp, xy). These gates frequently have different error rates and, hence, contribute differently to the overall quality of the circuit. That would also somewhat avoid the need for deprecations. Maybe this is the point where it would be worth to really add "basis_gates" to the Architectures in QMAP (similar to how Qiskit does this) and keep track of their counts.

I'm not sure I understand. Are you talking about the CircuitInfo struct inside MappingResults? I would assume that the number of gates before and after the mapping are generally very similar, with the mapped circuit simply having more Hadamard or Swap gates that are used to perform the mapping. The count of a specific gate like cp doesn't seem that relevant as it should be the same before and after the mapping, right?

[burgholzer]

In addition, I was thinking that it shouldn't be that hard to get arbitrary two-qubit gates to work (i.e., not only controlled gates, but maybe also something like an iSWAP gate or Google's fsim gate). Essentially, one has to look for places where a control and a target are expected and add some extra case handling if the considered operation has two targets and no controls.

I haven't looked that deep into qmap yet, so it's hard for me to comment on this. I would guess that the mapping algorithm doesn't care much about the semantics of the gates, so whether there are two targets or one target and one control shouldn't matter too much.

Yeah, the mapping algorithm itself does not really care; it's all about connectivity. But the current code base does 🙃 There are explicit places where it is assumed that if a gate has no controls, it must be a single-qubit gate. Or, vice verse, where a two-qubit gate is always expected to have a control. It would be great to isolate and eliminate these (unnecessary) assumptions.

[burgholzer]

I was also wondering whether it would make sense to switch to a dictionary or separate counts for the individual two-qubit gates. Some devices, e.g., those offered by Rigetti offer multiple two-qubit gates (cz, cp, xy). These gates frequently have different error rates and, hence, contribute differently to the overall quality of the circuit. That would also somewhat avoid the need for deprecations. Maybe this is the point where it would be worth to really add "basis_gates" to the Architectures in QMAP (similar to how Qiskit does this) and keep track of their counts.

I'm not sure I understand. Are you talking about the CircuitInfo struct inside MappingResults? I would assume that the number of gates before and after the mapping are generally very similar, with the mapped circuit simply having more Hadamard or Swap gates that are used to perform the mapping. The count of a specific gate like cp doesn't seem that relevant as it should be the same before and after the mapping, right?

As for the mapping itself, I tend to agree. Since it is all about the connectivity of the circuit, the existing gates will (more or less) stay the same. Probably, it is just that the result would then more closely follow what Qiskit is doing, i.e., providing a dictionary of gate counts. In addition, these counts can start to change by quite a bit if you take optimizations into account (e.g., gate cancellation, gate fusion). As an example: it is known that a swap followed/preceded by a CNOT on the same qubits can be reduced to 2 CNOTS (instead of 3+1). Also the swap gate itself is not native to any device I know of. this means, in the end, it has to be decomposed again to the native gate set of the device in question.

[JoachimMarin]

I implemented the basic case distinction we talked about to flip control and target. Current problems:

• I only added special cases for the already discussed gates cx and cz. Would need to research which other gates behave the same.
• I didn't update costs yet. Problem is, that the Architecture uses COST_DIRECTION_REVERSE without considering the current gate when using Dijkstra::buildTable. It's also used here, but there we could add a case distinction, because there is gate context. The usages of GATES_OF_DIRECTION_REVERSE also all have gate context.

[JoachimMarin]

Thanks for the detailed feedback. How would these tests look like? Especially for the heuristic mapper the output isn't necessarily deterministic, so comparing the mapped OpenQASM code to the expected result may not always work. I guess if the circuit is small enough, you could get deterministic results.

[burgholzer]

Thanks for the detailed feedback. How would these tests look like? Especially for the heuristic mapper the output isn't necessarily deterministic, so comparing the mapped OpenQASM code to the expected result may not always work. I guess if the circuit is small enough, you could get deterministic results.

Good question. I think it could be a collection of really small test circuits and constructed examples, where one definitely know what's best (even for the heuristic mapper). A couple of things I could think of:

• making sure that all new kinds of two-qubit gates can be processed by the mapper without error
• making sure that gates are inverted properly in the mapping (e.g., a controlled-Z does not get Hadamards added)
• making sure that the resulting circuit is still functionally equivalent to the original circuit (best done on the Python side, where similar checks are already included in the test/python folder using our QCEC library)
• for the exact mapper: checking that the direction reverse option for the additional two-qubit gates is actually picked up properly and used.

The list above is probably incomplete, but should give you a rough idea of where to go.

[JoachimMarin]

Sorry for the long delay. I had some troubles with the tests. After making my changes, the existing python tests no longer passed. The reason for that is, that I defaulted to swap for direction reverse in the distance table (the only place where there is no gate context when calculating costs), so the mapping resulted in a different circuit. Changing the distance table to use the hadamard direction reverse keeps the results the same as before and makes the tests pass. However, the reason the tests failed are not related to my changes and were simply triggered by a different circuit being fed to the verify function of qcec. The problem can be reproduced in python by installing qcec from pip, so it's certainly not related to any of my changes. Here is the problematic code:

def example():
    qc1 = QuantumCircuit(3)
    qc1.h(0)
    qc1.cx(0, 1)
    qc1.cx(1, 2)
    qc1.measure_all()

    qc2 = QuantumCircuit(5, 3)
    qc2.h(1)
    qc2.cx(1, 0)
    qc2.swap(0, 2)
    qc2.cx(2, 4)
    qc2.barrier()
    qc2.measure(1, 0)
    qc2.measure(2, 1)
    qc2.measure(4, 2)

    result23 = verify(qc2, qc2)

    qc3 = QuantumCircuit(5, 3)
    qc3.h(1)
    qc3.h(2)
    qc3.cx(1, 0)
    qc3.h(0)
    qc3.cx(2, 0)
    qc3.h(0)
    qc3.h(2)
    qc3.measure(1, 0)
    qc3.measure(0, 1)
    qc3.measure(2, 2)

    result13 = verify(qc1, qc3)
    print("1 and 3 works:", result13)

    result12 = verify(qc1, qc2)
    print("1 and 2 works:", result12)

I constructed this example based on the tests in qmap. Here qc1 is the original circuit, qc2 is the mapped circuit when using the swap direction reverse for the distance table and qc3 is the mapped circuit when using the hadamard direction reverse for the distance table. verify(qc1, qc3) works, while verify(qc1, qc2) triggers a segmentation fault. verify(qc2, qc2) fails with an exception:

terminate called after throwing an instance of 'std::out_of_range'
  what():  map::at

Is there something wrong with qc2? In particular the measure part, because replacing them with measure_all gets rid of any problems. I also tested without the swap, because it's not present in the other circuits, but even without it the same problems appear.

[burgholzer]

Sorry for the long delay. I had some troubles with the tests. After making my changes, the existing python tests no longer passed.

The reason for that is, that I defaulted to swap for direction reverse in the distance table (the only place where there is no gate context when calculating costs), so the mapping resulted in a different circuit. Changing the distance table to use the hadamard direction reverse keeps the results the same as before and makes the tests pass. However, the reason the tests failed are not related to my changes and were simply triggered by a different circuit being fed to the verify function of qcec.

The problem can be reproduced in python by installing qcec from pip, so it's certainly not related to any of my changes.

Here is the problematic code:

def example():

    qc1 = QuantumCircuit(3)

    qc1.h(0)

    qc1.cx(0, 1)

    qc1.cx(1, 2)

    qc1.measure_all()



    qc2 = QuantumCircuit(5, 3)

    qc2.h(1)

    qc2.cx(1, 0)

    qc2.swap(0, 2)

    qc2.cx(2, 4)

    qc2.barrier()

    qc2.measure(1, 0)

    qc2.measure(2, 1)

    qc2.measure(4, 2)



    result23 = verify(qc2, qc2)



    qc3 = QuantumCircuit(5, 3)

    qc3.h(1)

    qc3.h(2)

    qc3.cx(1, 0)

    qc3.h(0)

    qc3.cx(2, 0)

    qc3.h(0)

    qc3.h(2)

    qc3.measure(1, 0)

    qc3.measure(0, 1)

    qc3.measure(2, 2)



    result13 = verify(qc1, qc3)

    print("1 and 3 works:", result13)



    result12 = verify(qc1, qc2)

    print("1 and 2 works:", result12)

I constructed this example based on the tests in qmap. Here qc1 is the original circuit, qc2 is the mapped circuit when using the swap direction reverse for the distance table and qc3 is the mapped circuit when using the hadamard direction reverse for the distance table.

verify(qc1, qc3) works, while verify(qc1, qc2) triggers a segmentation fault.

verify(qc2, qc2) fails with an exception:

terminate called after throwing an instance of 'std::out_of_range'

  what():  map::at

Is there something wrong with qc2? In particular the measure part, because replacing them with measure_all gets rid of any problems. I also tested without the swap, because it's not present in the other circuits, but even without it the same problems appear.

No worries. That seems like a small bug in QCEC to me. Probably something related to how the Output Permutation is determined there. I'll look into that on Monday at the latest and get back to you (also on the other things in your message).

[burgholzer]

@JoachimMarin had some time today to check the above circuits. Can confirm that there is a small bug in the ZX equivalence checker in QCEC. See https://github.com/cda-tum/qcec/issues/251 for the tracking issue. You can temporarily work around the issue by disabling the ZX checker (pass run_zx_checker=False to the verify function). The issue should be fixed over the course of the week.

A note on the circuits though: As they are, qc2 and qc3 will never be equivalent to qc1 since they lack initial layout information. Qiskit (and QMAP) add that information during transpilation in the qc._layout member.

Another small remark: it would be great if you could resolve the conflicts with the main branch and update this branch with the latest changes from main. I'll try to look at the changes over the course of the week.

[JoachimMarin]

A note on the circuits though: As they are, qc2 and qc3 will never be equivalent to qc1 since they lack initial layout information. Qiskit (and QMAP) add that information during transpilation in the qc._layout member.

I'm aware of that. I haven't had any issues in terms of correctness so far with qcec. I only constructed this example to show the seg fault and exception.

Another small remark: it would be great if you could resolve the conflicts with the main branch and update this branch with the latest changes from main. I'll try to look at the changes over the course of the week.

I merged the changes of main into this branch. I'm having problems with ruff at the moment. It told me to put the Instructions import in a TYPE_CHECKING guard because it's technically not required at runtime, but it's necessary for the test collection.

[burgholzer]

A note on the circuits though: As they are, qc2 and qc3 will never be equivalent to qc1 since they lack initial layout information. Qiskit (and QMAP) add that information during transpilation in the qc._layout member.

I'm aware of that. I haven't had any issues in terms of correctness so far with qcec. I only constructed this example to show the seg fault and exception.

Right. Thanks for that. Someone from the team is on it!

Another small remark: it would be great if you could resolve the conflicts with the main branch and update this branch with the latest changes from main. I'll try to look at the changes over the course of the week.

I merged the changes of main into this branch. I'm having problems with ruff at the moment. It told me to put the Instructions import in a TYPE_CHECKING guard because it's technically not required at runtime, but it's necessary for the test collection.

That's unfortunate. However, I think you could get around that by not using Callable and the gate methods of the QuantumCircuit class, but rather directly use the respective Qiskit gates, as shown here https://qiskit.org/documentation/apidoc/circuit_library.html#standard-gates If ruff still complains, I'd be fine with putting a corresponding noqa statement on that import to silence the warning (in favor of using Any for typing, which is terrible).

[JoachimMarin]

Yeah, using the gate objects is much cleaner than the callables I had.

I'm still not fully satisfied. I wanted to use import qiskit.circuit.library as qcl, so the parametrization is not as verbose: https://github.com/cda-tum/qmap/blob/219eda2e60a030a74bae85b8b6bdbf198987a4a4/test/python/test_exact_mapper.py#L125-L143 If I do that however, qiskit.circuit.ControlledGate becomes the only thing that requires import qiskit, so ruff again complains that I should use TYPE_CHECKING, which breaks the tests.

[JoachimMarin]

Regarding the failing tests, I assume the CSdg is too new for Min Qiskit Test, so I can remove it. I don't know why the tests specifically fails for CRZ on ubuntu. I'm using ubuntu too and all tests pass, so it's hard to debug for me. I guess we should first check whether the ubuntu tests result in different mapped circuits or if just the verify function behaves differently for the same input.

[burgholzer]

If I do that however, qiskit.circuit.ControlledGate becomes the only thing that requires import qiskit, so ruff again complains that I should use TYPE_CHECKING, which breaks the tests.

I think this might be fixed by the update of ruff in https://github.com/cda-tum/qmap/pull/257. You can try locally by changing to version v0.0.254 in the pre-commit-config.yaml.

[burgholzer]

Regarding the failing tests, I assume the CSdg is too new for Min Qiskit Test, so I can remove it. I don't know why the tests specifically fails for CRZ on ubuntu. I'm using ubuntu too and all tests pass, so it's hard to debug for me. I guess we should first check whether the ubuntu tests result in different mapped circuits or if just the verify function behaves differently for the same input.

I'll try and see what I can do about that. I have some ideas that I'd like to try out. I'll get back to you 👍🏼

Edit: Yes, CSdg is to new to be supported by the old qiskit version. However, it can be emulated as CPhase(-pi/2).

[burgholzer]

I just pushed some changes refactoring the tests. Let's see how it goes in the CI. The most notable change was https://github.com/cda-tum/qmap/pull/235/commits/2bd795ecc9faad9e2b8fc0066d1c2a240236b53b#diff-6e119ab7fc0a1c33640478892a0de88927c32b1853edf3c2feac815072f79550R2 Which is why ruff was giving you a hard time. The from __future__ import annotations import is needed for PEP 563 (https://peps.python.org/pep-0563/) to take effect. That PEP adds delayed evaluation of annotations. This will be the default in some upcoming Python version. Until then, the behavior is controlled by the __future__ import.

[JoachimMarin]

I only considered the exact mapper so far. Swap reversals are no longer possible, instead they are realized by swap permutations and disabling reversals in the coupling constraints.

The swap limit is currently problematic, because in my test cases it defaulted to zero with SwapReduction::CouplingLimit, so I disabled the swap limit for them. However, if the swap limit is enabled and too low, no solution can be found.

Originally I used mostly python tests, because they made it easier to analyze the mapped circuit. To still analyze the mapped circuit, I added a function to obtain it: https://github.com/cda-tum/qmap/blob/e71fb87e448a86c25aea74734fe637ea156dd0a4/include/Mapper.hpp#L257 And then loop over the gates: https://github.com/cda-tum/qmap/blob/e71fb87e448a86c25aea74734fe637ea156dd0a4/test/test_exact.cpp#L658-L676 Maybe there is a better way to do it?

[burgholzer]

Just pushed some changes that clean up the code, add some more checks, and (most importantly) fixes the coupling limit computation. The computation didn't really take directionality into account. That's why a two-qubit architecture would always have a coupling limit of zero, although a SWAP might be necessary in the directed case. I hope I fixed everything. Some further tests would probably be great here (e.g. on the coupling limit of some directed architectures).

I like the addition of the getter for the mapped circuit.

Unfortunately, there is no gate counting method yet that's similar to Qiskit. Such a function would be convenient though. It would go into the QFR repository, specifically the QuantumComputation class.

[JoachimMarin]

I updated the heuristic mapper, specifically the distance table to support the different costs for direction reversal. The distance table now uses pairs of <double,bool> where the boolean indicates whether a direction reversal is necessary. The distance function now uses the OpType, so that the direction reversal cost can be added depending on the op type.

Inside updateHeuristicCost I used the cost of COST_UNIDIRECTIONAL_SWAP * 2 to guide the heuristic algorithm to make the right choice, but I'm not sure if this is correct.

In general I think there is the danger for both mappers to want to use direction reverse when it's not possible. The exact mapper if the swap limit is too low and the heuristic mapper if it makes a non optimal decision.

[burgholzer]

I updated the heuristic mapper, specifically the distance table to support the different costs for direction reversal. The distance table now uses pairs of <double,bool> where the boolean indicates whether a direction reversal is necessary. The distance function now uses the OpType, so that the direction reversal cost can be added depending on the op type.

Inside updateHeuristicCost I used the cost of COST_UNIDIRECTIONAL_SWAP * 2 to guide the heuristic algorithm to make the right choice, but I'm not sure if this is correct.

Thanks again. I think this needs some further changes to work properly. I just talked to @EliasLF (who is currently working on #218). That PR touches some important parts of the heuristic mapper and fixes some potential bugs. Furthermore, some of the changes there should make the changes here a little easier. Elias agreed to pull out relevant changes from the other PR into separate PRs that can be integrated quickly and act as a better basis for the PR here. I'll postpone a detailed review of the changes here until these updates are in.

In general I think there is the danger for both mappers to want to use direction reverse when it's not possible. The exact mapper if the swap limit is too low and the heuristic mapper if it makes a non optimal decision.

The exact mapper should never run into this risk. The SWAP limit in the default mode is always chosen in a way that a satisfying mapping is possible. If the swap limit is custom set and set too low, the mapper will just return unsat. For the heuristic mapper, this is more of a risk, but it should be possible to avoid that risk by carefully engineering the cost function.

[burgholzer]

Some important changes have made it into main over the last couple of days. Notably

• #274
• #269
• #268
• #264

Some of these changes overlap with the changes here, causing some conflicts. As for the exact mapper, not too much has changed, so the conflicts should be fairly easy to resolve. As for the heuristic mapper, some refactoring has been done that should actually make the necessary changes in this PR a little easier as the computation of the cost for the heuristic is much more localized now. This might require a little more effort to resolve the conflicts. One more thing to take into account: #268 added native support for quite some more two-qubit gates. More specifically:

• DCX
• ECR
• RXX
• RYY
• RZZ
• RZX
• XX_Minus_YY
• XX_Plus_YY

All of these are two-target gates, i.e., they don't have a dedicated control and target. Most of these still have a preferred direction. They should be considered in the direction reversal as well. You can use the verification tab in https://www.cda.cit.tum.de/app/ddvis/ to check the proper direction reversal conditions.

One thing that I was discussing with @EliasLF, that might turn out really well as a follow up PR to this one here, is that, at the moment, there is a global fixed cost for bi-directional and uni-directional SWAPs. Now this PR introduces (global) per gate direction reversal handling. It would be great if the cost for a SWAP and the respective direction reversals were determined by the Architecture class. Hadamard gates, e.g., are not part of every native gate set out there and, thus, the relation between the costs might be different. Ideally, some new kind of GateSet data structure is designed, that allows to compute the respective costs. Every Architecture can, then, be augmented with a GateSet that dictates the cost. Alternatively, or in conjunction, one can keep a collection of reversal rules for all gates supported in the QFR (very similar to what this PR is doing) and use that to avoid having to break down blocks of gates that are not yet supported by the device but most be decomposed later on.

TLDR: @JoachimMarin Could you please resolve the conflicts based on the new changes and try to adapt the existing solution in this PR? Then, we'll see where we are at.

[JoachimMarin]

I have to finish my master's thesis in 3 weeks, so I don't have much time for programming at the moment. I don't know when I'll find the time for the requested changes.

[burgholzer]

I have to finish my master's thesis in 3 weeks, so I don't have much time for programming at the moment. I don't know when I'll find the time for the requested changes.

Hey @JoachimMarin 👋🏻 Any chance that you might want to continue working on this? No worries if you don't have time, but it would be much appreciated!

[JoachimMarin]

It was more work than I initially thought, so I couldn't finish it in time. I don't have the time for it, but I hope the discussion here and my work can be useful when work on two-qubit gates continues.