Add DAGDependencyV2 and Converters #11705

enavarro51 · 2024-02-01T15:09:31Z

Summary

Add new DAGDependencyV2 and Converters

Details and comments

This PR is a replacement for #11310. In that PR, the new DAGDependencyV2 was created and the associated template matching code was modified to use it. This PR only creates the dag and the 2 converters required. The following changes were made,

There is a new DAGDependencyV2 which no longer uses DAGDepNode, but instead uses the existing DAGOpNode without modification. The makes for a cleaner and much reduced memory profile for the nodes.
Additional methods from DAGCircuit, such as find_bit were added to the DAGDependencyV2 and other methods were modified to more closely match the 2 dags.
The information stored previously in the node attributes would now be accessed in the template matching code through calls to the rustworkx functions once the template matching code is refactored.
A terminology change was made in DAGDependencyV2. direct_successors is now successors and successors is now descendants. Similarly for predecessors and ancestors. This mirrors the usage in rustworkx.

Doing some local tests on an 8000 gate circuit and converting the circuit to a dag dependency, V2 used ~300MB of memory and V1 used ~2.5GB of memory.

The next phase will be to refactor the template matching code to use V2 and to optimize the matching.

edit (@jakelishman):

Warning

Just to highlight to anyone else reading this, again: all this is deliberately not public, and it's all so not public (undocumented, and has explicitly private names) that we're not even marking it with the "experimental" API. This is for near-term experimentation and there's a good chance it may even be replaced entirely with a pure-Rust implementation before being made public.

qiskit-bot · 2024-02-01T15:09:35Z

One or more of the the following people are requested to review this:

@Qiskit/terra-core

coveralls · 2024-02-01T15:28:34Z

Pull Request Test Coverage Report for Build 8705828497

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.

For more information on this, see Tracking coverage changes with pull request builds.
To avoid this issue with future PRs, see these Recommended CI Configurations.
For a quick fix, rebase this PR at GitHub. Your next report should be accurate.

Details

204 of 281 (72.6%) changed or added relevant lines in 4 files are covered.
84 unchanged lines in 7 files lost coverage.
Overall coverage decreased (-0.1%) to 89.262%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
qiskit/visualization/dag_visualization.py	0	3	0.0%
qiskit/dagcircuit/dagdependency_v2.py	170	244	69.67%

Files with Coverage Reduction	New Missed Lines	%
qiskit/synthesis/two_qubit/xx_decompose/circuits.py	1	92.86%
qiskit/transpiler/passes/routing/sabre_swap.py	2	96.82%
qiskit/synthesis/two_qubit/xx_decompose/decomposer.py	2	90.63%
crates/qasm2/src/lex.rs	5	92.37%
crates/qasm2/src/parse.rs	12	96.23%
qiskit/quantum_info/operators/symplectic/pauli.py	29	84.64%
qiskit/transpiler/passes/synthesis/unitary_synthesis.py	33	89.02%

Totals
Change from base Build 8614257652:	-0.1%
Covered Lines:	60353
Relevant Lines:	67613

💛 - Coveralls

…dag_dep_v2

alexanderivrii

I am very excited about this new DAG-dependency interface because it's significantly closer to the DAGCircuit interface and in principle allows to unify the two even further. Ideally I would like the two interfaces to be almost fully identical (modulo the comment below) and I have left several inline comments to that extent. In particular, I am suggesting to remove or to adapt all methods that don't have a close DAGCircuit analogue (or add such methods to DAGCircuit as well). (This does not apply to internal methods prefixed with _).

But even right now this allows to write transpiler passes that can work with either circuit representation.

Other than that, we want release notes and a few more tests exploring various DAGDependencyV2 functionality (possibly many of these can be adapted from DAGDependency tests).

The promised comment is that DAG-dependency is conceptually different from a DAG-circuit and some operations on DAG-dependency have to be implemented considerably differently. For instance, we don't yet have a DAG-dependency analogue of substitute_node_with_dag because adding new nodes to DAG dependency generally involves performing commutativity checks and recursively examining descendants and ancestors of the existing nodes.

qiskit/dagcircuit/dagdependency_v2.py

