Лёгких путей в квантовых вычислениях не бывает ⚡ экспресс
Исследуется вычислительная мощность неэрмитовых квантовых схем. Если когерентная нормированная неунитарная эволюция реализуема с полиномиальными затратами, модель способна на постселекцию, что даёт неправдоподобную сложностную мощь. Определён класс NHBQP(U) для полиномиальных схем с фиксированным неунитарным гейтом U на O(1) кубитах и перенормировкой. Доказано: NHBQP(U) содержит PostBQP; в равномерной модели NHBQP(U)=PostBQP=PP. PostBQP считается неразрешимым, поэтому масштабируемое неэрмитово преимущество требует ограничений. Изучены очищения ограниченных систем: унитарные схемы с постселекцией моделируют неэрмитову эволюцию и траектории. Если очищение в сильно симулируемом семействе (Клиффорд, matchgate, тензорные сети малого ранга) при вероятности событий Ω(2^{-poly(n)}), симуляция классически эффективна. Добавление неэрмитовости к универсальной системе даёт чрезмерную мощь, а к сильно симулируемой — выигрыша нет.
Квантовые компьютеры танцуют обратимый вальс: шаг вперёд — шаг назад, и система в исходной точке. Но в некоторых процессах танцор исчезает в темноте без возврата. Такие необратимые шаги добавляют в систему энтропию — меру необратимого беспорядка. Если бы квантовый компьютер мог легко исполнять такие финты, он бы решал задачи, на которые у обычных машин ушла бы вечность. Это нарушало бы все известные правила сложности вычислений. Однако та же логика подсказывает: лёгких путей нет. Удивительно, но схожая безвозвратная потеря информации происходит у чёрных дыр, и эта загадка заставила Хокинга пересмотреть собственные взгляды. Природа не терпит вседозволенности — даже в квантовом мире.
🎯 Обратимость вычислений в квантовом мире не прихоть, а следствие закона сохранения энергии — принципа, работающего с паровых машин до наших дней.