A recent trend developing in quantum compiler optimizations [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]} is to
exploit more potential from the hardware with more detailed device information.
Different from the innovations in this direction that are mostly driven by the underlying technologies, Paulihedral takes another approach which is to enable deeper compiler optimizations by leveraging the algorithmic properties of the high-level quantum programs.
Relatively little attention has been paid to this direction because
1) it is exceedingly difficult to extract useful high-level semantics from gate sequences, which is the level that most compiler infrastructures today operate at,
and
2) scalable yet effective static analysis of quantum programs is also very hard as the size of the operation matrices grows exponentially with the number of qubits.
We believe that these are two critical yet difficult open problems in the future development of quantum compiler/software infrastructure since they prevent the compiler from automatically detecting high-level and large-scale optimization opportunities.
