задачи для квантового компьютера с ответами

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

Давайте теперь сравним обычный компьютер и квантовый.

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

    a|0> + b|1>, такое, что a^2+b^2=1

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

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

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

Примеры квантовых вентилей:

Есть понятие универсального набора вентилей
, которых достаточно для выполнения любого квантового вычисления. Например, универсальным является набор, включающий вентиль Адамара, вентиль фазового сдвига, вентиль CNOT и вентиль π⁄8. С их помощью можно выполнить любое квантовое вычисление на произвольном наборе кубитов.

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

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

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

Один кубит нам тоже совершенно бесполезен (ну если только в академическом плане),

чтобы производить вычисления нам нужна система кубитов (квантовых объектов)

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

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

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

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

Такая вероятностная природа квантовых вычислений обусловлена самой вероятностной сутью квантового мира. “Бог не играет в кости со вселенной”
, — говорил старик Эйнштейн, но все эксперименты и наблюдения пока (в текущей научной парадигме) подтверждают обратное.

Квантовое вычислительное превосходство.

Википедия дает нам следующее определение квантового вычислительного превосходства:

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

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

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

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

Декогеренция

Описание от N+1
.

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

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

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

На текущий момент время декогеренции в лучших квантовых решениях составляет порядка десятков и сотен микросекунд
.

Есть прекрасный сайт
, на котором можно посмотреть сравнительные таблицы параметров
всех созданных квантовых систем. В эту статью для примера вынесены только два топовых процессора — от IBM IBM Q System One
и от Google Sycamore
. Как мы видим, время декогеренции (Т2) не превышает 200 мкс.

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

Чем нам грозит декогеренция?

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

То есть нам надо:

Инициализировать систему кубитов
Провести вычисление (цепочка вентильных операций)
Считать результат

И сделать все это за 150 мкс. Не успел — результат превратился в тыкву.

Гейт CNOT

Который чаще рисуют в следующем виде:

Верхний кубит называют “управляющим”, второй кубит называют “управляемым”. Смысл гейта следующий:

управляющий кубит проходит без изменений,
управляемый кубит инвертруется, если управляющий кубит в состоянии $|1\rangle$
, либо остается без изменений, если управляющий кубит в состоянии $|0\rangle$

По сути для управляемого кубита это кубит NOT, который включается только если на управляющем кубите 1, и выключен в остальных случаях.

Если задать данное преобразование формулой, то это будет:

ЗАДАЧИ ДЛЯ КВАНТОВОГО КОМПЬЮТЕРА С ОТВЕТАМИ

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

$\left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array} \right) \left( \begin{array}{cccc} \alpha_{00} \\ \alpha_{01} \\ \alpha_{10} \\ \alpha_{11} \end{array} \right) = \left( \begin{array}{cccc} \alpha_{00} \\ \alpha_{01} \\ \alpha_{11} \\ \alpha_{10} \end{array} \right)$

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

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

На управляющий вход гейта подается произвольный кубит в любом произвольном состояни $\alpha_0 |0\rangle + \alpha_{1} |1\rangle$
На управляемый вход подается кубит $|0\rangle$
то есть, другими словами кубит в состоянии $1\cdot |0\rangle + 0\cdot |1\rangle$
Что будет на выходе? Можем решать эту задачу любым удобным способом, например решим ее так. Запишем совместное состояние двух кубитов на входе, где выделим управляющий кубит желтым маркером:

Далее, мы инвертируем управляемый кубит там, где управляющий кубит был равен 1.

Теперь выкинем из ответа те состояния, где амплитуда 0 и остается

$\alpha_0 |00\rangle +\alpha_1 |11\rangle$

А мы знаем по прошлым частям, что такое состояние, это состояние квантовой запутанности. Если мы теперь измерим любой из кубитов и получим, к примеру 0, то после этого второй кубит будет показывать в результате измерения 0 с вероятностью 100%.

Теперь мы научились программно получать такие запутанные состояния с помощью гейта CNOT.

