Три тысячи метров над уровнем моря, отвесная стена. Классический скалолаз карабкается по одному маршруту, шаг за шагом, и часто застревает в локальном минимуме — небольшой нише, из которой нет хода вверх. Квантовый скалолаз действует иначе: он способен перепрыгнуть через ущелье и приземлиться в соседнем бассейне энергии, где маршрут лучше.
Энергетический ландшафт — это график энергии всех возможных конфигураций системы. Для задачи оптимизации каждая точка ландшафта соответствует решению, а высота — его качеству. NP-трудные задачи, такие как поиск основного состояния модели Изинга, имеют изрезанный ландшафт с множеством локальных минимумов. Классические эвристики, например имитационный отжиг, имитируют охлаждение металла: система медленно остывает, стремясь к минимуму энергии, но часто застревает в неглубоких ямах.
Алгоритм Qjump работает итеративно. Имея текущее решение — битовую строку, — квантовая схема генерирует множество кандидатов, «перепрыгивая» в соседние энергетические бассейны. Схема состоит из слоя кодирования, нескольких слоёв операторов стоимости и смешивания, вдохновлённых QAOA, и измерений. Параметры схемы не оптимизируются вариационно, а берутся из предварительно рассчитанных значений для глубокого QAOA, что исключает проблему бесплодных плато. После квантового сэмплирования классический компьютер выполняет локальный поиск — жадный спуск — для каждого кандидата и выбирает лучшее решение.
Эксперименты проводились на 104-кубитном сверхпроводящем процессоре с медианной точностью двухкубитных гейтов 99,5%. На 20 отобранных сложных экземплярах Qjump в среднем находил глобальный минимум в 2,23 раза чаще, чем имитационный отжиг, за фиксированное время. При экстраполяции на будущее оборудование с частотой сэмплирования 0,4 МГц и быстрым управлением через FPGA оценка времени до решения показала ускорение в 2,34 раза. Для меньших систем преимущество было меньше: 0,98 раза для 60 кубитов и 1,56 раза для 84 кубитов. Это указывает на улучшение с ростом размера задачи. QAOA с локальным поиском оказался почти неэффективным для этих задач.
Qjump показал, что гибридные схемы — где квантовый процессор используется только для «прыжков» по ландшафту, а классический компьютер для точной оптимизации — могут быть практичным путём к квантовому преимуществу на шумных промежуточных квантовых устройствах. Раньше было неясно, могут ли такие устройства без коррекции ошибок превзойти классические эвристики. Теперь есть конкретный механизм разделения труда, снижающий требования к глубине схем и качеству кубитов. Это расширяет применимость существующих квантовых процессоров для задач оптимизации уже сегодня: логистика, планирование, финансы.
Квантовый скалолаз не заменяет классического. Он лишь перепрыгивает через ущелья, а классический спуск доводит решение до совершенства. Вместе они взбираются туда, куда поодиночке не добраться.
Для отбора сложных экземпляров задачи учёные сгенерировали 4000 случайных конфигураций связей и полей, а затем оставили только 20, на которых классический имитационный отжиг работал хуже всего. Это гарантирует, что сравнение было честным: квантовый алгоритм испытывался на самых трудных случаях.