Transformata Fourier cuantică

Pentru acest modul Qiskit in Classrooms, studenții trebuie să aibă un mediu Python funcțional cu următoarele pachete instalate:

• qiskit v2.1.0 sau mai nou
• qiskit-ibm-runtime v0.40.1 sau mai nou
• qiskit-aer v0.17.0 sau mai nou
• qiskit.visualization
• numpy
• pylatexenc

Pentru a configura și instala pachetele de mai sus, consultă ghidul Instalare Qiskit. Pentru a rula joburi pe computere cuantice reale, studenții vor trebui să își creeze un cont IBM Quantum® urmând pașii din ghidul Configurează-ți contul IBM Cloud.

Acest modul a fost testat și a folosit 13 secunde de timp QPU. Aceasta este o estimare de bună-credință; utilizarea ta reală poate varia.

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

Introducere

Transformata Fourier este un instrument omniprezent cu aplicații în matematică, fizică, procesarea semnalelor, compresia datelor și nenumărate alte domenii. O versiune cuantică a transformatei Fourier, numită pe bună dreptate transformata Fourier cuantică, stă la baza unora dintre cei mai importanți algoritmi cuantici.

Astăzi, după o reîmprospătare a transformatei Fourier clasice, vom vorbi despre cum implementăm transformata Fourier cuantică pe un computer cuantic. Apoi, vom discuta una dintre aplicațiile transformatei Fourier cuantice într-un algoritm numit algoritmul de estimare a fazei. Estimarea cuantică a fazei este o subrutină în celebrul algoritm de factorizare al lui Shor, uneori denumit „bijuteria de coroană" a calculului cuantic. Acest modul se îndreaptă spre un alt modul dedicat în întregime algoritmului lui Shor, dar este conceput și ca unul de sine stătător. Transformata Fourier cuantică este un algoritm fascinant și util în sine!

Transformata Fourier clasică

Înainte să ne aruncăm în transformata Fourier cuantică, să ne reîmprospătăm mai întâi cunoștințele despre versiunea clasică. Transformata Fourier este o metodă de transformare dintr-o „bază" în alta. Poți să te gândești la două baze ca la perspective diferite ale aceleiași probleme — ambele sunt moduri valide de a exprima o funcție, dar una sau cealaltă poate fi mai revelatoare, în funcție de problema în cauză. Câteva exemple de perechi de baze conectate prin transformata Fourier sunt poziția și momentul cinetic, respectiv timpul și frecvența.

Să vedem un exemplu despre cum ne poate ajuta transformata Fourier să determinăm ce notă cântă un instrument pe baza formei de undă audio. De obicei, vedem formele de undă reprezentate în baza timp — adică amplitudinea undei este exprimată ca funcție de timp.

Putem aplica transformata Fourier acestei forme de undă pentru a trece din baza timp în baza frecvență:

În baza frecvență, putem vedea cu ușurință un vârf clar la aproximativ 260 Hz. Acesta este un Do central!

Acum, poate ai fi reușit să determini că se cânta un Do central fără să folosești transformata Fourier, dar ce se întâmplă dacă mai multe note sunt cântate simultan? Atunci forma de undă devine mai complicată atunci când o reprezentăm în baza timp:

Dar spectrul de frecvență identifică clar trei vârfuri:

Acesta a fost un acord Do major, cântând notele Do, Mi și Sol.

Acest tip de analiză Fourier ne poate ajuta să extragem componentele de frecvență ale oricărui semnal complicat.

Transformata Fourier discretă

Transformata Fourier este utilă pentru numeroase aplicații de procesare a semnalelor. Dar în majoritatea acestor aplicații din lumea reală (inclusiv exemplul muzical de mai sus), dorim să transformăm un set discret de $N$ puncte de date — nu o funcție continuă. În acest caz, folosim transformata Fourier discretă. Transformata Fourier discretă (DFT) acționează asupra unui vector $(x_0, ..., x_{N-1})$ și îl mapează la vectorul $(y_0, ..., y_{N-1})$ conform formulei:

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

