Что такое квантовые алгоритмы, как они устроены и в чем их
преимущество по сравнению с классическими вычислениями? Физики
Алексей Федоров и Евгений Киктенко рассказали ПостНауке об истории
квантовых алгоритмов, концепте квантового превосходства и
перспективах появления квантового компьютера.Это материал изгида
Квантовыйкомпьютер. Партнер гида Академия Росатома.Квантовые
алгоритмы и их отличие от классическихАлгоритмы формализованная
последовательность действий для решения какой-либо задачи.
Классические алгоритмы предназначены для решения задач с
использованием ресурсов классических компьютеров (то есть
вычислительных устройств, для описания которых достаточно
использования классической физики).Современные достижения в области
управления отдельными квантовыми объектами, такими как атомы, ионы,
фотоны (частицы света), электроны, позволяют создавать приборы и
устройства принципиально нового типа. При их функционировании и,
соответственно, описаниисущественную роль играют эффекты квантовой
физики, принципиально не поддающиеся описанию с точки зрения
классической физики. Разработка таких устройств является предметом
квантовых технологий.Одним из наиболее бурно развивающихся
направлений квантовых технологий являются квантовые вычисления.
Идея состоит в том, чтобы задействовать явления квантовой физики
для ускорения решения вычислительных задач. Для квантовых
вычислительных устройств можно, так жекак и для случая классических
вычислений,ввести понятие алгоритма. Поскольку квантовые объекты
находятся изначально в некотором квантовом состоянии, а в процессе
реализации алгоритма квантовое состояние трансформируется в другое,
то квантовый алгоритм можно охарактеризовать как определенную
последовательность преобразований квантового состояния. При этом в
результате преобразований мы получаем квантовое состояние, которое
должно содержать в себе ответ, то есть решение задачи. Путем
измерения квантового состояния мы извлекаем этот ответ из квантовой
системы. Это достаточно общее описание квантовых алгоритмов. Далее
все зависит от того, к какой модели квантовых вычислений мы хотим
этот квантовый алгоритм применить.Квантовые вычисления можно
реализовывать для совершенно различных физических систем, таких как
ансамбли ультрахолодных атомов и ионов, квантово-оптические
системы, сверхпроводниковые цепочки и так далее. Стоит отметить,
что несмотря на то, что теоретическая база квантовой теории
информации универсальна и может быть применена к любой физической
реализации, при конкретной реализации возникают определенные
детали, которые связаны, например, с ограничениями физической
системы.Возможно дополнить эти рассуждения. Одним из ключевых
понятий для классической теории вычисления является машина Тьюринга
модель любых вычислительных устройств. С помощью концепции машины
Тьюринга удается формализовать понятие алгоритма. В 1980-е годы
появилась концепция квантовой машины Тьюринга как некоторого
обобщения классической машины. Квантовая машина Тьюринга помогает
формализовать описание квантовых алгоритмов.Как устроены квантовые
вычисленияСегодня наиболее изученной (и в какой-то мере наиболее
интуитивно понятной) является цифровая модель квантовых вычислений
еетакже называют вентильной,гейтовой. Цифровая модель квантовых
вычислений может рассматриваться как обобщение классической
цифровой модели вычислений.Классические вычислительные устройства
оперируют регистрами с информационными битами, которые принимают
состояние либо 0, либо 1. Поэтому классический алгоритм можно также
представлять как некоторую реализацию булевой функции (функции
двоичной переменной), которая получает на входе строку битов,
что-то с ними делает и на выходе отдает другую строку. Далее
возникает вопрос: как может быть реализована данная булева
функция?Оказывается, что любую функцию можно разложить на
элементарные логические операции типа и/или. Фактически алгоритм
представляет собой реализацию логических операций над этими
битами.Квантовые вычисления привносят понятие кубита квантового
обобщения бита, квантовой суперпозиции состояний 0 и 1.
Математически это соответствует тому, что с каждымиз альтернативных
состояний (0 и 1) мы сопоставляем комплексное число и утверждаем,
что объект может находиться в какой-то степени в состоянии 0и в
какой-то степени в состоянии 1. Вероятности нахождения в состояниях
0 и 1 определяются квадратом модулей соответствующих комплексных
чисел. Чтобы модифицировать квантовое состояние, мы выполняем с ним
квантовые аналоги логических операций, которые в квантовой физике
описываются унитарными операциями, называющимися вентилями
(гейтами).1Важный аспект квантовой физики концепция измерения,
которое обнаруживает кубит в одном из двух
классическихальтернативных состояний (0 или 1). Именно измерение
является финальнымэтапом реализации квантового алгоритма. Таким
образом, в цифровом квантовом компьютере алгоритм реализуется как
последовательность квантовых логических операций над квантовым
регистром (регистром из кубитов), за которым следует финальное
считывающее измерение, дающее на выходе классическую строку битов.
Теоретически в регистре может быть произвольно большое число
кубитов. Чтобы задать квантовое состояние всей системы, необходимо
указать, в какой степени эти двухуровневые объекты находятся в
каждом из возможных состояний. Возвращаясь к примеру с
классическими системами:если у нас есть три монетки, то они могут
находиться в одном из восьми состояний от 0-0-0 до 1-1-1 (все
возможные комбинации нулей и единиц). Если мы рассматриваем
систему, в которой три кубита находятся в запутанном состоянии, то
нам нужно задать степень, в которой эти три монетки находятся в
каждом из всех возможных восьми состояний,то есть в какой степени
они находятся в состоянии 0-0-0, в какой в состоянии 0-0-1 и так
далее. Выходит, нам нужно задать уже восемь комплексных чисел. А
если у нас, допустим, 50 запутанных кубитов, то количество этих
комплексных чисел, необходимое для определения квантового
состояния, 250. Таким образом, построение квантового компьютера
открывает нам доступ к экспоненциально большому вычислительному
пространству.Если говорить более точно математически, то в
начальный момент времени в квантовом регистре мы инициализируем
состояние, скажем, 50 кубитов, так что на входеимеем вектор с 250
элементами. Далее мы действуем на этот вектор унитарными
операциями, которые описываются матрицами. В результате действия
унитарных операций квантовое состояние меняется. На завершающем
этапе мы извлекаем информацию о квантовой системе путем измерения и
получаем из 50-кубитной системы классическую информацию в виде
50-битного вектора.При реализации квантовых алгоритмов может быть
необходимо совершать сложные преобразования над квантовым
состоянием. Тем не менееоказывается, что сложные многокубитные
квантовые операции тоже можно разложить на отдельные блоки операции
над одним или двумя кубитами. Кажется, что здесь возникает
проблема: если в классическом случае булева функция оперирует
дискретными пространствами, то в квантовых состояниях с
комплексными числами все матрицы непрерывные (аналоговые)и их может
быть бесконечно много. Одним из важнейших достижений квантовой
теории информации является теорема Соловея Китаева. Она утверждает,
чтоесли есть некая целевая матрица, которую вы хотите реализовать,
и есть некоторый конечный набор доступных гейтов,обладающий
свойством универсальности, то можно реализовать другую матрицу,
которая будет близка к целевой с любой наперед заданной точностью.
Оказывается, что такой универсальный набор гейтов можно составить
лишь из набора однокубитных гейтов (в минимальном случаеих может
быть всего два) и одного двухкубитного гейта.Напомним, что процесс
получения результата квантового алгоритма, 50-битной строки, носит
вероятностный характер. Эту вероятность задают комплексные числа,
которые использовались, чтобы описать, в какой степени квантовые
биты находились в одном из возможных состояний (количество всех
возможных 50-битных строк равняется250). В процессе измерения
происходит коллапс: все элементы вектора состояния, кроме одного,
обращаются в 0, а элемент вектора состояния, соответствующий
реализовавшемуся исходу, становится равным 1. Поэтому искусство
построения квантовых алгоритмов состоит в выборе конкретных
унитарных операций, которые можно будет применить к квантовым битам
так, чтобы финальное измерение дало какую-то полезную информацию.
Квантовые алгоритмы дают потенциальное превосходство над
классическими за счет этого доступа к экспоненциально большому
пространству состояний и возможности управлять всеми состояниями
одновременно.Кроме цифровой модели квантовых вычисленийесть и
другие, напримерадиабатическая модель квантовых вычислений. Она
основана на приведении системы в требуемое состояние,
характеризующееся минимумом энергии (основное состояние
гамильтониана). Изначально квантовая система приготавливается в
основном состоянии некоторого фиксированного гамильтониана. Затем
параметры системы (гамильтониан) достаточно медленно меняются,
принимая значения, соответствующие решаемой задаче. Изменившееся
(эволюционировавшее) состояние системы считывается в качестве
ответа. При этом вся эволюция происходит адиабатически, то есть
достаточно медленно, что гарантирует тот факт, что система остается
в основном состоянии. Было доказано, что цифровая и адиабатическая
модели квантовых вычислений эквивалентны.Отметим также, что, помимо
универсальных квантовых вычислительных устройств, то есть
устройств, решающих любую задачу, существуют и квантовые
вычислительные устройства специализированного типа,
напримерквантовые симуляторы.2История квантовых алгоритмовИстория
квантовых вычислений началасьв каком-то смыслене с квантовой
физики. Одной из первых работ на пути к концепции квантовых
вычислений стала работа Рольфа Ландауэра, в которой им была
произведена попытка анализа ограничений, накладываемых физикой на
процесс вычислений. В этой работе он сформулировал знаменитый
принцип, известный сегодня как принцип Ландауэра: вычислительная
система при потере одного бита информации выделяет небольшое
количество тепла, пропорциональное температуре этой системы.Трудом
Ландауэра вдохновился Чарльз Беннет человек, вписавший себя в
историю квантовых информационных технологий тем, что сделал
существенный вклад и в квантовые вычисления, и в квантовую
криптографию. Один из базовых протоколов квантовой криптографии
носит его имя: BB84 протокол Беннета и Брассара.Беннет развил идею
Ландауэра в своих работах и во время дискуссии с Ричардом Фейнманом
озадачил его вопросом о том, какие ограничения квантовая физика
накладывает на вычисления. Ричард Фейнман, известный сегодня как
один из отцов концепции квантовых вычислений, начинает одну из
своих работ (Quantum mechanical computers), посвященную квантовым
компьютерам, с описания этого случая. Указав, что серьезных
ограничений, кроме очевидных размерных ограничений,он не обнаружил,
Фейнман предлагает рассмотреть, что было бы, если бы алгоритмы
строились на базе не классических, а квантовых принципов.Часто
справедливо замечают, что некорректно упоминать только Фейнмана как
основоположника концепции квантовых вычислений. Важную роль здесь
сыграли такие теоретики, как Юрий Манин или Пол Бениофф. Однако
фактически именно вместе с этими идеями Фейнмана появилась
тенденция разрабатывать квантовые алгоритмы. В 1985 году Дэвид Дойч
формализовал понятие квантовой машины Тьюринга и предложил один из
первых квантовых алгоритмов алгоритм Дойча Йожи. Сет Ллойд
формализовал идею Фейнмана универсального квантового симулятора, то
есть возможности с помощью квантовых вычислительных устройств
моделировать любые другие квантовые системы.Когда идея квантовых
вычислений была озвучена впервые, она встретила вполне оправданную
критику. С математической точки зрения концепция квантовых
вычислений выглядит очень красиво. Но с точки зрения
экспериментальной реализации задача построения квантового
компьютера казалась невыполнимой, поскольку требовала организации
необычайно точных операций над квантовыми состояниями отдельных
квантовых объектов.Невзирая на это, в 1990-е началасьцелая волна
исследований квантовых вычислений. Питер Шор предложил квантовый
алгоритм факторизации и дискретного логарифмирования, позже
названный его именем, который справляется с данными задачами
значительно быстрее всех известных классических алгоритмов (здесь
под скоростью понимается количество требуемых элементарных операций
как функции параметра сложности задачи в нашем случае это размера
числа, которое нужно факторизовать или от которого нужно посчитать
дискретный логарифм). Важно отметить, что эти задачи имеютважное
значение в криптографии. Фактически Шор показал, что квантовый
компьютер может взламывать практически всю используемую на
сегодняшний день асимметричную криптографию.Далее Шор
продемонстрировал, что с ошибками, естественно возникающими из
экспериментальных ограничений в возможности манипулирования
квантовыми состояниями, можно бороться с помощью введения некоторой
избыточности при кодировании квантовых состояний. Таким образом,
Шор сформулировал принцип квантовой коррекции ошибок. Он показал,
что для того, чтобы закодировать состояние одного логического
кубита (то естьабстрактной единицы квантовой информации, с которой
идет работа с точки зрения квантового алгоритма), можно
использовать несколько физических двухуровневых носителей
физических кубитов. При этом, даже если в состоянии одного из
физических кубитов произойдет случайное изменение, существует
возможность восстановить исходное состояние всей системы кубитов
(существует возможность исправить ошибку). По сути в работе
Шораиспользовался обобщенный на случай квантовых состояний подход
классических кодов коррекции ошибок, теоретическая основа которых
была разработана в середине века Клодом Шенноном. Полученный
результат показал, что квантовые вычисления это не просто красивая
математическая идея, а потенциально реализуемая на практике
технология.На сегодняшний день гонка вокруг квантовых компьютеров
ведется не только за количество и качество кубитов, но и за
эффективные квантовые алгоритмы для решения полезных индустриальных
задач, а также методы коррекции ошибок.Виды квантовых
алгоритмовАлгоритм Дойча (1985) и алгоритм Дойча Йожи
(1992)Представим довольно искусственную задачу: у нас есть
некоторая булева функция, в оригинале функция одной переменной.
Нужно за минимальное количество обращений к этой функции
определить:эта функцияконстантная (на все входы всегда выдает либо
0, либо 1) или сбалансированная (для половины входов выдает 0, а
для другой половины 1).Условно говоря, у нас есть один бит, мы
переводим его в другой бит. И оказывается, что функций, переводящих
одну величину, принимающую значения 0 и 1, в другую аналогичную
величину, всего четыре. Первая функция f(x)=x ничего с аргументом
не делает. Вторая функция 0 переводит в 1, а 1 в 0: f(x)=1-x.
Третья функция f(x)=0 всегда возвращает 0. А четвертая f(x)=1
всегда возвращает 1. Эти четыре функции мы разбиваем на два класса:
первые две сбалансированные, а две другие константные. Грубо
говоря, нам дали черный ящик, внутри которого зашита какая-то из
четырех функций. Наша задача понять, к какому классу принадлежит
функция, находящаяся внутри ящика. А все, что мы умеем, это
подавать что-то этому черному ящику на вход и смотреть, что будет
на выходе.Эту задачу можно решать классическим образом (отправлять
входы и смотреть выходы) или квантовым. В первом случаенам
потребуется два запроса к нашему ящику: мы можем посмотреть, что он
выдает в ответ на входящий 0 и на 1, а затем однозначно определить
саму функцию и ее тип. Второй вариант решения реализация алгоритма
Дойча. Мы конструируем для этого черного ящика специальный
квантовый аналог, который называется квантовым оракулом.2По сути
квантовый оракул это многокубитный гейт, который, как мы уже знаем,
можно реализовать с помощью однокубитных и двухкубитных операций.
Мы отправляем в квантовый оракул специально приготовленное
квантовое состояние, затем производим дополнительную квантовую
операцию и по итогу измерения результирующего выходного состояния
можем понять, какому классу (константная или сбалансированная)
относится функция внутри черного ящика. Появляется ощущение магии,
потому что однозначный ответ мы узнаем уже за один проход, таким
образом получаем ускорение по сравнению с классическим
способом.Алгоритм Дойча был очень важен в историческом контексте.
Дойч показал, что квантовые вычисления помогают решать задачи
быстрее, чем классические компьютеры. Следующий важный шаг был
связан с обобщением этого алгоритма на случай функций произвольного
числа переменных.Алгоритм Шора (1994)Работа над рядом квантовых
алгоритмов, таких как алгоритм Саймона, Шора и Гровера, велась
параллельно и в одном направлении. Идеологически они являются
развитием идеи Дойча, который заложил модель установления
соответствия.Алгоритм Шора это на самом деле некоторая надстройка
над другим базовым алгоритмом алгоритмом поиска периода. Он
используется для решения задачи о черном ящике, реализующем
некоторую функцию, ведущую себя периодическим образом. Мы знаем
функцию, еепериод нужно найти. И оказывается, что в классике, если
период достаточно большой, то все, что мы можем, это перебирать
варианты до тех пор, пока не найдем два аргумента, дающих одно и то
же значение. В квантовом случае алгоритм строится иначе. Нам нужен
квантовый оракул, реализующий эту функцию, а также квантовое
преобразование Фурье аналог дискретного (быстрого) преобразования
Фурье (FFT).Идея алгоритма интуитивно довольно простая. На вход
квантового оракула подаются два регистра кубитов: первый
соответствует входным значениям функции, второй выходным. В первом
регистре приготавливается суперпозиция всех возможных входных
значений, второй регистр инициализируется фиксированным состоянием,
после чего на выходе мы получаем квантовую суперпозицию всех
возможных входов и соответствующих им выходов. Затем делаем
измерение выходного регистра, в результате чего получаем некоторое
случайное значение функции, а в другом регистре суперпозицию всех
аргументов функции, соответствующих полученном значению. Дальше
применяем квантовое преобразование Фурье над первым регистром и в
считывающем измеренииполучаем величину, пропорциональную обратному
периоду функции. Повторяя эту операцию несколько раз и используя
классический алгоритм Евклида для поиска наибольшего общего
делителя (НОД), мы получаем сам период.Оказывается, что задачу
факторизации разложения чисел на простые множители и задачу
дискретного логарифмирования можно свести к задаче поиска периода.
Важным практическим следствием этого является тот факт, что при
реализации алгоритма Шора можно разлагать числа на простые
множители и решать задачи дискретного логарифмирования значительно
быстрее, чем с помощью любых известных на сегодняшний день
классических алгоритмов. Поэтому это серьезная угроза для
криптографии с открытым ключом, построенной на этих принципах. Все
это зародило колоссальный интерес к технологии квантовых вычислений
как потенциальному инструменту для решения задач, недоступных для
классических компьютеров, и драйверу развития других
технологий.Развитие квантовой и постквантовой криптографии важные
последствия изобретения алгоритма Шора.Алгоритм Гровера (1996)Цель
алгоритм поиск элемента в неупорядоченной базе данных. Можно
считать, что у нас есть черный ящик с неким фиксированным
количеством входов, равным N, среди которых есть лишь один, на
который черный ящик скажет да, в то время как на остальные он
говорит нет. Задача наиболее оптимальным образом найти этот элемент
в классическом и квантовом случае. Оказывается, что квантовый
алгоритм решения такой задачи дает преимущество как говорят,
квадратичное ускорение, поскольку в данном случае вместо порядка N
запросов, которые нам нужны в классическом случае, понадобится лишь
корень из N запросов.Можно понять это следующим образом. Если в
классикемы решали бы эту задачу, пробуя один вариант за другим, то
в квантовом случае алгоритм строится так, что мы создаем некоторое
квантовое состояние, содержащее сразу все возможные варианты
входов. Затем подаем его на черный ящик (квантовый оракул), а с
выходом производим некоторые преобразования. Потом вновь подаем
результирующее состояние в оракул и производим некоторые
преобразования. После порядка корня из N итерацийфинальное
измерение почти точно дают искомый вход.Обобщение алгоритма Гровера
называют алгоритмом увеличения амплитуды то есть тот факт, что мы
делаем квантовые преобразования таким образом, чтобы увеличить
вероятность в результате измерения обнаружить правильный ответ.
Квантовая механика дает нам возможность пробовать эти черные ящики,
посылая на них суперпозиции всех возможных состояний. Это то, что
классически трудно себе представитьЦифровые квантовые
симуляторыЦифровые квантовые симуляторы семейство алгоритмов,
которое имеет важное практическое значение. Если Фейнман
сформулировал идею возможности использовать квантовые системы для
моделирования других квантовых систем на уровне концепции, то Сет
Ллойд в работе Universal quantum simulators строго показал, как это
может быть реализовано.Идея в том, что квантовая система
описывается некоторыми уравнениями, и можно точно установить
соответствие между степенями свободы этой системы и кубитами, а
также эволюцией и унитарными преобразованиями, которые над кубитами
нужно совершить. Тем самым можно точно моделировать другие
квантовые системы на квантовом компьютере.Это очень мощная
концептуальная идея, потому что большое количество представляющих
интерес вещей, например материалы и лекарства,на фундаментальном
уровне устроены как сложные квантовые объекты. Моделировать их
классическим образом весьма затратно, на точном квантовом уровне
очень сложно, и это требует колоссальных вычислительных ресурсов. А
в данном случае мы получаем инструмент в виде квантового компьютера
для моделирования любых других квантовых систем. Так что при
появлении квантового компьютера может стать возможным процесс
ускорения получения востребованных химических элементов и
сокращения затрат их производство.Современное состояние и
перспективы развития квантовых алгоритмовСегодня возникают идеи
новых моделей квантовых вычислений и алгоритмов. Например, алгоритм
Ллойда решение систем линейных уравнений на квантовых компьютерах.
Многие новые алгоритмы перечислены на сайте Quantum Algorithm Zoo.
Кроме того, нам необходимо понимание фундаментальных ограничений
квантовых моделей. У нас есть все основания полагать, что квантовый
компьютер какие-то задачи решает хорошо, а какие-то не очень. Но
точного и окончательного описания нет.Также нам нужно адаптировать
квантовые алгоритмы под возможность работы с так называемыми noise
intermediate-scale quantum devices (NISQ) шумными квантовыми
компьютерами промежуточного масштаба, то есть теми квантовыми
компьютерами, которые у нас есть сейчас. У них есть от 50 до 100
кубитов, есть ошибки, но нет способа их коррекции. Есть
предположение, что, даже несмотря на такие ограничения, их уже тоже
можно использовать полезным образом.До сих пор люди демонстрировали
на малых квантовых компьютерах некие базовые принципы. Например,
алгоритмы Дойча в почти всех возможных физических реализациях
квантовых вычислительных устройств, алгоритм Шора для разных чисел
(скажем, 15 и 21) и так далее. Так мы поняли, как работают базовые
принципы этих алгоритмов. И возник вопрос: что делать дальше? Как
задействовать доступные ресурсы квантовых состояний для решения
практических задач?Из этой идеи возникли, например, вариационные
алгоритмы, в которых квантовая часть отвечает за вычисление
значения некоторой целевой функции для данных параметров, которое
потом используется для изменения параметров с помощью классических
алгоритмов оптимизации. Это гибридная квантово-классическая модель,
где для решения задачи мы используем и квантовые процессоры, и
классические алгоритмы, и важно, что она может быть реализована с
использованием NISQ.Есть обоснованная надежда, что в будущем
появятся эффективные способы коррекции ошибоки мы сможем
реализовывать более сложные квантовые алгоритмы, которые не могут
быть реализованы на текущем поколении квантовых вычислительных
устройств. Компания IBM ввела полезную меру мощности квантовых
компьютеров квантовый объем (сочетание количества и качества
кубитов). Сегодня нам нужно растить не только количество кубитов,
но и качество операций с ними, чтобы в идеале добиться когерентных
и безошибочно работающих кубитов.
Стоит отметить, что уже сейчас развиваются альтернативные решения
вроде квантового отжига совокупности методов для решения на
квантовом компьютере задач дискретной оптимизации путем кодирования
исходных данных в некоторую физическую конфигурацию системы.
Устройства квантового отжига производятся компанией D-Wave и
активно используются для прототипирования решения различных
практических задач.Квантовое превосходство и квантовый
компьютерЕсть специфическая категория квантовых алгоритмов,
направленная на демонстрацию так называемого квантового
превосходства, узкоспециализированные квантовые алгоритмы, которые
строятся с целью показать, что квантовый процессор как
вычислительная машина превосходит классический в решении какой-то
задачи. Этим вопросом занималась в том числе исследовательская
команда компания Google. На эту тему было много замечательных
работ, в том числе Скотта Ааронсона (The Computational Complexity
of Linear Optics).В случае работы Google в 2019 году для
демонстрации квантового превосходства была выбрана задача
моделирования случайных квантовых цепочек (random quantum
circuits). Работает это следующим образом. Над достаточно большим
количеством кубитов (в случае Google 53) совершается длинная
последовательность операций (в эксперименте Google более 1500) и
проводится измерение результатов. Получить такие же результаты на
классическом суперкомпьютере будет крайне сложно из-за огромного
пространства состояний.Однако затем начались дебаты вокруг времени,
необходимого для выполнения той же задачи на классическом
компьютере. Некоторые компании, напримерIBM и Alibaba, указали, что
превосходство квантовой системы при определенных условиях может
быть не столь значительным, как об этом заявляли в Google. Поэтому
один из важных аспектов оценки квантовых систем бенчмаркинг
(сравнение). В зависимости от того, с каким классическим аналогом
мы сравниваем квантовые алгоритмы, мы получим разные
сведения.Большая история была связана с машиной канадской компании
D-Wave. Это вообще один из самых обсуждаемых и противоречивых
игроков на рынке квантовых вычислений. Компания D-Wave давно
заявляет, что у них есть квантовый компьютер, который успешно
работает по модели квантового отжига. К D-Wave было много вопросов
на тему того, как вообще понять, что этот квантовый компьютер дает
преимущества над классическим именно за счет квантовых эффектов.
Представители D-Wave приводили детальное сравнение работы их
компьютера с классическим алгоритмом, эмулирующим поведение такой
квантовой системы, и на этом примере заявляли о своих
преимуществах. Правда, люди до сих пор продолжают дискутировать на
эту тему: есть мнение, что квантовые эффекты не играют никакой
роли.Тем не менеев 2015 году команда исследователей, в том числе из
Google, провела детальное сравнение и нашла экспериментальные
свидетельства того, что компьютер D-Wave действительно имеет
преимущество перед классическим вычислителем. В итоге это
исследование (What is the Computational Value of Finite-Range
Tunneling?) стало предвестником демонстрации квантового
превосходства уже компании Google, которое продемонстрировали чуть
позже, в 2019 году,на квантовом процессоре Sycamore.В 2020 году в
эксперименте китайской группы было показано квантовое превосходство
путем решения задачи бозонного сэмплинга. Авторы эксперимента
приводят оценки того, как долго пришлось бы решать эту задачу на
обычном суперкомпьютере там есть два варианта, но речь в любом
случае о миллиардах лет. Это и есть очередная демонстрация
квантового превосходства: квантовый вычислитель решил задачу, для
которой классическому суперкомпьютеру требуется колоссальное
время.Вместо заключенияЧасто задают вопрос Будет ли у нас квантовый
компьютер?.Стоит начать с того, что какие-то квантовые компьютеры
можно использовать уже сейчас: можно программировать квантовые
компьютеры маленького масштаба в образовательных и научных целях,
делать на квантовых компьютерах и симуляторах промежуточного
масштаба научные открытия и прототипировать квантовые алгоритмы.
Вопрос о том, можно ли с помощью текущего поколения квантовых
компьютеров показать ускорение в решении экономически
востребованной задачи, пока открыт.Как мы будем использовать
квантовый компьютер? Общая идея состоит в том, что он станет
дополнительным ускорителем, сопроцессором. Здесь идеология примерно
такая же, как с графическими процессорами, которым мы предоставили
для решения именно графические задачи. Теперь мы знаем, какие
задачи можно выделить в квантовый процессор.Будут ли квантовые
вычислительные устройства не процессорами, а полноценными
компьютерами? Интересный и сложный вопрос. В ближайшее
времянаиболее реалистично думать о них именно как о сопроцессорах
для решения определенных задач. Тем не менеебудущее прогнозировать
сложно, по крайней мере не имея сейчас мощных квантовых
компьютеров.На заре компьютерной эпохи тоже говорили, что миру
будет нужно всего пять компьютеров, и не могли представить себе
приложения, требующего более 637 килобайт оперативной памяти.На
сегодняшний день достигнуты значительные результаты в области
создания методов для управления (манипуляции) квантовым
состояниями. Вообще говоря, базовые задачи квантовых технологий
можно определить так: инициализировать квантовые состояния в
некотором заранее известном квантовом состоянии, управлять ими для
изменения этого состояния, а также иметь возможность измерять
квантовые состояния.
Дополнительные материалыR. Landauer. Irreversibility and Heat
Generation in the Computing Process. IBM JOURNAL, july 1961.Манин
Ю. И. Вычислимое и невычислимое. М.: Советское радио, 1980.Ааронсон
С. Квантовые вычисления со времен Демокрита. М.: Альпина Нон-фикшн,
2017.Нильсен М., Чанг И. Квантовые вычисления и квантовая
информация. М.: Мир, 2006.Прескилл Дж. Квантовая информация и
квантовые вычисления. Том 1-2. Ижевск: РХД, 20082011.
