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

Квантовый алгоритм факторизации целых чисел

Алгоритм Шора — это квантовый алгоритм для нахождения простых множителей целого числа. Он был разработан в 1994 году американским математиком Питером Шором . ^{[1] [2]} Это один из немногих известных квантовых алгоритмов с убедительными потенциальными приложениями и убедительными доказательствами суперполиномиального ускорения по сравнению с наиболее известными классическими (неквантовыми) алгоритмами. ^[3] С другой стороны, факторизация чисел, имеющих практическое значение, требует гораздо больше кубитов , чем будет доступно в ближайшем будущем. ^[4] Другая проблема заключается в том, что шум в квантовых схемах может подорвать результаты, ^[5] требуя дополнительных кубитов для квантовой коррекции ошибок .

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

На квантовом компьютере для факторизации целого числа алгоритм Шора выполняется за полиномиальное время , то есть затраченное время полиномиально по . ^[6] Он требует квантовых вентилей порядка с использованием быстрого умножения, ^[7] или даже с использованием асимптотически самого быстрого алгоритма умножения, известного в настоящее время благодаря Харви и Ван дер Ховену, ^[8] таким образом демонстрируя, что задача факторизации целого числа может быть эффективно решена на квантовом компьютере и, следовательно, находится в классе сложности BQP . Это значительно быстрее, чем самый эффективный известный классический алгоритм факторизации, общее решето числового поля , который работает за субэкспоненциальное время : . ^[9] ${\displaystyle N}$ ${\displaystyle \log N}$ ${\displaystyle O\!\left((\log N)^{2}(\log \log N)(\log \log \log N)\right)}$ ${\displaystyle O\!\left((\log N)^{2}(\log \log N)\right)}$ ${\displaystyle O\!\left(e^{1.9(\log N)^{1/3}(\log \log N)^{2/3}}\right)}$

Осуществимость и воздействие

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

• Схема RSA​
• Обмен ключами Диффи-Хеллмана в конечном поле
• Обмен ключами Диффи-Хеллмана на эллиптической кривой ^[10]

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

Физическая реализация

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

В 2001 году алгоритм Шора был продемонстрирован группой в IBM , которая разложила на , используя реализацию ЯМР квантового компьютера с семью кубитами. ^[11] После реализации IBM две независимые группы реализовали алгоритм Шора с использованием фотонных кубитов, подчеркнув, что при запуске схем алгоритма Шора наблюдалась многокубитная запутанность . ^{[12] [13]} В 2012 году факторизация была выполнена с использованием твердотельных кубитов. ^[14] Позже, в 2012 году, была достигнута факторизация . ^[15] В 2016 году факторизация была выполнена снова с использованием захваченных ионных кубитов с техникой рециркуляции. ^[16] В 2019 году была предпринята попытка факторизовать число с использованием алгоритма Шора на IBM Q System One , но алгоритм не сработал из-за накапливающихся ошибок. ^[17] Однако все эти демонстрации скомпилировали алгоритм, используя предварительное знание ответа, а некоторые даже упростили алгоритм таким образом, что он стал эквивалентен подбрасыванию монеты. ^[18] Кроме того, были предприняты попытки использования квантовых компьютеров с другими алгоритмами. ^[19] Однако эти алгоритмы похожи на классическую проверку факторов методом грубой силы, поэтому, в отличие от алгоритма Шора, они не должны когда-либо работать лучше, чем классические алгоритмы факторизации. ^[20] ${\displaystyle 15}$ ${\displaystyle 3\times 5}$ ${\displaystyle 15}$ ${\displaystyle 21}$ ${\displaystyle 15}$ ${\displaystyle 35}$

Теоретический анализ алгоритма Шора предполагает, что квантовый компьютер свободен от шума и ошибок. Однако практические реализации в ближайшем будущем должны будут иметь дело с такими нежелательными явлениями (когда будет доступно больше кубитов, может помочь квантовая коррекция ошибок ). В 2023 году Цзинь-И Цай показал, что при наличии шума алгоритм Шора асимптотически почти наверняка терпит неудачу для больших полупростых чисел, которые являются произведениями двух простых чисел в последовательности OEIS A073024. ^[5] Эти простые числа обладают свойством иметь простой множитель больше , и имеют положительную плотность в множестве всех простых чисел. Следовательно, для возможности факторизации всех чисел с помощью алгоритма Шора потребуется коррекция ошибок. ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle p^{2/3}}$

Алгоритм

Задача, которую мы пытаемся решить, такова: дано нечетное составное число , найти его целые множители ${\displaystyle N}$ .

Для достижения этого алгоритм Шора состоит из двух частей:

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

Классическая редукция

Полный алгоритм факторизации возможен, если мы сможем эффективно разложить произвольное число на два целых числа и больше 1, поскольку если одно из них или не являются простыми, то алгоритм факторизации можно, в свою очередь, применять к ним до тех пор, пока не останутся только простые числа. ${\displaystyle N}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle q}$