А теперь вспомним о том, что гейты обладают свойством обратимости и применим гейт CNOT к результату повторно. Не будем повторять все выкладки достаточно прочитать все что было раньше в обратном порядке. В итоге мы с помощью этого гейта “распутаем” квантовую запутанность и получим снова два независимых кубита, один из которых в состоянии $|0\rangle$
а другой кубит в состоянии $\alpha_0 |0\rangle + \alpha_{1} |1\rangle$

Задача 1

Построить программу, где на вход подаются два кубита в состояни $|00\rangle$
, а на выходе – запутанное состояние двух кубитов, где состояния $|00\rangle , |11\rangle$
равновероятны.

Выше, мы уже получали запутанное состояние, используя гейт CNOT:

$\alpha_0 |00\rangle +\alpha_1 |11\rangle$

Чтобы состояния были равновероятны, достаточно будет выполнения условия:

$\alpha_0=\alpha_1$

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

$|\alpha_0|^2+|\alpha_1|^2=1$

Данная система тривиальна и дает решение:

$\alpha_0=\alpha_1= \frac{1}{\sqrt{2}}$

То есть по условию задачи, нам нужно получить состояние:

$\frac{1}{\sqrt{2}} |00\rangle +\frac{1}{\sqrt{2}} |11\rangle$

Нам нужно получить такое состояние из двух кубитов, каждый из которых в состоянии $|0\rangle$
.

Чтобы получить такое состояние, используя гейт CNOT, нам надо на управляемый вход подать кубит в состоянии $|0\rangle$
. Здесь ничего делать не надо.

А вот на управляющий кубит нам надо подать состояние

$\frac{1}{\sqrt{2}} |0\rangle +\frac{1}{\sqrt{2}} |1\rangle$

И вопрос, как получить такое состояние из $|0\rangle$
?

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

Таким образом, общая схема программы, решения задачи выглядит так:

Схема получения равновероятных запутанных состояний

Задача 2

Разобрать работу следующей программы:

Два кубита, один в состоянии $|0\rangle$
, другой в состоянии $\alpha_0 |0\rangle + \alpha_{1} |1\rangle$
Кубиты проходят через гейт CNOT, как мы уже знаем, после этого гейта образуется запутанное состояние:

$\alpha_0 |00\rangle +\alpha_1 |11\rangle$

Далее один из кубитов поступает в гейт Адамара, после чего измеряется. Измерение обозначается на схемах в виде такой пиктограммы стрелочного прибора. В процессе измерения измеряемый кубит уничтожается. В каком состоянии окажется второй кубит в итоге работы данной программы?

С гейтом CNOT все уже понятно и разобрано, “отлаживаем” далее программу слева направо.

Какое состояние получится после гейта Адамара можно вычислить двумя способами, разберём оба:

1-ый способ.
Запишем состояние кубита, который поступает в гейт Адамара в виде вектора. Одним компонентом вектора будет множитель, что у кубита при состоянии $|0\rangle$
, а вторым компонентом будет множитель при состоянии $|1\rangle$
. Второй кубит в преобразовании Адамара не участвует, но его состояния также являются частями вектора.

$\alpha_0 |00\rangle +\alpha_1 |11\rangle \rightarrow \left( \begin{array}{cccc} \alpha_0 |0\rangle \\ \alpha_1 |1\rangle \end{array} \right)$

Далее умножим матрицу, которая соответствует преобразованию Адамара, на этот вектор

$\frac{1}{\sqrt{2}}\left( \begin{array}{cccc} 1 & 1 \\ 1 & -1\end{array} \right) \left( \begin{array}{cccc} \alpha_0 |0\rangle \\ \alpha_1 |1\rangle \end{array} \right)=\frac{1}{\sqrt{2}}\left( \begin{array}{cccc} \alpha_0|0\rangle+\alpha_1|1\rangle \\ \alpha_0|0\rangle-\alpha_1|1\rangle \end{array} \right)$

И далее мы возвращаем этот вектор в привычный вид, приписывая к одному компоненту вектора состояние $|0\rangle$
, а ко второму компоненту вектора состояние $|1\rangle$

