?

Log in

No account? Create an account

eslitak

Previous Entry Поделиться Next Entry
11:51 pm: Квантовый ликбез 23. Квантовый параллелизм.
Предыдущие посты

Тут следует немного поговорить о том, для чего вообще нужен квантовый компьютер.

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

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

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

А задачи второго типа распределять между несколькими компьютерами очень даже полезно. Скажем, в задаче по факторизации: возьмём сотню компьютеров, разобьём область поиска возможных делителей на сотню кусков и "заставим" первый компьютер искать делители в первом куске, второй - во втором, и так далее. Таким образом, используя сотню параллельно работающих машин, среднее время поиска решения можно сократить в ту же сотню раз.

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

В предыдущей части был рассмотрен принцип действия классического компьютера. Мы выбрали для рассмотрения теоретическую модель компьютера на базе битового регистра. Вкратце напомню, как это работает.

C1. Сначала записываем в битовый регистр исходные данные, то есть, устанавливаем каждый бит в определённое состояние «0» или «1».

C2. Запускаем компьютер, и он «обрабатывает» биты - изменяет их состояние в соответствие с программой, задающей последовательность операций. Программа может быть сколь угодно разветвлённой, длинной и сложной, но при этом она строится из ограниченного (базисного) набора элементарных операций. Аналогично тому как из множества одинаковых кирпичей можно построить здание любой формы. По окончании работы программы в битовом регистре образуется результат вычисления.

C3. Читаем результат из регистра.

Буква «C» в номере пункта означает, что речь здесь идёт о классическом (Classical) компьютере.

Так вот, квантовый компьютер устроен похоже, только в нём используются не простые биты, а квантовые. И от этого по кажному пункту возникает своя квантовая специфика. Давайте её рассмотрим. Буква «Q» в номере пункта - говорим о квантовом (Quantum) компьютере. Для начала "потренируемся" на одном кубите.

Q1. Для обычного бита существует только два варианта состояния: «0» или «1», причём, бит может находиться только в одном из них. А квантовое состояние кубита, как мы уже знаем, в общем случае представляет собой совокупность двух бесконечных групп реализуемых виртуальных вариантов. Варианты одной группы несут в себе классическое состояние «0», варианты второй группы - классическое состояние «1». Упрощая картину можно сказать, что кубит несёт в себе две альтернативы одновременно. Стало быть, если в бит мы можем «записать» либо «0», либо «1», то в кубит можно «записать» комбинацию двух значений сразу.

Q2. Смотрим на пункт C2: операция над битом «работает» только с одной версией исходных данных, и результат, стало быть, тоже получается только один. Скажем, если в бит был записан «0», и мы применили к нему операцию «NOT», то в результате получим единицу.

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




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



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

Q3. А вот с чтением результата из кубита всё несколько сложнее. По окончании расчёта в регистре хранится комбинация результатов, да. Но прочитать мы можем только один из них, причём, выбор тут абсолютно случайный. Ведь что такое считывание из памяти с точки зрения физики? Это, по сути, измерение состояния ячейки памяти. А квантовое измерение всегда даёт только одни результат из множества реализуемых альтернатив, в случае одного кубита - один из двух.

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

С многокубитными квантовыми системами мы уже знакомились в части 20, кто забыл, пожалуйста, вернитесь туда и освежите в памяти. Количество альтернатив (результатов измерений) для многокубитной системы равняется 2n, где n - количество кубитов. В контексте квантовых вычислений каждую альтернативу мы рассматриваем как один экземпляр исходных данных. Значит, если мы оперируем с одним кубитом, мы обрабатываем одновременно два варианта, в одном из которых «на входе» число «0», в другом - число «1». Если мы имеем дело с двухкубитным регистром, то обработке подвергаются уже суперпозиция из четырёх чисел сразу. Трёхкубитный регистр – восемь чисел, и так далее. Если же взять, например, регистр размером в 32 кубита, тогда одна вычислительная схема сможет обрабатывать сразу 4294967296 (четыре с лишним миллиарда!!!) вариантов входных данных. Например, если мы решаем задачу факторизации, то одна квантовая схема потенциально способна за один проход отыскать делитель среди более чем четырёх миллиардов чисел.

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


Продолжение


Tags: ,

Comments

[User Picture]
From:yoginka
Date:Июнь 25, 2014 04:55 pm
(Link)
Ждем продолжения. Это должно быть самым интересным.
[User Picture]
From:eslitak
Date:Июнь 25, 2014 07:19 pm
(Link)
Продолжение на подходе.

Хотелось бы узнать: до этого места понятно изложено?
[User Picture]
From:yoginka
Date:Июнь 26, 2014 05:00 am
(Link)
Понятно. Но я - не показатель, я давно в этой теме копаюсь.
From:invalid1gr
Date:Июль 25, 2017 09:06 am
(Link)
Добавлю к трем имеющимся комментариям, что нашел Вашу статью на заслуженном третьем месте в выдаче гугла по запросу "Квантовый параллелизм". Здесь все отлично разжевано. Отложил в закладки прочитать весь цикл.
[User Picture]
From:eslitak
Date:Июль 31, 2017 08:45 am
(Link)
Спасибо, жду отзыв на "весь цикл" :)
Разработано LiveJournal.com