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

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

Алгоритм Шора — это квантовый алгоритм нахождения простых множителей целого числа. Он был разработан в 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] В 2019 году была предпринята попытка факторизовать число с использованием алгоритма Шора на IBM Q System One , но алгоритм не удался из-за накопления ошибок. ^[16] Хотя квантовые компьютеры разлагают большие числа с использованием других алгоритмов, ^[17] эти алгоритмы аналогичны классической проверке факторов методом перебора, поэтому, в отличие от алгоритма Шора, от них не ожидается, что они когда-либо будут работать лучше, чем классические алгоритмы факторизации. ^[18] ${\displaystyle 15}$ ${\displaystyle 3\times 5}$ ${\displaystyle 15}$ ${\displaystyle 21}$ ${\displaystyle 35}$

Теоретический анализ алгоритма Шора предполагает, что квантовый компьютер свободен от шума и ошибок. Однако в ближайшем будущем практическим реализациям придется иметь дело с такими нежелательными явлениями (когда будет доступно больше кубитов, квантовая коррекция ошибок может помочь). В 2023 году Джин-И Цай изучил влияние шума и пришел к выводу, что существует особый класс чисел (произведения двух простых чисел из A073024, плотных в полупростых числах), алгоритм Шора не может факторизовать такие числа при наличии шума. ^[5] Следовательно, чтобы иметь возможность факторизовать все числа с помощью алгоритма Шора, потребуется коррекция ошибок.

Алгоритм

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

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

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

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

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

Основное наблюдение заключается в том, что, используя алгоритм Евклида , мы всегда можем эффективно вычислить НОД между двумя целыми числами. В частности, это означает, что мы можем эффективно проверить , является ли число четным, и в этом случае 2 тривиально является фактором. Итак, давайте предположим, что это странно для оставшейся части обсуждения. После этого мы можем использовать эффективные классические алгоритмы, чтобы проверить, является ли это степенью простого числа . ^[19] Для простых степеней существуют эффективные классические алгоритмы факторизации, ^[20] поэтому остальная часть квантового алгоритма может предполагать, что это не простая степень. ${\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 r}$ ${\displaystyle a}$

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

Квантовая подпрограмма требует, чтобы и были взаимно простыми, ^[2] что верно, поскольку на этом этапе алгоритма не создается нетривиальный множитель . Это видно из сравнения, которое делит , написанное . Это можно факторизовать, используя разность квадратов : ${\displaystyle a}$ ${\displaystyle N}$ ${\displaystyle \gcd(a,N)}$ ${\displaystyle N}$ ${\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}$

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

1. Выберите случайное число . ${\displaystyle 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] На практике одного вызова подпрограммы поиска квантового порядка достаточно для полного факторинга с очень высокой вероятностью успеха, если использовать более продвинутую редукцию. ^[21] ${\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] , но была позже предложена Китаевым. ^[22]

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

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

В общем, алгоритм оценки квантовой фазы для любого унитарного и собственного состояния , такого, что , отправляет входные состояния в выходные состояния, близкие к , где – целое число, близкое к . Другими словами, он переводит каждое собственное состояние в состояние, близкое к соответствующему собственному значению. Для целей нахождения квантового порядка мы используем эту стратегию, используя унитарную единицу, определяемую действием ${\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}^{k}}$ ${\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}$

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

Затем мы применяем алгоритм непрерывных дробей для поиска целых чисел и , где дает наилучшее приближение дроби для приближения, измеренного по схеме, для и взаимно простые и . Число кубитов в первом регистре , определяющее точность аппроксимации, гарантирует, что ${\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}$

Узкое место

Узким местом алгоритма Шора во время выполнения является квантовое модульное возведение в степень , которое намного медленнее, чем квантовое преобразование Фурье и классическая пред-/пост-обработка. Существует несколько подходов к построению и оптимизации схем модульного возведения в степень. Самый простой и (на данный момент) наиболее практичный подход — имитировать обычные арифметические схемы с обратимыми вентилями , начиная с сумматоров с пульсирующим переносом . Знание базы и модуля возведения в степень облегчает дальнейшую оптимизацию. ^{[23] [24]} В обратимых схемах обычно используются элементы порядка элементов для кубитов. Альтернативные методы асимптотически улучшают количество вентилей за счет использования квантовых преобразований Фурье , но не могут конкурировать с кубитами менее 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 , алгоритм факторизации, который, как говорят, «часто намного быстрее, чем алгоритм Шора» ^[25]
• Алгоритм Гровера

