Адиабатические квантовые вычисления: почему бы просто не установить систему в ее проблемном гамильтониане HPHPH_{P} немедленно?

Справочная информация. В любом алгоритме адиабатического квантового компьютера (АКК) мы решаем задачи следующим образом: у нас есть начальный гамильтониан, ЧАС 0 , основное состояние которого легко найти, и проблемный гамильтониан ЧАС п , основное состояние которого кодирует решение нашей задачи. Если мы затем развиваем наш AQC на время Т так что его энергия описывается гамильтонианом

ЧАС ( т ) "=" ( 1 − т / Т ) ЧАС 0 + ( т / Т ) ЧАС п
то при соблюдении нескольких условий система будет находиться в основном состоянии ЧАС п вовремя Т (и вуаля, у нас будет решение нашей проблемы)

Вопрос: Если мы просто настроим АКК так, чтобы его энергия изначально описывалась гамильтонианом ЧАС п , почему бы системе просто не «упасть» в свое основное состояние (немедленно закодировав решение нашей проблемы)? Почему нам нужно эволюционировать АКК из исходного гамильтониана? ЧАС 0 в ЧАС п ?

Ответы (3)

Большинство NP-полных задач можно сформулировать как нахождение основного состояния некоторого гамильтониана. Если вы создадите физическую систему с таким гамильтонианом, это будет «фрустрированная система». Он перейдет в состояние, являющееся локальным минимумом энергии, и, хотя квантовая механика говорит, что он в конце концов перейдет в основное состояние (при условии, что он не изолирован, то есть существует какой-то механизм потери энергии), время, затрачиваемое на это, легко может быть на много порядков больше, чем время жизни Вселенной.

Если вы хотите вычислить основное состояние произвольного проблемного гамильтониана, вам нужно выполнить поиск по 1/2 ^ N состояниям. Для N=100 это практически невозможно даже при массовом распараллеливании, и даже это все еще на порядки ниже размеров задач, имеющих промышленное применение. Конечно, лучшие классические алгоритмы используют эвристику и структуру задач для повышения управляемости, но есть надежда, что AQC обеспечит хотя бы полиномиальное ускорение некоторых алгоритмов и вытеснит из воды лучшие классические алгоритмы на самых больших суперкомпьютерах ( еще предстоит продемонстрировать).

Однажды я задал точно такой же вопрос во время курса по квантовым вычислениям. Системы «попадают» в свои основные состояния только тогда, когда они находятся в тепловом равновесии при нулевой температуре . Обе эти части проблематичны: (а) многие системы, которые были предложены для квантовых вычислений, имеют энергетические шкалы, достаточно низкие, чтобы довести их до достаточно низких температур чрезвычайно сложно, и (б) как указал Питер Шор, вы понятия не имеете сколько времени потребуется системе, чтобы на самом деле достичь теплового равновесия - у вас может быть физический эквивалент проблемы со знаком Монте-Карло, где для локальных возмущений требуется экспоненциально много времени для размера системы, чтобы привести вас к тепловому равновесию.

Но если вы можете управлять начальным гамильтонианом ЧАС 0 , вы можете "принудить" систему к ее основному состоянию намного быстрее - в принципе с помощью фильтрации измерений, но более реалистично, делая ЧАС 0 нефрустрированный и с очень большим характерным энергетическим масштабом. Например, если у вас есть система квантовых спинов, и вы прикладываете ко всей системе огромное однородное поле («огромное» означает намного большее, чем температура и соответствующий масштаб взаимодействия спинов), тогда вся система будет выровнена по полю очень сильно. быстро, и вы можете быть уверены, что находитесь в основном состоянии.

На самом деле довольно легко (по крайней мере, в теории) построить системы так, чтобы (а) не было проблемой. Большая проблема (б).
@PeterShor Верно, но я думаю, что есть системы, в которых (а) сложно. D-Wave работает («работает») при 15 мК, чего не так уж сложно достичь, но разве нет также предложений по AQC в системах с холодным атомом (например, arxiv.org/abs/quant-ph/0406144 )? Это должно быть выполнено в масштабе нанокельвина, что намного, намного сложнее, чем милликельвин.
@tparker Спасибо, отличный ответ. Является ли это однородное поле (которое применяется к системе, чтобы ускорить ее достижение основного состояния) тем, что используется в алгоритмах квантового отжига (например, в машинах D-Wave)? И это то, что делает возможным «туннелирование» между барьерами, разделяющими локальные минимумы в алгоритмах квантового отжига?
@AlexMichael Я не знаю ответа на твой первый вопрос. Я не уверен, понимаю ли я ваш второй вопрос, но адиабатическая теорема гарантирует, что основное состояние начального гамильтониана будет развиваться в основное состояние конечного гамильтониана, пока гамильтониан изменяется намного медленнее, чем установленная шкала времени через энергетическую щель в первое возбужденное состояние, потому что система может квантово-туннелировать через энергетические барьеры, пока у нее есть для этого достаточно времени. В принципе, детали исходного гамильтониана не важны, важен только размер его энергетической щели.
почему я могу заставить исходный гамильтониан H0 находиться в основном состоянии, но не заставить конечный гамильтониан находиться в основном состоянии?
@hii: исходный гамильтониан выбран специально, чтобы вы могли заставить его находиться в основном состоянии.
@hii Да, как я уже сказал выше, ключевые ингредиенты, из которых состоит ЧАС 0 Гораздо легче иметь дело с (а) нефрустрированным основным состоянием и (б) очень большим разрывом до первого возбужденного состояния. Такие гамильтонианы довольно легко спроектировать, и они переходят в основное состояние гораздо быстрее, чем окончательный «проблемный» гамильтониан. ЧАС п (который, как правило, разочаровывает и сложен в разработке).

Вы начинаете в каком-то состоянии, которое тогда представляет собой сложную путаницу собственных состояний. И вы не дали механизм распада. Просто эволюция с одним Hp. Вы знаете только, как начать с основного состояния H0 и двигаться оттуда.

Адиабатические квантовые вычисления: почему бы просто не установить систему в ее проблемном гамильтониане HPHPH_{P} немедленно?
СпросиСетьПолитика конфиденциальности1y, 1v