Start making the transpiler Target aware #7227

mtreinish · 2021-11-04T18:19:28Z

Summary

In #5885 we added the next version of the abstract Backend interface
BackendV2 which added the concept of a Target which represents a
compiler target for the transpiler. It contains all the information
about the constraints of a backend for the compiler to use and replaces
the combination of basis_gates, coupling_map, etc and expands the
representation to model more complex devices. However, in #5885 we only
introduced the interface and didn't modify the transpiler to use the
Target natively or any of the extra information it contains. This commit
is the start of the process of updated the transpiler to work with a
target natively. To start if a backend has a target that is now passed
through from transpile to the passmanager_config so we can start passing
it directly to passes as we enable it. Then the basis translator is
updated to work natively with a target instead of the basis gates list
it used before. In addition to using a target directly support is added
for heterogeneous gate sets so that target instructions can work on only
a subset of qargs.

Additionally, to ensure that we're respecting direcitonality of non-symmetric
gates after translating the GateDirection and CheckDirection passes are
updated to work with a target too so they can adapt to strict direction constraints
defined in the target.

Building off this in the future There are additional features in target
that we might want to expand support for in the BasisTranslator in the
future, such as supporting custom variants of the same gate, or handling
fixed angle rotation gate variants, etc.

Details and comments

mtreinish · 2021-11-04T18:20:38Z

This is tagged as on hold because it's on top of #5885 and will need to be rebased after #5885 merges. To see the contents of just this PR you can look at the last commit: 84361f2 which contains the diff for this PR

coveralls · 2021-11-04T18:53:01Z

Pull Request Test Coverage Report for Build 1537465186

308 of 350 (88.0%) changed or added relevant lines in 14 files are covered.
1 unchanged line in 1 file lost coverage.
Overall coverage increased (+0.02%) to 83.099%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
qiskit/transpiler/passes/basis/basis_translator.py	50	51	98.04%
qiskit/transpiler/target.py	30	31	96.77%
qiskit/transpiler/passmanager_config.py	5	7	71.43%
qiskit/test/mock/fake_backend_v2.py	34	39	87.18%
qiskit/test/mock/fake_mumbai_v2.py	46	51	90.2%
qiskit/transpiler/passes/utils/gate_direction.py	35	45	77.78%
qiskit/compiler/transpiler.py	66	84	78.57%

Files with Coverage Reduction	New Missed Lines	%
qiskit/transpiler/passes/basis/basis_translator.py	1	98.44%

Totals
Change from base Build 1532852473:	0.02%
Covered Lines:	51664
Relevant Lines:	62172

💛 - Coveralls

qiskit/test/mock/fake_backend_v2.py

ajavadia · 2021-11-18T12:30:21Z

can you add a test to transpile a circuit containing ccx to FakeMumbaiV2? It should utilize rzx(pi/2) and rzx(pi/4) if you base this branch off of #7279

jakelishman

Some comments - mostly it looks like it works right to me, but I had some questions about potential scaling issues (which I suppose are more closely linked to Target than this PR)

qiskit/transpiler/passes/basis/basis_translator.py

jakelishman · 2021-11-18T11:01:56Z

qiskit/transpiler/passes/basis/basis_translator.py

            return dag

+        qarg_indices = {qubit: index for index, qubit in enumerate(dag.qubits)}


And again it appears... If only there were a built-in collections.OrderedSet type.

Heh, yeah. We really need the find_bits api for the dag class. I think we're well past the point where the majority of the passes do this.

jakelishman · 2021-11-18T14:32:19Z

qiskit/transpiler/passes/basis/basis_translator.py

+        if size not in all_permutations_all_size:
+            all_permutations_all_size[size] = set(permutations(range(target.num_qubits), size))
+        if qargs != all_permutations_all_size[size]:
+            incomplete_basis_gates.append(inst)


This is O(n^d) for a target with n qubits and a maximum gate arity of d. I'm assuming that once we get to large backends, then they just won't be able to specify all properties for every pair (or even triple!) of qubits - even Eagle's going to be a bit of problem with ~16,000 elements necessary in these sets. Are we allowed to assume that a target is well-formed? If so, can we just skip creating our own permutation, and test the size of the set?

Also, are the qubits guaranteed to be ordered from 0 to n - 1? I feel like I remember the qubit properties data structure being a dictionary, not an array.

