Какое минимальное целочисленное значение имеет смысл сделать квантовую факторизацию?

11

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

SalvaCardona
источник
2
Очень точный расчет будет зависеть от таких деталей, как реализация операций сложения в квантовом алгоритме, а также от точных операций, используемых в лучшем классическом алгоритме факторизации. В обоих случаях мы часто привыкли игнорировать постоянные факторы в объеме требуемой работы, но даже больше в классическом случае, чем в квантовом случае. Вы были бы удовлетворены оценкой порядка величины (например, квантовое преимущество, полученное где-то между 350-370 битами - чтобы обеспечить возможный ответ, который я создал из воздуха, не основываясь на реальном анализе)?
Ниль де Бодрап,
@NieldeBeaudrap Я бы сказал, что по указанным вами причинам точное количество будет невозможно предоставить. Если ваша оценка «из воздуха» основана на каких-то рассуждениях, я думаю, это было бы интересно. (Другими словами, образованное предположение имеет ценность, но дикое предположение не имеет)
Дискретная ящерица
@DiscreteLizard: если бы у меня был надежный способ оценки, готовый к сдаче, я бы не дал пример ответа, не основанного на анализе :-) Я уверен, что есть разумный способ получить интересную оценку, но я бы ее использовал. возможность легко обеспечить будет иметь слишком большие полосы ошибок, чтобы быть очень интересным.
Ниль де Бёдрап,
Так как эта проблема (или была) обычно воспринимается как типичное «доказательство» того, что квантовые компьютеры способны на подвиги вне сфер классических вычислений, но почти всегда в строгих условиях сложности вычислений (то есть, пренебрегая всеми константами и действительны только для произвольно высокого ввода размеры) Я бы сказал, что приблизительный ответ (и его вывод) уже будет полезен / педагогичен. Может быть, люди из CS / absoluteCS могут быть готовы помочь.
agaitaarino
1
@agaitaarino: Я согласен, хотя ответ должен предполагать более или менее точный отчет о производительности лучших классических алгоритмов факторизации. Остальное может быть сделано достаточно хорошим учеником в области квантовых вычислений.
Ниль де Бодрап,

Ответы:

8

Квантовая часть алгоритма Шора, по сути, представляет собой единичное модульное возведение в степень, выполненное в суперпозиции, с последующим преобразованием Фурье и затем измерением. Модульное возведение в степень является безусловно самой дорогой частью.

Предположим, что [...] каждая элементарная логическая операция математической факторизации одинаково затратна по времени в классической и в квантовой факторизации

Если предположить, что модульное возведение в степень занимает ровно столько же времени на квантовом компьютере, сколько на классическом компьютере, то переход, когда квантовые вычисления стали лучше, произойдет при очень малом числе. Вычисление модульных возведений в степень очень быстро, классически, потому что вы можете использовать повторное возведение в квадрат. Я бы дико оценил кроссовер даже до того, как вы дойдете до 30-битных чисел (чисел более миллиарда).

Но квантовые компьютеры не собираются заниматься математикой так же быстро, как классические компьютеры . Например, на моем ноутбуке я могу сделать 1000-битное модульное возведение в степень в python за доли секунды. Но на предсказуемых квантовых компьютерах это заняло бы часы или дни. Проблема заключается в огромной ( огромной ) разнице в стоимости логических элементов AND.

|T

Итак, предположим, что мы получаем миллион T состояний в секунду, и мы хотим преобразовать это в скорость 64-битных сложений для сравнения с классической машиной. Для 64-битного сложения требуется 64 логических элемента И, для каждого из которых требуется 4 Т. 1 миллион, разделенный на 4, разделенный на 64, дает ... около 4 кГц. Для контраста классическая машина легко сделает миллиард дополнений в секунду. Квантовые сумматоры в миллион раз медленнее, чем классические сумматоры (опять же, дикая оценка, и имейте в виду, что это число должно улучшаться со временем).

Другой фактор, который стоит учитывать, - это разная стоимость квантовых и классических компьютеров. Если у вас есть сто миллионов долларов, и вы выбираете между одним квантовым компьютером и тысячей классических компьютеров, этот коэффициент 1000 должен быть учтен. В этом смысле мы могли бы сказать, что квантовые сумматоры в миллиард раз менее эффективны, чем классические сумматоры (в FLOPS / $).

Постоянный факторный штраф в миллиард обычно является немедленным нарушением условий сделки. И для квантовых алгоритмов с простым квадратичным преимуществом (таких как Гровер), я утверждаю, что это фактически нарушитель соглашения. Но алгоритм Шора экспоненциально улучшается по сравнению с классической стратегией, когда вы увеличиваете число битов в числе для вычисления коэффициента. Сколько битов, прежде чем мы съедим эту «жалкую» константу 10 ^ 9 с нашим экспоненциальным ростом в преимуществе?

Учтите, что RSA-640 был учтен в 2005 году, используя ~ 33 года процессора. Квантовый компьютер должен быть в состоянии сделать это число менее чем за день. Если у вас есть тысяча классических компьютеров, работающих над этой проблемой, они закончат работу примерно через две недели. Таким образом, кажется, что квант выигрывает на 640 битах, но только на порядок или три. Так, может быть, отсечка произойдет где-то около 500 бит?

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

Крейг Гидни
источник
Это хорошее усилие, но как вы оцениваете 30 бит? С чем именно вы сравниваете алгоритм Шора, когда считаете, что это вероятная точка пересечения?
Ниль де Бодрап,
1
@NieldeBeaudrap Как я уже сказал, это дикое предположение. Я рисую: модульное умножение имеет приличный постоянный коэффициент (классически). Так же и продолженные дроби. У алгоритмов факторинга также есть хорошие постоянные факторы? Возможно нет? Если это так, кроссовер произойдет почти сразу, а не в больших количествах. Если кто-то захочет сравнить эти две вещи друг с другом, я обновлю ответ. Я считаю "мясо" остальным.
Крейг Гидни
1
Я бы не стал возражать против этого как обеспечения интуиции, за исключением того, что ваше дикое предположение точно относится к предмету вопроса. (Этот вопрос также ставится таким образом, что предполагает осведомленность о проблемах тактовой частоты.) Самые быстрые методы для факторизации очень больших чисел включают в себя большие постоянные факторы, но на самом деле суть вопроса в этом; но для чисел около миллиарда мы могли бы даже рассмотреть пробное деление, используя таблицу простых чисел примерно до 32 767, что на практике было бы очень быстрым. Количественное сравнение даже с этим было бы началом.
Ниль де Бодрап,
6

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

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

  • Ван Метер, Ито и Лэдд. Архитектурно-зависимое время выполнения алгоритма Шора . Proc. Мезоскопическая сверхпроводимость + спинтроника 2006; [ arXiv: Quant-Ph / 0507023 ]

Ван Метер, Ито и Лэдд пытаются сравнить производительность алгоритма Шора с доступной вычислительной технологией, выполняющей сито числового поля (самый известный классический алгоритм для факторизации). У меня не было времени, чтобы разобраться в деталях этого документа - вероятно, можно получить превосходный ответ, но рисунок 1 этой статьи позволяет нам сделать разумную численную оценку:

введите описание изображения здесь

Здесь крутые кривые представляют время вычислений классических вычислительных сетей. Кривая, обозначенная «NFS, 104 ПК, 2003», по-видимому, указывает на вычисления (и предполагаемое время вычислений) для ста четырех персональных компьютеров около 2003 года, о чем сообщила RSA Security Inc. в 2004 году [ http: //www.rsasecurity. com / rsalabs / node.asp? id = 2096] .

NNvv2×1011операций в секунду. Гипотетический сравнительный анализ алгоритма Шора должен быть сделан на квантовом компьютере, работающем с сопоставимой тактовой частотой.

109

  • Несмотря на преимущество операций в секунду в 200 и более раз, график действительно показывает, когда эта классическая реализация NFS с частотой 200 ГГц превосходит квантовый компьютер с частотой 1 ГГц, выполняющий алгоритм Шора (примерно с 200-значными числами), и квантовый компьютер с частотой 1 МГц ( около 330 цифр).
  • У нас также есть кривая, проецирующая производительность «в 2018 году», которая в 1000 раз превышает классическую вычислительную мощность: перехваты с квантовыми компьютерами с тактовой частотой 1 ГГц и 1 МГц имеют 350-битные числа и 530-битные числа.

Увеличение точек пересечения по сравнению с квантовыми вычислениями, от расчета в 2003 году до прогнозируемого в 2018 году, представляющего увеличение тактовой частоты в 1000 раз, составляет примерно 5/3. Исходя из этого, мы можем оценить, что вычислительное преимущество по сравнению с размером чисел, которое может быть быстро решено классическим компьютером, благодаря увеличению скорости в 200 раз, составляет примерно 7/6. Затем мы можем оценить, что точка пересечения одного классического компьютера с тактовой частотой 1 ГГц, выполняющего NFS, с квантовым компьютером с тактовой частотой 1 ГГц, выполняющим алгоритм Шора, составляет около 170 битных чисел.

Итог - точный ответ будет зависеть от многих технических предположений, которые могут существенно изменить точный результат, поэтому лучше искать приблизительную оценку. Но этот вопрос был исследован, по крайней мере, один раз, и, сделав несколько предположений и экстраполяций на производительность, основанную на классической производительности в 2003 году, кажется, что алгоритмы Шора превзойдут самый известный классический алгоритм на основе операций за числами около 170 бит.

Ниль де Бодрап
источник
Это хороший ответ. Стоит отметить, что идея этой статьи об «элементарной логической операции» (очень уместно) находится на уровне логического элемента AND, а не на уровне инструкции CPU или операции BigInt (что, как я подозреваю, было тем, что спрашивал мышления). В своем собственном ответе я предполагал, что модульное возведение в степень было сделано «как классически», что, например, потребовало бы умножения БПФ. Вот почему я угадал число, которое было намного ниже, чем в этой статье, которая (соответственно) выполняет умножение школьных учебников с сумматорами пульсаций переноса для своей квантовой арифметики.
Craig Gidney
@SalvaCardona: я рекомендую, чтобы вы не приняли мой ответ. Мой анализ очень поверхностный, и вы должны подождать для лучшего анализа.
Ниль де Бёдрап,