Вычислительная сложность cs.CC

В 2019 году группа теоретиков задалась простым вопросом: что произойдёт, если в обычный квантовый компьютер встроить один-единственный необратимый элемент — вентиль, который чуть-чуть «съедает» вероятность? Ответ оказался убийственным. Любой такой вентиль, сколь угодно слабый, мгновенно превращает машину в устройство, способное решать задачи класса PostBQP = PP.

Классический компьютер сортирует данные подобно человеку, методично перебирающему песчинки разного цвета — одну за другой. Квантовый процессор действует иначе, заимствуя принцип у природы: подобно тому как капля воды разлагает солнечный свет на радугу, демонстрируя весь спектр оттенков одновременно, новый алгоритм мгновенно схватывает суть гигантских массивов информации.

В квантовой механике есть список разрешённых операций, и до недавнего времени считалось, что любая операция из этого списка рано или поздно найдёт своё воплощение в лаборатории. Оказалось, что это не так. Некоторые измерения похожи на дверь, для которой математика выписала ключ, но физический мир отказывается его изготавливать. Ключ к этой двери — задача, которую компьютерщики называют «3SAT».

Стоит подать питание, и карусель Фробениуса приходит в движение: каждый элемент конечного поля переходит в своего q-го потомка, а координаты сдвигаются по кругу.

Осень 1956 года. Курт Гёдель выводит на листе бумаги вопрос, обращённый к умирающему Джону фон Нейману: можно ли проверить выполнимость булевой формулы быстрее, чем полным перебором? Ответ придёт через 69 лет — и окажется укусом логического уробороса, мифического змея, поедающего собственный хвост. Змей рождается из случайности.