qiskit-bot
commented
1 month ago One or more of the following people are relevant to this code:
@Qiskit/terra-core@kevinhartman@mtreinish
Open henryzou50 opened 1 month ago
qiskit-bot
commented
1 month ago One or more of the following people are relevant to this code:
@Qiskit/terra-core@kevinhartman@mtreinish
coveralls
commented
1 month ago | Changes Missing Coverage | Covered Lines | Changed/Added Lines | % | ||
|---|---|---|---|---|---|
| crates/accelerate/src/sabre/route.rs | 61 | 63 | 96.83% | ||
| crates/accelerate/src/sabre/heuristic.rs | 8 | 29 | 27.59% | ||
| <!-- | Total: | 71 | 94 | 75.53% | --> |
| Files with Coverage Reduction | New Missed Lines | % | ||
|---|---|---|---|---|
| crates/qasm2/src/lex.rs | 7 | 91.73% | ||
| crates/qasm2/src/parse.rs | 18 | 96.69% | ||
| <!-- | Total: | 25 | --> |
| Totals | |
|---|---|
| Change from base Build 10506699788: | -0.03% |
| Covered Lines: | 67855 |
| Relevant Lines: | 75755 |
Summary
This pull request introduces a new heuristic,
CriticalHeuristic, to theSabreSwappass in Qiskit. TheCriticalHeuristicprioritizes routing decisions based on the criticality of quantum operations, as determined by the number of descendant gates in the circuit's Directed Acyclic Graph (DAG). This enhancement provides users with additional control over the routing process, allowing them to optimize circuits by focusing on critical paths, potentially reducing overall circuit depth and/or swap count.Details and Comments
Key Changes:
New Heuristic (
CriticalHeuristic) inheuristic.rs:CriticalHeuristicstruct, which ranks quantum gates by the number of descendants they have, prioritizing gates with more descendants.CriticalHeuristicincludesweightandscaleparameters, allowing users to adjust its impact on routing decisions.Descendant Ranking Map in
route.rs:descendants_rankfield in theRoutingStatestruct to store the ranking of nodes based on the number of descendants. This map is populated only when theCriticalHeuristicis enabled.populate_descendants_rank_mapthat calculates and ranks nodes based on their number of descendants, storing the results in thedescendants_rankmap.Integration of
CriticalHeuristicinchoose_best_swap:choose_best_swapmethod to evaluate potential swaps by considering how they enable the routing of gates with high descendant rankings. Swaps that allow the routing of more critical operations are favored.update_routemethod and the main routing loop inswap_map_trialhave been updated to integrate theCriticalHeuristic, ensuring that routing decisions consider the criticality of operations when this heuristic is used.Future Considerations:
CriticalHeuristicon different types of circuits, particularly those with complex critical paths. Depending on the results, I may need to reconsider how the scoring is calculated to optimize performance across a broader range of circuits.Notes
CriticalHeuristicis expected to perform well in circuits where managing critical paths is essential, but its effectiveness across all circuit types needs further validation.CriticalHeuristicwith the SABRE routing framework, and to verify that it interacts as expected with other heuristics.