Основное наблюдение заключается в том, что, используя алгоритм Евклида , мы всегда можем эффективно вычислить НОД между двумя целыми числами. В частности, это означает, что мы можем эффективно проверить , является ли четным, в этом случае 2 является тривиальным множителем. Таким образом, предположим, что является нечетным для оставшейся части этого обсуждения. После этого мы можем использовать эффективные классические алгоритмы для проверки, является ли степенью простого числа . ^[21] Для степеней простого числа существуют эффективные классические алгоритмы факторизации, ^[22] поэтому остальная часть квантового алгоритма может предполагать, что не является степенью простого числа. ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$

Если эти простые случаи не дают нетривиального множителя , алгоритм переходит к обработке оставшегося случая. Мы выбираем случайное целое число . Возможный нетривиальный делитель может быть найден путем вычисления , что можно сделать классически и эффективно с помощью алгоритма Евклида . Если это дает нетривиальный множитель (то есть ), алгоритм завершен, а другой нетривиальный множитель равен . Если нетривиальный множитель не был идентифицирован, то это означает, что и выбор являются взаимно простыми , поэтому содержится в мультипликативной группе целых чисел по модулю , имеющей мультипликативную обратную по модулю . Таким образом, имеет мультипликативный порядок по модулю , то есть ${\displaystyle N}$ ${\displaystyle 2\leq a<N}$ ${\displaystyle N}$ ${\displaystyle \gcd(a,N)}$ ${\displaystyle \gcd(a,N)\neq 1}$ ${\textstyle {\frac {N}{\gcd(a,N)}}}$ ${\displaystyle N}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle N}$

${\displaystyle a^{r}\equiv 1{\bmod {N}}}$

и является наименьшим положительным целым числом, удовлетворяющим этому сравнению. ${\displaystyle r}$

Квантовая подпрограмма находит . Это можно увидеть из сравнения, которое делит , записанного . Это можно разложить на множители с помощью разности квадратов : Поскольку мы разложили выражение таким образом, алгоритм не работает для нечетного (потому что должно быть целым числом), то есть алгоритм должен был бы перезапуститься с новым . В дальнейшем мы можем поэтому предположить , что четно. Не может быть так, что , так как это означало бы , что противоречиво означало бы, что будет порядком , который уже был . На этом этапе может быть или не быть так, что . Если неверно, что , то это означает, что мы можем найти нетривиальный множитель . Мы вычисляем Если , то это означает, что было верно, и нетривиальный множитель не может быть достигнут из , и алгоритм должен перезапуститься с новым . В противном случае мы нашли нетривиальный множитель , при этом другой является , и алгоритм завершен. Для этого шага это также эквивалентно вычислению ; он создаст нетривиальный множитель, если нетривиален, и не создаст, если он тривиален (где ). ${\displaystyle r}$ ${\displaystyle N}$ ${\displaystyle a^{r}-1}$ ${\displaystyle N\mid a^{r}-1}$ $${\displaystyle N\mid (a^{r/2}-1)(a^{r/2}+1)}$$ ${\displaystyle r}$ ${\displaystyle a^{r/2}}$ ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle N\mid a^{r/2}-1}$ ${\displaystyle a^{r/2}\equiv 1{\bmod {N}}}$ ${\textstyle {\frac {r}{2}}}$ ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle N\mid a^{r/2}+1}$ ${\displaystyle N\mid a^{r/2}+1}$ ${\displaystyle N}$ $${\displaystyle d=\gcd(N,a^{r/2}-1)}$$ ${\displaystyle d=1}$ ${\displaystyle N\mid a^{r/2}+1}$ ${\displaystyle N}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\textstyle {\frac {N}{d}}}$ ${\displaystyle \gcd(N,a^{r/2}+1)}$ ${\displaystyle \gcd(N,a^{r/2}-1)}$ ${\displaystyle N\mid a^{r/2}+1}$

Алгоритм переформулируется следующим образом: пусть будет нечетным, а не степенью простого числа. Мы хотим вывести два нетривиальных множителя . ${\textstyle N}$ ${\textstyle N}$

1. Выберите случайное число . ${\textstyle 1<a<N}$
2. Вычислите наибольший общий делитель чисел и . ${\displaystyle K=\gcd(a,N)}$ ${\displaystyle a}$ ${\displaystyle N}$
3. Если , то — нетривиальный множитель , а другой множитель — , и на этом мы заканчиваем. ${\displaystyle K\neq 1}$ ${\displaystyle K}$ ${\displaystyle N}$ ${\textstyle {\frac {N}{K}}}$
4. В противном случае используйте квантовую подпрограмму для определения порядка . ${\displaystyle r}$ ${\displaystyle a}$
5. Если нечетное, то вернитесь к шагу 1. ${\displaystyle r}$
6. Вычислить . Если нетривиально, то другой фактор — , и мы закончили. В противном случае вернуться к шагу 1. ${\displaystyle g=\gcd(N,a^{r/2}+1)}$ ${\displaystyle g}$ ${\textstyle {\frac {N}{g}}}$

