Полезен ли квантовый отжиг?

Я читал о квантовом отжиге, особенно о том, как его делают такие компании, как D-wave. Я думаю, что понимаю, как это работает и как оно использует туннелирование, чтобы найти глобальный оптимум в данном энергетическом потенциале.

Но слон в комнате: какая от этого польза? Какой смысл искать оптимум в потенциале, который вы сами создали? Если бы потенциал был черным ящиком, то я мог бы найти какое-то применение. Но очевидно, что потенциал подготавливается контролируемым образом, так что кажется, что это противоречит цели.

Пожалуйста, проясните мое замешательство.

Вы спрашиваете, почему полезно найти минимум функции, которую вы создали сами? Предположим, вы пытаетесь понять, как построить дом с минимальной суммой денег. Вы можете написать функцию для необходимой суммы денег, где строительные материалы являются входными данными. Это функция, которую вы создали, но вы, очевидно, хотели бы минимизировать ее.

Ответы (2)

Вы думаете, что «потенциал» принимает вид совершенно произвольной, неструктурированной функции всей конфигурации поля. Поиск минимума такой функции является примером того, что в теоретической информатике называется «неструктурированным поиском». Действительно, квантовый отжиг не дает большого ускорения для неструктурированного поиска; было доказано, что алгоритм Гровера дает наилучшее возможное квантовое ускорение для неструктурированного поиска, которое представляет собой «всего лишь» квадратный корень, а не экспоненциальное ускорение.

(На самом деле это не совсем правильно. Найти минимум совершенно произвольной неструктурированной функции еще сложнее, чем обычная формулировка проблемы принятия решения неструктурированного поиска, потому что она лежит даже за пределами эквивалента поиска класса сложности NP. Это потому, что даже если бы квантовый компьютер дал вам ответ, единственный возможный способ проверить его было бы эффективно повторить весь поиск снова.Так что в реальном мире такой квантовый компьютер может быть не очень полезен, потому что не будет практический способ проверить, был ли его ответ правильным или в компьютере была ошибка.Кроме того, если пространство поиска было экспоненциально большим, то даже загрузка условия задачи вкомпьютер может занять больше времени, чем возраст Вселенной, не говоря уже о том, чтобы компьютер решал эту задачу.)

Но это не тот потенциал, который создается при квантовом отжиге. Потенциал не произвольный, а строго структурированный. Прототипом проблемы, которую атакует QA, является проблема спинового стекла Изинга . Детали не важны, но дело в том, что только экспоненциально малая часть всех возможных потенциалов может быть сформулирована как спиновое стекло Изинга. (Конкретно, задание гамильтониана изинговского спинового стекла на системе Н спины требует только указания ( Н  выбирать  2 ) "=" ( 1 / 2 ) Н ( Н − 1 ) ∼ Н 2 разными параметрами, а для совершенно произвольного гамильтониана требуется 2 Н параметры для указания.) Поскольку вы указали ∼ Н 2 различные связи, но не явные ∼ 2 Н различных возможных энергий, вы на самом деле не «имеете точное представление» о потенциале, хотя формально вы точно знаете его.

В качестве аналогии рассмотрим задачу коммивояжера: если бы я просто перечислил кучу поездок с указанием их продолжительности и попросил бы вас найти самую короткую, то эта (неструктурированный поиск) не была бы очень интересной задачей с математической точки зрения. Ясно, что единственное возможное решение — пройти каждую поездку одну за другой и оставить самую короткую из найденных. Неудивительно, что квантовые компьютеры ( любого типа, а не только отжиг) не могут значительно ускорить решение такой бесструктурной задачи. Но если бы я вместо этого дал вам список расстояний между городами и попросил вас найти кратчайший маршрут, соединяющий их все (обычная постановка задачи), то (а) информацию нужно просто констатироватьзадача (структурированного поиска) может быть экспоненциально сжата, (б) есть гораздо больше математических инструментов, которые мы можем использовать для ее решения, и (в) квантовые компьютеры могут быть намного эффективнее классических компьютеров при поиске кратчайшего пути. (Я говорю «может», потому что, в отличие от проблемы спинового стекла Изинга, практически никто в теоретическом сообществе CS не думает, что квантовые компьютеры смогут эффективно решить проблему коммивояжера.)

