01 — परिचय
Deutsch-Jozsa Algorithm क्या है?
1992 में David Deutsch और Richard Jozsa द्वारा प्रस्तुत, यह quantum computing के इतिहास में एक मील का पत्थर है।
ऐतिहासिक महत्व
Deutsch-Jozsa algorithm को 1992 में David Deutsch और Richard Jozsa ने प्रस्तुत किया। यह quantum algorithms के क्षेत्र में एक अग्रणी कार्य था।
Quantum Supremacy
यह पहला quantum algorithm था जिसने quantum supremacy demonstrate किया — यह दिखाया कि quantum computers कुछ समस्याओं को classical computers से बेहतर हल कर सकते हैं।
Exponential गति
यह algorithm classical computers से exponentially तेज़ है — जहाँ classical computer को 2n-1+1 queries चाहिए, quantum computer सिर्फ 1 query में answer देता है!
02 — समस्या
समस्या क्या है?
Deutsch-Jozsa algorithm एक बहुत ही specific प्रश्न का उत्तर देता है: दिया गया function "Constant" है या "Balanced"?
- हमें एक function f(x) दिया जाता है जो 0 या 1 output देता है
- यह function या तो "Constant" है (सभी inputs के लिए same output) या "Balanced" है (आधे inputs के लिए 0, आधे के लिए 1)
- हमें बताना है कि function Constant है या Balanced
- Classical computer को worst case में 2n-1+1 बार query करनी पड़ती है
- Quantum computer सिर्फ 1 query में answer देता है!
03 — Algorithm के Steps
Algorithm कैसे काम करता है?
Deutsch-Jozsa algorithm 5 सरल steps में काम करता है। हर step में quantum states कैसे बदलती हैं, यह नीचे दिखाया गया है।
Initialization — प्रारंभिक अवस्था
n input qubits को |0⟩ अवस्था में और 1 ancilla (सहायक) qubit को |1⟩ अवस्था में set करें। यह हमारा शुरुआती बिंदु है।
Hadamard Gate — H Gate लगाएँ
सभी qubits (input + ancilla) पर Hadamard transform लगाएँ। यह सभी qubits को superposition में डाल देता है — हर qubit एक साथ |0⟩ और |1⟩ दोनों अवस्थाओं में होता है।
Oracle (Uf) — Black Box
Quantum oracle Uf लगाएँ — यह एक quantum black-box है जो function f को encode करता है। Oracle superposition की वजह से एक ही बार में सभी inputs पर काम करता है।
Hadamard Gate (फिर से) — दूसरा H Gate
Input qubits पर दोबारा Hadamard Gate लगाएँ। यह step quantum interference पैदा करता है — constructive या destructive interference तय करता है कि final state क्या होगी।
Measurement — मापन
Input qubits को measure करें। अगर सभी qubits 0 मिलें → function Constant है। अगर कोई भी qubit 1 मिले → function Balanced है। बस, एक ही measurement में answer!
04 — Quantum Circuit
Quantum Circuit Diagram
नीचे Deutsch-Jozsa algorithm का quantum circuit diagram है। Qubits बाएँ से दाएँ बहते हैं — gates में से गुज़रते हुए।
05 — तुलना
Classical vs Quantum तुलना
Deutsch-Jozsa algorithm quantum computing की शक्ति को स्पष्ट रूप से दर्शाता है।
| पहलू | Classical | Quantum (DJ) |
|---|---|---|
| Queries की संख्या | 2n-1 + 1 | 1 |
| गति (Speed) | Exponential | Constant |
| त्रुटि दर (Error) | 0% | 0% |
| n=10 के लिए Queries | 513 | 1 |
| n=20 के लिए Queries | 524,289 | 1 |
| n=50 के लिए Queries | ~5.6 × 1014 | 1 |
| Deterministic? | हाँ | हाँ |
06 — मुख्य अवधारणाएँ
Key Concepts
Deutsch-Jozsa algorithm इन तीन quantum computing अवधारणाओं पर आधारित है।
सुपरपोजीशन
Superposition
एक qubit एक साथ |0⟩ और |1⟩ दोनों अवस्थाओं में हो सकता है। Hadamard gate के बाद, n qubits एक साथ 2n अवस्थाओं में होते हैं — यही quantum parallelism की शक्ति है। Oracle इन सभी अवस्थाओं पर एक साथ काम करता है।
क्वांटम इंटरफेरेंस
Quantum Interference
दूसरे Hadamard gate के बाद, quantum waves एक-दूसरे से interfere करती हैं। Constant function में constructive interference होता है (सभी |0⟩ पर केंद्रित), जबकि Balanced function में destructive interference |0⟩ को cancel कर देता है।
Oracle / Black Box
Quantum Oracle (Uf)
Oracle एक quantum black box है — हमें function f की internal working नहीं पता, लेकिन हम इसे query कर सकते हैं। Quantum oracle |x, y⟩ → |x, y ⊕ f(x)⟩ transformation करता है। DJ algorithm की खूबसूरती यह है कि एक ही oracle call में answer मिल जाता है।