Было показано, что это, скорее всего, будет успешным после нескольких запусков. ^[2] На практике, одного вызова подпрограммы нахождения квантового порядка достаточно, чтобы полностью факторизовать с очень высокой вероятностью успеха, если использовать более продвинутую редукцию. ^[23] ${\displaystyle N}$

Подпрограмма нахождения квантового порядка

Цель квантовой подпрограммы алгоритма Шора — при наличии взаимно простых целых чисел и найти порядок по модулю , который является наименьшим положительным целым числом, таким что . Для достижения этой цели алгоритм Шора использует квантовую схему, включающую два регистра. Второй регистр использует кубиты, где — наименьшее целое число, такое что , т. е . . Размер первого регистра определяет точность приближения, которое выдает схема. Можно показать, что использование кубитов дает достаточную точность для нахождения . Точная квантовая схема зависит от параметров и , которые определяют задачу. В следующем описании алгоритма для обозначения квантовых состояний и для обозначения тензорного произведения используется обозначение скобок , а не логическое И . ${\displaystyle N}$ ${\displaystyle 1<a<N}$ ${\displaystyle r}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle a^{r}\equiv 1{\pmod {N}}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle N\leq 2^{n}}$ ${\displaystyle n=\left\lceil {\log _{2}N}\right\rceil }$ ${\displaystyle 2n+1}$ ${\displaystyle r}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle \otimes }$

Алгоритм состоит из двух основных этапов:

1. Используйте квантовую фазовую оценку с унитарным представлением операции умножения на (по модулю ), и входное состояние (где второй регистр состоит из кубитов). Собственные значения этого кодируют информацию о периоде и могут быть записаны как сумма его собственных векторов. Благодаря этим свойствам этап квантовой фазовой оценки дает на выходе случайное целое число вида для случайного . ${\displaystyle U}$ ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle |0\rangle ^{\otimes 2n+1}\otimes |1\rangle }$ ${\displaystyle |1\rangle }$ ${\displaystyle n}$ ${\displaystyle U}$ ${\displaystyle |1\rangle }$ ${\displaystyle {\frac {j}{r}}2^{2n+1}}$ ${\displaystyle j=0,1,...,r-1}$
2. Используйте алгоритм непрерывных дробей для извлечения периода из результатов измерений, полученных на предыдущем этапе. Это процедура постобработки (с помощью классического компьютера) данных измерений, полученных при измерении выходных квантовых состояний, и извлечения периода. ${\displaystyle r}$

Связь с квантовой фазовой оценкой не обсуждалась в первоначальной формулировке алгоритма Шора ^[2] , но была позднее предложена Китаевым ^{[24] .}

Оценка квантовой фазы

Квантовая подпрограмма в алгоритме Шора