unde luăm $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$. (Rețineți că există și alte convenții care au un semn minus în exponent, deci fii atent când întâlnești DFT în practică.) Reamintim că $e^{2\pi i \frac{jk}{N}}$ este o funcție periodică, cu perioada $\frac{N}{k}$. Astfel, prin înmulțirea cu această funcție, transformata Fourier este, în esență, o modalitate de a descompune funcția (discretă) $\{x_{j}\}$ într-o combinație liniară a funcțiilor periodice constitutive, fiecare cu perioada $\frac{N}{k}$.

Transformata Fourier cuantică

Acum am văzut cum transformata Fourier este folosită pentru a reprezenta o funcție ca o combinație liniară a unui nou set de „funcții de bază". Transformările de bază se fac regulat și pe stările Qubit. De exemplu, starea unui singur Qubit $|\psi\rangle$ poate fi exprimată în baza computațională $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$, cu stările de bază $|0\rangle$ și $|1\rangle$, sau în baza $X$ $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ cu stările de bază $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ și $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$. Ambele sunt la fel de valide, dar una poate fi mai naturală decât cealaltă, în funcție de tipul de problemă pe care încerci să o rezolvi.

Stările Qubit pot fi exprimate și în baza Fourier, unde o stare este exprimată în funcție de o combinație liniară a stărilor de bază Fourier $|\phi_y\rangle$, mai degrabă decât stările de bază computaționale obișnuite, $|x\rangle$. Pentru a face acest lucru, trebuie să aplici o transformată Fourier cuantică (QFT):

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

cu $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$ ca mai sus, iar $N$ este numărul de stări de bază din sistemul tău cuantic. Rețineți că, deoarece lucrăm acum cu Qubiți, $m$ Qubiți îți dau $2^m$ stări de bază, deci $N=2^m$. Aici, stările de bază sunt scrise ca un singur număr $|x\rangle$ unde $x$ variază de la $0$ la $N-1$, dar mai frecvent vei vedea stările de bază exprimate ca $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$, ..., $|11...11\rangle$, unde fiecare cifră binară reprezintă starea Qubitului 0 până la $m-1$, de la dreapta la stânga. Există o modalitate simplă de a converti aceste stări binare la un singur număr: tratează-le pur și simplu ca numere binare! Deci, $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$, și așa mai departe, până la $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$.

Construiește intuiția pentru stările de bază Fourier

Deci, tocmai am trecut în revistă care sunt stările de bază computaționale și cum sunt ordonate: sunt setul de stări în care fiecare Qubit este fie în $0$, fie în $1$, și le ordonăm de la starea în care toți Qubiții sunt $0$, $|00...00\rangle$, până la starea în care sunt toți $1$, $|11...11\rangle$.

Dar cum putem înțelege stările de bază Fourier? Toate stările de bază Fourier sunt superpoziții egale ale tuturor stărilor de bază computaționale, dar fiecare stare diferă de celelalte prin periodicitatea fazei componentelor. Pentru a înțelege acest lucru mai concret, să aruncăm o privire la cele patru stări de bază Fourier ale unui sistem cu doi Qubiți. Cea mai joasă stare Fourier este cea a cărei fază nu variază deloc:

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

Putem vizualiza această stare reprezentând amplitudinea complexă a fiecăruia dintre termeni. Linia roșie ghidează ochiul pentru a-ți arăta cum faza acestei amplitudini se răsucește în jurul planului complex ca funcție a stării de bază computaționale. Pentru $|\phi_0\rangle$, faza rămâne constantă:

Următoarea stare de bază Fourier este cea ale cărei faze ale componentelor se răsucesc de la $0$ la $2\pi$ o singură dată:

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

Și putem vedea această răsucire în graficul amplitudinii complexe față de starea de bază computațională:

Deci, fiecare stare are o fază cu $2\pi/4$ radiani mai mare decât starea anterioară, când sunt ordonate în mod standard, deoarece în acest exemplu avem patru stări de bază ($N=4$). Următoarea stare de bază se răsucește de la 0 la $2\pi$ de două ori:

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

În sfârșit, cea mai înaltă componentă Fourier este cea cu faza variind cel mai rapid. Pentru exemplul nostru cu doi Qubiți, este cea ale cărei faze se răsucesc de la 0 la $2\pi$ de trei ori:

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

