Квантовый параллелизм – отжиг с выключателями и прочее веселье / Сбербанк corporate blog / Habr

отжиг с выключателями и прочее веселье / Сбербанк corporate blog / Habr

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

Квантовый параллелизм

Согласно законам квантовой механики, частица может находиться во всех своих состояниях одновременно. Это состояние кубита называется суперпозиция. В суперпозиции амплитуды базисных состояний принимают ненулевые значения – a|0⟩ + b|1⟩ и при этом сохраняется требование нормировки.

Квантовая частица может находиться в суперпозиции только до момента измерения. После измерения она коллапсирует в одно из своих базисных состояний – 0 или 1. Если мы имеем регистр кубитов, которые находятся в суперпозиции, то состояние самого регистра можно определить следующим образом:

(a₀|0⟩ + b₀|1⟩)(a₁|0⟩ + b₁|1⟩)…(a_n|0⟩ + b_n|1⟩) =
a₀×a₁×…×a_n|00..0⟩ + a₀×a₁×…×b_n|00…1⟩ +…+ b₀×b₁×…×b_n|11…1⟩

Важно понимать, что множители, которые стоят перед состояниями, – это не вероятность. Иначе мы бы получили классическую систему с ограничением – неизвестно, в каком именно состоянии она находится. А квантовый бит находится в обоих состояниях одновременно. Мы имеем возможность обработки сразу всех 2

n возможных комбинаций!

Для того чтобы перевести кубит в состояние суперпозиции, нужно применить к нему специальное преобразование – гейт Адамара. Еще одно применение гейта Адамара вернет кубит в одно из базисных состояний. Так выглядит матрица гейта Адамара и пример его применения:

H×|0⟩ = H×(1|0⟩ + 0|1⟩) = 1/sqr(2)|0⟩ + 1/sqr(2)|1⟩
H×(1/sqr(2)|0⟩ + 1/sqr(2)|1⟩) = 1|0⟩ + 0|1⟩ = |0⟩

Интересно действие двухкубитного гейта CNOT при контролирующем кубите в суперпозиции – CNOT запутывает кубиты. Запутанное состояние – это явление, при котором кубиты нельзя рассматривать по отдельности, так как их состояние теперь общее.

Приведем пример. Допустим, у нас есть регистр из двух кубитов в начальном состоянии — в базисном состоянии |0⟩). Применим гейт Адамара к первому кубиту – получим следующее состояние регистра:

H×I×|00⟩= H×(1|0⟩ + 0|1⟩) × I×(1|0⟩ + 0|1⟩) = (1/sqr(2)|0⟩ + 1/sqr(2)|1⟩) × (1|0⟩ + 0|1⟩) =
1/sqr(2)|00⟩ + 1/sqr(2)|10⟩

Первый и второй кубиты в этом регистре независимы друг от друга. Второй кубит до сих пор в состоянии |0⟩ и если мы его измерим, то все равно не получим информации о состоянии первого – тот может быть как в состоянии 0, так и в состоянии 1. Применим двухкубитный гейт CNOT:

CNot × (1/sqr(2)|00⟩ + 1/sqr(2)|10⟩) = CNot × (1/sqr(2)|00⟩ + 0|01⟩ + 1/sqr(2)|10⟩ + 0|11⟩) =
1/sqr(2)|00⟩ + 0|01⟩ + 0|10⟩ + 1/sqr(2)|11⟩ = 1/sqr(2)|00⟩ + 1/sqr(2)|11⟩

Теперь кубиты находятся в запутанном состоянии, и измерение любого из них заставит немедленно коллапсировать другой! Состояние регистра показывает, что оба кубита находятся в одинаковом состоянии — 0 или 1. Так что измерив один, мы точно узнаем состояние другого.

После того, как мы запутали кубиты, нельзя просто так свернуть один из них в базисное состояние – их нужно сначала распутать. Попробуйте самостоятельно создать данную схему на квантовом редакторе IBM и оцените результат:

Коллапс и количество получаемой информации