Спасибо за подробный ответ, но я боюсь, что это все еще не касается моего вопроса. Я не делаю никаких предположений относительно того, является ли потенциальная функция произвольной или структурированной. Кроме того, что мы вообще подразумеваем под «структурированным»? О каком показателе мы говорим? Энтропия? Квантовая чистота? Я до сих пор не понимаю, какое это имеет значение. «Компьютер» D-волны подготавливает потенциал (структурированный или нет) контролируемым образом. Он «знает» точно, как распределять интенсивности и тем самым расположение всех оптимумов. Вы видите, что я имею в виду?
@Tfovid Они не готовят потенциал напрямую. Они непосредственно подготавливают связи в гамильтониане. Это однозначно определяет потенциал, но только за счет невероятно сложных вычислений, которые невозможно выполнить на практике. Поэтому они не всегда знают местонахождение оптимумов.
@Tfovid Вам нужно концептуально различать длину- Н 2 список гамильтоновых связей, который дает вам формулу для расчета потенциала, и сам потенциал, рассматриваемый как список 2 Н разные энергии. Они математически изоморфны, потому что, зная одно, вы в принципе можете найти другое с достаточным вычислительным временем. Но на практике они совершенно разные, потому что время на преобразование непрактично велико. Программисты D-Wave знают только первое. Наличие списка связей не позволяет на практике узнать значения ее минимумов.
@Tfovid Возможно, нам следует вернуться и прояснить более простой вопрос. Вы понимаете общую концепцию, что может быть трудно найти минимум известной функции? (Я не пытаюсь язвить, это честный вопрос.) Если да, то ответ на ваш вопрос кажется ясным.
Я понимаю сложность поиска минимума известной функции. Тот факт, что у меня есть четко определенное, замкнутое выражение некоторой функции, не означает, что я могу легко считать ее глобальный минимум. Тем не менее, если я закодирую эту функцию в физической системе, я буду знать ее значение в каждой точке. Например, я знаю потенциал каждого атома в моей решетке, так как я подготовил их сам. Ключевой момент, который я пытаюсь донести, заключается в том, что у меня есть полный контроль над каждым атомом в моей системе. Я подготовил это. Я знаю, где все оптимумы для начала.
@Tfovid Я совершенно не понимаю, почему вы думаете, что «имея полный контроль над» функцией и «подготовив ее» самостоятельно, вам будет легче «узнать, с чего начать все оптимумы», чем в случае общего известная функция (которую, по определению, вы также «знаете значение в каждой точке», но которую, как вы утверждаете, вы каким-то образом «не имеете полного контроля»). В конце концов, вы не можете построить произвольный потенциал при квантовом отжиге, а только чрезвычайно сильно ограниченный потенциал. Возможно, нам следует сдаться и подождать, пока кто-то другой не взвесит свое мнение, кто лучше понимает ваше замешательство.
@Tfovid Вы понимаете, что этот «потенциал» не является функцией В ( Икс → ) в позиционном пространстве? Потенциал присваивает энергию каждой возможной конфигурации спина. В ( с 1 , с 2 , … , с 1024 ) . Хотя легко вычислить В ( … ) для данной конфигурации спина на самом деле трудно узнать, где находятся оптимумы, даже если вы знаете функцию В очень хорошо. Вы говорите, что "знаете, где оптимумы для начала" - пожалуйста, подготовьте такую ​​​​функцию В и покажи где они ;)
@Noiralef Я думаю, что мы приближаемся: я действительно думал о потенциале как о функции над некоторым типом позиционного пространства. На моей (упрощенной) картинке это выглядело как двумерная решетка спинов, каждый из которых приготовлен при определенном потенциале. Это неправильно?
Я имел в виду эту картину , где явно спины приготовлены в заданном пространственном расположении. Если вы сделаете левый нижний угол за начало координат, то я подготовлю вращение там вниз, а затем подготовлю вращение в позиции (0, 1) вверх и т. д.
@Tfovid Да, это очень неправильно. Я не знаю, что значит иметь индивидуальное вращение «в потенциале». Вы просто имеете в виду, что каждый спин испытывает различное магнитное поле в г -направление? В этом случае основное состояние — это просто каждый спин, направленный вдоль его локального поля, и нечего преуменьшать.
@Tfovid Причина, по которой спин-стекло Изинга нетривиально решить, заключается в том, что вращения на разных сайтах связаны вместе , поэтому вы не можете просто думать о системе по одному вращению за раз.
@Tfovid При квантовом отжиге вы вообще не готовите начальное состояние спинов - вы готовите гамильтониан.

Задача нахождения основного состояния спинового стекла Изинга (задача, которую якобы решает D-Wave) является NP-полной , поэтому, если мы сможем ее решить, то сможем эффективно адаптировать наше решение для решения любой задачи класса сложности NP. - что составляет огромный массив полезных задач. См . здесь конкретные алгоритмы преобразования решения спинового стекла Изинга в решения более полезных задач.

Я это понимаю, но это все равно не объясняет, зачем нам нужно оптимизировать функцию (т. е. потенциал), которую мы сами подготовили контролируемым образом . Если я собираюсь нарисовать x ^ 2 как свой потенциал, то, по-видимому, я уже знаю, что он будет наименьшим при x = 0, и это противоречит цели его минимизации.
@Tfovid Если функция проста, как Икс 2 , то обязательно. Но, как сказал DanielSank, для более сложных функций минимум может быть далеко не очевиден, даже если мы точно знаем функцию. Проблемы оптимизации могут быть чрезвычайно сложными. Учтите, что в задаче о коммивояжере, каноническом примере «сложной» вычислительной задачи, функция стоимости точно известна.
Я не понимаю, как сложность функции имеет какое-либо отношение к этому. Если вы собираетесь контролируемо создавать потенциальную функцию (через системы спинов или что-то еще), то вы должны четко знать, где должен лежать каждый потенциал, включая самый низкий/самый высокий. Если вы этого не сделаете, то вы не хозяин своей собственной потенциальной функции, и тогда мы говорим о чем-то другом.
@Tfovid Да, вы действительно «точно знаете, где [лежит] каждый потенциал, включая самый низкий / самый высокий». Но вы не знаете, какой из них самый низкий/самый высокий. Область определения потенциальной функции настолько велика, что простая проверка каждого значения по одному может занять больше времени, чем возраст Вселенной. Трудность нахождения минимального значения известной функции не имеет ничего общего с тем, насколько «контролируемо» эта функция была реализована экспериментально.
Боюсь, мы здесь "говорим мимо друг друга". «Грандиозность» или сложность потенциальной функции не имеют отношения к проблеме. Вы сами создали потенциальную функцию; вы сами настроили каждое вращение/атом/что угодно, чтобы создать его, и поэтому вы знаете его ценность в первую очередь в каждой точке. Какой тогда смысл искать его апостериори с помощью туннелирования или любого другого метода. Как я упоминал в своем исходном посте, если бы потенциал был черным ящиком, то отжиг для оптимизации имел бы смысл. Но это не то, что я понял из того, что делает D-wave.
@Tfovid Ах, кажется, теперь я понимаю твое замешательство. Я создам отдельный ответ.
Полезен ли квантовый отжиг?
СпросиСетьПолитика конфиденциальности1y, 0v