Quantum Fourier transform

Para sa Qiskit in Classrooms module na ito, kailangan ng mga estudyante ng gumaganang Python environment na may mga sumusunod na naka-install na package:

• qiskit v2.1.0 o mas bago
• qiskit-ibm-runtime v0.40.1 o mas bago
• qiskit-aer v0.17.0 o mas bago
• qiskit.visualization
• numpy
• pylatexenc

Para i-set up at i-install ang mga package sa itaas, tingnan ang gabay na I-install ang Qiskit. Para makapagpatakbo ng mga job sa tunay na quantum computer, kailangan ng mga estudyante na mag-set up ng account sa IBM Quantum® sa pamamagitan ng pagsunod sa mga hakbang sa gabay na I-set up ang iyong IBM Cloud account.

Ang module na ito ay nasubok at gumamit ng 13 segundo ng oras ng QPU. Ito ay isang magandang-loob na pagtatantya; ang iyong aktwal na paggamit ay maaaring mag-iba.

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

Panimula

Ang Fourier transform ay isang ubiquitous na kasangkapan na may mga aplikasyon sa matematika, pisika, signal processing, data compression, at napakaraming iba pang larangan. Ang quantum na bersyon ng Fourier transform, na angkop na pinangalanang quantum Fourier transform, ang pundasyon ng ilan sa mga pinakamahalagang quantum algorithm.

Ngayon, pagkatapos ng isang paalala tungkol sa klasikal na Fourier transform, pag-uusapan natin kung paano natin isinasagawa ang quantum Fourier transform sa isang quantum computer. Pagkatapos, tatalakayin natin ang isa sa mga aplikasyon ng quantum Fourier transform sa isang algorithm na tinatawag na phase estimation algorithm. Ang quantum phase estimation ay isang subroutine sa sikat na factoring algorithm ni Shor, na kung minsan ay tinutukoy bilang "crown jewel" ng quantum computing. Ang module na ito ay nagtatayo patungo sa isa pang module tungkol sa Shor's algorithm, ngunit nilalayon din itong maging nagsasarili. Ang quantum Fourier transform ay isang kahanga-hangang at kapaki-pakinabang na algorithm sa sarili nito!

Ang klasikal na Fourier transform

Bago tayo sumabak sa quantum Fourier transform, unahin nating alalahanin ang klasikal na bersyon. Ang Fourier transform ay isang paraan ng pag-transform mula sa isang tinatawag na "basis" patungo sa isa pa. Maaari mong isipin ang dalawang basis bilang iba't ibang pananaw ng parehong problema — parehong may bisa na paraan upang ipahayag ang isang function, ngunit ang isa o ang isa pa ay maaaring mas kapaki-pakinabang, depende sa problemang nararapit. Ilang halimbawa ng mga pares ng basis na konektado ng Fourier transform ay posisyon at momentum, at oras at dalas.

Tingnan natin ang isang halimbawa kung paano ang Fourier transform ay makakatulong sa atin na malaman kung anong nota ang tinutugtog ng isang instrumento batay sa audio waveform nito. Karaniwan, nakikita natin ang mga waveform na kinakatawan sa time basis — iyon ay, ang amplitude ng alon ay ipinahahayag bilang isang function ng oras.

Maaari tayong mag-Fourier transform ng waveform na ito para lumipat mula sa time basis patungo sa frequency basis:

Sa frequency basis, madali tayong makakakita ng malinaw na tuktok sa humigit-kumulang 260 Hz. Iyon ay isang middle C!

Ngayon, maaaring nagawa mong matukoy na ang isang middle C ay tinutugtog nang hindi gumagamit ng Fourier transform, ngunit paano kung maraming nota ang tinutugtog nang sabay-sabay? Ang waveform ay nagiging mas kumplikado kapag ini-plot natin ito sa time basis:

Ngunit ang frequency spectrum ay malinaw na nagtatukoy ng tatlong tuktok:

Ito ay isang C-major chord, na tumutugtog ng mga nota C, E, at G.

Ang ganitong uri ng Fourier analysis ay makakatulong sa atin na kunin ang mga frequency component ng anumang uri ng kumplikadong signal.

Discrete Fourier transform