Производя вычисления над квантовым регистром из n кубитов, мы имеем возможность одновременно обрабатывать все 2ⁿ возможных состояния. Однако при измерении каждый кубит коллапсирует в одно из своих базисных состояний, а значит — после измерения результата у нас нет возможности получить больше информации, чем в классическом случае – мы получим только одно из возможных состояний с соответствующей вероятностью.

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

Алгоритм Гровера

Алгоритм, представляющий множество таких преобразований, называется алгоритмом Гровера. Он позволяет квадратично ускорить поиск в неструктурированной БД. Обычно сложность поиска в неструктурированном наборе данных равна O(n), то есть в худшем случае нам необходимо просмотреть все записи. Квантовый алгоритм позволяет решить эту задачу за  O(√n).

Например, у нас есть 40 бит и нам нужно найти одну из всех возможных комбинаций, удовлетворяющую некоторому условию. В классическом случае нам понадобится обработать порядка 1 000 000 000 000 разных комбинаций. Квантовый алгоритм позволит получить результат за 1 000 000.

Рассмотрим пример. У нас имеется регистр из n кубитов, находящихся в суперпозиции. Таким образом, у нас есть 2

n всех возможных состояний, и амплитуда каждого равна 1/√2ⁿ (именно при таком значении сумма квадратов модулей будет равна 1). Изобразим это в виде диаграммы:

Также у нас есть один дополнительный кубит, который мы будем называть функциональным, и функция-оракул. Оракул переводит функциональный кубит из базисного состояния |0⟩ в состояние |1⟩ ровно на том наборе, который мы ищем.

Чтобы при измерении получить именно то состояние, которое соответствует функции-оракулу, мы проделываем следующие действия:

• Изменяем знак амплитуды искомого значения на отрицательный. Для этого переводим функциональный кубит в состояние |1⟩ на всех наборах, далее применяем к нему гейт Адамара и затем функцию-оракул ко всему регистру. После этого действия картина будет выглядеть так:
  

Пунктирной линией на рисунках отмечено среднее значение амплитуды. После того, как знак у целевой амплитуды изменился, значение среднего опустилось ниже.

• Так как мы обрабатываем все состояния одинаково, то не можем изменить какую-то одну амплитуду. Но можем сделать инверсию относительно среднего – отобразить значение амплитуды, взяв за ось значение среднего:
  

• Как мы видим, значение искомой амплитуды выросло относительно остальных. По итогам выполнения этого набор действий порядка Pi×0,25×√2ⁿ раз, искомая амплитуда будет почти равна единице.
  

Представим, например, что нам нужно найти число в диапазоне от 0 до 7, которое после циклического битового сдвига влево даст число, меньшее 2. На классическом вычислителе данный класс задач решается только перебором. Нам необходимо было бы вычислить нашу функцию (битовый сдвиг) на всех аргументах и затем к каждому результату применять условие. Квантовый алгоритм позволяет сделать это моментально.

Квантовая оптимизация

Все рассмотренные ранее алгоритмы и приемы справедливы для так называемого универсального квантового компьютера – вычислителя, способного производить элементарные преобразования и фактически решать любую задачу (в простейшем случае моделируя классический алгоритм).

Но существует целый пласт математических задач, в которых как таковые вычисления не требуются, а необходимо найти такую комбинацию аргументов, на которой определённого вида функция примет минимальное значение. Этот класс задач – задачи оптимизации — подробнее будет разобран далее.

Квантовый отжиг

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

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

Рассмотрим математическую задачу, известную под названием «игра с выключателями света». Ее цель — нахождение лучших конфигураций включения и выключения для множества переключателей. Вот как это выглядит графически:

Представим, что у каждого переключателя есть вес, который мы не можем изменить. Мы можем включать (ON) или выключать (OFF) каждый переключатель. ON обозначает умножение на 1, а OFF — на -1. Затем мы складываем все веса переключателей, умноженные на их значения ON / OFF. Цель игры — установить переключатели для получения самого низкого значения суммы. Вес i-го выключателя обозначим через h_i, а состояние переключателя через s_i