alexanderivrii · 2024-02-05T09:55:02Z

qiskit/dagcircuit/dagdependency_v2.py

+    def get_node(self, node_id):
+        """
+        Args:
+            node_id (int): label of considered node.
+
+        Returns:
+            node: corresponding to the label.
+        """
+        return self._multi_graph.get_node_data(node_id)


I am slightly confused: DAGCircuit does not have this function nor ever checks _multi_graph.get_node_data. Maybe we don't need these functions, given your changes to unifying the predecessor/successor interface? I.e. this looks like a point where the APIs for DAGCircuit and DAGDependencyV2 slightly deviate, and I am wondering if we can avoid this.

This is needed in template matching so not important there, but also in _update_edges since that method is written using node indices instead of node object ids. I did a first try to convert this method to using object ids, but could not come up with an efficient way to do it. So for now I would leave this and address it later.

The use of node indices could also be a problem if nodes are inserted or removed and then iterated over.

Leaving this in until I rewrite _update_edges to not use indices. Also used in some of the tests, which will need to be redone later.

Agreed. What about making get_node into an internal function (i.e. just renaming it to _get_node), so that we will able to freely change/remove it later?

BTW, let's rewrite _update_edges in a follow-up PR, not now.

Agreed on _get_node and redo _update_edges later.

alexanderivrii · 2024-02-05T11:16:09Z

qiskit/dagcircuit/dagdependency_v2.py

