Лекция 6. Графовые состояния и симуляция стабилизаторных схем

На этой Лекции мы обсудили, как можно использовать графовые состояния для симуляции стабилизаторных схем. Любое стабилизаторное состояние локально клиффордово (LC) эквивалентно графовому состоянию. При этом, два графовых состояния локально LC-эквивалентны тогда и только тогда, когда их графы эквивалентны при действии локальной комплементации. Чистые стабилизаторные состояния можно хранить в памяти как таблицу смежности, тогда такая таблица занимает $\mathcal{O}(n d)$ памяти, где $n$ число кубитов и $d$ максимальная степень графа. Действие однокубитных клиффордовых вентилей в этом случае занимает $\mathcal{O}(1)$ времени. Чтобы обновить состояние при действии $CZ$, может потребоваться обновлять граф при помощи локальных комплементаций, это займёт $\mathcal{O}(d^2)$ времени. Так же, однокубитные измерения тоже займут $\mathcal{O}(d^2)$ времени. Описанный симулятор работает на практике не сильно медленнее, чем метод стабилизаторных табло, а в некоторых задачах значительно его обгоняет.