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


Квантовый компьютер — Википедия

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

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

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

Идея о квантовых вычислениях была высказана Юрием Маниным в 1980 году[3].

Одна из первых моделей квантового компьютера была предложена[4]Ричардом Фейнманом в 1981 году. Вскоре Пол Бениофф описал теоретические основы построения такого компьютера[5].

Также концепцию квантового компьютера в 1983 году предлагал Стивен Визнер (англ.) в статье, которую он пытался опубликовать в течение более десяти лет до этого[6][7].

Необходимость в квантовом компьютере возникает тогда, когда мы пытаемся исследовать методами физики сложные многочастичные системы, подобные биологическим. Пространство квантовых состояний таких систем растет как экспонента от числа n{\displaystyle n} составляющих их реальных частиц, что делает невозможным моделирование их поведения на классических компьютерах уже для n=10{\displaystyle n=10}. Поэтому Визнер и Фейнман высказали идею построения квантового компьютера.

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

Если классический процессор в каждый момент может находиться ровно в одном из состояний |0⟩,|1⟩,…,|N−1⟩{\displaystyle |0\rangle ,|1\rangle ,\ldots ,|N-1\rangle } (обозначения Дирака), то квантовый процессор в каждый момент находится одновременно во всех этих базисных состояниях, при этом в каждом состоянии |j⟩{\displaystyle |j\rangle } — со своей комплексной амплитудой λj{\displaystyle \lambda _{j}}. Это квантовое состояние называется «квантовой суперпозицией» данных классических состояний и обозначается как

|Ψ⟩=∑j=0N−1λj|j⟩.{\displaystyle |\Psi \rangle =\sum \limits _{j=0}^{N-1}\lambda _{j}|j\rangle .}

Базисные состояния могут иметь и более сложный вид. Тогда квантовую суперпозицию можно проиллюстрировать, например, так: «Вообразите атом, который мог бы подвергнуться радиоактивному распаду в определённый промежуток времени. Или не подвергнуться. Мы можем ожидать, что у этого атома есть только два возможных состояния: „распад“ и „нераспад“, <…> но в квантовой механике у атома может быть некое объединённое состояние — „распада — нераспада“, то есть ни то, ни другое, а между. Вот это состояние и называется „суперпозицией“»[8].

Квантовое состояние |Ψ⟩{\displaystyle |\Psi \rangle } может изменяться во времени двумя принципиально различными путями:

  1. Унитарная квантовая операция (квантовый вентиль, англ. quantum gate), в дальнейшем просто операция.
  2. Измерение (наблюдение).

Если классические состояния |j⟩{\displaystyle |j\rangle } есть пространственные положения группы электронов в квантовых точках, управляемых внешним полем V{\displaystyle V}, то унитарная операция есть решение уравнения Шрёдингера для этого потенциала.

Измерение есть случайная величина, принимающая значения |j⟩, j=0,1,…,N−1{\displaystyle |j\rangle ,\ j=0,1,\ldots ,N-1} с вероятностями |λj|2{\displaystyle |\lambda _{j}|^{2}} соответственно. В этом состоит квантовомеханическое правило Борна. Измерение есть единственная возможность получения информации о квантовом состоянии, так как значения λj{\displaystyle \lambda _{j}} нам непосредственно недоступны. Измерение квантового состояния не может быть сведено к унитарной шрёдингеровской эволюции, так как, в отличие от последней, оно необратимо. При измерении происходит так называемый коллапс волновой функции |Ψ⟩{\displaystyle |\Psi \rangle }, физическая природа которого до конца не ясна. Спонтанные вредоносные измерения состояния в ходе вычисления ведут к декогерентности, то есть отклонению от унитарной эволюции, что является главным препятствием при построении квантового компьютера (см. физические реализации квантовых компьютеров).

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

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

Кубит[править | править код]

Идея квантовых вычислений состоит в том, что квантовая система из L двухуровневых квантовых элементов (квантовых битов, кубитов) имеет 2L линейно независимых состояний, а значит, вследствие принципа квантовой суперпозиции, пространство состояний такого квантового регистра является 2L-мерным гильбертовым пространством. Операция в квантовых вычислениях соответствует повороту вектора состояния регистра в этом пространстве. Таким образом, квантовое вычислительное устройство размером L кубитов фактически задействует одновременно 2L классических состояний.

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

Один классический бит может находиться в одном и только в одном из состояний |0⟩{\displaystyle |0\rangle } или |1⟩{\displaystyle |1\rangle }. Квантовый бит, называемый кубитом, находится в состоянии |ψ⟩=a|0⟩+b|1⟩{\displaystyle |\psi \rangle =a\,|0\rangle +b\,|1\rangle }, так что |a|² и |b|² — вероятности получить 0 или 1 соответственно при измерении этого состояния; a,b∈C{\displaystyle a,b\in \mathbb {C} }; |a|² + |b|² = 1. Сразу после измерения кубит переходит в базовое квантовое состояние, соответствующее классическому результату.

Пример:

Имеется кубит в квантовом состоянии 45|0⟩−35|1⟩{\displaystyle {\tfrac {4}{5}}\,|0\rangle -{\tfrac {3}{5}}\,|1\rangle }
В этом случае вероятность получить при измерении
0 составляет (4/5)² = 16/25 = 0,64,
1 составляет (−3/5)² = 9/25 = 0,36.
В данном случае при измерении мы получили 0 с вероятностью 0,64.
В результате измерения кубит переходит в новое квантовое состояние |0⟩{\displaystyle |0\rangle }, то есть при следующем измерении этого кубита мы получим 0 с единичной вероятностью (предполагается, что по умолчанию унитарная операция тождественна; в реальных системах это не всегда так).

Приведём для объяснения два примера из квантовой механики: 1) фотон находится в состоянии |ψ⟩{\displaystyle |\psi \rangle } суперпозиции двух поляризаций. Это состояние есть вектор в двумерной плоскости, систему координат в которой можно представлять как две перпендикулярные оси, так что a{\displaystyle a} и b{\displaystyle b} есть проекции |ψ⟩{\displaystyle |\psi \rangle } на эти оси; измерение раз и навсегда коллапсирует состояние фотона в одно из состояний |0⟩{\displaystyle |0\rangle } или |1⟩{\displaystyle |1\rangle }, причём вероятность коллапса равна квадрату соответствующей проекции. Полная вероятность получается по теореме Пифагора.

Перейдём к системе из двух кубитов. Измерение каждого из них может дать 0 или 1. Поэтому у системы есть 4 классических состояния: 00, 01, 10 и 11. Аналогичные им базовые квантовые состояния: |00⟩,|01⟩,|10⟩,|11⟩{\displaystyle |00\rangle ,|01\rangle ,|10\rangle ,|11\rangle }. И наконец, общее квантовое состояние системы имеет вид |Ψ⟩=a|00⟩+b|01⟩+c|10⟩+d|11⟩{\displaystyle |\Psi \rangle =a\,|00\rangle +b\,|01\rangle +c\,|10\rangle +d\,|11\rangle }. Теперь |a|² — вероятность измерить 00 и т. д. Отметим, что |a|² + |b|² + |c|² + |d|² = 1 как полная вероятность.

Если мы измерим только первый кубит квантовой системы, находящейся в состоянии |Ψ⟩{\displaystyle |\Psi \rangle }, у нас получится:

  1. С вероятностью p0=|a|2+|b|2{\displaystyle p_{0}=|a|^{2}+|b|^{2}} первый кубит перейдёт в состояние |0⟩{\displaystyle |0\rangle }, а второй — в состояние 1|a|2+|b|2(a|0⟩+b|1⟩){\displaystyle {\tfrac {1}{\sqrt {|a|^{2}+|b|^{2}}}}(a\,|0\rangle +b\,|1\rangle )},
  2. С вероятностью p1=|c|2+|d|2{\displaystyle p_{1}=|c|^{2}+|d|^{2}} первый кубит перейдёт в состояние |1⟩{\displaystyle |1\rangle }, а второй — в состояние 1|c|2+|d|2(c|0⟩+d|1⟩){\displaystyle {\tfrac {1}{\sqrt {|c|^{2}+|d|^{2}}}}(c\,|0\rangle +d\,|1\rangle )}.

В первом случае измерение даст состояние |Ψ0⟩=|0⟩⊗1|a|2+|b|2(a|0⟩+b|1⟩){\displaystyle |\Psi _{0}\rangle =|0\rangle \otimes {\tfrac {1}{\sqrt {|a|^{2}+|b|^{2}}}}(a\,|0\rangle +b\,|1\rangle )}, во втором — состояние |Ψ1⟩=|1⟩⊗1|c|2+|d|2(c|0⟩+d|1⟩){\displaystyle |\Psi _{1}\rangle =|1\rangle \otimes {\tfrac {1}{\sqrt {|c|^{2}+|d|^{2}}}}(c\,|0\rangle +d\,|1\rangle )}.

Мы снова видим, что результат такого измерения невозможно записать как вектор в гильбертовом пространстве состояний. Такое состояние, в котором участвует наше незнание о том, какой же результат получится на первом кубите, называют смешанным состоянием. В нашем случае такое смешанное состояние называют проекцией исходного состояния |Ψ⟩{\displaystyle |\Psi \rangle } на второй кубит и записывают в виде матрицы плотности вида ρ2=p0ρΨ0+p1ρΨ1{\displaystyle \rho _{2}=p_{0}\rho _{\Psi _{0}}+p_{1}\rho _{\Psi _{1}}}, где матрица плотности состояния |ψ⟩{\displaystyle |\psi \rangle } определяется как |ψ⟩⟨ψ|{\displaystyle |\psi \rangle \langle \psi |}.

