Квантовый поиск периода для числа15

Пройдите шаги алгоритма Шора для поиска периода $f(x)=13^x\bmod15$, выписывая состояние после каждого шага. Первый регистр содержит три кубита, второй — четыре. Разрешается десятичная запись, например $|3\rangle$вместо$|011\rangle$.

(a) Инициализируйте оба регистра в $|0\rangle$.

(b) Примените H к каждому кубиту первого регистра.

(c) Прибавьте $13^x\bmod15$ ко второму регистру, где x—значение первого.

(d) Сгруппируйте слагаемые с одинаковым f(x). Покажите периодичность амплитуд и объясните, почему обычное измерение не выявляет период эффективно.

(e) Примените квантовое преобразование Фурье к первому регистру.

(f) Каковы исходы его измерения и их связь с r? Какие исходы были бы для первого регистра из 8 кубитов и как тогда извлечь r?

Используйте соглашение $QFT_N|x\rangle=N^{-1/2}\sum_{y=0}^{N-1}e^{-2\pi ixy/N}|y\rangle$.