Ang Fourier transform ay kapaki-pakinabang para sa anumang bilang ng mga aplikasyon sa signal-processing. Ngunit sa karamihan ng mga totoong aplikasyon na ito (kasama ang halimbawa ng musika na ginamit natin sa itaas), gusto nating i-transform ang isang discrete na hanay ng $N$ data points — hindi isang tuloy-tuloy na function. Sa kasong ito, ginagamit natin ang discrete Fourier transform. Ang discrete Fourier transform (DFT) ay kumikilos sa isang vector $(x_0, ..., x_{N-1})$ at ini-map ito sa vector $(y_0, ..., y_{N-1})$ ayon sa formula:

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

kung saan kinukuha natin ang $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$. (Tandaan na may iba pang mga convention na may negatibong tanda sa exponential, kaya mag-ingat kapag nakita mo ang DFT sa labas.) Alalahanin na ang $e^{2\pi i \frac{jk}{N}}$ ay isang periodic na function, na may period na $\frac{N}{k}$. Kaya, sa pamamagitan ng pagpaparami ng function na ito, ang Fourier transform ay essentially isang paraan upang masira ang (discrete) function na $\{x_{j}\}$ sa isang linear na kumbinasyon ng mga bumubuo nitong periodic na function, bawat isa ay may period na $\frac{N}{k}$.

Ang quantum Fourier transform

Kaya ngayon, nakita na natin kung paano ginagamit ang Fourier transform upang kumatawan sa isang function bilang isang linear na kumbinasyon ng isang bagong hanay ng tinatawag na "basis functions." Ang mga basis transformation ay regular na ginagawa rin sa mga estado ng Qubit. Halimbawa, ang estado ng isang solong Qubit $|\psi\rangle$ ay maaaring ipahayag sa computational basis $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$, na may mga basis state na $|0\rangle$ at $|1\rangle$, o sa $X$ basis $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ na may mga basis state na $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ at $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$. Parehong may pantay na bisa, ngunit ang isa ay maaaring mas natural kaysa sa isa, depende sa uri ng problemang sinusubukan mong lutasin.

Ang mga estado ng Qubit ay maaari ring ipahayag sa Fourier basis kung saan ang isang estado ay ipinahahayag sa mga tuntunin ng isang linear na kumbinasyon ng mga Fourier basis state na $|\phi_y\rangle$, sa halip na ang karaniwang mga computational basis state na $|x\rangle$. Upang magawa ito, kailangan mong mag-apply ng quantum Fourier transform (QFT):

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

na may $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$ tulad ng nasa itaas, at $N$ ang bilang ng mga basis state sa iyong quantum system. Tandaan na, dahil nagtatrabaho tayo ngayon sa mga Qubit, ang $m$ Qubit ay nagbibigay sa iyo ng $2^m$ na mga basis state, kaya $N=2^m$. Dito, ang mga basis state ay nakasulat bilang isang solong numero $|x\rangle$ kung saan ang $x$ ay umaabot mula $0$ hanggang $N-1$, ngunit mas madalas mong makikita ang mga basis state na ipinahahayag bilang $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$, ..., $|11...11\rangle$, kung saan ang bawat binary digit ay kumakatawan sa estado ng Qubit 0 hanggang $m-1$, mula kanan hanggang kaliwa. May madaling paraan upang i-convert ang mga binary state na ito sa isang solong numero: ituring lamang silang mga binary number! Kaya, $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$, at iba pa, hanggang sa $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$.

Bumuo ng intuition para sa mga Fourier basis state

Kaya, napag-usapan na natin kung ano ang mga computational basis state at kung paano sila inayos: sila ang hanay ng mga estado kung saan ang bawat Qubit ay nasa $0$ o $1$, at inayos natin sila mula sa estado kung saan ang lahat ng Qubit ay $0$, $|00...00\rangle$, hanggang sa estado kung saan ang lahat ay $1$, $|11...11\rangle$.

Ngunit paano natin mauunawaan ang mga Fourier basis state? Lahat ng Fourier basis state ay magkaparehong superposition ng lahat ng computational basis state, ngunit ang bawat estado ay naiiba sa isa pa sa periodicity ng phase ng mga component. Upang maunawaan ito nang mas kongkreto, tingnan natin ang apat na Fourier basis state ng isang two-Qubit system. Ang pinakamababang Fourier state ay ang isa na ang phase ay hindi nagbabago:

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