В общем случае у системы из L кубитов существует 2L классических состояний (00000… (L нулей), …00001 (L цифр), … , 11111… (L единиц)), каждое из которых может быть измерено с вероятностями 0—1.

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

Вычисление[править | править код]

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

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

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

Большая часть современных ЭВМ работают по такой же схеме: n битов памяти хранят состояние и каждый такт времени изменяются процессором. В квантовом случае система из n кубитов находится в состоянии, являющемся суперпозицией всех базовых состояний, поэтому изменение системы касается всех 2n базовых состояний одновременно. Теоретически новая схема может работать намного (в экспоненциальное число раз) быстрее классической. Практически, например, квантовый алгоритм Гровера поиска в базе данных показывает квадратичный прирост мощности против классических алгоритмов

Алгоритмы[править | править код]

  • Алгоритм Гровера позволяет найти решение уравнения f(x)=1, 0⩽x<N{\displaystyle f(x)=1,\ 0\leqslant x<N} за время O(N){\displaystyle O({\sqrt {N}})}.
  • Алгоритм Шора позволяет разложить натуральное число n на простые множители за полиномиальное от log n время.
  • Алгоритм Залки — Визнера позволяет моделировать унитарную эволюцию квантовой системы n{\displaystyle n} частиц за почти линейное время с использованием O(n){\displaystyle O(n)} кубитов.
  • Алгоритм Дойча — Йожи позволяет «за одно вычисление» определить, является ли функция двоичной переменной f(n) постоянной (f1(n) = 0, f2(n) = 1 независимо от n) или «сбалансированной» (f3(0) = 0, f3(1) = 1; f4(0) = 1, f4(1) = 0).
  • Алгоритм Саймона[en] решает проблему чёрного ящика экспоненциально быстрее, чем любой классический алгоритм, включая вероятностные алгоритмы.

Было показано, что не для всякого алгоритма возможно «квантовое ускорение». Более того, возможность получения квантового ускорения для произвольного классического алгоритма является большой редкостью[11].

Пример реализации операции CNOT на зарядовых состояниях электрона в квантовых точках[править | править код]

Любая квантовая операция может быть реализована при помощи логического вентиля «контролируемое отрицание» (CNOT) и поворота состояния одного кубита[12][13].

Один кубит можно представить в виде электрона в двухъямном потенциале, так что |0⟩{\displaystyle |0\rangle } означает нахождение его в левой яме, а |1⟩{\displaystyle |1\rangle } — в правой. Это называется кубит на зарядовых состояниях. Общий вид квантового состояния такого электрона: |Ψ⟩=λ0|0⟩+λ1|1⟩{\displaystyle |\Psi \rangle =\lambda _{0}|0\rangle +\lambda _{1}|1\rangle }. Зависимость его от времени есть зависимость от времени амплитуд λ0,λ1{\displaystyle \lambda _{0},\lambda _{1}}; она задаётся уравнением Шрёдингера вида iℏ∂∂tΨ=HΨ{\displaystyle i\hbar {\tfrac {\partial }{\partial t}}\Psi =H\Psi }, где гамильтониан H{\displaystyle H} имеет в силу одинакового вида ям и эрмитовости вид (a−a−aa){\displaystyle {\begin{pmatrix}a&-a\\-a&a\end{pmatrix}}} для некоторой константы a{\displaystyle a}, так что вектор |0~⟩=12(|0⟩+|1⟩){\displaystyle |{\tilde {0}}\rangle ={\tfrac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )} есть собственный вектор этого гамильтониана с собственным значением 0 (так называемое основное состояние), а |1~⟩=12(|0⟩−|1⟩){\displaystyle |{\tilde {1}}\rangle ={\tfrac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )} — собственный вектор со значением 2a{\displaystyle 2a} (первое возбуждённое состояние). Никаких других собственных состояний (с определённым значением энергии) здесь нет, так как наша задача двумерная.

Поскольку каждое состояние |Ψ⟩{\displaystyle |\Psi \rangle } переходит за время t{\displaystyle t} в состояние λ0exp⁡(0t)|0~⟩+λ1exp⁡(−2at/ℏ)|1~⟩{\displaystyle \lambda _{0}\exp(0t)|{\tilde {0}}\rangle +\lambda _{1}\exp(-2at/\hbar )|{\tilde {1}}\rangle }, то для реализации операции NOT (перехода |0⟩→|1⟩{\displaystyle |0\rangle \to |1\rangle } и наоборот достаточно просто подождать время t=πℏ/(2a){\displaystyle t=\pi \hbar /(2a)}. То есть операция NOT реализуется просто естественной квантовой эволюцией кубита при условии, что внешний потенциал задаёт двухъямную структуру; это делается с помощью технологии квантовых точек.

Для реализации CNOT надо расположить два кубита (то есть две пары ям) перпендикулярно друг другу и в каждой из них расположить по отдельному электрону. Тогда константа a{\displaystyle a} для первой (управляемой) пары ям будет зависеть от того, в каком состоянии находится электрон во второй (управляющей) паре ям: если ближе к первой, то a{\displaystyle a} будет больше, если дальше — меньше. Поэтому состояние электрона во второй паре определяет время совершения NOT в первой яме, что позволяет снова выбрать нужную длительность времени для реализации операции CNOT.

Эта схема очень приблизительная и идеализирована; реальные схемы сложнее и их реализация представляет вызов экспериментальной физике.

Квантовая телепортация[править | править код]

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

ru.wikipedia.org

Немного о квантовых компьютерах и о том, изменят ли они нашу жизнь

Многие из нас слышали о квантовом компьютер, но что он собой представляет, а главное какие задачи с помощью него можно решать, известно далеко не всем. Квантовый компьютер уже несколько лет активно изучают лучшие умы мира; он даже появлялся на обложке журнала Time, с подписью: «Он обещает решить некоторые самые сложные проблемы человечества, при этом никто не знает, как он в действительности работает».

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

Квантовый компьютер и непреодолимые трудности

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

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

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

Принцип работы квантового компьютера

Классический компьютер работает на основе транзисторов и кремниевых чипов, которые используют для обработки информации бинарный код, состоящий из нулей и единиц. Бит, как минимальная единица информации имеет два базовых состояния: 1 и 0. Изменения этих состояний можно легко контролировать: объекты могут либо находиться в конкретном месте, либо — не находится. Именно поэтому многие физические объекты внешнего мира можно перенести в виртуальный с помощью сложных комбинаций битов. Работа же квантового компьютера будет основываться на принципе суперпозиции, а вместо битов будут использоваться кубиты (квантовые биты), которые одновременно могут находиться во всевозможных состояниях (в 1 и 0 одновременно). По словам ученных, за счет этого квантовые компьютеры для определенных классов задач будут в миллионы раз мощнее нынешних. Сейчас уже описаны десятки всевозможных алгоритмов работы квантового компьютера, даже разрабатываются особые языки программирования.

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

Для чего нужен квантовый компьютер?

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

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

Исправление ошибок — основная проблема квантовых компьютеров

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

Кубиты изначально по своей природе нестабильны, они мгновенно забывают информацию, которую вы хотите сохранить на квантовый компьютер. Под воздействием на кубит окружающей среды нарушается связь внутри квантовой системы (процесс декогеренции). Чтобы избавиться от этого, квантовый процессор нужно максимально изолировать от воздействия внешних факторов. Как это сделать? — пока остается загадкой. По словам экспертов, 99% мощности такого компьютера уйдет на исправления ошибок, и лишь 1% хватит для решения любых задач. Конечно, от ошибок не удастся избавиться полностью, но если минимизировать их до определенного уровня, квантовый компьютер сможет работать.

Насколько человечество близко к созданию квантовых компьютеров?

Дать ответ на этот вопрос сейчас очень сложно — практически невозможно. Новости о прорывах в этой сфере появляются регулярно, но нельзя сказать, что они глобальные. В создании квантовых компьютеров заинтересованы все: начиная военными и заканчивая технологическими компаниями. Компания D-Wawe, с которой активно сотрудничает Google и NASA, заявляет, что создала процессор с 84 кубитами, но критики, проанализировавшие его сообщили, что он работает как классический. IBM несколько лет назад объявили, что создали чип с тремя кубитами, а Microsoft основательно занимается разработкой квантовых компьютеров еще с 2007 года.

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

habr.com

Квантовые компьютеры и конец безопасности

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

Мы живем в мире радиоволн и электромагнитных сигналов. Wi-Fi, GSM, спутниковое ТВ и GPS, точное время и FM-тюнер — лишь немногие из повседневных технологий, в которых используются электромагнитные волны. Конечно, в список нужно включить и все виды компьютеров, от гигантских дата-центров до смартфонов и ноутбуков. Одна из особенностей электромагнитных сигналов состоит в том, что их довольно легко измерить, то есть перехватить. Именно поэтому практически все вышеперечисленное сегодня снабжено технологией шифрования, защищающей информацию от чтения и изменения посторонними. При этом запасного канала связи обычно нет, и разработчики криптосистем блестяще решили сложную проблему — как договориться о секретном ключе шифрования, когда весь процесс переговоров могут слушать посторонние? Именно решение этой проблемы лежит в основе всех современных систем защиты, и именно ему предположительно положат конец квантовые компьютеры.  Спасет ли положение возникшая заодно квантовая криптография?

В чем соль

Название квантовых систем точно передает смысл — их работа основана на квантовых эффектах, таких как суперпозиция и спутывание (сцепление) микрочастиц.

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

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

Все кванты — в беленьком квадратике справа

Хозяйке на заметку. Современные системы, например лежащие в основе SSL, HTTPS, VPN и т.п., обычно шифруют все данные с помощью секретного ключа и симметричного алгоритма. Ключ одинаков у отправителя и получателя (отсюда название симметричный), устанавливается в начале сессии при помощи второй, асимметричной криптосистемы. Асимметричный алгоритм используется только для передачи секретного ключа в силу своей вычислительной сложности. Безопасность асимметричной криптосистемы основана на математической сложности решения той или иной задачи, например разложения на множители очень больших целых чисел (алгоритм RSA). Даже просто перемножить два больших числа относительно трудоемко, что уж говорить о переборе!  То есть речь идет о том, что шпион может перехватить сообщения, но на расшифровку уйдет неразумно много времени (от десятков до миллионов лет в зависимости от длины ключа). Как выясняется, квантовые компьютеры при помощи алгоритма Шора приходят к необходимому состоянию, соответствующему найденному решению математической задачи, существенно быстрее — почти так же быстро, как обычный компьютер проводит шифрование. Таким образом, несмотря на необходимость нескольких запусков и поддержку со стороны классических компьютеров,  квантовый компьютер может за очень короткое время подобрать числа для асимметричного алгоритма, что поможет атакующему извлечь секретный ключ и дальше спокойно расшифровывать основной обмен сообщениями. Качественные симметричные алгоритмы, например AES, кстати, не имеют особенностей, которые хотя бы теоретически приводили к таким опасным последствиям. В частности, квантовый компьютер, по имеющимся оценкам, может ускорить перебор ключей AES, но не радикально. Поиск 256-битного ключа AES  на квантовом компьютере эквивалентен поиску 128-битного ключа на обычном — вполне терпимо, запас прочности остается большим.

В чем трудность

Квантовый компьютер, быть может, давно стоял бы на столе каждого малолетнего хакера, желающего читать переписку одноклассников в «ВКонтакте», но создание компьютера сопряжено с рядом чисто инженерных сложностей, которые настолько велики, что некоторые специалисты считают создание «полноценного» квантового компьютера невыполнимой задачей. Главная проблема состоит в том, чтобы поддерживать кубиты в состоянии запутанности, поскольку любая квантовая система то и дело норовит «свалиться» в классическую, лишенную неопределенности. Тут нельзя не упомянуть многострадального кота Шредингера, который все же не может быть жив и мертв одновременно, а в квантовом компьютере это удивительное состояние должно поддерживаться достаточное время для прогона задачи и измерения результатов. Обычно речь идет о наносекундах, в лучших системах — единицах секунд. Сложность задачи растет с ростом числа кубитов. Для решения задач по взлому шифров нужен квантовый компьютер с 500–2000 кубитов (в зависимости от разрядности ключа в криптоалгоритме), в то время как большинство существующих систем оперируют с единицами кубитов (рекорд – 14 кубитов). Таким образом, взлом вашего SSL-сертификата на квантовом компьютере сегодня еще невозможен, но, возможно, будет реален уже через пять лет.

Главные популяризаторы науки и многострадального кота Шредингера — Пенни и Шелдон из «Теории Большого взрыва»

Шаги к цели

На фоне вышеописанных сложностей, с которыми сталкиваются почти все разработчики, очень вызывающе выглядят заявления физиков компании D-Wave, которая продает квантовые компьютеры из 512 кубит. Многие специалисты отрицают, что у D-Wave получился «настоящий» квантовый компьютер, поскольку он основан на эффекте квантового отжига,  но трудно спорить с деньгами — первыми клиентами, заплатившими до $10 млн за свой компьютер, стали гигант оборонной промышленности США Lockheed Martin и Google. Несмотря на все «но», компьютер решает определенный класс задач оптимизации явно квантовыми методами, то есть честно выполняет свою работу. Он не приспособлен для решения многих других «квантовых» задач, что признают и создатели, но практическую пользу уже приносит. Google планирует решать на компьютере задачи машинного обучения, а Lockheed Martin на ряде экспериментов убедились, что компьютер способен находить ошибки в программном коде сложнейших приложений, управляющих истребителями F-35.  Правда (и это хорошие новости для нас с вами), компьютер D-Wave плохо приспособлен для вышеописанных задач по факторизации, поэтому не представляет особой угрозы для современных криптоалгоритмов.  Угроза лежит в иной плоскости — работающий квантовый компьютер стимулирует большие компании и государства более активно вкладываться в разработки, ускоряя появление других видов квантовых компьютеров, которые способны подбирать криптоключи.

D-Wave Two — квантовый компьютер-отжигатель

Квантовая криптография

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

Попытка прослушать сигнал искажает сообщение.

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

Коммерческая система Cerberis для квантового распределения ключей

В отличие от квантовых компьютеров, квантовые криптосистемы уже давно не являются лабораторной инновацией. Хотя первые научные работы на эту тему появились тоже на рубеже 70–80-х годов ХХ века, до практического воплощения дело дошло быстрее. Первые лабораторные тесты прошли в 1989 году, а уже в конце 90-х функционировали коммерческие системы квантовой передачи ключей на расстояние от 20 до 50 км. Такие компании, как id Quantique и MagiQ Technologies, продают готовые системы передачи криптоключей по обычному оптоволоконному кабелю. Эти системы достаточно просты для установки обычным специалистом по прокладке компьютерных сетей. Соответственно, кроме разного рода военных и правительственных организаций их взяли на вооружение крупные коммерческие организации, банки и даже FIFA.

Идеальная защита?

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

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

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

www.kaspersky.ru

Как устроен и зачем нужен квантовый компьютер

Сей­час мно­го гово­рят о новых тех­но­ло­ги­ях вычис­ле­ния — в част­но­сти, то и дело зву­чат сло­ва «кван­то­вые вычис­ле­ния», «кван­то­вый интер­нет» и даже «кван­то­вая крип­то­гра­фия». Посмот­рим, что это такое и нуж­но ли оно нам. Нач­нём с кван­то­во­го ком­пью­те­ра. 

Биты и кубиты

В обыч­ном ком­пью­те­ре все вычис­ле­ния осно­ва­ны на поня­тии «бит». Это такой эле­мент, кото­рый может при­ни­мать зна­че­ния 0 или 1. Физи­че­ски это реа­ли­зо­ва­но так:

  1. В ком­пью­те­ре есть деталь под назва­ни­ем тран­зи­стор. Пред­ставь­те, что это кран на тру­бе: если его вклю­чить, вода польёт­ся, если выклю­чить — оста­но­вит­ся.
  2. В тран­зи­сто­ре вода — это элек­три­че­ство, и включение-выключение кра­на тоже зави­сит от элек­три­че­ства. Пред­ставь­те, что кра­ны соеди­не­ны меж­ду собой так, что вода из одно­го кра­на вклю­ча­ет или выклю­ча­ет дру­гой кран, — и так кас­ка­дом по цепоч­ке.
  3. Тран­зи­сто­ры соеди­не­ны таким хит­рым обра­зом, что когда они вклю­ча­ют­ся и выклю­ча­ют­ся, на них мож­но про­из­во­дить мате­ма­ти­че­ские вычис­ле­ния.
  4. Из-за того, что тран­зи­сто­ров очень мно­го (мил­ли­ар­ды), а рабо­та­ют они очень быст­ро (близ­ко к ско­ро­сти све­та), тран­зи­стор­ные ком­пью­те­ры могут очень быст­ро совер­шать мате­ма­ти­че­ские вычис­ле­ния.
  5. Всё, что вы види­те в ком­пью­те­ре, — это про­из­вод­ные от вычис­ле­ний. Вы види­те окно, бук­вы, кар­тин­ки, а где-то в самой-самой глу­бине это про­сто сло­же­ние и вычи­та­ние, а ещё глуб­же — включение-выключение кра­нов с элек­три­че­ством на ско­ро­сти све­та. 

Тран­зи­стор в ком­пью­те­ре может при­ни­мать зна­че­ние 1 или 0, то есть «вклю­чён» или «выклю­чен». С точ­ки зре­ния ком­пью­тер­ной логи­ки, этот тран­зи­стор назы­ва­ет­ся битом. Это мини­маль­ная еди­ни­ца инфор­ма­ции в ком­пью­те­ре. Физи­че­ски бит может быть в про­цес­со­ре, на чипе памя­ти, на маг­нит­ном дис­ке, но суть одна: это какое-то физи­че­ское про­стран­ство, кото­рое опре­де­лён­но либо вклю­че­но, либо выклю­че­но.

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

В кван­то­вом ком­пью­те­ре вме­сто битов — куби­ты. Куби­ты — это кван­то­вые части­цы, у кото­рых есть инте­рес­ная осо­бен­ность: кро­ме стан­дарт­ных 0 и 1 кубит может нахо­дить­ся меж­ду нулём и еди­ни­цей — это назы­ва­ют супер­по­зи­ци­ей. Нагляд­нее это вид­но на рисун­ке:


Кубит может при­ни­мать все зна­че­ния, кото­рые вид­ны на цвет­ной сфе­ре

Все решения уже известны

Ещё одна осо­бен­ность куби­тов — зави­си­мость зна­че­ния от изме­ре­ния. Это зна­чит, что про­грам­мист не узна­ет зна­че­ние куби­та до тех пор, пока его не изме­рит, а сам факт изме­ре­ния тоже вли­я­ет на зна­че­ние куби­та. Зву­чит стран­но, но это осо­бен­ность кван­то­вых частиц.

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

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


Рабо­чая тем­пе­ра­ту­ра внут­ри таких ком­пью­те­ров — минус 273 гра­ду­са по Цель­сию

Как делают кубиты и в чём сложность

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

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

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

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

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


Кван­то­вый про­цес­сор на девя­ти куби­тах от Google

Зачем нужны квантовые компьютеры

Одно из самых важ­ных при­ме­не­ний кван­то­во­го ком­пью­те­ра сей­час — раз­ло­же­ние на про­стые чис­ла. Дело в том, что вся совре­мен­ная крип­то­гра­фия осно­ва­на на том, что никто не смо­жет быст­ро раз­ло­жить чис­ло из 30–40 зна­ков (или боль­ше) на про­стые мно­жи­те­ли. На обыч­ном ком­пью­те­ре на это уйдёт мил­ли­ар­ды лет. Кван­то­вый ком­пью­тер смо­жет это сде­лать при­мер­но за 18 секунд.

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

Ещё кван­то­вые ком­пью­те­ры отлич­но под­хо­дят для моде­ли­ро­ва­ния слож­ных ситу­а­ций, напри­мер, рас­чё­та физи­че­ских свойств новых эле­мен­тов на моле­ку­ляр­ном уровне. Это, воз­мож­но, поз­во­лит быст­рее нахо­дить новые лекар­ства или решать слож­ные ресур­со­ём­кие зада­чи.

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

thecode.media

что такое квантовый компьютер и зачем он нужен — T&P

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

Евгений Глушков

Студент шестого курса МФТИ, инженер лаборатории искусственных квантовых систем, создатель и редактор ресурса Make It Quantum.

До квантовой в ходу была классическая теория электромагнитного излучения. В 1900 году немецкий ученый Макс Планк, который сам в кванты не верил, считал их вымышленной и чисто теоретической конструкцией, был вынужден признать, что энергия нагретого тела излучается порциями — квантами; таким образом, предположения теории совпали с экспериментальными наблюдениями. А пять лет спустя великий Альберт Эйнштейн прибегнул к этому же подходу при объяснении фотоэффекта: при облучении светом в металлах возникал электрический ток! Вряд ли Планк с Эйнштейном могли предположить, что своими работами закладывают основы новой науки — квантовой механики, которой будет суждено до неузнаваемости преобразить наш мир, и что в XXI веке ученые вплотную приблизятся к созданию квантового компьютера.

Вначале квантовая механика позволила объяснить структуру атома и помогла понять происходящие внутри него процессы. По большому счету сбылась давняя мечта алхимиков о превращении атомов одних элементов в атомы других (да, даже в золото). А знаменитая формула Эйнштейна E=mc2 привела к появлению атомной энергетики и, как следствие, атомной бомбы.

Квантовый процессор на пяти кубитах от IBM

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

Быстро и эффективно решать многие задачи позволило развитие электронных вычислительных машин — компьютеров. А постепенное уменьшение их размеров и стоимости (в связи с массовым производством) проложило компьютерам дорогу в каждый дом. С появлением интернета наша зависимость от компьютерных систем, в том числе и для коммуникации, стала еще сильнее.

Ричард Фейнман

Зависимость растет, постоянно растут вычислительные мощности, но настала пора признать, что, несмотря на свои впечатляющие возможности, компьютеры оказались не в состоянии решить все задачи, которые мы готовы перед ними ставить. Одним из первых об этом начал говорить знаменитый физик Ричард Фейнман: еще в 1981 году на конференции он заявил, что на обычных компьютерах принципиально невозможно точно рассчитать реальную физическую систему. Все дело в ее квантовой природе! Эффекты микромасштаба легко объясняются квантовой механикой и из рук вон плохо — привычной нам классической механикой: она описывает поведение больших объектов. Тогда-то в качестве альтернативы Фейнман предложил использовать для расчетов физических систем квантовые компьютеры.

Что же такое квантовый компьютер и в чем его отличие от компьютеров, к которым мы привыкли? Все дело в том, как мы представляем себе информацию.

Если в обычных компьютерах за эту функцию отвечают биты — нули и единички, — то в квантовых компьютерах им на смену приходят квантовые биты (сокращенно — кубиты). Сам кубит — вещь довольно простая. У него по-прежнему два основных значения (или состояния, как любят говорить в квантовой механике), которые он может принимать: 0 и 1. Однако благодаря свойству квантовых объектов под названием «суперпозиция» кубит может принимать все значения, которые являются комбинацией основных. При этом его квантовая природа позволяет ему находиться во всех этих состояниях одновременно.

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

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

Одна из переборных задач выделялась своей кажущейся бесполезностью — разложение больших чисел на простые множители (то есть делящиеся нацело только на самих себя и единицу). Это называется «факторизация». Дело в том, что обычные компьютеры умеют довольно быстро перемножать числа, пусть даже и весьма большие. Однако с обратной задачей разложения большого числа, получившегося в результате перемножения двух простых чисел, на исходные множители обычные компьютеры справляются очень плохо. Например, чтобы разложить на два сомножителя число из 256 цифр, даже самому мощному компьютеру понадобится не один десяток лет. А вот квантовый алгоритм, который может решить эту задачу за несколько минут, придумал в 1997 году английский математик Питер Шор.

  • Первый российский кубит под электронным микроскопом

  • Квантовый процессор на девяти кубитах от Google

С появлением алгоритма Шора перед научным сообществом встала серьезная проблема. Еще в конце 1970-х годов, основываясь на сложности задачи факторизации, ученые-криптографы создали алгоритм шифрования данных, получивший повсеместное распространение. В частности, с помощью этого алгоритма стали защищать данные в интернете — пароли, личную переписку, банковские и финансовые транзакции. И после многолетнего успешного использования вдруг оказалось, что зашифрованная таким способом информация становится легкой мишенью для алгоритма Шора, запущенного на квантовом компьютере. Дешифровка с его помощью становится минутным делом. Радовало одно: квантовый компьютер, на котором можно было бы запустить смертоносный алгоритм, еще не был создан.

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

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

Сотрудники лаборатории искусственных квантовых систем

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

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

Так что, на радость криптографам, квантовый компьютер — все еще дело будущего. Хотя уже совсем не такого далекого, как могло когда-то казаться, ведь к его созданию активно подключаются как крупнейшие корпорации вроде Intel, IBM и Google, так и отдельные государства, для которых создание квантового компьютера — вопрос стратегической важности.

Не пропустите лекцию:

theoryandpractice.ru

Квантовые компьютеры | Наука и жизнь

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

Американский математик и физик венгерского происхождения Иоганн фон Нейман (1903- 1957).

Американский физик-теоретик Ричард Филлипс Фейнман (1918-1988).

Американский математик Питер Шор, специалист в области квантовых вычислений. Предложил квантовый алгоритм быстрой факторизации больших чисел.

Американский математик Лов Гровер, автор квантового алгоритма быстрого поиска в базе данных.

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

Квантовый регистр - цепочка квантовых битов. Одно- или двухкубитовые квантовые вентили осуществляют логические операции над кубитами.

ВВЕДЕНИЕ, ИЛИ НЕМНОГО О ЗАЩИТЕ ИНФОРМАЦИИ

Как вы думаете, на какую программу в мире продано наибольшее количество лицензий? Не рискну настаивать, что знаю правильный ответ, но мне точно известен один неверный: это не какая-либо из версий Microsoft Windows. Самую распространенную операционную систему опережает скромный продукт фирмы RSA Data Security, Inc. - программа, реализующая алгоритм шифрования с открытым ключом RSA, названный так в честь его авторов - американских математиков Ривеста, Шамира и Адельмана.

Дело в том, что алгоритм RSA встроен в большинство продаваемых операционных систем, а также во множество других приложений, используемых в различных устройствах - от смарткарт до сотовых телефонов. В частности, имеется он и в Microsoft Windows, а значит, распространен заведомо шире этой популярной операционной системы. Чтобы обнаружить следы RSA, к примеру, в браузере Internet Explorer (программе для просмотра www-страниц в сети Интернет), достаточно открыть меню "Справка" (Help), войти в подменю "О программе" (About Internet Explorer) и просмотреть список используемых продуктов других фирм. Еще один распространенный браузер Netscape Navigator тоже использует алгоритм RSA. Вообще, трудно найти известную фирму, работающую в области высоких технологий, которая не купила бы лицензию на эту программу. На сегодняшний день фирма RSA Data Security, Inc. продала уже более 450 миллионов(!) лицензий.

Почему же алгоритм RSA оказался так важен?

Представьте, что вам необходимо быстро обменяться сообщением с человеком, находящимся далеко. Благодаря развитию Интернета такой обмен стал доступен сегодня большинству людей - надо только иметь компьютер с модемом или сетевой картой. Естественно, что, обмениваясь информацией по сети, вы бы хотели сохранить свои сообщения в тайне от посторонних. Однако полностью защитить протяженную линию связи от прослушивания невозможно. Значит, при посылке сообщений их необходимо зашифровать, а при получении - расшифровать. Но как вам и вашему собеседнику договориться о том, каким ключом вы будете пользоваться? Если послать ключ к шифру по той же линии, то подслушивающий злоумышленник легко его перехватит. Можно, конечно, передать ключ по какой-нибудь другой линии связи, например отправить его телеграммой. Но такой метод обычно неудобен и к тому же не всегда надежен: другую линию тоже могут прослушивать. Хорошо, если вы и ваш адресат заранее знали, что будете обмениваться шифровками, и потому заблаго-временно передали друг другу ключи. А как быть, например, если вы хотите послать конфиденциальное коммерческое предложение возможному деловому партнеру или купить по кредитной карточке понравившийся товар в новом Интернет-магазине?

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

Как раз такая криптографическая схема и применяется в алгоритме RSA - самом распространенном методе шифрования с открытым ключом. Причем для создания пары открытого и закрытого ключей используется следующая важная гипотеза. Если имеется два больших (требующих более сотни десятичных цифр для своей записи) простых числа M и K, то найти их произведение N=MK не составит большого труда (для этого даже не обязательно иметь компьютер: достаточно аккуратный и терпеливый человек сможет перемножить такие числа с помощью ручки и бумаги). А вот решить обратную задачу, то есть, зная большое число N, разложить его на простые множители M и K (так называемая задача факторизации ) - практически невозможно! Именно с этой проблемой столкнется злоумышленник, решивший "взломать" алгоритм RSA и прочитать зашифрованную с его помощью информацию: чтобы узнать закрытый ключ, зная открытый, придется вычислить M или K.

Для проверки справедливости гипотезы о практической сложности разложения на множители больших чисел проводились и до сих пор еще проводятся специальные конкурсы. Рекордом считается разложение всего лишь 155-значного (512-битного) числа. Вычисления велись параллельно на многих компьютерах в течение семи месяцев 1999 года. Если бы эта задача выполнялась на одном современном персональном компьютере, потребовалось бы примерно 35 лет машинного времени! Расчеты показывают, что с использованием даже тысячи современных рабочих станций и лучшего из известных на сегодня вычислительных алгоритмов одно 250-значное число может быть разложено на множители примерно за 800 тысяч лет, а 1000-значное - за 1025(!) лет. (Для сравнения возраст Вселенной равен ~1010 лет.)

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

Оказывается, используя законы квантовой механики, можно построить такие компьютеры, для которых задача факторизации (и многие другие!) не составит большого труда. Согласно оценкам, квантовый компьютер с памятью объемом всего лишь около 10 тысяч квантовых битов способен разложить 1000-значное число на простые множители в течение всего нескольких часов!

КАК ВСЕ НАЧИНАЛОСЬ?

Только к середине 1990-х годов теория квантовых компьютеров и квантовых вычислений утвердилась в качестве новой области науки. Как это часто бывает с великими идеями, сложно выделить первооткрывателя. По-видимому, первым обратил внимание на возможность разработки квантовой логики венгерский математик И. фон Нейман. Однако в то время еще не были созданы не то что квантовые, но и обычные, классические, компьютеры. А с появлением последних основные усилия ученых оказались направлены в первую очередь на поиск и разработку для них новых элементов (транзисторов, а затем и интегральных схем), а не на создание принципиально других вычислитель ных устройств.

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

По мере распространения компьютеров ученые, занимавшиеся квантовыми объектами, пришли к выводу о практической невозможности напрямую рассчитать состояние эволюционирующей системы, состоящей всего лишь из нескольких десятков взаимодействующих частиц, например молекулы метана (СН4). Объясняется это тем, что для полного описания сложной системы необходимо держать в памяти компьютера экспоненциально большое (по числу частиц) количество переменных, так называемых квантовых амплитуд. Возникла парадоксальная ситуация: зная уравнение эволюции, зная с достаточной точностью все потенциалы взаимодействия частиц друг с другом и начальное состояние системы, практически невозможно вычислить ее будущее, даже если система состоит лишь из 30 электронов в потенциальной яме, а в распоряжении имеется суперкомпьютер с оперативной памятью, число битов которой равно числу атомов в видимой области Вселенной(!). И в то же время для исследования динамики такой системы можно просто поставить эксперимент с 30 электронами, поместив их в заданные потенциал и начальное состояние. На это, в частности, обратил внимание русский математик Ю. И. Манин, указавший в 1980 году на необходимость разработки теории квантовых вычислительных устройств. В 1980-е годы эту же проблему изучали американский физик П. Бенев, явно показавший, что квантовая система может производить вычисления, а также английский ученый Д. Дойч, теоретически разработавший универсальный квантовый компьютер, превосходящий классический аналог.

Большое внимание к проблеме разработки квантовых компьютеров привлек лауреат Нобелевской премии по физике Р. Фейн-ман, хорошо знакомый постоянным читателям "Науки и жизни". Благодаря его авторитетному призыву число специалистов, обративших внимание на квантовые вычисления, увеличилось во много раз.

И все же долгое время оставалось неясным, можно ли использовать гипотетическую вычислительную мощь квантового компьютера для ускорения решения практических задач. Но вот в 1994 году американский математик, сотрудник фирмы Lucent Technologies (США) П. Шор ошеломил научный мир, предложив квантовый алгоритм, позволяющий проводить быструю факторизацию больших чисел (о важности этой задачи уже шла речь во введении). По сравнению с лучшим из известных на сегодня классических методов квантовый алгоритм Шора дает многократное ускорение вычислений, причем, чем длиннее факторизуемое число, тем значительней выигрыш в скорости. Алгоритм быстрой факторизации представляет огромный практический интерес для различных спецслужб, накопивших банки нерасшифрованных сообщений.

В 1996 году коллега Шора по работе в Lucent Technologies Л. Гровер предложил квантовый алгоритм быстрого поиска в неупорядоченной базе данных. (Пример такой базы данных - телефонная книга, в которой фамилии абонентов расположены не по алфавиту, а произвольным образом.) Задача поиска, выбора оптимального элемента среди многочисленных вариантов очень часто встречается в экономических, военных, инженерных задачах, в компьютерных играх. Алгоритм Гровера позволяет не только ускорить процесс поиска, но и увеличить примерно в два раза число параметров, учитываемых при выборе оптимума.

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

УСТРОЙСТВО КВАНТОВОГО КОМПЬЮТЕРА

Прежде чем рассказать, как же устроен квантовый компьютер, вспомним основные особенности квантовых систем (см. также "Наука и жизнь" № 8, 1998 г.; № 12, 2000 г.).

Для понимания законов квантового мира не следует прямо опираться на повседневный опыт. Обычным образом (в житейском понимании) квантовые частицы ведут себя лишь в том случае, если мы постоянно "подглядываем" за ними, или, говоря более строго, постоянно измеряем, в каком состоянии они находятся. Но стоит нам "отвернуться" (прекратить наблюдение), как квантовые частицы тут же переходят из вполне определенного состояния сразу в несколько различных ипостасей. То есть электрон (или любой другой квантовый объект) частично будет находиться в одной точке, частично в другой, частично в третьей и т. д. Это не означает, что он делится на дольки, как апельсин. Тогда можно было бы надежно изолировать какую-нибудь часть электрона и измерить ее заряд или массу. Но опыт показывает, что после измерения электрон всегда оказывается "целым и невредимым" в одной единственной точке, несмотря на то, что до этого он успел побывать одновременно почти везде. Такое состояние электрона, когда он находится сразу в нескольких точках пространства, называют суперпозицией квантовых состояний и описывают обычно волновой функцией, введенной в 1926 году немецким физиком Э. Шредингером. Модуль значения волновой функции в любой точке, возведенный в квадрат, определяет вероятность найти частицу в этой точке в данный момент. После измерения положения частицы ее волновая функция как бы стягивается (коллапсирует) в ту точку, где частица была обнаружена, а затем опять начинает расплываться. Свойство квантовых частиц быть одновременно во многих состояниях, называемое квантовым параллелизмом , успешно используется в квантовых вычислениях.

Квантовый бит

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

Квантовый регистр

Квантовый регистр устроен почти так же, как и классический. Это цепочка квантовых битов, над которыми можно проводить одно- и двухбитовые логические операции (подобно применению операций НЕ, 2И-НЕ и т.п. в классическом регистре).

К базовым состояниям квантового регистра, образованного L кубитами, относятся, так же как и в классическом, все возможные последовательности нулей и единиц длиной L. Всего может быть 2L различных комбинаций. Их можно считать записью чисел в двоичной форме от 0 до 2L-1 и обозначать . Однако эти базовые состояния не исчерпывают всех возможных значений квантового регистра (в отличие от классического), поскольку существуют еще и состояния суперпозиции, задаваемые комплексными амплитудами, связанными условием нормировки. Классического аналога у большинства возможных значений квантового регистра (за исключением базовых) просто не существует. Состояния классического регистра - лишь жалкая тень всего богатства состояний квантового компьютера.

Представьте, что на регистр осуществляется внешнее воздействие, например, в часть пространства поданы электрические импульсы или направлены лазерные лучи. Если это классический регистр, импульс, который можно рассматривать как вычислительную операцию, изменит L переменных. Если же это квантовый регистр, то тот же импульс может одновременно преобразовать до переменных. Таким образом, квантовый регистр, в принципе, способен обрабатывать информацию в раз быстрее по сравнению со своим классическим аналогом. Отсюда сразу видно, что маленькие квантовые регистры (L<20) могут служить лишь для демонстрации отдельных узлов и принципов работы квантового компьютера, но не принесут большой практической пользы, так как не сумеют обогнать современные ЭВМ, а стоить будут заведомо дороже. В действительности квантовое ускорение обычно значительно меньше, чем приведенная грубая оценка сверху (это связано со сложностью получения большого количества амплитуд и считывания результата), поэтому практически полезный квантовый компьютер должен содержать тысячи кубитов. Но, с другой стороны, понятно, что для достижения действительного ускорения вычислений нет необходимости собирать миллионы квантовых битов. Компьютер с памятью, измеряемой всего лишь в килокубитах, будет в некоторых задачах несоизмеримо быстрее, чем классический суперкомпьютер с терабайтами памяти.

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

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

КВАНТОВЫЕ КОМПЬЮТЕРЫ СЕГОДНЯ

Прототипы квантовых компьютеров существуют уже сегодня. Правда, пока что экспериментально удается собирать лишь небольшие регистры, состоящие всего из нескольких квантовых битов. Так, недавно группа, возглавляемая американским физиком И. Чангом (IBM), объявила о сборке 5-битового квантового компьютера. Несомненно, это большой успех. К сожалению, существующие квантовые системы еще не способны обеспечить надежные вычисления, так как они либо недостаточно управляемы, либо очень подвержены влиянию шумов. Однако физических запретов на построение эффективного квантового компьютера нет, необходимо лишь преодолеть технологические трудности.

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

И. Чанг развивает идею об использовании в качестве кубитов спинов ядер некоторых органических молекул.

Российский исследователь М. В. Фейгельман, работающий в Институте теоретической физики им. Л. Д. Ландау РАН, предлагает собирать квантовые регистры из миниатюрных сверхпроводни ковых колец. Каждое кольцо выполняет роль кубита, а состояниям 0 и 1 соответствуют направления электрического тока в кольце - по часовой стрелке и против нее. Переключать такие кубиты можно магнитным полем.

В Физико-технологическом институте РАН группа под руководством академика К. А. Валиева предложила два варианта размещения кубитов в полупроводниковых структурах. В первом случае роль кубита выполняет электрон в системе из двух потенциальных ям, создаваемых напряжением, приложенным к мини-электродам на поверхности полупроводника. Состояния 0 и 1 - положения электрона в одной из этих ям. Переключается кубит изменением напряжения на одном из электродов. В другом варианте кубитом является ядро атома фосфора, внедренного в определенную точку полупровод ника. Состояния 0 и 1 - направления спина ядра вдоль либо против внешнего магнитного поля. Управление ведется с помощью совместного действия магнитных импульсов резонансной частоты и импульсов напряжения.

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

ВЗГЛЯД В БУДУЩЕЕ

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

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

А что же станет с классическими компью-терами? Отомрут ли они? Вряд ли. И для классических, и для квантовых компьютеров найдутся свои сферы применения. Хотя, по всей видимости, соотношение на рынке будет все же постепенно смещаться в сторону последних.

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

Автор выражает благодарность Лову Гроверу и Питеру Шору за любезно предоставленные материалы и поддержку при написании статьи.

ЧТО ЧИТАТЬ О КВАНТОВЫХ КОМПЬЮТЕРАХ

Для более глубокого освоения этой темы можно прочитать обзорную статью Э. Риффеля, В. Полака "Основы квантовых вычислений", опубликованную в издаваемом в России журнале "Квантовые компьютеры и квантовые вычисления" (№ 1, 2000 г.). (Кстати, это первый и пока единственный в мире журнал, посвященный квантовым вычислениям. Дополнительную информацию о нем можно узнать в Интернете по адресу http://rcd.ru/qc.). Освоив эту работу, вы сможете читать научные статьи по квантовым вычислениям.

Несколько большая предварительная математическая подготовка потребуется при чтении книги А. Китаева, А. Шеня, М. Вялого "Классические и квантовые вычисления" (М.: МЦНМО-ЧеРо, 1999).

Ряд принципиальных аспектов квантовой механики, существенных для проведения квантовых вычислений, разобран в книге В. В. Белокурова, О. Д. Тимофеевской, О. А. Хрусталева "Квантовая телепортация - обыкновенное чудо" (Ижевск: РХД, 2000).

В издательстве РХД готовится к выходу в виде отдельной книги перевод обзора А. Стина, посвященный квантовым компьютерам.

По вторникам с 15.00 в конференц-зале Физико-технологического институт РАН в Москве проходит семинар "Квантовый компьютер". Информацию о том, как принять участие в семинаре, можно узнать в Интернете по адресу http://qc.ipt.ac.ru.

Следующая литература будет полезна не только в познавательном, но и в историческом плане:

1) Ю. И. Манин. Вычислимое и невычислимое.

- М.: Сов. радио, 1980.

2) И. фон Нейман. Математические основы квантовой механики.

- М.: Наука, 1964.

3) Р. Фейнман. Моделирование физики на компьютерах // Квантовый компьютер и квантовые вычисления:

Сб. в 2-х т. - Ижевск: РХД, 1999. Т. 2, с. 96-123.

4) Р. Фейнман. Квантово-механические компьютеры

// Там же, с. 123.-156.

См. в номере на ту же тему

Квантовые биты и вентили

www.nkj.ru

Как работает квантовый компьютер: Объясняем на пальцах | Технологии

С этим объяснением вы точно все наконец поймете.

Что такое квантовый компьютер? Вот определение этого термина, сокращенное до одного предложения:

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

В этом предложении скрыто слишком много нюансов, поэтому обратимся к простому примеру. Чтобы объяснить, что такое квантовый компьютер, давайте сначала поговорим о том, как работает обычная ЭВМ.

Как хранит информацию обычный компьютер

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

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

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

Давайте воспользуемся простым примером. Он может показаться немного искусственным, но все же поможет нам разобраться в принципах работы квантовых компьютеров.

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

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

Предположим, что отношения в группе распределяются следующим образом:

  • Аня и Ваня — друзья;
  • Аня и Сережа — враги;
  • Ваня и Сережа — враги.

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

  • Максимизировать число друзей;
  • Минимизировать число врагов, попавших в одно и то же такси.

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

