Читать «Журнал «Компьютерра» № 9 от 06 марта 2007 года» онлайн - страница 55

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

Несколько лет назад появилась идея адиабатического КК (АКК). Исходные данные задачи кодируются исходным состоянием набора кубитов — тем, которое имеет наименьшую возможную энергию. Потом систему начинают медленно менять. И это состояние минимальной энергии («основное состояние») тоже медленно меняется, но все время остается (по идее) состоянием с минимальной возможной энергией. И в конце концов процесс выруливает к такой конфигурации этого основного состояния, которая и кодирует ответ. Именно эту архитектуру выбрала для своего КК D-Wave.

О достоинствах и подводных камнях АКК во врезке рассказывает Артур Экерт. «Элементная база», на которой работает Orion — решетка размером 4х4 из сверхпроводящих элементов, колец из алюминия и ниобия. "Состояние кубита здесь зависит от наличия или отсутствия магнитного потока через кольцо. Этот поток для таких колец тоже квантуется. Как организовать взаимодействие кубитов? Детали, возможно, известны специалистам по сверхпроводимости; в препринте, на который ссылаются разработчики, речь идет об индуктивной связи через контур", — пояснил нам Юрий Ожигов.

Именно непроясненность принципиальных деталей и разочаровала академическое сообщество, следящее за проектом.

Жить NP-полной жизнью нелегко

•

В пресс-релизах D-Wave говорится о решении NP-полных задач, таких как составление расписаний авиаперелетов и головоломки судоку. Однако уже давно стало ясно, что с помощью КК скорее всего не удастся эффективно решать такие проблемы. Известно, как с помощью КК экспоненциально ускорить решение некоторых «структурированных» задач — например, факторизации целых чисел. Для NP-полных задач известно лишь, как добиться квадратичного ускорения по сравнению с прямым перебором вариантов. Это фундаментальный момент, который почти никто из писавших о D-Wave в популярной прессе не отметил.

• На вопрос об этом D-Wave отвечает: «все верно, но нас интересуют не точные, а приближенные решения, и не любых NP-полных задач, а только важных для практики». Однако и для таких задач ничто не указывает на возможность радикального ускорения при помощи КК. Для многих NP-полных задач получить приближенный ответ так же трудно, как точный. Более того, неизвестно, будет ли «адиабатический квантовый алгоритм», который D-Wave предлагает использовать, работать на практических задачах лучше, чем классический алгоритм — например, метод имитации отжига (simulated annealing).