Maaari nating i-visualize ang estado na ito sa pamamagitan ng pag-plot ng complex amplitude ng bawat isa sa mga term. Ang pulang linya ay nagbibigay-gabay sa mata upang ipakita sa iyo kung paano ang phase ng amplitude na ito ay nagpapaikot sa paligid ng complex plane bilang isang function ng computational basis state. Para sa $|\phi_0\rangle$, ang phase ay nananatiling constant:

Ang susunod na Fourier basis state ay ang isa na ang mga phase ng mga component ay nagpapaikot mula $0$ hanggang $2\pi$ nang isang beses lamang:

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

At makikita natin ang pag-ikot na ito sa plot ng complex amplitude versus computational basis state:

Kaya, ang bawat estado ay may phase na $2\pi/4$ radians na mas mataas kaysa sa estado bago ito kapag inayos sila sa karaniwang paraan, dahil sa halimbawang ito ay mayroon tayong apat na basis state ($N=4$). Ang susunod na basis state ay nagpapaikot mula 0 hanggang $2\pi$ nang dalawang beses:

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

Sa wakas, ang pinakamataas na Fourier component ay ang isa na may pinakamabilis na nagbabagong phase. Para sa ating halimbawa na may dalawang Qubit, ito ang isa na ang mga phase ay nagpapaikot mula 0 hanggang $2\pi$ nang tatlong beses:

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

Sa pangkalahatan, para sa isang $m$-Qubit na estado, magkakaroon ng $2^m$ Fourier basis state, na ang dalas ng pagbabago ng phase ay umaabot mula sa constant, para sa $|\phi_0\rangle$, hanggang sa mabilis na nagbabago para sa $|\phi_{2^m-1}\rangle$, kumukumpleto ng $2^m-1$ na pag-ikot sa paligid ng $2\pi$ sa superposition ng mga estado. Kaya, kapag kinukuha natin ang QFT ng isang quantum state, essentially ginagawa natin ang parehong pangunahing pagsusuri na ginawa natin para sa musical waveform sa Panimula. Tinutukoy natin ang mga Fourier frequency component na nag-aambag sa paglikha ng quantum state ng interes.

Subukan ang ilang halimbawang QFT

Subukan nating patuloy na buuin ang ating intuition para sa quantum Fourier transform sa pamamagitan ng paggawa ng isang estado sa computational basis, at pagkatapos ay tingnan kung ano ang mangyayari kapag inilapat natin ang QFT dito. Sa ngayon, ituring nating isang black box ang QFT na inilalapat natin gamit ang QFTGate mula sa Qiskit circuit library. Mamaya, titingnan natin ang loob nito upang makita kung paano ito isinasagawa.

Sisimulan natin sa pamamagitan ng pag-load ng mga kinakailangang package at pagpili ng isang device para patakbuhin ang ating Circuit:

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

# Load the Qiskit Runtime service
from qiskit_ibm_runtime import QiskitRuntimeService

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

service = QiskitRuntimeService()

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

print(backend.name)

ibm_pinguino2

Kung wala kang available na oras sa iyong account o nais gumamit ng simulator sa anumang dahilan, maaari mong patakbuhin ang cell sa ibaba para mag-set up ng simulator na magpapalita ng quantum device na pinili natin sa itaas:

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

Isang computational basis state

Una, subukan nating i-transform ang isang solong computational basis state. Sisimulan natin sa paggawa ng isang random na computational state:

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

Ngayon, i-Fourier transform natin ang estado na ito gamit ang 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)

Tulad ng makikita mo, sinusukat natin ang mga populasyon ng bawat estado na halos pantay, may kaunting experimental at statistical na ingay. Kaya, kung kukuha ka ng QFT ng isang solong computational basis state, ang resulta ay isang pantay na superposition ng lahat ng estado. Kung pamilyar ka sa Fourier transform, hindi ka malamang magugulat dito. Ang isang pangunahing prinsipyo na makakatulong sa atin na bumuo ng intuitive na koneksyon sa pagitan ng isang function at ng Fourier transform nito ay ang lapad ng isang function ay inversely proportional sa lapad ng Fourier transform nito. Kaya, ang isang bagay na napaka-localized sa oras, halimbawa, tulad ng isang napakaikling pulse, ay mangangailangan ng malawak na hanay ng mga dalas upang mabuo ang pulse na iyon. Ang signal na iyon ay magiging napakalalim sa Fourier space.

