Почему квантовый алгоритм QAOA не справился со стеклянным хаосом ✛ ✎ ✦
Поиск глобального минимума в модели спинового стекла Шеррингтона–Киркпатрика напоминает восхождение на ледник, где каждая трещина — коварный локальный оптимум, а истинное дно погребено под хаосом ледяных глыб. Классический альпинист, бредущий по градиенту, почти наверняка замёрзнет в ближайшей расщелине. Квантовый приближённый оптимизационный алгоритм (QAOA) был задуман как спасательный трос: за счёт квантовых эффектов он якобы способен просачиваться сквозь энергетические барьеры, словно сверхтекучий гелий — игнорируя трение ландшафта. Однако анализ с помощью приближения усечённой функции Вигнера рисует иную картину.
Этот метод, заимствованный из квантовой оптики и физики конденсированного состояния, подменяет квантовую эволюцию классическими вращениями, а начальные квантовые флуктуации — гауссовым шумом. Шум здесь — дрожь в руках альпиниста, порождённая принципом неопределённости Гейзенберга: чем точнее он фиксирует одно направление спина, тем сильнее размываются остальные. В терминах эффективного спина S минимальная амплитуда дрожи обратно пропорциональна S — как если бы знание маршрута лишало уверенности шагов.
Ключевой результат численного моделирования поражает: зависимость остаточной энергии от S немонотонна. При малых S энтропийный шум столь силён, что альпиниста трясёт, будто он попал в ледяной шторм, и склона не различить. При больших S дрожь утихает, но начальное состояние — суперпозиция всех возможных спиновых конфигураций — превращается в точку неустойчивого равновесия, как карандаш на острие. Малейшее дуновение квантового ветра — и ошибка растёт экспоненциально. Оптимальный баланс достигается, когда S масштабируется с глубиной схемы p. Тогда остаточная энергия убывает как log(p)/p — в точности как у классических эвристик. Но самый горький глоток: если убрать начальный шум совсем и перенастроить параметры, чисто классическая динамика даёт сходимость 1/p, обгоняя любой QAOA. Финальное измерение лишь добинаризует спины, придавая решению товарный вид.
Эта работа бьёт в самое сердце квантовых амбиций в комбинаторной оптимизации. Если классические алгоритмы дышат в спину, то строительство многокубитных монстров для NP-трудных задач рискует стать экономической химерой. Однако наука учит не пессимизму, а трезвости. Подобные результаты заставляют переосмыслить природу квантового ускорения: возможно, его истинное призвание — не универсальный поиск, а моделирование квантовой материи, где классический компьютер бессилен в принципе. В конечном счёте, ледник спиновых стёкол показал: квантовая магия — не панацея, а ювелирный инструмент, и порой его главная сила — в умении вовремя замолчать.
Модель Шеррингтона–Киркпатрика, изначально созданная для описания магнитных сплавов, теперь активно используется в теории нейросетей и распознавании образов. Её хаотический ландшафт оказался идеальным тренажёром для алгоритмов, а заодно — могильщиком надежд на лёгкое квантовое ускорение.