Rework `BasisTranslator` for faster basis search. #7211

georgios-ts · 2021-11-02T14:36:30Z

Summary

Closes #5539. Fixes #7219.
This commit reworks the logic of BasisTranslator._basis_search to perform a modified
BFS (instead of A* search) while searching for a set of transformation that maps source
basis to target basis. In more detail, we build a directed graph G = (V, E) where V
is the set of gates in the library and we add an edge (ga, gb) if there is an equivalence
rule in the library R = gb -> C_gb and ga in C_gb (in the edge we also attach the rule R).
Then, we do a BFS starting from the gates in the target basis. We traverse an edge (ga, gb, R)
only if we have previously visited all the gates appearing in the right side of R. We terminate
early if we've reached all gates in the original circuit. Otherwise, we can't map the given
circuit in this basis.

The performance improvement here mainly shows up when we attempt to target an unreachable basis,
since in other cases the previously used A* search was already fast and after all, the real
bottleneck of BasisTranslator for larger circuits is when we actually apply the basis transformation
rules.

Closes Qiskit#5539. This commit reworks the logic of `BasisTranslator._basis_search` to perform a modified BFS (instead of A* search) while searching for a set of transformation that maps source basis to target basis. In more detail, we build a directed graph `G = (V, E)` where `V` is the set of gates in the library and we add an edge `(ga, gb)` if there is an equivalence rule in the library `R = gb -> C_gb` and `ga in C_gb` (in the edge we also attach the rule `R`). Then, we do a BFS starting from the gates in the target basis. We traverse an edge `(ga, gb, R)` only if we have previously visited all the gates appearing in the right side of `R`. We terminate early if we've reached all gates in the original circuit. Otherwise, we can't map the given circuit in this basis. The performance improvement here mainly shows up when we attempt to target an unreachable basis, since in other cases the previously used A* search was already fast and after all, the real bottleneck of `BasisTranslator` for larger circuits is when we actually apply the basis transformation rules.

mtreinish · 2021-11-02T14:38:35Z

