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

Алгоритм Шора - это алгоритм квантового компьютера с полиномиальным временем для целочисленной факторизации. Неформально он решает следующую проблему: для заданного целого числа найти его простые множители. Он был открыт в 1994 году американским математиком Питером Шором. ${\ displaystyle N}$

На квантовом компьютере, чтобы разложить целое число на множители, алгоритм Шора работает за полиномиальное время (затраченное время полиномиально от размера целого числа, заданного на входе). В частности, он принимает квантовые вентили порядка с использованием быстрого умножения, тем самым демонстрируя, что проблема целочисленной факторизации может быть эффективно решена на квантовом компьютере и, следовательно, относится к классу сложности BQP. Это почти экспоненциально быстрее, чем наиболее эффективного известного классического алгоритма факторинга, то общее число поле решето, которое работает в суб-экспоненциальное время :. Эффективность алгоритма Шора обусловлена ​​эффективностью квантового преобразования Фурье и модульного возведения в степень с помощью повторных квадратов. ${\ displaystyle N}$${\ displaystyle \ log N}$ ${\ Displaystyle О \! \ влево ((\ журнал N) ^ {2} (\ журнал \ журнал N) (\ журнал \ журнал \ журнал N) \ вправо)}$ ${\ Displaystyle О \! \ влево (е ^ {1,9 (\ журнал N) ^ {1/3} (\ журнал \ журнал N) ^ {2/3}} \ справа)}$

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

В 2001 году алгоритм Шора был продемонстрирован группой в IBM, который учтенных в, используя реализацию ЯМР квантового компьютера с кубитами. После внедрения IBM две независимые группы реализовали алгоритм Шора с использованием фотонных кубитов, подчеркнув, что многокубитовая запутанность наблюдалась при выполнении схем алгоритма Шора. В 2012 году факторизация была проведена с использованием твердотельных кубитов. Кроме того, в 2012 году была достигнута факторизация, установив рекорд для наибольшего целого числа, факторизованного с помощью алгоритма Шора. В 2019 году была предпринята попытка разложить число 35 на множители с помощью алгоритма Шора на IBM Q System One, но алгоритм не удался из-за накопления ошибок. Однако квантовые компьютеры с помощью других алгоритмов, в частности, квантового отжига, разложили на множители гораздо большие числа. ${\ displaystyle 15}$${\ displaystyle 3 \ times 5}$ ${\ displaystyle 7}$ ${\ displaystyle 15}$${\ displaystyle 21}$

СОДЕРЖАНИЕ

• 1 Процедура
  • 1.1 Классическая партия
  • 1.2 Квантовая часть: подпрограмма определения периода
• 2 Объяснение алгоритма
  • 2.1 Получение коэффициентов из периода
  • 2.2 Определение периода
  • 2.3 Узкое место
• 3 Дискретные логарифмы
• 4 См. Также
• 5 ссылки
• 6 Дальнейшее чтение
• 7 Внешние ссылки

Процедура

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

Нам нужно быть нечетным (в противном случае - делителем) и не быть степенью простого числа (в противном случае это простое число является делителем), поэтому нам нужно проверить, что нет целых корней для. ${\ displaystyle N}$${\ displaystyle 2}$${\ displaystyle {\ sqrt [{k}] {N}}}$${\ Displaystyle 2 \ Leq К \ Leq {\ log _ {3}} (N)}$

Следовательно, мы можем считать, что это произведение двух взаимно простых целых чисел, больших чем. Из китайской теоремы об остатках следует, что существует по крайней мере четыре различных квадратных корня по модулю (поскольку есть два корня для каждого модульного уравнения). Цель алгоритма - найти квадратный корень из модуля, отличный от и, потому что тогда ${\ displaystyle N}$ ${\ displaystyle 2}$ ${\ displaystyle 1}$ ${\ displaystyle N}$${\ displaystyle b}$${\ displaystyle 1}$${\ displaystyle N}$${\ displaystyle 1}$${\ displaystyle -1}$

