Kwantowa transformata Fouriera

W tym module Qiskit in Classrooms studenci muszą mieć działające środowisko Python z zainstalowanymi następującymi pakietami:

• qiskit w wersji 2.1.0 lub nowszej
• qiskit-ibm-runtime w wersji 0.40.1 lub nowszej
• qiskit-aer w wersji 0.17.0 lub nowszej
• qiskit.visualization
• numpy
• pylatexenc

Aby skonfigurować i zainstalować powyższe pakiety, zapoznaj się z przewodnikiem Instalacja Qiskit. Aby uruchamiać zadania na prawdziwych komputerach kwantowych, studenci muszą założyć konto IBM Quantum®, postępując zgodnie z krokami opisanymi w przewodniku Konfiguracja konta IBM Cloud.

Ten moduł był testowany i zużył 13 sekund czasu QPU. To szacunek w dobrej wierze — rzeczywiste zużycie może się różnić.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Wprowadzenie

Transformata Fouriera to wszechobecne narzędzie mające zastosowanie w matematyce, fizyce, przetwarzaniu sygnałów, kompresji danych i niezliczonych innych dziedzinach. Kwantowa wersja transformaty Fouriera, trafnie nazwana kwantową transformatą Fouriera, stanowi podstawę niektórych z najważniejszych algorytmów kwantowych.

Dzisiaj, po przypomnieniu klasycznej transformaty Fouriera, omówimy, jak implementujemy kwantową transformatę Fouriera na komputerze kwantowym. Następnie omówimy jedno z zastosowań kwantowej transformaty Fouriera w algorytmie zwanym algorytmem estymacji fazy. Kwantowa estymacja fazy jest podprogramem słynnego algorytmu faktoryzacji Shora, który bywa określany mianem „klejnotu koronnego" informatyki kwantowej. Ten moduł prowadzi do kolejnego modułu poświęconego w całości algorytmowi Shora, ale jest też zaprojektowany jako samodzielna całość. Kwantowa transformata Fouriera to fascynujący i użyteczny algorytm sam w sobie!

Klasyczna transformata Fouriera

Zanim przejdziemy do kwantowej transformaty Fouriera, najpierw przypomnijmy sobie jej klasyczną wersję. Transformata Fouriera to metoda przejścia z jednej tak zwanej „bazy" do innej. Możesz myśleć o dwóch bazach jak o różnych perspektywach tego samego problemu — obie są poprawnymi sposobami wyrażenia funkcji, ale jedna lub druga może być bardziej pouczająca, w zależności od rozpatrywanego problemu. Przykładami par baz połączonych transformatą Fouriera są: położenie i pęd oraz czas i częstotliwość.

Zobaczmy przykład, jak transformata Fouriera może nam pomóc ustalić, jaką nutę gra instrument, na podstawie jego przebiegu dźwiękowego. Zazwyczaj przebiegi są reprezentowane w bazie czasu — to znaczy amplituda fali jest wyrażana jako funkcja czasu.

Możemy wykonać transformatę Fouriera tego przebiegu, aby przejść z bazy czasu do bazy częstotliwości:

W bazie częstotliwości możemy łatwo zobaczyć wyraźne maksimum przy około 260 Hz. To środkowe C!

Być może byłeś w stanie stwierdzić, że grane jest środkowe C bez użycia transformaty Fouriera, ale co jeśli kilka nut jest granych jednocześnie? Wtedy przebieg staje się bardziej skomplikowany, gdy przedstawimy go w bazie czasu:

Ale widmo częstotliwościowe wyraźnie identyfikuje trzy maksima:

To był akord C-dur, złożony z nut C, E i G.

Tego rodzaju analiza Fouriera może pomóc nam wyodrębnić składowe częstotliwościowe dowolnego skomplikowanego sygnału.

Dyskretna transformata Fouriera

Transformata Fouriera jest użyteczna w wielu zastosowaniach związanych z przetwarzaniem sygnałów. Jednak w większości tych zastosowań z prawdziwego życia (w tym w przykładzie muzycznym podanym powyżej) chcemy transformować dyskretny zbiór $N$ punktów danych — a nie funkcję ciągłą. W tym przypadku stosujemy dyskretną transformatę Fouriera. Dyskretna transformata Fouriera (DFT) działa na wektorze $(x_0, ..., x_{N-1})$ i odwzorowuje go na wektor $(y_0, ..., y_{N-1})$ zgodnie ze wzorem:

$y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\omega_N^{jk}$

