Как работают квантовые компьютеры. Собираем паззл


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


А недавно ко мне подошли коллеги и спросили “Ты понимаешь как работает квантовый компьютер? Можешь нам рассказать?” И тут я понял, что проблема со складыванием в голове целостной картинки есть не только у меня.


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



Оглавление




Дисклеймер


(к оглавлению)


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


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



Введение


(к оглавлению)


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



Как все начиналось


(к оглавлению)



Точкой отсчета квантовой эры принято считать 1900 год, когда М. Планк впервые выдвинул гипотезу о том, что энергия испускается и поглощается не непрерывно, а отдельными квантами (порциями). Идею подхватили и развили многие выдающиеся ученые того времени — Бор, Эйнштейн, Гейзенберг, Шредингер, что, в конечном счете, привело к созданию и развитию такой науки как квантовая физика. Про становление квантовой физики как науки в Сети есть много хороших материалов, в этой статье мы не будем подробно останавливаться на этом, но указать дату, когда мы вошли в новую квантовую эпоху, было необходимо.


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


Википедия указывает на то, что первым идею квантовых вычислений высказал в 1980 году наш ученый Юрий Манин. Но реально заговорили о ней только в 1981, когда небезызвестный Р. Фейнман в докладе на первой конференции по физике вычислений, проведенной в Массачусетском технологическом институте, отметил, что невозможно моделировать эволюцию квантовой системы на классическом компьютере эффективным способом. Он предложил элементарную модель квантового компьютера, который будет способен провести такое моделирование.


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


Основные вехи в истории создания квантовых компьютеров:



Как вы видите прошло 17 лет (с 1981 до 1998) с момента идеи до ее первой реализации в компьютере с 2-мя кубитами, и 21 год (с 1998 до 2019) до момента, когда количество кубитов увеличилось до 53-х. Потребовалось 11 лет (с 2001 до 2012) чтобы улучшить результат выполнения алгоритма Шора (мы остановимся на нем подробнее чуть далее) с числа 15 до 21. Также только три года назад мы подошли к тому, чтобы реализовать то, о чем говорил Фейнман, и научиться моделировать простейшие физические системы.


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



Ведущие игроки


(к оглавлению)



Слайды для этого раздела взяты из статьи Квантовый компьютер: большая игра на повышение. Лекция в Яндексе, от научного сотрудника Российского квантового центра Алексея Фёдорова. Позволю себе прямые цитаты:


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



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


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



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


(к оглавлению)



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


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

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



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


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



Основы. Квантовый объект и квантовые системы


(к оглавлению)



Самое главное, что надо понять из этого раздела, это то, что


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

Что же такое квантовый объект?


Квантовый объект — объект микромира (квантового мира), который проявляет квантовые свойства:

  • Имеет определенное состояние с двумя граничными уровнями
  • Находится в суперпозиции своего состояния до момента измерения
  • Запутывается с другими объектами для создания квантовых систем
  • Выполняет теорему о запрете клонирования (нельзя скопировать состояние объекта)

Разберем каждое свойство более подробно:


Имеет определенное состояние с двумя граничными уровнями (конечное состояние)

Классический пример из реального мира — монета. У нее есть состояние “сторона”, которая принимает два граничных уровня — “орел” и “решка”.


Находится в суперпозиции своего состояния до момента измерения

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


Запутывается с другими объектами для создания квантовых систем

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


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

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



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


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


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

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


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


Квантовая система — система запутанных квантовых объектов, обладающая следующими свойствами:

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

(и, забегая чуть вперед)


Следствие для квантовых программ:

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



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


(к оглавлению)



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


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

Логика


0 / 1
`a|0> + b|1>, a^2+b^2=1`

Физика


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

Носитель инф.


Уровни напряжения
Поляризация, спин,…

Операции


NOT, AND, OR, XOR над битами
Вентили: CNOT, Адамара,…

Взаимосвязь


Полупроводниковый чип
Запутанность между собой

Алгоритмы


Стандартные (см. Кнут)
Специальные (Шор, Гровер)

Принцип


Цифровой, детерминированный
Аналоговый, вероятностный

Логический уровень


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


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


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

a и b при этом представляют собой амплитуды вероятностей, а квадраты их модулей — собственно вероятности получить именно такие значения граничных состояний |0> и |1>, если схлопнуть кубит измерением прямо сейчас.


Физический уровень


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


Носитель информации


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


Операции


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


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


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


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


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

Взаимосвязь


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


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


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

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


Алгоритмы


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



Принцип


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


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

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



Физические реализации кубитов


(к оглавлению)



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


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

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



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


Ну и еще почитайте обзор возможных физических реализаций кубитов от Andrew Daley,2014.



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


(к оглавлению)



Материалы для данного раздела (задача и картинки) взяты из статьи “Просто о сложном. Как работает квантовый компьютер”.


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


Есть группа из трех человек: (А)ндрей, (B)олодя и (С)ережа. Есть два такси (0 и 1).


Известно также, что :


  • (А)ндрей, (B)олодя — друзья
  • (А)ндрей, (С)ережа — враги
  • (B)олодя и (С)ережа — враги

Задача: Разместить народ по такси так, чтобы Max(друзья) и Min(враги)


Оценка: L = (кол-во друзей) — (кол-во врагов) для каждого варианта размещения


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



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


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


У нас 2 возможных варианта размещения (такси 0 и такси 1) и 3 человека. Пространство решений 2^3 = 8. Перебрать 8 вариантов можно даже на калькуляторе, это не проблема. А теперь усложним задачу — у нас 20 человек и два автобуса, пространство решений 2^20 = 1 048 576. Тоже ничего сложного. Увеличим количество людей в 2.5 раза — возьмем 50 человек и два поезда, пространство решений теперь 2^50 = 1.12 x 10^15. У обычного (супер)компьютера уже начинаются серьезные проблемы. Увеличим кол-во людей в 2 раза, 100 человек дадут нам уже 1.2 x 10^30 возможных вариантов.


Все, за разумное время эту задачу не посчитать.



Подключаем суперкомпьютер


Самый мощный компьютер в настоящее время — номер 1 из Top500, это Summit, производительностью 122 Пфлопс. Предположим, что на расчет одного варианта нам достаточно 100 операций, тогда для решения задачи для 100 человек нам потребуется:


(1.2 x 10^30 100) / 122x10^15 / (606024365) = 3 х 10^37 лет.


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


Есть ли альтернативы? Как вы уже догадались, таки да, есть.


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



Совсем немного комбинаторики, теории вероятностей и странного экспериментатора


Возьмем мешок и положим в него 1000 белых и 1000 черных шаров. Будем проводить эксперимент — вынимать шар, записывать цвет, возвращать шар в мешок и перемешивать шары в мешке.