${\ Displaystyle b ^ {2} -1 = (b + 1) (b-1) = mN}$

для ненулевого целого числа, которое дает нам нетривиальные делители и о. Эта идея похожа на другие алгоритмы факторизации, такие как квадратное решето. ${\ displaystyle m}$${\ displaystyle \ gcd (N, b + 1)}$${\ displaystyle \ gcd (N, b-1)}$${\ displaystyle N}$

В свою очередь, поиск такого элемента сводится к нахождению элемента четного периода с определенным дополнительным свойством (как поясняется ниже, требуется, чтобы не выполнялось условие шага 6 классической части). Квантовый алгоритм используется для нахождения периода случайно выбранных элементов, так как это сложная задача на классическом компьютере. ${\ displaystyle b}$${\ displaystyle a}$${\ displaystyle a}$

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

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

Классическая часть

1. Выберите случайное число.${\ Displaystyle 1 lt;а lt;N}$
2. Compute, то наибольший общий делитель из и. Это можно сделать с помощью алгоритма Евклида. ${\ Displaystyle К = \ НОД (а, N)}$ ${\ displaystyle a}$${\ displaystyle N}$
3. Если, то является нетривиальным фактором, так что все готово.${\ displaystyle K \ neq 1}$${\ displaystyle K}$ ${\ displaystyle N}$
4. В противном случае используйте подпрограмму квантового определения периода (см. Ниже), чтобы найти, который обозначает период следующей функции: ${\ displaystyle r}$

   ${\ displaystyle f (x) = a ^ {x} {\ bmod {N}}.}$

   Это порядок из в группе, которая является наименьшее положительное целое число, для которого, или. По теореме Эйлера, водоразделов, где обозначает Функция Эйлера. ${\ displaystyle r}$${\ displaystyle a}$ ${\ Displaystyle (\ mathbb {Z} _ {N}) ^ {\ times}}$ ${\ displaystyle r}$${\ Displaystyle е (х + г) = е (х)}$${\ Displaystyle е (х + г) = а ^ {х + г} {\ bmod {N}} \ эквив а ^ {х} {\ bmod {N}}}$ ${\ displaystyle r}$${\ displaystyle \ varphi (N)}$${\ displaystyle \ varphi}$
5. Если нечетное, вернитесь к шагу 1.${\ displaystyle r}$
6. Если, то вернитесь к шагу 1.${\ Displaystyle а ^ {г / 2} \ экв-1 ({\ bmod {N}})}$
7. В противном случае оба и являются нетривиальными факторами, поэтому мы закончили.${\ Displaystyle \ НОД (а ^ {г / 2} + 1, N)}$${\ Displaystyle \ НОД (а ^ {г / 2} -1, N)}$${\ displaystyle N}$

Например: Учитывая, и, у нас есть, где и. Поскольку это произведение двух различных простых чисел, и значение равно, которое для есть, и делится. ${\ displaystyle N = 15}$${\ displaystyle a = 7}$${\ displaystyle r = 4}$${\ displaystyle \ gcd (7 ^ {2} \ pm 1,15) = \ gcd (49 \ pm 1,15)}$${\ displaystyle \ gcd (48,15) = 3}$${\ displaystyle \ gcd (50,15) = 5}$${\ displaystyle N}$${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle \ varphi (N)}$${\ displaystyle Np-q + 1}$${\ displaystyle N = 15}$${\ displaystyle 8}$${\ displaystyle r}$${\ displaystyle 8}$

Квантовая часть: подпрограмма определения периода

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

