We designed, fabricated, and measured anti-reflection coating (ARC) on sapphire that has 116% fractional bandwidth and transmission of at least 97% in the millimeter wave band. The ARC was based on patterning pyramid-like sub-wavelength structures (SWS) using ablation with a 15 W femto-second laser operating at 1030 nm. One side of each of two discs was fabricated with SWS that had a pitch of 0.54 mm and height of 2 mm. The average ablation volume removal rate was 1.6 mm$^{3}$/min. Measurements of the two-disc sandwich show transmission higher than 97% between 43 and 161 GHz. We characterize instrumental polarization (IP) arising from differential transmission due to asymmetric SWS. We find that with proper alignment of the two disc sandwich RMS IP across the band is predicted to be 0.07% at normal incidence, and less than 0.6% at incidence angles up to 20 degrees. These results indicate that laser ablation of SWS on sapphire and on other hard materials such as alumina is an effective way to fabricate broad-band ARC.