Рейтинг:4

Можете ли вы действительно игнорировать количество шагов квантовой обработки, необходимых для алгоритма Шора?

флаг gs

Ответы на вопрос Длина ключа 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?

Проводились ли исследования потенциального практического времени работы большого физического квантового компьютера, пытающегося выполнить алгоритм Шора для разложения больших чисел на множители? Действительно ли это поддерживает интерпретацию того, что вы можете просто игнорировать время обработки независимо от размера чисел?

флаг us
Насколько я понимаю, мы можем решить проблемы примерно с 50 кубитами, даже не вопрос времени выполнения. Если вы посмотрите «проблему измерения» в разделе обмена физикой, вы можете заключить, что даже определение проблемы — это кот Шрёдингера.
флаг jp
"даже классические компьютеры не могут выполнять какие-либо операции с вентилями 2,9x10" с использованием одной части входных данных"? Какие? Да, они могут! За пару миллисекунд!
флаг jp
Возможно, первый квантовый компьютер, который сделает это, будет не очень быстрым, так что вместо пары миллисекунд на это уйдет неделя, месяц или год. Это все равно намного быстрее, чем "навсегда"
флаг gs
@user253751 user253751 Я согласен с тем, что современные компьютеры могут выполнять операции, работающие с вентилями 2,9 × 10 дюймов, за очень короткое время, выполняя достаточное количество инструкций последовательно. Это напрямую следует из того, что современные ЦП могут выполнять до 5×1010 инструкций в секунду на ядро. Я имел в виду, что не существует инструкций SIMD, которые могут выполняться с таким большим числом вентилей (транзисторов) как одна операция, а это означает, что последовательное выполнение отдельных операций будет важным ограничивающим фактором.
Рейтинг:3
флаг my

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

Вы неправильно понимаете, что измеряется «операциями ворот». У квантового компьютера не было бы $2,9 \умножить на 10^7$ ворота (и все данные повторно устанавливаются через этот набор ворот).

Вместо этого квантовый компьютер должен был бы выполнить в общей сложности $2,9 \умножить на 10^7$ операции с воротами; очевидно, что нет необходимости выполнять их все одновременно (и, собственно, с Шором мы не можем, как из-за того, что теорема о запрете клонирования запрещает генерировать копии кубитов для отправки в независимые гейты, так и по более прагматичной причине, что входы некоторых операций ворот зависят от предыдущих операций ворот).

Что касается того, как эти $2,9 \умножить на 10^7$ операции гейта сопоставляются с аппаратными гейтами, ну маловероятно, что у нас будет $2,9 \умножить на 10^7$ физические ворота; некоторые аппаратные вентили, вероятно, будут повторно использоваться несколько раз в ходе вычислений (так же, как когда классический компьютер выполняет операцию RSA, одни и те же вентили повторно используются для реализации различных операций модульного умножения).

И если вам нужно какое-либо исправление ошибок между шлюзами, это потребует дополнительного пространства и, следовательно, также увеличит задержку.

Да мы знаем; в $2,9 \умножить на 10^7$ рисунок выше отражает логические кубиты; это приведет к некоторому большему количеству физических кубитов - размер увеличения будет зависеть от используемого кода квантовой коррекции ошибок (который будет зависеть, среди прочего, от фактической частоты ошибок операций с физическими кубитами).

Сколько в среднем догадок вам действительно потребуется для факторизации чисел, используемых в 2048-битном RSA?

С крайне высокой вероятностью один. Квантовый компьютер находит порядок $г$ по модулю $n$, то есть значение $х$ куда $g^x \экв 1 \bmod n$. Если только не приказ $г$ в отношении обоих $р$ и $q$ (простые множители) аномально мало (что, как можно показать, происходит только с крошечной вероятностью, если $г$ был выбран случайным образом), то значение $х$ можно использовать для быстрого факторинга.

флаг gs
Отличная информация! Можно ли все это резюмировать следующим образом? Учитывая квантовый компьютер с 4099 кубитами, 2048-битный ключ RSA может быть взломан с помощью 2,9 $ \x 10 ^ 7 $ операций ворот, и это устанавливает общее необходимое время вычислений. Фактическое необходимое время стены определяется эффективной средней тактовой частотой инструкций этого компьютера для выполнения этих операций.
флаг gs
Согласно https://quantumcomputing.stackexchange.com/a/2404/18991, кажется, что квантовые компьютеры могут выполнять около 5 миллионов операций в секунду, поэтому общее необходимое вычислительное время составит всего около 6 секунд! Таким образом, если количество кубитов действительно можно увеличить до тысяч без замедления отдельных операций, то скорость выполнения должна быть достаточно хорошей, чтобы не быть ограничивающим фактором на практике.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.