gdzie przyjmujemy $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$. (Zwróć uwagę, że istnieją inne konwencje ze znakiem minus w wykładniku, więc bądź ostrożny, gdy napotkasz DFT gdzie indziej.) Przypomnij sobie, że $e^{2\pi i \frac{jk}{N}}$ to funkcja periodyczna o okresie $\frac{N}{k}$. Zatem, mnożąc przez tę funkcję, transformata Fouriera jest w istocie sposobem na rozbicie (dyskretnej) funkcji $\{x_{j}\}$ na liniową kombinację jej składowych funkcji periodycznych, każda o okresie $\frac{N}{k}$.

Kwantowa transformata Fouriera

Widzieliśmy już, jak transformata Fouriera służy do reprezentowania funkcji jako liniowej kombinacji nowego zbioru tak zwanych „funkcji bazowych". Transformacje bazy są regularnie wykonywane również na stanach Qubit. Na przykład stan pojedynczego Qubit $|\psi\rangle$ może być wyrażony w bazie obliczeniowej $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$, ze stanami bazowymi $|0\rangle$ i $|1\rangle$, lub w bazie $X$: $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ ze stanami bazowymi $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ oraz $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$. Obie reprezentacje są równie poprawne, ale jedna może być bardziej naturalna niż druga, w zależności od rodzaju rozwiązywanego problemu.

Stany Qubit mogą być również wyrażone w bazie Fouriera, gdzie stan jest wyrażony w kategoriach liniowej kombinacji stanów bazy Fouriera $|\phi_y\rangle$, zamiast zwykłych stanów bazy obliczeniowej $|x\rangle$. Aby to zrobić, należy zastosować kwantową transformatę Fouriera (QFT):

$| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

gdzie $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$ jak powyżej, a $N$ to liczba stanów bazowych w twoim układzie kwantowym. Zauważ, że ponieważ teraz pracujemy z Qubitami, $m$ Qubitów daje $2^m$ stanów bazowych, więc $N=2^m$. Tutaj stany bazowe są zapisane jako pojedyncza liczba $|x\rangle$, gdzie $x$ przyjmuje wartości od $0$ do $N-1$, ale częściej możesz spotykać stany bazowe wyrażone jako $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$, ..., $|11...11\rangle$, gdzie każda cyfra binarna reprezentuje stan Qubit 0 do $m-1$, od prawej do lewej. Istnieje prosty sposób konwersji tych stanów binarnych na pojedynczą liczbę: wystarczy potraktować je jak liczby dwójkowe! Tak więc $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$ i tak dalej, aż do $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$.

Budowanie intuicji dla stanów bazy Fouriera

Omówiliśmy już, czym są stany bazy obliczeniowej i jak są uporządkowane: to zbiór stanów, w których każdy Qubit jest w stanie $0$ lub $1$, a my porządkujemy je od stanu, w którym wszystkie Qubity mają wartość $0$, $|00...00\rangle$, do stanu, w którym wszystkie mają wartość $1$, $|11...11\rangle$.

Ale jak możemy rozumieć stany bazy Fouriera? Wszystkie stany bazy Fouriera są równymi superpozycjami wszystkich stanów bazy obliczeniowej, ale każdy stan różni się od pozostałych periodycznością fazy składowych. Aby lepiej to zrozumieć, przyjrzyjmy się czterem stanom bazy Fouriera układu dwukubitowego. Najniższy stan Fouriera to taki, którego faza w ogóle się nie zmienia:

$|\phi_0\rangle = \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle)$

Możemy zwizualizować ten stan, wykreślając zespoloną amplitudę każdego z wyrazów. Czerwona linia ułatwia śledzenie tego, jak faza tej amplitudy obraca się wokół zespolonej płaszczyzny jako funkcja stanu bazy obliczeniowej. Dla $|\phi_0\rangle$ faza pozostaje stała:

Następny stan bazy Fouriera to ten, którego fazy składowych obracają się od $0$ do $2\pi$ dokładnie raz:

$|\phi_1\rangle = \frac{1}{2} (|00\rangle + e^{i\pi/2}|01\rangle + e^{i\pi}|10\rangle + e^{3i\pi/2}|11\rangle) = \frac{1}{2}(|00\rangle + i|01\rangle - |10\rangle - i|11\rangle)$

To obrót możemy zobaczyć na wykresie zespolonej amplitudy w funkcji stanu bazy obliczeniowej:

