Kvantové algoritmy: Odhad fáze

poznámka

Kento Ueda (15. května 2024)

Tento notebook představuje základní pojmy a implementaci kvantové Fourierovy transformace (QFT) a kvantového odhadu fáze (QPE).

Stáhni si pdf původní přednášky. Pamatuj, že některé úryvky kódu mohou být zastaralé, protože jde o statické obrázky.

Přibližný čas QPU potřebný pro tento experiment je 7 sekund.

1. Úvod

Kvantová Fourierova transformace (QFT)

Kvantová Fourierova transformace je kvantovým protějškem klasické diskrétní Fourierovy transformace. Jde o lineární transformaci aplikovanou na kvantové stavy, která zobrazuje výpočetní báze do jejich reprezentací ve Fourierově bázi. QFT hraje klíčovou roli v mnoha kvantových algoritmech a poskytuje efektivní metodu pro získávání informací o periodicitě z kvantových stavů. QFT lze implementovat pomocí $O(N^2)$ operací s kvantovými hradly, jako jsou Hadamardova hradla a Control-Phase hradla pro $N$ qubitů, což umožňuje exponenciální zrychlení oproti klasické Fourierově transformaci.

• Aplikace: Tvoří základ kvantových algoritmů, jako je Shorův algoritmus pro faktorizaci velkých celých čísel a diskrétní logaritmus.

Kvantový odhad fáze (QPE)

Kvantový odhad fáze je kvantový algoritmus používaný k odhadu fáze spojené s vlastním vektorem unitárního operátoru. Tento algoritmus vytváří most mezi abstraktními matematickými vlastnostmi kvantových stavů a jejich výpočetními aplikacemi.

• Aplikace: Umožňuje řešit úlohy, jako je hledání vlastních čísel unitárních matic a simulace kvantových systémů.

QFT a QPE společně tvoří zásadní páteř mnoha kvantových algoritmů řešících problémy, které jsou pro klasické počítače neproveditelné. Na konci tohoto notebooku získáš představu o tom, jak jsou tyto techniky implementovány.

2. Základy kvantové Fourierovy transformace (QFT)

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

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
from qiskit.visualization import plot_histogram, plot_bloch_multivector
from qiskit.quantum_info import Statevector
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit_ibm_runtime import Sampler

from numpy import pi

Analogicky s diskrétní Fourierovou transformací QFT působí na kvantový stav $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$ pro $N$ qubitů a zobrazuje ho na kvantový stav $\vert Y\rangle = \sum_{k=0}^{N-1} y_k \vert k \rangle$.

$$QFT_{N}: \vert j \rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk} \vert k \rangle$$

kde $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$.

Nebo reprezentace pomocí unitární matice:

$$U_{QFT} = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \sum_{k=0}^{N-1} \omega_N^{jk} \vert k \rangle \langle j \vert$$

2.1. Intuice

Kvantová Fourierova transformace (QFT) převádí mezi dvěma bázemi: výpočetní (Z) bází a Fourierovou bází. Co však Fourierova báze v tomto kontextu znamená? Nejspíš si vybavíš, že Fourierova transformace $F(\omega)$ funkce $f(x)$ popisuje konvoluci $f(x)$ se sinusoidální funkcí o frekvenci $\omega$. Laicky řečeno: Fourierova transformace je funkce, která popisuje, kolik z každé frekvence $\omega$ bychom potřebovali, abychom sestavili funkci $f(x)$ ze sinových (nebo kosinových) funkcí. Abys lépe pochopil, co v tomto kontextu QFT znamená, podívej se na níže uvedené sekvenční obrázky, které ukazují číslo zakódované binárně pomocí čtyř qubitů:

Ve výpočetní bázi ukládáme čísla binárně pomocí stavů $|0\rangle$ a $|1\rangle$.

Všimni si frekvence, s jakou se jednotlivé qubity mění; nejlevější qubit se překlápí při každém zvýšení čísla, další při každých 2 zvýšeních, třetí při každých 4 zvýšeních a tak dále.

Pokud na tyto stavy aplikujeme kvantovou Fourierovu transformaci, zobrazíme

$$|\text{State in Computational Basis}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{State in Fourier Basis}\rangle$$ $$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$

(Stavy ve Fourierově bázi často označujeme pomocí vlnovky (~)).

Ve Fourierově bázi ukládáme čísla pomocí různých rotací kolem osy Z:

