Kvantová Fourierova transformace

Pro tento modul Qiskit in Classrooms musí mít studenti funkční prostředí Python s nainstalovanými následujícími balíčky:

• qiskit v2.1.0 nebo novější
• qiskit-ibm-runtime v0.40.1 nebo novější
• qiskit-aer v0.17.0 nebo novější
• qiskit.visualization
• numpy
• pylatexenc

Jak nastavit a nainstalovat výše uvedené balíčky, najdeš v průvodci Instalace Qiskit. Aby bylo možné spouštět úlohy na skutečných kvantových počítačích, studenti si budou muset vytvořit účet u IBM Quantum® podle kroků v průvodci Nastavení účtu IBM Cloud.

Tento modul byl otestován a využil 13 sekund času QPU. Jedná se o odhad v dobré víře; tvoje skutečné využití se může lišit.

# 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'

Úvod

Fourierova transformace je všudypřítomný nástroj s aplikacemi v matematice, fyzice, zpracování signálů, kompresi dat a nespočtu dalších oblastí. Kvantová verze Fourierovy transformace, příhodně pojmenovaná kvantová Fourierova transformace, tvoří základ pro některé z nejdůležitějších kvantových algoritmů.

Dnes, po připomenutí klasické Fourierovy transformace, si povíme, jak kvantovou Fourierovu transformaci implementujeme na kvantovém počítači. Potom si probereme jedno z využití kvantové Fourierovy transformace v algoritmu zvaném algoritmus odhadu fáze. Kvantový odhad fáze je podprogram v Shorově slavném algoritmu pro faktorizaci, který se někdy označuje jako „korunní klenot" kvantového výpočtu. Tento modul směřuje k dalšímu modulu zcela věnovanému Shorovu algoritmu, ale je také zamýšlen jako samostatný celek. Kvantová Fourierova transformace je fascinující a užitečný algoritmus sám o sobě!

Klasická Fourierova transformace

Než se pustíme do kvantové Fourierovy transformace, připomeňme si nejprve klasickou verzi. Fourierova transformace je metoda přechodu z jedné tzv. „báze" do jiné. Dvě báze si můžeš představit jako různé perspektivy téhož problému — obě jsou platnými způsoby vyjádření funkce, ale jedna nebo druhá může být přehlednější v závislosti na konkrétním problému. Příklady dvojic bází propojených Fourierovou transformací jsou poloha a hybnost, a čas a frekvence.

Podívejme se na příklad toho, jak by nám Fourierova transformace mohla pomoci zjistit, jakou notu hraje nástroj, na základě jeho zvukového průběhu. Typicky vidíme průběhy vyjádřené v časové bázi — tedy amplituda vlny je vyjádřena jako funkce času.

Tento průběh můžeme Fourierovou transformací přejít z časové báze do frekvenční báze:

Ve frekvenční bázi jasně vidíme výrazný vrchol přibližně na 260 Hz. To je střední C!

Možná by ses i bez Fourierovy transformace dokázal/a dopátrat, že se hraje střední C, ale co kdybychom hráli více not najednou? Průběh by se pak v časové bázi zkomplikoval:

Ale frekvenční spektrum jasně identifikuje tři vrcholy:

Byl to akord C dur, zahrnující noty C, E a G.

Tento druh Fourierovy analýzy nám pomáhá extrahovat frekvenční složky jakéhokoliv složitého signálu.

Diskrétní Fourierova transformace

Fourierova transformace je užitečná pro celou řadu aplikací zpracování signálů. Ve většině těchto reálných aplikací (včetně výše uvedeného hudebního příkladu) ale chceme transformovat diskrétní sadu $N$ datových bodů — ne spojitou funkci. V tomto případě používáme diskrétní Fourierovu transformaci. Diskrétní Fourierova transformace (DFT) pracuje s vektorem $(x_0, ..., x_{N-1})$ a zobrazí ho na vektor $(y_0, ..., y_{N-1})$ podle vzorce:

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