Рекомендации

1. Шор, PW (1994). «Алгоритмы квантовых вычислений: дискретные логарифмы и факторинг». Материалы 35-го ежегодного симпозиума по основам информатики . IEEE-компьютер. Соц. Нажимать. стр. 124–134. дои : 10.1109/sfcs.1994.365700. ISBN 0818665807. S2CID  15291489.
2. Шор, Питер В. (октябрь 1997 г.). «Алгоритмы полиномиального времени для простой факторизации и дискретных логарифмов на квантовом компьютере». SIAM Journal по вычислительной технике . 26 (5): 1484–1509. arXiv : Quant-ph/9508027 . дои : 10.1137/S0097539795293172. ISSN  0097-5397. S2CID  2337707.
3. Nielsen, Майкл А.; Чуанг, Исаак Л. (9 декабря 2010 г.). Квантовые вычисления и квантовая информация (PDF) (7-е изд.). Издательство Кембриджского университета. ISBN 978-1-107-00217-3. Архивировано (PDF) из оригинала 11 июля 2019 г. Проверено 24 апреля 2022 г.
4. Гидни, Крейг; Экеро, Мартин (2021). «Как разложить 2048-битные целые числа RSA за 8 часов, используя 20 миллионов шумных кубитов». Квантовый . 5 : 433. arXiv : 1905.09749 . Бибкод : 2021Количество...5..433G. doi : 10.22331/q-2021-04-15-433. S2CID  162183806.
5. cai, Джин-И (15 июня 2023 г.). «Алгоритм Шора не учитывает большие целые числа при наличии шума». arXiv : 2306.10072 [квант-ph].
6. См. также псевдополиномиальное время .
7. Бекман, Дэвид; Чари, Амалавоял Н.; Девабхактуни, Шрикришна; Прескилл, Джон (1996). «Эффективные сети для квантового факторинга» (PDF) . Физический обзор А. 54 (2): 1034–1063. arXiv : Quant-ph/9602016 . Бибкод : 1996PhRvA..54.1034B. doi :10.1103/PhysRevA.54.1034. PMID  9913575. S2CID  2231795.
8. Харви, Дэвид; ван дер Хувен, Йорис (2020). «Умножение целых чисел за время O(n log n)». Анналы математики . дои : 10.4007/анналы.2021.193.2.4. S2CID  109934776.
9. "Сито числового поля" . www.wolfram.com . Проверено 23 октября 2015 г.
10. Реттелер, Мартин; Наэриг, Майкл; Своре, Криста М .; Лаутер, Кристин Э. (2017). «Оценки квантовых ресурсов для вычисления дискретных логарифмов на эллиптических кривых». В Такаги, Цуёси; Пейрин, Томас (ред.). Достижения в криптологии – ASIACRYPT 2017 – 23-я Международная конференция по теории и применениям криптологии и информационной безопасности, Гонконг, Китай, 3–7 декабря 2017 г., Материалы, Часть II . Конспекты лекций по информатике. Том. 10625. Спрингер. стр. 241–270. arXiv : 1706.06752 . дои : 10.1007/978-3-319-70697-9_9.
11. Вандерсипен, Ливен МК; Штеффен, Матиас; Брейта, Грегори; Яннони, Константино С.; Шервуд, Марк Х. и Чуанг, Исаак Л. (2001), «Экспериментальная реализация алгоритма квантового факторинга Шора с использованием ядерного магнитного резонанса» (PDF) , Nature , 414 (6866): 883–887, arXiv : quant-ph/0112176 , Bibcode : 2001Natur.414..883V, CiteSeerX 10.1.1.251.8799 , doi : 10.1038/414883a, PMID  11780055, S2CID  4400832 
12. Лу, Чао-Ян; Браун, Дэниел Э.; Ян, Тао и Пан, Цзянь-Вэй (2007), «Демонстрация скомпилированной версии алгоритма квантового факторинга Шора с использованием фотонных кубитов» (PDF) , Physical Review Letters , 99 (25): 250504, arXiv : 0705.1684 , Bibcode : 2007PhRvL ..99y0504L, doi : 10.1103/PhysRevLett.99.250504, PMID  18233508, S2CID  5158195
13. Ланьон, BP; Вейнхольд, Ти Джей; Лэнгфорд, Северная Каролина; Барбьери, М.; Джеймс, DFV; Гилкрист, А. и Уайт, А.Г. (2007), «Экспериментальная демонстрация скомпилированной версии алгоритма Шора с квантовой запутанностью» ( PDF) , Physical Review Letters , 99 (25): 250505, arXiv : 0705.1398 , Bibcode : 2007PhRvL.. 99y0505L, doi : 10.1103/PhysRevLett.99.250505, hdl : 10072/21608, PMID  18233509, S2CID  10010619
14. Лусеро, Эрик; Барендс, Рами; Чен, Ю; Келли, Джулиан; Мариантони, Маттео; Мегрант, Энтони; О'Мэлли, Питер; Санк, Дэниел; Вайнсенчер, Амит; Веннер, Джеймс; Уайт, Тед; Инь, И; Клеланд, Эндрю Н.; Мартинис, Джон М. (2012). «Вычисление простых множителей с помощью квантового процессора фазового кубита Джозефсона». Физика природы . 8 (10): 719. arXiv : 1202.5707 . Бибкод : 2012NatPh...8..719L. дои : 10.1038/nphys2385. S2CID  44055700.
15. Мартин-Лопес, Энрике; Мартин-Лопес, Энрике; Лэнг, Энтони; Лоусон, Томас; Альварес, Роберто; Чжоу, Сяо-Ци; О'Брайен, Джереми Л. (12 октября 2012 г.). «Экспериментальная реализация алгоритма квантового факторинга Шора с использованием переработки кубитов». Природная фотоника . 6 (11): 773–776. arXiv : 1111.4147 . Бибкод : 2012NaPho...6..773M. дои : 10.1038/nphoton.2012.259. S2CID  46546101.
16. Амико, Мирко; Салим, Зейн Х.; Кумф, Мьюир (08 июля 2019 г.). «Экспериментальное исследование алгоритма факторизации Шора на IBM Q». Физический обзор А. 100 (1): 012305. arXiv : 1903.00768 . doi : 10.1103/PhysRevA.100.012305. ISSN  2469-9926. S2CID  92987546.
17. Карамлу, Амир Х.; Саймон, Уильям А.; Катабарва, Амара; Схолтен, Трэвис Л.; Перопадре, Борха; Цао, Юдун (28 октября 2021 г.). «Анализ производительности вариационного квантового факторинга на сверхпроводящем квантовом процессоре». npj Квантовая информация . 7 (1): 156. arXiv : 2012.07825 . Бибкод : 2021npjQI...7..156K. doi : 10.1038/s41534-021-00478-z. ISSN  2056-6387. S2CID  229156747.
18. "Квантовые вычисления Мотт-и-Бейли" . Shtetl-Оптимизированный . 28 декабря 2019 г. Проверено 15 ноября 2021 г.
19. Бернштейн, Дэниел (1998). «Обнаружение совершенных степеней практически за линейное время». Математика вычислений . 67 (223): 1253–1283. дои : 10.1090/S0025-5718-98-00952-1 . ISSN  0025-5718.
20. например, вычисление первых корней числа , например, с помощью метода Ньютона и проверка каждого целочисленного результата на простоту ( тест на простоту AKS ). ${\displaystyle \log _{2}(N)}$ ${\displaystyle N}$
21. Экеро, Мартин (2021). «О полной эффективной факторизации любого целого числа за один запуск алгоритма поиска порядка». Квантовая обработка информации . 20 (6) 205: 1–14. arXiv : 2007.10044 . Бибкод : 2021QuIP...20..205E. дои : 10.1007/s11128-021-03069-1 . ISSN  1570-0755.
22. Китаев, А. Ю. (1995-11-20). «Квантовые измерения и проблема абелева стабилизатора». arXiv : Quant-ph/9511026 .
23. Марков, Игорь Л.; Саиди, Мехди (2012). «Квантовые схемы с постоянной оптимизацией для модульного умножения и возведения в степень». Квантовая информация и вычисления . 12 (5–6): 361–394. arXiv : 1202.6614 . Бибкод : 2012arXiv1202.6614M. дои : 10.26421/QIC12.5-6-1. S2CID  16595181.
24. Марков, Игорь Л.; Саиди, Мехди (2013). «Более быстрый факторинг квантовых чисел посредством синтеза цепей». Физ. Преподобный А. 87 (1): 012310. arXiv : 1301.3210 . Бибкод : 2013PhRvA..87a2310M. doi :10.1103/PhysRevA.87.012310. S2CID  2246117.
25. Бернштейн, Дэниел Дж.; Хенингер, Надя ; Лу, Пол; Валента, Люк (2017). «Постквантовый RSA» (PDF) . Постквантовая криптография . Конспекты лекций по информатике. Том. 10346. стр. 311–329. дои : 10.1007/978-3-319-59879-6_18. ISBN 978-3-319-59878-9. Архивировано (PDF) из оригинала 20 апреля 2017 г.

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