În general, pentru o stare cu $m$ Qubiți, vor exista $2^m$ stări de bază Fourier, a căror frecvență în variația fazei variază de la constantă, pentru $|\phi_0\rangle$, la rapid variabilă pentru $|\phi_{2^m-1}\rangle$, completând $2^m-1$ răsuciri în jurul lui $2\pi$ peste superpoziția de stări. Deci, când aplicăm QFT unui stat cuantic, facem practic aceeași analiză de bază pe care am făcut-o pentru forma de undă muzicală în Introducere. Determinăm componentele de frecvență Fourier care contribuie la crearea stării cuantice de interes.

Încearcă câteva exemple de QFT-uri

Să continuăm să ne construim intuiția pentru transformata cuantică Fourier prin crearea unui stare în baza computațională, apoi să vedem ce se întâmplă când aplicăm QFT-ul asupra ei. Deocamdată, vom trata QFT-ul ca pe o cutie neagră pe care o aplicăm folosind QFTGate din biblioteca de circuite Qiskit. Mai târziu, vom arunca o privire sub capotă pentru a vedea cum este implementat.

Începem prin a încărca pachetele necesare și a selecta un dispozitiv pe care să rulăm Circuit-ul nostru:

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

Dacă nu ai timp disponibil în contul tău sau dorești să folosești un simulator din orice motiv, poți rula celula de mai jos pentru a configura un simulator care va imita dispozitivul cuantic selectat anterior:

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

O singură stare din baza computațională

Mai întâi, să încercăm să transformăm o singură stare din baza computațională. Vom începe prin a crea o stare computațională aleatoare:

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

Acum, să transformăm Fourier această stare folosind 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)

După cum poți vedea, măsurăm populațiile fiecărei stări ca fiind mai mult sau mai puțin egale, cu mici variații datorate zgomotului experimental și statistic. Deci, dacă aplici QFT-ul unui singur stat din baza computațională, rezultatul este o superpozitie egală a tuturor stărilor. Dacă ești familiarizat cu transformatele Fourier, acest lucru probabil nu te surprinde. Un principiu de bază care ne poate ajuta să construim o legătură intuitivă între o funcție și transformata sa Fourier este că lățimea unei funcții este invers proporțională cu lățimea transformatei sale Fourier. Deci, ceva foarte localizat în timp, de exemplu, ca un impuls foarte scurt, va necesita o gamă largă de frecvențe pentru a genera acel impuls. Acel semnal va fi foarte larg în spațiul Fourier.

Acest fapt este de fapt legat de incertitudinea cuantică! Principiul incertitudinii al lui Heisenberg este enunțat de obicei ca $\Delta x \Delta p \ge \hbar / 2$. Deci, dacă incertitudinea în $x$ ($\Delta x$) este mică, incertitudinea în impuls ($\Delta p$) trebuie să fie mare, și invers. Se dovedește că trecerea din baza de poziție $x$ în baza de impuls $p$ se realizează printr-o transformată Fourier.

Notă: Ține minte că măsurăm populațiile în fiecare dintre stările de bază, deci pierdem informații despre fazele relative dintre diferitele părți ale superpozitiei. Deci, deși QFT-ul oricărui singur stat din baza computațională va produce aceeași distribuție egală a populației peste toate stările de bază, fazele nu vor fi neapărat aceleași.

Două stări din baza computațională

Acum, haideți să vedem ce se întâmplă atunci când pregătim o superpunere de stări din baza computațională. Ce crezi că va arăta transformata Fourier în acest caz?

Să alegem superpunerea:

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

Acum, haideți să aplicăm transformata Fourier acestei stări cu 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)

Acesta ar putea fi un rezultat mai surprinzător. Se pare că QFT-ul stării $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ este o superpunere a tuturor stărilor din baza cu index par. Dar dacă ne gândim înapoi la vizualizarea fiecărei stări din baza $|\phi_y\rangle$ și la modul în care faza fiecărei componente se înfășoară de $y$ ori în jurul lui $2\pi$, motivul pentru care obținem acest rezultat poate deveni clar.

Check your understanding