kde definujeme $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$. (Poznamenejme, že existují i jiné konvence se záporným znaménkem v exponentu, takže buď opatrný/á, když DFT uvidíš jinde.) Připomeňme, že $e^{2\pi i \frac{jk}{N}}$ je periodická funkce s periodou $\frac{N}{k}$. Fourierova transformace tak v podstatě rozkládá (diskrétní) funkci $\{x_{j}\}$ na lineární kombinaci jejích složkových periodických funkcí, z nichž každá má periodu $\frac{N}{k}$.

Kvantová Fourierova transformace

Viděli jsme tedy, jak se Fourierova transformace používá k vyjádření funkce jako lineární kombinace nové sady tzv. „bázových funkcí". Transformace báze se provádí i na stavech qubitů. Například stav jednoho qubitu $|\psi\rangle$ lze vyjádřit ve výpočetní bázi jako $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$ s bázovými stavy $|0\rangle$ a $|1\rangle$, nebo v bázi $X$ jako $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ s bázovými stavy $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ a $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$. Obě vyjádření jsou stejně platná, ale jedno může být přirozenější než druhé v závislosti na typu problému, který chceš řešit.

Stavy qubitů lze také vyjádřit ve Fourierově bázi, kde je stav vyjádřen jako lineární kombinace stavů Fourierovy báze $|\phi_y\rangle$, namísto obvyklých stavů výpočetní báze $|x\rangle$. K tomu je potřeba aplikovat kvantovou Fourierovu transformaci (QFT):

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

kde $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$ jako výše a $N$ je počet bázových stavů v tvém kvantovém systému. Protože pracujeme s qubity, $m$ qubitů nám dá $2^m$ bázových stavů, tedy $N=2^m$. Bázové stavy jsou zde zapsány jako jediné číslo $|x\rangle$, kde $x$ nabývá hodnot od $0$ do $N-1$, ale běžněji se setkáme s bázovými stavy vyjádřenými jako $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$, ..., $|11...11\rangle$, kde každá binární číslice reprezentuje stav qubitu 0 až $m-1$ zprava doleva. Existuje snadný způsob, jak tyto binární stavy převést na jediné číslo: stačí s nimi zacházet jako s binárními čísly! Tedy $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$ a tak dále až po $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$.

Vybuduj intuici pro stavy Fourierovy báze

Právě jsme si tedy připomněli, jaké jsou stavy výpočetní báze a jak jsou řazeny: jsou to stavy, kde každý qubit je buď ve stavu $0$, nebo $1$, a řadíme je od stavu, kde jsou všechny qubity $0$, $|00...00\rangle$, po stav, kde jsou všechny $1$, $|11...11\rangle$.

Jak ale dává smysl Fourierova báze stavů? Všechny stavy Fourierovy báze jsou rovnými superpozicemi všech stavů výpočetní báze, ale jednotlivé stavy se od sebe liší periodicitou fáze jejich složek. Abychom to pochopili konkrétněji, podívejme se na čtyři stavy Fourierovy báze dvouqubitového systému. Nejnižší stav Fourierovy báze je ten, jehož fáze se vůbec nemění:

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

Tento stav si můžeme vizualizovat vynesením komplexní amplitudy každého členu do grafu. Červená čára slouží jako vodítko a ukazuje, jak se fáze této amplitudy otáčí v komplexní rovině v závislosti na stavu výpočetní báze. Pro $|\phi_0\rangle$ zůstává fáze konstantní:

Další stav Fourierovy báze je ten, jehož fáze složek se otočí od $0$ do $2\pi$ právě jednou:

$|\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)$

A toto otočení vidíme v grafu komplexní amplitudy v závislosti na stavu výpočetní báze:

Každý stav má tedy fázi o $2\pi/4$ radiánů vyšší než předchozí stav (při řazení standardním způsobem), protože v tomto příkladu máme čtyři bázové stavy ($N=4$). Další bázový stav se otočí od 0 do $2\pi$ dvakrát:

$|\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)$

Nakonec nejvyšší Fourierova složka je ta s nejrychleji se měnící fází. Pro náš příklad se dvěma qubity je to ta, jejíž fáze se otočí od 0 do $2\pi$ třikrát:

$|\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)$

Obecně platí, že pro stav $m$ qubitů existuje $2^m$ stavů Fourierovy báze, jejichž frekvence změny fáze sahá od konstantní u $|\phi_0\rangle$ po rychle proměnnou u $|\phi_{2^m-1}\rangle$, přičemž superpozice stavů dokončí $2^m-1$ oběhů kolem $2\pi$. Když tedy aplikujeme QFT na kvantový stav, provádíme v podstatě totéž, co jsme dělali pro hudební průběh v úvodu. Určujeme Fourierovy frekvenční složky, které přispívají k vytvoření daného kvantového stavu.

Vyzkoušej si příklady QFT

Zkusme dále budovat intuici pro kvantovou Fourierovu transformaci tím, že vytvoříme stav ve výpočetní bázi a pak uvidíme, co se stane, když na něj aplikujeme QFT. Prozatím budeme s QFT zacházet jako s černou skříňkou, kterou aplikujeme pomocí QFTGate z knihovny obvodů Qiskit. Později se podíváme pod pokličku a zjistíme, jak je implementována.

Začneme načtením potřebných balíčků a výběrem zařízení, na kterém spustíme obvod:

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

Pokud nemáš na svém účtu dostupný čas nebo chceš z jakéhokoli důvodu použít simulátor, můžeš spustit níže uvedenou buňku a nastavit simulátor napodobující kvantové zařízení, které jsme vybrali výše:

# 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)

Jediný stav výpočetní báze

Nejprve zkusme transformovat jediný stav výpočetní báze. Začneme vytvořením náhodného výpočetního stavu:

# 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)

Nyní Fourierovsky transformujme tento stav 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 vidíš, měříme populace každého stavu jako více méně stejné, s určitým experimentálním a statistickým šumem. Pokud tedy aplikuješ QFT na jediný stav výpočetní báze, výsledkem je rovná superpozice všech stavů. Pokud znáš Fourierovy transformace, pravděpodobně tě to nepřekvapuje. Jeden základní princip, který nám pomáhá budovat intuitivní spojení mezi funkcí a její Fourierovou transformací, je, že šířka funkce je nepřímo úměrná šířce její Fourierovy transformace. Tedy něco velmi lokalizovaného v čase, například velmi krátký puls, bude vyžadovat široký rozsah frekvencí k jeho vytvoření. Takový signál bude ve Fourierově prostoru velmi široký.

Tato skutečnost přímo souvisí s kvantovou neurčitostí! Heisenbergův princip neurčitosti se typicky formuluje jako $\Delta x \Delta p \ge \hbar / 2$. Pokud je tedy neurčitost v $x$ ($\Delta x$) malá, neurčitost hybnosti ($\Delta p$) musí být velká, a naopak. Ukázalo se, že přechod z poziční báze $x$ do hybnostní báze $p$ je realizován Fourierovou transformací.

Poznámka: Pamatuj, že měříme populace v každém ze stavů báze, takže ztrácíme informace o relativních fázích mezi různými částmi superpozice. Takže ačkoli QFT libovolného jediného stavu výpočetní báze dá stejný rovnoměrný rozptyl populace přes všechny bázové stavy, fáze nemusí být nutně stejné.

Dva stavy výpočetní báze

Podívejme se nyní, co se stane, když připravíme superpozici stavů výpočetní báze. Jak si myslíš, že bude vypadat Fourierova transformace v tomto případě?

Zvolme superpozici:

$|\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)

Nyní Fourierovsky transformujme tento stav 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)

Tento výsledek možná trochu překvapuje. Zdá se, že QFT stavu $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ je superpozicí všech sudých bázových stavů. Pokud se ale vrátíme k naší vizualizaci každého bázového stavu $|\phi_y\rangle$ a toho, jak se fáze každé složky otáčí $y$-krát kolem $2\pi$, může se důvod, proč dostáváme tento výsledek, stát zřejmým.

Ověř si porozumění

Přečti si níže uvedené otázky, promysli svou odpověď a poté klikni na trojúhelník pro zobrazení řešení.

S použitím výše uvedené nápovědy vysvětli, proč je výsledek, který jsme získali pro QFT stavu $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$, očekávaný.

Odpověď:

Původní stav má relativní fázi 0 (nebo celočíselný násobek $2\pi$) mezi oběma částmi superpozice. Víme tedy, že tento stav má Fourierovy složky, jejichž fáze se shodují tímto způsobem: ty, které mají nulový posun fáze mezi členem |0000> a členem |1000>. Každý stav Fourierovy báze $|\phi_y\rangle$ je složen z členů, jejichž fáze se akumuluje rychlostí $2\pi y/N$, což znamená, že při standardním řazení má každý člen superpozice fázi o $2\pi y/N$ větší než předchozí člen. Tedy v polovičním bodě $N/2$ chceme, aby fáze $2\pi y/N * N/2$ byla celočíselným násobkem $2\pi$. To nastane, když je $y$ sudé.

Jaká superpozice výpočetních stavů by odpovídala QFT s vrcholy na každém lichém binárním čísle?

Odpověď:

Kdybys/kdybys aplikoval/a QFT na stav $\psi = |0\rangle - |N/2\rangle$, uviděl/a bys vrcholy na každém lichém binárně číslovaném stavu.

Rozebrání algoritmu QFT

Teď, když jsme získali lepší intuici pro vztah mezi stavy qubitů v komputační bázi a Fourierově bázi, pojďme se ponořit do samotného algoritmu QFT. Jinými slovy, jaké hradla skutečně implementujeme na kvantovém počítači, abychom dosáhli tohoto transformace?

Začněme v malém — s jediným qubitem. To znamená, že budeme mít dva bázové stavy. QFT$_2$ transformuje stavy komputační báze $|0\rangle$ a $|1\rangle$ na stavy Fourierovy báze $\phi_0$ a $\phi_1$:

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

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

Ověř si porozumění

Přečti si otázku (otázky) níže, zamysli se nad odpovědí, pak klikni na trojúhelník pro zobrazení řešení.

Pomocí rovnice pro QFT z předchozí sekce ověř tyto dva stavy Fourierovy báze výše.

Odpověď:

Obecný vzorec QFT je:

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

Pro jeden qubit ($n=1$), $N=2^n=2$ a $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$. Takže máme

$| \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)$

Podívej se na tyto dvě rovnice. Možná už znáš kvantové hradlo, které lze použít k implementaci této transformace. To znamená, že existuje hradlo, které transformuje stavy komputační báze $|0\rangle$ a $|1\rangle$ na příslušné stavy Fourierovy báze $|\phi_0\rangle$ a $|\phi_1\rangle$. Je to Hadamardovo hradlo! To bude ještě jasnější, pokud zavedeme maticovou reprezentaci operace 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$

Pokud tento zápis pro vyjádření kvantového operátoru neznáš, to nevadí! Jde o způsob, jak reprezentovat matici $N \times N$, kde $x$ a $y$ indexují sloupce a řádky matice od $0$ do $N-1$ a $\omega_N^{xy}$ je hodnota daného prvku. Takže prvek v 0. sloupci a 2. řádku by byl například $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

V této reprezentaci je každý stav komputační báze přiřazen k jednomu ze základních vektorů:

$$\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}.$$

Pokud se chceš o této reprezentaci dozvědět více do hloubky, podívej se na lekci Johna Watrouse o vícenásobných systémech v kurzu Základy kvantové informace.

Zkusme sestavit matici pro QFT$_4$. Pomocí výše uvedeného vzorce zjistíme, že

\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\}

Abychom tuto matici implementovali na kvantovém počítači, budeme muset zjistit, která kombinace hradel aplikovaných na které qubity nám dá unitární transformaci odpovídající výše uvedené matici. Jedno z potřebných hradel už známe: Hadamardovo. Dalším potřebným hradlem je hradlo řízené fáze (controlled-phase), které aplikuje relativní fázi $\alpha$ na stav cílového qubitu, pokud je řídicí qubit ve stavu $|1\rangle$. V maticovém tvaru to vypadá takto:

\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\}

Protože se mění pouze stav $|11\rangle$, ve skutečnosti nezáleží na tom, který qubit je považován za „řídicí" a který za „cílový". Výsledek bude v obou případech stejný.

Nakonec budeme potřebovat také hradla SWAP. Hradlo SWAP prohodí stavy dvou qubitů. Vypadá takto:

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

Postup pro sestavení obvodu QFT$_{2^m}$ na $m$ qubitech je iterativní — nejprve aplikuješ QFT$_{2^{m-1}}$ na qubity $1$ až $m-1$, pak přidáš některá hradla mezi qubit $0$ a zbývající $m-1$ qubitů. Ale pro aplikaci QFT$_{2^{m-1}}$ musíš nejprve aplikovat QFT$_{2^{m-2}}$ na qubity 2 až $m-1$ a pak přidat hradla mezi qubit 1 a zbývající qubity $2$ až $m-1$. Je to jako ruská matrjoškakatalogu: každá panenka přidává faktor dva k rozměru obvodu QFT, přičemž nejmenší panenka je úplně uprostřed jako QFT$_2$, neboli Hadamardovo hradlo.

Aby ses dostal/a na úroveň vložení panenky do té nejbližší větší, tedy zvýšení rozměru QFT o faktor dva, vždy postupuješ stejně:

1. Nejprve aplikuj QFT$_{2^{m-1}}$ na nejspodnějších $m-1$ qubitů. To je tvoje „menší panenka" ze sady ruských matrjošek, kterou brzy vložíš do té další největší.
2. Použij nejbližší qubit výše jako řídicí a aplikuj hradla řízené fáze na každý z dolních $m-1$ qubitů s fázemi ke standardním bázovým stavům každého ze zbývajících $m-1$ qubitů.
3. Proveď Hadamardovo hradlo na tomtéž nejvyšším qubitu, který byl použit jako řídicí ve fázových hradlech.
4. Použij hradla SWAP k permutaci pořadí qubitů tak, aby se nejméně významný (horní) bit stal nejvýznamnějším (dolním) bitem a všechny ostatní se posunou o jeden nahoru.

Funkci QFTGate z knihovny obvodů Qiskitu jsme již používali, ale nyní se podívejme dovnitř některých těchto hradel QFT a ověřme výše popsaný postup. Lze to udělat 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")

Takže, snad z prvních čtyř QFT začínáš vidět, jak je každý vnořen do toho o stupeň většího. Možná sis všiml/a, že některá fázová hradla nejsou přesně taková, jak předepisuje výše popsaný postup, a SWAPy se neobjevují po každé podrutině, ale pouze na úplném konci celého QFT. To nám šetří zbytečná hradla, která by způsobila, že obvod trvá déle a je náchylnější k chybám. Místo implementace SWAPu po každé vnořené panenky si obvod pamatuje, kde by každý stav qubitu měl být, a podle toho upravuje qubity, na které aplikuje fázová hradla. Pak závěrečná sada SWAPů na konci vše uvede na správné místo.

Aplikace QFT: Odhad fáze

Podívejme se, jak lze QFT použít k řešení užitečného problému v kvantovém výpočetnictví. Výpočet inverzní kvantové Fourierovy transformace je nezbytným krokem v algoritmu známém jako Kvantový odhad fáze (QPE), který je sám o sobě podrutinovým blokem v mnoha dalších algoritmech, včetně „korunního klenotech" kvantových algoritmů — Shorova algoritmu faktorizace.

Cílem QPE je odhadnout vlastní hodnoty unitárního operátoru. Unitární operátory jsou všudypřítomné v kvantovém výpočetnictví a nalezení vlastních hodnot jejich přidružených vlastních vektorů je u mnoha z nich nezbytným krokem v rámci rozsáhlejšího algoritmu. V závislosti na problému může vlastní hodnota reprezentovat energii Hamiltoniánu v simulačním problému, pomoci nám nalézt prvočíselné faktory čísla v Shorově algoritmu nebo obsahovat jiné zásadní informace. QPE je jednou z nejdůležitějších a nejpoužívanějších podrutin v kvantovém výpočetnictví.

Takže co to má společného s kvantovou Fourierovou transformací? No, jak si možná pamatuješ, každá vlastní hodnota $\lambda$ unitárního operátoru má velikost $|\lambda| = 1$. Každou vlastní hodnotu tedy můžeme zapsat jako komplexní číslo s velikostí jedna:

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

kde $\theta$ je reálné číslo mezi 0 a 1. Pokud chceš více informací o unitárních maticích, podívej se na lekci Johna Watrouse na toto téma v Základech kvantové informace.

Všimni si, že $\lambda$ je periodické v $\theta$. To by ti mohlo napovídat, že by mohlo být zapojeno QFT, protože jsme viděli, jak užitečné jsou QFT pro analýzu periodických funkcí. Níže si projdeme algoritmus a uvidíme přesně, jak QFT vstupuje do hry.

Jak QPE funguje

Nejprve začneme nejjednodušším algoritmem QPE, který přibližně odhaduje fázi na jediný binární digit přesnosti. Jinými slovy, tento algoritmus dokáže rozlišit mezi $\theta = 0$ a $\theta = 1/2$, ale lépe to neumí. Tady je schéma obvodu:

Qubity jsou připraveny ve stavu $|\pi_0\rangle = |\psi\rangle|0\rangle$, kde qubit $0$ je ve stavu $|0\rangle$ a zbývající qubity jsou ve stavu $|\psi\rangle$, který je vlastním stavem $U$. Po prvním Hadamardově hradle se stav qubitů stane:

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

Dalším hradlem je „řízené-$U$" hradlo. Toto aplikuje unitární operaci $U$ na spodní qubity ve stavu $|\psi\rangle$, pokud je qubit 0 ve stavu $|1\rangle$, ale nedělá s $|\psi\rangle$ nic, pokud je qubit 0 ve stavu $|0\rangle$. To transformuje qubity do stavu:

$|\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)$

Právě se stalo něco zvláštního: řízené-$U$ hradlo používá qubit $0$ pouze jako řídicí qubit, takže by se mohlo zdát, že toto hradlo vůbec nezmění stav qubitu 0. Ale nějak ho změní! Přestože byla operace aplikována na spodní qubity, celkovým efektem hradla je změna fáze qubitu $0$. Toto je známo jako „mechanismus zpětného kopnutí fáze" a používá se v mnoha kvantových algoritmech, včetně algoritmů Deutsch-Josza a Groverova. Pokud se chceš dozvědět více o mechanismu zpětného kopnutí fáze, podívej se na lekci Johna Watrouse o Kvantových dotazovacích algoritmech v Základech kvantových algoritmů.

Po zpětném kopnutí fáze aplikujeme ještě jedno Hadamardovo hradlo na qubit $0$, což vede ke stavu:

$|\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že když na konci změříme qubit $0$, naměříme $|0\rangle$ se 100% jistotou, pokud $\theta = 0$, a naměříme $|1\rangle$ se 100% jistotou, pokud $\theta = \frac{1}{2}$ (a pokud je náš kvantový počítač dokonalý, bez šumu). Pokud je $\theta$ něco jiného, je výsledné měření pouze pravděpodobnostní a říká nám jen omezené množství.

QPE s větší přesností: více qubitů

Tento jednoduchý koncept můžeme rozšířit na složitější algoritmus s libovolnou přesností. Pokud místo pouhého qubitu $0$ k měření fáze použijeme $m$ qubitů $0$ až $m-1$, budeme schopni odhadnout fázi s $m$ bity přesnosti. Podívejme se, jak to funguje:

Tento přesnější obvod QPE začíná stejně jako jednobitová verze: Hadamardova hradla jsou aplikována na prvních $m$ qubitů a zbývající qubity jsou připraveny ve stavu $|\psi\rangle$, čímž vzniká stav:

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

Nyní jsou aplikovány řízené unitární operace. Qubit $0$ je řídicím pro stejnou unitární operaci $U$ jako předtím. Ale teď je qubit $1$ řídicím pro unitární operaci $U^2$, což je jednoduše $U$ aplikované dvakrát. Vlastní hodnota $U^2$ je tedy $e^{2*2\pi i \theta}$. Obecně platí, že každý qubit $k$ od 0 do $m-1$ bude řídicím pro unitární operaci $U^{2^k}$. To znamená, že každý z těchto qubitů zažije zpětné kopnutí fáze $e^{2^k*2\pi i \theta}$. To vede ke stavu:

$|\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)$

To lze přepsat jako součet přes stavy komputační báze:

$|\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$

Zdá se ti ten součet povědomý? Je to QFT! Vzpomeň si na rovnici pro kvantovou Fourierovu transformaci:

$\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že, pokud je fáze $\theta = y/2^m$ pro nějaké celé číslo $y$ mezi $0$ a $2^m-1$, pak aplikace inverzního QFT na tento stav bude mít za výsledek stav:

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

a z $|y\rangle$ můžeme odvodit $\theta$.

Pokud $\theta/2^m$ není celočíselným násobkem, pak inverzní QFT pouze přiblíží $\theta$. Jak dobře se přiblíží $\theta$, bude pravděpodobnostní — to znamená, že nezíská vždy nejlepší přiblížení, ale bude poměrně blízko, a čím více qubitů $m$ použiješ, tím lepšího přiblížení dosáhneš. Chceš-li se dozvědět více o kvantifikaci tohoto přiblížení $\theta$, podívej se na lekci Johna Watrouse o Odhadu fáze a faktorizaci v Základech kvantových algoritmů.

Závěr

Tento modul poskytl přehled o tom, co je QFT, jak se implementuje na kvantovém počítači a jak je užitečná při řešení problémů. Nabídli jsme ti ochutnávku její užitečnosti, když jsme viděli, jak ji lze použít v kvantovém odhadu fáze k poznání vlastních hodnot unitární matice.

Klíčové pojmy

• Kvantová Fourierova transformace je kvantovým analogem diskrétní Fourierovy transformace.
• QFT je příkladem transformace báze.
• Postup kvantového odhadu fáze se opírá o mechanismus zpětného kopnutí fáze z řízených unitárních operací a o inverzní QFT.
• QFT a QPE jsou obě široce používané podrutiny v mnoha kvantových algoritmech.

Otázky

Pravda/Nepravda

1. P/N Kvantová Fourierova transformace je kvantovým analogem klasické diskrétní Fourierovy transformace (DFT).
2. P/N QFT lze implementovat pouze pomocí Hadamardových a CNOT hradel.
3. P/N QFT je klíčovou součástí Shorova algoritmu.
4. P/N Výstupem Kvantového odhadu fáze je kvantový stav reprezentující vlastní vektor operátoru.
5. P/N QPE vyžaduje použití inverzní Kvantové Fourierovy transformace (QFT$^\dag$).
6. P/N V QPE, pokud je fáze $\phi$ přesně reprezentovatelná pomocí $n$ bitů, algoritmus dá správný výsledek s pravděpodobností 1.

Krátké odpovědi

1. Kolik qubitů je potřeba pro provedení QFT na systému s $2^n$ datovými body?
2. Lze QFT použít na stav, který není stavem komputační báze? Pokud ano, co se stane?
3. Jak počet řídicích qubitů použitých v QPE ovlivňuje rozlišení výsledného odhadu fáze?

Úlohy

1. Pomocí násobení matic ověř, že kroky v algoritmu QFT skutečně vedou k matici $\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}$$

(Nemusíš to dělat ručně!)

Výzvy

1. Vytvoř čtyřqubitový stav, který je rovnou superpozicí všech lichých komputačních bázových stavů: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. Pak na stav proveď QFT. Jaký je výsledný stav? Vysvětli, proč tvůj výsledek dává smysl, s využitím svých znalostí Fourierových transformací.