.
В зависимости от того, какие переключатели установлены на ON или  OFF, мы получим разные итоговые суммы. Найти минимальную сумму будет легко, потому что есть простое правило для гарантированного минимума:
Если мы установим все переключатели с положительными показателями в положение OFF, а все переключатели с отрицательными показателями — в положение ON, то в сумме получим самое низкое общее значение.

Теперь усложним задачу: добавим новый вес J. Он будет изменяться в соответствии с состояниями ON/OFF соседних переключателей. А затем включен в итоговую сумму, которую мы получили ранее.

Теперь гораздо сложнее решить, должен ли выключатель быть включен или выключен, потому что его соседи влияют на него. Даже в простом примере с двумя переключателями мы не можем просто устанавливать параметр ON/OFF в положение, противоположное знаку собственного веса переключателей. Со сложной сетью выключателей задача становится практически нерешаемой.
С помощью нескольких переключателей мы можем просто попробовать каждую комбинацию ON и OFF, есть только четыре возможности: [ON ON], [ON OFF], [OFF ON] или [OFF OFF]. Но по мере того, как мы добавляем все больше и больше переключателей, количество возможных способов установки переключателей растет экспоненциально:
Как поможет квантовая механика? Мы начинаем с системы в ее квантовой суперпозиции, затем привлекаем квантовый компьютер (DWave), который, используя квантовую оптимизацию, находит для выключателей то состояние, в котором значение суммы будет самым низким.

«Задача инкассатора»

Давайте сформулируем тестовую задачу и попробуем ее решить с помощью квантового компьютера DWave. Задача звучит так – у банка есть служба инкассации и множество банкоматов в городе, откуда нужно забрать деньги. Чем короче маршрут, тем меньше шансов попасть в неприятную ситуацию. Соответственно нам необходимо найти оптимальный маршрут во взвешенном направленном графе с N вершинами. Эта задача больше известна под именем «Задача коммивояжера» и не имеет лучшего варианта решения, чем полный перебор.

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

       c
       c  This is a sample .qubo file
       c  with 4 nodes and 6 couplers
       c
       p  qubo  0  4  4  6
       c —        0  0   3.4
       1  1   4.5
       2  2   2.1
       3  3   -2.4
       c —        0  1   2.2
       0  2   3.4
       1  2   4.5
       0  3   -2
       0  2   3.4
       1  2   4.5
       0  3   -2
       1  3   4.5678
       2  3   -3.22

Через «с» обозначены строки с комментариями, далее мы задаем параметры программы в строке, начинающейся с символа «p». В этой строке мы задаем топологию (пока всегда 0), количество кубитов (в терминах игры со светом это «выключатели») и связей между парами (весы «J»). Далее идет блок с описанием весов каждого кубита. В этом блоке первые два числа должны быть одинаковыми, и они соответствуют номеру кубита. Следующий блок – блок весов связей между парами. Номер первого кубита должен быть всегда меньше второго.

Итак, разобравшись с форматом, приступим к решению нашей задачи.

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

Предположим, у нас всего 4 вершины, на каждом шаге мы можем находиться в одной из 4 вершин, соответственно весь набор кубитов разбивается на блоки по 4 кубита. В нашем случае из 4 вершин, нам нужен будет регистр из 16 кубитов, пронумеруем их – a₀…a₁₆. Соответственно, в первом блоке будут кубиты с номерами a₀..a₃ – они соответствуют нахождению в одной из вершин на первом шаге.

Теперь надо расставить веса кубитов и их связей внутри одного блока таким образом, чтобы только один кубит в каждом блоке в конечном решении оказался в состоянии 1, а остальные в 0.  Это связано с тем, что в конечном итоге мы можем находиться только в одной из вершин на каждом шаге. Сделать это довольно просто – мы выставим вес каждого кубита в -1, а связи между ними в 2. Действительно, если мы посмотрим на формулу Σh_is_i + ΣJ_ijs_is_j , то увидим, что минимальна она будет, если второе слагаемое будет равно нулю. А это произойдет только в двух случаях – если все кубиты равны 0 или если один любой находится в 1, а остальные в 0. Но при этом первое слагаемое даст минимум во втором случае.

