Dr. K. L. Metlov (dr_klm) wrote,
Dr. K. L. Metlov
dr_klm

Categories:

Квантовые вычисления. Здесь и сейчас.

На прошлой неделе смотрел Q&A сессию Дональда Кнута на Google Tech Talks. Там он, в ответе на один из вопросов, с восторгом упомянул о zero-suppressed decision diagram(ZDD). Тогда я о них еще не знал. Разбираясь с ZDD, я, естественно, разобрался и с BDD (Binary Decision Diagrams) и понял восторг Кнута.

Более того, похоже мы с ним шли к BDD похожим путем. Когда-то давным-давно (больше 10-ти лет назад) я столкнулся с задачей, стоявшей перед одним из моих коллег. А именно, задачей расчета энергетического спектра модели Изинга в присутствии внешнего магнитного поля. Зная спектр, можно потом тривиально рассчитать статистическую сумму, а значит все равновесные термодинамические свойства этой системы. Расчет спектра модели Изинга -- комбинаторная задача, причем, относящаяся к классу NP-полных. Тогда (десять лет назад) мне удалось ее довольно эффективно решить и рассчитать спектры двумерных изинговских систем, содержащих до 100 спинов (а значит 2^100 различных состояний). Столкнувшись с подобной по сложности комбинаторной задачей о покрытиях, примерно в то же время, Дональд Кнут сформулировал свой алгоритм Х (идейно, очень близкий к тому, что я независимо делал для модели Изинга). После этого Кнут (как и я) открыл для себя BDD. И понял, что это есть некий общий метод, который давно уже существовал в инженерии (его автор Randal E. Bryant), обобщающий, в том числе, и алгоритм X (и мой алгоритм для решения модели Изинга). О своем восторге от этого открытия Кнут неоднократно рассказывал в видео лекциях, мой восторг был не меньше.

На выходных я написал программу, вычисляющую BDD для состояний модели Изинга (на печать там выводится только спектр, но вычисленные BDD позволяют вытащить гораздо больше информации о состояниях). На моем компьютере (8Gb RAM) программа справляется с решетками до 8x8=64 спинов (с 2^64 состояний). Это уже само по себе удивительно, если представить себе -- сколько это 2^64 ! Тем более, если учесть, что BDD (и конкретно библиотека BuDDy) не специализированы и позволяют решать широчайший класс комбинаторных задач (ну, если не "решить", то хотя-бы "поставить" ;-). Однако, мой "алгоритм X", десять лет назад, справлялся с решетками вплоть до 10x10=100 спинов (вот, например, спектр такой треугольной решетки, вычисленный тогда). Для BDD на моем компьютере 8x8 пока предел. Но если у кого завалялся комп с 16-ю гигами, ;-) могу предложить запустить эту мою программу (думаю, что там нужно будет в несколько раз увеличить кэш и немного увеличить размер массива для узлов BDD, наверное что-то вроде bdd_init(300000000,30000000); или больше, ну и, конечно, nx=9 и ny=9). Интересно, до какого размера получится реально дойти ? ;-) Как будет при этом масштабироваться затраченные на расчет время и память ? По времени всё не так плохо, решетка 8x8 на моем Core Quad 2.5Ghz считается часа 4.5.

При чем тут квантовые компьютеры, спросите Вы ? Назовите переменные в BDD q-битами и считайте, что они принимают _одновременно_ значения и "0", и "1". Библиотека BuDDy (и другие реализации BDD) позволяют определять булевские функции, содержащие как биты, так и некоторое количество q-бит. После того как такая функция (BDD) определена, относительно неё можно формулировать множество нетривиальных запросов (например: принимает ли она значение "1" для каких либо чистых значений q-bit, если да -- то для каких). И, хотя адиабатический квантовый компьютер фирмы D-Wave с 64-ю q-битами только в планах, все состояния решаемой им модели Изинга с 64-ю спинами можно полностью классифицировать на моем компьютере уже сегодня (ну, или 10 лет назад ;-).

В любом случае, если даже квантовые компьютеры будут сделаны, интерфейс для работы с ними, я считаю, должен быть именно таким (как в библиотеке BuDDy). Так что задачи можно ставить уже сейчас. Это просто.

update (28.05.2011): D-wave "продает" свой первый 128-qбитный квантовый компьютер. Это, конечно, чистый пиар-ход (не понятно, правда, зачем... может готовят акции к продаже). В любом случае, если у Вас есть задачи для квантового компьютера -- Вы знаете к кому обращаться. Сделаю за полцены ! ;-))
Tags: popul
Subscribe

  • интуитивно-понятный интерфейс

    Удивительно, но ребёнок в свои 8 с небольшим месяцев уже научился листать странички на тачскрине моего фитнес-браслета. Причём, вполне осмысленно.…

  • статья

    Наша с супругой статья по мемристорам вышла сегодня в октябрьском номере Royal Society Open Science. С учетом того, что препринт мы выложили ещё…

  • Дмитрий Муратов

    Не знаю кто такой Дмитрий Муратов, никогда не слышал о нём. Но, если ему дали Нобелевскую премию мира -- хорошим человеком он быть не может.

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments