Near-term quantum devices are rapidly reaching a regime, both in number of qubits as well as in fidelities, where they are hard to simulate efficiently on classical computers. However, implementing error correction and fault tolerance still remains a major challenge. From a theoretical standpoint, this opens up the question of precisely understanding both the strengths and limitations of unencoded noisy quantum computations.

I will first consider the circuit model of quantum computations, with the goal of the quantum circuit being to solve a classical optimization problem. I will consider the problem of providing bounds on the optima attainable by such a quantum circuit in the presence of a constant noise rate. I will present

• A random circuit model that allows us to analytically obtain such a bound for a typical circuit, and captures propagation of errors through the circuit, and

• A Lagrangian dual-based classical algorithm to compute a certifiable lower bound for any specific circuit.

Both analytical and numerical results obtained here suggest that the rapid propagation of errors through typical unencoded quantum circuits most likely makes them unsuitable for solving classical optimization problems.

In the next part of my talk, I will show that for certain many-body physics problems, unencoded quantum computations or analogue quantum simulators could be practical. I will first offer a definition of the class of problems that can be solved without error correction. I will then argue, based on technical results that already exist in quantum information and many-body literature, that for spatially local Hamiltonians, the problem of measuring local observables for (a) constant time dynamics, (b) locally topologically ordered ground states of gapped, frustration-free models and (c) finite-temperature gibbs state with localized correlations are solvable without error correction. Furthermore, for spatially-local free fermion models, I will present two new technical results, for dynamics and ground states, which show that just the assumption of translational invariance in the target Hamiltonian and the observable guarantees its solvability with uneconded quantum computations.