Read the question(s) below, think about your answer, then click the triangle to reveal the solution.

Folosind indiciul de mai sus, explică de ce rezultatul obținut pentru QFT-ul lui $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ este de așteptat.

Răspuns:

Starea originală are o fază relativă de 0 (sau un multiplu întreg al lui $2\pi$) între cele două părți ale superpunerii. Deci știm că această stare are componente Fourier ale căror faze se potrivesc în același mod: cele care au o deplasare de fază de 0 între termenul |0000> și termenul |1000>. Fiecare stare din baza Fourier $|\phi_y\rangle$ este compusă din termeni a căror fază se acumulează cu o rată de $2\pi y/N$, adică, ordonați în modul obișnuit, fiecare termen din superpunere are o fază cu $2\pi y/N$ mai mare decât termenul precedent. Deci, la jumătatea drumului $N/2$, vrem ca faza $2\pi y/N * N/2$ să fie un multiplu întreg al lui $2\pi$. Acest lucru se întâmplă când $y$ este par.

Ce superpunere de stări computaționale ar corespunde unui QFT cu vârfuri pe fiecare număr binar impar?

Răspuns:

Dacă ai aplica QFT-ul stării $\psi = |0\rangle - |N/2\rangle$, ai vedea vârfuri pe fiecare stare cu număr binar impar.

Descompunerea algoritmului QFT

Acum că am căpătat mai multă intuiție despre relația dintre stările Qubit din baza computațională și baza Fourier, haideți să aprofundăm algoritmul QFT în sine. Cu alte cuvinte, ce Gate-uri implementăm efectiv pe calculatorul cuantic pentru a realiza această transformare?

Să începem cu ceva simplu, cu un singur Qubit. Asta înseamnă că vom avea două stări de bază. QFT$_2$ transformă stările din baza computațională $|0\rangle$ și $|1\rangle$ în stările din baza Fourier $\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)$

Verifică-ți înțelegerea

Citește întrebarea (întrebările) de mai jos, gândește-te la răspuns, apoi apasă pe triunghi pentru a dezvălui soluția.

Folosește ecuația pentru QFT din secțiunea anterioară pentru a verifica cele două stări ale bazei Fourier de mai sus.

Răspuns:

Formula generală a QFT este:

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

Pentru un singur Qubit ($n=1$), $N=2^n=2$, și $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$. Astfel, avem

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

Aruncă o privire la acele două ecuații. Poate că știi deja ce Gate cuantic poate fi folosit pentru a implementa această transformată. Adică există un Gate care transformă stările bazei computaționale $|0\rangle$ și $|1\rangle$ în stările respective ale bazei Fourier $|\phi_0\rangle$ și $|\phi_1\rangle$. Este un Gate Hadamard! Acest lucru devine și mai clar dacă introducem o reprezentare matriceală a operației 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$

Dacă nu ești familiarizat cu această notație pentru exprimarea unui operator cuantic, nu-i bai! Este o modalitate de a reprezenta o matrice $N \times N$, unde $x$ și $y$ indexează coloanele și rândurile matricei, de la $0$ la $N-1$, iar $\omega_N^{xy}$ este valoarea acelei intrări particulare. Astfel, intrarea din coloana 0 și rândul 2, de exemplu, ar fi $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

În această reprezentare, fiecare stare a bazei computaționale este asociată cu unul dintre vectorii bazei:

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

Dacă dorești să înveți mai în profunzime despre această reprezentare, consultă lecția lui John Watrous despre sisteme multiple din cursul Basics of quantum information.

Să încercăm să construim matricea pentru QFT$_4$. Folosind formula de mai sus, găsim că

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

Pentru a implementa această matrice pe un calculator cuantic, va trebui să determinăm ce combinație de Gate-uri aplicate căror Qubiți ne va oferi o transformare unitară care să corespundă matricei de mai sus. Știm deja unul dintre Gate-urile necesare: Hadamard. Un alt Gate de care vom avea nevoie este Gate-ul de fază controlată, care aplică o fază relativă $\alpha$ stării Qubitului țintă, atât timp cât Qubit-ul de control se află în starea $|1\rangle$. În formă matriceală, acesta arată astfel:

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

