Grover's Algorithm Explained with Python (PhD Ki Koi Zaroorat Nahi)

Zara socho, ek deewar hai jisme 1 million (das lakh) ek jaisi grey lockers lagi hain. Un sabme se sirf ek locker ke peeche ek golden ticket chhupa hai. Baaki sab khaali hain.

Na koi naksha milega, na koi ishara, na hi koi mehrbaan chowkidar tumhe hint dega. Tumhari poori kainaat mein bas ek hi taaqat hai: ek locker kholo, andar jhaanko, aur agar khaali nikla toh band karke agle wale pe chale jao.

Agar tum ek classical computer ho (science ki zabaan mein matlab "woh bilkul normal computer jo abhi tumhare desk pe raha hai"), toh yeh sach mein mushkil kaam hai. Worst case mein, tumhe locker ke baad locker check karna padega, shayad poore ek million, tab jaake kismat chamke. Computer scientists ise likhte hain O(N): kaam seedhi lakeer mein badhta hai lockers ki tadaad ke saath. Lockers double karo, dard bhi double, isse bachne ka koi tareeka nahi.

Ek quantum algorithm hai jiska naam hai Grover's Algorithm, jo tumhara golden ticket taqreeban 1,000 steps mein dhoond leta hai, 1,000,000 ki jagah. Isliye nahi ki yeh cheating karta hai, aur isliye bhi nahi ki quantum computers jaadu se har cheez mein "faster" ho jaate hain (haqeeqat mein zyaadatar kaamon mein woh nahi hote). Asal wajah yeh hai ki Grover's algorithm ek aisa tareeka istemal karta hai jo ek classical computer structurally kar hi nahi sakta: yeh sahi locker ko dheere dheere bheed se alag khada kar deta hai, jab tak woh chilla na de "PICK ME."

Is post ke aakhir tak, tumhe bilkul saaf samajh aa jaayega ki yeh dhakka kaise kaam karta hai, aur tumhare paas hoga asli Python code (tested aur working, koi hawa-hawaai baat nahi) jo yeh sab ek asli quantum simulator pe kar dikhaata hai, tumhare apne machine pe. Koi linear algebra ki purani yaadein taaza karne ki zaroorat nahi. Chalo shuru karte hain.

Pehle, woh boring classical baseline

Pehle yeh baat clear kar lete hain, kyunki tumhe iski zaroorat padegi ek paimane ke taur pe.

Agar tumhare paas N lockers hain aur sirf ek inaam hai, aur lockers sach mein unsorted hain, kuch bhi exploit karne layak nahi, toh ek classical computer unhe ek-ek karke check karega. Average mein N/2 koshishein lagengi, aur worst case mein poore N. Yehi hai O(N), linear time. Koi chaalaak indexing tareeka yahan kaam nahi aayega, kyunki "unsorted" ka matlab hi yeh hai: sort karne ke liye kuch hai hi nahi. Yeh bas waisa hi hai jaise ek dher mein se ek sui dhoondna, bina kisi tarteeb ke.

Ya kam se kam, tab tak jab tak tum classical bits mein phanse ho.

Pehli Anokhi Cheez: Superposition

Ek classical computer mein, bit ya toh 0 hota hai ya 1. Bilkul thos taur par. Boringly. Beech ka koi raasta nahi.

Lekin ek qubit (jo ki bit ka quantum version hai), use hum ek aisi halat mein daal sakte hain jise superposition kehte hain. Ismein qubit ek hi waqt mein 0 bhi hota hai aur 1 bhi. Sochiye ek sikka (coin) jo hawa mein ghoom raha hai. Aisa nahi hai ki aapko abhi pata nahi ki heads aayega ya tails (woh toh aam probability hoti hai). Asliyat yeh hai ki jab tak sikka zameen par gir nahi jata aur aap use dekh nahi lete, tab tak woh dono halaton mein ek saath hota hai.