<img source="\frac{1}{\sqrt{2}}|0\rangle\otimes(\alpha_0|0\rangle+\alpha_1|1\rangle) +\frac{1}{\sqrt{2}}|1\rangle\otimes(\alpha_0|0\rangle-\alpha_1|1\rangle)\quad

” alt=”\frac{1}{\sqrt{2}}|0\rangle\otimes(\alpha_0|0\rangle+\alpha_1|1\rangle) +\frac{1}{\sqrt{2}}|1\rangle\otimes(\alpha_0|0\rangle-\alpha_1|1\rangle)\quad

” src=”https://habrastorage.org/getpro/habr/formulas/f/f6/f6c/f6c7a4da4821b5af72223f3278f10123.svg”>

Можем раскрыть скобки, тогда получится

$\frac{1}{\sqrt{2}}(\alpha_0|00\rangle+\alpha_1|01\rangle+\alpha_0|10\rangle-\alpha_1|11\rangle)$

Это и будет нашим состоянием после применения гейта Адамара.

2-ой способ.
Более аналитический, зато не требует матриц.

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

$|0\rangle\xrightarrow{H}\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$

$|1\rangle\xrightarrow{H}\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$

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

Применяем правила преобразования Адамара к левому кубиту:

$|0\rangle \otimes \alpha_0|0 \rangle+|1\rangle\otimes\alpha_1|1\rangle\xrightarrow{H} \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\otimes \alpha_0|0\rangle+\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\otimes\alpha_1|1\rangle=$

$= \frac{1}{\sqrt{2}}(\alpha_0|00\rangle+\alpha_1|01\rangle+\alpha_0|10\rangle-\alpha_1|11\rangle)$

Приходим к тому же результату, что и в способе 1.

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

Чтобы нагляднее увидеть результат, удобнее пользоваться формулой

Если в процессе измерения кубита получился 0, то “вычеркиваем” из состояния те старшие кубиты, что были в состоянии 1, по оставшемуся кубиту остается состояние

$\alpha_0|0\rangle+\alpha_1|1\rangle$

Вычеркиваем состояние 1, так как процесс измерения дал 0

Если в процессе измерения кубита получился 1, то “вычеркиваем” из состояния те старшие кубиты, что были в состоянии 0, по оставшемуся кубиту остается схожее состояние, но с другой фазой

$\alpha_0|0\rangle-\alpha_1|1\rangle$

Задача 2 решена, но попробуем продолжить построение цепи следующим образом: Допустим в конце цепи из задачи 2 сидит программист и действует следующим образом:

если в результате измерения был 0, то программист ничего не делает
если в результате измерения был 1, то программист к оставшемуся кубиту применяет однокубитный гейт “Инверсия фазы”. Обозначим эту схему следующим способом.

Здесь после измерительного прибора, в зависимости от результата измерения работает, либо не работает еще один гейт “Инверсия фазы”. Если в результате измерения был 1, то оставшийся кубит был в состоянии $\alpha_0|0\rangle-\alpha_1|1\rangle$
. Применяем к нему гейт инверсии фазы, получаем $\alpha_0|0\rangle+\alpha_1|1\rangle$
А это ровно такое же результат какой у нас получался в случае, если бы результатом измерения был 0. Поэтому объединим эти результаты и запишем следующей схемой:

Данную программу назовем программой переноса состояния. Обратите внимание, кубит в произвольном состоянии $\alpha_0|0\rangle+\alpha_1|1\rangle$
поступал на верхний вход программы, а вышел из нижнего. Казалось бы, такая программа не имеет никакого практического смысла. Поступил кубит в произвольном состоянии, и мы очень сложным способом добились того, чтобы получить то же самое, что было на входе. И не ждите подвоха, это правда. Действительно программа не имеет никакого практического смысла. Мы на ней попрактиковались в отладке программ и гейтов. И далее мы еще кое что в ней поменяем, что придаст в новой программе некоторый смысл.

Двухкубитный гейт Адамара

По сути, двухкубитный гейт Адамара, это два гейта Адамара в одной коробке, каждый независимо воздействет на свой кубит.