Итак, мы выставляем таким образом веса на всех шагах (блоках из вершин) нашего пути. Теперь, если мы пошлем нашу программу на исполнение, нам придёт ответ вида (0001 0100 1000 1000). Для удобства мы разделили их на блоки по 4 кубита пробелами. Мы видим, что в каждом блоке только одна единичка, и ее номер в блоке соответствует номеру вершины. В нашем решении есть блоки с одинаковым номером вершины – 1000. Нам нужно исключить такие варианты решения, т.к. мы не можем возвращаться в уже пройденные вершины. Для того, чтобы сделать это, мы будем рассматривать новые блоки – объединяющие одну и ту же вершину на разных шагах.

Рассмотрим блок a₀,a₄,a₈,a₁₂. Эти кубиты соответствуют нахождению в первой вершине на соответствующем шаге. Аналогично предыдущему пункту, только один из них должен быть равен единице – тогда мы окажемся в первой вершине только один раз за весь путь. Расставляем веса связей для всех таких блоков и отправляем программу на исполнение. Получаем ответ вида (0001 0100 1000 0001 0010). Отлично, мы уже получили путь, соответствующий определению, теперь нужно найти оптимальный путь согласно весам ребер графа. Для этого мы берем значения из матрицы смежности графа и переносим эти значения в нашу конфигурацию. После этого получаем результат.

Решение до парсинга

Решение после парсинга

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

Мы провели пробный запуск на 14 вершинах на конкретном графе. Алгоритм перебора нашел кратчайший путь длиной 91, время работы заняло примерно 10 мин. Метод Литтла отработал почти мгновенно и дал результат 104. Квантовый алгоритм отработал тоже почти мгновенно и дал результат 97. При этом если программу на квантовом компьютере строить с учетом физических связей, то мы получим результат, аналогичный перебору.

Максимальный граф, который на данный момент мы можем обработать с помощью квантового вычислителя, содержит 44 вершины. На классическом вычислителе в общем случае это займет несоизмеримо большее количество времени, т.к. сложность растет по формуле n!..

Квантовый компьютер, построенный на принципах отжига, имеет большую мощность, чем существующие универсальные компьютеры, но при этом ограничен классом решаемых задач. У нас нет возможности задать первоначальные состояния кубитов или производить над ними какие-то унитарные преобразования – у нас есть только одна возможность – найти комбинацию, при которой значение функции Σh_is_i + ΣJ_ijs_is_j при заданной конфигурации окажется минимальным. Однако даже с учетом этого ограничения квантовые компьютеры показывают существенный прирост производительности и могут быть эффективно использованы в задачах оптимизации.

Квантовые компьютеры сегодня

На данный момент существуют следующие основные направления реализации квантовых компьютеров:

• На ионах в одномерном ионном кристалле в ловушке Пауля.
  
• В полупроводниковых кристаллах бесспинового моноизотопного кристалла кремния
  
• Кубиты на электронах в полупроводниковых квантовых точках.
  
• Кубиты на сверхпроводниковых мезоструктурах.
  
• На одиночных атомах в микрорезонаторах.
  
• С помощью линейных оптических элементов (оптический квантовый компьютер).
  

Наиболее проработанными на сегодняшний день являются квантовые компьютеры DWave и IBM Q

DWave имеет статус «аналогового квантового компьютера», так как способен решать лишь узкий круг задач квантового отжига. Но при этом его заявленная мощность составляет 2 000 кубитов.

IBM Q – это программа по разработке универсальных квантовых компьютеров, на которых можно исполнять произвольные квантовые алгоритмы. В данный момент работают системы из 20 кубитов (коммерческое использование), и открытые системы Q Experience на 16 и 5 кубитов. Q Experience cейчас, пожалуй, единственная открытая платформа, позволяющая разрабатывать квантовые алгоритмы. Она представляет собой набор атомарных гейтов, которые можно применять к кубитам.