Квантовые схемы, используемые для этого алгоритма, специально разработаны для каждого выбора и каждого варианта случайного выбора, используемого в. Учитывая, найти такое, что подразумевает, что. Входные и выходные кубитов регистры нужно держать суперпозицию значений от до, и поэтому имеют кубиты каждый. Использование того, что может показаться вдвое большим количеством кубитов, чем необходимо, гарантирует, что существуют, по крайней мере, разные значения, которые производят то же самое, даже когда период приближается. ${\ displaystyle N}$${\ displaystyle a}$${\ Displaystyle е (х) = а ^ {х} {\ bmod {N}}}$${\ displaystyle N}$${\ displaystyle Q = 2 ^ {q}}$${\ Displaystyle N ^ {2} \ leq Q lt;2N ^ {2}}$${\ displaystyle {\ dfrac {Q} {r}}gt; N}$ ${\ displaystyle 0}$${\ displaystyle Q-1}$${\ displaystyle q}$${\ displaystyle N}$${\ displaystyle x}$${\ displaystyle f (x)}$${\ displaystyle r}$${\ displaystyle {\ dfrac {N} {2}}}$

Действуйте следующим образом:

1. Инициализировать регистры для

   ${\ displaystyle {\ frac {1} {\ sqrt {Q}}} \ sum _ {x = 0} ^ {Q-1} | x \ rangle = \ left ({\ frac {1} {\ sqrt {2 }}} \ sum _ {x_ {1} = 0} ^ {1} | x_ {1} \ rangle \ right) \ otimes \ cdots \ otimes \ left ({\ frac {1} {\ sqrt {2}} } \ sum _ {x_ {q} = 0} ^ {1} | x_ {q} \ rangle \ right).}$

   где обозначает тензорное произведение. ${\ displaystyle \ otimes}$

   Это начальное состояние представляет собой суперпозицию состояний, и его легко получить путем создания независимых кубитов, каждый из которых является суперпозицией состояний и. Мы можем добиться этого, инициализировав кубиты в нулевое положение, а затем применив вентиль Адамара параллельно к каждому из кубитов, где.${\ displaystyle Q}$${\ displaystyle q}$ ${\ displaystyle 0}$${\ displaystyle 1}$ ${\ displaystyle q}$${\ displaystyle 2 ^ {q} = Q}$
2. Постройте как квантовую функцию и примените ее к вышеуказанному состоянию, чтобы получить ${\ displaystyle f (x)}$

   ${\ displaystyle U_ {f} | x, 0 ^ {q} \ rangle = | x, f (x) \ rangle}$

   ${\ displaystyle U_ {f} {\ frac {1} {\ sqrt {Q}}} \ sum _ {x = 0} ^ {Q-1} | x, 0 ^ {q} \ rangle = {\ frac { 1} {\ sqrt {Q}}} \ sum _ {x = 0} ^ {Q-1} | x, f (x) \ rangle}$

   Это все еще суперпозиция состояний. Однако кубиты, то есть входные кубиты и () выходные кубиты, теперь запутаны или неразделимы, поскольку состояние не может быть записано как тензорное произведение состояний отдельных кубитов. Важно отметить, что значение, содержащее искомое значение, теперь сохраняется в фазе входных кубитов в результате «фазового отката», когда использование кубитов в качестве управляющих входов для унитарных вентилей изменяет относительную фазу управляющих кубитов.${\ displaystyle Q}$${\ displaystyle q + n}$${\ displaystyle q}$${\ displaystyle n}$${\ Displaystylegt; {\ журнал _ {2}} (N)}$ ${\ displaystyle r}$${\ displaystyle x}$