Давайте попробуем вычислить какие состояния будут получаться у двухкубитного Адамара для состояний: $|00\rangle, |01\rangle, |10\rangle, |11\rangle$
и попробуем построить матрицу 4х4 такого гейта.

$|00\rangle\xrightarrow{H}\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) \otimes\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$

<img source="=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle+|11\rangle)\quad $|0\rangle$ ” alt=”=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle+|11\rangle)\quad $|0\rangle$ ” src=”https://habrastorage.org/getpro/habr/formulas/b/b6/b6b/b6b51e420da3034f52f5ec2a93df4051.svg”>

$|01\rangle\xrightarrow{H}\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\otimes\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$

<img source="= \frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle)\quad $|1\rangle$ ” alt=”= \frac{1}{2}(|00\rangle-|01\rangle+|10\rangle-|11\rangle)\quad $|1\rangle$ ” src=”https://habrastorage.org/getpro/habr/formulas/8/85/85f/85f64a18bf66d7b5346cec3b9ea5c8fd.svg”>

состояние $|10\rangle$
. Почти не отличается от прошлого случая, просто знаки меняются в других местах.

$|10\rangle\xrightarrow{H}\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\otimes\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$

<img source="=\frac{1}{2}(|00\rangle+|01\rangle -|10\rangle – |11\rangle)\quad

” alt=”=\frac{1}{2}(|00\rangle+|01\rangle -|10\rangle – |11\rangle)\quad

” src=”https://habrastorage.org/getpro/habr/formulas/c/c9/c9e/c9e96bcade72dba7f4f443248d5adbdd.svg”>

$|11\rangle\xrightarrow{H}\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\otimes\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$

<img source="= \frac{1}{2}(|00\rangle-|01\rangle-|10\rangle+|11\rangle)\quad

” alt=”= \frac{1}{2}(|00\rangle-|01\rangle-|10\rangle+|11\rangle)\quad

” src=”https://habrastorage.org/getpro/habr/formulas/8/83/836/8362551e5004205a32ad64e2069ffa53.svg”>

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

$\alpha_{00} |00\rangle + \alpha_{01} |01\rangle + \alpha_{10} |10\rangle + \alpha_{11} |11\rangle\equiv\left( \begin{array}{cccc} \alpha_{00} \\ \alpha_{01} \\ \alpha_{10} \\ \alpha_{11} \end{array} \right)$

Отсюда получается, что

$|00\rangle\equiv\left( \begin{array}{cccc} 1 \\ 0 \\ 0 \\ 0 \end{array} \right), |01\rangle\equiv\left( \begin{array}{cccc} 0 \\ 1 \\ 0 \\ 0 \end{array} \right),$

$|10\rangle\equiv\left( \begin{array}{cccc} 0 \\ 0 \\ 1 \\ 0 \end{array} \right), |11\rangle\equiv\left( \begin{array}{cccc} 0 \\ 0 \\ 0 \\ 1 \end{array} \right)$

Теперь переходим к поиску матрицы. Запишем выражение

в векторно-матричном виде

$\left(\begin{array}{cccc} H \end{array} \right)\left( \begin{array}{cccc} 1 \\ 0 \\ 0 \\ 0 \end{array} \right)=\frac{1}{2}\times\left(\begin{array}{cccc} 1 \\ 1 \\ 1 \\ 1 \end{array}\right)$

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

, $\alpha_{00} |00\rangle + \alpha_{01} |01\rangle + \alpha_{10} |10\rangle + \alpha_{11} |11\rangle\equiv\left( \begin{array}{cccc} \alpha_{00} \\ \alpha_{01} \\ \alpha_{10} \\ \alpha_{11} \end{array} \right)$ ,
получаем остальные вертикальные колонки, и, наконец, запишем всю матрицу двухкубитного гейта Адамара:

$\frac{1}{2}\times \left( \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{array} \right)$

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

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

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

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

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

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

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

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