Использование квантовых вычислений

Помимо описанных ранее сценариев, квантовые вычисления могут отлично работать в других сферах.

Квантовая криптография. Защита информации основана на том, что задача расшифровки не решаема. Квантовая криптография основана на невозможности нарушить законы физики. Один из примеров – обмен секретными ключами BB84. Вася передает Маше набор квантовых частиц. Ревнивый злоумышленник Петя прослушивает канал связи и может перехватить частицы. Но для этого Пете придется измерить их. Он неминуемо разрушит их первоначальное состояние, что станет известно Васе и Маше.

Защита блокчейна. В принципе, она основана на том, что майнерам требуется большое количество времени, чтобы с помощью перебора найти число, при котором хеш блока меньше определенного порога. Это не позволяет подменить блок — пока новый хеш будет вычислен, цепочка уйдет далеко вперед. Квантовый блокчейн за счет параллелизма может мгновенно найти такое число, при котором хеш блока будет недосягаемо мал для классических вычислителей. Таким образом, атаковать сеть можно будет только при захвате 51% квантовых майнеров. А это выводит доверие на новый уровень – сговор более половины игроков с такими возможностями маловероятен.

Известно, что в 2014 году китайские исследователи впервые реализовали распознавание рукописного текста с помощью квантовых вычислений.

Наконец, мгновенная обработка колоссального объема данных и решение задач по оптимизации делают квантовые технологии одним из наиболее перспективных инструментов в области искусственного интеллекта и машинного обучения. По этой причине в 2013 году Google и NASA создали совместную лабораторию по исследованиям в этой области.

Подготовлено по материалам Дмитрия Сапаева, старшего руководителя направления по развитию ИТ-систем в отделе разработки ЦТИ Сбербанк-Технологий, и Дмитрия Булычкова, директора проектов в Центре технологических инноваций Сбербанка.

habr.com

Квантовый параллелизм — это… Что такое Квантовый параллелизм?



Квантовый параллелизм

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

См. также

Примечания

Ссылки

• R Jozsa. Characterising Classes of Functions Computable by Quantum Parallelism. Proc Roy Soc Lond A,volume 435: 563—574, September 1991.
• Гровер Л. К. Польза суперпозиции
• «Quantum Parallelism and the Exact Simulation of Physical Systems, » Computing Frontiers, Ischia, Italy, April 14, 2004.
• «The Challenges and the Promise of Quantum Parallelism, » (with G. M. Marinescu) Concurrent Processing, NATO Science Series, Computer and System Sciences, Vol. 195, IOS Press, pp. 159—174, 2005.
• «Quantum Parallelism, » 18th Annual ACM International Conference on Supercomputing (St.Mallo, France, June 2004).
• Dugic, Miroljub; Cirkovic, Milan M. Quantum Parallelism in Quantum Information Processing, опубликовано также в Journal of Theoretical Physics, Volume 41, Number 9, September 2002, pp. 1641—1649(9)
• B. Paredes, F. Verstraete, J. I. Cirac. Exploiting Quantum Parallelism To Simulate Quantum Random Many-Body Systems
• Holger F. Hofmann. Quantum parallelism of the controlled-NOT operation: An experimental criterion for the evaluation of device performance. Phys. Rev. A 72, 022329 (2005)
• Martin Ziegler. Computational Power of Infinite Quantum Parallelism. International Journal of Theoretical Physics Volume 44, Number 11 / November, 2005
• Алгоритм Дойча
• Mark A. Bashuk Solving a maze with a quantum computer

Категории:

• Квантовая механика
• Квантовый компьютер
• Информатика

Wikimedia Foundation. 2010.

• Рагуза
• Гранхольм, Бруно Фердинанд

Смотреть что такое «Квантовый параллелизм» в других словарях:

• Квантовый алгоритм — Квантовый алгоритм  это алгоритм, предназначенный для выполнения на квантовом компьютере. Квантовый алгоритм представляет собой классический алгоритм, который задает последовательность унитарных операций (гейтов, или вентилей) с указанием,… …   Википедия