Ang katotohanang ito ay talagang may kaugnayan sa quantum uncertainty! Ang uncertainty principle ni Heisenberg ay karaniwang isinasaad bilang $\Delta x \Delta p \ge \hbar / 2$. Kaya kung ang uncertainty sa $x$ ($\Delta x$) ay maliit, ang uncertainty sa momentum ($\Delta p$) ay kailangang malaki, at vice versa. Lumalabas na ang pag-transform mula sa position basis $x$ patungo sa momentum basis $p$ ay nagagawa sa pamamagitan ng Fourier transform.

Tandaan: Huwag kalimutan, sinusukat natin ang mga populasyon sa bawat isa sa mga basis state, kaya nawawala ang impormasyon tungkol sa mga kamag-anak na phase sa pagitan ng iba't ibang bahagi ng superposition. Kaya, habang ang QFT ng anumang solong computational basis state ay magbubunga ng parehong pantay na pagkalat ng populasyon sa lahat ng basis state, ang mga phase ay hindi kinakailangang magiging pareho.

Dalawang computational basis state

Ngayon, tingnan natin kung ano ang mangyayari kapag naghanda tayo ng superposition ng mga computational basis state. Ano sa tingin mo ang hitsura ng Fourier transform sa kasong ito?

Piliin natin ang superposition:

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

Ngayon, i-Fourier transform natin ang estado na ito gamit ang 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)

Ang isa na ito ay maaaring medyo mas nakakagulat. Mukhang ang QFT ng estado $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ ay isang superposition ng lahat ng even basis state. Ngunit kung iisipin natin muli ang ating visualization ng bawat basis state na $|\phi_y\rangle$, at kung paano ang phase ng bawat component ay nagpapaikot ng $2\pi$ ng $y$ beses, ang dahilan kung bakit nakuha natin ang resultang ito ay maaaring maging malinaw.

Suriin ang iyong pag-unawa

Basahin ang mga tanong sa ibaba, pag-isipan ang iyong sagot, pagkatapos ay i-click ang tatsulok upang makita ang solusyon.

Gamit ang pahiwatig sa itaas, ipaliwanag kung bakit ang resulta na nakuha natin para sa QFT ng $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ ay inaasahan.

Sagot:

Ang orihinal na estado ay may kamag-anak na phase na 0 (o isang integer multiple ng $2\pi$) sa pagitan ng dalawang bahagi ng superposition. Kaya, alam natin na ang estado na ito ay may mga Fourier component na ang mga phase ay tumutugma rin sa paraang iyon: ang mga may 0 na phase shift sa pagitan ng |0000> term at ng |1000> term. Ang bawat Fourier basis state na $|\phi_y\rangle$ ay binubuo ng mga term na ang phase ay nag-aakumula sa rate na $2\pi y/N$, ibig sabihin, kapag inayos sa karaniwang paraan, ang bawat term sa superposition ay may phase na $2\pi y/N$ na mas mataas kaysa sa term na nauna. Kaya, sa kalagitnaan $N/2$, gusto nating ang phase na $2\pi y/N * N/2$ ay maging isang integer multiple ng $2\pi$. Nangyayari ito kapag ang $y$ ay even.

Anong superposition ng computational state ang tutugma sa isang QFT na may mga tuktok sa bawat kakaibang binary number?

Sagot:

Kung kukuha ka ng QFT ng estado $\psi = |0\rangle - |N/2\rangle$, makakakita ka ng mga tuktok sa bawat kakaibang binary numbered state.

Pag-aralan ang QFT algorithm

Ngayong mas naiintindihan na natin ang relasyon ng mga qubit state sa computational basis at sa Fourier basis, tuklasin na natin ang mismong QFT algorithm. Ibig sabihin, anong mga Gate ang aktwal na ginagamit sa quantum computer para makamit ang transform na ito?

Magsimula tayo sa pinakasimple: iisang qubit. Ibig sabihin, dalawa lang ang basis state. Ang QFT$_2$ ay nagko-convert ng mga computational basis state na $|0\rangle$ at $|1\rangle$ sa mga Fourier basis state na $\phi_0$ at $\phi_1$:

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

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

