Алгоритм факторинга Шора

27

У меня небольшие проблемы с полным пониманием последних шагов алгоритма факторинга Шора.

Учитывая мы хотим вычислить, мы выбираем случайный который имеет порядок .Nxr

Первый шаг включает в себя настройку регистров и применение оператора Адамара. На втором этапе применяется линейный оператор. На третьем шаге измеряется второй регистр (я считаю, что этот шаг можно выполнить позже). Четвертый шаг дискретного преобразования Фурье применяется к первому регистру. Затем мы измеряем первый регистр.

Вот где я немного туманен:

Мы получаем измерение в виде .j,xkmodN

Отсюда можно найти сходимости дроби , сходимыми являются возможные значения порядка . Здесь мы просто попробуем все сходящиеся и если мы не найдем качестве одного из сходящихся, мы просто начнем снова?j2qr<Nr

Кроме того, как отличается вероятность для возможных значений ? Они, как я понимаю, должны иметь одинаковую вероятность, но в статье Шора говорится, что это не так?j

Просто немного сбит с толку, так как некоторые газеты, кажется, говорят разные вещи.

Спасибо.

Каллум
источник
21
@Peter Shor может даже помочь вам с этим.
Дейв Кларк,
1
Задавая эти вопросы, я думаю, что лучше понимаю это. Чтобы уточнить для тех, кто заинтересован, мы получаем измерение в виде j,xkmodN где все, что нам нужно, это j . Значение j можно записать как j=2qk/r , разделив на 2q мы получим k/r и из этого мы можем найти его сходящиеся, знаменатель <N сходящегося является возможным значением r , если это не алгоритм запускается снова. Вероятность нахождения j основана на сумме, которая зависит от значения 2q и периода r .
Каллум

Ответы:

47

Отсюда можно найти сходимости дроби j/2q , сходимыми являются возможные значения порядка r. Здесь мы просто попробуем все сходящиеся <N и если мы не найдем r качестве одного из сходящихся, мы просто начнем снова?

Ты мог бы; алгоритм работает довольно быстро, если вы делаете. Если вы хотите уменьшить ожидаемое количество квантовых шагов, вы можете также сделать некоторые другие тесты; например, вы должны проверить, является ли кратным одного из сходящихся. Но если вы не найдете после этих расширенных тестов, вам нужно начать заново.rr

Кроме того, как отличается вероятность для возможных значений ? Они, как я понимаю, должны иметь одинаковую вероятность, но в статье Шора говорится, что это не так?j

Я не знаю, смогу ли я вам чем-нибудь помочь, потому что вы не дали мне достаточно информации, чтобы я объяснил, почему вы сбиты с толку. Вероятность для каждого значения во фракции (почти) одинакова. Однако в зависимости от того, где именно находится между соседними значениями и , вероятности конкретных значений различаются.kk/rk/rj/2q(j+1)/2qj

Питер Шор
источник
33
Мне нравится, как вы называете газету "бумагой Шора" :)
Suresh Venkat
Я просто немного не уверен в том, как работает вероятность, вот и все. я, сказав, что . В примерах, которые я видел, была симметрия в распределении вероятностей относительно средней точки оси , всегда ли это так? Предположим, что , означает ли это, что для всех возможных значений , где , все будут иметь равную вероятность из ? Спасибо. Prob(j)=12q×([2qk1r]+1)|a=0[2qk1r]e2πirja/2q|2xr=2tj=k02qrk0=0,,r1j12t
Каллум
3
Если , то на самом деле все возможные значения будут иметь равную вероятность . r=2tj1/2t
Питер Шор