На текущий момент нет полносвязных архитектурных схем из > 6 кубитов
Чтобы на реальном процессоре запутать кубит 0 с, например, 15-м может потребоваться несколько десятков дополнительных операций
Больше операций -> больше ошибок -> сильнее влияние декогерентности

D-Wave

Если коротко (взято из вики):

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

Более подробно можно почитать, например, тут
, тут
(осторожно, может не открываться из России), или у Scott Aaronson
в статье
из его блога
. Кстати, очень рекомендую почитать вообще его блог, там много хорошего материала

Вообще с самого начала анонсов у научного сообщества возникали вопросы к компьютерам D-Wave. Например, в 2014 году IBM поставила под сомнение факт, что D-Wave использует квантовые эффекты.
Дело дошло до того, что в 2015 году Google вместе с NASA купила один из таких квантовых компьютеров и после исследований подтвердила
, что таки да, компьютер работает и вычисляет задачу быстрее, чем обычный. Еще про заявление Google можно почитать тут
и, например, тут
.

Главное, что компьютеры D-Wave, с их сотнями и тысячами кубитов нельзя использовать для вычисления и запуска квантовых алгоритмов. На них нельзя запустить алгоритм Шора, например. Все, что они могут — это используя определенные квантовые механизмы решать определенную задачу оптимизации. Можно считать, что D-Wave это такой квантовый ASIC для конкретной задачи.

Алгоритм Шора.

Наиболее известным квантовым алгоритмом является алгоритм Шора
(придумал в 1994 году английский математик Питер Шор
), который нацелен на решение задачи разложения чисел на простые множители (задача факторизации, дискретного логарифма).

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

На сегодняшний день результаты
более чем скромные. Лучшие результаты факторизации с помощью алгоритма Шора — числа 15
и 21
, что сильно меньше, чем 2048 бит. Для остальных результатов из таблицы применялся иной алгоритм
расчетов, но даже лучший по этому алгоритму результат (291311) сильно далек от реального применения.

Подробнее про алгоритм Шора можно почитать, например, вот тут
. Про практическую реализацию — тут
.

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

Дисклеймер

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

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

Квантовые гейты в случае многокубитных операций

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

$\alpha_{00} |00\rangle + \alpha_{01} |01\rangle + \alpha_{10} |10\rangle + \alpha_{11} |11\rangle$

Требует матрицы размера 4х4 для преобразования одного состояния в другое

$\left( 4х4 \right) \left( \begin{array}{cccc} \alpha_{00} \\ \alpha_{01} \\ \alpha_{10} \\ \alpha_{11} \end{array} \right) = \left( \begin{array}{cccc} \alpha_{00} \\ \alpha_{01} \\ \alpha_{10} \\ \alpha_{11} \end{array} \right)$

И далее все нарастает экспоненциально, преобразование трехкубитного состояния требует матрицы 8х8 и так далее.

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

Рассмотрим самые важные и частоиспользуемые гейты.

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

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

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

В квантово-механической системе нет такой четкости, а есть вероятность, которая определяет ее суть. Правильный вопрос здесь — какова вероятность, что тарелки разбились или целы, какова вероятность, что значения регистра 0 или 1?

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

На классическом уровне неопределенность маскирует наше незнание. Например, когда мы покупаем лотерейный билет «Спортлото», для нас появляется вероятность выиграть, потому что мы не знаем выигрышный номер.

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

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

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

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

«Память» квантового компьютера

В чем основная разница между квантовой и классической памятью компьютера? В обычном компьютере мы записываем числа в двоичном коде. Например, число 8 в двоичной системе выглядит как 00001000, и для его записи достаточно 4 битов.

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

На практике у методов измерения ограниченная точность. Будем считать, что она соответствует обычной машинной (float). Получается, что кубит содержит два числа: вероятности, что кубит в состоянии 0 и в состоянии 1.

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

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

Квантовый компьютер экспоненциально лучше обычного.

Один кубит это 2 вещественных числа. Два кубита — 4 вещественных числа. Но восемь кубитов это 256 потенциальных конфигураций
восьми нулей и единиц — два в восьмой степени.