Subukan ang iyong pag-unawa

Basahin ang mga tanong sa ibaba, isipin ang iyong sagot, tapos i-click ang tatsulok para makita ang solusyon.

Gamitin ang equation ng QFT mula sa nakaraang seksyon para i-verify ang dalawang Fourier basis state sa itaas.

Sagot:

Ang pangkalahatang QFT formula ay:

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

Para sa iisang qubit ($n=1$), $N=2^n=2$, at $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$. Kaya, mayroon tayong

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

Tingnan mo ang dalawang equation na iyon. Maaaring alam mo na ang isang quantum Gate na magagamit para i-implement ang transform na ito. Ibig sabihin, may isang Gate na nagko-convert ng mga computational basis state na $|0\rangle$ at $|1\rangle$ sa kani-kanilang Fourier basis state na $|\phi_0\rangle$ at $|\phi_1\rangle$. Ito ay ang Hadamard gate! Nagiging mas malinaw ito kapag ipinakilala natin ang matrix representation ng operasyong 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$

Kung hindi ka pamilyar sa notasyong ito para sa pagpapahayag ng quantum operator, okay lang! Ito ay isang paraan ng paglalarawan ng isang $N \times N$ matrix, kung saan ang $x$ at $y$ ay nag-i-index ng mga column at row ng matrix, mula $0$ hanggang $N-1$, at ang $\omega_N^{xy}$ ang halaga ng partikular na entry na iyon. Kaya, ang entry sa ika-0 column at ika-2 row, halimbawa, ay magiging $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

Sa representasyong ito, ang bawat computational basis state ay nauugnay sa isa sa mga basis vector:

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

Kung nais mong matuto nang mas malalim tungkol sa representasyong ito, tingnan ang leksyon ni John Watrous tungkol sa multiple systems sa kursong Basics of quantum information.

Subukan nating buuin ang matrix para sa QFT$_4$. Gamit ang formula sa itaas, mahahanap natin na

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

Para mai-implement ang matrix na ito sa isang quantum computer, kailangan nating alamin kung anong kombinasyon ng mga Gate na inilapat sa kung aling mga qubit ang magbibigay ng unitary transformation na tugma sa matrix sa itaas. Alam na natin ang isa sa mga Gate na kakailanganin: ang Hadamard. Ang isa pang Gate na kakailanganin natin ay ang controlled-phase gate, na nag-a-apply ng relative phase na $\alpha$ sa state ng target qubit, basta nandoon ang control qubit sa state na $|1\rangle$. Sa matrix form ito ay ganito ang hitsura:

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

Dahil ang state na $|11\rangle$ lang ang binabago, hindi talaga mahalaga kung aling qubit ang itinuturing na "control" at aling qubit ang "target." Magiging pareho pa rin ang resulta.

Panghuli, kakailanganin din natin ang ilang SWAP gate. Ang SWAP gate ay nagpapalitan ng mga state ng dalawang qubit. Ganito ang hitsura nito:

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

Ang proseso ng pagbuo ng QFT$_{2^m}$ Circuit sa $m$ qubit ay paulit-ulit — unang inilalapat ang QFT$_{2^{m-1}}$ sa mga qubit $1$ hanggang $m-1$, tapos may mga Gate na idadagdag sa pagitan ng qubit $0$ at ng iba pang $m-1$ na qubit. Ngunit para ma-apply ang QFT$_{2^{m-1}}$, kailangan munang i-apply ang QFT$_{2^{m-2}}$ sa mga qubit 2 hanggang $m-1$, tapos magdagdag ng ilang Gate sa pagitan ng qubit 1 at ng mga natitirang qubit na $2$ hanggang $m-1$. Para itong Russian nesting doll: ang bawat doll ay nagdadagdag ng factor na dalawa sa dimensyon ng QFT Circuit, na ang pinakamaliit na doll sa gitna ay ang QFT$_2$, o ang Hadamard gate.

Para makapaglagay ng doll sa susunod na pinakamalaking doll, at sa gayon ay mapalaki ang dimensyon ng QFT ng isang factor na dalawa, lagi kang sumusunod sa parehong proseso:

1. Una, i-apply ang QFT$_{2^{m-1}}$ sa pinakamababang $m-1$ na qubit. Ito ang iyong "mas maliit na doll" mula sa Russian nesting doll set na malapit mo nang ilagay sa susunod na pinakamalakin.
2. Gamitin ang susunod na qubit sa itaas bilang control, at mag-apply ng mga controlled phase gate sa bawat isa sa mga pinakamababang $m-1$ na qubit, na may mga phase sa standard basis state ng bawat isa sa natitirang $m-1$ na qubit.
3. Mag-perform ng Hadamard sa parehong pinaka-itaas na qubit na ginamit bilang control sa mga phase gate.
4. Gumamit ng mga SWAP gate para baguhin ang pagkakasunod ng mga qubit, upang ang pinaka-mababa (itaas) na bit ay maging pinaka-mataas (ibaba), at ang lahat ng iba pa ay umakyat ng isa.

Nagagamit na natin ang function na QFTGate mula sa Qiskit circuit library, ngunit ngayon tingnan natin ang loob ng ilan sa mga QFT gate na ito para i-verify ang prosesong nakabalangkas sa itaas. Magagawa natin ito gamit ang 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")

Sana, mula sa unang apat na QFT, nagsisimula ka nang makita kung paano naka-nest ang bawat isa sa loob ng susunod na pinakamalaki. Maaaring napansin mo, gayunpaman, na ang ilan sa mga phase gate ay hindi eksaktong ayon sa prosesong nabalangkas natin sa itaas, at ang mga SWAP ay hindi lumalabas pagkatapos ng bawat subroutine, kundi nasa dulo lamang ng buong QFT. Nakakatipid ito ng mga hindi kinakailangang Gate, na magpapahaba ng pagpapatakbo ng Circuit at magpapalaki ng posibilidad ng error. Sa halip na i-implement ang SWAP pagkatapos ng bawat nested doll, sinisigurado ng Circuit kung saan dapat na naroroon ang bawat qubit state at iniaayos ang mga qubit kung saan nito inilalapat ang mga phase gate. Pagkatapos, ang panghuling hanay ng mga SWAP sa dulo ay naglalagay ng lahat sa tamang lugar nito.

Gamitin ang QFT: Phase estimation

Tingnan natin kung paano magagamit ang QFT para malutas ng isang kapaki-pakinabang na problema sa quantum computing. Ang pagkalkula ng inverse quantum Fourier transform ay isang kinakailangang hakbang sa isang algorithm na kilala bilang Quantum Phase Estimation (QPE), na mismong isang subroutine sa maraming iba pang algorithm, kabilang ang "crown jewel" ng mga quantum algorithm, ang factoring algorithm ni Shor.

Ang layunin ng QPE ay tantiyahin ang mga eigenvalue ng isang unitary operator. Ang mga unitary operator ay laganap sa quantum computing, at madalas, ang paghanap ng mga eigenvalue ng kanilang mga kaugnay na eigenvector ay isang kinakailangang hakbang sa isang mas malaking algorithm. Depende sa problema, ang isang eigenvalue ay maaaring kumakatawan sa enerhiya ng isang Hamiltonian sa isang simulation-type na problema, makakatulong sa atin na hanapin ang mga prime factor ng isang numero sa algorithm ni Shor, o maglaman ng iba pang mahahalagang impormasyon. Ang QPE ay isa sa mga pinakamahalaga at pinakamalawak na ginagamit na subroutine sa quantum computing.

Kaya, anong kinalaman nito sa quantum Fourier transform? Tulad ng maaari mong matandaan, ang anumang eigenvalue na $\lambda$ ng isang unitary operator ay may magnitude na $|\lambda| = 1$. Kaya maisusulat natin ang bawat eigenvalue bilang isang kumplikadong numero na may magnitude na isa:

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

kung saan ang $\theta$ ay isang tunay na numero sa pagitan ng 0 at 1. Kung nais mo ng karagdagang impormasyon tungkol sa mga unitary matrix, tingnan ang leksyon ni John Watrous sa paksa sa Basics of quantum information.