Провели эксперимент 10 раз, вытащили 10 черных шаров. Возможно? Вполне. Дает нам эта выборка какое-то разумное понятие об истинном распределение в мешке? Очевидно, что нет. Что надо сделать — правильно, повторить эксперимент миллион раз и рассчитать частоты выпадения черных и белых шаров. Получим, например 49.95% черных и 50.05% белых. В этом случае уже более-менее понятна структура распределения из которого мы семплируем (вынимаем один шарик).


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


Добавим в наш мешок 10 красных и 10 зеленых шаров (ошибки). Повторим эксперимент 10 раз. Вытащили 5 красных и 5 зеленых. Возможно? Да. Можем что-то сказать об истинном распределении — Нет. Что надо сделать — ну вы поняли.


Для получения понимания о структуре вероятностного распределения надо многократно просемплировать единичные исходы из этого распределения и усреднить результаты.

Связываем теорию с практикой


Теперь вместо черных и белых шаров давайте возьмём бильярдные шары, и положим в мешок 1000 шаров с номером 2, 1000 с номером 7 и 10 шаров с другими номерами. Представим себе экспериментатора, который обучен простейшим действиям (достать шар, записать номер, положить шар обратно в мешок, перемешать шары в мешке) и делает он это за 150 микросекунд. Ну такой экспериментатор на спидах (не реклама наркотиков!!!). Тогда за 150 секунд он сможет провести наш эксперимент 1 миллион раз и предоставить нам результаты усреднения.


Усадили экспериментатора, дали мешок, отвернулись, подождали 150 секунд — получили:


номер 2 — 49.5%, номер 7 — 49.5%, остальные номера в сумме — 1%.


Да, все верно, наш мешок — это квантовый компьютер с алгоритмом, решающим нашу задачу, а шары — возможные варианты решения. Поскольку правильных решений два, то квантовый компьютер будет выдавать нам равновероятно любое из этих возможных решений, и 0.5% (10/2000) ошибок, о которых мы поговорим позднее.


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

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


Теперь представим себе, что для задачи, в которой участвуют 100 человек (пространство решений 2^100 мы помним об этом), правильных решений тоже только два. Тогда, если взять 100 кубитов и написать алгоритм, вычисляющий нашу целевую функцию (L, см. выше) над этими кубитами, то мы получим мешок, в котором будет 1000 шаров с номером первого правильного ответа, 1000 с номером второго правильного ответа и 10 шаров с другими номерами. И наш экспериментатор за те же 150 секунд выдаст нам оценку вероятностного распределения правильных ответов.


Время выполнения квантового алгоритма (с некоторыми допущениями) можно считать константным О(1) по отношению к размерности пространства решений (2^N).

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



Кубит и параллельные миры


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


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


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


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


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

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


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


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



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


(к оглавлению)



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


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



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

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


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



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


(к оглавлению)


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


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


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



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


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



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


(к оглавлению)


Алгоритм Гровераквантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения F(X) = 1, где F — есть булева функция от n переменных. Был предложен американским математиком Ловом Гровером в 1996 году.


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


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


Алгоритм Гровера. Представьте, что у вас имеется N штук пронумерованных закрытых коробок. Они все пустые кроме одной, в которой находится мячик. Ваша задача: узнать номер коробки, в которой находится мячик (этот неизвестный номер часто обозначают буквой w).


Как решать эту задачу? Самым тупым способом, по очереди открывать коробки, и рано или поздно вы наткнетесь на коробку с мячиком. А сколько в среднем коробок нужно проверить до того, как будет обнаружена коробка с мячиком? В среднем нужно открыть примерно половину коробок N/2. Главное здесь то, что если мы увеличим число коробок в 100 раз, то в те же 100 раз увеличится и среднее число коробок, которые нужно открыть до того, как будет найдена коробка с мячиком.


Теперь сделаем ещё одно уточнение. Пусть мы не сами открываем коробки руками и проверяем наличие мячика в каждой, а имеется некий посредник, назовем его Оракул (Oracle). Мы говорим Оракулу — «проверь коробку номер 732», и Оракул честно проверяет и отвечает «в коробке номер 732 мячика нет». Теперь вместо слов о том, сколько коробок нам нужно в среднем открыть, мы говорим «сколько раз в среднем мы должны обратиться к Оракулу для того, чтобы найти номер коробки с мячиком»


Оказывается, что если перевести эту задачу с коробками, мячиком и Оракулом на квантовый язык, то выходит замечательный результат: для поиска номера коробки с мячиком среди N коробок нам нужно потревожить Оракула всего примерно SQRT(N) раз!


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



Алгоритм Дойча-Йожи


(к оглавлению)


Алгоритм Дойча — Йожи (упоминается также как алгоритм Дойча — Джозы) — [квантовый алгоритм](https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B9%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC), предложенный Давидом Дойчем и Ричардом Йожей в 1992 году, и ставший одним из первых примеров алгоритмов, предназначенных для выполнения на квантовых компьютерах. _


Задача Дойча — Йожи заключается в определении, является ли функция нескольких двоичных переменных F(x1, x2, … xn) постоянной (принимает либо значение 0, либо 1 при любых аргументах) или сбалансированной (для половины области определения принимает значение 0, для другой половины 1). При этом считается априорно известным, что функция либо является константой, либо сбалансирована. (С)


Еще можно почитать тут. Более простое объяснение:


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



Проблемы квантовых компьютеров


(к оглавлению)



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


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

Крайне рекомендую прочитать статью “Характеристики квантовых компьютеров”, особенно комментарии к ней.


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



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


(к оглавлению)



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


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


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


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

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


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


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


Computer Name
N Qubits
Max paired
T2 (мкс)
IBM Q System One
20
6
70
Google Sycamore
53
4
~150-200

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


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

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


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

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


Но это еще не все...



Ошибки


(к оглавлению)



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


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

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


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


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


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


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


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


Computer
1-Qubit Gate Fidelity
2-Qubit Gate Fidelity
Readout Fidelity
IBM Q System One
99.96%
98.31%
Google Sycamore
99.84%
99.38%
96.2%

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


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



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


(к оглавлению)



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


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


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


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


Computer Name
N Qubits
Max paired
T2 (мкс)
IBM Q System One
20
6
70
Google Sycamore
53
4
~150-200

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



Итак:


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



Итоги


(к оглавлению)


Декогеренция — прокрустово ложе современных квантовых вычислений. В 150 мкс мы должны уложить все:


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

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


We measure a qubit coherence time in excess of 0.5 s, and with magnetic shielding we expect this to improve to be longer than 1000 s


Про эту технологию еще можно почитать здесь или, например, здесь.


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


Ну и, наконец, современные архитектуры не позволяют с минимальными затратами реализовать схемы запутанности лучше, чем 1 к 4 или 1 к 6.



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


(к оглавлению)


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


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

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



D-Wave


(к оглавлению)