Deoarece doar starea $|11\rangle$ este modificată, de fapt nu contează care Qubit este considerat „control" și care este „țintă." Rezultatul va fi același în ambele cazuri.

În final, vom mai avea nevoie și de câteva Gate-uri SWAP. Un Gate SWAP schimbă stările a doi Qubiți. Arată astfel:

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

Procedura pentru a construi un Circuit QFT$_{2^m}$ pe $m$ Qubiți este iterativă — mai întâi aplici QFT$_{2^{m-1}}$ pe Qubiții $1$ până la $m-1$, apoi adaugi câteva Gate-uri între Qubit-ul $0$ și ceilalți $m-1$ Qubiți. Dar pentru a aplica QFT$_{2^{m-1}}$, trebuie mai întâi să aplici QFT$_{2^{m-2}}$ pe Qubiții 2 până la $m-1$, apoi să adaugi câteva Gate-uri între Qubit-ul 1 și Qubiții rămași $2$ până la $m-1$. Este ca o păpușă matrioșcă: fiecare păpușă adaugă un factor de doi la dimensiunea Circuit-ului QFT, cea mai mică păpușă aflându-se chiar în centru, fiind QFT$_2$, sau Gate-ul Hadamard.

Pentru a introduce o păpușă în următoarea mărime mai mare, mărind astfel dimensiunea QFT cu un factor de doi, urmezi întotdeauna aceeași procedură:

1. Mai întâi, aplică QFT$_{2^{m-1}}$ pe cei $m-1$ Qubiți de la bază. Aceasta este „păpușa mai mică" din setul de matrioșcă pe care urmează să o introduci în păpușa mai mare.
2. Folosește Qubit-ul următor de deasupra ca și control și aplică Gate-uri de fază controlată fiecăruia dintre cei $m-1$ Qubiți de la bază, cu faze corespunzătoare stărilor bazei standard ale fiecăruia dintre cei $m-1$ Qubiți rămași.
3. Aplică un Hadamard pe acel Qubit de la vârf care a fost folosit ca și control în Gate-urile de fază.
4. Folosește Gate-uri SWAP pentru a permuta ordinea Qubiților, astfel încât bitul cel mai puțin semnificativ (de sus) să devină bitul cel mai semnificativ (de jos), iar toți ceilalți să se deplaseze cu unul în sus.

Am folosit deja funcția QFTGate din biblioteca de Circuit-uri Qiskit, dar acum să aruncăm o privire în interiorul câtorva dintre aceste Gate-uri QFT pentru a verifica procedura de mai sus. Putem face asta cu 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")

Sperăm că, din primele patru QFT-uri, poți începe să observi cum fiecare este imbricată în cea mai mare de dimensiune superioară. Poate ai observat, totuși, că unele dintre Gate-urile de fază nu sunt exact conform procedurii prezentate mai sus, iar SWAP-urile nu apar după fiecare subrutină, ci doar la sfârșitul QFT complet. Aceasta ne economisește Gate-uri inutile, care ar face Circuit-ul să dureze mai mult și să fie mai predispus la erori. În loc să implementeze SWAP-ul după fiecare păpușă imbricată, Circuit-ul urmărește unde ar trebui să se afle fiecare stare de Qubit și ajustează în consecință Qubiții la care aplică Gate-urile de fază. Apoi, un set final de SWAP-uri la sfârșit pune totul la locul potrivit.

Aplică QFT: Estimarea fazei

Să vedem cum poate fi folosit QFT pentru a rezolva o problemă utilă în calculul cuantic. Calculul transformatei cuantice Fourier inverse este un pas necesar într-un algoritm cunoscut sub denumirea de Estimare Cuantică a Fazei (QPE), care este ea însăși o subrutină în multe alte algoritme, inclusiv în „bijuteria de coroană" a algoritmelor cuantice, algoritmul de factorizare al lui Shor.

