Title: Approximate Markovianity and the Classical Simulability of Noisy Quantum Circuits Speaker:  Yifan Frank Zhang (Princeton University) Date & Time:  December 4, 2025, 3:15pm Where to Attend: ATL 3100A and Virtual Via Zoom: https://princeton.zoom.us/j/94173454653
A many-body quantum state typically requires exponentially many parameters to describe. Yet, many physically relevant states possess structure that allows for efficient representations. In this talk, I will discuss a structural property called approximate Markovianity, which captures how information clusters in space. I will show how this concept enables new insights into phases of matter, spoofing quantum advantage, and the design of efficient generative AI models. In particular, I will present a classical algorithm for simulating noisy quantum circuits by leveraging approximate Markovianity. We prove that this algorithm runs in quasi-polynomial time when the noise rate exceeds a constant threshold. Furthermore, both analytical arguments and numerical experiments indicate that the same runtime extends to typical random quantum circuits—at arbitrary depth and noise levels—covering regimes beyond the reach of previous classical simulation methods. Taken together, our results significantly extend the boundary of classical simulability and highlight the limitations of noisy quantum circuits in demonstrating quantum advantage.
*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*