Pansinin na ang $\lambda$ ay periodic sa $\theta$. Maaari nitong ipamagkuha sa iyo na maaaring kabilang ang QFT, dahil nakita natin kung gaano kapaki-pakinabang ang mga QFT para sa pag-aanalisa ng mga periodic na function. Sa ibaba, tatahak tayo sa algorithm at makikita nang eksakto kung paano gumagalaw ang QFT.

Kung paano gumagana ang QPE

Una, magsisimula tayo sa pinakasimpleng QPE algorithm, na tinatayang tinatantiya ang phase sa isang binary digit ng katumpakan. Sa ibang salita, ang algorithm na ito ay kayang makilala ang pagkakaiba ng $\theta = 0$ at $\theta = 1/2$, ngunit hindi mahihigit sa iyon. Narito ang circuit diagram:

Ang mga qubit ay inihanda sa state na $|\pi_0\rangle = |\psi\rangle|0\rangle$, kung saan ang qubit $0$ ay nasa state na $|0\rangle$ at ang mga natitirang qubit ay nasa state na $|\psi\rangle$, na isang eigenstate ng $U$. Pagkatapos ng unang Hadamard, ang qubit state ay nagiging:

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

Ang susunod na Gate ay isang "controlled-$U$" gate. Inilalapat nito ang unitary operation na $U$ sa mga ibabang qubit na nasa state na $|\psi\rangle$ kung ang qubit 0 ay nasa state na $|1\rangle$, ngunit walang ginagawa sa $|\psi\rangle$ kung ang qubit 0 ay nasa state na $|0\rangle$. Binabago nito ang mga qubit sa state:

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

May kakaibang nangyari: ang controlled-$U$ gate ay gumagamit lang ng qubit $0$ bilang control qubit, kaya maaaring isipin na hindi babaguhin ng gate na ito ang state ng qubit 0 sa anumang paraan. Ngunit kahit papaano, ginagawa nito! Kahit inilapat ang operasyon sa mga ibabang qubit, ang pangkalahatang epekto ng gate ay baguhin ang phase ng qubit $0$. Ito ay kilala bilang "phase kickback mechanism," at ginagamit sa maraming quantum algorithm, kabilang ang mga algorithm ni Deutsch-Josza at Grover. Kung nais mong matuto nang higit pa tungkol sa phase-kickback mechanism, tingnan ang leksyon ni John Watrous tungkol sa Quantum query algorithms sa Fundamentals of quantum algorithms.

Pagkatapos ng phase-kickback, mag-a-apply tayo ng isa pang Hadamard sa qubit $0$, na nagbubunga ng state:

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

Kaya, kapag sinukat natin ang qubit $0$ sa dulo, susukat tayo ng $|0\rangle$ nang may 100% katiyakan kung $\theta = 0$ at susukat tayo ng $|1\rangle$ nang may 100% katiyakan kung $\theta = \frac{1}{2}$ (at kung perpekto ang ating quantum computer, walang ingay). Kung ang $\theta$ ay iba pa rito, ang panghuling sukat ay probabilistiko lamang at nagsasabi lang ng kaunting impormasyon.

QPE na may mas mataas na katumpakan: mas maraming qubit

Maaari nating palawigin ang simpleng konsepto na ito sa isang mas kumplikadong algorithm na may arbitrary na katumpakan. Sa halip na gamitin ang qubit $0$ lamang para sukatin ang phase, gagamitin natin ang $m$ qubit na $0$ hanggang $m-1$, at magagawa nating tantiyahin ang phase nang may $m$ bit ng katumpakan. Tingnan nating kung paano ito gumagana:

Ang mas tumpak na QPE Circuit na ito ay nagsisimula sa parehong paraan gaya ng single-bit na bersyon: inilalapat ang mga Hadamard sa unang $m$ qubit, at ang mga natitirang qubit ay inihanda sa state na $|\psi\rangle$, na lumilikha ng state:

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

Ngayon, inilalapat ang mga controlled-unitary. Ang qubit $0$ ang control para sa parehong unitary na $U$ gaya ng dati. Ngunit ngayon, ang qubit $1$ ang control para sa unitary na $U^2$, na simpleng $U$ na inilapat nang dalawang beses. Kaya, ang eigenvalue ng $U^2$ ay $e^{2*2\pi i \theta}$. Sa pangkalahatan, ang bawat qubit na $k$ mula 0 hanggang $m-1$ ang magiging control para sa unitary na $U^{2^k}$. Ibig sabihin, ang bawat qubit na ito ay makakaranas ng phase kickback na $e^{2^k*2\pi i \theta}$. Nagbubunga ito ng state:

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