• Квантовый компьютер — 3 кубита квантового регистра против 3 битов обычного Квантовый компьютер вычислительное устройство, работающее на основе квантовой механики. Квантовый компьютер принципиально отличается от классических компьютеров, работающих на основе …   Википедия

• квантовый компьютер — Термин квантовый компьютер Термин на английском quantum computer Синонимы квантовое вычислительное устройство Аббревиатуры КК Связанные термины Определение гипотетическое вычислительное устройство, которое при выполнении операций с данными… …   Энциклопедический словарь нанотехнологий

• Квантовые вычисления — 3 кубита квантового регистра против 3 битов обычного Квантовый компьютер  гипотетическое[1] вычислительное устройство, которое путем выполнения квантовых алгоритмов существенно использует при работе квантовомеханические эффекты, такие как… …   Википедия

• Квантовые компьютеры — 3 кубита квантового регистра против 3 битов обычного Квантовый компьютер  гипотетическое[1] вычислительное устройство, которое путем выполнения квантовых алгоритмов существенно использует при работе квантовомеханические эффекты, такие как… …   Википедия

• Кубит — (q бит, кьюбит; от quantum bit)  квантовый разряд или наименьший элемент для хранения информации в квантовом компьютере. Как и бит, кубит допускает два собственных состояния, обозначаемых и (обозначения Дирака), но при этом может находиться… …   Википедия

• Квантбит — Кубит (q бит, кьюбит; от quantum bit) квантовый разряд или наименьший элемент для хранения информации в квантовом компьютере . Как и бит, кьюбит допускает два собственных состояния, обозначаемых и , но при этом может находиться и в их… …   Википедия

• П:Ф — Начинающим · Сообщество · Порталы · Награды · Проекты · Запросы · Оценивание География · История · Общество · Персоналии · Религия · Спорт · Техника · Наука · Искусство · Философия …   Википедия

• Последние достижения в физике — Содержание 1 Космология 1.1 Открытие тёмной энергии 2 Физика элемента …   Википедия

dic.academic.ru

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

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

Продолжение

eslitak.livejournal.com

Квантовый параллелизм

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

См такжеправить

• Квантовый компьютер
• Квантовый алгоритм

Примечанияправить

1. ↑ 1 2 3 Beyond Bits: The Future of Quantum Information Processing Andrew M Steane, Eleanor G Rieffel
2. ↑ Eleanor Rieffel An Introduction to Quantum Computing for Non-Physicists

Ссылкиправить

• R Jozsa Characterising Classes of Functions Computable by Quantum Parallelism Proc Roy Soc Lond A,volume 435: 563—574, September 1991
• Гровер Л К Польза суперпозиции
• «Quantum Parallelism and the Exact Simulation of Physical Systems, » Computing Frontiers, Ischia, Italy, April 14, 2004
• «The Challenges and the Promise of Quantum Parallelism, » with G M Marinescu Concurrent Processing, NATO Science Series, Computer and System Sciences, Vol 195, IOS Press, pp 159–174, 2005
• «Quantum Parallelism, » 18th Annual ACM International Conference on Supercomputing StMallo, France, June 2004
• Dugic, Miroljub; Cirkovic, Milan M Quantum Parallelism in Quantum Information Processing, опубликовано также в Journal of Theoretical Physics, Volume 41, Number 9, September 2002, pp 1641—16499
• B Paredes, F Verstraete, J I Cirac Exploiting Quantum Parallelism To Simulate Quantum Random Many-Body Systems
• Holger F Hofmann Quantum parallelism of the controlled-NOT operation: An experimental criterion for the evaluation of device performance Phys Rev A 72, 022329 2005
• Martin Ziegler Computational Power of Infinite Quantum Parallelism International Journal of Theoretical Physics Volume 44, Number 11 / November, 2005
• Алгоритм Дойча
• Mark A Bashuk Solving a maze with a quantum computer