Для одного кубита выигрыш в 128 раз, а для восьми кубитов он существенно больше — 256*128. Система n кубитов в памяти эквивалентна $inline$
вещественных чисел.

Емкость квантовой памяти растет в геометрической прогрессии.

Память обычного ноутбука эквивалентна 15 кубитам, 40 кубитов равны памяти самых мощных вычислительных центров, а 50-60 кубитов превышают суммарную память всех вычислительных центров всего мира.

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

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

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

Если квантовый мир работает на уровне неопределенности, как вообще возможно что-то посчитать? У квантовой механики вероятностная природа, а нам нужен точный ответ. Как все будет работать, если нужно просто перемножить два числа?

Объясню на примере задач класса NP
, то есть задач разрешимости, решение которых невозможно найти за полиномиальное время — во всяком случае, в предположении $P\neq NP$
. Однако, правильность решения за полиномиальное время проверить можно. Это похоже на взлом закрытого замка: мы не умеем пользоваться отмычками, но можем быстро проверить любой ключ, если он есть.

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

Если окажется, что ответ неверен, запустим квантовый компьютер еще раз. Вероятность получения правильного ответа больше 50%, а часто гораздо больше. Значит, за 2-4 запуска квантового алгоритма мы получим правильный ответ.

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

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

У классического компьютера два параметра качества: объем памяти и количество операций. С обычным компьютером мы по умолчанию предполагаем, что у нас есть доступ ко всем ячейкам памяти для записи и чтения.

В квантовом случае есть три параметра.

Объем памяти или количество кубит
. Чем больше памяти, тем лучше? Для квантового компьютера нет — когда мы увеличиваем количество кубит, растет сложность квантовой системы. Систему становится тяжело поддерживать в изолированном состоянии.

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

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

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

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

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

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

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

Немного об эмуляции квантовых компьютеров

Квантовые вычисления можно эмулировать на обычном компьютере. Ведь действительно, смотрите
:

Состояние кубита можно представить
комплексным числом
, занимающим от 2х32 до 2х64 бита (8-16 байт) в зависимости от архитектуры процессора
Состояние N связанных кубитов можно представить в виде 2^N комплексных чисел, т.е. 2^(3+N) для 32-х битной архитектуры и 2^(4+N) для 64-х битной.
Квантовую операцию над N кубитами можно представить матрицей 2^N x 2^N

Для хранения эмулируемых состояний 10 кубитов нужны 8 КБ
Для хранения состояний 20 кубитов нужны 8 МБ
Для хранения состояний 30 кубитов нужны 8 ГБ
Для хранения состояний 40 кубитов нужны 8 Терабайт
Для хранения состояний 50 кубитов нужны 8 Петабайт и т.д.

Для сравнения, Summit
( Top-1 из Top-500
) несет на себе всего 2.8 Петабайт памяти.

Текущий рекорд симуляций
— 49 кубит поставленный в прошлом году на крупнейшем китайском суперкомпьютере ( Sunway Taihu Light
)

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

По операциям — для точной эмуляции схемы на 49 кубитов из каких-то 39 “тактов” (независимых слоев вентилей) потребовалось
2^63 комплексных умножений — 4 Пфлопс суперкомпьютера на протяжении 4 часов

Эмуляция квантового компьютера из 50+ кубит на классических системах считается невыполнимой за разумное время. В том числе из-за этого факта Google использовал для своего эксперимента с квантовым превосходством процессор с 53-мя кубитами.

Ошибки

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

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

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

Вычислительные ошибки гейтов
— любая операция (вентиль) над кубитами может с некоторой вероятностью завершиться с ошибкой, а нам для реализации алгоритма нужно выполнить сотни вентилей, вот и представьте, что мы получим в конце выполнения нашего алгоритма. Классический вариант ответа на вопрос — “Какова вероятность встретить динозавра в лифте?” — 50х50, или встретишь или нет.

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

Но тут возникает другая проблема — общее количество кубитов
. Смотрите, допустим у нас есть процессор со 100 кубитами, из которых 80 кубитов заняты коррекцией ошибок, тогда нам для вычислений остается только 20.

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

