Что умеет квантовый компьютер D-Wave?

Машина DWave вызвала немало споров в сообществе, когда она была впервые анонсирована. Машина в основном пытается решить NP-полную задачу оптимизации (MAX-2SAT), кодируя ее как основное состояние гамильтониана, и пытается достичь этого основного состояния, адиабатически переходя к нему из основного состояния эффективно охлаждаемого гамильтониана.

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

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

Шум — это реальная проблема с устройством DWave, и, хотя они опубликовали ряд технических документов, в которых проблема преуменьшается и пытаются продемонстрировать квантовые эффекты, время когерентности для отдельных кубитов намного короче, чем временная шкала для алгоритма. Таким образом, в сообществе распространено мнение, что это, по сути, дорогой классический компьютер специального назначения.

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

Позвольте мне добавить, что адиабатическая модель может кодировать универсальные квантовые вычисления, однако ограничения реализации DWave означают, что конкретная машина не может.

В нем упоминается: Нахождение глобального минимума , где функция перехода от одного минимума к другому обрабатывается квантовым туннелированием.

У меня такое ощущение, что для того, чтобы просто получить представление о том, что он может сделать на практике, можно было бы взглянуть на упомянутый пример спиновых очков. Другими словами, физика спиновой связи близка к реальной аппаратной реализации.

http://en.wikipedia.org/wiki/Spin_glass .

Актуальной может быть работа Джорджио Паризи (да, одно из партонных уравнений эволюции Альтарелли-Паризи) и его сотрудников Мезарда и Вирасоро.

См. Текст медали Больцмана 1992 г.:

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

http://en.wikipedia.org/wiki/Giorgio_Parisi#Awards