+    def remove_op_node(self, node):
+        """Remove an operation node n.
+


I am a little bit worried about this function in the context of DAG dependency. Though (after some thinking) I do believe that this method of removing nodes and reconnecting predecessors to successors is safe: we will not be able to incorrectly infer from dag dependency that two nodes commute when in fact they do not. It might not be compete: the dag dependency may say that two nodes do not commute when in fact they do. For example, suppose that we have a chain of nodes A -> B -> C. By definition, A and B do not commute, and B and C do not commute (but this says nothing about whether A and C commute). If we remove B and retain edges, we will end up with A -> C, which might be over-conservative if A and C do commute. Note that it's not enough to check the commutativity of A and C and remove the edge if they do commute, since we should also recursively check if C commutes with predecessors of A, and A commutes with successors of C. So at the minimum let's update the docstring of this function. Hmm, when would we ever want to remove nodes from a DAG?

The comment for replace_block_with_op addresses the question of commutativity of the output, which is relevant here as well. remove_op_node is used extensively in the transpiler passes.

Agreed, replace_block_with_op has the same flavor: the resulting DAG-dependency may hide some commutativity relations. So at some point we may want to add a function to reconstruct DAGDependency from scratch.

qiskit/dagcircuit/dagdependency_v2.py

alexanderivrii · 2024-02-06T08:07:11Z

qiskit/dagcircuit/dagdependency_v2.py

+        target_dag.comm_checker = CommutationChecker()
+


Can we do this instead: target_dag.comm_checker = self.comm_checker?

alexanderivrii · 2024-02-06T08:14:48Z

test/python/converters/test_circuit_to_dagdependency.py

+from test import QiskitTestCase

 from qiskit.converters.dagdependency_to_circuit import dagdependency_to_circuit
 from qiskit.converters.circuit_to_dagdependency import circuit_to_dagdependency
 from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
-from test import QiskitTestCase  # pylint: disable=wrong-import-order


I can't say that I fully understand why PR #10998 replaced all lines of the form

from test import QiskitTestCase

to

from test import QiskitTestCase # pylint: disable=wrong-import-order

but it may be best to keep the change here.

Not sure why either, but can leave as is.

alexanderivrii · 2024-02-06T08:19:43Z

test/python/converters/test_circuit_to_dagdependency_v2.py

+class TestCircuitToDagCanonical(QiskitTestCase):
+    """Test QuantumCircuit to DAGDependency."""


Should the name of the class be TestCircuitToDagDependency (not that it really matters).

alexanderivrii

Thanks for the quick updates. I have added a few more minor inline suggestions, with the only other thing being the release notes :).

sbrandhsn · 2024-04-08T14:16:43Z

qiskit/dagcircuit/dagdependency_v2.py

+        if key is None:
+            key = _key
+
+        return iter(rx.lexicographical_topological_sort(self._multi_graph, key=_key))


Suggested change

return iter(rx.lexicographical_topological_sort(self._multi_graph, key=_key))

return iter(rx.lexicographical_topological_sort(self._multi_graph, key=key))

I just stumbled upon this typo while working on something else. :-)

jakelishman

For others' reference: this DAGDependencyV2 is exploratory work that we're doing with Ed (@enavarro51) about reworking the DAGDependency into a usable and much faster form for template matching, and potentially using it more throughout other parts of the transpiler pipeline.

We're looking to merge it into the main Qiskit as a fully private object, mostly to support longer-term working on the project with Ed as an external contributor while working with us. There's a chance that the Python implementation never gets made fully public, but that instead we make a fully Rust version of this DAGDependencyV2 (with Python wrappers) and use that in things like template matching and commutation analysis. There are follow-up PRs to this that will do things like update the _update_wires function and the core data structure a little to include the requirement to track a leaves set when modifying the graph (in order to reduce the computational complexity of appends to the graph), but it's still in the largely exploratory phases at the moment.

Ed: I'm largely fine to merge this as-is, except for:

let's remove the public release note
we probably want to fix the typo Sebastian noticed

For the bits Sasha was talking about with remove_op_node (and really any removals): the best situation is probably just to remove those functions from this PR - if they're broken, there's no real reason to include them in even the exploratory merge. I've no issue with removing all the functions that exist that we don't immediately have a use for in the exploratory stuff - we can add useful things as/when we need them. If anything, it's probably best to start with less than more, just so we don't forget to remove the cruft later.

jakelishman · 2024-04-09T17:33:39Z

releasenotes/notes/add-dagdependency-v2-7c591d708d6a8ac1.yaml

Let's remove the release note, to keep it very much seeming internal.

Will remove the release note. As to other functions, I'll remove the remove_op_node and remove_all_ops_named functions. My question is, what does "all the functions that exist that we don't immediately have a use for" mean? There seems to be a difference of opinion on what that includes.

These `quantum_successors` etc have no meaning in `DAGDependency` (and V2) since the edges don't carry the data that the `DAGCircuit` functions check for; `DAGDependency` is in part a deliberate erasure of this data.

jakelishman

Thanks for this Ed. I've removed the quantum/classical successor/predecessor methods because they were checking edge data that completely doesn't exist on DAGDependency. I'm not super convinced that replace_block_with_op is completely right yet, but I think that might be the same as in DAGDependency and I don't want to erase it out from under Sasha.

Just to highlight to anyone else reading this, again: all this is deliberately not public, and it's all so not public (undocumented, and has explicitly private names) that we're not even marking it with the "experimental" API. This is for near-term experimentation and there's a good chance it may even be replaced entirely with a pure-Rust implementation before being made public.

enavarro51 added 7 commits January 4, 2024 06:55

Fix typing-extensions

08a23c5

Merge branch 'main' of https://github.com/Qiskit/qiskit-terra into main

8d06451

Merge branch 'main' of https://github.com/Qiskit/qiskit-terra into main

f70314a

Merge branch 'main' of https://github.com/Qiskit/qiskit-terra into main

c179d5b

Add dagdependency_v2 and converters

02adb42

Add V2 tests

229bf55

Cleanup testing

ed2d8ef

enavarro51 requested a review from a team as a code owner February 1, 2024 15:09

Merge branch 'main' into dag_dep_v2

ae06ad9

enavarro51 added 6 commits February 1, 2024 07:46

Move import

e186142

Merge branch 'dag_dep_v2' of github.com:enavarro51/qiskit-terra into …

f12d33d

…dag_dep_v2

Add copy_empty_like and topological_op_nodes

d9cf3cb

Merge branch 'main' of https://github.com/Qiskit/qiskit-terra into main

83972c6

Merge branch 'main' into dag_dep_v2

1659a57

Lint and providers update

3531ce3

alexanderivrii mentioned this pull request Feb 4, 2024

[WIP] more general block collection #11614

Closed

enavarro51 added 2 commits February 4, 2024 09:57

Change to apply_operation_back

8913f99

Fix converter init

f382edd

alexanderivrii reviewed Feb 5, 2024

View reviewed changes

Cleanup and remove indices methods

95affb7

alexanderivrii reviewed Feb 6, 2024

View reviewed changes

enavarro51 added 4 commits February 6, 2024 08:24

Change to _get_node and cleanup

f877937

Merge branch 'main' of https://github.com/Qiskit/qiskit-terra into main

e6d975c

Merge branch 'main' into dag_dep_v2

98ff569

Add reno

0b29d20

enavarro51 requested a review from nonhermitian as a code owner February 11, 2024 00:48

enavarro51 added 3 commits February 10, 2024 16:51

Merge branch 'main' of https://github.com/Qiskit/qiskit-terra into main

d698cac

Merge branch 'main' into dag_dep_v2

3d6fcaf

Lint

e13e700

enavarro51 mentioned this pull request Feb 11, 2024

Update _update_edges in DAGDependencyV2 #11764

Closed

enavarro51 added 11 commits February 14, 2024 11:37

Merge branch 'main' of https://github.com/Qiskit/qiskit-terra into main

415504a

Merge branch 'main' of https://github.com/Qiskit/qiskit-terra into main

b0e6690

Merge branch 'main' into dag_dep_v2

bd3084a

Convert to using leading _ for class and functions

4e30d7b

Merge branch 'main' of https://github.com/Qiskit/qiskit-terra into main

f0731e6

Merge branch 'main' into dag_dep_v2

6aea838

Cleanup test file import

08bae9f

Fix converters

43a2fef

Restart CI

7fdd21c

Merge branch 'main' of https://github.com/Qiskit/qiskit-terra into main

e5c951b

Merge branch 'main' of https://github.com/Qiskit/qiskit-terra into main

2de1ea6

sbrandhsn reviewed Apr 8, 2024

View reviewed changes

jakelishman reviewed Apr 9, 2024

View reviewed changes

enavarro51 and others added 5 commits April 9, 2024 15:07

Merge branch 'main' of https://github.com/Qiskit/qiskit-terra into main

e815358

Merge branch 'main' into dag_dep_v2

7ecd2fa

Remove reno and remove_ops functions and fix typo

ce1cf24

Remove init entries for v2

1f40e61

Remove meaningless methods

902fc49

These `quantum_successors` etc have no meaning in `DAGDependency` (and V2) since the edges don't carry the data that the `DAGCircuit` functions check for; `DAGDependency` is in part a deliberate erasure of this data.

jakelishman approved these changes Apr 16, 2024

View reviewed changes

jakelishman enabled auto-merge April 16, 2024 12:47

jakelishman added the Changelog: None Do not include in changelog label Apr 16, 2024

jakelishman added this pull request to the merge queue Apr 16, 2024

Merged via the queue into Qiskit:main with commit 6cae4cf Apr 16, 2024

jakelishman mentioned this pull request Jun 16, 2025

Improve the performance of qiskit.converters.dag_to_dagdependency #14612

Open

		def remove_op_node(self, node):
		"""Remove an operation node n.

		class TestCircuitToDagCanonical(QiskitTestCase):
		"""Test QuantumCircuit to DAGDependency."""

	return iter(rx.lexicographical_topological_sort(self._multi_graph, key=_key))
	return iter(rx.lexicographical_topological_sort(self._multi_graph, key=key))

Add DAGDependencyV2 and Converters #11705

Add DAGDependencyV2 and Converters #11705

Uh oh!

Conversation

enavarro51 commented Feb 1, 2024 • edited by jakelishman Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary

Details and comments

Uh oh!

qiskit-bot commented Feb 1, 2024

Uh oh!

coveralls commented Feb 1, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 8705828497

Warning: This coverage report may be inaccurate.

Details

💛 - Coveralls

Uh oh!

alexanderivrii left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

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!

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!

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!

alexanderivrii left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jakelishman left a comment

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!

jakelishman left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

enavarro51 commented Feb 1, 2024 •

edited by jakelishman

Loading

coveralls commented Feb 1, 2024 •

edited

Loading