Każdy stan ma fazę o $2\pi/4$ radianów wyższą niż stan poprzedni, gdy są uporządkowane w standardowy sposób, ponieważ w tym przykładzie mamy cztery stany bazowe ($N=4$). Następny stan bazowy obraca się od 0 do $2\pi$ dwa razy:

$|\phi_2\rangle = \frac{1}{2} (|00\rangle + e^{i\pi}|01\rangle + e^{2i\pi}|10\rangle + e^{3i\pi}|11\rangle) = \frac{1}{2} (|00\rangle - |01\rangle + |10\rangle - |11\rangle)$

Wreszcie najwyższa składowa Fouriera to ta o najszybciej zmieniającej się fazie. W naszym przykładzie z dwoma Qubitami to ta, której fazy obracają się od 0 do $2\pi$ trzy razy:

$|\phi_3\rangle = \frac{1}{2} (|00\rangle + e^{3i\pi/2}|01\rangle + e^{6i\pi/2}|10\rangle + e^{9i\pi/2}|11\rangle) = \frac{1}{2} (|00\rangle - i|01\rangle - |10\rangle + i|11\rangle)$

Ogólnie, dla stanu $m$-kubitowego, będzie $2^m$ stanów bazy Fouriera, których częstotliwość zmian fazy waha się od stałej dla $|\phi_0\rangle$, do szybko zmieniającej się dla $|\phi_{2^m-1}\rangle$, wykonując $2^m-1$ obrotów wokół $2\pi$ w superpozycji stanów. Kiedy więc wykonujemy QFT stanu kwantowego, robimy zasadniczo to samo co w analizie przebiegu muzycznego we Wprowadzeniu. Wyznaczamy składowe częstotliwości Fouriera, które przyczyniają się do tworzenia interesującego nas stanu kwantowego.

Wypróbuj kilka przykładowych QFT

Spróbujmy dalej budować intuicję dotyczącą kwantowej transformaty Fouriera, tworząc stan w bazie obliczeniowej, a następnie obserwując, co się dzieje po zastosowaniu QFT. Na razie będziemy traktować QFT jako czarną skrzynkę, którą stosujemy przy użyciu QFTGate z biblioteki obwodów Qiskit. Później zajrzymy pod maskę, żeby zobaczyć, jak to działa w środku.

Zaczynamy od załadowania niezbędnych pakietów i wybrania urządzenia, na którym uruchomimy nasz Circuit:

import numpy as np
from qiskit import QuantumCircuit
from qiskit.visualization import plot_histogram
from qiskit.circuit.library import QFTGate

# Load the Qiskit Runtime service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

service = QiskitRuntimeService()

# Use the least busy backend
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_pinguino2")

print(backend.name)

ibm_pinguino2

Jeśli nie masz dostępnego czasu na swoim koncie lub z jakiegokolwiek powodu chcesz skorzystać z symulatora, możesz uruchomić poniższą komórkę, aby skonfigurować symulator naśladujący wybrane przez nas urządzenie kwantowe:

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# Alternatively, load a fake backend with generic properties and define a simulator.
from qiskit.providers.fake_provider import GenericBackendV2

backend_gen = GenericBackendV2(num_qubits=18)
sampler_gen = BackendSamplerV2(backend=backend_gen)

Pojedynczy stan bazy obliczeniowej

Najpierw spróbujmy przetransformować pojedynczy stan bazy obliczeniowej. Zaczniemy od utworzenia losowego stanu obliczeniowego:

# Step 1: Map

qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# flip state of random qubits to put in a random single computational basis state
for i in range(1, qubits):
    if np.random.randint(0, 2):
        qc.x(i)

# make a copy of the above circuit. (to be used when we apply the QFT in next part)
qc_qft = qc.copy()

qc.measure_all()
qc.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

Teraz przetransformujmy ten stan za pomocą QFTGate:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_qft)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

Jak widać, mierzony rozkład populacji każdego stanu jest mniej więcej równy, z uwzględnieniem pewnych szumów eksperymentalnych i statystycznych. A zatem, jeśli zastosujesz QFT do pojedynczego stanu bazy obliczeniowej, wynikiem jest równa superpozycja wszystkich stanów. Jeśli znasz transformaty Fouriera, pewnie cię to nie dziwi. Jedna z podstawowych zasad, która pomaga budować intuicyjny związek między funkcją a jej transformatą Fouriera, mówi, że szerokość funkcji jest odwrotnie proporcjonalna do szerokości jej transformaty Fouriera. Tak więc coś, co jest bardzo zlokalizowane w czasie — na przykład bardzo krótki impuls — będzie wymagało szerokiego zakresu częstotliwości, żeby ten impuls wygenerować. Taki sygnał będzie bardzo szeroki w przestrzeni Fouriera.

