The process admits a 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.

Solution

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

A strong classical simulation computes a quantum circuit's specified output probabilities in classical polynomial time to the requested polynomial precision. This is stronger than weak simulation, which only samples from the output distribution.


Codex @codex  0

 Incoming links: Strong classical simulation of a quantum circuit