3. Примените обратное квантовое преобразование Фурье ко входному регистру. Это преобразование (работающий на суперпозиции состояний) использует -й корень из единицы, такие как распределять амплитуду любого заданного состояния поровну между всеми из состояний, и делать это по-другому для каждой по- разному. Таким образом, получаем ${\ displaystyle Q = 2 ^ {q}}$${\ displaystyle Q}$ ${\ displaystyle \ omega = e ^ {\ frac {2 \ pi i} {Q}}}$${\ Displaystyle | х \ rangle}$${\ displaystyle Q}$${\ Displaystyle | у \ rangle}$${\ displaystyle x}$

   ${\ displaystyle {U _ {\ operatorname {QFT}}} (| x \ rangle) = {\ frac {1} {\ sqrt {Q}}} \ sum _ {y = 0} ^ {Q-1} \ omega ^ {xy} | y \ rangle.}$

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

   ${\ displaystyle {\ frac {1} {Q}} \ sum _ {x = 0} ^ {Q-1} \ sum _ {y = 0} ^ {Q-1} \ omega ^ {xy} | y, f (x) \ rangle.}$

   Теперь мы переупорядочиваем эту сумму как

   ${\ displaystyle {\ frac {1} {Q}} \ sum _ {z = 0} ^ {N-1} \ sum _ {y = 0} ^ {Q-1} \ left [\ sum _ {x \ в \ {0, \ ldots, Q-1 \}; ~ f (x) = z} \ omega ^ {xy} \ right] | y, z \ rangle.}$

   Это суперпозиция гораздо больше, чем состояний, но гораздо меньше, чем состояний, поскольку существует меньше, чем различных значений. Позволять ${\ displaystyle Q}$${\ displaystyle Q ^ {2}}$${\ displaystyle Q}$${\ Displaystyle г = е (х)}$
   • ${\ displaystyle \ omega = e ^ {\ frac {2 \ pi i} {Q}}}$быть корнем -й степени из единства,${\ displaystyle Q}$
   • ${\ displaystyle r}$быть периодом,${\ displaystyle f}$
   • ${\ displaystyle x_ {0}}$быть наименьшим из тех, для которых (у нас есть), и${\ Displaystyle х \ в \ {0, \ ldots, Q-1 \}}$${\ Displaystyle е (х) = г}$${\ displaystyle x_ {0} lt;r}$
   • написать ${\ displaystyle m-1 = \ left \ lfloor {\ frac {Q-x_ {0} -1} {r}} \ right \ rfloor}$
   • ${\ displaystyle b}$индексирует их, начиная с по, так что.${\ displaystyle x}$${\ displaystyle 0}$${\ displaystyle m-1}$${\ displaystyle x_ {0} + rb lt;Q}$
   Тогда - единичный вектор в комплексной плоскости ( является корнем из единицы, а и являются целыми числами), а коэффициент в конечном состоянии равен ${\ displaystyle \ omega ^ {ry}}$${\ displaystyle \ omega}$${\ displaystyle r}$${\ displaystyle y}$${\ displaystyle {\ dfrac {1} {Q}} \ left | y, z \ right \ rangle}$

   ${\ displaystyle \ sum _ {x \ in \ {0, \ ldots, Q-1 \}; ~ f (x) = z} \ omega ^ {xy} = \ sum _ {b = 0} ^ {m- 1} \ omega ^ {(x_ {0} + rb) y} = \ omega ^ {x_ {0} y} \ sum _ {b = 0} ^ {m-1} \ omega ^ {rby}.}$

   Каждый член в этой сумме представляет собой разный путь к одному и тому же результату, и возникает квантовая интерференция - конструктивная, когда единичные векторы указывают почти в одном направлении в комплексной плоскости, что требует этой точки вдоль положительной действительной оси. ${\ displaystyle \ omega ^ {ryb}}$${\ displaystyle \ omega ^ {ry}}$