Scopul QPE este de a estima valorile proprii ale unui operator unitar. Operatorii unitari sunt omniprezenti în calculul cuantic și, adesea, găsirea valorilor proprii ale vectorilor proprii asociați este un pas necesar într-un algoritm mai amplu. În funcție de problemă, o valoare proprie poate reprezenta energia unui Hamiltonian într-o problemă de tip simulare, ne poate ajuta să găsim factorii primi ai unui număr în algoritmul lui Shor sau poate conține alte informații esențiale. QPE este una dintre cele mai importante și mai utilizate subrutine din calculul cuantic.

Deci, ce legătură are aceasta cu o transformată cuantică Fourier? Ei bine, după cum poate îți amintești, orice valoare proprie $\lambda$ a unui operator unitar are magnitudinea $|\lambda| = 1$. Deci putem scrie fiecare valoare proprie ca un număr complex cu magnitudinea unu:

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

unde $\theta$ este un număr real între 0 și 1. Dacă dorești mai multe informații despre matricele unitare, vezi lecția lui John Watrous pe acest subiect în Basics of quantum information.

Observă că $\lambda$ este periodic în $\theta$. Deja, aceasta îți poate sugera că ar putea fi implicat un QFT, deoarece am văzut cât de utile sunt QFT-urile pentru analiza funcțiilor periodice. Mai jos, vom parcurge algoritmul și vom vedea exact cum intervine QFT-ul.

Cum funcționează QPE

Mai întâi, vom începe cu cel mai simplu algoritm QPE, care estimează aproximativ faza la un singur digit binar de precizie. Cu alte cuvinte, acest algoritm poate distinge între $\theta = 0$ și $\theta = 1/2$, dar nu poate face mai bine de atât. Iată diagrama Circuit-ului:

Qubiții sunt pregătiți în starea $|\pi_0\rangle = |\psi\rangle|0\rangle$, unde Qubit-ul $0$ se află în starea $|0\rangle$, iar Qubiții rămași se află în starea $|\psi\rangle$, care este o stare proprie a lui $U$. După primul Hadamard, starea Qubiților devine:

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

Următorul Gate este un Gate „controlled-$U$". Acesta aplică operația unitară $U$ Qubiților de jos care se află în starea $|\psi\rangle$ dacă Qubit-ul 0 se află în starea $|1\rangle$, dar nu face nimic față de $|\psi\rangle$ dacă Qubit-ul 0 se află în starea $|0\rangle$. Aceasta transformă Qubiții în starea:

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

Tocmai s-a întâmplat ceva ciudat: Gate-ul controlled-$U$ folosește doar Qubit-ul $0$ ca Qubit de control, deci s-ar putea crede că acest Gate nu ar schimba deloc starea Qubit-ului 0. Totuși, o face! Chiar dacă operația a fost aplicată Qubiților de jos, efectul general al Gate-ului este de a schimba faza Qubit-ului $0$. Acesta este cunoscut sub denumirea de „mecanismul de phase kickback" și este folosit în multe algoritme cuantice, inclusiv algoritmele Deutsch-Josza și Grover. Dacă dorești să afli mai multe despre mecanismul de phase kickback, vezi lecția lui John Watrous despre Algoritme de interogare cuantică din Fundamentals of quantum algorithms.

După phase kickback, aplicăm încă un Hadamard Qubit-ului $0$, ceea ce duce la starea:

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

Deci, când măsurăm Qubit-ul $0$ la final, vom măsura $|0\rangle$ cu certitudine 100% dacă $\theta = 0$ și vom măsura $|1\rangle$ cu certitudine 100% dacă $\theta = \frac{1}{2}$ (și dacă calculatorul nostru cuantic este perfect, fără zgomot). Dacă $\theta$ este altceva, măsurătoarea finală este doar probabilistică și ne spune doar atât.

QPE cu mai multă precizie: mai mulți Qubiți

Putem extinde acest concept simplu la un algoritm mai complex cu precizie arbitrară. Dacă, în loc să folosim doar Qubit-ul $0$ pentru a măsura faza, folosim $m$ Qubiți de la $0$ la $m-1$, vom putea estima faza cu $m$ biți de precizie. Să vedem cum funcționează:

Acest Circuit QPE mai precis începe la fel ca versiunea cu un singur bit: Hadamard-urile sunt aplicate primilor $m$ Qubiți, iar Qubiții rămași sunt pregătiți în starea $|\psi\rangle$, creând starea:

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