Maaari itong isulat muli bilang kabuuan ng mga computational basis state:

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

Pamilyar ba sa iyo ang kabuuan? Ito ay isang QFT! Alalahanin ang equation para sa quantum Fourier transform:

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

Kaya, kung ang phase na $\theta = y/2^m$ para sa ilang integer na $y$ sa pagitan ng $0$ at $2^m-1$, ang pag-apply ng inverse QFT sa state na ito ay magreresulta sa state:

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

at mula sa $|y\rangle$, maaari nating matukoy ang $\theta$.

Kung ang $\theta/2^m$ ay hindi isang integer multiple, gayunpaman, ang pag-apply ng inverse QFT ay magtatayang lamang ng $\theta$. Kung gaano kahusay nitong tatantiyahin ang $\theta$ ay magiging probabilistiko, ibig sabihin, hindi palagi nating makukuha ang pinakamainam na pagtatantya, ngunit magiging medyo malapit ito, at habang marami kang ginagamit na qubit na $m$, mas mahusay ang pagtatantya na matatanggap mo. Para matuto tungkol sa kung paano sukatin ang pagtatantyang ito ng $\theta$, tingnan ang leksyon ni John Watrous tungkol sa Phase estimation and factoring sa Fundamentals of quantum algorithms.

Konklusyon

Binigyan ng pangkalahatang-ideya ng modyul na ito kung ano ang QFT, kung paano ito ini-implement sa isang quantum computer, at kung gaano kapaki-pakinabang ito sa paglutas ng mga problema. Binigyan natin ng panimulang panlasa ang kanyang pagiging kapaki-pakinabang nang makita natin kung paano ito magagamit sa quantum phase estimation para matuto tungkol sa mga eigenvalue ng isang unitary matrix.

Mga pangunahing konsepto

• Ang Quantum Fourier Transform ay ang quantum analog ng Discrete Fourier Transform.
• Ang QFT ay isang halimbawa ng basis transformation.
• Ang Quantum Phase Estimation procedure ay umaasa sa phase-kickback mechanism mula sa mga controlled-unitary operation, pati na rin ang inverse QFT.
• Ang QFT at QPE ay parehong malawak na ginagamit na subroutine sa maraming quantum algorithm.

Mga Tanong

Tama/Mali

1. T/M Ang Quantum Fourier Transform ay ang quantum analog ng classical discrete Fourier transform (DFT).
2. T/M Ang QFT ay maaaring i-implement gamit lamang ang Hadamard at CNOT gate.
3. T/M Ang QFT ay isang pangunahing bahagi ng algorithm ni Shor.
4. T/M Ang output ng Quantum Phase Estimation ay isang quantum state na kumakatawan sa eigenvector ng operator.
5. T/M Ang QPE ay nangangailangan ng paggamit ng inverse Quantum Fourier Transform (QFT$^\dag$).
6. T/M Sa QPE, kung ang phase na $\phi$ ay eksaktong maikukuhang pantay sa $n$ bit, ang algorithm ay nagbibigay ng tamang resulta nang may probability na 1.

Maikling sagot

1. Ilang qubit ang kailangan para ma-perform ang QFT sa isang sistema na may $2^n$ data point?
2. Maaari bang gamitin ang QFT sa isang state na hindi isang computational basis state? Kung gayon, ano ang mangyayari?
3. Paano nakakaapekto ang bilang ng control qubit na ginagamit sa QPE sa resolution ng resultang phase estimate?

Mga problema

1. Gamitin ang matrix multiplication para i-verify na ang mga hakbang sa QFT algorithm ay nagbubunga nga ng $\text{QFT}_4$ matrix:

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

(Hindi mo kailangang gawin ito nang mano-mano!)

Mga challenge na problema

1. Gumawa ng four-qubit state na pantay na superposisyon ng lahat ng odd computational bases: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. Pagkatapos ay mag-perform ng QFT sa state. Ano ang resultang state? Ipaliwanag kung bakit makatuwiran ang iyong resulta, gamit ang iyong kaalaman sa Fourier transform.