4. Выполните измерение. Мы получаем некоторый результат во входном регистре и некоторый результат в выходном регистре. В периодическом режиме вероятность измерения некоторого состояния определяется выражением ${\ displaystyle y}$${\ displaystyle z}$${\ displaystyle f}$${\ displaystyle | y, z \ rangle}$

   ${\ displaystyle \ mathrm {Pr} (| y, z \ rangle) = \ left | {\ frac {1} {Q}} \ sum _ {x \ in \ {0, \ ldots, Q-1 \}; ~ f (x) = z} \ omega ^ {xy} \ right | ^ {2} = {\ frac {1} {Q ^ {2}}} \ left | \ sum _ {b = 0} ^ {m -1} \ omega ^ {(x_ {0} + rb) y} \ right | ^ {2} = {\ frac {1} {Q ^ {2}}} | \ omega ^ {x_ {0} y} | ^ {2} \ left | \ sum _ {b = 0} ^ {m-1} \ omega ^ {bry} \ right | ^ {2}}$

   ${\ displaystyle = {\ frac {1} {Q ^ {2}}} \ left | \ sum _ {b = 0} ^ {m-1} \ omega ^ {bry} \ right | ^ {2} = { \ frac {1} {Q ^ {2}}} \ left | {\ frac {\ omega ^ {mry} -1} {\ omega ^ {ry} -1}} \ right | ^ {2} = {\ frac {1} {Q ^ {2}}} {\ frac {\ sin ^ {2} ({\ frac {\ pi mry} {Q}})} {\ sin ^ {2} ({\ frac {\ пи ry} {Q}})}}}$

   Анализ теперь показывает, что эта вероятность тем выше, чем ближе единичный вектор к положительной действительной оси или чем ближе к целому числу. Если это не сила, она не будет фактором.${\ displaystyle \ omega ^ {ry}}$${\ displaystyle {\ dfrac {yr} {Q}}}$${\ displaystyle r}$${\ displaystyle 2}$${\ displaystyle Q}$
5. Поскольку оно близко к некоторому целому числу, известное значение близко к неизвестному значению. Выполнение [классическое] дальнейшее расширение фракции на позволяет найти приближение из нее, которые удовлетворяют два условий: ${\ displaystyle {\ frac {yr} {Q}}}$${\ displaystyle c}$${\ displaystyle {\ dfrac {y} {Q}}}$${\ displaystyle {\ dfrac {c} {r}}}$ ${\ displaystyle {\ dfrac {y} {Q}}}$${\ displaystyle {\ dfrac {d} {s}}}$
   1. ${\ displaystyle s lt;N}$.
   2. ${\ displaystyle \ left | {\ dfrac {y} {Q}} - {\ dfrac {d} {s}} \ right | lt;{\ dfrac {1} {2Q}}}$.
   Учитывая эти несколько условий (и предполагая, является неприводимым ), очень вероятно, будет соответствующий период, или по крайней мере одним из факторов его.${\ displaystyle {\ dfrac {d} {s}}}$ ${\ displaystyle s}$${\ displaystyle r}$
6. Проверить (классически), если. Если так, то все готово.${\ Displaystyle е (х) = е (х + s) \ Leftrightarrow а ^ {s} \ эквив 1 {\ bmod {N}}}$
7. В противном случае (классически) получить больше кандидатов, используя кратные числа, или используя другие с рядом. Если какой-либо кандидат работает, то все готово.${\ displaystyle r}$${\ displaystyle s}$${\ displaystyle s}$${\ displaystyle {\ dfrac {d} {s}}}$${\ displaystyle {\ dfrac {y} {Q}}}$
8. В противном случае попробуйте еще раз, начиная с шага 1 этой подпрограммы.

Пояснение к алгоритму

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

Получение факторов из периода

Целые числа меньшие и взаимно простые с образуют мультипликативную группу целых чисел по модулю, которая является конечной абелевой группой. Размер этой группы определяется как. К концу шага 3 у нас есть целое число в этой группе. Поскольку группа конечна, она должна иметь конечный порядок, который является наименьшим положительным целым числом, таким, что ${\ displaystyle N}$ ${\ displaystyle N}$ ${\ displaystyle N}$ ${\ displaystyle G}$${\ displaystyle \ varphi (N)}$${\ displaystyle a}$${\ displaystyle a}$${\ displaystyle r}$

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