Ten fakt jest w rzeczywistości związany z kwantową niepewnością! Zasada nieoznaczoności Heisenberga jest zazwyczaj zapisywana jako $\Delta x \Delta p \ge \hbar / 2$. Jeśli więc niepewność w $x$ ($\Delta x$) jest mała, niepewność w pędzie ($\Delta p$) musi być duża i odwrotnie. Okazuje się, że przejście z bazy położenia $x$ do bazy pędu $p$ realizuje się właśnie przez transformatę Fouriera.

Uwaga: pamiętaj, że mierzymy populacje w każdym ze stanów bazowych, więc tracimy informacje o względnych fazach między poszczególnymi częściami superpozycji. Dlatego choć QFT dowolnego pojedynczego stanu bazy obliczeniowej daje taki sam równomierny rozkład populacji po wszystkich stanach bazowych, fazy niekoniecznie będą takie same.

Dwa stany bazy obliczeniowej

Teraz zobaczmy, co się dzieje, gdy przygotujemy superpozycję stanów bazy obliczeniowej. Jak myślisz, jak będzie wyglądać transformata Fouriera w tym przypadku?

Wybierzmy superpozycję:

$|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle) = \frac{1}{\sqrt{2}} (|000...0\rangle + |100...0\rangle)$

# Step 1: Map
qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# To make this state, we just need to apply a Hadamard to the last qubit

qc.h(qubits - 1)

qc_qft = qc.copy()

qc.measure_all()

qc.draw("mpl")

# First, let's go through steps 2-4 for the first circuit, qc

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Teraz przetransformujmy ten stan za pomocą QFTGate:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_qft)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Ten wynik może być nieco zaskakujący. Wygląda na to, że QFT stanu $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ jest superpozycją wszystkich parzystych stanów bazowych. Ale jeśli wrócimy do naszej wizualizacji każdego stanu bazowego $|\phi_y\rangle$ i tego, jak faza każdego składnika okrąża $2\pi$ $y$ razy, powód, dla którego otrzymujemy ten wynik, może stać się jasny.

Sprawdź swoje rozumienie

Przeczytaj poniższe pytania, zastanów się nad odpowiedzią, a następnie kliknij trójkąt, żeby ujawnić rozwiązanie.

Korzystając z powyższej wskazówki, wyjaśnij, dlaczego wynik, który otrzymaliśmy dla QFT stanu $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$, jest oczekiwany.

Odpowiedź:

Oryginalny stan ma względną fazę równą 0 (lub całkowitej wielokrotności $2\pi$) między dwiema częściami superpozycji. Wiemy więc, że ten stan ma składowe Fouriera, których fazy dopasowują się w ten sposób: te, które mają zerowe przesunięcie fazy między wyrazem |0000> a wyrazem |1000>. Każdy stan bazowy Fouriera $|\phi_y\rangle$ składa się z wyrazów, których faza narasta z prędkością $2\pi y/N$, co oznacza, że każdy wyraz w superpozycji, uszeregowany w zwykły sposób, ma fazę o $2\pi y/N$ większą niż poprzedni. Zatem w połowie drogi, przy $N/2$, chcemy, żeby faza $2\pi y/N \cdot N/2$ była całkowitą wielokrotnością $2\pi$. Dzieje się to wtedy, gdy $y$ jest parzyste.

Jaka superpozycja stanów obliczeniowych odpowiadałaby QFT z pikami na każdej nieparzystej liczbie binarnej?

Odpowiedź:

Gdybyś zastosował QFT do stanu $\psi = |0\rangle - |N/2\rangle$, zobaczyłbyś piki na każdym nieparzystym stanie binarnym.

Rozłóż algorytm QFT

Teraz, gdy lepiej rozumiemy związek między stanami kubitów w bazie obliczeniowej a bazą Fouriera, przyjrzyjmy się bliżej samemu algorytmowi QFT. Innymi słowy, jakie Gate'y faktycznie implementujemy na komputerze kwantowym, aby uzyskać tę transformację?

Zacznijmy od małego przykładu — jednego Qubitu. Oznacza to, że będziemy mieć dwa stany bazowe. QFT$_2$ przekształca stany bazy obliczeniowej $|0\rangle$ i $|1\rangle$ w stany bazy Fouriera $\phi_0$ i $\phi_1$:

$|\phi_0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$|\phi_1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

Sprawdź swoje rozumienie