Tagging as on hold because this is blocked on the next retworkx release (which will include Qiskit/rustworkx#469)

georgios-ts · 2021-11-02T14:43:26Z

Running with this PR the examples from #5539 (comment):

from time import time
import qiskit as qk

def t(basis):
    start = time()
    try:
        qk.transpile(qc, basis_gates=basis)
    except Exception:
        pass
    end = time()
    return end-start

qc = qk.QuantumCircuit(3)
qc.ccx(0, 1, 2)

for b in [['u'], ['u3', 'u2', 'u1'], ['sx', 'p'], ['rx', 'ry']]:
    print(b, t(b))
----
['u'] 0.007858991622924805
['u3', 'u2', 'u1'] 0.0064618587493896484
['sx', 'p'] 0.005505800247192383
['rx', 'ry'] 0.007333040237426758

coveralls · 2021-11-22T16:02:46Z

Pull Request Test Coverage Report for Build 2030486720

93 of 94 (98.94%) changed or added relevant lines in 2 files are covered.
No unchanged relevant lines lost coverage.
Overall coverage increased (+0.01%) to 83.555%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
qiskit/transpiler/passes/basis/basis_translator.py	92	93	98.92%

Totals
Change from base Build 2030484362:	0.01%
Covered Lines:	52715
Relevant Lines:	63090

💛 - Coveralls

jakelishman

This is cool! I just came by because it was top of my notifications and I need to get graph algorithms more solid in my head, but I left a couple of super minor comments that may make it a bit easier to read.

qiskit/transpiler/passes/basis/basis_translator.py

requirements.txt

Co-authored-by: Jake Lishman <jake@binhbar.com>

mtreinish · 2021-11-23T19:47:30Z

I ran the asv basis translator benchmarks (mainly out of curiosity) on my workstation and got these results:

Benchmarks that have improved:

       before           after         ratio
     [0a100080]       [e3f7c2d6]
     <main>        <georgios-ts-basis-translator-speed-up>
-        713±30ms          640±2ms     0.90  passes.MultipleBasisPassBenchmarks.time_basis_translator(14, 1024, ['u', 'cx', 'id'])
-       279±0.6ms          240±2ms     0.86  passes.MultipleBasisPassBenchmarks.time_basis_translator(5, 1024, ['u', 'cx', 'id'])
-        944±90ms          772±6ms     0.82  passes.MultipleBasisPassBenchmarks.time_basis_translator(14, 1024, ['rz', 'x', 'sx', 'cx', 'id'])
-        370±10ms          295±2ms     0.80  passes.MultipleBasisPassBenchmarks.time_basis_translator(5, 1024, ['rz', 'x', 'sx', 'cx', 'id'])
-      1.90±0.01s       1.38±0.01s     0.73  passes.MultipleBasisPassBenchmarks.time_basis_translator(20, 1024, ['rx', 'ry', 'rz', 'r', 'rxx', 'id'])
-      1.46±0.01s          971±2ms     0.66  passes.MultipleBasisPassBenchmarks.time_basis_translator(14, 1024, ['rx', 'ry', 'rz', 'r', 'rxx', 'id'])
-         781±1ms          347±2ms     0.44  passes.MultipleBasisPassBenchmarks.time_basis_translator(5, 1024, ['rx', 'ry', 'rz', 'r', 'rxx', 'id'])

Benchmarks that have stayed the same:

       before           after         ratio
     [0a100080]       [e3f7c2d6]
     <main>        <georgios-ts-basis-translator-speed-up>
        1.18±0.1s       1.07±0.01s     0.91  passes.MultipleBasisPassBenchmarks.time_basis_translator(20, 1024, ['rz', 'x', 'sx', 'cx', 'id'])
         982±50ms          893±5ms     0.91  passes.MultipleBasisPassBenchmarks.time_basis_translator(20, 1024, ['u', 'cx', 'id'])

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE INCREASED.

It looks like there is a nice performance improvement here across the board. Definitely more than just the negative case where there is no path found.

requirements.txt

mtreinish

Overall this LGTM, I'm happy with how this looks. The one thing I'm wondering though is as a future optimization instead of building the graph on demand in the pass would it makes sense to incrementally build it in the equivalence library itself as we add rules. Then for the pass we can just add the dummy node and edges for the target basis (and remove them at the end of the pass). We can look at that in a future PR though or I might be missing something that's blocking us from doing that.

mtreinish · 2022-03-16T22:05:52Z

qiskit/transpiler/passes/basis/basis_translator.py


        qarg_local_basis_transforms = {}
        for qarg, local_source_basis in qargs_local_source_basis.items():
-            expanded_target = target_basis | self._qargs_with_non_global_operation[qarg]
+            expanded_target = set(target_basis)


Is this just to avoid the double add to the set for 1q gates? Or was this causing a bug somewhere?

The previous line had actually no effect since self._qargs_with_non_global_operation is indexed by a tuple but qarg is a frozenset.

mtreinish · 2022-03-17T13:12:35Z

qiskit/transpiler/passes/basis/basis_translator.py

+    # This is only neccessary since gates in target basis are currently reported by
+    # their names and we need to have in addition the number of qubits they act on.


If a target is set we can get this via:

gate_num_qubits = target.operation_from_name(name).num_qubits

but that doesn't cover the non-target path.

Thanks for mentioning that but since we still need this for the non-target case I guess it doesn't hurt much to leave it as is.

mtreinish · 2022-03-17T13:21:00Z

Actually one thing is it might be good to have a release note for this, since we're fixing some issues and maybe advertise the performance improvement too

georgios-ts · 2022-03-17T16:03:52Z

The one thing I'm wondering though is as a future optimization instead of building the graph on demand in the pass would it makes sense to incrementally build it in the equivalence library itself as we add rules

Yeah, I thought about that too but since EquivalenceLibrary has already a different notion of a basis graph https://github.com/Qiskit/qiskit-terra/blob/main/qiskit/circuit/equivalence.py#L202 (which is closer to the previous basis search strategy) I just wanted to avoid any confusion.

Release note added in 908f66b. I didn't advertise fixing #7219 since this issue seems already fixed in main (probably by #7279)

mtreinish · 2022-03-17T16:19:03Z

Yeah, I thought about that too but since EquivalenceLibrary has already a different notion of a basis graph https://github.com/Qiskit/qiskit-terra/blob/main/qiskit/circuit/equivalence.py#L202 (which is closer to the previous basis search strategy) I just wanted to avoid any confusion.

Well it looks like that function only exists internally for drawing the equivalence library so it's not super critical. I think we can either split it out that existing graph method as _build_visualization_graph to make the intent clear, update the draw() method to generating a dot file from the new graph structure (not sure that's possible), or just change the visualization output to represent the new graph format (I don't think a stable visualization format is that important for this). But either way, we can do this in a follow up fairly easily and discuss the specifics there.

mtreinish

This LGTM now, thanks for doing this

georgios-ts requested a review from a team as a code owner November 2, 2021 14:36

mtreinish added the on hold Can not fix yet label Nov 2, 2021

mtreinish added this to the 0.20 milestone Nov 2, 2021

mtreinish added the performance label Nov 2, 2021

georgios-ts mentioned this pull request Nov 3, 2021

Odd RZX decompositions #7219

Closed

georgios-ts mentioned this pull request Nov 15, 2021

Add bfs-search Qiskit/rustworkx#469

Merged

georgios-ts added 3 commits November 19, 2021 17:56

merge 'upstream/main'

465c907

switch from bfs to dijkstra search for more efficient output circuits

29e1334

merge 'upstream/main'

207beaa

lint

8ad47e4

jakelishman reviewed Nov 23, 2021

View reviewed changes

georgios-ts and others added 2 commits November 23, 2021 19:41

move visitor class outside of _basis_search function

820aab6

set comprehension

e3f7c2d

Co-authored-by: Jake Lishman <jake@binhbar.com>

mtreinish mentioned this pull request Nov 30, 2021

Start making the transpiler Target aware #7227

Merged

mtreinish reviewed Jan 28, 2022

View reviewed changes

requirements.txt Outdated Show resolved Hide resolved

merge 'upstream/main'

7d1cf06

jakelishman removed the on hold Can not fix yet label Feb 23, 2022

jakelishman mentioned this pull request Feb 23, 2022

Compiler hangs (infinite loop), when transpile( ) receives invalid gate names #7636

Closed

georgios-ts added 7 commits February 24, 2022 14:38

fix expanded_target if 1q-non global op

9aa46c2

merge 'upstream/main'

5b97fb6

adjust test case

6fb0adc

docstring and log messages improvements

c12b291

merge origin

0a021e4

fix failing tests

4b70021

merge 'upstream/main'

fa5ff9e

kdk mentioned this pull request Mar 2, 2022

[WIP] broadcast arguments mixin #7718

Closed

mtreinish previously approved these changes Mar 17, 2022

View reviewed changes

mtreinish added Changelog: Bugfix Include in the "Fixed" section of the changelog Changelog: New Feature Include in the "Added" section of the changelog labels Mar 17, 2022

georgios-ts added 2 commits March 17, 2022 16:02

merge 'upstream/main'

e2a3cf2

release note

908f66b

georgios-ts dismissed mtreinish’s stale review via 908f66b March 17, 2022 16:00

mtreinish approved these changes Mar 23, 2022

View reviewed changes

mtreinish added automerge and removed Changelog: Bugfix Include in the "Fixed" section of the changelog labels Mar 23, 2022

Merge branch 'main' into basis-translator-speed-up

f8ae1c6

mergify bot merged commit 95c2aa2 into Qiskit:main Mar 23, 2022

mtreinish mentioned this pull request Mar 26, 2022

Add equivalences from CX to CPhase+U and CRZ+U #7013

Merged

mtreinish mentioned this pull request Sep 2, 2022

Refactor EquivalenceLibrary to internally be a graph #8664

Closed

		# This is only neccessary since gates in target basis are currently reported by
		# their names and we need to have in addition the number of qubits they act on.

Rework BasisTranslator for faster basis search. #7211

Rework BasisTranslator for faster basis search. #7211

Uh oh!

Conversation

georgios-ts commented Nov 2, 2021 • edited by ajavadia Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary

Uh oh!

mtreinish commented Nov 2, 2021

Uh oh!

georgios-ts commented Nov 2, 2021

Uh oh!

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

Uh oh!

Pull Request Test Coverage Report for Build 2030486720

💛 - Coveralls

Uh oh!

jakelishman left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

mtreinish commented Nov 23, 2021

Uh oh!

Uh oh!

mtreinish left a comment

Choose a reason for hiding this comment

Uh oh!

mtreinish Mar 16, 2022

Choose a reason for hiding this comment

Uh oh!

georgios-ts Mar 17, 2022

Choose a reason for hiding this comment

Uh oh!

mtreinish Mar 17, 2022

Choose a reason for hiding this comment

Uh oh!

georgios-ts Mar 17, 2022

Choose a reason for hiding this comment

Uh oh!

mtreinish commented Mar 17, 2022

Uh oh!

georgios-ts commented Mar 17, 2022

Uh oh!

mtreinish commented Mar 17, 2022

Uh oh!

mtreinish left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Rework `BasisTranslator` for faster basis search. #7211

Rework `BasisTranslator` for faster basis search. #7211

georgios-ts commented Nov 2, 2021 •

edited by ajavadia

Loading

coveralls commented Nov 22, 2021 •

edited

Loading