квантовый параллелизм биология, квантовый параллелизм в, квантовый параллелизм литература, квантовый параллелизм это

---

Квантовый параллелизм Информацию О

---

---

Квантовый параллелизм Комментарии

Квантовый параллелизм
Квантовый параллелизм
Квантовый параллелизм Вы просматриваете субъект

Квантовый параллелизм что, Квантовый параллелизм кто, Квантовый параллелизм описание

There are excerpts from wikipedia on this article and video

www.turkaramamotoru.com

Квантовый параллелизм — Википедия. Что такое Квантовый параллелизм

Материал из Википедии — свободной энциклопедии

Квантовый параллелизм — принцип, лежащий в основе работы квантовых компьютеров и позволяющий им потенциально превзойти в производительности классические компьютеры. В основе квантового параллелизма лежит использование при вычислениях суперпозиций базовых состояний, что позволяет одновременно производить большое количество вычислений с различными исходными данными. Например, 64-разрядный квантовый регистр может хранить до 264{\displaystyle 2^{64}} значений одновременно^[1][2], а квантовый компьютер может все эти значения одновременно обрабатывать^[1]. Тем не менее, извлечение результатов таких вычислений затруднено, что ограничивает область применения квантовых компьютеров^[1].

См. также

Примечания

Ссылки

• R Jozsa. Characterising Classes of Functions Computable by Quantum Parallelism. Proc Roy Soc Lond A,volume 435: 563—574, September 1991.
• Гровер Л. К. Польза суперпозиции
• «Quantum Parallelism and the Exact Simulation of Physical Systems, » Computing Frontiers, Ischia, Italy, April 14, 2004.
• «The Challenges and the Promise of Quantum Parallelism, » (with G. M. Marinescu) Concurrent Processing, NATO Science Series, Computer and System Sciences, Vol. 195, IOS Press, pp. 159–174, 2005.
• «Quantum Parallelism, » 18th Annual ACM International Conference on Supercomputing (St.Mallo, France, June 2004).
• Dugic, Miroljub; Cirkovic, Milan M. Quantum Parallelism in Quantum Information Processing, опубликовано также в Journal of Theoretical Physics, Volume 41, Number 9, September 2002, pp. 1641—1649(9) (недоступная ссылка)
• B. Paredes, F. Verstraete, J. I. Cirac. Exploiting Quantum Parallelism To Simulate Quantum Random Many-Body Systems
• Holger F. Hofmann. Quantum parallelism of the controlled-NOT operation: An experimental criterion for the evaluation of device performance. Phys. Rev. A 72, 022329 (2005) (недоступная ссылка)
• Martin Ziegler. Computational Power of Infinite Quantum Parallelism. International Journal of Theoretical Physics Volume 44, Number 11 / November, 2005
• Алгоритм Дойча
• Mark A. Bashuk Solving a maze with a quantum computer

wiki.sc

Квантовый параллелизм — Howling Pixel

Квантовый параллелизм — принцип, лежащий в основе работы квантовых компьютеров и позволяющий им потенциально превзойти в производительности классические компьютеры. В основе квантового параллелизма лежит использование при вычислениях суперпозиций базовых состояний, что позволяет одновременно производить большое количество вычислений с различными исходными данными. Например, 64-разрядный квантовый регистр может хранить до 264{\displaystyle 2^{64}} значений одновременно^[1][2], а квантовый компьютер может все эти значения одновременно обрабатывать^[1]. Тем не менее, извлечение результатов таких вычислений затруднено, что ограничивает область применения квантовых компьютеров^[1].

См. также

Примечания

1. ↑ ^{1 2 3} Beyond Bits: The Future of Quantum Information Processing Andrew M. Steane, Eleanor G. Rieffel
2. ↑ Eleanor Rieffel. An Introduction to Quantum Computing for Non-Physicists

Ссылки