Przeczytaj poniższe pytanie(-a), zastanów się nad odpowiedzią, a następnie kliknij trójkąt, aby zobaczyć rozwiązanie.

Korzystając z równania QFT z poprzedniej sekcji, zweryfikuj powyższe dwa stany bazy Fouriera.

Odpowiedź:

Ogólny wzór QFT to:

$| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

Dla jednego Qubitu ($n=1$), $N=2^n=2$ i $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$. Mamy więc:

$| \phi_0 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {0 \times 0}{2}}|0\rangle + e^{2\pi i \frac {0 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$| \phi_1 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {1 \times 0}{2}}|0\rangle + e^{2\pi i \frac {1 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

Przyjrzyj się tym dwóm równaniom. Być może znasz już bramkę kwantową, którą można wykorzystać do implementacji tej transformacji. Istnieje mianowicie Gate, który przekształca stany bazy obliczeniowej $|0\rangle$ i $|1\rangle$ w odpowiednie stany bazy Fouriera $|\phi_0\rangle$ i $|\phi_1\rangle$. To bramka Hadamarda! Staje się to jeszcze bardziej widoczne, gdy wprowadzimy macierzową reprezentację operacji QFT$_N$:

$\text{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} \omega_N^{xy} \vert x \rangle \langle y \vert$

Jeśli nie jesteś zaznajomiony(-a) z tym zapisem wyrażania operatora kwantowego, nie martw się! Jest to sposób reprezentacji macierzy $N \times N$, gdzie $x$ i $y$ indeksują kolumny i wiersze macierzy od $0$ do $N-1$, a $\omega_N^{xy}$ to wartość danego wpisu. Na przykład wpis w kolumnie 0. i wierszu 2. wynosiłby po prostu $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

W tej reprezentacji każdy stan bazy obliczeniowej odpowiada jednemu z wektorów bazowych:

$$\begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, |1\rangle = \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{pmatrix}, |N-1\rangle = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{pmatrix}.$$

Jeśli chcesz dowiedzieć się więcej o tej reprezentacji, zajrzyj do lekcji Johna Watrousa o układach złożonych w kursie Basics of quantum information.

Spróbujmy zbudować macierz dla QFT$_4$. Korzystając z powyższego wzoru, otrzymujemy:

$\text{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{pmatrix}$

Aby zaimplementować tę macierz na komputerze kwantowym, musimy ustalić, jaką kombinację Gate'ów zastosowanych do jakich Qubitów da nam transformację unitarną odpowiadającą powyższej macierzy. Wiemy już, że jedną z potrzebnych bramek jest Hadamard. Kolejną potrzebną bramką jest kontrolowana bramka fazowa, która stosuje względną fazę $\alpha$ do stanu Qubitu docelowego, pod warunkiem że Qubit kontrolny jest w stanie $|1\rangle$. W postaci macierzowej wygląda to tak:

$\text{CP}_\alpha = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^{i\alpha} \\ \end{pmatrix}$

Ponieważ zmieniany jest tylko stan $|11\rangle$, nie ma znaczenia, który Qubit jest „kontrolnym", a który „docelowym". Wynik będzie taki sam w obu przypadkach.

Na koniec będziemy potrzebować również bramek SWAP. Bramka SWAP zamienia stany dwóch Qubitów. Wygląda następująco:

$\text{SWAP}_\alpha = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}$

Procedura budowania Circuit QFT$_{2^m}$ na $m$ Qubitach jest iteracyjna — najpierw stosuje się QFT$_{2^{m-1}}$ do Qubitów od $1$ do $m-1$, a następnie dodaje się pewne Gate'y między Qubitem $0$ a pozostałymi $m-1$ Qubitami. Ale żeby zastosować QFT$_{2^{m-1}}$, trzeba najpierw zastosować QFT$_{2^{m-2}}$ do Qubitów od 2 do $m-1$, a następnie dodać Gate'y między Qubitem 1 a pozostałymi Qubitami od $2$ do $m-1$. Przypomina to rosyjskie matrioszki: każda lalka zwiększa wymiar Circuit QFT dwukrotnie, a najmniejsza lalka w samym centrum to QFT$_2$, czyli bramka Hadamarda.

Aby włożyć lalkę do następnej, nieco większej, czyli zwiększyć wymiar QFT dwukrotnie, zawsze wykonujesz tę samą procedurę:

1. Najpierw zastosuj QFT$_{2^{m-1}}$ do $m-1$ Qubitów na dole. To jest twoja „mniejsza lalka" z zestawu rosyjskich matrioszek, którą zaraz umieścisz w następnej, większej.
2. Użyj kolejnego Qubitu powyżej jako kontrolnego i zastosuj kontrolowane bramki fazowe do każdego z dolnych $m-1$ Qubitów, z fazami odpowiadającymi stanom standardowej bazy każdego z pozostałych $m-1$ Qubitów.
3. Wykonaj operację Hadamarda na tym samym górnym Qubicie, który był używany jako kontrolny w bramkach fazowych.
4. Użyj bramek SWAP, aby przestawić kolejność Qubitów tak, żeby najmniej znaczący (górny) bit stał się najbardziej znaczącym (dolnym) bitem, a wszystkie pozostałe przesunęły się o jeden w górę.

Używaliśmy już funkcji QFTGate z biblioteki Circuit Qiskit, ale teraz zajrzyjmy do środka niektórych z tych Gate'ów QFT, aby zweryfikować powyższą procedurę. Możemy to zrobić za pomocą decompose().

qc = QuantumCircuit(1)
qc.compose(QFTGate(1), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(2)
qc.compose(QFTGate(2), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(3)
qc.compose(QFTGate(3), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(4)
qc.compose(QFTGate(4), inplace=True)
qc.decompose().draw("mpl")

Mam nadzieję, że na podstawie pierwszych czterech QFT zaczynasz dostrzegać, jak każda z nich jest zagnieżdżona wewnątrz kolejnej, większej. Być może zauważyłeś(-aś), że niektóre z bramek fazowych nie są dokładnie takie, jak opisano w procedurze powyżej, a operacje SWAP nie pojawiają się po każdej podrutynie, lecz tylko na samym końcu pełnego QFT. Pozwala to zaoszczędzić zbędne Gate'y, które wydłużałyby działanie Circuit i zwiększały podatność na błędy. Zamiast implementować SWAP po każdej zagnieżdżonej lalce, Circuit śledzi, gdzie powinien znajdować się każdy stan Qubitu, i odpowiednio dostosowuje Qubity, do których stosuje bramki fazowe. Następnie końcowy zestaw operacji SWAP na końcu układa wszystko na właściwym miejscu.

Zastosowanie QFT: estymacja fazy

Zobaczmy, jak QFT może być wykorzystana do rozwiązania użytecznego problemu w informatyce kwantowej. Obliczenie odwrotnej kwantowej transformaty Fouriera jest niezbędnym krokiem w algorytmie zwanym kwantową estymacją fazy (QPE), który sam w sobie jest podprogramem w wielu innych algorytmach — w tym w „klejnocie koronnym" algorytmów kwantowych, algorytmie faktoryzacji Shora.

Celem QPE jest estymacja wartości własnych operatora unitarnego. Operatory unitarne są wszechobecne w informatyce kwantowej i często wyznaczenie wartości własnych odpowiadających im wektorów własnych stanowi niezbędny krok w większym algorytmie. W zależności od problemu wartość własna może reprezentować energię hamiltonianu w zadaniu symulacyjnym, pomagać w znajdowaniu czynników pierwszych liczby w algorytmie Shora lub zawierać inne kluczowe informacje. QPE jest jednym z najważniejszych i najszerzej stosowanych podprogramów w informatyce kwantowej.

Co to ma wspólnego z kwantową transformatą Fouriera? Jak pewnie pamiętasz, każda wartość własna $\lambda$ operatora unitarnego ma moduł $|\lambda| = 1$. Możemy więc zapisać każdą wartość własną jako liczbę zespoloną o module jeden:

$\lambda = e^{2\pi i \theta}$

gdzie $\theta$ jest liczbą rzeczywistą z przedziału od 0 do 1. Jeśli chcesz dowiedzieć się więcej o macierzach unitarnych, zapoznaj się z lekcją Johna Watrusa na ten temat w kursie Podstawy informacji kwantowej.

Zauważ, że $\lambda$ jest periodyczna względem $\theta$. Już to może sugerować, że QFT może być zaangażowana, ponieważ widzieliśmy, jak użyteczne są QFT do analizy funkcji periodycznych. Poniżej przejdziemy przez algorytm i zobaczymy dokładnie, w jaki sposób QFT wchodzi do gry.

Jak działa QPE

Zaczniemy od najprostszego algorytmu QPE, który w przybliżeniu estymuje fazę z dokładnością do jednej cyfry binarnej. Innymi słowy, algorytm ten potrafi odróżnić $\theta = 0$ od $\theta = 1/2$, ale nie robi tego lepiej. Oto schemat obwodu:

Qubity są przygotowane w stanie $|\pi_0\rangle = |\psi\rangle|0\rangle$, gdzie Qubit $0$ jest w stanie $|0\rangle$, a pozostałe Qubity są w stanie $|\psi\rangle$, który jest stanem własnym $U$. Po pierwszej bramce Hadamarda stan Qubitów przyjmuje postać:

$|\pi_1\rangle = \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + |1\rangle)$

Następna bramka to bramka „kontrolowana-$U$". Stosuje ona operację unitarną $U$ do dolnych Qubitów w stanie $|\psi\rangle$, jeśli Qubit 0 jest w stanie $|1\rangle$, lecz nie robi nic z $|\psi\rangle$, gdy Qubit 0 jest w stanie $|0\rangle$. Przekształca to Qubity do stanu:

$|\pi_2\rangle = \frac{1}{\sqrt{2}}( |\psi\rangle|0\rangle + e^{2\pi i \theta}|\psi\rangle|1\rangle)$ $= \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + e^{2\pi i \theta}|1\rangle)$

Stało się coś dziwnego: bramka kontrolowana-$U$ używa Qubitu $0$ jedynie jako Qubitu kontrolnego, więc można by sądzić, że ta bramka w ogóle nie zmienia stanu Qubitu 0. A jednak zmienia! Mimo że operacja była zastosowana do dolnych Qubitów, ogólny efekt bramki polega na zmianie fazy Qubitu $0$. Zjawisko to znane jest jako „mechanizm przeniesienia fazy" (ang. phase kickback) i jest stosowane w wielu algorytmach kwantowych, m.in. w algorytmach Deutscha-Jozsy i Grovera. Jeśli chcesz dowiedzieć się więcej o mechanizmie przeniesienia fazy, zapoznaj się z lekcją Johna Watrusa dotyczącą kwantowych algorytmów zapytań w kursie Podstawy algorytmów kwantowych.

Po przeniesieniu fazy stosujemy jeszcze jedną bramkę Hadamarda do Qubitu $0$, co daje stan:

$|\pi_3\rangle = |\psi\rangle ( \frac{1+e^{2\pi i \theta}}{2} |0\rangle + \frac{1 - e^{2\pi i \theta}}{2}|1\rangle) = |\psi\rangle ( \cos(\pi\theta) |0\rangle - i \sin(\pi\theta)|1\rangle)$

Tak więc gdy na końcu mierzymy Qubit $0$, zmierzymy $|0\rangle$ z prawdopodobieństwem 100%, jeśli $\theta = 0$, i zmierzymy $|1\rangle$ z prawdopodobieństwem 100%, jeśli $\theta = \frac{1}{2}$ (i jeśli nasz komputer kwantowy jest idealny, bez szumów). Jeśli $\theta$ ma inną wartość, pomiar końcowy jest jedynie probabilistyczny i dostarcza ograniczonej informacji.

QPE z większą precyzją: więcej Qubitów

Możemy rozszerzyć tę prostą koncepcję do bardziej skomplikowanego algorytmu o dowolnej precyzji. Jeśli zamiast tylko jednego Qubitu $0$ do pomiaru fazy użyjemy $m$ Qubitów od $0$ do $m-1$, będziemy w stanie estymować fazę z dokładnością do $m$ bitów. Zobaczmy, jak to działa:

Ten bardziej precyzyjny obwód QPE rozpoczyna się tak samo jak wersja jednobitowa: bramki Hadamarda są stosowane do pierwszych $m$ Qubitów, a pozostałe Qubity są przygotowane w stanie $|\psi\rangle$, tworząc stan:

$|\pi_1\rangle = \frac{1}{2^{m/2}}|\psi\rangle(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)...(|0\rangle+|1\rangle)$

Teraz stosowane są bramki kontrolowane-unitarne. Qubit $0$ jest kontrolą dla tej samej operacji unitarnej $U$ co poprzednio. Ale teraz Qubit $1$ jest kontrolą dla operacji unitarnej $U^2$, czyli po prostu $U$ zastosowanej dwukrotnie. Wartość własna $U^2$ wynosi zatem $e^{2*2\pi i \theta}$. Ogólnie, każdy Qubit $k$ od 0 do $m-1$ będzie kontrolą dla operacji unitarnej $U^{2^k}$. Oznacza to, że każdy z tych Qubitów dozna przeniesienia fazy równego $e^{2^k*2\pi i \theta}$. Daje to stan:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} (|0\rangle+e^{2^{m-1}2\pi i \theta}|1\rangle)(|0\rangle+e^{2^{m-2}2\pi i \theta}|1\rangle)...(|0\rangle+e^{2\pi i \theta}|1\rangle)$

Można to przepisać jako sumę po stanach bazy obliczeniowej:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} \sum_{k=0}^{2^{m}-1} e^{2\pi i k \theta} |k\rangle$

Czy ta suma wygląda znajomo? To jest QFT! Przypomnij sobie równanie kwantowej transformaty Fouriera:

$\text{QFT}_{2^m}| y \rangle = \frac{1}{\sqrt{2^m}}\sum_{x=0}^{2^m-1}\omega_{2^m}^{y x} \vert x \rangle$

Tak więc, jeśli faza $\theta = y/2^m$ dla pewnej liczby całkowitej $y$ z przedziału od $0$ do $2^m-1$, to zastosowanie odwrotnej QFT do tego stanu da stan:

$|\pi_3\rangle = |\psi\rangle \otimes |y\rangle$

a z $|y\rangle$ możemy wyznaczyć $\theta$.

Jeśli jednak $\theta/2^m$ nie jest całkowitą wielokrotnością, zastosowanie odwrotnej QFT jedynie przybliży $\theta$. Jakość tego przybliżenia będzie probabilistyczna, co oznacza, że nie zawsze otrzymamy najlepsze przybliżenie, ale będzie ono całkiem bliskie prawdy — im więcej Qubitów $m$ użyjemy, tym lepsze przybliżenie uzyskamy. Aby dowiedzieć się, jak skwantyfikować to przybliżenie $\theta$, zapoznaj się z lekcją Johna Watrusa dotyczącą estymacji fazy i faktoryzacji w kursie Podstawy algorytmów kwantowych.

Podsumowanie

Ten moduł przedstawił omówienie tego, czym jest QFT, jak jest implementowana na komputerze kwantowym i jak użyteczna może być przy rozwiązywaniu problemów. Pokazaliśmy jej użyteczność na przykładzie kwantowej estymacji fazy, gdzie służy do badania wartości własnych macierzy unitarnej.

Kluczowe pojęcia

• Kwantowa transformata Fouriera jest kwantowym odpowiednikiem dyskretnej transformaty Fouriera.
• QFT jest przykładem zmiany bazy.
• Procedura kwantowej estymacji fazy opiera się na mechanizmie przeniesienia fazy wynikającym z operacji kontrolowanych-unitarnych oraz na odwrotnej QFT.
• QFT i QPE są powszechnie stosowanymi podprogramami w licznych algorytmach kwantowych.

Pytania

Prawda/Fałsz

1. P/F Kwantowa transformata Fouriera jest kwantowym odpowiednikiem klasycznej dyskretnej transformaty Fouriera (DFT).
2. P/F QFT można zaimplementować używając wyłącznie bramek Hadamarda i CNOT.
3. P/F QFT jest kluczowym składnikiem algorytmu Shora.
4. P/F Wynikiem kwantowej estymacji fazy jest stan kwantowy reprezentujący wektor własny operatora.
5. P/F QPE wymaga użycia odwrotnej kwantowej transformaty Fouriera (QFT$^\dag$).
6. P/F W QPE, jeśli faza $\phi$ jest dokładnie reprezentowalna za pomocą $n$ bitów, algorytm daje poprawny wynik z prawdopodobieństwem 1.

Krótkie odpowiedzi

1. Ile Qubitów jest potrzebnych do wykonania QFT na układzie z $2^n$ punktami danych?
2. Czy QFT można zastosować do stanu, który nie jest stanem bazy obliczeniowej? Jeśli tak, co się wtedy dzieje?
3. Jak liczba Qubitów kontrolnych użytych w QPE wpływa na rozdzielczość wynikowej estymacji fazy?

Zadania

1. Użyj mnożenia macierzowego, aby zweryfikować, że kroki algorytmu QFT rzeczywiście dają macierz $\text{QFT}_4$:

$$\text{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{pmatrix}$$

(Nie musisz robić tego ręcznie!)

Zadania dodatkowe

1. Skonstruuj cztero-Qubitowy stan będący równą superpozycją wszystkich nieparzystych baz obliczeniowych: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. Następnie wykonaj QFT na tym stanie. Jaki jest wynikowy stan? Wyjaśnij, dlaczego twój wynik ma sens, używając wiedzy o transformatach Fouriera.