Algoritmi cuantici: Estimarea fazei

notă

Kento Ueda (15 mai 2024)

Acest notebook prezintă conceptele fundamentale și implementarea Transformatei Fourier Cuantice (QFT) și a Estimării Fazei Cuantice (QPE).

Descarcă PDF-ul al cursului original. Reține că unele fragmente de cod pot deveni depreciate, deoarece acestea sunt imagini statice.

Timpul estimat QPU pentru a rula acest experiment este de 7 secunde.

1. Introducere

Transformata Fourier Cuantică (QFT)

Transformata Fourier Cuantică este echivalentul cuantic al transformatei Fourier discrete clasice. Este o transformare liniară aplicată stărilor cuantice, care mapează bazele computaționale în reprezentările lor în baza Fourier. QFT joacă un rol esențial în mulți algoritmi cuantici, oferind o metodă eficientă de extragere a informațiilor de periodicitate din stările cuantice. QFT poate fi implementată cu $O(N^2)$ operații folosind Gate-uri cuantice precum Gate-urile Hadamard și Gate-urile de Fază Controlată pentru $N$ qubiți, permițând o accelerare exponențială față de transformata Fourier clasică.

• Aplicații: Este o componentă fundamentală în algoritmi cuantici precum algoritmul lui Shor pentru factorizarea numerelor întregi mari și logaritmul discret.

Estimarea Fazei Cuantice (QPE)

Estimarea Fazei Cuantice este un algoritm cuantic utilizat pentru estimarea fazei asociate unui eigenvector al unui operator unitar. Acest algoritm oferă o punte între proprietățile matematice abstracte ale stărilor cuantice și aplicațiile lor computaționale.

• Aplicații: Poate rezolva probleme precum găsirea valorilor proprii ale matricelor unitare și simularea sistemelor cuantice.

Împreună, QFT și QPE formează coloana vertebrală esențială a multor algoritmi cuantici care rezolvă probleme imposibil de abordat pentru calculatoarele clasice. La finalul acestui notebook, vei dobândi o înțelegere a modului în care aceste tehnici sunt implementate.

2. Bazele Transformatei Fourier Cuantice (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

Prin analogie cu transformata Fourier discretă, QFT acționează asupra unui stări cuantice $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$ pentru $N$ qubiți și o mapează la starea cuantică $\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$$

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

Sau reprezentarea matricei unitare:

$$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. Intuiție

Transformata Fourier cuantică (QFT) face conversia între două baze: baza computațională (Z) și baza Fourier. Dar ce înseamnă baza Fourier în acest context? Probabil îți amintești că transformata Fourier $F(\omega)$ a unei funcții $f(x)$ descrie convoluția lui $f(x)$ pe o funcție sinusoidală cu frecvența $\omega$. Pe înțelesul tuturor: transformata Fourier este o funcție care descrie cât din fiecare frecvență $\omega$ ar trebui să folosim pentru a construi o funcție $f(x)$ din funcții sinus (sau cosinus). Pentru a înțelege mai bine ce înseamnă QFT în acest context, privește imaginile de mai jos, care arată un număr codificat în binar, folosind patru qubiți:

În baza computațională, stocăm numerele în binar folosind stările $|0\rangle$ și $|1\rangle$.

Observă frecvența cu care diferiți qubiți se schimbă; qubit-ul din stânga se inversează la fiecare increment al numărului, următorul la fiecare 2 incremente, al treilea la fiecare 4 incremente și tot așa mai departe.

Dacă aplicăm o transformată Fourier cuantică acestor stări, mapăm

$$|\text{Stare în Baza Computațională}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{Stare în Baza Fourier}\rangle$$ $$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$

(Deseori notăm stările în baza Fourier folosind tilda (~)).

În baza Fourier, stocăm numerele folosind diferite rotații în jurul axei Z:

IFRAME

Numărul pe care vrem să-l stocăm dictează unghiul la care fiecare qubit este rotit în jurul axei Z. În starea $|\widetilde{0}\rangle$, toți qubiții sunt în starea $|{+}\rangle$. Cum se vede în exemplul de mai sus, pentru a codifica starea $|\widetilde{5}\rangle$ pe 4 qubiți, am rotit qubit-ul din stânga cu $\tfrac{5}{2^n} = \tfrac{5}{16}$ ture complete ($\tfrac{5}{16}\times 2\pi$ radiani). Următorul qubit este rotit de două ori mai mult ($\tfrac{10}{16}\times 2\pi$ radiani, sau $10/16$ ture complete), acest unghi se dublează pentru qubit-ul următor și tot așa.

Din nou, observă frecvența cu care fiecare qubit se schimbă. Qubit-ul din stânga (qubit 0) în acest caz are frecvența cea mai mică, iar cel din dreapta frecvența cea mai mare.

2.2 Exemplu: QFT cu 1 qubit

Să considerăm cazul $N = 2^1 = 2$.

Matricea unitară poate fi scrisă:

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

Această operație este rezultatul aplicării Gate-ului Hadamard ($H$).

2.3 Reprezentarea ca produs a QFT

Să generalizăm o transformare pentru $N = 2^n$, $QFT_{N}$ acționând asupra stării $\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{deoarece}\: \omega_N^{xy} = e^{2\pi i \frac{xy}{N}} \:\text{și}\: 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{rescriind în notație binară fracționară}\: 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{după expandarea exponențialei unei sume ca produs de exponențiale,} \\ & = \frac{1}{\sqrt{N}} \bigotimes_{k=1}^n \left(\vert0\rangle + e^{2 \pi i x /2^k } \vert1\rangle \right) \:\text{după rearanjarea sumei și produselor, și expandarea} \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 Exemplu: Construcția Circuit-ului QFT cu 3 qubiți

Din descrierea de mai sus, s-ar putea să nu fie clar cum să construiești un circuit QFT. Pentru moment, reține doar că ne așteptăm ca cei trei qubiți să aibă faze care evoluează cu „viteze" diferite. Înțelegerea exactă a modului în care aceasta se traduce într-un Circuit este lăsată ca exercițiu pentru cititor. Există mai multe diagrame și exemple în PDF-ul cursului. Resurse suplimentare includ această lecție din cursul Fundamentele algoritmilor cuantici.

Vom demonstra QFT folosind doar simulatoare și, prin urmare, nu vom folosi framework-ul Qiskit patterns până când nu trecem la estimarea fazei cuantice.

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

Încercăm să aplicăm QFT pe $|5\rangle$ ca exemplu.

Mai întâi, confirmăm notația binară a numărului întreg 5 și creăm Circuit-ul care codifică starea 5:

bin(5)

'0b101'

qc = QuantumCircuit(3)

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

Verificăm stările cuantice folosind simulatorul Aer:

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

În final, adăugăm QFT și vizualizăm starea finală a qubiților noștri:

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)

