Abstract Error mitigation techniques, while instrumental in extending the capabilities of near-term quantum computers, often suffer from exponential resource scaling with noise levels. To address this limitation, we introduce a novel approach, namely, constant runtime error mitigation by restricted evolution (EMRE). Through numerical simulations, we demonstrate that EMRE surpasses the performance of Probabilistic Error Cancellation (PEC) while maintaining constant sampling overhead. The constant sampling overhead comes at the cost of a small non-zero bias. We provide a methodology to compute the optimal bias by connecting it to a resource-theoretic measure. We also evaluate bounds on the bias under different noise models and give exact results for the case of depolarizing and dephasing noise. Using these exact results, we derive an even more efficient strategy to implement EMRE. Additionally, we introduce Hybrid EMREs (HEMREs), a continuous family of error mitigation protocols that encompass PEC and EMRE as special cases. HEMREs offer a tunable bias parameter, enabling a trade-off between sample complexity and error reduction. The numerical evidence suggests the scalability and practicality of our proposal. Hence, our error mitigation protocols provide flexibility in balancing error mitigation with computational overhead, catering to practical application requirements of near-term and early-fault tolerant quantum devices. Similar content being viewed by others Acknowledgements We would like to thank Zhenyu Cai, Suguru Endo, Abhinav Kandala, Ying Li and Zlatko Minev, for helpful discussions. We thank our management executives- Kevin Ferreira, Yipeng Ji, Paria Nejat of LG Electronics Toronto AI Lab for their constant support throughout this work. Last but not least, we are grateful to Euwern Teh of LG Electronics Toronto AI Lab for showing us how to draw beautiful quantum circuits. Throughout our numerical computations, we used the open-source software Mitiq58 to deploy PEC in circuits. No funding was received for this research. Author information Authors