IFRAME

Úhel, o který se každý qubit kolem osy Z otočí, určuje číslo, které chceme uložit. Ve stavu $|\widetilde{0}\rangle$ jsou všechny qubity ve stavu $|{+}\rangle$. Jak je vidět ve výše uvedeném příkladu, k zakódování stavu $|\widetilde{5}\rangle$ na 4 qubitech jsme nejlevější qubit otočili o $\tfrac{5}{2^n} = \tfrac{5}{16}$ celé otáčky ($\tfrac{5}{16}\times 2\pi$ radiánů). Další qubit je otočen o dvojnásobek ($\tfrac{10}{16}\times 2\pi$ radiánů, tedy $10/16$ celé otáčky), tento úhel se pak zdvojnásobuje pro další qubit a tak dále.

Opět si všimni frekvence, s jakou se jednotlivé qubity mění. Nejlevější qubit (qubit 0) má v tomto případě nejnižší frekvenci a ten nejpravější nejvyšší.

2.2 Příklad: 1qubitová QFT

Uvažujme případ $N = 2^1 = 2$.

Unitární matici lze zapsat:

$$\begin{aligned} U_{QFT} & = \frac{1}{\sqrt{2}} \sum_{j=0}^{1} \sum_{k=0}^{1} \omega_2^{jk} \vert k \rangle \langle j \vert \\ & = \frac{1}{\sqrt{2}} (\omega_2^{0} \vert 0 \rangle \langle 0 \vert + \omega_2^{0} \vert 0 \rangle \langle 1 \vert + \omega_2^{0} \vert 1 \rangle \langle 0 \vert + \omega_2^{1} \vert 1 \rangle \langle 1 \vert) \\ & = \frac{1}{\sqrt{2}} (\vert 0 \rangle \langle 0 \vert + \vert 0 \rangle \langle 1 \vert + \vert 1 \rangle \langle 0 \vert - \vert 1 \rangle \langle 1 \vert) \\ & = H \end{aligned}$$

Tato operace je výsledkem aplikace Hadamardova hradla ($H$).

2.3 Reprezentace QFT jako součinu

Zobecněme transformaci pro $N = 2^n$, $QFT_{N}$ působící na stav $\vert x \rangle = \vert x_1\ldots x_n \rangle$.

$$\begin{aligned} QFT_N\vert x \rangle & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1}\omega_N^{xy} \vert y \rangle \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i xy / 2^n} \vert y \rangle ~\text{protože}\: \omega_N^{xy} = e^{2\pi i \frac{xy}{N}} \:\text{a}\: N = 2^n \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i \left(\sum_{k=1}^n y_k/2^k\right) x} \vert y_1 \ldots y_n \rangle \:\text{přepsáno do zlomkové binární notace}\: y = y_1\ldots y_n, y/2^n = \sum_{k=1}^n y_k/2^k \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \prod_{k=1}^n e^{2 \pi i x y_k/2^k } \vert y_1 \ldots y_n \rangle \:\text{po rozepsání exponenciály součtu na součin exponenciál,} \\ & = \frac{1}{\sqrt{N}} \bigotimes_{k=1}^n \left(\vert0\rangle + e^{2 \pi i x /2^k } \vert1\rangle \right) \:\text{po přerovnání sum a součinů a rozepsání} \sum_{y=0}^{N-1} = \sum_{y_1=0}^{1}\sum_{y_2=0}^{1}\ldots\sum_{y_n=0}^{1} \\ & = \frac{1}{\sqrt{N}} \left(\vert0\rangle + e^{\frac{2\pi i}{2}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^2}x} \vert1\rangle\right) \otimes \ldots \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^{n-1}}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^n}x} \vert1\rangle\right) \end{aligned}$$

2.4 Příklad: Konstrukce obvodu pro 3qubitovou QFT

Z výše uvedeného popisu nemusí být zřejmé, jak sestrojit obvod QFT. Prozatím si jen všimni, že očekáváme, že tři qubity budou mít fáze, které se vyvíjejí různými „rychlostmi”. Přesné pochopení, jak se to promítá do obvodu, je ponecháno jako cvičení pro čtenáře. V přednáškovém pdf najdeš řadu diagramů a příkladů. Mezi další zdroje patří tato lekce z kurzu Fundamentals of quantum algorithms.

QFT budeme demonstrovat pouze pomocí simulátorů, a tak nebudeme používat framework Qiskit patterns, dokud nepřejdeme ke kvantovému odhadu fáze.