Humare liye jo baat sabse zyada ahmiyat rakhti hai woh yeh hai: jab aap kayi saare qubits ko ek saath superposition mein daalte hain, toh sirf kuch cheezon ka mix nahi milta. Balki aapko 0s aur 1s ke saare mumkin combinations ek single quantum state mein mil jaate hain, bilkul jaise transparent photographs ko ek ke upar ek rakh diya gaya ho. Agar 3 qubits superposition mein hain, toh saare 8 combinations (000, 001, 010, 011, 100, 101, 110, 111) ek saath maujood hain, aur har ek ke paas "amplitude" ka ek barabar hissa hota hai (amplitude ko aap ek chhupa hua probability samajh sakte hain: iska square nikaliye aur aapko us outcome ke milne ke asli chances pata chal jaayenge).

Sunne mein yeh ek cheat code lagta hai na? Aisa lagta hai ki bas ek baar jhaanko aur sab kuch fauran pata chal jaayega? Lekin nahi! Yahi toh twist hai. Jis waqt aap kisi superposition ko measure (observe) karte hain, woh collapse ho kar un saare combinations mein se sirf ek aam jawab ban jata hai, jo random chuna jata hai. Baqi saari possibilities hamesha ke liye ghayab ho jaati hain. Saara layered potential khatam, aur aapke haath lagta hai wahi 1-in-N chance wala aam sa locker jo aapko pehle bhi mil raha tha.

Toh sirf superposition se humara koi fayda nahi hone wala. Hamein ek aisa tarika chahiye jisse hum jhaankne (measure karne) se pehle hi baazi apne haq mein palat sakein. Grover's algorithm poora khel isi par khelta hai, aur iske paas do makhsoos (specific) moves hain, jinhe woh baar-baar dohrayata hai.

Move 1: Oracle (yaani "Woh Jaadui curse")

Ek jaadui dabba socho (magic box). Tum usme ek locker ka number daalte ho, aur andar hi andar use pata hota hai kaunsa sahi hai, lekin woh tumhe seedha jawaab nahi dega. Iske bajaye: agar tum sahi locker daalo, toh woh chupke se usko ek raaz-wala curse de deta hai, uska phase flip karke (seedhi bhasha mein: uss locker ke amplitude ko βˆ’1 se multiply kar deta hai). Agar galat locker daalo, toh bilkul kuch nahi hota.

Sabse pareshaan (surprising) karne wali baat yeh hai ki yeh curse kuch bhi aisa nahi badalta jo tum dekh sako. Abhi measure karo, toh wahi purana 1-in-N wala chance milega, kyunki probability sirf amplitude ke size ki fikar karti hai (woh bhi square karke), uske sign ki nahi. Ek curse jo bas minus sign flip kare, woh apne aap mein bilkul ghaayab, na dikhne wala hai. Chalaak, aur upar se bekaar lagta hai.

Lekin yehi toh asli hathiyaar hai jo hamari doosri chaal ko chahiye.

Move 2: Diffuser (yaani "The Group Photo Flip")

Yeh woh move hai jo sach mein aisa kuch karti hai jo tum dekh sako.

Socho saare N lockers ke amplitudes ek bar chart ki tarah hain. Oracle chalne se pehle, har bar ki height bilkul barabar hai (yehi hai woh "even superposition" jiski baat pehle hui thi). Oracle chalne ke baad, sirf ek akela bar, woh sahi locker, ulta ho jaata hai: height wahi rehti hai, lekin ab negative ho jaati hai, jabki baaki sab positive aur waise hi rehte hain.

Diffuser ek kaam karta hai jise kehte hain inversion about the mean: yeh saare bars ki average height nikalta hai, phir har ek bar ko us average line ke around reflect kar deta hai, bilkul aaine ki tarah. Sabse khoobsurat baat yeh hai ki jis bar pe curse tha woh pehle se hi sabse neeche tha (negative tha, yaad hai na), toh use average ke around reflect karne se woh seedha upar ki taraf udd jaata hai, kisi bhi normal bar se zyaada oonchaai tak. Baaki jo bars the, woh pehle se hi average ke kareeb the, toh woh mushkil se hilte hain.

