Оценка фазы и основа алгоритма Шора
После рассмотрения алгоритма Дойча-Йожа и алгоритма Гровера, сегодня мы сосредоточимся на квантовом преобразовании Фурье. Основная концепция, которую мы будем развивать здесь, заключается в использовании квантового компьютера для разработки аналога дискретного преобразования Фурье (ДПФ). ДПФ играет важную роль в цифровой обработке сигналов и позволяет нам разделить входной сигнал, который разбросан во времени, на количество частот определенных амплитуд и фаз, чтобы все эти частоты могли сформировать исходный сигнал.Давайте посмотрим, как мы можем построить квантовый аналог ДПФ, и это ляжет в основу алгоритма Шора и квантовой оценки фазы. Этот пост будет немного тяжелым по математике, но вы можете привыкнуть, проверив предыдущие посты.
От классического до квантового: ДПФ
Начнем с классического ДПФ. Мы можем записать правило преобразования как —
Формула может показаться немного пугающей, но на самом деле она довольно проста. Давайте воплотим это в жизнь. Рассмотрим xⱼ= 2, 1, вычислим y
Поскольку векторы состояния для кубитов являются векторами комплексных чисел, мы можем понять, что и к ним применимо ТПФ. Рассмотрим |ψ⟩ = ∑ aⱼ |j⟩. Можно вычислить ДПФ этого состояния как —
Лучший способ думать о КТП как о ТПФ, применяемом к амплитудам квантового состояния. Кроме того, мы видим, что F является линейным. Мы также можем думать о вышеупомянутом преобразовании как о карте между двумя векторами состояния как —
Возможность выполнения таких преобразований физически зависит от того, является ли оператор F унитарным или нет, и можно легко показать, что F действительно унитарный (попробуйте сами еще проверьте мой блокнот, ссылка в конце поста).
Давайте рассмотрим состояние одного кубита как |ψ⟩=α|0⟩+β|1⟩. Каким будет результат после применения QFT к этому состоянию? Мы уже видели, что применение КТП к состоянию влияет только на амплитуду состояния. Рассчитаем изменение амплитуды по уравнению (2). Здесь N=2¹, таким образом —
Таким образом, F|ψ⟩=b₀|0⟩+b₁|1⟩= (1/√ 2)(α+β)|0⟩+(1/√2)(α−β) |1⟩. Итак, мы видим, что амплитуды изменились от α→(1/√2)(α+β) и β→(1/√2)(α−β). Мы уже знаем это преобразование, это преобразование Адамара (H), применяемое к состоянию одного кубита. Здесь следует отметить два важных момента: во-первых, мы видим, что наша исходная база, основа Z, изменилась на основу X, а во-вторых, вентиль H будет важным компонентом для построения схема QFT. Но является ли вентиль H единственным компонентом, который нам нужен для построения схемы QFT? Давайте посмотрим на аналогичный пример, как показано выше, но мы будем использовать 2 кубита.
|ψ⟩=a_{00}|00⟩+a_{01}|01⟩+a_{ 10}|10⟩+a_{11}|11⟩, здесь N=2² . Давайте просто посчитаем преобразованные амплитуды
Если мы рассмотрим ω=exp(iπ/2), затем ω⁴=1 и так далее… Для этого случая с двумя кубитами мы можем записать матрицу преобразования как —
Если мы сравним преобразование, примененное к состоянию 1 кубита, с этими 2 состояниями кубита, мы увидим, что, хотя амплитуды для преобразований 1 кубита являются действительными (мы знаем это также из преобразования Адамара), здесь мы имеем действительные, а также комплексные амплитуды. Кроме того, вентиль Адамара является обратным самому себе, а эта матрица преобразования — нет. На этом этапе, внимательно изучив bₖ, мы видим, что помимо суперпозиции нам также нужно ввести некоторые фазовые ворота. Фазовые ворота формы ниже сделают эту работу —
Мы также видим, что вращение зависит и от других битов, поэтому вместо простого фазового вентиля мы можем ввести управляемый фазовый вентиль (CP), как показано ниже:
Действие CP в двухкубитном состоянии |x₀x₁⟩, где первый кубит является управляющим, а второй — целевым дан кем-то -
На этом этапе также важно описать ворота H с точки зрения вращения —
Обобщенное правило квантового преобразования Фурье:
Учитывая квантовое состояние с n кубитами, обобщенное правило квантового преобразования Фурье выглядит следующим образом:
где члены в показателях степени могут быть расширены, как показано ниже:
С этим обобщенным выражением, возможно, становится более понятным, почему нам нужен вентиль суперпозиции (H) вместе с управляемым фазовым вентилем.
Давайте посмотрим, как мы можем создать такое преобразование, используя вентили Адамара и контролируемой фазы, и для этого мы рассмотрим 3 вентиля.
- Применить вентиль H к 1-му кубиту
2. Применить фазовый вентиль к |x₀⟩ в зависимости от |x₁⟩, т.е. управляемый фазовый вентиль
3. Примените второй управляемый фазовый вентиль к |x₀⟩ с |x₂⟩ в качестве управляющего бита.
4. Теперь мы повторяем процесс для второго кубита, поэтому применяем вентиль H ко второму кубиту.
5. Теперь применяем управляемый фазовый вентиль на 2-м кубите в зависимости от 3-го кубита
6. Наконец, мы применяем вентиль H к последнему кубиту.
Мы можем легко сравнить с уравнением 8 и увидеть, что наш результат аналогичен для n=3 кубитов, за исключением порядка кубитов; Итак, нам нужно поменять местами кубиты |x₂⟩ и |x₀⟩, к счастью, есть своп-гейты, которые сделают эту работу за нас! Давайте построим схему с помощью Qiskit.
Построение схемы квантового преобразования Фурье:
Мы обсудили шаги по построению схемы квантового преобразования Фурье для 3 кубитов, и здесь мы будем использовать библиотеку Qiskit для пошагового построения схемы.
Ниже приведен блок кода, который мы будем использовать для построения схемы QFT для 3 кубитов.
Мы можем нарисовать схему, добавив немного «стиля», и она выглядит так:
Используя эту схему, попробуем закодировать состояние |110⟩. Поэтому мы будем использовать приведенную выше схему с небольшими изменениями, как показано ниже:
Лучший способ понять результат QFT - построить векторы состояния, как показано ниже:
circ1.save_statevector()
qasm_sim = q.Aer.get_backend('qasm_simulator')
statevector = qasm_sim.run(circ1).result().get_statevector()
q.visualization.plot_bloch_multivector(statevector)
Изначально кубит 0 находился в состоянии |0⟩, а кубиты 1 и 2 находились в состоянии |1⟩. Мы пытаемся закодировать состояние |110⟩, также известное как 6 (2² +2¹+0). Таким образом, первый кубит поворачивается точно на 6/2³ ×2π=270∘. Второй кубит вращается на 6/2²×2π=540∘=2π+π, а третий кубит вращается на 6/2¹×2π=3×2π. Также важно отметить, что эти углы рассчитываются от начальной стадии |˜0⟩, где все кубиты находятся в состоянии |+⟩, и мы достигли состояния |˜6⟩. ~ (тильда) — распространенный способ обозначения состояний в пространстве Фурье.
Квантовое преобразование Фурье будет чрезвычайно полезно позже, когда мы углубимся в алгоритм Шора, который также показал силу и важность квантовых вычислений. Мы вернемся к этому в следующем посте!
Будьте сильными и будьте здоровы!!
Использованная литература:
[1] «Квантовые вычисления и квантовая информация», Нильсен, М. и Чуанг, И. Страницы 217–220.
[2] Учебник Qiskit: Квантовое преобразование Фурье
[3] Моя записная книжка: Ссылка на GitHub