Следовательно, делит (тоже пишется). Предположим, что мы можем получить и что это даже. (Если нечетное, то на шаге 5 мы должны перезапустить алгоритм с другим случайным числом) Теперь квадратный корень по модулю, который отличается от. Это потому, что это порядок по модулю, так, иначе порядок в этой группе был бы таким. Если, то на шаге 6 мы должны перезапустить алгоритм с другим случайным числом. ${\ displaystyle N}$ ${\ displaystyle a ^ {r} -1}$${\ displaystyle N \ mid a ^ {r} -1}$${\ displaystyle r}$${\ displaystyle r}$${\ displaystyle a}$${\ Displaystyle б \ эквив а ^ {г / 2} {\ bmod {N}}}$${\ displaystyle 1}$${\ displaystyle N}$${\ displaystyle 1}$${\ displaystyle r}$${\ displaystyle a}$${\ displaystyle N}$${\ Displaystyle а ^ {г / 2} \ not \ эквив 1 {\ bmod {N}}}$${\ displaystyle a}$${\ displaystyle {\ dfrac {r} {2}}}$${\ Displaystyle а ^ {г / 2} \ экв-1 {\ bmod {N}}}$${\ displaystyle a}$

В конце концов, мы должны навести порядок в этом. Это потому, что такое a является квадратным корнем по модулю, отличному от и, существование которого гарантируется китайской теоремой об остатках, поскольку не является степенью простого числа. ${\ displaystyle a}$${\ displaystyle r}$${\ displaystyle G}$${\ Displaystyle б \ эквив а ^ {г / 2} \ не \ эквив \ пм 1 {\ bmod {N}}}$${\ displaystyle b}$${\ displaystyle 1}$${\ displaystyle N}$${\ displaystyle 1}$${\ displaystyle -1}$${\ displaystyle N}$

Мы утверждаем, что это правильный фактор, т. Е. Фактически, если, то делит так, что это противоречит построению. Если, с другой стороны, то по тождеству Безу существуют такие целые числа, что ${\ displaystyle d = \ gcd (b-1, N)}$${\ displaystyle N}$${\ displaystyle d \ neq 1, N}$${\ displaystyle d = N}$${\ displaystyle N}$${\ displaystyle b-1}$${\ Displaystyle б \ эквив 1 {\ bmod {N}}}$${\ displaystyle b}$${\ displaystyle d = \ gcd (b-1, N) = 1}$ ${\ displaystyle u, v}$

${\ displaystyle (b-1) u + Nv = 1.}$

Умножая обе части на, получаем ${\ displaystyle b + 1}$

${\ displaystyle (b ^ {2} -1) u + N (b + 1) v = b + 1.}$

Когда делит, мы находим, что делит так, что опять же противоречит конструкции. ${\ displaystyle N}$${\ Displaystyle Ь ^ {2} -1 \ эквив а ^ {г} -1 {\ bmod {N}}}$${\ displaystyle N}$${\ displaystyle b + 1}$${\ Displaystyle б \ экв-1 {\ bmod {N}}}$${\ displaystyle b}$

Следовательно, это требуемый собственный коэффициент. ${\ displaystyle d}$${\ displaystyle N}$

Определение периода

Алгоритм определения периода Шора во многом полагается на способность квантового компьютера одновременно находиться во многих состояниях.

Физики называют такое поведение « суперпозицией » состояний. Чтобы вычислить период функции, мы оцениваем функцию во всех точках одновременно. ${\ displaystyle f}$

Однако квантовая физика не позволяет нам напрямую получить доступ ко всей этой информации. Измерение будет давать только один из всех возможных значений, уничтожая всех остальных. Если бы не теорема о запрете клонирования, мы могли бы сначала измерить без измерения, а затем сделать несколько копий результирующего состояния (которое представляет собой суперпозицию состояний, у всех одинаковых). Измерение этих состояний даст разные значения, которые дают одинаковые значения, что приводит к периоду. Поскольку мы не можем сделать точные копии квантового состояния, этот метод не работает. Следовательно, мы должны тщательно преобразовать суперпозицию в другое состояние, которое с большой вероятностью вернет правильный ответ. Это достигается квантовым преобразованием Фурье. ${\ displaystyle f (x)}$${\ displaystyle x}$${\ displaystyle f (x)}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle f (x)}$

