IBM Research Team Bounds Quantum Circuit Complexity Growth

One gate at a time: complexity growth in random quantum circuits Until now, quantifying how quickly simulating quantum computations becomes classically intractable relied upon approximations yielding polynomial improvements only. New calculations demonstrate that computational resources required for these simulations grow almost linearly with time, specifically as Ω(T / log T), up to times around 4ⁿ. This represents an improvement by a factor of poly(n) over existing bounds, offering fresh insight into fundamental limits of quantum computation.