• R Jozsa. Characterising Classes of Functions Computable by Quantum Parallelism. Proc Roy Soc Lond A,volume 435: 563—574, September 1991.
• Гровер Л. К. Польза суперпозиции
• «Quantum Parallelism and the Exact Simulation of Physical Systems, » Computing Frontiers, Ischia, Italy, April 14, 2004.
• «The Challenges and the Promise of Quantum Parallelism, » (with G. M. Marinescu) Concurrent Processing, NATO Science Series, Computer and System Sciences, Vol. 195, IOS Press, pp. 159–174, 2005.
• «Quantum Parallelism, » 18th Annual ACM International Conference on Supercomputing (St.Mallo, France, June 2004).
• Dugic, Miroljub; Cirkovic, Milan M. Quantum Parallelism in Quantum Information Processing, опубликовано также в Journal of Theoretical Physics, Volume 41, Number 9, September 2002, pp. 1641—1649(9) (недоступная ссылка)
• B. Paredes, F. Verstraete, J. I. Cirac. Exploiting Quantum Parallelism To Simulate Quantum Random Many-Body Systems
• Holger F. Hofmann. Quantum parallelism of the controlled-NOT operation: An experimental criterion for the evaluation of device performance. Phys. Rev. A 72, 022329 (2005) (недоступная ссылка)
• Martin Ziegler. Computational Power of Infinite Quantum Parallelism. International Journal of Theoretical Physics Volume 44, Number 11 / November, 2005
• Алгоритм Дойча
• Mark A. Bashuk Solving a maze with a quantum computer

Квантовый алгоритм

Квантовый алгоритм — это алгоритм, предназначенный для выполнения на квантовом компьютере.

Квантовый компьютер

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

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

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

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

This page is based on a Wikipedia article written by authors (here).
Text is available under the CC BY-SA 3.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

howlingpixel.com

Квантовый параллелизм Википедия

Квантовый параллелизм — принцип, лежащий в основе работы квантовых компьютеров и позволяющий им потенциально превзойти в производительности классические компьютеры. В основе квантового параллелизма лежит использование при вычислениях суперпозиций базовых состояний, что позволяет одновременно производить большое количество вычислений с различными исходными данными. Например, 64-разрядный квантовый регистр может хранить до 264{\displaystyle 2^{64}} значений одновременно^[1][2], а квантовый компьютер может все эти значения одновременно обрабатывать^[1]. Тем не менее, извлечение результатов таких вычислений затруднено, что ограничивает область применения квантовых компьютеров^[1].

См. также[ | ]

Примечания[ | ]

Ссылки[ | ]

• R Jozsa. Characterising Classes of Functions Computable by Quantum Parallelism. Proc Roy Soc Lond A,volume 435: 563—574, September 1991.
• Гровер Л. К. Польза суперпозиции
• «Quantum Parallelism and the Exact Simulation of Physical Systems, » Computing Frontiers, Ischia, Italy, April 14, 2004.
• «The Challenges and the Promise of Quantum Parallelism, » (with G. M. Marinescu) Concurrent Processing, NATO Science Series, Computer and System Sciences, Vol. 195, IOS Press, pp. 159–174, 2005.
• «Quantum Parallelism, » 18th Annual ACM International Conference on Supercomputing (St.Mallo, France, June 2004).
• Dugic, Miroljub; Cirkovic, Milan M. Quantum Parallelism in Quantum Information Processing, опубликовано также в Journal of Theoretical Physics, Volume 41, Number 9, September 2002, pp. 1641—1649(9) (недоступная ссылка)
• B. Paredes, F. Verstraete, J. I. Cirac. Exploiting Quantum Parallelism To Simulate Quantum Random Many-Body Systems
• Holger F. Hofmann. Quantum parallelism of the controlled-NOT operation: An experimental criterion for the evaluation of device performance. Phys. Rev. A 72, 022329 (2005) (недоступная ссылка)
• Martin Ziegler. Computational Power of Infinite Quantum Parallelism. International Journal of Theoretical Physics Volume 44, Number 11 / November, 2005
• Алгоритм Дойча
• Mark A. Bashuk Solving a maze with a quantum computer

ru-wiki.ru