Решение задачи на обычном компьютере

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

  • Аня едет в такси 0;
  • Ваня также едет в такси 0;
  • Сережа едет в такси 1.

Поскольку для каждого пассажира есть два варианта, всего существует 2 * 2 * 2 = 8 способов разместить трех человек в двух машинах. Вот список всех возможных конфигураций:

С помощью трех битов можно представить любую из этих комбинаций.

Вычисление оценки для каждой конфигурации

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

  • Максимизировать число пар друзей в автомобиле;
  • Минимизировать количество пар врагов;

Давайте определим оценку следующим образом:

(оценка некоторого размещения) = (количество дружественных пар в автомобиле) — (число враждебных пар в автомобиле)

Предположим, что Аня, Ваня и Сережа сели в такси 1. В битах это выглядит как 111. В данной ситуации имеется только одна пара друзей — Аня и Ваня, но две враждебных пары: Аня и Сережа, Ваня и Сережа. Таким образом, общий балл этой конфигурации равен 1 — 2 = -1

Решение задачи

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

Как видно, имеется два правильных решения — 001 и 110. Оба набрали наибольшее количество очков (1). Эта задача довольно проста. Ее сложность стремительно возрастает по мере увеличения числа людей. С тремя пассажирами существует восемь возможных конфигураций. С четырьмя их число возрастает до 2 * 2 * 2 * 2 = 16 конфигураций. В общем случае с N пассажирами существует (2 в степени N) возможных расстановок. Если у нас всего 100 человек, необходимо просчитать:

2¹⁰⁰ ~= 10³⁰ = один миллион миллионов миллионов миллионов миллионов конфигураций.

Обычному компьютеру это не под силу.

Решение задачи на квантовом компьютере

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

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

Пока нет единой точки зрения на данный феномен. Можно рассматривать его следующим образом.

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

В одном из миров кубит равен 0, в другом он равен 1. Что произойдет, если второй кубит также одновременно установить на 0 и 1? В этом случае у нас появится четыре параллельных мира. В первом мире оба кубита установлены на 0 (00). Во втором они равны 01. В третьем — 01, в четвертом — 11.

Похожим образом, если установить все три кубита на 0 и 1, возникнут восемь параллельных миров: 000, 001, 010, 011, 100, 101, 110 и 111.

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

В этом конкретном примере квантовый компьютер теоретически найдет одно из лучших решений за доли секунды (001 или 110):

На самом деле, чтобы вычислить эту задачу, необходимо задать квантовому два начальных условия:

  • Все потенциальные решения, представленные кубитами;
  • Функцию, которая каждому решению присваивает некую оценку. В данном случае она подсчитывает число дружеских и вражеских пар в автомобиле.

Используя эти данные, квантовый компьютер найдет одно из лучших решений за доли секунды. В нашем случае это будет 001 или 110 с баллом, равном единице.

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

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