# Prepare for 3 qubits circuit
qr = QuantumRegister(3)
cr = ClassicalRegister(3)
qc = QuantumCircuit(qr, cr)

qc.h(2)
qc.cp(pi / 2, 1, 2)  # Controlled-phase gate from qubit 1 to qubit 2
qc.cp(pi / 4, 0, 2)  # Controlled-phase gate from qubit 0 to qubit 2
qc.draw(output="mpl")

qc.h(1)
qc.cp(pi / 2, 0, 1)  # Controlled-phase gate from qubit 0 to qubit 1

qc.draw(output="mpl")

qc.h(0)

qc.draw(output="mpl")

qc.swap(0, 2)

qc.draw(output="mpl")

Jako příklad zkusíme aplikovat QFT na $|5\rangle$.

Nejprve potvrdíme binární zápis celého čísla 5 a vytvoříme obvod kódující stav 5:

bin(5)

'0b101'

qc = QuantumCircuit(3)

qc.x(0)
qc.x(2)
qc.draw(output="mpl")

Kvantové stavy zkontrolujeme pomocí simulátoru Aer:

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Nakonec přidáme QFT a podíváme se na výsledný stav našich qubitů:

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Vidíme, že naše funkce QFT zafungovala správně. Qubit 0 byl otočen o $\tfrac{5}{8}$ plné otáčky, qubit 1 o $\tfrac{10}{8}$ plné otáčky (což odpovídá $\tfrac{1}{4}$ plné otáčky) a qubit 2 o $\tfrac{20}{8}$ plné otáčky (což odpovídá $\tfrac{1}{2}$ plné otáčky).

2.5 Cvičení: QFT

(1) Implementuj QFT pro 4 qubity.

##your code goes here##

(2) Aplikuj QFT na $|14\rangle$, simuluj a vykresli stavový vektor pomocí Blochovy sféry.

##your code goes here##

Řešení cvičení: QFT

(1)

qr = QuantumRegister(4)
cr = ClassicalRegister(4)
qc = QuantumCircuit(qr, cr)

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

(2)

bin(14)

'0b1110'

qc = QuantumCircuit(4)

qc.x(1)
qc.x(2)
qc.x(3)
qc.draw("mpl")

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)
qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

3. Základy odhadu kvantové fáze (QPE)

Pro danou unitární operaci $U$ QPE odhaduje $\theta$ v $U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$, protože $U$ je unitární, všechny jeho vlastní hodnoty mají normu 1.

3.1 Postup

1. Nastavení

$\vert\psi\rangle$ se nachází v jedné sadě qubitových registrů. Další sada $n$ qubitů tvoří čítací registr, do kterého uložíme hodnotu $2^n\theta$:

$$|\psi_0\rangle = \lvert 0 \rangle^{\otimes n} \lvert \psi \rangle$$

2. Superpozice

Aplikuj $n$-bitovou operaci Hadamardova hradla $H^{\otimes n}$ na čítací registr:

$$|\psi_1\rangle = {\frac {1}{2^{\frac {n}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes n} \lvert \psi \rangle$$

3. Řízené unitární operace

Potřebujeme zavést řízené unitární $CU$, které aplikuje unitární operátor $U$ na cílový registr pouze tehdy, pokud příslušný řídicí bit je $|1\rangle$. Protože $U$ je unitární operátor s vlastním vektorem $|\psi\rangle$ takovým, že $U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$, platí:

$$U^{2^{j}}|\psi \rangle =U^{2^{j}-1}U|\psi \rangle =U^{2^{j}-1}e^{2\pi i\theta }|\psi \rangle =\cdots =e^{2\pi i2^{j}\theta }|\psi \rangle$$

3.2 Příklad: T-gate QPE

Použijme T-gate jako příklad QPE a odhadněme jeho fázi $\theta$.

$$T|1\rangle = \begin{pmatrix} 1 & 0\\ 0 & e^\frac{i\pi}{4}\\ \end{pmatrix} \begin{pmatrix} 0\\ 1\\ \end{pmatrix} = e^\frac{i\pi}{4}|1\rangle$$

Očekáváme, že najdeme:

$$\theta = \frac{1}{8}$$

kde

$$T|1\rangle = e^{2i\pi\theta}|1\rangle$$

Inicializujeme $\vert\psi\rangle = \vert1\rangle$ vlastního vektoru T-gate aplikací hradla $X$:

qpe = QuantumCircuit(4, 3)
qpe.x(3)
qpe.draw(output="mpl")

Dále aplikujeme Hadamardova hradla na čítací qubit:

for qubit in range(3):
    qpe.h(qubit)
qpe.draw(output="mpl")

Provedeme řízené unitární operace:

repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.draw(output="mpl")

Aplikujeme inverzní kvantovou Fourierovu transformaci pro převod stavu čítacího registru a poté změříme čítací registr:

from qiskit.circuit.library import QFT

# Apply inverse QFT
qpe.append(QFT(3, inverse=True), [0, 1, 2])
qpe.draw(output="mpl")

for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

Můžeme simulovat pomocí simulátoru Aer:

aer_sim = AerSimulator()
shots = 2048

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

Vidíme, že s jistotou dostaneme jeden výsledek (001), který se převede na desetinné číslo: 1. Nyní potřebujeme náš výsledek (1) vydělit $2^n$, abychom dostali $\theta$:

$$\theta = \frac{1}{2^3} = \frac{1}{8}$$

Shorův algoritmus nám umožňuje faktorizovat číslo tím, že sestavíme obvod s neznámým $\theta$ a získáme $\theta$.

3.3 Cvičení

Odhadni $\theta = 1/3$ pomocí 3 qubitů pro počítání a jednoho qubitu pro vlastní vektor.

$P|1\rangle = e^{i\lambda}|1\rangle$. Protože chceme implementovat $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$, musíme nastavit $\lambda = \tfrac{2 \pi}{3}$.

##your code goes here##

Řešení cvičení: $\theta = 1/3$

# Create and set up circuit
qpe = QuantumCircuit(4, 3)

# Apply H-Gates to counting qubits:
for qubit in range(3):
    qpe.h(qubit)

# Prepare our eigenstate |psi>:
qpe.x(3)

# Do the controlled-U operations:
angle = 2 * pi / 3
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(angle, counting_qubit, 3)
    repetitions *= 2

# Do the inverse QFT:
qpe.append(QFT(3, inverse=True), [0, 1, 2])

for n in range(3):
    qpe.measure(n, n)

qpe.draw(output="mpl")

aer_sim = AerSimulator()
shots = 4096

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

4. Spuštění pomocí primitivy Qiskit Runtime Sampler

Provedeme QPE na skutečném kvantovém zařízení a budeme postupovat podle 4 kroků Qiskit patterns.

1. Namapuj problém do kvantově nativního formátu
2. Optimalizuj obvody
3. Spusť cílový obvod
4. Post-procesuj výsledky

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler

# Loading your IBM Quantum® account(s)

service = QiskitRuntimeService()

4.1 Krok 1: Namapuj problém na kvantové obvody a operátory

qpe = QuantumCircuit(4, 3)
qpe.x(3)
for qubit in range(3):
    qpe.h(qubit)
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.append(QFT(3, inverse=True), [0, 1, 2])
for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

backend = service.least_busy(simulator=False, operational=True, min_num_qubits=4)

print(backend)

<IBMBackend('ibm_strasbourg')>

4.2 Krok 2: Optimalizace pro cílový hardware

# Transpile the circuit into basis gates executable on the hardware
pm = generate_preset_pass_manager(backend=backend, optimization_level=2)
qc_compiled = pm.run(qpe)

qc_compiled.draw("mpl", idle_wires=False)

4.3 Krok 3: Spuštění na cílovém hardware

real_sampler = Sampler(mode=backend)
job = real_sampler.run([qc_compiled], shots=1024)
job_id = job.job_id()
print("job id:", job_id)

job id: d13p4zb5z6q00087ag00

job = service.job(job_id)  # Input your job-id between the quotations
job.status()

'DONE'

result_real = job.result()
print(result_real)

PrimitiveResult([SamplerPubResult(data=DataBin(c=BitArray(<shape=(), num_shots=1024, num_bits=3>)), metadata={'circuit_metadata': {}})], metadata={'execution': {'execution_spans': ExecutionSpans([DoubleSliceSpan(<start='2025-06-09 22:39:00', stop='2025-06-09 22:39:00', size=1024>)])}, 'version': 2})

4.4 Krok 4: Post-procesování výsledků

from qiskit.visualization import plot_histogram

plot_histogram(result_real[0].data.c.get_counts())

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'