Алгоритм Шора - это алгоритм квантового компьютера с полиномиальным временем для целочисленной факторизации . [1] Неформально это решает следующую проблему: если задано целое число, найдите его простые множители . Он был изобретен в 1994 году американским математиком Питером Шором .
На квантовом компьютере разложить целое число на множители , Алгоритм Шора работает за полиномиальное время (затраченное время полиномиально от , размер целого числа, заданного на входе). [2] В частности, он принимает квантовые ворота порядкаиспользуя быстрое умножение, [3] тем самым демонстрируя, что проблема целочисленной факторизации может быть эффективно решена на квантовом компьютере и, следовательно, относится к классу сложности BQP . Это почти экспоненциально быстрее, чем самый эффективный из известных классических алгоритмов факторизации, сито общего числового поля , которое работает в субэкспоненциальное время :. [4] Эффективность алгоритма Шора обусловлена эффективностью квантового преобразования Фурье и модульного возведения в степень с помощью повторных квадратов . [5]
Если бы квантовый компьютер с достаточным количеством кубитов мог работать, не поддаваясь квантовому шуму и другим явлениям квантовой декогеренции , то алгоритм Шора можно было бы использовать для взлома схем криптографии с открытым ключом , таких как широко используемая схема RSA . RSA основан на предположении, что разложение больших целых чисел на множители сложно вычислить. Насколько известно, это предположение справедливо для классических (неквантовых) компьютеров; не известен ни один классический алгоритм, который может разложить целые числа на множители за полиномиальное время. Однако алгоритм Шора показывает, что разложение целых чисел на множители эффективно на идеальном квантовом компьютере, поэтому может оказаться возможным победить RSA, построив большой квантовый компьютер. Это также было мощным мотиватором для разработки и создания квантовых компьютеров, а также для изучения новых алгоритмов квантовых компьютеров. Это также способствовало исследованию новых криптосистем, защищенных от квантовых компьютеров, которые в совокупности называются постквантовой криптографией .
В 2001 году алгоритм Шора был продемонстрирован группой в IBM , которая учла в , используя ЯМР-реализацию квантового компьютера скубиты. [6] После внедрения IBM две независимые группы реализовали алгоритм Шора с использованием фотонных кубитов, подчеркнув, что многокубитовая запутанность наблюдалась при выполнении схем алгоритма Шора. [7] [8] В 2012 году факторизацияпроводился с твердотельными кубитами. [9] Кроме того, в 2012 г. факторизациябыла достигнута, установив рекорд для наибольшего целого числа, факторизованного с помощью алгоритма Шора. [10] В 2019 году была предпринята попытка разложить число 35 на множитель с помощью алгоритма Шора на IBM Q System One , но алгоритм не удался из-за накопления ошибок. [11] Однако квантовые компьютеры с помощью других алгоритмов, в частности, квантового отжига, разложили на множители гораздо большие числа . [12]
Процедура
Проблема, которую мы пытаемся решить, заключается в том, что для составного числа , Чтобы найти нетривиальный делитель из (делитель строго между а также ). Прежде чем пытаться найти такой делитель, можно использовать относительно быстрые алгоритмы проверки простоты , чтобы убедиться, что действительно составной.
Нам нужно быть нечетным (иначе является делителем) и не должно быть степенью простого числа (в противном случае это простое число является делителем), поэтому нам нужно проверить, что нет целых корней для .
Следовательно, мы можем считать, что является произведением двух взаимно простых целых чисел, больших, чем. Из китайской теоремы об остатках следует, что существует не менее четырех различных квадратных корней из по модулю (поскольку у каждого модульного уравнения есть два корня). Цель алгоритма - найти квадратный корень из по модулю это отличается от а также , потому что тогда
для ненулевого целого числа что дает нам нетривиальные делители а также из . Эта идея похожа на другие алгоритмы факторизации , такие как квадратное решето .
В свою очередь, найдя такой сводится к поиску элемента четного периода с некоторым дополнительным свойством (как поясняется ниже, требуется, чтобы не выполнялось условие шага 6 классической части). Квантовый алгоритм используется для нахождения периода случайно выбранных элементов., так как на классическом компьютере это сложная задача.
Алгоритм Шора состоит из двух частей:
- Сведение, которое может быть выполнено на классическом компьютере, проблемы факторизации к проблеме определения порядка .
- Квантовый алгоритм для решения задачи нахождения порядка.
Классическая часть
- Выберите случайное число .
- Вычислить , То наибольший общий делитель из а также . Это можно сделать с помощью алгоритма Евклида .
- Если , то это число является нетривиальным множителемИтак, мы закончили.
- В противном случае используйте подпрограмму квантового определения периода (см. Ниже), чтобы найти , который обозначает период следующей функции:
- Если является нечетным, затем вернитесь к шагу 1.
- Если , затем вернитесь к шагу 1.
- В противном случае оба а также являются нетривиальными факторами Итак, мы закончили.
Например: Дано , , а также , у нас есть , где а также . Для это произведение двух различных простых чисел, а также , значение просто , который для является , а также разделяет .
Квантовая часть: подпрограмма определения периода
Квантовые схемы, используемые для этого алгоритма, специально разработаны для каждого выбора и каждый выбор случайного используется в . Дано, найти такой, что , откуда следует, что . Регистры входных и выходных кубитов должны содержать суперпозиции значений из к , и так кубиты каждый. Использование того, что может показаться вдвое большим количеством кубитов, чем необходимо, гарантирует, что существует как минимум разные значения которые производят то же самое , даже если период подходы .
Действуйте следующим образом:
- Инициализировать регистры для
где обозначает тензорное произведение .
Это начальное состояние представляет собой суперпозицию состояний и легко получается путем генерации независимых кубитов , каждый из которых является суперпозицией а также состояния. Мы можем добиться этого, инициализировав кубиты в нулевом положении, а затем применив вентиль Адамара параллельно к каждому из кубиты, где . - Построить как квантовую функцию и примените ее к указанному выше состоянию, чтобы получить
- Примените обратное квантовое преобразование Фурье ко входному регистру. Это преобразование (работающее на суперпозиции состояния) использует -й корень из единства, такой как распределить амплитуду любого заданного заявлять одинаково среди всех принадлежащий состояний, и делать это по-разному для каждого . Таким образом, получаем
- быть -й корень из единства,
- быть периодом ,
- быть самым маленьким из для которого (у нас есть ), а также
- написать
- индексирует эти , убегая от к , чтобы .
- Выполните измерение. Получаем какой-то результат во входном регистре и какой-то результат в выходном регистре. В виде является периодическим, вероятность измерения некоторого состояния дан кем-то
- С близко к некоторому целому числу , известное значение близко к неизвестному значению . Выполнение [классического] разложения цепной дроби на позволяет нам находить приближения из него, которые удовлетворяют двум условиям: Учитывая эти множественные условия (и предполагая, что является неприводимым ), очень вероятно, будет подходящий период , или, по крайней мере, один из факторов.
- .
- .
- Проверить (классически), если . Если так, то все готово.
- В противном случае (классически) получить больше кандидатов на используя кратные , или используя другие с участием возле . Если какой-либо кандидат работает, то все готово.
- В противном случае попробуйте еще раз, начиная с шага 1 этой подпрограммы.
Пояснение к алгоритму
Алгоритм состоит из двух частей. Первая часть алгоритма превращает задачу факторизации в задачу нахождения периода функции и может быть реализована классическим способом. Вторая часть находит период с помощью квантового преобразования Фурье и отвечает за квантовое ускорение.
Получение факторов из периода
Целые числа меньше и совмещать собразуют мультипликативную группу целых чисел по модулю N {\ displaystyle N} , которая является конечной абелевой группой . Размер этой группы определяется как. К концу шага 3 у нас есть целое числов этой группе. Поскольку группа конечна, должен иметь конечный порядок , которое является наименьшим положительным целым числом такое, что
Следовательно, разделяет (также написано ). Предположим, что мы можем получитьи что это даже. (Если нечетно, то на шаге 5 мы должны перезапустить алгоритм с другим случайным числом ) Сейчас квадратный корень из по модулю это отличается от . Это потому что это порядок по модулю , так , иначе порядок в этой группе будет . Если, то на шаге 6 мы должны перезапустить алгоритм с другим случайным числом .
В конце концов, мы должны ударить порядка в такой, что . Это потому, что такой квадратный корень из по модулю Кроме как а также , существование которой гарантируется китайской теоремой об остатках, поскольку не главная сила.
Мы утверждаем, что является правильным фактором , т.е. . Фактически, если, тогда разделяет , чтобы , что противоречит построению . Если же, с другой стороны,, то по тождеству Безу существуют целые числа такой, что
Умножая обе стороны на , мы получаем
В виде разделяет , мы находим, что разделяет , чтобы , что снова противоречит построению .
Следовательно, это необходимый коэффициент .
Определение периода
Алгоритм определения периода Шора во многом полагается на способность квантового компьютера находиться во многих состояниях одновременно.
Физики называют такое поведение « суперпозицией » состояний. Чтобы вычислить период функции, мы оцениваем функцию одновременно во всех точках.
Однако квантовая физика не позволяет нам напрямую получить доступ ко всей этой информации. Измерение будет давать только один из всех возможных значений, уничтожая всех остальных. Если бы не теорема о запрете клонирования , мы могли бы сначала измерить без измерения , а затем сделайте несколько копий результирующего состояния (которое представляет собой суперпозицию состояний, у всех одинаковые ). Измерение по этим штатам предоставит разные значения, которые дают одинаковые , ведущий к периоду. Поскольку мы не можем сделать точные копии квантового состояния , этот метод не работает. Следовательно, мы должны тщательно преобразовать суперпозицию в другое состояние, которое с большой вероятностью вернет правильный ответ. Это достигается квантовым преобразованием Фурье .
Таким образом, Шору пришлось решить три проблемы «реализации». Все они должны были быть реализованы «быстро», что означает , что они могут быть реализованы с числом квантовых вентилей , который является многочлен в.
- Создайте суперпозицию состояний. Это можно сделать, применив вентили Адамара ко всем кубитам во входном регистре. Другой подход - использовать квантовое преобразование Фурье (см. Ниже).
- Реализуйте функцию как квантовое преобразование. Для этого Шор использовал многократное возведение в квадрат для своего модульного преобразования возведения в степень. Важно отметить, что этот шаг сложнее реализовать, чем квантовое преобразование Фурье, поскольку для его выполнения требуются вспомогательные кубиты и значительно больше вентилей.
- Выполните квантовое преобразование Фурье. Используя вентили управляемого вращения и вентили Адамара, Шор разработал схему для квантового преобразования Фурье (с), который использует только ворота. [14]
После всех этих преобразований измерение даст приближение к периоду . Для простоты предположим, что существует такой, что целое число. Тогда вероятность измерения является . Чтобы увидеть это, мы замечаем, что тогда
для всех целых чисел . Следовательно, сумма, квадрат которой дает нам вероятность измерить будет , в виде занимает примерно значений и, следовательно, вероятность . Есть возможные значения такой, что целое число, а также возможности для , поэтому в сумме вероятностей .
Примечание. Другой способ объяснить алгоритм Шора - это отметить, что это всего лишь замаскированный алгоритм квантовой оценки фазы .
Узкое место
Узким местом выполнения алгоритма Шора является квантовое модульное возведение в степень , которое намного медленнее, чем квантовое преобразование Фурье и классическая предварительная / постобработка. Существует несколько подходов к построению и оптимизации схем для модульного возведения в степень. Самый простой и (в настоящее время) наиболее практичный подход - имитировать обычные арифметические схемы с обратимыми вентилями , начиная с сумматоров с переносом пульсации . Знание базы и модуля возведения в степень облегчает дальнейшую оптимизацию. [15] [16] Реверсивные схемы обычно используются в порядке ворота для кубиты. Альтернативные методы асимптотически улучшают количество вентилей с помощью квантовых преобразований Фурье , но не могут конкурировать с менее чем 600 кубитами из-за высоких констант.
Дискретные логарифмы
Учитывая группу с заказом и генератор , предположим, мы знаем, что , для некоторых , и мы хотим вычислить , который представляет собой дискретный логарифм :. Рассмотрим абелеву группу, где каждый коэффициент соответствует модульному сложению значений. Теперь рассмотрим функцию
Это дает нам абелеву проблему скрытых подгрупп , так каксоответствует гомоморфизму групп . Ядро соответствует кратным. Итак, если мы сможем найти ядро, мы сможем найти.
Смотрите также
- GEECM , алгоритм факторизации, который, как говорят, «часто намного быстрее, чем алгоритм Шора» [17]
- Алгоритм Гровера
Рекомендации
- Перейти ↑ Shor, PW (1994). «Алгоритмы квантовых вычислений: дискретные логарифмы и факторизация». Материалы 35-го ежегодного симпозиума по основам информатики . IEEE Comput. Soc. Пресс: 124–134. DOI : 10.1109 / sfcs.1994.365700 . ISBN 0818665807.
- ^ См. Также псевдополиномиальное время .
- ^ Бекман, Дэвид; Chari, Amalavoyal N .; Девабхактуни, Шрикришна; Прескилл, Джон (1996). «Эффективные сети для квантового факторинга» (PDF) . Physical Review . 54 (2): 1034–1063. arXiv : квант-ph / 9602016 . Bibcode : 1996PhRvA..54.1034B . DOI : 10.1103 / PhysRevA.54.1034 . PMID 9913575 .
- ^ "Сито числового поля" . wolfram.com . Проверено 23 октября 2015 года .
- ^ Гидни, Крейг. «Алгоритм квантового факторинга Шора» . Алгоритмические утверждения . Проверено 28 ноября 2020 .
- ^ Vandersypen, Lieven MK; Штеффен, Матиас; Брейта, Грегори; Yannoni, Costantino S .; Шервуд, Марк Х. и Чуанг, Исаак Л. (2001), «Экспериментальная реализация алгоритма квантового разложения Шора с использованием ядерного магнитного резонанса» (PDF) , Nature , 414 (6866): 883–887, arXiv : Quant-ph / 0112176 , Bibcode : 2001Natur.414..883V , CiteSeerX 10.1.1.251.8799 , DOI : 10.1038 / 414883a , PMID 11780055
- ^ Лу, Чао-Ян; Браун, Дэниел Э .; Ян, Тао и Пан, Цзянь-Вэй (2007), «Демонстрация скомпилированной версии алгоритма квантового факторинга Шора с использованием фотонных кубитов» (PDF) , Physical Review Letters , 99 (25): 250504, arXiv : 0705.1684 , Bibcode : 2007PhRvL ..99y0504L , DOI : 10,1103 / PhysRevLett.99.250504 , PMID 18233508
- ^ Ланьон, BP; Weinhold, TJ; Лэнгфорд, штат Северная Каролина; Barbieri, M .; Джеймс, DFV; Гилкрист, А. и Уайт, А.Г. (2007), «Экспериментальная демонстрация скомпилированной версии алгоритма Шора с квантовой запутанностью» (PDF) , Physical Review Letters , 99 (25): 250505, arXiv : 0705.1398 , Bibcode : 2007PhRvL .. 99y0505L , DOI : 10,1103 / PhysRevLett.99.250505 , ЛВП : 10072/21608 , PMID 18233509
- ^ Лусеро, Эрик; Барендс, Рами; Чен, Ю; Келли, Джулиан; Мариантони, Маттео; Мегрант, Энтони; О'Мэлли, Питер; Затонул, Даниэль; Вайнсенчер, Амит; Веннер, Джеймс; Белый, Тед; Инь, Йи; Cleland, Andrew N .; Мартинис, Джон М. (2012). "Вычисление простых факторов с помощью квантового процессора джозефсоновских фазовых кубитов". Физика природы . 8 (10): 719. arXiv : 1202.5707 . Bibcode : 2012NatPh ... 8..719L . DOI : 10.1038 / nphys2385 .
- ^ Мартин-Лопес, Энрике; Мартин-Лопес, Энрике; Лэйнг, Энтони; Лоусон, Томас; Альварес, Роберто; Чжоу, Сяо-Ци; О'Брайен, Джереми Л. (12 октября 2012 г.). «Экспериментальная реализация алгоритма квантового факторизации Шора с использованием рециклинга кубитов». Природа Фотоника . 6 (11): 773–776. arXiv : 1111.4147 . Bibcode : 2012NaPho ... 6..773M . DOI : 10.1038 / nphoton.2012.259 .
- ^ Амико, Мирко; Saleem, Zain H .; Кумф, Мьюир (2019-07-08). "Экспериментальное исследование алгоритма факторинга Шора на IBM Q" . Physical Review . 100 (1): 012305. arXiv : 1903.00768 . DOI : 10.1103 / PhysRevA.100.012305 . ISSN 2469-9926 .
- ^ Цзян, Шусянь; Britt, Keith A .; Маккаски, Александр Дж .; Скромный, Трэвис С .; Кайс, Сабер (5 декабря 2018 г.). «Квантовый отжиг для первичной факторизации» . Научные отчеты . 8 (1): 17667. arXiv : 1804.02733 . Bibcode : 2018NatSR ... 817667J . DOI : 10.1038 / s41598-018-36058-Z . ISSN 2045-2322 . PMC 6281593 . PMID 30518780 .
- ^ Авторы Qiskit. «Учебник Qiskit: квантовая оценка фазы» . IBM . Дата обращения 7 ноября 2020 .
- ↑ Шор, 1999 , стр. 14
- ^ Марков, Игорь Л .; Саиди, Мехди (2012). "Оптимизированные константами квантовые схемы для модульного умножения и возведения в степень". Квантовая информация и вычисления . 12 (5–6): 361–394. arXiv : 1202,6614 . Bibcode : 2012arXiv1202.6614M . DOI : 10.26421 / QIC12.5-6-1 .
- ^ Марков, Игорь Л .; Саиди, Мехди (2013). «Более быстрое квантовое числовое разложение посредством синтеза схем». Phys. Rev. A . 87 (1): 012310. arXiv : 1301.3210 . Bibcode : 2013PhRvA..87a2310M . DOI : 10.1103 / PhysRevA.87.012310 .
- ^ Бернштейн, Даниэль Дж .; Хенингер, Надя ; Лу, Пол; Валентина, Люк (2017). «Постквантовый RSA» (PDF) . Международный семинар по постквантовой криптографии . Конспект лекций по информатике. 10346 : 311–329. DOI : 10.1007 / 978-3-319-59879-6_18 . ISBN 978-3-319-59878-9. Архивировано (PDF) из оригинала 20 апреля 2017 года.
дальнейшее чтение
- Нильсен, Майкл А. и Чуанг, Исаак Л. (2010), Квантовые вычисления и квантовая информация, 10-е юбилейное издание , Cambridge University Press, ISBN 9781107002173.
- Филип Кэй, Раймонд Лафламм, Мишель Моска, Введение в квантовые вычисления , Oxford University Press, 2007, ISBN 0-19-857049-X
- «Объяснение для человека на улице» по Ааронсон , « утвержден » Питер Шор. (Шор написал: «Отличная статья, Скотт! Это лучшая работа по объяснению квантовых вычислений обывателю из всех, что я видел»). Альтернативная метафора QFT была представлена в одном из комментариев . Скотт Ааронсон предлагает следующие 12 ссылок для дальнейшего чтения (из «10 10 5000 руководств по квантовым алгоритмам, которые уже есть в сети»):
- Шор, Питер В. (1997), "Полиномиальные алгоритмы для простой факторизации и дискретных логарифмов на квантовом компьютере", SIAM J. Comput. , 26 (5): 1484–1509, arXiv : Quant-ph / 9508027v2 , Bibcode : 1999SIAMR..41..303S , doi : 10.1137 / S0036144598347011. Отредактированная версия оригинальной статьи Питера Шора («28 страниц, LaTeX. Это расширенная версия статьи, опубликованной в Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Санта-Фе, Нью-Мексико, 20 ноября. 22, 1994. Незначительные исправления внесены в январе 1996 г. ").
- Квантовые вычисления и алгоритм Шора , Страница квантовых алгоритмов Мэтью Хейворда , 2005-02-17, imsa.edu, LaTeX2HTML-версия исходного документа LaTeX , также доступная в формате PDF или postscript .
- Квантовые вычисления и алгоритм факторинга Шора , Рональд де Вольф, CWI и Амстердамский университет, 12 января 1999 г., постскриптум на 9 страницах.
- Алгоритм факторинга Шора , Заметки из лекции 9 Berkeley CS 294–2 от 4 октября 2004 г., 7-страничный постскриптум.
- Глава 6 Квантовые вычисления , 91-страничный постскриптум, Caltech, Preskill, PH229.
- Квантовые вычисления: учебное пособие по Сэмюэл Л. Браунштейн .
- Квантовые состояния алгоритма Шора , Нил Янг, последнее изменение: вторник, 21 мая, 11:47:38 1996.
- III. Взлом RSA-шифрования с помощью квантового компьютера: алгоритм факторинга Шора , конспект лекций по квантовым вычислениям, Корнельский университет, физика 481–681, CS 483; Весна 2006 г. Н. Дэвид Мермин. Последняя редакция 28 марта 2006 г., 30-страничный документ PDF.
- Lavor, C .; Мансур, LRU; Португалия, Р. (2003). «Алгоритм Шора факторинга больших целых чисел». arXiv : квант-ph / 0303175 .
- Ломонако-младший (2000). «Алгоритм квантового факторинга Шора». arXiv : квант-ph / 0010034 .Эта статья представляет собой письменную версию часовой лекции по квантовому алгоритму разложения Питера Шора. 22 страницы.
- Глава 20 «Квантовые вычисления» , « Вычислительная сложность: современный подход» , черновик книги: от января 2007 г., Санджив Арора и Боаз Барак, Принстонский университет. Опубликовано как Глава 10 Квантовые вычисления Санджив Арора, Боаз Барак, «Вычислительная сложность: современный подход», Cambridge University Press, 2009, ISBN 978-0-521-42426-4
- Шаг к квантовым вычислениям: запутывание 10 миллиардов частиц , из журнала Discover, датированного 19 января 2011 года.
- Йозеф Груска - Вызовы квантовых вычислений также в математике без ограничений: 2001 г. и далее , редакторы Бьёрн Энгквист, Вильфрид Шмид, Springer, 2001 г., ISBN 978-3-540-66913-5
Внешние ссылки
- Версия 1.0.0 libquantum : содержит реализацию алгоритма Шора на языке C с имитируемой библиотекой квантового компьютера, но для переменной ширины в short.c следует установить значение 1, чтобы повысить сложность выполнения.
- Компания PBS Infinite Series создала два видеоролика, объясняющих математику алгоритма Шора: « Как взломать криптографию » и « Взломать на квантовой скорости с помощью алгоритма Шора ».