Pull to refresh

Первый высокоуровневый язык программирования для квантовых компьютеров

Programming *Algorithms *Haskell *
Хотя квантовые компьютеры существуют пока только в теории, но это не мешает делать обоснованные предположения об их будущей архитектуре и, что более важно, об интерфейсе взаимодействия с ними. Таким образом, уже сейчас есть возможность проектировать программные симуляторы квантовых компьютеров — и писать софт.

Группа американских учёных, получив финансирование от исследовательского центра Национальной разведки США (IARPA) разработала высокоуровневый язык программирования Quipper. Он создан на основе Haskell и лучше подходит для реализации квантовых алгоритмов, чем QCL (основан на C).

На сегодняшний день известно как минимум 45 алгоритмов для квантовых компьютеров. Все они описаны в научных статьях, но ни один не был реализован в программном коде. С появлением Quipper появилась такая возможность. В дальнейшем программисты смогут просто использовать готовые библиотеки для квантовых компьютеров, как они это делают сейчас на высокоуровневых языках для классической архитектуры.

Разработчики Quipper призывают закодировать все известные алгоритмы на новом ЯП, сами они для проверки реализовали семь нетривиальных квантовых алгоритмов из литературы:

  • Бинарное спаянное дерево (Binary Welded Tree, BWT), arXiv:quant-ph/0209131. Поиск обозначенного узла в графе.
  • Булева формула (Boolean Formula, BF), arXiv:0704.3628 и arXiv:quant-ph/0703015, любая формула AND-OR размера N может быть вычислена за время n1/2+o(1) на квантовом компьютере. Реализована версия, которая вычисляет выигрышную стратегию в настольной игре гекс.
  • Порядок класса (Class Number, CL), Proceedings of the 34th ACM Symposium on Theory of Computing, 2002. Квантовый алгоритм для вычисления уравнения Пелля и главного идеала за полиномиальное время.
  • Оценка основного состояния квантово-механической системы (Ground State Estimation, GSE), Molecular Physics, 109(5):735–750, 2011. Вычисление энергетических уровней для конкретной молекулы.
  • Квантовые линейные системы (Quantum Linear Systems, QLS), arXiv:0811.3171. Решение линейной системы уравнений.
  • Кратчайший уникальный вектор (Unique Shortest Vector, USV), arXiv:cs/0304005. Поиск кратчайшего вектора среди имеющихся вариантов.
  • Поиск треугольника (Triangle Finding, TF), arXiv:quant-ph/0310134. Поиск треугольников в насыщенном графе.

Список алгоритмов определило агентство IARPA, в контексте программы IARPA Quantum Computer Science.

Как известно из истории, первые компьютеры приходилось программировать в машинных кодах, что было достаточно сложной и трудоёмкой задачей. Существенный прорыв случился благодаря разработке первого высокоуровневого языка программирования Фортран в 1957 гг. С этого момента взаимодействие человека и машины вышло на новый уровень, и мы смогли задавать компьютеру более сложные задачи.

Само по себе существование такого языка с высокоуровневыми абстракциями и реализованными на нём алгоритмами поможет в создании новых алгоритмов для квантовых компьютеров, считают авторы языка Quipper.


Компьютер D-Wave

Quipper подходит для программирования теоретических квантовых компьютеров нескольких архитектур (реализация кубитов в фотонах, электронах и т.д.), но не подходит для программирования действующего «квантового» компьютера D-Wave, который критики не считают полноценным квантовым компьютером из-за его узкой специализации. Что, впрочем, не помешало компании Google недавно купить два компьютера D-Wave с процессорами по 512 кубитов за $15 млн.

[New Scientist]
Tags:
Hubs:
Total votes 78: ↑69 and ↓9 +60
Views 77K
Comments Comments 45