catalyst icon indicating copy to clipboard operation
catalyst copied to clipboard

[Frontent] Review the topological sorting algorithm used in the two-staged tracing

Open sergei-mironov opened this issue 2 years ago • 0 comments

The future improvement reminder issue. The nested tape tracer introduced by https://github.com/PennyLaneAI/catalyst/pull/240 relies on the topological sorting which might need reviewing. The sorting is used as the final step in the merging of two lists of JAX equations: one list containing classical equation and the other one induced by the quantum tape. Currently the sorting uses JAX variables for building dependencies which may lead to correct yet ill-ordered flow of equations.

Some questions worth answering:

  • Could/should we preserve the original flow of equations as close as possible?
  • Could we simplify the sorting algorithm by removing Box used for dependency tracking?

sergei-mironov avatar Sep 21 '23 17:09 sergei-mironov