Yeah, I think I'm going to need to change to search for each edge (or multiqubit gate) in the target instead of trying to compute all the valid permutations and figure out if we need this or not. This is still WIP and something I realized a while ago (I should have left a comment) because also we're almost always going to be returning something for size >=2 here unless they have complete connectivity (which ions do at least). Since the full permutation map is all to all. I'm planning to update the logic here, I've just been concentrating on #5885 because that really needs to merge soon so we can unblock this and other things

Sure, no problem - apologies if this review was a bit premature.

Take a look at the current version (I force pushed it because I've been rebasing on #5885 as that changes) I think this should be more efficient than before. It still scales with the number of edges in the coupling map but not the full permutation. I did try adding a search for each edge and the performance was horrific on that.

jakelishman · 2021-11-18T14:38:17Z

qiskit/transpiler/passes/basis/basis_translator.py

+            for gate in self._incomplete_basis:
+                for qarg in self._target[gate]:
+                    qarg_with_incomplete[qarg].add(gate)


I may well be wrong, but this feels like it's doing some extra iteration - it feels like there'll be a way to combine it into _compute_incomplete_basis and reuse the set differences we're already calculating in there, rather than needing to duplicate it.

test/python/transpiler/test_target.py

qiskit/transpiler/passes/basis/basis_translator.py

jakelishman · 2021-11-23T17:49:39Z

qiskit/transpiler/passes/basis/basis_translator.py

+        if len(qargs) != size_dict[len(qarg_sample)]:
+            incomplete_basis_gates.append(inst)


I don't think this actually tests if the gate applies to all qubits, right? If I have a target with no coupling at all between qubits 0 and 2 and a single 2q gate, then this test will appear true, because the qargs will be exactly the set of operands to this gate, so size_dict[2] will be the same as len(qargs), even though there's not full connectivity (which I what I think the previous iteration of this function was testing).

Also, minor sidenote: do targets need to specify symmetric gates like cz with qargs (a, b) and (b, a), or only one of the pair?

Ah, yeah my bad I made a copy paste error this should be len(qargs) not len(qarg_sample).

Right the earlier iteration was doing the wrong thing. We want this to return a list of instructions which do not apply globally in the target, for 1q this is on all qubits, for 2q this is on all edges in the coupling graph, >3q on all valid qargs in the target of that size. The previous iteration was incorrect because it was always checking the full permutation which was only true on an all to all coupling map (it was only correct in the 1q case).

Also, minor sidenote: do targets need to specify symmetric gates like cz with qargs (a, b) and (b, a), or only one of the pair?

They need to be specified bidirectionally (so (a, b) and (b, a)) the way the target is implemented now. Otherwise the target will treat it like you can only run cz on (a, b) or (b, a) (whichever you put in the target).

With the new explanation, I think what you've got written here is correct. That also makes way more sense to me - I was stuck still thinking about the old version of the function as what we were trying to achieve.

Taking another look at it I actually I think I did this correctly, I'm trying to get the size of the qargs tuple to look up the number of valid options in the target. So for example if we have a 3q bidirectional linear coupling map: [(0, 1), (1, 0), (1, 2), (2, 1)] and have cx defined on all edges, but ecr only on reverse (so (1, 0) and (2, 1)). The check here should be:

For ecr:

size_dict = {1: 3, 2: 4} len([(1, 0), (2, 1)]) != len(size_dict[2])

which will add ecr to the incomplete list.

While for cx it'll be:

len([(0, 1), (1, 0), (1, 2), (2, 1)] != size_dict[2]

which means we don't add cx to the incomplete list because it's on all edges in the coupling graph.

Yeah, I agree - I thought it was wrong because I thought we were shooting for the old, incorrect behaviour.

This is an interesting question. Do we want ecr to show up as incomplete here given that this case (a gate is available on an edge, but in the reverse of the direction required) is usually handled by GateDirection?

I think we do at least until we can make gate direction target aware. The other thing is if we wanted to rely on gate direction for this we'd need to differentiate between unidirectional gates vs bidirectional gates in the target (at least for the compute_non_global_operation_names() method which it doesn't do right now.

I don't think gate direction needs to be target aware (yet), but I do think the BasisTranslator should not (maybe not yet) be gate direction aware. Otherwise, e.g. if we have the equivalent of a non-symmetric coupling map (with some non-global gates), the BasisTranslator would raise before we get a chance to run GateDirection.

The problem here is that in the case where you have a target that's like what's in FakeBackendV2 where cx is on (0, 1) and ecr is on (1, 0) if you treat each 2q gate as symmetric (or a weak edge in a directed graph) if you have a circuit with a 2q gate on (1, 0) outside the basis you'll almost always end up with cx(1, 0) in the output circuit. This is also why gate direction being target aware is a requirement because the coupling map object that gets used is of the global edges independent of which gates so gate direction will think that's valid unless it's made target aware. That being said even if you do this and make gate direction target aware (I have a commit on this PR branch locally doing it) this still ends up with a less than ideal result because you'll end up with cx(0, 1) with the h gates around it where ecr(1, 0) is a valid and less gates

mtreinish · 2021-11-30T15:37:48Z

can you add a test to transpile a circuit containing ccx to FakeMumbaiV2? It should utilize rzx(pi/2) and rzx(pi/4) if you base this branch off of #7279

I have tested this and it doesn't pick rzx right now, for two reasons I think. The first is that the path to cx is likely shorter and will be favored by the basis translator. The second is this PR doesn't handled tuned variants correctly, it only adds support for heterogeneous gate sets (so different gates on different qubits). So right now even where there is a path from ccx -> rzx the basis translator won't think this is valid because rzx_30, rzx_45, and rzx_90 are the targets it considers. The first half should be easily fixable with #7211 where we can change the search based on error rates. The second half though we probably will need to rework how the basis translator finds matches to consider the gate instance and not just the name (although the name will be needed still for mapping).

In Qiskit#5885 we added the next version of the abstract Backend interface BackendV2 which added the concept of a Target which represents a compiler target for the transpiler. It contains all the information about the constraints of a backend for the compiler to use and replaces the combination of basis_gates, coupling_map, etc and expands the representation to model more complex devices. However, in Qiskit#5885 we only introduced the interface and didn't modify the transpiler to use the Target natively or any of the extra information it contains. This commit is the start of the process of updated the transpiler to work with a target natively. To start if a backend has a target that is now passed through from transpile to the passmanager_config so we can start passing it directly to passes as we enable it. Then the basis translator is updated to work natively with a target instead of the basis gates list it used before. In addition to using a target directly support is added for heterogeneous gate sets so that target instructions can work on only a subset of qargs. Building off this in the future There are additional features in target that we might want to expand support for in the BasisTranslator in the future, such as supporting custom variants of the same gate, or handling fixed angle rotation gate variants, etc.

mtreinish · 2021-12-01T14:40:02Z

Ok now that #5885 has merged I've rebased this on main and it's unblocked now

Co-authored-by: georgios-ts <45130028+georgios-ts@users.noreply.github.com>

kdk

Thanks for the updates here. Few additional small questions.

Also, can you update the BasisTranslator docstring to include how it should handle non-global operations? I think it would also be good to add a few additional test cases for the new behavior. Maybe different variants of cx, cz and ecr on an input circuit targeting a 4q device that has q0 ->(cx) q1 ->(ecr) q2 ->(cx) -> q3 ->(ecr) q0 and the bidirectional version of the same would give some additional coverage.

qiskit/transpiler/passes/basis/basis_translator.py

kdk · 2021-12-02T23:23:03Z

qiskit/transpiler/passes/basis/basis_translator.py

+            if len(qarg) > 1:
+                qubit_set = frozenset(qarg)
+                for non_local_qarg, local_basis in qarg_with_incomplete.items():
+                    if qubit_set.issuperset(non_local_qarg):


Minor, but at some point, it might be faster to look for all the unique subsets of qarg in qarg_with_incomplete. (I'm assuming the max(len(qargs)) will be stay relatively small, and the size of qarg_with_incomplete will grow, but maybe that's also a concern better left for #7346.)

qiskit/transpiler/preset_passmanagers/level3.py

qiskit/transpiler/passes/basis/basis_translator.py

qiskit/transpiler/passes/utils/gate_direction.py

…complete_source_basis -> qargs_local_source_basis

georgios-ts · 2021-12-03T16:55:57Z

Another unexpected behavior that will not come up in preset pass managers since BasisTranslator runs post-routing and the circuit will already be adapted in hardware connectivity but if run as a standalone pass, the following will raise or will not raise if you uncomment the commented line.
(IMO it should raise in both cases)

from qiskit.circuit import QuantumCircuit, Parameter
from qiskit.circuit.library import UGate, CXGate, ECRGate
from qiskit.circuit.equivalence_library import SessionEquivalenceLibrary as sel

from qiskit.transpiler import PassManager, Target, InstructionProperties
from qiskit.transpiler.passes import BasisTranslator

gmap = Target()

# U gate in qubit 0.
theta = Parameter('theta')
phi = Parameter('phi')
lam = Parameter('lambda')
u_props = {
    (0,): InstructionProperties(duration=5.23e-8, error=0.00038115),
    (1,): InstructionProperties(duration=5.23e-8, error=0.00038115),
    (2,): InstructionProperties(duration=5.23e-8, error=0.00038115),
}
gmap.add_instruction(UGate(theta, phi, lam), u_props)

cx_props = {
    (0, 1): InstructionProperties(duration=5.23e-7, error=0.00098115),
    # (1, 2): InstructionProperties(duration=5.23e-7, error=0.00098115),
}
gmap.add_instruction(CXGate(), cx_props)

ecr_props = {
    (1, 2): InstructionProperties(duration=5.23e-7, error=0.00098115),
}
gmap.add_instruction(ECRGate(), ecr_props)

qc = QuantumCircuit(3)
qc.cx(0, 2)

pm = PassManager([
    BasisTranslator(sel, target_basis=None, target=gmap)
])

circ = pm.run(qc)

test/python/providers/test_backend_v2.py

This fixes 2 issues found in review with the the transpile() functions handling of target. First if a target kwarg is passed by a user that target will be used instead of the backend for not just the target but also all derived quantities (such as coupling_map and basis_gates). Also previously the backend_properties field was not being correctly built from a target (both for a backendv2 or a standalone target). So a converter helper function was added to go from a target and build a BackendPropeties object from the data contained in the target. This will enable noise aware transpilation until the transpiler passes are all target aware.

Optimization level 3 is different from the other lower optimization levels because it uses unitary synthesis by default. The unitary synthesis pass is basis and coupling map to optimize the synthesized circuit for a unitary to be hardware efficient. However when using a target the basis gates and coupling map don't give a complete picture of the device constraints (mainly the non-global gates if any). To account for this we need to run the gate direction pass after unitary synthesis to correct an incorrect decision the unitary synthesis pass might make based on it's incomplete data. Once UnitarySynthesis is target aware we probably do not require this anymore.

…tangling gates

…acking

qiskit/compiler/transpiler.py

qiskit/test/mock/fake_backend_v2.py

qiskit/transpiler/passes/basis/basis_translator.py

qiskit/transpiler/preset_passmanagers/level3.py

test/python/providers/test_backend_v2.py

Co-authored-by: Kevin Krsulich <kevin@krsulich.net>

qiskit/compiler/transpiler.py

kdk

Thanks for the updates here, this LGTM.

mtreinish added on hold Can not fix yet priority: high Changelog: None Do not include in changelog labels Nov 4, 2021

mtreinish added this to the 0.19 milestone Nov 4, 2021

mtreinish requested review from chriseclectic, jyu00 and a team as code owners November 4, 2021 18:19

mtreinish mentioned this pull request Nov 5, 2021

Add BackendV2 abstract class #5885

Merged

8 tasks

mtreinish force-pushed the target-basis-passes branch 3 times, most recently from 756c8d3 to ca5e714 Compare November 17, 2021 12:23

ajavadia reviewed Nov 18, 2021

View reviewed changes

qiskit/test/mock/fake_backend_v2.py Outdated Show resolved Hide resolved

qiskit/test/mock/fake_backend_v2.py Show resolved Hide resolved

jakelishman reviewed Nov 18, 2021

View reviewed changes

mtreinish force-pushed the target-basis-passes branch 2 times, most recently from 1e85dd1 to 2546ab9 Compare November 22, 2021 15:08

jakelishman reviewed Nov 23, 2021

View reviewed changes

mtreinish force-pushed the target-basis-passes branch 3 times, most recently from c17ab6b to 54a609f Compare November 30, 2021 15:23

kdk self-assigned this Nov 30, 2021

mtreinish mentioned this pull request Nov 30, 2021

Add support for BackendV2 and Target to transpiler #7113

Closed

mtreinish force-pushed the target-basis-passes branch from 54a609f to 070db99 Compare December 1, 2021 14:39

mtreinish removed the on hold Can not fix yet label Dec 1, 2021

mtreinish changed the title ~~[WIP] Start making the BasisTranslator Target/BackendV2 aware~~ Start making the BasisTranslator Target/BackendV2 aware Dec 1, 2021

mtreinish and others added 2 commits December 3, 2021 08:58

Correct detection of non-global ops with strict_direction=False

a9ee118

Co-authored-by: georgios-ts <45130028+georgios-ts@users.noreply.github.com>

Fix handling of non-local subset searching

4801594

kdk reviewed Dec 3, 2021

View reviewed changes

mtreinish added 4 commits December 3, 2021 10:46

Simplify target path in gate direction pass

fe21d8d

Rename extra_source_basis -> local_source_basis

52a5e4f

Rename incomplete_basis -> non_global_operations

32f326a

Rename qarg_with_incomplete -> qargs_with_non_global_operation and in…

04cbf94

…complete_source_basis -> qargs_local_source_basis

kdk reviewed Dec 3, 2021

View reviewed changes

test/python/providers/test_backend_v2.py Show resolved Hide resolved

mtreinish added 7 commits December 3, 2021 13:06

Calculate qargs with non global operation once per pass instance

bbbfc43

Expand docstring to include non-global operation behavior description

1a918c0

Add test assertion that it matches the target

ed966aa

Add tests of 5q ghz on non-linear non-global target with different en…

05b5b68

…tangling gates

Use frozenset instead of tuple for local search and transformation tr…

da0aafc

…acking

mtreinish requested a review from kdk December 3, 2021 21:54

mtreinish commented Dec 3, 2021

View reviewed changes

qiskit/compiler/transpiler.py Outdated Show resolved Hide resolved

Fix copy paste error for gate error in _target_to_backend_properties

fb25aa0

kdk reviewed Dec 3, 2021

View reviewed changes

Apply suggestions from code review

e2b1ff4

Co-authored-by: Kevin Krsulich <kevin@krsulich.net>

kdk reviewed Dec 3, 2021

View reviewed changes

qiskit/compiler/transpiler.py Outdated Show resolved Hide resolved

mtreinish added 2 commits December 3, 2021 18:22

Only run gate direction in level 3 with a target

c6df7ef

Move target overrides inside _parse_transpile_args()

488eab0

kdk approved these changes Dec 4, 2021

View reviewed changes

kdk added the automerge label Dec 4, 2021

mergify bot merged commit 1a9f938 into Qiskit:main Dec 4, 2021

mtreinish deleted the target-basis-passes branch December 4, 2021 01:05

mtreinish mentioned this pull request Jun 2, 2022

Add function to easily generate preset pass managers #8125

Merged

jakelishman mentioned this pull request Jun 29, 2023

backend.target.get_non_global_operation_names always returns empty list Qiskit/qiskit-ibm-provider#490

Closed

		return dag

		qarg_indices = {qubit: index for index, qubit in enumerate(dag.qubits)}

		if len(qargs) != size_dict[len(qarg_sample)]:
		incomplete_basis_gates.append(inst)

Start making the transpiler Target aware #7227

Start making the transpiler Target aware #7227

Uh oh!

Conversation

mtreinish commented Nov 4, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary

Details and comments

Uh oh!

mtreinish commented Nov 4, 2021

Uh oh!

coveralls commented Nov 4, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 1537465186

💛 - Coveralls

Uh oh!

Uh oh!

Uh oh!

ajavadia commented Nov 18, 2021

Uh oh!

jakelishman left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mtreinish Nov 23, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mtreinish commented Nov 30, 2021

Uh oh!

mtreinish commented Dec 1, 2021

Uh oh!

kdk left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

mtreinish commented Nov 4, 2021 •

edited

Loading

coveralls commented Nov 4, 2021 •

edited

Loading

mtreinish Nov 23, 2021 •

edited

Loading