Да, интересно вот так вот проникать в новые для себя области !
Но вообще-то "спиновое стекло" - это не система, а состояние (термодинамическая фаза). Я понимаю, что когда говорят "гамильтониан спиновых стекол" - хотят сказать "гамильтониан некоторой системы, допускающий при определённых условиях существование спин-стекольной фазы". Обычно в этом качестве рассматривается изинговский гамильтониан с дефектами, но состояние спинового стекла может быть реализовано и в других системах. В том числе и системах _без_ дефектов и не обязательно в изинговских.
Вообще, пересечение с комбинаторикой тут простое и давно понятное. Современные рассуждения, мне кажется, только подпускают туману, фокусируясь на модных в недавнее время спиновых стёклах (модных совсем по другой причине, связанной с третьим законом термодинамики и теоремой Нернста). Модель Изинга для квантового спина 1/2 допускает 2 состояния со спинами +1/2 и -1/2 (обычно умножают на 2 и говорят о спинах 1 и -1). Если спинов N, то состояний такой системы 2N. Налицо экспоненциальный рост, как в NP-полных задачах. Вычисление статистической суммы такой системы требует суммирования по всем состояниям и на первый взгляд (а в некоторых случаях это вроде бы можно даже доказать) решается только полным их перебором, а значит принадлежит к классу NP полных. Именно поэтому я первым делом именно её (для изинговского гамильтониана с внешним полем и произвольно разорванными связями, т.е. с дефектами) и решал на своём " квантовом компьютере здесь и сейчас".
Но есть нюансы. Для изинговской системы из N спинов в присутствии внешнего поля аналитическое выражение для статистической суммы неизвестно. Но, если внешнего поля нет, то для той-же системы N спинов с теми же 2N состояниями Изинг в своей знаменитой работе 1925-го года такое выражение получил (собственно, именно поэтому модель и стала носить его имя).
Надо отметить, что я эту статью отыскал, пытаясь отыскать другую статью про поиск решений в ширину для стохастических алгоритмов поиска решения. Там тоже рассматривалась модель спиновых стёкол, поскольку, похоже, её удобно так рассматривать. И в той статье так же ходили по ландшафту целевой функции, только по-другому. Да, а саму статью я обнаружил после расследования, как же умные люди в университетах решают проблемы, что вы решали с помощью "квантового компьютера".
Статья в моём посту интересна тем, что смотрит на задачи поиска решения логической выполнимости через их приближение (к 3-XOR разного рода) и предлагает некий параметр для характеризации этого приближения.
Конечно же, там упущено много интересного, что стоило бы проверить. В качестве примера: как соотносится параметр d для случайной 3-XOR со средней "шириной" ограничения? То есть, с модулем разности между максимальным и минимальным индексом переменных в ограничении. Но это и есть самое интересное - думать о том, о чём другие не смогли подумать.
Но конкретно задача о _случайной_ 3-XOR - это типичная задача из теории спиновых стёкол, в комбинаторных задачах всегда есть _конкретное_ значение связей. Ограничение взаимодействия по количеству ближайших соседей (вполне имеющее смысл в физике), как правило, сильно ограничивает класс решаемых комбинаторных задач. Причём очень сильно, вплоть до того, что он сводится к моделированию всё тех же спиновых стёкол. Так появляются смешные парадоксальные утверждения (Вы наверняка их видели): учёные построили квантовый компьютер и теперь, с его помощью, они могут моделировать квантовые системы (часто одну единственную систему - сам компьютер ;-).
Для каких-то оценок, может быть, усреднённые по случайным реализациям связи могли бы и пригодиться (особенно, если бы они были аналитическими), но могут и не пригодиться...
RRT это новое название для хорошо известного (в т.ч. и используемого при моделировании спиновых стёкол) метода Монте-Карло, который широко применяется и имеет известные ограничения. В частности, он плохо работает для сложных энергетических ландшафтов с множеством метастабильных состояний (и всегда, для любого d можно подобрать такой гамильтониан/задачу, что метод Монте-Карло глобального минимума не найдёт). Это особенно актуально для комбинаторных задач, многие из которых имеют _единственное_ решение.
Но вообще-то "спиновое стекло" - это не система, а состояние (термодинамическая фаза). Я понимаю, что когда говорят "гамильтониан спиновых стекол" - хотят сказать "гамильтониан некоторой системы, допускающий при определённых условиях существование спин-стекольной фазы". Обычно в этом качестве рассматривается изинговский гамильтониан с дефектами, но состояние спинового стекла может быть реализовано и в других системах. В том числе и системах _без_ дефектов и не обязательно в изинговских.
Вообще, пересечение с комбинаторикой тут простое и давно понятное. Современные рассуждения, мне кажется, только подпускают туману, фокусируясь на модных в недавнее время спиновых стёклах (модных совсем по другой причине, связанной с третьим законом термодинамики и теоремой Нернста). Модель Изинга для квантового спина 1/2 допускает 2 состояния со спинами +1/2 и -1/2 (обычно умножают на 2 и говорят о спинах 1 и -1). Если спинов N, то состояний такой системы 2N. Налицо экспоненциальный рост, как в NP-полных задачах. Вычисление статистической суммы такой системы требует суммирования по всем состояниям и на первый взгляд (а в некоторых случаях это вроде бы можно даже доказать) решается только полным их перебором, а значит принадлежит к классу NP полных. Именно поэтому я первым делом именно её (для изинговского гамильтониана с внешним полем и произвольно разорванными связями, т.е. с дефектами) и решал на своём " квантовом компьютере здесь и сейчас".
Но есть нюансы. Для изинговской системы из N спинов в присутствии внешнего поля аналитическое выражение для статистической суммы неизвестно. Но, если внешнего поля нет, то для той-же системы N спинов с теми же 2N состояниями Изинг в своей знаменитой работе 1925-го года такое выражение получил (собственно, именно поэтому модель и стала носить его имя).
К.Л.М.
Reply
Статья в моём посту интересна тем, что смотрит на задачи поиска решения логической выполнимости через их приближение (к 3-XOR разного рода) и предлагает некий параметр для характеризации этого приближения.
Конечно же, там упущено много интересного, что стоило бы проверить. В качестве примера: как соотносится параметр d для случайной 3-XOR со средней "шириной" ограничения? То есть, с модулем разности между максимальным и минимальным индексом переменных в ограничении. Но это и есть самое интересное - думать о том, о чём другие не смогли подумать.
Reply
Но конкретно задача о _случайной_ 3-XOR - это типичная задача из теории спиновых стёкол, в комбинаторных задачах всегда есть _конкретное_ значение связей. Ограничение взаимодействия по количеству ближайших соседей (вполне имеющее смысл в физике), как правило, сильно ограничивает класс решаемых комбинаторных задач. Причём очень сильно, вплоть до того, что он сводится к моделированию всё тех же спиновых стёкол. Так появляются смешные парадоксальные утверждения (Вы наверняка их видели): учёные построили квантовый компьютер и теперь, с его помощью, они могут моделировать квантовые системы (часто одну единственную систему - сам компьютер ;-).
Для каких-то оценок, может быть, усреднённые по случайным реализациям связи могли бы и пригодиться (особенно, если бы они были аналитическими), но могут и не пригодиться...
RRT это новое название для хорошо известного (в т.ч. и используемого при моделировании спиновых стёкол) метода Монте-Карло, который широко применяется и имеет известные ограничения. В частности, он плохо работает для сложных энергетических ландшафтов с множеством метастабильных состояний (и всегда, для любого d можно подобрать такой гамильтониан/задачу, что метод Монте-Карло глобального минимума не найдёт). Это особенно актуально для комбинаторных задач, многие из которых имеют _единственное_ решение.
К.Л.М.
Reply
Leave a comment