Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 324 / 4 / a / i / Solution

The process admits a strong classical simulation of a quantum circuit if a classical algorithm, given its circuit and input descriptions, computes either output probability to the requested polynomial precision in time polynomial in the input size and precision parameter. This asks for the probabilities themselves, rather than only efficient samples from their distribution.