Метка «квантовые вычисления»

Квантовый поиск при помощи алгоритма ГровераСегодня вслед за первыми квантовыми алгоритмами, которые мы уже рассмотрели (см. алгоритм Дойча и алгоритм Дойча-Йожи — если кто-то ещё не читал эти статьи, то предлагаю предварительно с ними ознакомиться, поскольку без этого изложение может показаться несколько туманным), предлагаю изучить алгоритм Гровера для неструктурируемого квантового поиска. Этот алгоритм был разработан американским математиком Ловом Гровером в 1996 году (уже намного позже того, как модель квантовых вычислений стала в моде). Этот алгоритм использует свойство квантовой интерференции для того, чтобы решать крайне насущную задачу по поиску значения некоторого параметра, на котором заданная функция выдаёт определённый результат.

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

Эта статья является продолжением в цикле статей по модели квантовых вычислений, поэтому если начать читать её без ознакомления с предыдущими статьями цикла, что-то может показаться непонятным. Так что читателя, который впервые набрёл на эти мои заметки, я отправляю к первым статьям: 1, 2, 3, 4.

Итак, если кто-то заинтересовался, то как обычно добро пожаловать под кат.

Читать полностью »

Квантовая схемотехника: некоторые приёмы и техникиСегодня в рамках работы над книгой «Квантовые вычисления и функциональное программирование» я хотел бы представить на суд почтеннейшей публики свою очередную статью про квантовые вычисления.

Квантовая схемотехника — это, по сути, методология анализа и, главное, синтеза квантовых схем, реализующих те или иные алгоритмы (в общем понимании, не только квантовые). Обобщённо любой вычислительный процесс представляется в виде тройки (вход, процесс преобразования, выход). Принимая во внимание это соображение, задачами квантовой схемотехники можно назвать:

  1. Прямой анализ. При наличии схемы входа и описания вычислительного процесса определить схему выхода.
  2. Обратный анализ. При наличии описания вычислительного процесса и схемы выхода определить схему входа.
  3. Синтез. При наличии схем входа и выхода построить описание вычислительного процесса.

К сожалению, в имеющейся литературе по квантовым вычислениям данные вопросы практически не находят своего отражения (от силы есть пара источников на русском языке, где кратко рассматриваются некоторые из них), а именно они являются краеугольным камнем прикладного программирования. Поэтому далее в этой статье я постараюсь в полной мере раскрыть все три аспекта квантовой схемотехники.

Читать полностью »

Проект по написанию книги «Квантовые вычисления и функциональное программирование»Идея книги про модель квантовых вычислений появилась у меня в голове уже давно. Сразу после прохождения курса по квантовой механике и квантовым вычислениям на Coursera (краткое описание см. здесь) у меня в голове родился вопрос: «Почему же это курс по квантовым вычислениям устроен так, что программисту он довольно непонятен, но, скорее, рассчитан на физика?». Сама модель квантовых вычислений меня поразила до глубины души, и после глубочайших раздумий я начал поглощать одну книгу за другой, одну статью за другой. В итоге после прочтения и изучения более 20 источников на русском языке я прихожу к неутешительному выводу — ещё не написана книга о модели квантовых вычислений, которая объясняла бы эту модель прикладному программисту. Ведь что получается? Большинство источников сегодня рассказывают про ядерные спины, ионные ловушки, нотацию Дирака и суперпозицию, объясняя всё это для физика. Но как прикладной программист очень часто не имеет никакого понятия по физических процессах, происходящих внутри обычного процессора, так и в данном случае разъяснение физических принципов реализации унитарных преобразований в виде особого вида гамильтонианов в уравнении Шрёдингера больше затуманивает суть вещей для разработчика программ, нежели раскрывает красоту и мощь этой новой модели.

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

Читать полностью »

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

Дальнейшее изложение будет проводиться с использованием многочисленных примеров на языке программирования Haskell. Дело в том, что по моему сугубому мнению, функциональное программирование находится намного ближе к модели квантовых вычислений, чем любой иной тип. Обосновывать эту точку зрения я сейчас не буду. Но суть в ином — для постижения модели квантовых вычислений нужен намного более суровый сдвиг парадигмы, чем, к примеру, такой сдвиг от структурного программирования к объектно-ориентированному и тем более к функциональному. Здесь нет ни слова о том, что кто-то из программистов находится выше или ниже, но лишь о том, что освоение новой модели — это реальный переворот в мозгах и способе алгоритмического мышления.

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

Читать полностью »

image

АНБ финансирует разработку квантового компьютера, позволившего бы ему взломать практически любое шифрование, используемое сегодня, пишет The Washington Post. Пока что однако нет никаких свидетельств того, что агентству удалось продвинуться дальше, чем другим исследователям, которые над этим работают.

Благодаря документу, переданному Эдвардом Сноуденом, стало известно об исследовательской программе «Внедрение в сложные цели» с бюджетом 79,7 млн долларов, одной из целей которой является создание квантового компьютера, который может быть использован для криптографии. Согласно документу, большая часть исследований ведётся в физической лаборатории Мэрилендского университета. Как далеко продвинулась работа, в документе не раскрывается.
Читать полностью »

Сказал как-то раз Евклид, что параллельные линии не пересекаются. И назвал он это пятым постулатом. Жалко, что не вторым.

В этой статье я бы хотел перейти от сферических котов Шредингера в резонаторах Гельмгольца к чему-то более практичному, тем более, что Хабр интересуют физические реализации и применение квантовых компьютеров.

Тут я решил рассказать про составные системы и описать алгоритм Дойча.

Читать полностью »

Хей, Амиго!
Я уже очень давно читаю Хабрахабр и встретил очень мало статей, посвященных квантовым компьютерам. И ни одной про квантовые вычисления.

«Надо это дело исправить», подумал я. Тем более, что эта тема довольно интересна.
Читать полностью »