шор об алгоритме шора

[avva]

Peter Shor: The Early Days of Quantum ComputationВоспоминания Питера Шора о ранней истории квантовых вычислений, в 80-х и 90-х, и о его собственных открытиях. Шор открыл, в 94-м году, знаменитый квантовый алгоритм быстрого разложения на множители, который произвел впечатление разорвавшейся бомбы, и наверное очень сильно подстегнул всю эту науку.

Comments

[spamsink]

Шор - голова, ему простые числа с целью разложения на множители в рот не клади!

In 2019 an attempt was made to factor the number 35 using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors.

[xgrbml]

Старая эпиграмма (забыл автора, к сожалению):

To read our email, how mean
Of the spies and their quantum machine!
Be comforted though,
The do not yet know
How to factorize twelve or fifteen.

[spamsink]

Да-да. С тех пор квантовая наука ушла как минимум на двадцать вперёд.

[buddha239]

Точно это - самый важный пример?:) Вроде бы, этот метод (модифицированный?)) эллиптическую криптографию тоже ломает.

[igmor]

Он в статье об этом и говорит, что сначала он придумал алгоритм для дискретного логарифма а потом каким-то способом (каким?) смог найти аналог для факторизации на простые числа.

Later that week, I was able to solve the
factoring problem as well. There’s a strange relation between discrete log and
factoring. There’s no formula for taking an algorithm for one of these problems
and applying it to the other. However, any time somebody has found an improved
algorithm for one of them, people have reasonably quickly come up with a similar
solution for the other one. This case was no different - knowing the discrete log
algorithm, it was fairly easy to find a factoring algorithm.

[buddha239]

Так дискретный логарифм, кажися, поважнее будет.:)

[igmor]

Почему? Обе криптографические схемы достаточно распространены, RSA даже намного более.

[muh2a]

Пути мышления неисповедимы, но в алгоритме Шора, как мне кажется, нет ничего удивившего бы копенгагенца.

Но мне вот непонятно, правда ли, что для алгоритма Шора требуется экспоненциально (по битам) точный контроль? Ну, типа, для квантового Фурье требуется повернуть фазу с экспоненциальной точностью. Я не разбирался в квантовом Фурье. Если это так - то аналоговый компьютер и есть аналоговый компьютер. Кстати, человек от которого я это слышал, утверждает, что квантовое доминирование Гугла - жульничество, поскольку Гугл сам может экспериментально определить результат только с конечной достоверностью, но сравнивает время с вычислениями, проводимыми точно. А если делать вычисления с той же достоверностью (оставляя только главные собственные числа матриц), то Гугл бьется лаптопом этого человека.

[spamsink]

Квантовый компьютер - это массивно-параллельный аналоговый компьютер. Другое дело, что эквивалентная параллельность его увеличивается не экспоненциально в зависимости от количества кубитов, а медленнее; или, другими словами, NP ⊈ BQP.

Так что даже если квантовые компьютеры достигнут такого уровня, чтобы ломать секретные ключи типичных нынешних размеров за практически полезные время/деньги (без этого ограничения надо было бы сказать "когда", но с ним - пока только "если"), то увеличение размера ключей в несколько раз решит проблему.

[buddha239]

А с какой скоростью растет время "квантового взлома" при увеличении размера ключа?

[spamsink]

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

[soimu]

не согласен с мнением Дэвида Дойча о том, что квантовые вычисления практически неизбежно приводят к многомировой интерпретации как единственно резонной

Ну здесь он (Шор) заблуждается...

[geribo]

Так подстегнул, что через 30 лет никакого "квантового компьютера" нет в помине (и не будет).