Таким образом, Шору пришлось решить три проблемы «реализации». Все они должны были быть реализованы «быстро», что означает, что они могут быть реализованы с числом квантовых вентилей, который является многочленом в. ${\ displaystyle \ log N}$

1. Создайте суперпозицию состояний. Это можно сделать, применив вентили Адамара ко всем кубитам во входном регистре. Другой подход - использовать квантовое преобразование Фурье (см. Ниже).
2. Реализуйте функцию как квантовое преобразование. Для этого Шор использовал многократное возведение в квадрат для своего модульного преобразования возведения в степень. Важно отметить, что этот шаг сложнее реализовать, чем квантовое преобразование Фурье, поскольку для его выполнения требуются вспомогательные кубиты и значительно больше вентилей.${\ displaystyle f}$
3. Выполните квантовое преобразование Фурье. Используя вентили с управляемым вращением и вентили Адамара, Шор разработал схему для квантового преобразования Фурье (с), которая использует только вентили.${\ displaystyle Q = 2 ^ {q}}$${\ displaystyle {\ dfrac {q (q-1)} {2}} = O \! \ left ((\ log Q) ^ {2} \ right)}$

После всех этих преобразований измерение даст приближение к периоду. Для простоты предположим, что есть такие, что является целым числом. Тогда вероятность измерить равна. Чтобы увидеть это, мы замечаем, что тогда ${\ displaystyle r}$${\ displaystyle y}$${\ displaystyle {\ dfrac {yr} {Q}}}$${\ displaystyle y}$${\ displaystyle 1}$

${\ displaystyle e ^ {- {\ frac {2 \ pi ibyr} {Q}}} = 1}$

для всех целых чисел. Таким образом, сумма, квадрат дает нам вероятность измерения будет, как и занимает около значений и, таким образом, вероятность. Есть возможные значения таким образом, что представляет собой целое число, а также возможности, поэтому вероятность подводить к. ${\ displaystyle b}$${\ displaystyle y}$${\ displaystyle {\ dfrac {Q} {r}}}$${\ displaystyle b}$${\ displaystyle {\ dfrac {Q} {r}}}$${\ Displaystyle {\ dfrac {1} {г ^ {2}}}}$${\ displaystyle r}$${\ displaystyle y}$${\ displaystyle {\ dfrac {yr} {Q}}}$${\ displaystyle r}$${\ displaystyle f (x_ {0})}$${\ displaystyle 1}$

Примечание. Другой способ объяснить алгоритм Шора - это отметить, что это всего лишь замаскированный алгоритм квантовой оценки фазы.

Узкое место

