Kvantiniai algoritmai

I Eksperimento tikslai

II Teorija

Kvantinis pranasumas

Kvantiniai algoritmai naudoja superpozicija ir interferncija, kad isbandytu daug galimybiu vienu metu. Skirtingai nuo klasikiniu algoritmu, kurie tikrina iejimus po viena, kvantinis kompiuteris gali isvertinti funkcija visiems iejimams vienu metu -- tai vadinama kvantiniu lygiagretinimu.

Deutsch algoritmas

Deutsch algoritmas (1985) yra paprasciausias pavyzdys, rodantis kvantini pranasuma. Turime nezinoma 1-bito funkcija f:{0,1} -> {0,1}. Yra 4 galimos funkcijos:

Klasikiskai reikia 2 iskvietimu nustatyti ar f pastovi, ar subalansuota. Deutsch algoritmas tai padaro su 1 isskaukymu.

Bernstein-Vazirani algoritmas

Turime nezinoma n-bitu "slaptaji eilute" s. Orakulas apskaiciuoja f(x) = s . x (mod 2), kur "." yra vidinis sandauga (XOR po sudauginus bitus). Klasikiskai reikia n uzklausa, kvantiskai -- tik 1 uzklausos.

2-kubitu atveju (SpinQ Gemini) s gali buti: 00, 01, 10 arba 11. Orakulo grandis priklauso nuo s: jei atitinkamas s bitas = 1, taikome CNOT varata tarp to kubito ir pagalbinio kubito.

Grover paieskos algoritmas

Grover algoritmas (1996) sprencia paieskos problema: rasti pazymeta elementa N elementu nerikiuotoje duomenu bazeje. Klasikiskai reikia O(N) uzklausa, kvantiskai -- tik O(sqrt(N)).

Algoritmas susideda is dvieju pagrindiniu operaciju, kartojamu ~sqrt(N) kartu:

SpinQ Gemini sistemoje N = 2^2 = 4, todel pakanka tik 1 iteracijos (zymejimas + stiprinimas), kad radus taikini su tikimybe 1.

III Deutsch algoritmo simuliatorius

Pasirinkite funkcija ir stebkite, kaip kvantine grandine vienu orakulo issaukimu nustato, ar funkcija pastovi, ar subalansuota.

IV Bernstein-Vazirani simuliatorius

Pasirinkite slaptaja 2-bitu eilute s ir stebkite, kaip algoritmas ja atranda vienu orakulo issaukimu.

V Grover paieskos simuliatorius

Pasirinkite taikinio busena ir stebkite, kaip Grover algoritmas sustiprina jos amplitude viena iteracija. Galite eksperimentuoti su skirtingais taikiniais.

VI Grover algoritmas zingsnis po zingsnio

Stebkite, kaip keiciasi amplitudes kiekviename algoritmo zingsnyje. Naudokite mygtukus, kad pereitumete per kiekviena grandines etapa.

VII SpinQ Gemini realizacija

SpinQ Gemini sistemoje visi trys algoritmai realizuojami naudojant branduolinio magnetinio rezonanso (BMR) impulsines sekas. Sistema naudoja du kubitus: vandenilio (H-1) ir fluoro (F-19) branduolius chloroformo molekuleje.

Baziniai vartai ir ju NMR atitikmenys

Orakulo konstrukcija skirtingiems taikiniams

Stiprinimo operatorius R_s

Amplitudes stiprinimo operatorius R_s = H^(x2) * R_0 * H^(x2), kur R_0 = X * CZ * X (ignoruojant globalia faze). Pilna grandis N=4 atveju:

VIII Eksperimento procedura

IX Kontroliniai klausimai

X Apibendrinimas

XI Programinis pavyzdys ir RQmod alternatyva

Grover paiesos algoritma (taip pat Deutsch ir Bernstein-Vazirani) galima realizuoti tiek tiesiogine SpinQit/Qiskit grandine Python kalboje, tiek deklaratyviai .rqmod modelyje, kuri ResilQ Studio kompiliuoja i ResilQ IR ir QASM2 / SpinQit darba.

Pythonas: Grover paieska N=4 (1 iteracija)

2 kubitu Grover algoritme paslepta busena |11⟩ randama tiksliai vienos iteracijos metu. Orakulas zymejimui naudoja CZ varta, difuzeris — H, X, CZ, X, H seka.

# grover_2q.py — Grover paieska N=4, taikinys |11⟩ (SpinQit)
from spinqit import Circuit, BasicSimulator, get_compiler
from spinqit.model import H, X, CZ, MEASURE

qc = Circuit(2)

# 1) Vienoda superpozicija
qc.append(H, [0]); qc.append(H, [1])

# 2) Orakulas: pakeicia |11⟩ faze
qc.append(CZ, [0, 1])

# 3) Difuzeris: stiprina taikini
qc.append(H, [0]); qc.append(H, [1])
qc.append(X, [0]); qc.append(X, [1])
qc.append(CZ, [0, 1])
qc.append(X, [0]); qc.append(X, [1])
qc.append(H, [0]); qc.append(H, [1])

qc.append(MEASURE, [0, 1])

backend = BasicSimulator()
exe     = get_compiler("native").compile(qc, 0)
print(backend.run(exe, 1024).counts)
# tikimasi: ~100% |11⟩

Alternatyva: .rqmod modelis

RQmod modelyje algoritmas aprasomas auksciau abstrakcijos lygmeniu — fiksuojamas taikinys, iteraciju skaicius ir sekmes kriterijus. ResilQ Studio sugeneruoja QASM2 grandine ir CBOM iroduma.

// lab8-grover.rqmod
audit "lab8-grover-search" {
  targets = ["spinq-gemini-lab"]

  layers {
    use { runtime, openssl }
  }

  experiment grover {
    qubits      = [q0, q1]
    target      = "|11⟩"
    iterations  = 1
    oracle      { gate = cz; on = [q0, q1] }
    diffuser    = standard
    measure     = z_basis
    shots       = 1024
    verify      { p_target_min = 0.95 }
  }

  backend quantum {
    provider  = spinqit
    emit      = qasm2
    max_width = 2
  }

  output { formats = [json, cbom, qasm] }
}

resilq-q compile lab8-grover.rqmod --out build/lab8

Apie RQmod