2000-кубитный компьютер D-Wave 2000Q. Источник: D-Wave Systems


На фоне заявления Google о достижении квантового превосходства используя процессор с 53-мя кубитами, компьютеры и анонсы от компании D-Wave, в которых число кубитов исчисляется тысячами, несколько сбивает с толку. Ну действительно, если 53 кубита смогли достичь квантового превосходства, то на что же способен компьютер с 2048 кубитами? Но не все так хорошо...


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


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

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


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


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


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


(к оглавлению)



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


  • Состояние кубита можно представить комплексным числом, занимающим от 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-мя кубитами.


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


(к оглавлению)



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


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

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


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


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



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


(к оглавлению)



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


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


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

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


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


Ну и, конечно, Scott Aaronson в своем блоге не смог обойти своим вниманием это заявление. Его анализ вместе со всеми ссылками и Scott’s Supreme Quantum Supremacy FAQ! как обычно стоят того, чтобы потратить на них свое время. На хабре есть перевод этого FAQ, и обязательно почитайте комментарии, там есть ссылки на предварительные документы, утекшие в Сеть до официального объявления.


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


Я могу, конечно, вам сказать, но чувствую себя при этом глуповато. Вычисление такое: экспериментатор генерирует случайную квантовую схему С (т.е. Случайную последовательность 1-кубитных и 2-кубитных — между ближайшими соседями — вентилей, с глубиной к примеру в 20, действующую на 2D сеть n=50-60 кубитов). После этого экспериментатор посылает С на квантовый компьютер, и просит его применить С к начальному состоянию из 0, измерить результат в базисе {0,1}, послать обратно n-битную наблюдаемую последовательность (строку) и повторить несколько тысяч или миллионов раз. Наконец, используя свое знание о С, экспериментатор проводит статистическую проверку на соответствие результата с ожидаемым выходом от квантового компьютера.



Совсем коротко:


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

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

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



Резюме


(к оглавлению)


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

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


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

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


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

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


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

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


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

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


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



Заключение


(к оглавлению)


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


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


Спасибо за внимание, надеюсь эта статья будет кому-нибудь полезной.


(С) Kruegger



Благодарности


(к оглавлению)



@Oxoron за вычитку и замечания по исходному тексту, а также за статью “Характеристики квантовых компьютеров”


@a5b за информационно-насыщенные комментарии к “Характеристики квантовых компьютеров”, да и не только к ней, которые во многом помогли мне разобраться с этим пазлом.


Всем авторам статей и публикаций, материалы которых были использованы при написании этой статьи.



Список ресурсов


(к оглавлению)





Неотсортированные (но не менее интересные) статьи с просторов Сети

Средняя зарплата в IT

120 000 ₽/мес.
Средняя зарплата по всем IT-специализациям на основании 3 502 анкет, за 1-ое пол. 2021 года Узнать свою зарплату
Реклама
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее

Комментарии 101

    0
    И тебе привет) Спасибо за пост.
      +1

      Все равно нихрена непонятно :-(


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


      Пока виден только один смысл — взломать шифрование быстрее, пока не взломали другие.

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

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

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

              del

              0
              Насколько я понял, многие задачи связанные с оптимизацией. То есть те кот. решаются сегодня перебором. К примеру, решение задачи TSP(Travelling salesman problem) Поиск кратчайшего/ оптимального маршрута позводит сэкономить кучу денег на производствах, передвижении, той же экологии. Куча добра :)
                +1

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

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

                    Чтоб придумать алгоритм — железо не требуется. Шор и Гровер свои алгоритмы выдумали в 90х, когда о каком-либо железе даже и не мечтали. Но вот прошло 30 лет, а воз и ныне там.

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

                          А зачем разрабатывать железо для чего-то, что не имеет ценности? Ценность классических вычислительных машин была понятна и ясна еще во времена Беббиджа, а то и раньше. А вот зачем вкладывать деньги в разработку квантовых машин? Зачем они? Что они нам дадут?


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


                          Даже в науке спрос рождает предложение.

                            0
                            Во первых КК — это инвестиция. Кто первый освоит технологию, тот и применение найдет и бизнес выстроит.
                            Может как пример не слишком удачный, но все же — Ipad. При выходе не особо было понятно насколько этот девайс будет удобным и полезным. Тем не менее рынок он взял, аудиторию создал и ПО написали в достаточном количестве. Далее уже и другие производители подтянулись.
                              0
                              Я не думаю, что при создании первой микросхемы (в начале 60х) думали о том, что компьютеры станут персональными, а люди будут общаться в «социальной сети», создавшая которую компания будет стоить $520 млрд.
                  0
                  Медицина. К примеру симуляция сворачиваемости белков.
                +1
                А как же симуляция? уже сегодня на этом нашли кучу материалов, да и ранее, тот же графен.

                P.S. Спасибо за статью, самое понятное объяснение что я видел.
                  0
                  Спасибо. А можно ссылки на эти результаты? Мне они не попадались, к сожалению.
                  UPD: Увидел от Shkaff выше, ушел читать…
                0
                Крю, отличная статья! Утащил себе) Жду продолжение, особенно отличие IBM и Google в считывании результатов с КК.
                  0
                  Отличная статья! Спасибо!
                    +1
                    Очень большое спасибо. Давно слежу за темой, естественно как полнейший профан, но гик.
                    Статья очень хорошо написана. С одной стороны от А до Я, с другой стороны доступным языком и избегания излишнего углубления в детали. Опять же, для всех у кого возникают вопросы, большое количество ссылок по любой связанной теме.
                    Спасибо!
                      +3
                      Спасибо. Именно такого результата и планировалось достичь. Рад, если мне это все-таки удалось )
                      +2
                      Присоединяюсь к остальным поблагодарившим. Это впервые когда я осилил статью по этой теме и картинка действительно прояснилась.
                      Но меня как и раньше мучает вопрос и я впервые решаюсь его задать: что за штуковина на КДПВ? почему она больше напоминает что-то из мира стимпанка нежели что-то из мира електроники?
                        0
                        Спасибо. По поводу картинки — ну это и есть сам виновник торжества — квантовый компьютер. Вот тут можно посмотреть и почитать поподробнее. Насколько я понимаю, мы видим каскадные охладители, а чуть ниже (на КДПВ не влезло) расположена капсула с собственно процессором.

                        From top to bottom, the system gradually cools from four Kelvin — liquid-helium temperatures — to 800 milliKelvin, 100 milliKelvin and, finally, 10 milliKelvin. Inside the canister, that's 10 thousandths of a degree above absolute zero. The wires, meanwhile, carry RF-frequency signals down to the chip.


                        Могу в чем-то ошибаться, физическое устройство (и современные реализации) квантовых установок глубоко не прорабатывал.
                          +1
                          Дополню немного: на картинке криостат растворения , в нем есть несколько стадий охлаждения (как описано) — каждая золотистая плита охлаждается до определенной температуры. По закрученным трубочкам проходят провода.
                        0
                        Видно, что начиная с середины и до конца статья писалась наспех. Вначале все описано просто и доступно раскрываются вводные аргументы по субъекту статьи. А потом, просто ссылки — алгоритм Шора просто обозначили и нечего не описали, только лишь ссылки выдали. Тут же следом, красиво описали остальные два алгоритма.

                        После этого делайте часто странные выводы: мол нет реальной коммерческой реализации, но за минуту до этого пишите, что Гугл купил у D Wave один образец для проверки. Короче такого по мелочам много в статье. А ещё пишите, мол мешок — это и есть квантовый комп:
                        Да, все верно, наш мешок — это квантовый компьютер с алгоритмом, решающим нашу задачу, а шары — возможные варианты решения. Поскольку правильных решений два, то квантовый компьютер будет выдавать нам равновероятно любое из этих возможных решений, и 0.5% (10/2000) ошибок, о которых мы поговорим позднее.

                        Нет, мешок это вводное условие, а компьютер — это аппарат исполняющий вычислительные действия над «мешком»)

                        Однако в целом почитать интересно и полезно.
                          0

                          Насчёт квантового превосходства не совсем понял…
                          -Распределение полученных семплов сравнивается с ожидаемым


                          Значит они как то посчитали какая интерференция должна быть на выходе, что бы сравнивать с полученной с КК. Тогда где превосходство?

                            +2
                            Наколько я понял, Google сначала провел несколько итераций с меньшим количеством кубитов (до ~50), проэмулировал схему на своих кластерах, провел статистические тесты — и убедился, что сэмулированное распределение совпадает с полученным от КК.

                            Потом они запустили схему на 53-х кубитном КК, получили результат и сказали — «кто хочет — проверяйте».

                            Вот тут, в ответе B6, Ааронсон раскрывает этот метод более подробно. В оригинальной статье это параграф "The classical computational cost".

                            Эксперты — поправьте, если где ошибся.
                            0

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


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


                            Как верить остальному?

                              +2
                              «Полупроводниковый транзистор» — это тавтология

                              Нет, не тавтология!
                              Тёплый ламповый транзистор 1908 года — задолго до полупроводников.
                              image
                              Классический тёплый ламповый двойной транзистор.
                              image
                              Были ещё транзисторы на пневматике и гидравлике.
                              Можно при желании извратнуться и создать механический транзистор, или на реле.
                              Смутила следующая фраза: «физической реализацией бита для обычного компьютера выступает полупроводниковый транзистор… .»

                              *фейспалм*
                              Про тёплые ламповые компьютеры никогда не слышали?
                              А про компьютеры на реле? На пневматике? На гидравлике?
                              Про первый компьютер от Чарльза Бэбиджа на механике — уж точно никогда не слышали?

                              И про то что ENIAC (Electronic Numerical Integrator and Computer) не имел полупроводников — для вас тоже новость?
                              image

                              PS во что превратился Хабр, если гумантиарии тут вопрошают «Как верить остальному?» *дабл-фейспалм*
                                +3

                                Лампа — не транзистор, в том-то и дело. Транзистор обязательно полупроводниковый.


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


                                Я недавно на Хабре, но тут, скорей, не хватает статей по обычным компьютерам, чем по квантовым.

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

                                  Но я считаю, что на лампе можно реализовать все упомянутые свойства.
                                    0

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

                                      0
                                      В современной электронике они действительно из п/п делаются.
                                      Я вот слабо представляю, как на ламповых транзисторах реализовать задачи вроде «разложение числа 15 на множители».
                                        0
                                        Согласен. Только не «ламповый транзистор», а триод. Транзистор не абстрактный элемент, а вполне конкретный полупроводниковый радиоэлектронный компонент.
                                          0
                                          Хорошо, я понял. Диод есть и вакуумный, а с 1 сеткой будет триод.
                              +3
                              Квантовый компьютер работает на аналоговом, вероятностном принципе.

                              А в чём аналоговость квантового компьютера?
                                +1
                                В том, что каждое измерение даёт (немного) разные результаты.
                                0
                                С монеткой сложно, но попробуем. Представьте мы подбросили три монетки

                                Только вот пример с запутанными фотонами, как я понимаю, выглядит так.
                                Представьте, что мы подбросили 2 монетки, сцепленные орлами или решками. То есть, если 1 состоянию условно сопоставить значение "+1", а другому — "-1", то сумма всегда будет 0. Такой механизм создания пары монетокфотонов.

                                P.S. А все же нужно понять, как «нахождение периода функции» помогает в факторизации. Для числа 15 и 45 — вроде как легко.
                                  –1
                                  Представим себе экспериментатора, который обучен простейшим действиям (достать шар, записать номер, положить шар обратно в мешок, перемешать шары в мешке)

                                  тут небольшое лукавство — мы не знаем, на реальном квантовом компьютере, из чего выбираем. Ведь не из шаров или иных материальных объектов. Природа множества из которого выбираем не определена детерминировано.
                                  Так что предположение о справедливости аксиомы выбора тут просто необходимо.
                                    +1

                                    А каким боком тут аксиома выбора?

                                    +2
                                    Огромное спасибо, давно интересовалась этим, но везде расплывчато написано. Тут же все собрано и систематизировано. Особенно огромное спасибо за примеры с монетами, доступно и понятно ( вспомнила, меня в детстве так же учили сложению и вычитанию, не могла понять и тогда решили на конфетах. Все быстро поняла. И теперь, если что не понятно, прошу обьяснить «на конфетах». У вас получилось.
                                      +2
                                      Мда, текущая ситуация с квантовыми компами выглядит уныло. Однако, тенденция посмотреть в сторону от классических дискретных вычислительных систем — это хорошо.
                                      Вспомнилась байка про секретные советские кирпичи :)…
                                      """ При проведении ядерных испытаний для рассчета зависимости силы взрывной волны от расстояния американцы расставили пару сотен дорогостоящих сложных датчиков… провели испытания, на компьютерах обработали информацию… А позже от своей разведки получают донесение: Советский Союз произвел ядерные испытания, были произведены измерения взрывной волны в десятках тысячах точек, включая эпицентр взрыва… На вопрос КАК??? Позже был получен ответ: советы просто напросто на разном удалении расставили пронумерованные кирпичи, а потом по их разбросу произвели расчеты… """
                                      (это байка, если что :))
                                      Но что то в этом есть похожее сабж :)
                                        0
                                        Завис на статье реально на долго, потому как такой компиляции информации о квантовых компьютерах реально найти до сих пор былоочень и очень трудно.
                                        И да, Хабр, все-таки все еще торт!
                                        Что касается самой технологии и алгоритмов, то мне кажется, что на сегодня просто не хватает ни железа, ни денег на его разработку, ни методов по удешевлению того самого железа. Вполне возможно, что да, развитие крвантовых вычислений зависит от возможных будущих открытий в физике, но на сегодня не думаю, что будет какое-то дальнейшее революционное развитие.
                                          +2
                                          Как верно описано в статье, ахиллесова пята всего этого хайпа по квантовым вычислениям — время декогеренции.
                                          Ну мой личный взгляд, это принципиально не решаемая проблема. Просто потому, что если тепловые, звуковые и электромагнитные взаимодействия действительно можно экранировать так или иначе с достаточным уровнем экранирования, то гравитацию — экранировать нельзя никак. А гравитационное взаимодействие в любом случае присутствует (между квантово-запутанными кубитами и всем сущим вокруг). И чем больше кубит в системе — тем выше это взаимодействие, а значит тем меньше время жизни полносвязанного состояния (причем зависимость там скорее экспоненциальная чем линейная). Это взаимодействие обычно никак не учитывают просто потому что до сих по не существует никакого моста между квантовой механикой и гравитацией, наоборот оные сущности резко конфликтуют. Но это никак не отменяет сам факт гавитационного взаимодействия, а далее, из самых общих и предельно нестрогих ) соображений, лично мне вполне очевидно что квантовые вычисления общего назначения с большим кол-вом полносвязанных кубит это заведомо недостижимая в техническом плане концепция, увы.
                                            +1
                                            В пределах классических соображений гравитационное влияние между кубитами настолько мало, что оно не будет приводить к сколь-либо заметной декогеренции. Мы, конечно, не знаем, каково это будет в квантовой гравитации, но скорее уж мы вряд ли когда-либо сможем достаточно изолировать систему от обычных воздействий. Но декогеренция решается какой-то мере коррекцией ошибок, так что в целом вопрос в достаточно эффективном коде.
                                              0
                                              Так по идее речь о грав. взаимодействии кубитов с Землей (ещё Луна и Солнце как переменные источники). Хотя я не скажу, как при конкретной реализации кубита грав. поле может повлиять на его состояние.
                                                0
                                                Хотя я не скажу, как при конкретной реализации кубита грав. поле может повлиять на его состояние.

                                                Так и никто не скажет. Фундаментальной науке пока даже отдаленно не известно как подружить (в плане теоретической стыкуемости) гравитацию и КМ.
                                                  +1
                                                  Ну в целом мы прекрасно умеем дружить гравитацию и КМ в обычных режимах (скажем, квантовая теория поля в искривленном пространстве-времени посчитает почти что угодно). Только на очень малых масштабах или очень сильных полях возникают проблемы.
                                              0
                                              Так я веду речь не про взаимодействие между кубитами, а про взаимодействие оных кубит с внешней материей. С планетой, с солнцем, ну и т.п. Вот это — ну никак не заэкранировать, и это взаимодействие идет очень даже активно, хотя и не поддается описанию в рамках КМ. Иначе говоря, полноценной изолированной от всего внешнего системы из квантово запутанных кубит просто не создать, гравитация не даст. И чем больше оных кубит — тем сильнее «не даст», примерно экспоненциально сильнее.
                                                +1
                                                Не очень понимаю: квантовая гравитация актуальна либо на малых масштабах, либо в сильных полях. Взаимодействие с планетой описывается прекрасно классически, и не дает значительного вклада в декогеренцию. Единственный вариант, когда это может повлиять — если вы специальные модели гравитационной декогренции, но пока нет никаких причин их рассматривать серьезно.
                                                  +2
                                                  Интересные ссылки, надо их покурить — вполне возможно что я не прав. Спасибо.
                                              0

                                              А при считывании состояния когерентность разрушается?

                                                0
                                                Если вы считали все кубиты, вам уже плевать на когерентность.
                                                Если вы считали только часть кубитов, когерентность все еще остается проблемой для оставшейся части.
                                                  0
                                                  Так значит проблема в том, что нельзя быстро считать состояние кубитов? А решение проблемы быстрого считывания обнулит проблему увеличения длительности когерентности?
                                                    0
                                                    Я имел ввиду, что однажды измеренные кубиты уже не декогерируют. Для неизмеренных же «время жизни» составляет те самые 150 мкс.
                                                      +1
                                                      Ну постойте. Когда мы измеряем кубиты, по принципу неопределённостей мы оказываем на них воздействие. Раз оказываем воздействие — разрушаем состояние квантовой запутанности с ещё не измеренным кубитами. Не?
                                                    0
                                                    А кубиты в принципе возможно считать все ОДНОВРЕМЕННО?
                                                    Если у нас 128 кубитов, то с каждым считанным кубитом проблема когерентности для оставшихся кубитов не нарастает?
                                                      –1
                                                      Слово «ОДНОВРЕМЕННО» в контексте квантовых эффектов выглядит подозрительно. Но считывание отдельных кубитов не добавляет срока жизни системе.

                                                      В теории, может имеет смысл «посменная работа». Берем Х кубитов, они работают 75 мкс, мы их запутываем по Беллу со второй «сменой» из Х кубитов, они работают 75 мкс, мы их запутываем по Беллу с третьей «сменой» из Х кубитов…

                                                      Но этот вопрос я бы проверял экспериментально.
                                                        +1
                                                        Если мои представления соответствуют действительности, то такая схема не сработает. Декогеренция — это запутывание с окружением. Если вторая пачка запутана с первой, а первая запутывается с окружением, то вся система оказывается запутанной с ним же. То есть состояние окружения уже вошло в состав нашей системы, и её «внутренние» состояния больше не будут интерферировать между собой так, как предполагалось алгоритмом.
                                                          0
                                                          Да, звучит разумно. Но есть надежда, что декогеренция будет «грызть» первую смену, а не вторую. А вторая после запутывания от первой уже не зависит.
                                                            +1
                                                            В том-то и дело, что если вторая запутана с первой, то она не может не зависеть от неё. Если системы A и B находятся в запутанном состоянии |0A0B> + |1A1B>, и система A у нас запутывается с E (environment): |0A0E> + |1A1E>, то общее состояние системы получится |0A0B0E> + |1A1B1E>. То есть всё запутано со всем.
                                                              0
                                                              Да, Е запутывается с кубитом 0. Более того, Е может как-то повлиять на кубит 0 (собственно, в этом суть декогеренции). Но влияет ли декогеренция на кубит 1 через кубит 0?

                                                              Взгляните на схему: верхний кубит (окружение) влияет на серединный (эмулируя декогеренцию), но нижний кубит остается неизменным. Если серединный кубит не самоизмерится, мы можем продолжать вычисления с нижним.
                                                                0
                                                                Интересно, как физически создаются операции вроде CNOT.
                                                                То есть я понимаю, что в кристаллах с квадратической нелинейностью (вроде тех, что используют для удвоения частоты) с какой-то вероятностью рождается запутанная пара фотонов. Как создать потом 4 фотона? Или тут речь о том, что 2 пары фотонов дают по 1 фотону в 2 оптических пути? Но так у нас не будет 4 фотонов, запутанных все вместе.
                                                                  +2
                                                                  Это иллюзия, вызванная структурой блок-схемы. Даже если для кубита нарисована прямая линия без «воздействий», это не означает, что его состояние остаётся неизменным. В квантовых вычислениях состояние системы описывается всеми кубитами одновременно, их единым, объединённым состоянием. Именно в этом и заключается вся мощь квантовых вычислений, что размерность пространства состояний растёт экспоненциально с ростом числа кубитов.

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

                                                                  Если перевести это на язык вычислений, то, подходя формально, надо все операторы рассматривать не как действующие на какой-то конкретный кубит или пару кубитов, а как действующие на весь их набор. То есть вместо вентиля X, действующего на кубит 0, у нас применяется оператор XII, действующий на все три кубита (I — единичный оператор, не меняющий состояния). Если у нас было факторизуемое состояние, то после применения такого оператора оно и останется таковым. Если же было запутанным, то этот X повлияет на всё объединённое состояние системы, включающее в себя все кубиты, несмотря на то, что формально он применяется только к первому из них.

                                                                  Рассмотрим для простоты не трёх-, а двухкубитную систему, которая факторизуема. Например, |00>+|01>, что можно представить как |0>⊗(|0>+|1>). То есть, первый кубит обнулён, второй — в суперпозиции. (Нормировку для простоты опускаю.) Если мы подействуем X на первый кубит, состояние поменяется на |10>+|11> = |1>⊗(|0>+|1>). Здесь всё просто и очевидно: на что подействовали, то и поменялось.

                                                                  А теперь возмём запутанное состояние: |00>+|11>. Его уже нельзя представить в виде произведения двух независимых состояний отдельных кубитов. И если мы подействуем тем же X на тот же первый кубит, то получится |01>+|10>. Было одно состояние, стало совсем другое. И тут попросту бессмысленно задавать вопрос, остался ли второй кубит в прежнем состоянии. Мы ведь даже не можем это состояние вычленить, чтобы что-то про него сказать.
                                                                    0
                                                                    А теперь возмём запутанное состояние: |00>+|11>. Его уже нельзя представить в виде произведения двух независимых состояний отдельных кубитов. И если мы подействуем тем же X на тот же первый кубит, то получится |01>+|10>. Было одно состояние, стало совсем другое. И тут попросту бессмысленно задавать вопрос, остался ли второй кубит в прежнем состоянии. Мы ведь даже не можем это состояние вычленить, чтобы что-то про него сказать.

                                                                    С теоретической точки зрения этой имеет смысл. С практической же… Вот есть у нас состояние |00>+|11>. При измерении 2 кубита мы получим ноль или один с вероятностью 50\50. Теперь мы применили Х к первому кубиту (симулировали декогеренцию), получили |01>+|10>. При измерении 2 кубита мы все так же получим ноль или один с вероятностью 50\50. По факту, мы можем извращаться с первым кубитом как черная дыра с пространственно-временным континуумом — второй кубит будет выдавать 0\1 с вероятностью 50\50 (конечно, если первый кубит не измерится).

                                                                    А потом все просто. Берем N кубитов, делаем первый шаг для условного Гровера. Запутываем их еще с N кубитами, «правильные» вероятности переносятся на «вторую» смену. Делаем шаг Гровера относительно второй смены, переносим вероятности на третью смену. Под конец имеем систему с 99.99% «закогерированными» кубитами, и N кубитами в нужном нам состоянии.

                                                                    Вполне возможно, что я чего-то не понимаю. Может, вы сможете предложить схему, демонстрирующую вашу точку зрения? Потому что, судя по этой схеме, все работает. Основное вычисление в верхнем ряду, переносы состояний сделаны через SWAP, после SWAP всякая периодика изображает декогеренцию.
                                                                      0
                                                                      При измерении 2 кубита мы все так же получим ноль или один с вероятностью 50\50.
                                                                      <…>
                                                                      Может, вы сможете предложить схему, демонстрирующую вашу точку зрения?
                                                                      Проблема в том, что измерение — это лишь конечный этап, а вся затея с «перебросом запутанности» была задумана, чтобы продлить этап квантовых вычислений. А они зависят от точного значения амплитуд, причём, повторюсь, для всей системы в целом (в отличие от измерений).

                                                                      Вот другой пример, надеюсь, лучше демонстрирующий мою мысль. Предположим, кубит A — «мусорный» (окружение), кубит B — рабочий. Изначально кубит B в состоянии |0>+|1>, и мы применяем H, чтобы привести его в состояние |0>. Если он не запутан с кубитом A, то всё работает, как задумано. Однако если у нас B запутывается с A, и состояние получается |00>+|11>, то вентиль H на второй кубит выдаст нам результат |00>+|01>+|10>-|11>. Мы измеряем второй кубит — и получаем 0 или 1 с вероятностью 50/50 вместо гарантированного нуля. Алгоритм поломан.

                                                                      P. S. К сожалению, приведённую схему пока не могу прокомментировать: давно не возился с квантовыми вычислениями, и надо много времени, чтобы снова въехать в тему и для начала хотя бы разобраться, что эта схема иллюстрирует.
                                                                        0
                                                                        Ок, я изобразил ваши доводы. Первая схема: — двойной Адамар на «боевой кубит»; результат: ноль. Вторая схема: двойной Адамар и промежуточная «декогеренция»; результат: суперпозиция. Мой контр-аргумент: Адамар, SWAP на чистый кубит (который до сих пор не принимал участия в вычислениях), Адамар на чистый кубит. Результат на чистом кубите совпадает с результатом в первой схеме.

                                                                        kruegger Shkaff — ваше мнение? Можно ли избежать проблему декогеренции, регулярно добавляя в схему «чистые» кубиты (при условии, что декогеренция не вызывает самоизмерения на кубитах)?

                                                                          +1
                                                                          Я не вчитывался в подробности аргументов, но примерно так работает коррекция ошибок: добавляем в систему много дополнительных кубитов, куда будет записываться часть информации, и декогеренция не так страшна (можно измерять доп. кубиты, чтобы проверить, произошла ли уже декогеренция, и исправлять ошибку). В итоге на один логический кубит, работающий без ошибок, приходится несколько десятков-сотен-тысяч физических кубитов, на которые действует декогеренция.
                                                                            +1
                                                                            Ага, теперь уловил схему. Все активные кубиты своппятся попарно с пачкой резервных, что не создаёт запутанности. Хм… А ведь чёрт его знает, может и сработать. С другой стороны, тогда непонятно, почему это не применяют. Подозреваю, что там могут быть какие-то технические трудности (скажем, невозможно разбить пачку кубитов на две части так, чтобы с одной стороны, они могли взаимодействовать между собой, а с другой, чтобы декогеренция одной части не приводила к декогеренции другой). Тут я уже недостаточно подкован, увы.
                                                                          0
                                                                          Запутываем их еще с N кубитами

                                                                          Повторю вопрос. Знаете ли Вы. какой физический процесс дает…
                                                                          Хотя стоп — Вы тут просто создаете N пар запутанных (только попарно) фотонов? Это вроде как можно.
                                                                            0
                                                                            Друг, я настолько ламер в физике, что даже не пытаюсь в эту тему лезть. Увы, не могу ответить на твой вопрос. Но в Шоре кубиты запутываются довольно причудливо; во всяком случае, сложнее "N пар запутанных (только попарно) фотонов".
                                                                              0
                                                                              Ну тогда извините:)
                                                                              Я знаю механизм, как рождают пару фотонов — спонтанное параметрическое рассеяние.
                                                                              Как я понимаю, происходит (с некоторой малой вероятностью) в кристаллах с квадратической нелинейностью. Это те, что используются для удвоения частоты (2 фотона сливаются в один), а как-то производят и обратный процесс.
                                                                                +1
                                                                                Как я понимаю, происходит (с некоторой малой вероятностью) в кристаллах с квадратической нелинейностью.

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

                                                                                В принципе, никто не мешает вам создать и больше запутанных фотонов: берете много источников одиночных фотонов, много делителей луча, и запутываете все со всеми. Вот как тут, например.
                                                          0
                                                          При считывании в классическом смысле Вы получаете результат «кубит в состоянии 1», после чего этот кубит фиксируется в каком-то состоянии вместо запутанного. Причем не факт, что в состоянии 1.
                                                        –1
                                                        Хотя я считаю, что такие экспериментальные исследования полезны и могут привести к лучшему пониманию сложных квантовых систем, я скептически отношусь к тому, что эти усилия когда-нибудь приведут к созданию практического квантового компьютера. Такой компьютер должен был бы иметь возможность манипулировать — на микроскопическом уровне и с огромной точностью — физической системой, характеризующейся невообразимо огромным набором параметров, каждый из которых может принимать непрерывный диапазон значений. Можем ли мы научиться управлять более чем 10^300 непрерывно изменяющимися параметрами, определяющими квантовое состояние такой системы?

                                                        Мой ответ прост. Нет никогда.


                                                        «The Case Against Quantum Computing
                                                        The proposed strategy relies on manipulating with high precision an unimaginably huge number of variables
                                                        By Mikhail Dyakonov»

                                                        spectrum.ieee.org/computing/hardware/the-case-against-quantum-computing
                                                          +2
                                                          «Если выдающийся ученый говорит, что что-то возможно, то скорее всего он прав. Если выдающийся ученый говорит, что что-то невозможно, то скорее всего он не прав» (С)
                                                          0
                                                          Спасибо большое за статью, в который раз читаю про квантовые компьютеры и в который раз очень интересно и как в первый раз (память у меня как у рыбки).
                                                          Вопросик возник — для получения каких-то результатов вычислений нам надо процесс «вычисление -> съём результатов» проделать какое-то большое кол-во раз (миллион, например). С текущим развитием технологий (декогеренция 150-200микро секунд) нужно кучу усилий затратить чтобы хотя бы один «съём результатов» взять. Как же тогда проходят вычислений и доказательства превосходства?
                                                            0

                                                            Огромное спасибо за статью! Впервые я что-то да понял :)


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

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

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


                                                              Вопросы: Можно ли это сделать, если да, то можно ли производство поставить на поток и будет ли это дёшево?

                                                                +3
                                                                Гениально! Срочно патентовать!

                                                                А если серьезно, то тепловой шум обычного резистора дает отличный по настоящему случайный шум в очень широкой частотной полосе. И ГСЧ на этом давно и успешно производят. Резистор стоит даже не знаю на сколько порядков меньше чем квантовый компьютер )))))
                                                                  0
                                                                  Формально тепловой шум — не квантово случайный, а потому может быть взломан и не подходит для истинно ГСЧ. Но есть и простые квантовые схемы: на источниках фотонов или туннелировании.
                                                                    0
                                                                    Формально тепловой шум — не квантово случайный

                                                                    Ммм… а собственно, почему? Ведь колебания кристаллической решетки/электронов будут не нулевыми даже при абсолютном нуле, именно в силу квантовости оных объектов. Так что, по идее, и тепловой шум при комнатной температуре состоит из двух компонент — формально детерминированной и квантовой. Хотя, учитывая что взаимодействие отдельных атомов кристалической решетки, равно как и электронов с оными, это квантовые процессы, детерминированности там нет нигде. Т.е. «взломать» тепловой шум нельзя даже формально.?
                                                                      +1

                                                                      Проблема подобного ГСЧ в том, что Вы понятия не имеете, из какого "распределения" он будет Вам выдавать числа, так как нельзя контролировать окружающую среду. А незнание и изменчивость распределения потенциально может привести к проблемам. Например, когда при определенной температуре или каком другом внешнем влиянии злоумышленник может "подтасовать" то распределение, что ему нужно. Это если мы говорим о криптографии.


                                                                      Можем взять что-то безопасней, например, обычный метод Монте-Карло. Если распределение ГСЧ будет не равномерным, а смещенным куда-нибудь, то Ваш Монте-Карло будет давать смещенную оценку, что снова же нежелательно. Более того, из-за незнания распределения и ее вариабильности во времени, мы не сможем установить верхнюю границу ошибки. И это будет касаться всех вероятностных алгоритмов и эвристик. А других причин иметь ГСЧ у нас и нет, и поэтому смысла в таком ГСЧ тоже особо нет.

                                                                        0
                                                                        Ну вот тепловой шум при нулевой температуре и будет истинно случайным. В целом вы правы, фундаментально все квантовое. Только вот на более высоком уровне часть оказывается «классическим» — т.е. его можно предсказать в теории. Если вы генерируете СЧ, вы не хотите классической части совсем. В частности, они подвержены всяким атакам — просто измените температуру системы, и СЧ поменяются.
                                                                          0
                                                                          Тепловой шум случаен, да. Если будете очень точно определять положение 1-2 атомов — будет у Вас ГСЧ.
                                                                      0
                                                                      А шум, который он генерирует можно использовать для генераторов случайных чисел.
                                                                      Так и собираются делать, вот тут в посте немного есть про это в В9. Основное преимущество: возможность доказать, что числа на самом деле случайные. Но супер дорого, есть гораздо более простые способы.
                                                                      +2

                                                                      Хорошая статья, хоть примерно начал понимать суть.
                                                                      Думаю, одна из причин проблем непонимания — не совсем корректный перевод термина "quantum computer" на русский.
                                                                      Думаю, правильнее называть это не квантовый компьютер, а квантовый вычислитель или квантовый сопроцессор. Компьютер — это что то, способное решать самые разные задачи. А тут просто некая разновидность математического сопроцессора, решающая очень быстро определенные классы задач.

                                                                        –1

                                                                        Тут стоит сказать, что вот этот пассаж:


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

                                                                        — это уже фантазия автора. Что именно автор собирается усреднять в тех же алгоритмах Гровера и Шора?

                                                                          0

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

                                                                            +1
                                                                            Спасибо за статью. Я понимаю, что любая аналогия имеет ограниченную область применения и мой вопрос, возможно, звучит очень глупо, но всё же: почему нельзя заменить квантовый компьютер тем же мешком с шарами? Это невозможно из-за отсутствия запутанности между объектами или же по какой-то иной причине? Мне хочется понять, что именно принципиально отличает данную аналогию от реальности.
                                                                              0
                                                                              На самом деле любой макроскопический «мешок с шарами» нельзя описывать как абсолютно случайный объект. Конечно шары описываются квантовой механикой и, как я понимаю, даже являются суперпозицией множества решений ур-ия Шрёдингера.
                                                                              Можете глянуть для примера здесь, «мешок с шарами» будет описан как суперпозиция каких-то состояний, но не с такими простыми коэффициентами.
                                                                                0
                                                                                Как Я понимаю проблему:
                                                                                вы в классическом компьютере не можете ОДНИМ действией выбирать шар из КАЖДОГО мешка.
                                                                                Если у вас есть 10 мешков. и вы совершаете 10 операций вытаскивания, то на классическом компютере вы вытащите 10 шаров, а на квантовов 10 раз по 10 шаров.
                                                                                +1
                                                                                Википедия указывает на то, что первым идею квантовых вычислений высказал в 1980 году наш ученый Юрий Манин.
                                                                                Википедия как раз говорит о том, что «Quantum computing began in the early 1980s, when physicist Paul Benioff proposed a quantum mechanical model of the Turing machine.» (https://link.springer.com/article/10.1007%2FBF01011339)
                                                                                  +1
                                                                                  Спасибо, я ориентировался на русскую версию, а там описано ровно наоборот:
                                                                                  Идея о квантовых вычислениях была высказана Юрием Маниным в 1980 году[3].

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

                                                                                  Не готов спорить какой вариант более верный, но еще раз спасибо за уточнение.
                                                                                    +2
                                                                                    Ради любопытства проверил: книга Манина вышла в ноябре 80 (сдана в печать в мае), а Бениофф вышел в мае 80:
                                                                                    Скриншоты



                                                                                    Так что тут, наверное, можно считать реально одновременным:)
                                                                                    Кому интересно, вот что написано у Манина:
                                                                                    стр. 15 книги


                                                                                  0
                                                                                  Физики создали соединение лития, осмия и кислорода, которое проявляет свойства спиновой жидкости. Это одно из немногих подобных веществ и первое, содержащее осмий. 28.04.2018 nauka.vesti.ru/article/1048092
                                                                                  Исследователи полагают, что материал позволит создавать квантовые компьютеры. Достижение описано в научной статье, опубликованной в журнале Scientific Reports группой во главе с Масом Субраманианом (Mas Subramanian) из Орегонского университета в США.
                                                                                  nature.com/articles/s41598-018-25028-0
                                                                                  «Явление квантовой спиновой жидкости до сих пор было обнаружено в очень немногих неорганических материалах, некоторые из которых содержат иридий. Осмий находится рядом с иридием в периодической таблице [Менделеева] и имеет все нужные характеристики для образования соединений, которые могут поддерживать состояние квантовой спиновой жидкости», – поясняет Субраманиан.
                                                                                  today.oregonstate.edu/news/discovery-new-material-key-step-toward-more-powerful-computing
                                                                                  ru.wikipedia.org/wiki/Спиновая_жидкость одно из магнитных состояний вещества, наряду с ферромагнетизмом и антиферромагнетизмом. Обусловлено «жидким» поведением спинов, собственных моментов импульсов элементарных частиц при низких температурах. Возмущение спинов происходит вплоть до самых низких температур.
                                                                                  Крайне редко встречаются вещества, у которых даже при самом экстремальном охлаждении спины продолжают вести себя хаотично. Это состояние и называется спиновой жидкостью.
                                                                                  Авторы исследовали вещество с химической формулой Li2,15Os0,85O3.
                                                                                  Поясним, что непривычные глазу дробные числа в ней связаны с тем, что формула отражает строение не отдельных молекул, а о больших кристаллов, и в пределах одного такого кристалла разные атомы лития и осмия имеют разные валентности. Причём кристаллическая решётка этого вещества по форме напоминает пчелиные соты.
                                                                                  Исследовав это соединение с помощью дифракции нейтронов и рентгеновской абсорбционной спектроскопии, учёные обнаружили явление, называемое магнитной фрустрацией. Оно заключается в том, что само строение кристаллической решётки мешает спинам электронов выстроиться одинаково по всему кристаллу.
                                                                                  Признаков такой упорядоченности не было обнаружено даже при температуре, всего на 0,1 градуса отличающейся от абсолютного нуля. Из этого авторы заключили, что основным состоянием (то есть состоянием с минимальной энергией) для этого вещества, скорее всего, и является уже упомянутая спиновая жидкость.
                                                                                    +2
                                                                                    Кремниевый спиновый кубит Intel совершенствуется и обрастает научной базой С 2015 года на основе интереса к квантовым вычислениям компания Intel сотрудничает с нидерландским институтом QuTech.
                                                                                    Научные партнёры компании продвинулись в изучении как сверхпроводящих кубитов и систем на их основе, так и в изучении систем на кремниевых спиновых кубитах. И хотя научные коллективы QuTech остаются главной опорой Intel в изучении квантовых платформ компании, мировое научное сообщество начинает потихоньку включаться в процесс изучения квантовых вычислителей микропроцессорного гиганта.
                                                                                    3dnews.ru/983785

                                                                                    Квантовый чип Tangle Lake с 49 кубитами В январе 2018 года исполнительный директор компании Intel
                                                                                    Брайан Кржанич сообщил о создании сверхпроводящего квантового чипа под кодовым именем «Tangle Lake», обладающего 49 кубитами. По его прогнозу, квантовые компьютеры помогут в создании лекарств, финансовом моделировании и составлении прогнозов погоды. Intel ведёт разработки квантовых компьютеров по двум направлениям: создание устройств на сверхпроводниках и кремниевых чипов со «спиновыми кубитами».
                                                                                    ru.wikipedia.org/wiki/Квантовый_компьютер#Экспериментальные_образцы
                                                                                    0
                                                                                    del
                                                                                      0
                                                                                      del

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

                                                                                      Самое читаемое