Масштабирование квантового компьютера

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

В случае четырех человек число операций остается прежним — 1. То же самое справедливо для 100 человек. Одной операцией квантовый компьютер вычисляет все 2¹⁰⁰ ~= 10³⁰ возможных конфигураций.

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

Подписывайтесь на наш канал в Яндекс.Дзен. Лучшее о финансах и технологиях, а также криптовалюты, эксклюзивы и немного лайфстайла.

ru.ihodl.com

Характеристики квантовых компьютеров / Habr

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

Я делаю фейспалм после каждого прочтения подобной фразы. До добра это не довело, начало садиться зрение; скоро придется обращаться к Meklon.

Думаю, пора несколько систематизировать основные параметры квантового компьютера. Их несколько:

  1. Количество кубитов
  2. Время удержания когерентности (время декогеренции)
  3. Уровень ошибок
  4. Архитектура процессора
  5. Цена, доступность, условия содержания, время амортизации, инструменты программирования, и т.д.

Количество кубитов


Тут все очевидно, чем больше, тем лучше. На деле же, за кубиты нужно платить, и в идеале нужно покупать ровно столько кубитов, сколько требуется для выполнения задачи. Для разработчика эксклюзивных игровых автоматов достаточно одного кубита на автомат (для генерации рандома). Для «брутфорса» RSA-2048 — как минимум 2048 кубитов.

Самые распиаренные квантовые алгоритмы носят имена Гровера и Шора. Гровер позволяет «хакать» хеши. Для краха биткоина нужны компьютеры с как минимум 256 кубитами на борту (можно пошаманить со сложностью биткоина, но давайте остановимся на этой круглой цифре). Шор позволяет факторизовать числа. Для факторизации числа длиной n двоичных разрядов нужно как минимум n кубитов.

Текущий максимум: 50 кубитов (уже 72?). И на самом деле, 50 кубитов это предел. Предел симуляции квантового компьютера. В теории, мы можем симулировать любое число кубитов на классических вычислителях. На практике, добавление одного кубита в симуляцию требует удвоения классических вычислителей. Добавьте сюда слухи об удвоении кубитов каждый год, и задайте себе вопрос: как дебажить алгоритмы для 256\512\1024\2048 кубитов? Симулятора нет, на квантовом процессоре брейк-поинт не поставишь.

Время удержания когерентности (время декогеренции)


Когеренция и когерентность — это не одно и то же. Я предпочитаю сравнивать когерентность с регенерацией оперативной памяти. На планке RAM миллиарды ячеек, на каждой висит заряд, нулевой или единичный. У этого заряда есть очень интересное свойство — он стекает. Изначально «единичная» ячейка становится ячейкой на 0.99, затем 0.98, и так далее. Соответственно, на нулевой накапливается 0.01, 0.02, 0.03… Приходится этот заряд обновлять, «регенерировать». Все, что меньше половины, сбрасывается до нуля, все остальное добивается до единицы.

Квантовые процессоры регенерировать не получится. Соответственно, на все вычисления есть один цикл, до первого «потекшего» кубита. Время до первого «подтека» и называется временем декогеренции. Когерентность же это состояние, когда кубиты еще не «протекли». Здесь можно посмотреть чуть более взрослые объяснения.

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

Приблизительно здесь возникает понятие логического кубита. Грубо говоря, если у вас есть процессор на 100 кубитов, но 40 из них направлены на фиксацию декогерентности — у вас остаются 60 логических кубитов. Тех, на которых вы исполняете ваш алгоритм. Концепт логических кубитов сейчас скорее теоретический, про практические реализации лично я не слышал.

Ошибки и их коррекция


Еще один бич квантовых процессоров. Если вы инвертируете кубит, с вероятностью в 2% операция закончится ошибкой. Если вы запутываете 2 кубита, вероятность ошибки достигает 8%. Возьмите число в 256 битов, захешируйте его на SHA-256, посчитайте количество операций, посчитайте вероятность выполнить ВСЕ эти операции безошибочно.

Математики предоставляют решение: коррекция ошибок. Алгоритмы есть. Реализация одного запутывания 2 логических кубитов требует 100.000 физических кубитов. Битко-капец наступит нескоро.

Архитектура процессора


Строго говоря, квантовых компьютеров нет. Есть только квантовые процессоры. Зачем нужна оперативка, когда время на работу ограничивается миллисекундами? Я программирую на Q#, но это язык высокого уровня. Выделил себе 15 кубитов, и делай с ними что хочешь. Захотел, запутал первый кубит с десятым. Возжелал — запутал первые шесть.

На реальном процессоре такой свободы нет. Попросил запутать первый кубит с 15 — компилятор сгенерирует 26 дополнительных операций. Если повезет. Если не повезет — сгенерирует сотню. Дело в том, что кубит может запутываться только с соседями. Больше, чем 6 соседей на кубит, я не видел. В принципе, есть оптимизирующие квантовые программы компиляторы, но они пока скорее теоретические.

У каждого процессора свой набор инструкций, и связи между кубитами различаются. В идеальном мире у нас есть произвольные Rx, Ry, Rz, и их комбинации, плюс свободное запутывание по десятку признаков, плюс Swap: посмотрите на операторы в Quirk. В реале же у нас имеется несколько пар кубитов, и запутывание CNOT (q[0], q[1]) обходится в одну операцию, а CNOT(q[1], q[0]) — уже в 7. А когерентность тает…

Цена, доступность, условия содержания, время амортизации, инструменты программирования…


Цены не афишируются, доступность рядовому гражданину околонулевая, время амортизации на практике не посчитано, инструменты программирования только зарождаются. Документация на arxiv.org.

Так какую же информация требовать от экспертов при выпуске нового квантового компьютера?


Помимо списка сверху, мне нравятся варианты от PerlPower и Alter2:
Вот бы каждая статья про новый квантовый компьютер начиналась с двух характеристик — количества одновременного спутанных кубитов, и времени удержания кубитов.
Или ещё лучше — с времени выполнения простейшего бенчмарка, например нахождения простых множителей числа 91.

habr.com

Квантовый компьютер - что это простыми словами, принцип действия

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

Я впервые начал интересоваться  этой темой при просмотре  фильмов про Эдварда Сноудена. Как известно, этот американский гражданин собрал несколько терабайт  конфиденциальной информации (компромата)  о деятельности спецслужб США,  хорошенько зашифровал ее и выложил в Интернет. «Если, сказал он, со мной что-нибудь случиться, информация будет расшифрована и станет таким образом доступна для всех.»

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

Принципы работы квантового компьютера для чайников

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

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

Так в чем же разница между обычным и квантовым компьютером? Ведь обычный компьютер тоже работает на электричестве, а электричество —  это куча очень маленьких частиц — электронов?

Наши с Вами компьютеры работают по принципу или «Да» или «Нет».  Если есть ток в проводе, это «Да»или «Единица». Если тока в проводе  «Нет», то это «Ноль». Вариант  значения «1 «и «0» есть единица хранения информации под названием «Бит».. Один байт это 8 бит и так далее и так далее…

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

Путем перебора  и  вычислений Ваш компьютер обрабатывает  Ваши запросы в Яндексе, ищет нужные  до тех пор, пока не решит задачу и  путем исключения  не  докопается до нужной Вам . Выводит на монитор шрифты, картинки в читаемом для нас виде… Пока надеюсь ничего сложного? А картинка  — это тоже нули и единицы.

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

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

Продолжим. И вот на смену «нашему» биту приходит квантовый бит. Его еще называют «Кубит». У него то же всего два исходных  состояния «ноль» и «единица». Но, так как природа его «квантовая», то он может  ОДНОВРЕМЕННО принимать все  возможные промежуточные значения. И одновременно находиться в них. Теперь значения не надо последовательно вычислять, перебирать.., долго искать в базе. Они известны уже заранее, сразу. Вычисления идут параллельно.

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

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

А что сейчас ? А вот так выглядит квантовый процессор под микроскопом  на 9 кубит от фирмы Google.

Неужели они нас обогнали? 9 кубит или по «старому» 15 бит, это не так много пока еще. Плюс дороговизна, масса технических проблем и короткое время «жизни» квантов. Но вспомните что сначала были 8 битные, потом появились 16 битные процессоры… Так будет и с этими …

Квантовый компьютер в России — миф или реальность?

А мы что же? А мы то же не за печкой родились. Вот нарыл фото первого российского Кубита под микроскопом. Тут правда он один.

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

Последние новости о квантовом компьютере России мощностью 51 кубит

Вот новости этого лета. Наши дядечки (честь им и хвала!) разработали самый мощный в мире (!) квантовый (!) компьютер  51 кубит(!)т. Самое интересное то, что до этого Google анонсировало свой компьютер на 49 кубит. И по их оценкам они должны были его закончить через месяц или около того. А наши решили показать уже готовый, свой квантовый процессор на 51 кубит.. Браво! Вот какая идет гонка. Нам хотя бы не отставать. Потому что ожидается  большой прорыв в науке, когда  эти системы заработают. Вот фото человека, который  представлял нашу разработку на «квантовом» международном форуме.

