Лекция 12. Лемма о разрежении, квазивероятностные разложения квантовых схем

На последней Лекции мы обсудили важную лемму про разложение состояния в сумму стабилизаторных состояний. Если задано некоторое разложение $\lvert\psi\rangle = \sum_j c_j \lvert\phi_j\rangle$, то можно воспользоваться процедурой рандомизации, и построить случайное состояние $\lvert\Omega\rangle$, которое является равномерной суммой стабилизаторных состояний, с большой вероятностью близкое к желаемому результату. При этом, число стабилизаторных состояний в разложении $\lvert\Omega\rangle$ ограничено квадратом суммы модулей в разложении $\sum_j \lvert c_j\rvert$. Идея леммы о разрежении близка к общей методике симуляции квантовых схем при помощи разложения в квазивероятностные суммы более простых схем.