• Нильсен, Майкл А. и Чуанг, Исаак Л. (2010), Квантовые вычисления и квантовая информация, издание к 10-летию , Cambridge University Press, ISBN 9781107002173.
• Филип Кэй, Рэймонд Лафламм, Мишель Моска, Введение в квантовые вычисления , Oxford University Press, 2007, ISBN 0-19-857049-X 
• «Объяснение для обывателя» Скотта Ааронсона , «одобренное» Питером Шором. (Шор написал: «Отличная статья, Скотт! Это лучшая работа по объяснению квантовых вычислений обывателю, которую я когда-либо видел»). Альтернативная метафора 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 февраля 2005 г., imsa.edu, LaTeX2HTML-версия исходного документа LaTeX, также доступна в формате PDF или постскриптум.
• Квантовые вычисления и алгоритм факторизации Шора, Рональд де Вольф, CWI и Амстердамский университет, 12 января 1999 г., 9-страничный постскриптум.
• Алгоритм факторинга Шора, заметки из лекции 9 Беркли CS 294–2 от 4 октября 2004 г., 7-страничный постскриптум.
• Глава 6 «Квантовые вычисления». Архивировано 30 апреля 2020 г. в Wayback Machine , 91-страничный постскриптум, Калифорнийский технологический институт, Preskill, PH229.
• Квантовые вычисления: учебник Сэмюэля Л. Браунштейна.
• Квантовые состояния алгоритма Шора, Нил Янг, последнее изменение: вторник, 21 мая, 11:47:38 1996 г.
• III. Взлом шифрования RSA с помощью квантового компьютера: алгоритм факторизации Шора, конспекты лекций по квантовым вычислениям, Корнельский университет, физика 481–681, CS 483; Весна 2006 г., Н. Дэвид Мермин. Последняя редакция 28 марта 2006 г., 30-страничный PDF-документ.
• Лавор, К.; Мансур, ЛРУ; Португалия, Р. (2003). «Алгоритм Шора для факторизации больших целых чисел». arXiv : Quant-ph/0303175 .
• Ломонако-младший (2000). «Алгоритм квантового факторинга Шора». arXiv : Quant-ph/0010034 . Эта статья представляет собой письменную версию часовой лекции, посвященной алгоритму квантового факторинга Питера Шора. 22 страницы.
• Глава 20 «Квантовые вычисления», из книги «Вычислительная сложность: современный подход» , черновик книги: датирован январем 2007 г., Санджив Арора и Боаз Барак, Принстонский университет. Опубликовано в главе 10 «Квантовые вычисления» Санджива Арора, Боаза Барака, «Сложность вычислений: современный подход», 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 создала два видеоролика, объясняющих математические принципы алгоритма Шора: «Как взломать криптографию» и «Взлом на квантовой скорости с помощью алгоритма Шора».