Узким местом выполнения алгоритма Шора является квантовое модульное возведение в степень, которое намного медленнее, чем квантовое преобразование Фурье и классическая предварительная / постобработка. Существует несколько подходов к построению и оптимизации схем для модульного возведения в степень. Самый простой и (в настоящее время) наиболее практичный подход - имитировать обычные арифметические схемы с обратимыми вентилями, начиная с сумматоров с переносом пульсации. Знание базы и модуля возведения в степень облегчает дальнейшую оптимизацию. Обратимые схемы обычно используют в порядке вентилей для кубитов. Альтернативные методы асимптотически улучшают количество вентилей за счет использования квантовых преобразований Фурье, но не могут конкурировать с менее чем 600 кубитами из-за высоких констант. ${\ Displaystyle п ^ {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 г = {\ журнал _ {г}} (х)}$${\ Displaystyle \ mathbb {Z} _ {p} \ times \ mathbb {Z} _ {p}}$

${\ displaystyle f \ двоеточие \ mathbb {Z} _ {p} \ times \ mathbb {Z} _ {p} \ to G \ ;; \; f (a, b) = g ^ {a} x ^ {- б}.}$

Это дает нам абелеву проблему скрытых подгрупп, что соответствует гомоморфизму групп. Ядро соответствует кратным. Итак, если мы сможем найти ядро, мы сможем найти. ${\ displaystyle f}$ ${\ Displaystyle (г, 1)}$${\ displaystyle r}$

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

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

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

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

• Нильсен, Майкл А. и Чуанг, Исаак Л. (2010), Квантовые вычисления и квантовая информация, 10-е юбилейное издание, Cambridge University Press, ISBN   9781107002173.
• Филип Кэй, Раймонд Лафламм, Мишель Моска, Введение в квантовые вычисления, Oxford University Press, 2007, ISBN   0-19-857049-X
• «Объяснение для человека на улице» по Ааронсон, « утвержден » Питер Шор. (Шор написал: «Отличная статья, Скотт! Это лучшая работа по объяснению квантовых вычислений обывателю из всех, что я видел»). Альтернативная метафора QFT была представлена ​​в одном из комментариев. Скотт Ааронсон предлагает следующие 12 ссылок для дальнейшего чтения (из «10 ^{10 5 000} руководств по квантовым алгоритмам, которые уже есть в сети»):
• Шор, Питер В. (1997), "Полиномиальные алгоритмы для простой факторизации и дискретных логарифмов на квантовом компьютере", SIAM J. Comput., 26 (5): 1484–1509, arXiv : Quant-ph / 9508027v2, Bibcode : 1999SIAMR..41..303S, doi : 10.1137 / S0036144598347011. Отредактированная версия оригинальной статьи Питера Шора («28 страниц, LaTeX. Это расширенная версия статьи, опубликованной в Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Санта-Фе, Нью-Мексико, 20 ноября. 22, 1994. Незначительные исправления внесены в январе 1996 г. ").
• Квантовые вычисления и алгоритм Шора, Страница квантовых алгоритмов Мэтью Хейворда, 2005-02-17, imsa.edu, LaTeX2HTML-версия исходного документа LaTeX, также доступная в формате PDF или postscript.
• Квантовые вычисления и алгоритм факторинга Шора, Рональд де Вольф, CWI и Амстердамский университет, 12 января 1999 г., постскриптум на 9 страницах.
• Алгоритм факторинга Шора, Заметки из лекции 9 Berkeley CS 294–2 от 4 октября 2004 г., 7-страничный постскриптум.
• Глава 6 Квантовые вычисления, 91-страничный постскриптум, Caltech, Preskill, PH229.
• Квантовые вычисления: учебное пособие по Сэмюэл Л. Браунштейн.
• Квантовые состояния алгоритма Шора, Нил Янг, последнее изменение: вторник, 21 мая, 11:47:38 1996.
• III. Взлом RSA-шифрования с помощью квантового компьютера: алгоритм факторинга Шора, конспект лекций по квантовым вычислениям, Корнельский университет, физика 481–681, CS 483; Весна 2006 г. Н. Дэвид Мермин. Последняя редакция 28 марта 2006 г., 30-страничный документ PDF.
• Lavor, C.; Мансур, LRU; Португалия, Р. (2003). «Алгоритм Шора факторинга больших целых чисел». arXiv : квант-ph / 0303175.
• Ломонако-младший (2000). «Алгоритм квантового факторинга Шора». arXiv : квант-ph / 0010034. Эта статья представляет собой письменную версию часовой лекции по квантовому алгоритму разложения Питера Шора. 22 страницы.
• Глава 20 «Квантовые вычисления», « Вычислительная сложность: современный подход», черновик книги: от января 2007 г., Санджив Арора и Боаз Барак, Принстонский университет. Опубликовано как Глава 10 Квантовые вычисления Санджив Арора, Боаз Барак, «Вычислительная сложность: современный подход», Cambridge University Press, 2009, ISBN   978-0-521-42426-4
• Шаг к квантовым вычислениям: запутывание 10 миллиардов частиц, из журнала Discover, датированного 19 января 2011 года.
• Йозеф Груска - Проблемы квантовых вычислений также в математике без ограничений: 2001 г. и позже, редакторы Бьёрн Энгквист, Вильфрид Шмид, Springer, 2001 г., ISBN   978-3-540-66913-5

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

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