Quantum Algorithms क्यों जीतते हैं
यहीं वह वादा है जिसने इस field को launch किया। कुछ problems बढ़ने पर exponentially कठिन होते जाते हैं: input size दोगुना करो, और काम दोगुना नहीं होता — explode हो जाता है। ऐसे problem के सामने classical computer ऐसा है जैसे कोई चम्मच से समंदर खाली करने की कोशिश करे। quantum algorithms, कुछ खास problems के लिए, इस explosion को एक gentle slope में बदल सकते हैं।
वह classic plot imagine करो जो हर quantum course बनाता है। horizontal axis है problem size n — मान लो उस number के digits जिसे factor करना है — 0 से 60 तक। vertical axis है computational steps, लगभग 1,200,000 तक। अब 3 curves बनाओ। n² वाली curve और n³ वाली curve floor से चिपकी रहती हैं: n = 60 पर भी उन्हें सिर्फ कुछ हज़ार steps चाहिए। लेकिन 2ⁿ वाली curve एक अलग ही जानवर है — पहले flat, फिर rocket की तरह ऊपर और chart के top को तोड़ती हुई। यही rocket है जिसका सामना classical algorithms कठिन problems पर करते हैं। quantum algorithms का मकसद इस rocket को वापस floor तक खींच लाना है।
flagship example है factoring — किसी बड़ी संख्या को उसके prime factors में तोड़ना। जितने classical तरीके हम जानते हैं, वे digits की संख्या के साथ brutally scale होते हैं, और यही hardness आधुनिक encryption की रक्षा करती है: आपके bank transactions इसलिए safe हैं क्योंकि 600-digit number को factor करने में classical machines को universe की age से ज़्यादा time लगेगा। Shor's algorithm (1994) उसी number को इतने steps में factor करता है जो सिर्फ polynomially बढ़ते हैं — efficiently, explosively नहीं। वही problem, effort की अलग ही दुनिया।
तो quantum algorithm की merit इस बात से मापी जाती है कि उसका काम problem size के साथ कैसे scale होता है, raw speed से नहीं। quantum computer तेज़ clock नहीं है — यह एक ऐसी machine है जो कुछ classically intractable problems को tractable बना सकती है। वह "कुछ" बहुत मायने रखता है, और अगला section इस बारे में ईमानदार है।
आम ग़लतफ़हमी: “Shor's algorithm O(log n) steps में factor करता है — मतलब लगभग instant।” नहीं। Shor's polynomial time में चलता है (digits की संख्या में लगभग cubic), जो efficient है लेकिन logarithmic से बहुत दूर। किसी भी chart या slogan से सावधान रहो जो इसे instant जैसा बताए — ईमानदार दावा polynomial बनाम super-polynomial है, और वही पहले से revolutionary है।
गहरे उतरें — गणित और सटीकता
complexity theory इसे एक precise भाषा देती है। P उन problems की class है जिन्हें classical computer polynomial time में solve कर सकता है — ऐसा time जो input size n के \(n^2\), \(n^3\) या किसी fixed power की तरह बढ़ता है। BQP ("bounded-error quantum polynomial time") इसका quantum analogue है: वे problems जिन्हें quantum computer polynomial time में solve कर सकता है, error probability ज़्यादा से ज़्यादा \(\tfrac{1}{3}\) के साथ। P का हर problem BQP में भी है — quantum computer efficiently वह सब कर सकता है जो classical कर सकता है — और दृढ़ता से माना जाता है (हालाँकि proven नहीं है) कि BQP strictly बड़ा है: इसमें integer factoring और discrete logarithms जैसे problems हैं जो जहाँ तक कोई बता सकता है, P के बाहर हैं।
Shor's algorithm वह exhibit है जिसने BQP को मशहूर किया। classically, सबसे अच्छा known factoring method — general number field sieve — sub-exponential time में चलता है: साफ \(2^n\) नहीं, लेकिन फिर भी super-polynomial, बड़े inputs के लिए practical होने से कहीं ज़्यादा तेज़ी से बढ़ता हुआ। Shor's algorithm, quantum Fourier transform और period-finding पर बना, n-digit number को n में polynomial time में factor करता है (standard multiplication के साथ लगभग \(O(n^3)\)। polynomial बनाम super-polynomial ईमानदार framing है — "exponential speedup" slogan है, और यह justified है, क्योंकि classical scaling exponential जैसी ही है भले ही literally \(2^n\) न हो।
वह caveat जो field को ईमानदार रखता है: exponential speedup problem-specific है, universal नहीं। P के ज़्यादातर problems को कोई meaningful quantum advantage नहीं मिलता, और BQP के बाहर के ज़्यादातर problems quantum computers के लिए भी कठिन रहते हैं। field की कला है structured problems खोजना — periodicity, hidden subgroups, unstructured search (Grover's quadratic speedup), quantum simulation — जहाँ interference और entanglement वह खरीदते हैं जो classical machines नहीं खरीद सकतीं। quantum computer एक specialist instrument है, universal accelerator नहीं।
मुख्य बातें
- quantum algorithm की merit इस बात से मापी जाती है कि उसका काम problem size के साथ कैसे scale होता है — polynomial बनाम super-polynomial — clock speed से नहीं।
- steps-बनाम-size वाले classic plot पर 2ⁿ curve chart से बाहर explode होती है जबकि n² और n³ floor से चिपकी रहती हैं; quantum algorithms का मकसद कठिन problems को वापस floor तक लाना है।
- factoring flagship है: classically super-polynomial (best known: general number field sieve), quantumly polynomial — Shor's algorithm (1994) से।
- Shor's polynomial time में चलता है — digits में लगभग cubic — O(log n) में नहीं; ईमानदार दावा polynomial बनाम super-polynomial है।
- exponential speedup problem-specific है: P ⊆ BQP strictly बड़ा माना जाता है लेकिन proven नहीं है, और रोज़मर्रा के ज़्यादातर problems को quantum computers से कुछ नहीं मिलता।
अपनी समझ परखें
Q1.computational steps (y-axis) बनाम problem size n (x-axis, 0–60) वाले classic plot पर, n² और n³ curves की तुलना में 2ⁿ curve कैसी दिखती है?
exponential scaling n के साथ explode होती है; polynomial curves (n², n³) धीरे बढ़ती हैं। quantum algorithms का पूरा point है कठिन problems को rocket curve से floor तक लाना।
Q2.Shor's factoring algorithm के बारे में कौन-सा कथन सही है?
Shor's polynomial है, जबकि classical general number field sieve sub-exponential scale होता है। O(log n) एक myth है; P बनाम BQP की strictness अभी unproven है।
Q3.एक startup दावा करता है कि उसका quantum computer 'सारे computing tasks को exponentially speed up' करेगा। इस दावे में क्या ग़लत है?
quantum advantage structured problems (periodicity, search, simulation) पर लागू होता है; यह universal accelerator नहीं है।
संदर्भ (References)
इस पाठ के दावे जिन किताबों, papers और articles से लिए गए हैं — हर एक के नीचे लिखा है कि उसका इस्तेमाल किस बात के लिए हुआ।
- Shor, P., "Algorithms for quantum computation: discrete logarithms and factoring" (Proc. 35th FOCS, 1994). · source ↗
किस लिए इस्तेमाल हुआ: Shor's polynomial-time factoring result and its basis in quantum period-finding. - Nielsen & Chuang, Quantum Computation and Quantum Information, Ch. 3 (complexity classes P and BQP).
किस लिए इस्तेमाल हुआ: P vs. BQP framing and the problem-specific nature of quantum speedup.
सुझाव: पेज बदलने के लिए ← / → दबाएँ।