Quantum computers offer a promising solution to the task of simulating many-body physics A scalable fault-tolerant quantum computer with a large supply of logical qubits would allow us to answer many interesting questions about physical systems. In the near term we can only access a limited number of noisy physical qubits, and thus cannot do full error correction. This has raised an important theoretical question of identifying the limitations and applicability of near-term quantum hardware.

In my talk, I will first consider quantum dynamics, in the presence of a constant rate of depolarizing noise, that are aimed at solving a classical or quantum optimization problem. I will provide theoretical and numerical arguments that for such dynamics, the entropy accumulation through the circuit imposes a hard constraint on the circuit depths/evolution time beyond which we expect to lose quantum advantage in solving such problems.I will then consider the question of possible quantum advantage with less pessimistic noise models than depolarizing noise. In the worst-case, with a constant rate of error, it is generically expected that the accuracy of a quantum simulation/computation degrades with both the error rate *and* problem size. However, I will show that for a coherent error model, many physically relevant many-body problems, where the goal is to calculate the phase-diagram of a many-body order parameter, are robust to errors and can possibly solved without error correction while retaining an accuracy guarantee limited only by the error rate and not by the size of the problem.

**References:**

- R. Trivedi, J. I. Cirac, “Transitions in computational complexity of continuous-time local open quantum dynamics”, Phys. Rev. Lett 129 (26), 260405 (2022).
- Gonzalez*, R. Trivedi*, J. I. Cirac, “Error propagation in NISQ devices for solving classical optimization problems,” Phys. Rev. X Quantum 3 (4), 040326 (2022).
- Trivedi, A. F. Rubio, J. I. Cirac, “Quantum advantage and stability to errors in analogue quantum simulators,” arXiv:2212.04924 (2022).