Фамилия этого ученого — Михаил Лукин. Сегодня его имя в центре внимания. Невозможно создать такой проект в одиночку, мы это понимаем. Он и его команда создали на сегодня самый мощный в мире(!) квантовый компьютер или процессор. Вот что говорят по этому поводу  компетентные лица:

«Квантовый компьютер функционирующий, он гораздо страшнее атомной бомбы, — отмечает сооснователь Российского квантового центра Сергей Белоусов. — Он (Михаил Лукин) сделал систему, в которой больше всего кубитов. На всякий случай. На данный момент, я думаю, это более чем в два раза больше кубитов, чем у кого-либо другого. И он специально сделал 51 кубит, а не 49. Потому что Google всё время говорили, что сделают 49».

Впрочем, сам Лукин и руководитель квантовой лаборатории Google Джон Мартинес конкурентами или соперниками себя не считают. Учёные убеждены, что их главным соперником является природа, а основной целью — развитие технологий и их внедрение для продвижения человечества на новый виток развития.

«Неправильно думать об этом, как о гонке, — справедливо считает Джон Мартинес. — Настоящая гонка у нас с природой. Потому что это действительно сложно — создать квантовый компьютер. И это просто захватывающе, что кому-то удалось создать систему с таким большим количеством кубитов. Пока 22 кубита — это максимум, что мы могли сделать. Хоть мы и использовали всё своё волшебство и профессионализм».

Да, все это очень  интересно. Если вспомнить аналогии, когда изобрели транзистор, никто не мог знать, что на этой технологии через 70 лет будут работать компьютеры. В одном только  современном процессоре количество их достигает 700 миллионов..Первый компьютер весил много тонн и занимал большие площади. Но персональные компьютеры все равно  появились — много позже…

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

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

Только  бы не подвел  человеков  свой собственный квантовый компьютер, данный нам при рождении — это наша голова. Так что, пока не спешите выкидывать на помойку свои гаджеты. Они долго Вам еще послужат.  Пишите, если статья была интересной. Заходите чаще. До свидания!

Автор публикации

не в сети 21 час

admin

0 Комментарии: 59Публикации: 348Регистрация: 04-09-2015

fast-wolker.ru

«Для чего нужен квантовый компьютер?» – Яндекс.Кью

До сегодняшнего дня существовал только 17-ти кубитный компьютер, разработанный IBM. Авторы новой работы улучшили результат в три раза, создав компьютер на холодных атомах, удерживаемых оптическими пинцетами (о различиях этих двух машин можно узнать из ответа NEKTO V-PALTO) . 

Число кубитов в квантовом компьютере так же важно, как и число битов в обычном ЭВМ. Только вот при измерении бита мы всегда получим один и тот же результат — «ноль» или «единицу», а измерение одинаково приготовленных кубитов будет с некоторой вероятностью давать и «ноль», и «единицу» — до измерения кубит будет одновременно и «нулем» и «единицей». Как говорят физики — он будет в суперпозиции двух состояний.

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

Один из самых простых примеров — алгоритм Дойча. Предположим, у вас есть функция, которая может иметь значение ноль или единица, в зависимости от аргумента. Аргумент тоже может быть нулем или единицей. Всего существует четыре таких простых функции. Чтобы узнать, всегда ли эта функция выдает строго ноль или строго единицу, классическому алгоритму потребуется дважды ее вычислить. Для квантового алгоритма хватит одного вычисления.

Другой пример — алгоритм Шора для разложения натурального числа на простые множители. Классические алгоритмы могут сделать это только полным перебором, причем с ростом количества знаков в раскладываемом натуральном числе количество операций растет экспоненциально (условно, каждый знак увеличивает время расчета в 10 раз). Квантовому алгоритму требуется лишь полиномиальное время (полином от числа знаков в числе).

Есть еще несколько примеров, связанных с перебором, которые быстро решаются с помощью квантовых алгоритмов. Основной прирост производительности в таких задачах связан именно с существованием кубитов в суперпозиции состояний. Интересно, что в ряде случаев в алгоритм можно вводить суперпозицию порядка вычислений. То есть, например, одновременно проводить над числом умножение, а потом возведение в степень, и возведение в степень, а потом умножение. Такие операции позволяют выяснить за одно действие, есть ли разница между порядком выполнения двух операций (A, затем B, и B, затем A).

Зато такие задачи, как сложение двух натуральных чисел (например, 2+2), для квантового компьютера оказываются совсем не тривиальными. 

Подробнее научно-популярным языком о квантовых компьютерах здесь.

Для более глубокого освоения этой темы можно прочитать обзорную статью Э. Риффеля, В. Полака "Основы квантовых вычислений". Освоив эту работу, вы сможете читать научные статьи по квантовым вычислениям.

Следующая литература будет полезна не только в познавательном, но и в историческом плане:

1) Ю. И. Манин. Вычислимое и невычислимое

2) И. фон Нейман. Математические основы квантовой механики

3) Р. Фейнман. Моделирование физики на компьютерах

4) Р. Фейнман. Квантово-механические компьютеры

yandex.ru

Почему так сложно создать квантовый компьютер?

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

Почему за квантовым компьютером будущее?

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

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

Перемножить целые числа — это просто, а вот узнать, на какие простые множители разлагается число — крайне трудная задача для классического компьютера. 15 факторизуется на простые числа 3 и 5. Но что если число очень большое и состоит из тысяч цифр?

В теории на классическом компьютере такую задачу разрешить можно, однако на практике это потребует много времени. Увеличивается число — временны́е затраты возрастают по экспоненте и быстро выходят на времена, сравнимые с возрастом Вселенной. А алгоритм Шора, используя возможности квантовых компьютеров, способен произвести факторизацию за время, не намного превосходящее время умножения целых чисел.

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

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

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

А еще квантовые компьютеры могут быть очень полезными для моделирования динамики сложных квантовых систем. Именно в этом еще в начале 80-х годов прошлого века видел их выгоду знаменитый физик, лауреат Нобелевской премии Ричард Фейнман. Кстати, сама идея квантовых вычислений предложена известным советским математиком Юрием Маниным в 1980 году.

Что же такое квантовый компьютер?

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

— Помните мысленный эксперимент с котом Шредингера? Пока мы не откроем коробку, кот в ней и «жив», и «мертв» одновременно. Состояние кота в коробке и называется суперпозицией.

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

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

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

Сверхпроводящие кубиты можно создавать на основе существующих методов литографии и помещать на чипы, не боясь, что они куда-нибудь сбегут как атомы. Так, в 2015 году Министерство образования и науки РФ сообщало о создании кубитов из четырех джозефсоновских контактов на «петле» размером в один микрон: «Контакты состоят из алюминиевых полосок, разделенных слоем диэлектрика (оксида алюминия) толщиной около 2 нанометров». Для печати кубита использовалась технология электронной и фотолитографии. Процесс этот весьма увлекательный и подробно расписан создателями в их блоге.

Существуют ли настоящие квантовые компьютеры?

— Они уже есть, и вполне настоящие. Их покупают и продают. Канадская компания «Ди-вэйв» (D-Wave) с 2011 года продает процессоры на нескольких сотнях и более кубитов. Одним из покупателей является аэрокосмическая корпорация «Локхид Мартин» (Lockheed Martin), приобретшая один из первых 128-кубитных процессоров за $11 млн. В начале прошлого года «Ди-вэйв» выпустила устройство с 2000 кубитов.

Правда, на стол в каждой отдельной семье квантовый компьютер поставить трудно — это ящик трехметровой высоты стоимостью $15 млн, внутри которого холоднее, чем в открытом космосе, нагретом реликтовым излучением до 2,725 Кельвина или -270,425 градусов по Цельсию. [Компьютер D-Wave работает при температуре -273 градуса по Цельсию, тогда как на орбите Земли средняя температура абсолютно черного тела составит +4 градуса — прим. Onliner.by]. И даже если оставить сомнения в истинной квантовости компьютера «Ди-вэйв», выгода от него — лишь для отдельных специализированных задач.

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

А летом прошлого года группа физиков под руководством профессора Гарварда и сооснователя Российского квантового центра Михаила Лукина смогла создать 51-кубитный квантовый компьютер для моделирования квантовых систем, то есть квантовый симулятор. «Наш симулятор обладает достаточно хорошей когерентностью и довольно большим количеством кубитов, но все это есть и у других систем. Что важно — нам удалось сделать систему с высокой степенью программируемости», — говорил Михаил Лукин в интервью РБК. Квантовый симулятор, по мнению американского ученого Кристофера Монро, это то, что можно запрограммировать под выполнение лишь определенного вида задач и со временем превратить в универсальный квантовый компьютер, когда станет возможно программировать симулятор произвольным образом. Михаил Лукин отмечает, что на данном этапе исследований грань между компьютером и симулятором очень размыта.

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

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

Что останавливает торжество квантовых компьютеров?

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

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

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

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

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

Компьютеры в каталоге Onliner.by

Читайте также:

Наш канал в Telegram. Присоединяйтесь!

Быстрая связь с редакцией: читайте паблик-чат Onliner и пишите нам в Viber!

Перепечатка текста и фотографий Onliner.by запрещена без разрешения редакции. [email protected]

tech.onliner.by


Смотрите также



© 2010- GutenBlog.ru Карта сайта, XML.