Ответы на вопрос Длина ключа RSA и алгоритм Шора предложить, например, 2048-битное шифрование RSA было бы тривиально взломано квантовым компьютером на 4099 кубитов с использованием алгоритма Шора (наиболее известная реализация алгоритма, требующая 2n+3 кубитов).
Это правда? Если я правильно понял, необходимое количество вентилей (логически квантовых операций) будет около log(2^2048)^2Ãlog(log(2^2048))Ãlog(log(log(2^2048) )) что составляет примерно 2,9Ã10â·. Принимая во внимание, что даже классические компьютеры не могут выполнять какие-либо операции с 2,9×10 вентилями, используя один фрагмент входных данных, на самом деле не имеет смысла предполагать, что такое большое количество вентилей может управляться квантовым компьютером в нетривиальных задачах. время.
Я бы предположил, что для того, чтобы квантовый компьютер выполнил один шаг выполнения алгоритма Шора, необходимо было бы (логически) пропустить один вход через все эти вентили, что было бы аналогично классическому компьютеру, выполняющему достаточно компьютерного кода, чтобы пропустить один 2048-битный вход через 2,9×10†. · ворота.Поскольку информация не может двигаться быстрее скорости света, а ворота имеют ненулевые размеры, это не может произойти за тривиальное время. И если вы используете фотоны для кубитов в квантовом компьютере, длина волны, вероятно, задает минимальные размеры для ворот независимо от производственных возможностей.
И если вам нужно какое-либо исправление ошибок между шлюзами, это потребует дополнительного пространства и, следовательно, также увеличит задержку.
Кроме того, если я правильно понял, чтобы фактически факторизовать большие числа с помощью алгоритма Шора, вам нужно использовать классический компьютер для генерации случайного предположения, и алгоритм Шора затем будет использовать это предположение, чтобы, возможно, выдать данные, необходимые для вычисления факторов. Сколько в среднем догадок вам действительно потребуется для факторизации чисел, используемых в 2048-битном RSA?
Проводились ли исследования потенциального практического времени работы большого физического квантового компьютера, пытающегося выполнить алгоритм Шора для разложения больших чисел на множители? Действительно ли это поддерживает интерпретацию того, что вы можете просто игнорировать время обработки независимо от размера чисел?
