Add `DepthHeuristic` to SABRE routing heuristics

[henryzou50]

Summary

This pull request introduces a new heuristic, DepthHeuristic, to the SabreSwap. The DepthHeuristic is designed to minimize circuit depth by penalizing swaps that increase the circuit's depth during the routing process. This enhancement provides users with additional flexibility to prioritize depth optimization, complementing the existing heuristics in SABRE.

Note: This pull request is currently a draft. I am still working on refining the depth calculation to ensure it's "truly correct," and additional enhancements will be added in future commits.

Details and Comments

Key Changes:

1. New Heuristic (DepthHeuristic) in heuristic.rs:

   • Added the DepthHeuristic struct, similar to BasicHeuristic and DecayHeuristic.
   • The DepthHeuristic includes weight and scale parameters, allowing users to adjust its impact on routing decisions.
   • Unlike LookaheadHeuristic and DecayHeuristic, this heuristic does not require additional parameters like size or reset. It is solely focused on depth-based penalties.

2. Depth Tracking in route.rs:

   • Introduced qubit_depths in RoutingState to track the depth of each qubit as routing progresses. It is only updated if the pass is ran with the depth heuristic.
   • Implemented a circuit_depth method to calculate the depth of the circuit as we progress through the routing, and considers the additional swaps as 3 cnots.
   • Integrated the DepthHeuristic into the choose_best_swap method to penalize swaps that increase circuit depth.
   • Updated the update_route method to correctly adjust qubit_depths when applying swaps and gates.

3. Updates to sabre_swap.py and test_sabre_swap.py:

   • Integrated DepthHeuristic into the SABRE transpiler, making it available for use alongside other heuristics.
   • Added tests for DepthHeuristic to ensure it functions correctly within the SABRE routing framework.

Future Considerations:

• Depth Calculation Refinement: Currently, the depth calculations are based on whether a swap adds depth to the circuit but do not consider the impact of immediate gates that can be applied after the swap. This refinement is critical because prioritizing swaps that enable multiple immediate gates without significant depth increase can improve routing efficiency. I have these changes in a separate branch and will be added once the corresponding tests are validated and passing.

• Upcoming CriticalHeuristic: I am also working on a new CriticalHeuristic in another branch and will make a seperate PR for that once that passes all the tests. This heuristic will focus on the critical path of the DAG, prioritizing gates that are part of this path.

• Dynamic Scaling of Depth Impact: We may want to think about having future iterations may explore dynamically scaling the depth penalty based on other heuristics or the size of the circuit, providing more nuanced control over depth optimization during routing.

• Automated Depth Validation: While manual tests were conducted to validate circuit_depth, an automated test would be beneficial. Specifically, this test should compare circuit_depth in RoutingState with the depth of a decomposed circuit in Python. At the moment, I could not think of an efficient way that matches qiskit's testing scheme to compare the result of a function in rust vs in python. The test should also address scenarios involving initial DAG circuits with swap gates, which are currently not decomposed into three swaps in the Rust implementation.

[qiskit-bot]

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

• @Qiskit/terra-core
• @kevinhartman
• @mtreinish

[coveralls]

Pull Request Test Coverage Report for Build 14646234278

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

• 156 of 186 (83.87%) changed or added relevant lines in 3 files are covered.
• 288 unchanged lines in 9 files lost coverage.
• Overall coverage increased (+1.7%) to 89.548%

---

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
crates/accelerate/src/sabre/route.rs	142	146	97.26%
crates/accelerate/src/sabre/heuristic.rs	12	38	31.58%
<!--	Total:	156	186

Files with Coverage Reduction	New Missed Lines	%
crates/qasm2/src/lex.rs	5	92.73%
crates/accelerate/src/euler_one_qubit_decomposer.rs	6	91.33%
crates/qasm2/src/parse.rs	6	97.61%
crates/accelerate/src/consolidate_blocks.rs	11	94.72%
crates/accelerate/src/high_level_synthesis.rs	20	90.55%
crates/accelerate/src/unitary_synthesis.rs	28	94.78%
crates/accelerate/src/vf2_layout.rs	28	83.11%
crates/accelerate/src/basis/basis_translator/mod.rs	55	88.99%
crates/accelerate/src/target_transpiler/mod.rs	129	79.11%
<!--	Total:	288

Totals
Change from base Build 14637349697:	1.7%
Covered Lines:	70689
Relevant Lines:	78940

---

💛 - Coveralls

[henryzou50]

Thank you for the review! I’ve made the changes to address your comments.

The most consistent case studies where this new heuristic shows significant improvement over lookahead are circuits with sequentially dependent interaction chains, like QFT and GHZ. I’ve added a test case to demonstrate this improvement, though I’m not entirely sure how to conclusively prove the improvement is inherent to the depth heuristic rather than due to random variability.

From my testing, for large circuit sizes and coupling maps with higher connectivity than a ring, the depth heuristic consistently yields better depth reductions by leveraging parallel swaps, although it does lead to an increase in the number of gates added. To ensure thoroughness, the test I added runs multiple trials and compares the median results. However, in practice, a single trial often shows this advantage clearly.