На том же сайте
есть сравнительные таблицы процессоров по уровням ошибок. Для сравнения возьмем те же процессоры, что и в предыдущем примере — IBM IBM Q System One
и Google Sycamore
:

Здесь фиделити
— мера схожести двух квантовых состояний. Величину ошибки можно грубо представить как 1-Fidelity. Как мы видим, ошибки на 2-х кубитных гейтах и ошибки считывания являются главным препятствием к выполнению сложных и длинных алгоритмов на существующих квантовых компьютерах.

Еще можно почитать роадмап от 2016
года от NQIT
по решению задачи коррекции ошибок.

Заявление Google о достижении квантового превосходства

54-кубитный процессор Sycamore

Итак, в октябре 2019 года разработчики Google опубликовали в научном издании Nature статью « Квантовое превосходство с применением программируемого сверхпроводящего процессора
». Авторы объявили о достижении впервые в истории квантового превосходства с помощью 54-кубитного процессора «Sycamore».

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

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

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

Что же в реальности сделал Google? Для детального понимания почитайте Ааронсона, а кратко вот:

Создается случайная схема длиной 20 из 53 кубитов используя вентили
Схема запускается с начальным состоянием [0.0] на выполнение
Выход схемы представляет собой случайную битовую строку (семпл)
Распределение результата не является случайным (интерференция)
Распределение полученных семплов сравнивается с ожидаемым
Делается вывод о квантовом превосходстве

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

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

Резюме

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

Развитие квантовых вычислений позволит (когда-нибудь) решать задачи:

Моделирования сложных физических систем на квантовом уровне
Нерешаемые на обычном компьютере из-за вычислительной сложности

Основные проблемы при создании и эксплуатации квантовых компьютеров:

Декогеренция
Ошибки (декогеренции и вентильные)
Архитектура процессоров (полносвязные схемы кубитов)

Состояние дел на текущий момент:

По факту — самое начальное R&D
.
РЕАЛЬНОЙ коммерческой эксплуатации еще нет (и непонятно, когда будет)

Что может помочь:

Какое-то физическое открытие, снижающее затраты на обвязку и эксплуатацию процессоров
Открытие чего-то, что на порядок увеличит время декогеренции и/или снизит число ошибок

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

Ну а пока — нарабатываем опыт в квантовом программировании, собираем и создаем квантовые алгоритмы, тестируем идеи и прочее и прочее. Ждем прорыва.

Что значит квантовая революция для IT-индустрии

Пока что ничего. Мы находимся в так называемой эре NISQ — Noisy Intermediate-Scale Quantum technology
. Это значит, что сейчас нет таких квантовых устройств, которые могли бы соперничать с классическими компьютерами. Пока нельзя создать квантовую систему, которая по всем параметрам превзойдет классическую: достаточно небольшую, универсальную и изолированную. Пока получаются только системы, которые выполняют узкоспециальные задачи определенного сорта лучше, чем вычислительный кластер. Квантовые технологии пока непрактичны. Хотелось бы использовать этот огромный потенциал для своих ежедневных задач, но неизвестно, как это сделать.

У квантовых технологий огромный «подрывной потенциал». Если научиться хорошо решать хотя бы одну из оптимизационных задач, о которых говорилось выше, это изменит одну конкретную индустрию, как минимум. Надеюсь, что через 5-10 лет в некоторых направлениях ситуация изменится.

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

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

То, с каким интересом участники HighLoad++ восприняли доклад о квантовых компьютерах и АЭС
, натолкнуло нас на мысль уделить большее внимание подобным темам на наших конференциях. Поэтому на РИТ++
в мае в онлайне
у нас будут секции научпопа и применения IT в смежных областях. И это только малая часть новинок фестиваля «Российские интернет-технологии» — подробнее смотрите на сайте и в рассылке
.

Прототипы

Выделю три прототипа, над которыми работают крупные компании. Google, IBM, Intel, Microsoft вкладываются в развитие квантовых компьютеров. Все вместе они вложили больше 500 млн долларов в разработку, лаборатории и исследовательские центры.

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

