The original idea that a quantum machine can potentially solve many-body quantum mechanical problems more efficiently than classical computers is due to R. Feynman who proposed the use of quantum computers to investigate the fundamental properties of nature at the quantum scale. In particular, the solution of problems in electronic structure, material design, high energy physics, and statistical mechanics is a challenging computational task as the number of resources needed increases exponentially with the number of degrees of freedom. Thanks to the development of new quantum technologies witnessed over the last decades, we have now the possibility to address these classes of problems with the help quantum computers. To achieve this goal, new quantum algorithms able to best exploit the potential quantum speedup of state-of-the-art, noisy, quantum hardware have also been developed . In this talk, I will first introduce the basic quantum algorithms for the solution of quantum mechanics and statistical mechanics problems with exponential scaling in the number of dregrees of freedom, focusing on those aspects that will make possible to achieve quantum advantage with near-term quantum computers. In the second part, I will highlight the potential advantages of the new generation of quantum algorithms for applications in chemistry [2,3] (ground and excited states calculations), high energy physics  (lattice gauge theory) and biology . Finally, applications of quantum machine learning algorithms in natural science applications will also be discussed.  N. Moll, et al., Quantum Sci. Technol., 3, 030503 (2018).  P. Baroutsos, et al., Phys. Rev. A, 98, 022322 (2018).  P. Baroutsos, et al., Chemical Science, 12, 4345 (2021).  S. Mathis, et al., Phys. Rev. D, 102, 094501 (2020).  A. Robert et al., npj Quantum Inf., 7, 1-5 (2021). *The authors acknowledge the financial support from the Swiss National Science Foundation (SNF) through Grant No. 200021-179312.