improving `quantum_causal_cone` method in python

alexanderivrii commented 5 days ago

Summary

When trying to port the method DAGCircuit.quantum_causal_cone (introduced in #10325) to Rust, I have noticed that the existing algorithm examines each node multiple times (when reached from different paths), making the algorithm worst-case exponential.

For a specific example, consider the circuit

q0_0: ──■─────────■─────────■─────────■─────────■─────────■───────
      ┌─┴─┐     ┌─┴─┐     ┌─┴─┐     ┌─┴─┐     ┌─┴─┐     ┌─┴─┐     
q0_1: ┤ X ├──■──┤ X ├──■──┤ X ├──■──┤ X ├──■──┤ X ├──■──┤ X ├──■──
      └───┘┌─┴─┐└───┘┌─┴─┐└───┘┌─┴─┐└───┘┌─┴─┐└───┘┌─┴─┐└───┘┌─┴─┐
q0_2: ──■──┤ X ├──■──┤ X ├──■──┤ X ├──■──┤ X ├──■──┤ X ├──■──┤ X ├      ...
      ┌─┴─┐└───┘┌─┴─┐└───┘┌─┴─┐└───┘┌─┴─┐└───┘┌─┴─┐└───┘┌─┴─┐└───┘
q0_3: ┤ X ├─────┤ X ├─────┤ X ├─────┤ X ├─────┤ X ├─────┤ X ├─────
      └───┘     └───┘     └───┘     └───┘     └───┘     └───┘     
q0_4: ────────────────────────────────────────────────────────────

In this PR we hash the set of processed non-directive nodes.

Let me also explain the point about not hashing "directive" nodes such as barriers (or measures). A barrier may involve all the qubits in the circuit, however not all of these should be considered to be a part of the causal cone. So when processing a barrier node the original algorithm only adds the quantum predecessors of that barrier node that intersect the current set of qubits in the quantum cone. However, this does potentially require to examine each barrier multiple times. (Aside: I am still not fully certain that this logic is 100% correct, however I was not able to find an example where this does not do what's intended). See also #10325.

This PR does not change this logic, however for clarity the two cases (directives and not-directives) are treated separately (and there are some other minor renaming and other minor code simplifications). It also adds more Python tests that explore the corner-cases.

It would be nice to have this PR merged before adding the Rust version of this to the new DAGCircuit, as it can serve as a reference for that implementation and also adds more python tests.

qiskit-bot commented 5 days ago

One or more of the following people are relevant to this code:

@Qiskit/terra-core

coveralls commented 5 days ago

Pull Request Test Coverage Report for Build 9678104465

Details

15 of 15 (100.0%) changed or added relevant lines in 1 file are covered.
5 unchanged lines in 1 file lost coverage.
Overall coverage increased (+0.02%) to 89.776%

Files with Coverage Reduction	New Missed Lines	%
crates/qasm2/src/lex.rs	5	92.88%
<!--	Total:	5		-->

Totals
Change from base Build 9676629284:	0.02%
Covered Lines:	63802
Relevant Lines:	71068

💛 - Coveralls

coveralls commented 4 days ago

Pull Request Test Coverage Report for Build 9692828532

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

15 of 15 (100.0%) changed or added relevant lines in 1 file are covered.
93 unchanged lines in 3 files lost coverage.
Overall coverage increased (+0.02%) to 89.78%

Files with Coverage Reduction	New Missed Lines	%
crates/qasm2/src/lex.rs	5	92.88%
qiskit/circuit/quantumcircuit.py	16	95.69%
crates/circuit/src/operations.rs	72	72.35%
<!--	Total:	93	-->

Totals
Change from base Build 9676629284:	0.02%
Covered Lines:	63818
Relevant Lines:	71083

Qiskit / qiskit