  This paper introduces Fermihedral, a compiler framework focusing on
discovering the optimal Fermion-to-qubit encoding for targeted Fermionic
Hamiltonians. Fermion-to-qubit encoding is a crucial step in harnessing quantum
computing for efficient simulation of Fermionic quantum systems. Utilizing
Pauli algebra, Fermihedral redefines complex constraints and objectives of
Fermion-to-qubit encoding into a Boolean Satisfiability problem which can then
be solved with high-performance solvers. To accommodate larger-scale scenarios,
this paper proposed two new strategies that yield approximate optimal solutions
mitigating the overhead from the exponentially large number of clauses.
Evaluation across diverse Fermionic systems highlights the superiority of
Fermihedral, showcasing substantial reductions in implementation costs, gate
counts, and circuit depth in the compiled circuits. Real-system experiments on
IonQ's device affirm its effectiveness, notably enhancing simulation accuracy.