В общем случае алгоритм квантовой оценки фазы для любого унитарного и собственного состояния , такого что , отправляет входные состояния в выходные состояния, близкие к , где — целое число, близкое к . Другими словами, он отправляет каждое собственное состояние в состояние, близкое к соответствующему собственному значению. Для целей квантового поиска порядка мы используем эту стратегию, используя унитарное значение, определенное действием Действие на состояния с не имеет решающего значения для функционирования алгоритма, но должно быть включено, чтобы гарантировать, что общее преобразование является четко определенным квантовым вентилем. Реализация схемы для квантовой оценки фазы с требует возможности эффективной реализации вентилей . Этого можно достичь с помощью модульного возведения в степень , что является самой медленной частью алгоритма. Таким образом определенный вентиль удовлетворяет , что немедленно подразумевает, что его собственные значения являются корнями -й степени из единицы . Кроме того, каждое собственное значение имеет собственный вектор вида , и эти собственные векторы таковы, что ${\displaystyle U}$ ${\displaystyle |\psi \rangle }$ ${\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle }$ ${\displaystyle |0\rangle |\psi \rangle }$ ${\displaystyle |\phi \rangle |\psi \rangle }$ ${\displaystyle \phi }$ ${\displaystyle 2^{2n+1}\theta }$ ${\displaystyle |\psi _{j}\rangle }$ ${\displaystyle U}$ $${\displaystyle U|k\rangle ={\begin{cases}|ak{\pmod {N}}\rangle &0\leq k<N,\\|k\rangle &N\leq k<2^{n}.\end{cases}}}$$ ${\displaystyle U}$ ${\displaystyle |k\rangle }$ ${\displaystyle N\leq k<2^{n}}$ ${\displaystyle U}$ ${\displaystyle U^{2^{j}}}$ ${\displaystyle U^{r}=I}$ ${\displaystyle r}$ ${\displaystyle \omega _{r}^{k}=e^{2\pi ik/r}}$ ${\displaystyle \omega _{r}^{j}}$ ${\textstyle |\psi _{j}\rangle =r^{-1/2}\sum _{k=0}^{r-1}\omega _{r}^{-kj}|a^{k}\rangle }$ $${\displaystyle {\begin{aligned}{\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\psi _{j}\rangle &={\frac {1}{r}}\sum _{j=0}^{r-1}\sum _{k=0}^{r-1}\omega _{r}^{jk}|a^{k}\rangle \\&=|1\rangle +{\frac {1}{r}}\sum _{k=1}^{r-1}\left(\sum _{j=0}^{r-1}\omega _{r}^{jk}\right)|a^{k}\rangle =|1\rangle ,\end{aligned}}}$$

где последнее тождество следует из формулы геометрической прогрессии , которая подразумевает . ${\textstyle \sum _{j=0}^{r-1}\omega _{r}^{jk}=0}$

Использование квантовой оценки фазы на входном состоянии затем вернет целое число с высокой вероятностью. Точнее, схема квантовой оценки фазы отправляет в так, что результирующее распределение вероятностей достигает пика около , с . Эту вероятность можно сделать произвольно близкой к 1, используя дополнительные кубиты. ${\displaystyle |0\rangle ^{\otimes 2n+1}|\psi _{j}\rangle }$ ${\displaystyle 2^{2n+1}j/r}$ ${\displaystyle |0\rangle ^{\otimes 2n+1}|\psi _{j}\rangle }$ ${\displaystyle |\phi _{j}\rangle |\psi _{j}\rangle }$ ${\displaystyle p_{k}\equiv |\langle k|\phi _{j}\rangle |^{2}}$ ${\textstyle k=2^{2n+1}j/r}$ ${\textstyle p_{2^{2n+1}j/r}\geq {\frac {4}{\pi ^{2}}}\approx 0.4053}$

Применяя приведенные выше рассуждения к входным данным , квантовая фазовая оценка приводит к эволюции. Измеряя первый регистр, теперь у нас есть сбалансированная вероятность нахождения каждого , каждый из которых дает целочисленное приближение к , которое можно разделить на , чтобы получить десятичное приближение для . ${\displaystyle |0\rangle ^{\otimes 2n+1}|1\rangle }$ $${\displaystyle |0\rangle ^{\otimes 2n}|1\rangle ={\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|0\rangle ^{\otimes 2n}|\psi _{j}\rangle \to {\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\phi _{j}\rangle |\psi _{j}\rangle .}$$ ${\displaystyle 1/r}$ ${\displaystyle |\phi _{j}\rangle }$ ${\displaystyle 2^{2n+1}j/r}$ ${\displaystyle 2^{2n+1}}$ ${\displaystyle j/r}$

Алгоритм непрерывной дроби для извлечения периода

Затем мы применяем алгоритм непрерывных дробей для поиска целых чисел и , где дает наилучшее приближение дроби для приближения, измеренного из схемы, для и взаимно просты и . Количество кубитов в первом регистре, , которое определяет точность приближения, гарантирует, что заданное наилучшее приближение из суперпозиции было измерено ^[2] (что можно сделать произвольно вероятным, используя дополнительные биты и усекая вывод). Однако, хотя и являются взаимно простыми, может случиться так, что и не являются взаимно простыми. Из-за этого и могли потерять некоторые множители, которые были в и . Это можно исправить, повторно запустив подпрограмму нахождения квантового порядка произвольное количество раз, чтобы получить список приближений дроби, где — количество запусков подпрограммы. Каждое из них будет иметь различные множители, поскольку схема (вероятно) измерит несколько различных возможных значений . Чтобы восстановить фактическое значение, мы можем взять наименьшее общее кратное каждого : Наименьшее общее кратное будет порядком исходного целого числа с высокой вероятностью. На практике, одного запуска подпрограммы нахождения квантового порядка, как правило, достаточно, если используется более продвинутая постобработка. ^[25] ${\textstyle b}$ ${\textstyle c}$ ${\textstyle {\frac {b}{c}}}$ ${\textstyle b,c<N}$ ${\textstyle b}$ ${\textstyle c}$ ${\displaystyle 2n+1}$ $${\displaystyle {\frac {b}{c}}={\frac {j}{r}}}$$ ${\textstyle |\phi _{j}\rangle }$ ${\textstyle b}$ ${\textstyle c}$ ${\textstyle j}$ ${\textstyle r}$ ${\textstyle b}$ ${\textstyle c}$ ${\textstyle j}$ ${\textstyle r}$ $${\displaystyle {\frac {b_{1}}{c_{1}}}_{\textstyle ,}\;{\frac {b_{2}}{c_{2}}}_{\textstyle ,}\ldots {\vphantom {\frac {b_{1}}{c_{1}}}}_{\textstyle ,}\;{\frac {b_{s}}{c_{s}}}}$$ ${\textstyle s}$ ${\textstyle c_{k}}$ ${\textstyle j}$ ${\textstyle r}$ ${\textstyle c_{k}}$ $${\displaystyle \mathrm {lcm} (c_{1},c_{2},\ldots ,c_{s})}$$ ${\textstyle r}$ ${\textstyle a}$

Выбор размера первого регистра

Оценка фазы требует выбора размера первого регистра для определения точности алгоритма, а для квантовой подпрограммы алгоритма Шора кубитов достаточно, чтобы гарантировать, что оптимальная битовая строка, измеренная на основе оценки фазы (то есть где является наиболее точным приближением фазы из оценки фазы), позволит восстановить фактическое значение . ${\displaystyle 2n+1}$ ${\displaystyle |k\rangle }$ ${\textstyle k/2^{2n+1}}$ ${\displaystyle r}$

Каждое измерение до в алгоритме Шора представляет собой суперпозицию целых чисел, приближающихся к . Пусть представляет собой наиболее оптимальное целое число в . Следующая теорема гарантирует, что алгоритм непрерывных дробей восстановится из : ${\displaystyle |\phi _{j}\rangle }$ ${\displaystyle 2^{2n+1}j/r}$ ${\displaystyle |k\rangle }$ ${\displaystyle |\phi _{j}\rangle }$ ${\displaystyle j/r}$ ${\displaystyle k/2^{2{n}+1}}$

Теорема  —  Если и являются целыми битами, то алгоритм цепных дробей, запущенный на, восстановит как и . ${\displaystyle j}$ ${\displaystyle r}$ ${\displaystyle n}$ $${\displaystyle \left\vert {\frac {j}{r}}-\phi \right\vert \leq {\frac {1}{2r^{2}}}}$$ ${\displaystyle \phi }$ ${\textstyle {\frac {j}{\gcd(j,\;r)}}}$ ${\textstyle {\frac {r}{\gcd(j,\;r)}}}$

^[3] Как и оптимальная битовая строка из оценки фазы, имеет точность до бит . Таким образом, это означает, что алгоритм непрерывных дробей восстановит и (или с их наибольшим общим делителем, вычтенным из). ${\displaystyle k}$ ${\displaystyle k/2^{2{n}+1}}$ ${\displaystyle j/r}$ ${\displaystyle 2n+1}$ $${\displaystyle \left\vert {\frac {j}{r}}-{\frac {k}{2^{2n+1}}}\right\vert \leq {\frac {1}{2^{2{n}+1}}}\leq {\frac {1}{2N^{2}}}\leq {\frac {1}{2r^{2}}}}$$ ${\displaystyle j}$ ${\displaystyle r}$

Узкое место

Узким местом времени выполнения алгоритма Шора является квантовое модульное возведение в степень , которое намного медленнее, чем квантовое преобразование Фурье и классическая предварительная/постобработка. Существует несколько подходов к построению и оптимизации схем для модульного возведения в степень. Самый простой и (в настоящее время) наиболее практичный подход — имитировать обычные арифметические схемы с обратимыми вентилями , начиная с сумматоров с непрерывным переносом . Знание основания и модуля возведения в степень облегчает дальнейшую оптимизацию. ^{[26] [27]} Обратимые схемы обычно используют порядка вентилей для кубитов. Альтернативные методы асимптотически улучшают количество вентилей, используя квантовые преобразования Фурье , но не могут конкурировать с менее чем 600 кубитами из-за высоких констант. ${\displaystyle n^{3}}$ ${\displaystyle n}$

Нахождение периода и дискретные логарифмы

Алгоритмы Шора для задач дискретного журнала и поиска порядка являются примерами алгоритма, решающего задачу поиска периода. ^{[ требуется ссылка ]} . Все три являются примерами задачи скрытой подгруппы .

Алгоритм Шора для дискретных логарифмов

Дана группа с порядком и генератором , предположим, что мы знаем , что для некоторого , и мы хотим вычислить , который является дискретным логарифмом : . Рассмотрим абелеву группу , где каждый фактор соответствует модульному сложению значений. Теперь рассмотрим функцию ${\displaystyle G}$ ${\displaystyle p}$ ${\displaystyle g\in G}$ ${\displaystyle x=g^{r}\in G}$ ${\displaystyle r\in \mathbb {Z} _{p}}$ ${\displaystyle r}$ ${\displaystyle r={\log _{g}}(x)}$ ${\displaystyle \mathbb {Z} _{p}\times \mathbb {Z} _{p}}$

${\displaystyle f\colon \mathbb {Z} _{p}\times \mathbb {Z} _{p}\to G\;;\;f(a,b)=g^{a}x^{-b}.}$

Это дает нам задачу абелевой скрытой подгруппы , где соответствует гомоморфизму группы . Ядро соответствует кратным . Таким образом, если мы можем найти ядро, мы можем найти . Существует квантовый алгоритм для решения этой задачи. Этот алгоритм, как и алгоритм нахождения множителей, принадлежит Питеру Шору, и оба они реализованы путем создания суперпозиции с использованием вентилей Адамара, за которым следует реализация в виде квантового преобразования, за которым следует квантовое преобразование Фурье. ^[3] В связи с этим квантовый алгоритм для вычисления дискретного логарифма также иногда называют «алгоритмом Шора». ${\displaystyle f}$ ${\displaystyle (r,1)}$ ${\displaystyle r}$ ${\displaystyle f}$

Проблему нахождения порядка можно также рассматривать как проблему скрытой подгруппы. ^[3] Чтобы увидеть это, рассмотрим группу целых чисел при сложении, и для заданного, такого что: , функция ${\displaystyle a\in \mathbb {Z} }$ ${\displaystyle a^{r}=1}$

${\displaystyle f\colon \mathbb {Z} \to \mathbb {Z} \;;\;f(x)=a^{x},\;f(x+r)=f(x).}$

Для любой конечной абелевой группы существует квантовый алгоритм для решения скрытой подгруппы за полиномиальное время. ^[3] ${\displaystyle G}$ ${\displaystyle G}$

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

• GEECM , алгоритм факторизации, который, как говорят, «часто намного быстрее, чем алгоритм Шора» ^[28]
• Алгоритм Гровера

Ссылки

1. Шор, П. В. (1994). «Алгоритмы для квантовых вычислений: дискретные логарифмы и факторизация». Труды 35-го ежегодного симпозиума по основам компьютерной науки . стр. 124–134. doi :10.1109/sfcs.1994.365700. ISBN 978-0-8186-6580-6.
2. Шор, Питер В. (октябрь 1997 г.). «Алгоритмы полиномиального времени для разложения на простые множители и дискретных логарифмов на квантовом компьютере». Журнал SIAM по вычислениям . 26 (5): 1484–1509. arXiv : quant-ph/9508027 . doi : 10.1137/S0097539795293172. S2CID  2337707.
3. Нильсен, Майкл А.; Чуан, Айзек Л. (9 декабря 2010 г.). Квантовые вычисления и квантовая информация (PDF) (7-е изд.). Cambridge University Press. ISBN 978-1-107-00217-3. Архивировано (PDF) из оригинала 2019-07-11 . Получено 24 апреля 2022 .
4. Гидни, Крейг; Экера, Мартин (2021). «Как факторизовать 2048-битные целые числа RSA за 8 часов, используя 20 миллионов шумных кубитов». Quantum . 5 : 433. arXiv : 1905.09749 . Bibcode :2021Quant...5..433G. doi :10.22331/q-2021-04-15-433. S2CID  162183806.
5. Cai, Jin-Yi (2024). «Алгоритм Шора не факторизует большие целые числа при наличии шума». Science China Information Sciences . 67 (7). arXiv : 2306.10072 . doi :10.1007/s11432-023-3961-3.
6. См. также псевдополиномиальное время .
7. Бекман, Дэвид; Чари, Амалавойал Н.; Девабхактуни, Шрикришна; Прескилл, Джон (август 1996 г.). «Эффективные сети для квантовой факторизации». Physical Review A. 54 ( 2): 1034–1063. arXiv : quant-ph/9602016 . Bibcode : 1996PhRvA..54.1034B. doi : 10.1103/physreva.54.1034. PMID  9913575.
8. Харви, Дэвид; ван дер Хувен, Йорис (март 2021 г.). «Целочисленное умножение за время O (n log n)» (PDF) . Annals of Mathematics . 193 (2). doi :10.4007/annals.2021.193.2.4.
9. "Number Field Sieve". wolfram.com . Получено 23 октября 2015 г. .
10. Roetteler, Martin; Naehrig, Michael; Svore, Krysta M .; Lauter, Kristin E. (2017). «Оценки квантовых ресурсов для вычисления дискретных логарифмов эллиптических кривых». В Takagi, Tsuyoshi; Peyrin, Thomas (ред.). Advances in Cryptology – ASIACRYPT 2017 – 23-я Международная конференция по теории и применению криптологии и информационной безопасности, Гонконг, Китай, 3–7 декабря 2017 г., Труды, часть II . Lecture Notes in Computer Science. Vol. 10625. Springer. pp. 241–270. arXiv : 1706.06752 . doi :10.1007/978-3-319-70697-9_9. ISBN 978-3-319-70696-2.
11. Вандерсипен, Ливен МК; Штеффен, Маттиас; Брейта, Грегори; Яннони, Костантино С.; Шервуд, Марк Х.; Чуан, Айзек Л. (декабрь 2001 г.). «Экспериментальная реализация квантового алгоритма факторизации Шора с использованием ядерного магнитного резонанса». Nature . 414 (6866): 883–887. arXiv : quant-ph/0112176 . Bibcode :2001Natur.414..883V. doi :10.1038/414883a. PMID  11780055.
12. Лу, Чао-Ян; Браун, Дэниел Э.; Ян, Тао; Пан, Цзянь-Вэй (19 декабря 2007 г.). «Демонстрация скомпилированной версии алгоритма квантовой факторизации Шора с использованием фотонных кубитов». Physical Review Letters . 99 (25): 250504. arXiv : 0705.1684 . Bibcode :2007PhRvL..99y0504L. doi :10.1103/PhysRevLett.99.250504. PMID  18233508.
13. Lanyon, BP; Weinhold, TJ; Langford, NK; Barbieri, M.; James, DFV; Gilchrist, A.; White, AG (19 декабря 2007 г.). "Экспериментальная демонстрация скомпилированной версии алгоритма Шора с квантовой запутанностью". Physical Review Letters . 99 (25): 250505. arXiv : 0705.1398 . Bibcode : 2007PhRvL..99y0505L. doi : 10.1103/PhysRevLett.99.250505. PMID  18233509.
14. Лусеро, Эрик; Барендс, Рами; Чен, Ю; Келли, Джулиан; Мариантони, Маттео; Мегрант, Энтони; О'Мэлли, Питер; Санк, Дэниел; Вайнсенчер, Амит; Веннер, Джеймс; Уайт, Тед; Инь, И; Клеланд, Эндрю Н.; Мартинис, Джон М. (2012). "Вычисление простых множителей с помощью квантового процессора с фазовым кубитом Джозефсона". Nature Physics . 8 (10): 719. arXiv : 1202.5707 . Bibcode :2012NatPh...8..719L. doi :10.1038/nphys2385. S2CID  44055700.
15. Мартин-Лопес, Энрике; Мартин-Лопес, Энрике; Лэнг, Энтони; Лоусон, Томас; Альварес, Роберто; Чжоу, Сяо-Ци; О'Брайен, Джереми Л. (12 октября 2012 г.). «Экспериментальная реализация алгоритма квантовой факторизации Шора с использованием рециркуляции кубитов». Nature Photonics . 6 (11): 773–776. arXiv : 1111.4147 . Bibcode :2012NaPho...6..773M. doi :10.1038/nphoton.2012.259. S2CID  46546101.
16. Monz, Thomas; Nigg, Daniel; Martinez, Esteban A.; Brandl, Matthias F.; Schindler, Philipp; Rines, Richard; Wang, Shannon X.; Chuang, Isaac L.; Blatt, Rainer (4 марта 2016 г.). «Реализация масштабируемого алгоритма Шора». Science . 351 (6277): 1068–1070. arXiv : 1507.08852 . Bibcode :2016Sci...351.1068M. doi :10.1126/science.aad9480. PMID  26941315. S2CID  17426142.
17. Амико, Мирко; Салим, Зайн Х.; Камф, Мьюир (8 июля 2019 г.). «Экспериментальное исследование алгоритма факторизации Шора с использованием IBM Q Experience». Physical Review A. 100 ( 1): 012305. arXiv : 1903.00768 . Bibcode : 2019PhRvA.100a2305A. doi : 10.1103/PhysRevA.100.012305. S2CID  92987546.
18. Смолин, Джон А.; Смит, Грэм; Варго, Александр (июль 2013 г.). «Сверхупрощение квантовой факторизации». Nature . 499 (7457): 163–165. arXiv : 1301.7007 . Bibcode :2013Natur.499..163S. doi :10.1038/nature12290. PMID  23846653.
19. Карамлоу, Амир Х.; Саймон, Уильям А.; Катабарва, Амара; Шолтен, Трэвис Л.; Перопадре, Борха; Као, Юдун (28 октября 2021 г.). «Анализ производительности вариационной квантовой факторизации на сверхпроводящем квантовом процессоре». npj Quantum Information . 7 (1): 156. arXiv : 2012.07825 . Bibcode : 2021npjQI...7..156K. doi : 10.1038/s41534-021-00478-z.
20. "Квантовые вычисления мотт-энд-бейли". Shtetl-Optimized . 2019-12-28 . Получено 2021-11-15 .
21. Бернстайн, Дэниел (1998). «Обнаружение совершенных степеней за существенно линейное время». Математика вычислений . 67 (223): 1253–1283. doi :10.1090/S0025-5718-98-00952-1.
22. например, вычисление первых корней , например, методом Ньютона и проверка каждого целочисленного результата на простоту ( тест на простоту AKS ). ${\displaystyle \log _{2}(N)}$ ${\displaystyle N}$
23. Экера, Мартин (июнь 2021 г.). «О полной эффективной факторизации любого целого числа за один запуск алгоритма поиска порядка». Квантовая обработка информации . 20 (6): 205. arXiv : 2007.10044 . Bibcode : 2021QuIP...20..205E. doi : 10.1007/s11128-021-03069-1 .
24. Китаев, А. Ю. (1995). «Квантовые измерения и проблема абелева стабилизатора». arXiv : quant-ph/9511026 .
25. Экера, Мартин (май 2024 г.). «О вероятности успеха нахождения квантового порядка». Труды ACM по квантовым вычислениям . 5 (2): 1–40. arXiv : 2201.07791 . doi : 10.1145/3655026 .
26. Марков, Игорь Л.; Саиди, Мехди (2012). «Константно-оптимизированные квантовые схемы для модульного умножения и возведения в степень». Квантовая информация и вычисления . 12 (5–6): 361–394. arXiv : 1202.6614 . Bibcode :2012arXiv1202.6614M. doi :10.26421/QIC12.5-6-1. S2CID  16595181.
27. Марков, Игорь Л.; Саиди, Мехди (2013). "Быстрая факторизация квантовых чисел с помощью синтеза цепей". Phys. Rev. A. 87 ( 1): 012310. arXiv : 1301.3210 . Bibcode : 2013PhRvA..87a2310M. doi : 10.1103/PhysRevA.87.012310. S2CID  2246117.
28. Бернстайн, Дэниел Дж.; Хенингер, Надя; Лу, Пол; Валента, Люк (2017). «Постквантовый RSA». Постквантовая криптография . Конспект лекций по информатике. Том 10346. С. 311–329. doi :10.1007/978-3-319-59879-6_18. ISBN 978-3-319-59878-9.

Дальнейшее чтение

• Нильсен, Майкл А.; Чуан, Айзек Л. (2010). Квантовые вычисления и квантовая информация: 10-е юбилейное издание . Cambridge University Press. ISBN 978-1-107-00217-3.
• Кей, Филлип; Лафламм, Рэймонд; Моска, Мишель (2006). Введение в квантовые вычисления . doi :10.1093/oso/9780198570004.001.0001. ISBN 978-0-19-857000-4.
• «Объяснение для обывателя» Скотта Ааронсона , «одобренное» Питером Шором. (Шор написал: «Отличная статья, Скотт! Это лучшая работа по объяснению квантовых вычислений обывателю, которую я видел».). Альтернативная метафора для QFT была представлена ​​в одном из комментариев. Скотт Ааронсон предлагает следующие 12 ссылок для дальнейшего чтения (из «10 ^{10 5000} руководств по квантовым алгоритмам, которые уже есть в сети.»):
• Шор, Питер В. (1997), «Алгоритмы полиномиального времени для разложения на простые множители и дискретных логарифмов на квантовом компьютере», SIAM J. Comput. , 26 (5): 1484–1509, arXiv : quant-ph/9508027v2 , Bibcode : 1999SIAMR..41..303S, doi : 10.1137/S0036144598347011. Переработанная версия оригинальной статьи Питера Шора («28 страниц, LaTeX. Это расширенная версия статьи, опубликованной в Трудах 35-го ежегодного симпозиума по основам компьютерной науки, Санта-Фе, Нью-Мексико, 20–22 ноября 1994 г. Незначительные изменения внесены в январе 1996 г.»).
• Квантовые вычисления и алгоритм Шора, страница Мэтью Хейворда «Квантовые алгоритмы», 17.02.2005, imsa.edu, версия LaTeX2HTML исходного документа LaTeX, также доступная в формате PDF или PostScript.
• Квантовые вычисления и алгоритм факторизации Шора, Рональд де Вольф, CWI и Амстердамский университет, 12 января 1999 г., 9-страничный постскриптум.
• Алгоритм факторизации Шора, заметки с лекции 9 в Беркли CS 294–2, от 4 октября 2004 г., 7-страничный постскриптум.
• Глава 6. Квантовые вычисления. Архивировано 30 апреля 2020 г. в Wayback Machine , 91-страничный постскриптум, Caltech, Preskill, PH229.
• Квантовые вычисления: учебник Сэмюэля Л. Браунштейна.
• Квантовые состояния алгоритма Шора, Нил Янг, Последнее изменение: Вт Май 21 11:47:38 1996.
• III. Взлом шифрования RSA с помощью квантового компьютера: алгоритм факторизации Шора, заметки лекций по квантовым вычислениям, Корнелльский университет, физика 481–681, CS 483; весна 2006 г., Н. Дэвид Мермин. Последняя редакция 28.03.2006, 30-страничный документ PDF.
• Lavor, C.; Manssur, LRU; Portugal, R. (2003). "Алгоритм Шора для факторизации больших целых чисел". arXiv : quant-ph/0303175 .
• Ломонако, младший (2000). «Квантовый алгоритм факторизации Шора». arXiv : quant-ph/0010034 . Данная статья представляет собой письменную версию часовой лекции, посвященной квантовому алгоритму факторизации Питера Шора. 22 страницы.
• Глава 20 Квантовые вычисления, из Computational Complexity: A Modern Approach , Черновик книги: Датировано январем 2007 г., Санджив Арора и Боаз Барак, Принстонский университет. Опубликовано как Глава 10 Квантовые вычисления из книги Санджив Арора, Боаз Барак, "Computational Complexity: A Modern Approach", Cambridge University Press, 2009, ISBN 978-0-521-42426-4 
• Шаг к квантовым вычислениям: запутывание 10 миллиардов частиц. Архивировано 20 января 2011 г. на Wayback Machine , из журнала «Discover Magazine» от 19 января 2011 г.
• Йозеф Грушка - Проблемы квантовых вычислений также в неограниченной математике: 2001 и далее, редакторы Бьорн Энгквист, Вильфрид Шмид, Springer, 2001, ISBN 978-3-540-66913-5 

Внешние ссылки

• Версия 1.0.0 libquantum: содержит реализацию алгоритма Шора на языке C с библиотекой имитируемого квантового компьютера, но переменная ширины в shor.c должна быть установлена ​​на 1 для улучшения сложности выполнения.
• PBS Infinite Series сняли два видеоролика, объясняющих математику, лежащую в основе алгоритма Шора: «Как взломать криптографию» и «Взлом на квантовой скорости с помощью алгоритма Шора».
• Полная реализация алгоритма Шора с помощью Classiq