Optimizing a quantum circuit is hard because it requires exploring a vast space of functionally equivalent circuits, produced by applying local circuit rewrites such as gate cancellation and commutation. Each additional rewrite can exponentially expand the space of equivalent circuits, so existing optimizers can only explore a tiny fraction of this space and often produce suboptimal results. We present \textsc{Quasar}, a new quantum circuit optimizer that can generate a \emph{step-limited optimal} circuit: given a bound on rewrite iterations, it returns the lowest-cost circuit reachable within that bound. To achieve this, \textsc{Quasar} constructs two complementary e-graphs for the quantum circuit's graph and sequence representations. \textsc{Quasar} then infers an atomic rewrite set for application on both e-graphs, which improves optimization performance by orders of magnitude. Finally, \textsc{Quasar} employs a series of new optimization techniques to ensure both soundness and scalability of equality saturation on quantum circuits. Across standard benchmarks, \textsc{Quasar} achieves geometric-mean reductions of 20.2% in 2-qubit gate count, 33.5% in total gate count, and 24.2% in circuit depth, and a 21.4% fidelity improvement over unoptimized circuits, outperforming or matching state-of-the-art rewrite-based optimizers on 75%, 92%, 62%, and 80% of circuits, respectively.