Универсальные квантовые компьютеры

Это универсальные машины от Google и IBM с памятью примерно 20 кубит.
Они выполняют любые операции, потому что полная универсальность доступна с относительно небольшим числом кубитов, дальше возникает практическое ограничение. Возможно, через год люди научатся работать с 30-40 кубитами.

Универсальные квантовые компьютеры способны реализовать произвольные квантовые алгоритмы, например, алгоритмы Шора и Гровера.

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

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

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

Другим примером, демонстрирующим потенциал квантовых вычислений, является Алгоритм Гровера
для задачи перебора или поиска решения уравнения $inline$
, где $inline$
какая-то сложная функция.

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

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

Квантовые симуляторы ограниченной универсальности

Это другое направление: универсальность ограничивается, но поддерживается изоляция (когерентность). Это компьютеры на рубеже в 50-70 кубитов, что в смысле памяти уже больше, чем любой суперкомпьютер.

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

В октябре 2019 Google заявил, что достиг квантового превосходства. Новость появилась во всех ведущих газетах и журналах, соответствующая научная статья была опубликована в Nature. Тематические статьи выпустили многие газеты, даже New York Times и Wall Street Journal, которые далеки от науки.

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

Некогерентные процессоры с числом кубитов от 2 тысяч

Если забыть про универсальность и когерентность, можно добавлять 2 или даже 3-4 тысячи кубитов. Этим направлением занимается компания D-Wave из Канады. У них есть процессоры с тысячей кубитов, но без когерентности.

Направления развития

На текущий момент (могу ошибаться, поправьте) основные усилия (и более-менее значимые результаты) у всех ведущих игроков сосредоточены на двух направлениях:

Специализированные квантовые компьютеры
, которые направлены на решение одной конкретной специфической задачи, например, задачи оптимизации. Примером продукта являются квантовые компьютеры D-Wave.
Универсальные квантовые компьютеры
— которые способны реализовать произвольные квантовые алгоритмы (Шора, Гровера, и т.д.). Реализации от IBM, Google.

Прочие же вектора развития, которые дает нам квантовая физика, такие как:

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

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

Дополнительно можно почитать дорожную карту развития квантовых технологий
, ну и гуглите “ развитие квантовых технологий
”, например, вот
, вот
и вот
.

Пути решения проблем

Для решения вышеуказанных проблем, в настоящее время используют следующие подходы и методы:

Использование криокамер с низкими температурами (10 мК (–273,14°C))
Использование максимально защищенных от внешних воздействий процессорных блоков
Использование систем квантовой коррекции ошибок (Логический кубит)
Использование оптимизаторов при программировании схем для конкретного процессора

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

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

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

Наиболее известные на сегодняшний день алгоритмы это:

В отличие от классических, квантовые компьютеры не универсальны.
До сих пор найдено лишь небольшое число квантовых алгоритмов. (С)

Спасибо oxoron
за ссылку на Quantum Algorithm Zoo
, место, где, по уверениям автора ( “Stephen Jordan”
), собраны и продолжают собираться лучшие представители квантово-алгоритмического мира.

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

Про урокцифры: AGENT ARMORY SW ЧТО ЭТО ЗА ПРОГРАММА

задачи для квантового компьютера с ответами

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

Квантовое вычислительное превосходство.

Декогеренция

Гейт CNOT

Задача 1

Задача 2

Двухкубитный гейт Адамара

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

D-Wave

Алгоритм Шора.

Дисклеймер

Квантовые гейты в случае многокубитных операций

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

«Память» квантового компьютера

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

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

Немного об эмуляции квантовых компьютеров

Ошибки

Заявление Google о достижении квантового превосходства

Оглавление

Резюме

Что значит квантовая революция для IT-индустрии

Прототипы

Универсальные квантовые компьютеры

Квантовые симуляторы ограниченной универсальности

Некогерентные процессоры с числом кубитов от 2 тысяч

Направления развития

Пути решения проблем

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

Добавить комментарий Отменить ответ