Acum, unitarele controlate sunt aplicate. Qubit-ul $0$ este controlul pentru același unitar $U$ ca înainte. Dar acum, Qubit-ul $1$ este controlul pentru unitarul $U^2$, care este pur și simplu $U$ aplicat de două ori. Astfel, valoarea proprie a lui $U^2$ este $e^{2*2\pi i \theta}$. În general, fiecare Qubit $k$ de la 0 la $m-1$ va fi controlul pentru unitarul $U^{2^k}$. Aceasta înseamnă că fiecare dintre acești Qubiți va experimenta un phase kickback de $e^{2^k*2\pi i \theta}$. Rezultă starea:

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

Aceasta poate fi rescrisă ca o sumă peste stările bazei computaționale:

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

Suma îți pare familiară? Este un QFT! Reamintește-ți ecuația pentru o transformată cuantică Fourier:

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

Deci, dacă faza $\theta = y/2^m$ pentru un număr întreg $y$ între $0$ și $2^m-1$, atunci aplicând QFT-ul invers acestei stări vom obține starea:

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

și din $|y\rangle$, putem deduce $\theta$.

Dacă $\theta/2^m$ nu este un multiplu întreg, totuși, atunci aplicând QFT-ul invers vom aproxima doar $\theta$. Cât de bine aproximează $\theta$ va fi probabilistic, adică nu vom obține întotdeauna cea mai bună aproximare, dar va fi destul de aproape, iar cu cât mai mulți Qubiți $m$ folosești, cu atât mai bună va fi aproximarea. Pentru a afla cum se cuantifică această aproximare a lui $\theta$, consultă lecția lui John Watrous despre Estimarea fazei și factorizare din Fundamentals of quantum algorithms.

Concluzie

Acest modul a oferit o prezentare generală a ce este un QFT, cum este implementat pe un calculator cuantic și cât de util poate fi în rezolvarea problemelor. Ți-am oferit o idee despre utilitatea sa când am văzut cum poate fi folosit în estimarea cuantică a fazei pentru a afla informații despre valorile proprii ale unei matrice unitare.

Concepte critice

• Transformata Fourier Cuantică este analogul cuantic al Transformatei Fourier Discrete.
• QFT este un exemplu de transformare a bazei.
• Procedura de Estimare Cuantică a Fazei se bazează pe mecanismul de retroacțiune a fazei din operațiile unitare controlate, precum și pe o QFT inversă.
• QFT și QPE sunt ambele subrutine utilizate pe scară largă în numeroși algoritmi cuantici.

Întrebări

Adevărat/Fals

1. A/F Transformata Fourier Cuantică este analogul cuantic al transformatei Fourier discrete clasice (DFT).
2. A/F QFT poate fi implementată folosind doar porți Hadamard și CNOT.
3. A/F QFT este o componentă esențială a algoritmului lui Shor.
4. A/F Rezultatul Estimării Cuantice a Fazei este o stare cuantică ce reprezintă vectorul propriu al operatorului.
5. A/F QPE necesită utilizarea Transformatei Fourier Cuantice inverse (QFT$^\dag$).
6. A/F În QPE, dacă faza $\phi$ este reprezentabilă exact cu $n$ biți, algoritmul dă rezultatul corect cu probabilitatea 1.

Răspunsuri scurte

1. Câți qubiți sunt necesari pentru a efectua o QFT pe un sistem cu $2^n$ puncte de date?
2. Poate fi utilizată QFT pe o stare care nu este o stare de bază computațională? Dacă da, ce se întâmplă?
3. Cum influențează numărul de qubiți de control utilizați în QPE rezoluția estimării fazei rezultate?

Probleme

1. Folosește înmulțirea matriceală pentru a verifica că pașii algoritmului QFT conduc într-adevăr la matricea $\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}$$

(Nu trebuie să faci asta manual!)

Probleme de provocare

1. Creează o stare cu patru qubiți care să fie o superpoziție egală a tuturor bazelor computaționale impare: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. Apoi efectuează o QFT pe stare. Care este starea rezultată? Explică de ce rezultatul tău are sens, folosind cunoștințele tale despre transformatele Fourier.