Какие целые числа были учтены в алгоритме Шора?

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

В настоящее время учитываются только меньшие целые числа. Например, в этой статье обсуждается разложение .$15=5{\times}3$

Каково в этом смысле современное состояние исследований? Есть ли какая-нибудь недавняя статья, в которой говорится, что некоторые большие цифры были разложены?

Первичная факторизация 21 (7x3), кажется, самая большая из сделанных на сегодняшний день с помощью алгоритма Шора; это было сделано в 2012 году, как подробно описано в этом документе . Следует отметить, однако, что гораздо большие числа, такие как 56 153 в 2014 году, были учтены с использованием алгоритма минимизации, как подробно описано здесь . Для удобной ссылки см. Таблицу 5 этого документа :

$$\begin{array}{c} \textbf{Table 5:}~\text{Quantum factorization records} \\ \hline \small{ \begin{array}{cccccc} \text{Number} & \text{# of factors} & \begin{array}{c}\text{# of qubits} \\ \text{needed} \end{array} & \text{Algorithm} & \begin{array}{c}\text{Year} \\ \text{implemented} \end{array} & \begin{array}{c}\text{Implemented} \\ \text{without prior} \\ \text{knowledge of} \\ \text{solution} \end{array} \\ \hline 15 & 2 & 8 & \text{Shor} & 2001~\left[2\right] & \chi \\ & 2 & 8 & \text{Shor} & 2007~\left[3\right] & \chi \\ & 2 & 8 & \text{Shor} & 2007~\left[3\right] & \chi \\ & 2 & 8 & \text{Shor} & 2009~\left[5\right] & \chi \\ & 2 & 8 & \text{Shor} & 2012~\left[6\right] & \chi \\ 21 & 2 & 10 & \text{Shor} & 2012~\left[7\right] & \chi \\ 143 & 2 & 4 & \text{minimization} & 2012~\left[1\right] & \checkmark \\ 56153 & 2 & 4 & \text{minimization} & 2012~\left[1\right] & \checkmark \\ \hline 291311 & 2 & 6 & \text{minimization} & \text{not yet} & \checkmark \\ 175 & 3 & 3 & \text{minimization} & \text{not yet} & \checkmark \end{array}} \end{array}_{\Large{.}}$$

Для Алгортма Шора : Современное состояние все еще 15 . Чтобы «разложить» 21 в статье, которую упоминает Хизер, им пришлось использовать тот факт, что чтобы выбрать свою базу а . Это было объяснено в 2013 году в статье « Притворяться о факторных числах на квантовом компьютере» , позже опубликованной Nature с несколько более дружелюбным названием . Квантовый компьютер не учитывал 21, но он подтвердил, что факторы 7 и 3 действительно верны.$21=7\times 3$$a$

Для алгоритма отжига : уровень техники 376289 . Но мы не знаем, как это будет масштабироваться. Очень грубый верхний предел количества кубитов, необходимых для расчета RSA-230, составляет 5,5 миллиардов кубитов (но это может быть значительно снижено лучшими компиляторами), в то время как алгоритм Шора может сделать это с 381 кубитом .

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

Это обсуждается у Дж. Смолина, Дж. Смита, А. Варго: «Притворяться в факторизации больших чисел на квантовом компьютере» , Nature 499, 163-165 (2013) . В частности, авторы также приводят пример числа с 20000 двоичными цифрами, которое может быть учтено на квантовом компьютере с двумя кубитами, с точно такой же реализацией, которая использовалась ранее для разложения на другие числа.

Следует отметить, что «ручные упрощения», которые авторы выполняют, чтобы прийти к этому квантовому алгоритму, - это то, что также было сделано, например, для исходного эксперимента с учетом 15.