Yeh ek baar karo, aur sahi locker ka bar ab saaf saaf sabse lamba dikhta hai. Ek aur Oracle+Diffuser round chalao, aur woh aur bhi lamba ho jaata hai. Sahi tadaad mein dohraao, aur sahi wala bar sabpe haavi ho jaata hai. Tab jaake, measure karne pe bekaar chances ki jagah zabardast chances milte hain.

Is do-step combo ka ek pakka naam hai: amplitude amplification. Yeh dhadakta hua dil hai takriban har us quantum search algorithm ka jisse tumhara kabhi bhi saamna hoga.

Toh yeh kitni baar dohraana (repeat) padta hai?

Aap soch rahe honge: hum Oracle+Diffuser ko sirf ek baar chala kar khatam kyun nahi kar dete? Ya phir ek hazaar baar kyun nahi chalate taaki bilkul pakka ho jaye?

Pata yeh chala hai ki aap is kaam ko hadd se zyada (overdo) bhi kar sakte hain. Sochiye ek compass ki sui (needle) ko jo shuru mein sideways hai, jiska aapke jawab se koi lena-dena nahi hai. Har ek Oracle+Diffuser ka round us sui ko thoda sa ghuma kar "sahi jawab ki taraf" le jata hai. Agar aap sahi taadad mein rotations karenge, toh sui bilkul nishane par rukegi jab aap measure karenge. Lekin agar aap us sweet spot se aage nikal gaye, toh sui nishane ko paar karke doosri taraf chali jaayegi, aur aapke jeetne ke chances dobara kam hone lagenge. Grover's algorithm ka mizaaj hi aisa periodic hai.

Iska jaadui number (asli formula) taqreeban yeh hai:

iterations ≈ (π / 4) × √N

Haan, yeh wahi geometry class wala asli Ο€ hai! Iske piche ki haqeeqat yeh hai ki har ek Oracle+Diffuser round asal mein ek rotation hai, ek fixed angle par, jo "sahi jawab" aur "baqi sab" ke abstract 2D space mein hota hai. Ise istemal karne ke liye aapko iska derivation nikalne ki zaroorat nahi hai, bas is formula par bharosa kijiye aur neeche code mein iska kamaal dekhiye.

Is formula ki ek aur khaas baat dekhiye: rounds ki taadad √N ke hisab se badhti hai, na ki $N$ ke hisab se. Yeh square root hi sabse badi wajah hai jiski wajah se Grover's algorithm itna ahmiyat rakhta hai. Yeh kitna bada fayda hai, is par aage baat karte hain.

Chalo, ab asli code likhte hain

Hum Qiskit ka istemal karenge, jo IBM ka open-source Python framework hai aur quantum circuits banane ke kaam aata hai. Pehle ise install karo:

pip install qiskit qiskit-aer

qiskit tumhe circuit-building tools deta hai; qiskit-aer tumhe ek tez local simulator deta hai, taaki tum yeh sab bina kisi asli quantum computer tak pahunch ke bhi chala sako.

Step 1: superposition banao

Qiskit mein har quantum circuit ki zindagi shuru hoti hai ek QuantumCircuit ke roop mein, aur woh gate jo superposition banata hai woh hai Hadamard gate, h. Ise har qubit pe lagane se hamara bore-karne-wala |000> shuru wala state, sabhi aath possibilities ke barabar superposition mein badal jaata hai:

from qiskit import QuantumCircuit

n = 3  # hum 2^3 = 8 lockers mein dhoond rahe hain
qc = QuantumCircuit(n, n)
qc.h(range(n))  # har qubit pe Hadamard β†’ saare 8 states ka barabar superposition

Step 2: Oracle banao

Humein bas ek target bitstring (jaise 101) ka phase flip karna hai, aur baaki har state ko bina chhuye chhodna hai.

Tareeka yeh hai ki ek multi-controlled Z gate khud-ba-khud all-ones state, 111, ka phase flip kar deta hai, aur kuch aur nahi. Toh agar hamara target all-ones nahi hai, toh hum thodi der ke liye uske 0-bits ko X gates se 1 mein badal dete hain, multi-controlled Z lagate hain, phir un bits ko wapas palat dete hain. Yeh bilkul aisa hai jaise target ko ek bhes pehna diya jaaye taaki woh 111 jaisa dikhe, bas itni der ke liye ki usse curse mil jaaye, phir bhes utaar diya jaaye:

def oracle(qc, marked_state):
    n = len(marked_state)
    bits = marked_state[::-1]  # Qiskit qubits ko right-to-left number karta hai
    zero_positions = [i for i, b in enumerate(bits) if b == '0']

    for i in zero_positions:
        qc.x(i)  # bhes: 0-bits ko 1 mein badlo

    # multi-controlled Z, H + multi-controlled-X + H se banaya gaya
    qc.h(n - 1)
    qc.mcx(list(range(n - 1)), n - 1)
    qc.h(n - 1)

    for i in zero_positions:
        qc.x(i)  # bhes wapas utaaro

Yeh h / mcx / h wala sandwich ek standard circuit tareeka hai: ek multi-controlled X gate, jise target qubit pe Hadamards mein lapeta gaya ho, bilkul multi-controlled Z gate ki tarah behave karta hai. Isse humein koi extra gate types import karne ki zaroorat nahi padti, kyunki yahan sab kuch sirf H aur X-family gates se bana hai.

Step 3: Diffuser banao

Diffuser (inversion about the mean) mein pata chalta hai ki lagbhag wahi recipe dobara istemal hoti hai. Agar tum gaur se dekho, iski beech ki teen lines bilkul oracle ke bhes-curse-bhes-utaaro wale pattern jaisi hain, jo hamesha ke liye 000 ko target maan ke set ki gayi hain, bas iske aage-peeche ek extra Hadamards ka jodaa laga hai taaki pehle ek alag basis mein jump kiya ja sake:

def diffuser(qc, n):
    qc.h(range(n))
    qc.x(range(n))

    qc.h(n - 1)
    qc.mcx(list(range(n - 1)), n - 1)
    qc.h(n - 1)

    qc.x(range(n))
    qc.h(range(n))

Step 4: sab kuch jodo

Ab bas Hadamards ko chain karo, phir Oracle+Diffuser ko iterations baar dohraao, phir measure karo:

import math
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

def build_grover_circuit(marked_state, iterations):
    n = len(marked_state)
    qc = QuantumCircuit(n, n)
    qc.h(range(n))                     # step 1: superposition banao
    for _ in range(iterations):
        oracle(qc, marked_state)       # step 2: jawaab ko curse karo
        diffuser(qc, n)                # step 3: use amplify karo
    qc.measure(range(n), range(n))
    return qc

def optimal_iterations(n):
    N = 2 ** n
    return max(1, math.floor((math.pi / 4) * math.sqrt(N)))

marked_state = "101"
n = len(marked_state)
iterations = optimal_iterations(n)

qc = build_grover_circuit(marked_state, iterations)

sim = AerSimulator()
compiled = transpile(qc, sim)
result = sim.run(compiled, shots=1000).result()
counts = result.get_counts()

print(f"{marked_state} ko {2**n} possibilities mein dhoondh rahe hain, {iterations} iteration(s) ke saath")
print(counts)

Bas itna hi hai poora algorithm. Itna zyaada code nahi hai kisi aisi cheez ke liye jo classical search ko maat de deti hai, aur sach kahun toh yehi iski khoobsurati hai.

Ab isse sach mein chalate hain

Maine upar wala code bilkul waise hi chalaya jaise likha hai, 101 ko 8 possibilities (3 qubits) mein dhoondte hue, simulator pe 1,000 shots ke saath. Yeh raha jo nateeja aaya:

101 ko 8 possibilities mein dhoondh rahe hain, 2 iteration(s) ke saath
{'101': 948, '111': 11, '100': 10, '001': 8, '110': 8, '000': 6, '010': 5, '011': 4}

1,000 measurements mein se, 948 101 (hamara target) pe aaye, aur baaki sabko chhoti-moti ginti mili. Tasveer ki tarah dekho toh aisa dikhta hai:

101 | ######################################## 948  <-- hamara jawaab!
111 | # 11
100 | # 10
001 | # 8
110 | # 8
000 | # 6
010 | # 5
011 | # 4

Ek bhi Oracle+Diffuser round chalne se pehle, un saare 8 bars ki height bilkul barabar hoti: har locker ke paas exactly 1-in-8 (12.5%) ka mauka hota. Amplitude amplification ke do rounds ke baad, hamara target 94% se upar pahunch jaata hai.

Us "bahut hi aasan" wale extreme ke baare mein jaanna hai? n = 2 aur marked_state = "11" try karo. Sirf 4 possibilities ke saath, ek hi iteration 100.0% success ke saath kaam kar deta hai, ek badiya, saaf-suthra toy case jisse intuition banti hai scale up karne se pehle.

Theek hai, lekin mujhe iski parwaah kyun karni chahiye?

Sahi sawaal hai. Ab numbers mein faayda dekho:

Dhoondhne Wale Lockers (N)	Classical Worst Case	Grover's Algorithm (β‰ˆ (Ο€/4)βˆšN)
100	100	~8
10,000	10,000	~79
1,000,000	1,000,000	~785
4,294,967,296 (2Β³Β²)	~4.3 arab	~51,472

Ise kehte hain quadratic speedup, aur yeh search-shaped problems ke liye sach mein badi baat hai: database lookups, kuch tarah ke puzzles ko brute-force karna, aur (yeh agla part developers ko thoda sidha bitha deta hai) symmetric encryption keys ko brute-force karna.

Ek jaldi wali myth-busting baat, kyunki yeh sawaal bahut baar aata hai: tumne shayad suna hoga ki quantum computers "saari encryption tod denge." Woh asal mein ek alag algorithm hai, Shor's algorithm, jo RSA aur doosre "hard math problem" wale schemes ko exponential speedup se tabaah kar deta hai. Grover's algorithm mukaable mein kaafi shareef hai. Yeh sirf quadratic speedup deta hai, aur sirf symmetric-key cheezon pe lagu hota hai jaise AES ya hashes ko brute-force karna, RSA-jaisi asymmetric encryption pe bilkul nahi.

Phir bhi ek asli nuksaan toh hai: Grover's algorithm ko ek k-bit symmetric key pe laga do, toh uski effective strength lagbhag aadhi ho jaati hai (2^k wali search ban jaati hai ~2^(k/2) wali search). Yehi wajah hai ki security wale log AES-256 ko AES-128 se zyaada recommend karte hain, kisi bhi aisi cheez ke liye jo lambe waqt tak surakshit rehni chahiye: 256 bits tumhe ek aaraam-daayak 128-bit ka margin de dete hain, chahe saamne quantum attacker Grover's algorithm hi kyun na chala raha ho.

Ek Chhoti Si Summary (TL;DR)

• N unsorted items mein classical search karne mein O(N) time lagta hai. Iska koi shortcut nahi hai.
• Grover's algorithm isi kaam ko taqreeban O(√N) mein kar deta hai do moves ko baar-baar repeat karke: ek Oracle jo sahi jawab ke phase par chupke se minus sign lagata hai, aur ek Diffuser jo us chhupay gae minus sign ko ek bade probability boost mein badal deta hai.
• Oracle+Diffuser combo ko taqreeban (π/4)√N baar dohraana padta hai. Isse zyaada karo, toh chances phir se neeche gir jaate hain.
• Yeh quadratic speedup hai, exponential nahi: sach mein kaam ka hai, lekin woh "encryption khatam" wala scenario nahi jo log kabhi kabhi soch lete hain. Woh toh Shor's algorithm ka kaam hai.
• Yeh sab sirf 40 lines ke real, runnable Qiskit code mein simat jata hai, jo ab tumhare paas maujood hai.

Ab aap khud jaakar marked_state string ko badaliye, n ko 5 ya 6 qubits tak badhayein, aur bar chart ka kamaal dekhiye. Is cheez ko hamesha ke liye zehan mein bithane ka isse behtar koi tarika nahi hai.