Putem vedea că funcția noastră QFT a funcționat corect. Qubit 0 a fost rotit cu $\tfrac{5}{8}$ dintr-o tură completă, qubit 1 cu $\tfrac{10}{8}$ ture complete (echivalent cu $\tfrac{1}{4}$ dintr-o tură completă), iar qubit 2 cu $\tfrac{20}{8}$ ture complete (echivalent cu $\tfrac{1}{2}$ dintr-o tură completă).

2.5 Exercițiu: QFT

(1) Implementează QFT cu 4 qubiți.

##your code goes here##

(2) Aplică QFT pe $|14\rangle$, simulează și trasează vectorul de stare folosind sfera Bloch.

##your code goes here##

Soluția exercițiului: 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. Bazele Estimării Fazei Cuantice (QPE)

Dat fiind o operație unitară $U$, QPE estimează $\theta$ în $U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$, deoarece $U$ este unitar, toate valorile sale proprii au norma 1.

3.1 Procedură

1. Configurare

$\vert\psi\rangle$ se află într-un set de registre de qubiți. Un set suplimentar de $n$ qubiți formează registrul de numărare în care vom stoca valoarea $2^n\theta$:

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

2. Suprapunere

Aplică o operație Hadamard de $n$ biți $H^{\otimes n}$ pe registrul de numărare:

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

3. Operații unitare controlate

Trebuie să introducem unitarul controlat $CU$ care aplică operatorul unitar $U$ pe registrul țintă numai dacă bitul de control corespunzător este $|1\rangle$. Deoarece $U$ este un operator unitar cu eigenvectorul $|\psi\rangle$ astfel încât $U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$, aceasta înseamnă:

$$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 Exemplu: QPE cu Gate-ul T

Să folosim Gate-ul $T$ ca exemplu de QPE și să estimăm faza sa $\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$$

Ne așteptăm să găsim:

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

unde

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

Inițializăm $\vert\psi\rangle = \vert1\rangle$ al eigenvectorului Gate-ului $T$ aplicând un poartă $X$:

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

Apoi, aplicăm Gate-uri Hadamard pe qubiții de numărare:

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

Efectuăm operațiile unitare controlate:

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

Aplicăm transformata Fourier cuantică inversă pentru a converti starea registrului de numărare, apoi măsurăm registrul de numărare:

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

Putem simula folosind simulatorul 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)

Vedem că obținem un singur rezultat (001) cu certitudine, care se traduce în zecimal: 1. Acum trebuie să împărțim rezultatul nostru (1) la $2^n$ pentru a obține $\theta$:

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

Algoritmul lui Shor ne permite să factorizăm un număr construind un circuit cu $\theta$ necunoscut și obținând $\theta$.

3.3 Exercițiu

Estimează $\theta = 1/3$ folosind 3 qubiți pentru numărare și un qubit pentru un eigenvector.

$P|1\rangle = e^{i\lambda}|1\rangle$. Deoarece vrem să implementăm $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$, trebuie să setăm $\lambda = \tfrac{2 \pi}{3}$.

##your code goes here##

Soluția exercițiului: $\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. Execuție folosind primitiva Qiskit Runtime Sampler

Vom efectua QPE folosind un dispozitiv cuantic real și vom urma cei 4 pași ai pattern-urilor Qiskit.

1. Mapează problema într-un format nativ cuantic
2. Optimizează Circuit-urile
3. Execută Circuit-ul țintă
4. Post-procesează rezultatele

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler

# Loading your IBM Quantum® account(s)

service = QiskitRuntimeService()

4.1 Pasul 1: Maparea problemei în Circuit-uri cuantice și operatori

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 Pasul 2: Optimizarea pentru hardware-ul țintă

# 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 Pasul 3: Execuție pe hardware-ul țintă

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 Pasul 4: Post-procesarea rezultatelor

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'