সরাসরি পর্বে যান
পর্ব ৭৫ · ৮৫-এর মধ্যে · মডিউল ১২

Quantum computation আর BQP-র পরিচয়

Quantum Computation and an Introduction to BQP — Qubits, Measurement, Quantum Gates and Circuits, BPP ⊆ BQP ⊆ PSPACE, Deutsch–Jozsa, Grover's Search, Shor's Factoring and the Open Question of BQP versus NP

Taught in Bangla, this lesson explains qubits as amplitude vectors, measurement and interference, gates and circuits, and defines BQP with an outline of BPP ⊆ BQP ⊆ PSPACE. It proves Deutsch–Jozsa and Grover's √N search with its optimality, shows how Shor reduces factoring to period finding, and notes that BQP versus NP is open. An in-page NumPy state-vector simulator (Pyodide) runs the algorithms, and a real desktop qiskit run on its statevector sampler, not hardware, repeats Deutsch–Jozsa.

এই পর্বে যা শিখবেন

  • Qubit, state vector, measurement আর interference-এর নিখুঁত অর্থ, আর “একসাথে 0 আর 1” কথাটির সীমা
  • H, X, Z, phase আর CNOT gate, unitary matrix, entanglement আর quantum circuit
  • BQP-র সংজ্ঞা, আর BPP ⊆ BQP ⊆ PSPACE-এর প্রমাণের রূপরেখা
  • Deutsch–Jozsa আর Grover-এর algorithm প্রমাণসহ, আর Shor-এর factoring-এর কাঠামো
  • BQP বনাম NP, extended Church–Turing thesis আর “quantum advantage” দাবি সতর্কভাবে পড়া

১ · Bit, মুদ্রা আর qubit — amplitude কেন আলাদা

পর্ব ৬৯-এ একটি probabilistic যন্ত্রের অবস্থাকে সম্ভাবনার একটি তালিকা হিসেবে দেখা যায়: একটি মুদ্রার জন্য (p0, p1), যেখানে p0 + p1 = 1 আর দুটিই ≥ 0. Quantum যন্ত্রে এই তালিকার জায়গায় আসে amplitude-এর তালিকা, আর পার্থক্যটি একটিই কিন্তু বিশাল: amplitude ঋণাত্মক (আসলে complex) হতে পারে।

পুকুরে একসাথে দুটি ঢিল ছুড়ুন। দুই দিক থেকে আসা ঢেউ কোথাও মিলে উঁচু হয়, কোথাও একটির চূড়া অন্যটির খাদে পড়ে পানি প্রায় সমান থাকে। সম্ভাবনা এমন করতে পারে না: দুটি পথে একই জায়গায় পৌঁছানোর সম্ভাবনা শুধু যোগ হয়, কখনো কাটে না। Amplitude ঢেউয়ের মতো: দুটি পথ থেকে +½ আর −½ এলে যোগফল 0, অর্থাৎ সেই ফল আর কখনো দেখা যায় না। একে বলে interference.

সংজ্ঞা ১.১ (Qubit আর measurement)

একটি qubit-এর অবস্থা হলো |ψ⟩ = α|0⟩ + β|1⟩, যেখানে α, β দুটি complex number আর |α|2 + |β|2 = 1. এখানে |0⟩ = (1, 0) আর |1⟩ = (0, 1) দুটি ভিত্তি-vector, আর α, β-কে বলে amplitude.

Measurement (ভিত্তি {|0⟩, |1⟩}-এ): ফল 0 আসে |α|2 সম্ভাবনায়, ফল 1 আসে |β|2 সম্ভাবনায় (Born-এর নিয়ম)। মাপার পর অবস্থা ফলের সঙ্গে মিলে যায়: 0 এলে নতুন অবস্থা |0⟩, 1 এলে |1⟩.

“|ψ⟩” লেখাটিকে বলে ket, Dirac-এর চিহ্ন; এটি শুধু একটি column vector-এর নাম। α = β = 1/√2 হলে অবস্থাটি একটি superposition: মাপলে 0 আর 1 সমান সম্ভাবনায় আসে। এটিকে প্রায়ই “একসাথে 0 আর 1” বলা হয়, কিন্তু কথাটি বিভ্রান্তিকর। মাপলে একটিই ফল আসে, আর মাপার আগের অবস্থা থেকে বাড়তি কিছু “পড়া” যায় না। (1/√2)(|0⟩ + |1⟩) আর (1/√2)(|0⟩ − |1⟩) মাপলে হুবহু একই পরিসংখ্যান দেয়, অথচ তারা আলাদা অবস্থা। পার্থক্যটি ধরা পড়ে শুধু পরের gate-গুলোর interference-এ।

Complexity-র দৃষ্টিতে তুলনাটি এভাবে লেখা যায়। Probabilistic যন্ত্রের একটি ধাপ হলো একটি stochastic matrix দিয়ে গুণ: সব ঘর ≥ 0, প্রতিটি কলামের যোগফল 1, তাই সম্ভাবনার যোগফল (1-norm) রক্ষা পায়। Quantum যন্ত্রের একটি ধাপ হলো একটি unitary matrix দিয়ে গুণ, যা amplitude-এর বর্গের যোগফল (2-norm) রক্ষা করে। দুই মডেলেই অবস্থা একটি 2n মাত্রার vector; পার্থক্য শুধু কোন norm আর কোন চিহ্ন অনুমোদিত। এই ছোট পার্থক্য থেকেই পরের সব algorithm-এর শক্তি আসে।

নিচের stepper একটি qubit-এ Hadamard gate H (অংশ ২-এ সংজ্ঞা) প্রয়োগ করে দেখায় কীভাবে একই সম্ভাবনা থেকে দুটি আলাদা ভবিষ্যৎ আসে।

1q ← |0⟩2q ← H q3এখনই measure?4নাকি q ← H q5H, Z, H একসাথে
অবস্থা = α∣0⟩ + β∣1⟩
(α, β)
P(0), P(1)
  1. শুরু. q = |0⟩, অর্থাৎ α = 1, β = 0. মাপলে নিশ্চিতভাবে 0.
  2. H প্রয়োগ. H|0⟩ = (|0⟩ + |1⟩)/√2, তাই α = β = 1/√2 ≈ 0.707. মাপলে 0 আর 1 প্রতিটি ½ সম্ভাবনায়, ঠিক একটি ন্যায্য মুদ্রার মতো।
  3. এখনই মাপলে. ফল 0 বা 1, প্রতিটি ½ সম্ভাবনায়, আর অবস্থা ভেঙে |0⟩ বা |1⟩ হয়ে যায়। এরপর আরেকটি H দিলে আবার ৫০–৫০; superposition-এর তথ্য হারিয়ে গেছে।
  4. না মেপে আবার H. H(|0⟩ + |1⟩)/√2 = ½(|0⟩ + |1⟩) + ½(|0⟩ − |1⟩) = |0⟩. |1⟩-এর দুটি অবদান +½ আর −½ কেটে গেল। মুদ্রা দুবার ছুড়লে এমন হয় না; এটিই interference.
  5. মাঝে Z. Z শুধু |1⟩-এর চিহ্ন উল্টায়: (|0⟩ − |1⟩)/√2. এবার H দিলে কাটে |0⟩-এর অবদান, ফল নিশ্চিত |1⟩. ধাপ ২ আর এই অবস্থার পরিসংখ্যান একই ছিল, তবু ভবিষ্যৎ আলাদা।

২ · অনেক qubit, gate আর circuit

দুটি qubit-এর ভিত্তি-অবস্থা চারটি: |00⟩, |01⟩, |10⟩, |11⟩, আর সাধারণ অবস্থা এদের একটি রৈখিক সমন্বয়, চারটি amplitude-এর বর্গের যোগফল 1. সাধারণভাবে n qubit-এর অবস্থা ℂ2n-এর একটি একক vector: 2n-টি amplitude, প্রতিটি n-bit string x-এর জন্য একটি। দুটি আলাদা অবস্থা জোড়া লাগানো হয় tensor product দিয়ে: (a|0⟩ + b|1⟩) ⊗ (c|0⟩ + d|1⟩) = ac|00⟩ + ad|01⟩ + bc|10⟩ + bd|11⟩. এই সূচকীয় বৃদ্ধিই classical simulation-কে কঠিন করে: 40 qubit-এর পুরো state vector রাখতে 240-টি complex সংখ্যা, প্রতিটি 16 byte ধরলে 16 TiB memory.

Quantum যন্ত্রের প্রতিটি ধাপ (measurement ছাড়া) একটি unitary matrix U দিয়ে গুণ: U†U = I, যেখানে U† হলো conjugate transpose. Unitary matrix vector-এর দৈর্ঘ্য বদলায় না, তাই সম্ভাবনার যোগফল 1-ই থাকে; আর U† দিয়ে উল্টে আগের অবস্থায় ফেরা যায়। অর্থাৎ প্রতিটি quantum gate উল্টানো যায়; একমাত্র অপরিবর্তনীয় ধাপ measurement. জ্যামিতির ভাষায় unitary হলো ঘূর্ণন আর প্রতিফলনের complex সংস্করণ (মেশিন লার্নিং কোর্সের পর্ব ০৭-এ বাস্তব matrix-এর ঘূর্ণন আর projection আছে)।

GateMatrix বা কাজমন্তব্য
X[0 1; 1 0]: |0⟩ ↔ |1⟩classical NOT
Z[1 0; 0 −1]: |1⟩ → −|1⟩phase উল্টানো; classical সমতুল্য নেই
H (Hadamard)(1/√2)[1 1; 1 −1]|0⟩ → (|0⟩ + |1⟩)/√2, |1⟩ → (|0⟩ − |1⟩)/√2; H · H = I
S, T (phase gate)diag(1, i), diag(1, eiπ/4)S · S = Z, T · T = S
CNOT|c, t⟩ → |c, t ⊕ c⟩control c = 1 হলে target উল্টায়; দুই qubit
Toffoli (CCX)|a, b, t⟩ → |a, b, t ⊕ (a ∧ b)⟩উল্টানো যায় এমন AND; t = 0 হলে a ∧ b লেখে

একটি quantum circuit হলো qubit-গুলোর ওপর এমন gate-এর একটি ক্রম, শেষে কিছু qubit-এর measurement. পর্ব ৭০-এর Boolean circuit-এর সঙ্গে মিল স্পষ্ট, পার্থক্য দুটি: প্রতিটি gate উল্টানো যায় (তাই input আর output-এর qubit-সংখ্যা সমান), আর মানগুলো 0/1 নয়, amplitude. {H, T, CNOT} একটি universal gate set: যেকোনো unitary-কে এদের দিয়ে ইচ্ছেমতো কাছাকাছি নকল করা যায়, আর Solovay–Kitaev theorem (১৯৯০-এর দশকের শেষভাগ) অনুসারে নির্ভুলতা ε পেতে gate লাগে শুধু polylog(1/ε) গুণ।

CNOT দিয়ে এমন অবস্থা তৈরি হয়, যা দুটি আলাদা qubit-এর গুণফল নয়। |00⟩-এ প্রথম qubit-এ H, তারপর CNOT দিলে Bell অবস্থা (|00⟩ + |11⟩)/√2 পাওয়া যায়।

দাবি ২.১ (Bell অবস্থা entangled)

(|00⟩ + |11⟩)/√2-কে কোনো a, b, c, d-এর জন্য (a|0⟩ + b|1⟩) ⊗ (c|0⟩ + d|1⟩) আকারে লেখা যায় না।

প্রমাণ।

  1. ধরুন লেখা যায়। Tensor product খুললে ac|00⟩ + ad|01⟩ + bc|10⟩ + bd|11⟩. — সংজ্ঞা
  2. মেলালে ac = bd = 1/√2 আর ad = bc = 0. — সহগ তুলনা
  3. ad = 0 মানে a = 0 বা d = 0. a = 0 হলে ac = 0, d = 0 হলে bd = 0; দুটিই ধাপ ২-এর বিরোধী। ∎

এমন অবস্থাকে বলে entanglement: দুটি qubit মাপলে ফল সবসময় মেলে (00 বা 11), অথচ কোনো qubit-এর আলাদা কোনো “নিজস্ব” অবস্থা নেই। নিচের ব্লকে একটি ছোট state-vector simulator আছে: gate মানে matrix-গুণ, measurement মানে |αx|2 সম্ভাবনায় x বাছাই। Stepper-এর সব অবস্থা এখানে হিসাব হয়, শেষে Bell অবস্থা ১০০০ বার মাপা হয়।

# A tiny state-vector simulator: n qubits = 2^n complex amplitudes.
import numpy as np
H = np.array([[1, 1], [1, -1]]) / np.sqrt(2)
X = np.array([[0, 1], [1, 0]]); Z = np.diag([1, -1])
def apply(state, gate, q, n):       # gate on qubit q (qubit 0 = leftmost bit)
    ops = [gate if i == q else np.eye(2) for i in range(n)]
    U = ops[0]
    for op in ops[1:]: U = np.kron(U, op)
    return U @ state
def cnot(state, c, t, n):           # flip bit t of every basis state whose bit c is 1
    new = state.copy()
    for i in range(2 ** n):
        if (i >> (n - 1 - c)) & 1: new[i ^ (1 << (n - 1 - t))] = state[i]
    return new
def show(name, s):
    n = int(np.log2(len(s)))
    parts = [f"{a.real:+.3f}|{i:0{n}b}>" for i, a in enumerate(s) if abs(a) > 1e-9]
    print(f"{name:12} {' '.join(parts):32} P = {np.round(np.abs(s) ** 2, 3)}")
zero = np.array([1, 0], dtype=complex)
show("|0>", zero)
show("H|0>", apply(zero, H, 0, 1))
show("H H|0>", apply(apply(zero, H, 0, 1), H, 0, 1))
show("H X|0>", apply(apply(zero, X, 0, 1), H, 0, 1))
show("H Z H|0>", apply(apply(apply(zero, H, 0, 1), Z, 0, 1), H, 0, 1))
bell = cnot(apply(np.kron(zero, zero), H, 0, 2), 0, 1, 2)
show("Bell", bell)
rng = np.random.default_rng(75)     # measurement: outcome i with probability |a_i|^2
shots = rng.choice(4, size=1000, p=np.abs(bell) ** 2)
print("1000 measurements of Bell:", {f"{i:02b}": int((shots == i).sum()) for i in range(4)})

আসল আউটপুট (ব্রাউজারের Python):

|0>          +1.000|0>                        P = [1. 0.]
H|0>         +0.707|0> +0.707|1>              P = [0.5 0.5]
H H|0>       +1.000|0>                        P = [1. 0.]
H X|0>       +0.707|0> -0.707|1>              P = [0.5 0.5]
H Z H|0>     +1.000|1>                        P = [0. 1.]
Bell         +0.707|00> +0.707|11>            P = [0.5 0.  0.  0.5]
1000 measurements of Bell: {'00': 504, '01': 0, '10': 0, '11': 496}

প্রথম পাঁচ লাইন stepper-এর পাঁচটি অবস্থা: H|0⟩-এ দুটি amplitude +0.707, H H|0⟩-এ আবার শুধু |0⟩, আর H Z H|0⟩ = |1⟩. চতুর্থ লাইনে H X|0⟩ = H|1⟩-এর |1⟩-amplitude −0.707, অথচ সম্ভাবনা H|0⟩-এর মতোই [0.5 0.5]: চিহ্ন সম্ভাবনায় দেখা যায় না। Bell অবস্থায় শুধু |00⟩ আর |11⟩; ১০০০ বার মাপায় 01 বা 10 একবারও আসেনি, আর 00 ও 11 প্রায় সমান। লক্ষ করুন, simulator 2n × 2n matrix বানায়; n বাড়লে এটি দ্রুত অচল হয়, যা অংশ ৭-এর প্রশ্নের মূলে।

৩ · BQP — quantum যন্ত্রের দক্ষ গণনার শ্রেণি

BPP-র মতোই BQP-র সংজ্ঞায় তিনটি অংশ: একটি polynomial আকারের যন্ত্র, প্রতিটি input-এর জন্য ভুলের সীমা, আর যন্ত্রগুলো দক্ষভাবে লেখা যায় এমন শর্ত। Circuit-এর ভাষায় লেখা সবচেয়ে সহজ (Yao ১৯৯৩ সালে দেখান বলে পরিচিত, quantum Turing machine আর quantum circuit polynomial খরচে সমতুল্য)।

সংজ্ঞা ৩.১ (BQP, bounded-error quantum polynomial time)

একটি ভাষা A ∈ BQP, যদি quantum circuit-এর একটি polynomial-time uniform circuit family {Cn} থাকে, যার প্রতিটি Cn gate set {H, T, CNOT} থেকে বানানো, আকার n-এর polynomial, আর n + m(n)-টি qubit-এ কাজ করে (m একটি polynomial), এমনভাবে যে দৈর্ঘ্য n-এর প্রতিটি w-এর জন্য Cn-কে |w⟩|0m(n)⟩-এ চালিয়ে প্রথম qubit মাপলে:

w ∈ A ⇒ Pr[ফল 1] ≥ 2/3,     w ∉ A ⇒ Pr[ফল 1] ≤ 1/3

“Uniform” শর্ত জরুরি: নইলে প্রতিটি n-এর জন্য আলাদা, অগণনযোগ্যভাবে বাছা circuit একটি undecidable ভাষাও “চিনতে” পারত, যেমন P/poly-তে হয় (পর্ব ৭০)। ভুলের 1/3 সংখ্যাটির কোনো বিশেষত্ব নেই: circuit-টি k বার চালিয়ে সংখ্যাগরিষ্ঠ ভোট নিলে ভুল exponential হারে কমে, পর্ব ৬৯-এর amplification-এর হুবহু যুক্তিতে। অন্য যেকোনো যুক্তিসংগত universal gate set নিলেও একই শ্রেণি পাওয়া যায়, Solovay–Kitaev-এর কারণে। ইতিহাস: Deutsch ১৯৮৫ সালে quantum Turing machine সংজ্ঞায়িত করেন; Bernstein আর Vazirani ১৯৯৩ সালে BQP সংজ্ঞায়িত করে BQP ⊆ PSPACE প্রমাণ করেন বলে পরিচিত।

উপপাদ্য ৩.২ (জানা অন্তর্ভুক্তি)

P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE.

প্রমাণের রূপরেখা।

  1. P ⊆ BQP: যেকোনো Boolean circuit-কে Toffoli gate দিয়ে উল্টানো যায় এমন circuit-এ বদলানো যায়, বাড়তি “আবর্জনা” qubit রেখে (Bennett-এর reversible computation, ১৯৭৩); ভিত্তি-অবস্থায় Toffoli একটি permutation, তাই সেটিই একটি quantum circuit. আর Toffoli নিজে H, T, CNOT দিয়ে হুবহু বানানো যায়। — reversible simulation
  2. BPP ⊆ BQP: একটি নতুন |0⟩-এ H দিয়ে মাপলে একটি ন্যায্য মুদ্রা মেলে। সব মুদ্রা শুরুতেই এভাবে বানিয়ে বাকি গণনা ধাপ ১-এর মতো চালানো যায়; ভুলের সীমা অপরিবর্তিত। (মাপাটাও শেষ পর্যন্ত পিছিয়ে দেওয়া যায়: deferred measurement.) — H দিয়ে মুদ্রা
  3. BQP ⊆ PSPACE: শেষ অবস্থার একটি amplitude হলো αT(y) = Σx UT[y, x] · αT−1(x). প্রতিটি gate বড়জোর দুটি qubit ছোঁয়, তাই যোগফলে বড়জোর চারটি অশূন্য পদ। এই recursion depth-first চালালে জায়গা লাগে প্রতি স্তরে O(n + m) bit, মোট O(T · (n + m)): polynomial, সময় exponential. তারপর y-এর ওপর একটি counter চালিয়ে Σy: প্রথম bit 1 |αT(y)|2 যোগ করে 1/2-এর সঙ্গে তুলনা। — পথ ধরে যোগফল, জায়গা পুনর্ব্যবহার
  4. BQP ⊆ PP আরও সূক্ষ্ম (Adleman, DeMarrais আর Huang ১৯৯৭ বলে পরিচিত): ধাপ ৩-এর পথ-যোগফলকে ধনাত্মক আর ঋণাত্মক পথের গণনার পার্থক্য হিসেবে লেখা যায়, আর PP ঠিক এমন গণনা তুলনা করতে পারে। PP ⊆ PSPACE পর্ব ৬৯-এ প্রমাণিত। ∎

ধাপ ৩-এর একটি সূক্ষ্মতা: H আর T-এর amplitude 1/√2 আর eiπ/4-এর মতো অমূলদ সংখ্যা। তবে এরা সবই Q(√2, i)-এর মতো একটি সসীম বীজগণিতীয় field-এ থাকে, যেখানে হুবহু হিসাব সম্ভব, অথবা যথেষ্ট নির্ভুলতায় গোল করা যায়। এই উপপাদ্যের একটি তাৎক্ষণিক ফল: quantum computer কোনো undecidable সমস্যা সমাধান করে না। প্রতিটি quantum circuit একটি সাধারণ Turing machine exponential সময়ে নকল করতে পারে, তাই পর্ব ৪৭-এর Church–Turing thesis অটুট থাকে। প্রশ্ন শুধু দক্ষতার: তা নিয়ে অংশ ৭।

৪ · Deutsch–Jozsa — এক query-তে নিশ্চিত উত্তর

প্রথম algorithm-টি একটি query complexity-র প্রশ্ন: একটি function f: {0, 1}n → {0, 1} একটি “কালো বাক্স” (oracle) হিসেবে দেওয়া; প্রতিবার একটি x দিলে বাক্স f(x) জানায়। খরচ গোনা হয় query-র সংখ্যায়। বাজারঘরের একটি পুরনো ছাড়-যাচাই module ভাবুন, যার code হারিয়ে গেছে: হয় সব কোডে একই উত্তর দেয় (constant), নয়তো ঠিক অর্ধেক কোডে “হ্যাঁ” (balanced); অন্য কোনো রকম নয়। এটি একটি promise problem: প্রতিশ্রুতির বাইরের input নিয়ে কোনো দাবি নেই।

উপপাদ্য ৪.১ (deterministic নিম্নসীমা)

যেকোনো deterministic classical algorithm-কে সবচেয়ে খারাপ ক্ষেত্রে 2n−1 + 1টি query করতে হয়, আর এতগুলো যথেষ্ট।

প্রমাণ, একটি adversary argument দিয়ে।

  1. প্রতিপক্ষ প্রথম 2n−1টি আলাদা query-র প্রতিটিতে উত্তর দেয় 0. — প্রতিপক্ষের কৌশল
  2. এই অবস্থায় দুটি function উত্তরগুলোর সঙ্গে খাপ খায়: constant f ≡ 0, আর একটি balanced f, যা জিজ্ঞাসিত 2n−1টি x-এ 0 আর বাকি 2n−1টিতে 1. — দুটিই প্রতিশ্রুতি মানে
  3. Algorithm এখানে থামলে দুই ক্ষেত্রে একই উত্তর দেয়, তাই একটিতে ভুল। অতএব অন্তত 2n−1 + 1টি query লাগে। — deterministic মানে একই ইতিহাসে একই উত্তর
  4. যথেষ্টতা: 2n−1 + 1টি আলাদা x-এ সব উত্তর সমান হলে f balanced হতে পারে না, কারণ balanced f-এ প্রতিটি মান ঠিক 2n−1বার আসে। ∎

Quantum algorithm (Deutsch আর Jozsa, ১৯৯২; পরে Cleve, Ekert, Macchiavello আর Mosca-র উন্নত রূপ) একটি query-তেই নিশ্চিত উত্তর দেয়। Oracle হলো unitary Uf|x⟩|y⟩ = |x⟩|y ⊕ f(x)⟩. বাড়তি qubit-টি (ancilla) যদি |−⟩ = (|0⟩ − |1⟩)/√2 অবস্থায় থাকে, তাহলে Uf|x⟩|−⟩ = (−1)f(x)|x⟩|−⟩: f-এর মান amplitude-এর চিহ্নে উঠে আসে। একে বলে phase oracle বা phase kickback.

Deutsch–Jozsa circuit, n = 2

বাঁ থেকে ডানে সময়। ওপরের দুটি তার input qubit, নিচেরটি ancilla.

Deutsch–Jozsa circuit: H on all, one U_f query, H on inputs, measure |0⟩ |0⟩ |1⟩ H H H H H U f একটি query মাপা 00 → constant অন্য → balanced
ছবি ৭৫.১ — ancilla |1⟩-এ H দিলে |−⟩ হয়, তাই Uf শুধু চিহ্ন বদলায়। শেষে input qubit-গুলো মাপা হয়; ancilla আর দরকার নেই।
উপপাদ্য ৪.২ (Deutsch–Jozsa)

উপরের circuit শেষে 0n মাপে সম্ভাবনা 1-এ, যদি f constant; আর সম্ভাবনা 0-তে, যদি f balanced.

প্রমাণ।

  1. H⊗n|0n⟩ = 2−n/2 Σx |x⟩, সব 2nটি x সমান amplitude-এ। — প্রতিটি qubit-এ H
  2. Phase oracle-এর পর: 2−n/2 Σx (−1)f(x) |x⟩. — phase kickback
  3. H⊗n|x⟩ = 2−n/2 Σy (−1)x·y |y⟩, যেখানে x·y = Σ xiyi mod 2. y = 0n-এ x·y = 0, তাই শেষ অবস্থায় |0n⟩-এর amplitude = 2−n Σx (−1)f(x). — H-এর সূত্র
  4. f constant হলে যোগফল ±2n, amplitude ±1, সম্ভাবনা 1. f balanced হলে +1 আর −1 ঠিক সমান সংখ্যায়, যোগফল 0, সম্ভাবনা 0. ∎
1|00⟩ (ancilla |−⟩)2H ⊗ H3U_f একবার: চিহ্ন (−1)^f(x)4H ⊗ H5মাপা: 00 কি না?
f(00) = 0, f(01) = 0, f(10) = 1, f(11) = 1
amp 00, 01
amp 10, 11
P[00]
  1. শুরু. Input |00⟩, ancilla |−⟩. f(x1x2) = x1: অর্ধেক input-এ 0, অর্ধেকে 1, তাই balanced.
  2. H ⊗ H. চারটি ভিত্তি-অবস্থার প্রতিটির amplitude ½; মাপলে প্রতিটি ¼ সম্ভাবনায়।
  3. একটি query. f(10) = f(11) = 1, তাই এই দুটির চিহ্ন উল্টায়: (½, ½, −½, −½). সম্ভাবনা বদলায়নি, শুধু চিহ্ন।
  4. আবার H ⊗ H. |00⟩-এর amplitude = ½(½ + ½ − ½ − ½) = 0: অবদানগুলো কেটে গেল। |10⟩-এর amplitude = ½(½ + ½ + ½ + ½) = 1. f constant (যেমন f ≡ 0) হলে এখানে সব ভার যেত |00⟩-এ।
  5. মাপা. ফল নিশ্চিত 10, যা 00 নয়, তাই উত্তর “balanced”, ভুলের সম্ভাবনা শূন্য। Deterministic যন্ত্রের এখানে 21 + 1 = 3টি query লাগত।

নিচের ব্লক n = 2-এ প্রতিশ্রুতি মানে এমন সব ৮টি function (২টি constant, ৬টি balanced), আর n = 3-এর সব ৭০টি balanced function-এ algorithm চালায়।

# Deutsch-Jozsa: one oracle query decides "constant or balanced" with certainty.
import numpy as np
from itertools import product
def hadamard_all(n):                 # H tensor H tensor ... (n times), a 2^n x 2^n matrix
    H = np.array([[1, 1], [1, -1]]) / np.sqrt(2); U = np.array([[1.0]])
    for _ in range(n): U = np.kron(U, H)
    return U
def dj(f_table, n):                  # returns P[measure 0...0]
    Hn = hadamard_all(n)
    s = Hn @ np.eye(2 ** n)[0]       # H^n |0...0>: equal superposition
    s = s * (-1.0) ** np.array(f_table)  # phase oracle: |x> -> (-1)^f(x) |x>
    s = Hn @ s                       # H^n again: interference
    return abs(s[0]) ** 2
print("n = 2: f(00) f(01) f(10) f(11) -> P[00]   kind")
for f in product((0, 1), repeat=4):
    kind = {0: "constant", 4: "constant", 2: "balanced"}.get(sum(f), "neither")
    if kind != "neither":
        print(f"        {f}      {dj(f, 2):.3f}   {kind}")
n, N = 3, 8
probs = [dj(t, n) for t in product((0, 1), repeat=N) if sum(t) == N // 2]
print(f"n = 3: {len(probs)} balanced functions, max P[000] = {max(probs):.3f};",
      f"constant gives {dj([0] * N, n):.3f}; deterministic needs {N // 2 + 1} queries")
print("not promised, f = 1 only on 00 (n = 2): P[00] =", round(dj((1, 0, 0, 0), 2), 3))

আসল আউটপুট (ব্রাউজারের Python):

n = 2: f(00) f(01) f(10) f(11) -> P[00]   kind
        (0, 0, 0, 0)      1.000   constant
        (0, 0, 1, 1)      0.000   balanced
        (0, 1, 0, 1)      0.000   balanced
        (0, 1, 1, 0)      0.000   balanced
        (1, 0, 0, 1)      0.000   balanced
        (1, 0, 1, 0)      0.000   balanced
        (1, 1, 0, 0)      0.000   balanced
        (1, 1, 1, 1)      1.000   constant
n = 3: 70 balanced functions, max P[000] = 0.000; constant gives 1.000; deterministic needs 5 queries
not promised, f = 1 only on 00 (n = 2): P[00] = 0.25

দুটি constant function-এ P[00] = 1, ছয়টি balanced-এ 0; n = 3-এর ৭০টি balanced function-এর একটিতেও 000 আসেনি, যেখানে deterministic যন্ত্রের ৫টি query লাগত। শেষ লাইন প্রতিশ্রুতির গুরুত্ব দেখায়: যে f শুধু একটি input-এ 1, সেটি constant-ও নয়, balanced-ও নয়; সেখানে P[00] = (1 − 2/4)2 = 0.25, কোনো নিশ্চিত উত্তর নেই।

সত্যিকারের run (ডেস্কটপ, uv প্রকল্পে qiskit 2.6.2, Apache-2.0 licence, Python 3.12.13; qiskit-এর নিজস্ব statevector sampler, কোনো hardware নয়)। qiskit-এ কোনো usage-reporting বা telemetry নেই: installed package-এর Python code-এ network ব্যবহার নেই, আর compiled অংশে network library যুক্ত নেই, তা আগে পরীক্ষা করা হয়েছে। n = 3, ancilla-সহ চারটি qubit, oracle f(x) = x0 ⊕ x1 ⊕ x2 তিনটি CNOT দিয়ে:

~/bazarghar-toc$ uv add qiskit
 + qiskit==2.6.2
 + numpy==2.5.5
 …
~/bazarghar-toc$ uv run python grover_dj.py
python 3.12.13 | qiskit 2.6.2 | numpy 2.5.5
…
Deutsch-Jozsa, balanced f, 1000 shots: {'111': 1000}
Deutsch-Jozsa, constant f, 1000 shots: {'000': 1000}

Balanced f-এ ১০০০ বারের প্রতিবার 111, কখনো 000 নয়; constant f-এ প্রতিবার 000. XOR function-এর জন্য ফলটি হুবহু অনুমানযোগ্য: H⊗3 সব ভার পাঠায় y = 111-এ, কারণ (−1)f(x) = (−1)x·111.

বাড়িয়ে বলবেন না: এই ব্যবধান শুধু deterministic আর নির্ভুল classical algorithm-এর বিপক্ষে। একটি randomized algorithm k-টি এলোমেলো x-এ f দেখে: দুই রকম মান পেলে “balanced”, নইলে “constant” বলে। Constant f-এ সে কখনো ভুল করে না; balanced f-এ ভুল করে শুধু যখন সব k মান সমান, সম্ভাবনা 2 · 2−k. দশটি query-তে ভুল ≤ 1/512. Randomized classical যন্ত্রের সঙ্গে exponential ব্যবধান প্রথম দেখা যায় Simon-এর ১৯৯৪ সালের সমস্যায় (ভাবনার প্রশ্ন ২)।

৫ · Grover — কাঠামোহীন খোঁজে √N

বাজারঘরের ছাড়-যাচাই বাক্সে N = 2nটি সম্ভাব্য কোড, যার ঠিক একটি বৈধ, আর বাক্স শুধু “হ্যাঁ/না” বলে। কোনো কাঠামো জানা না থাকলে classical যন্ত্রকে (randomized হলেও) গড়ে প্রায় N/2টি কোড চেষ্টা করতে হয়। Grover-এর algorithm (Lov Grover, ১৯৯৬) প্রায় (π/4)√N query-তে বৈধ কোডটি খুঁজে পায়।

Algorithm-এর প্রতিটি ধাপ (Grover iteration) দুটি প্রতিফলন:

  • Oracle O: বৈধ কোড w-এর amplitude-এর চিহ্ন উল্টানো, অর্থাৎ phase oracle.
  • Diffusion D = 2|s⟩⟨s| − I: এখানে |s⟩ = H⊗n|0n⟩ সমান superposition. প্রতিটি amplitude-এর ওপর D-এর কাজ খুব সহজ: ax → 2 · (গড়) − ax, অর্থাৎ গড়ের সাপেক্ষে প্রতিফলন. বানাতে লাগে H⊗n, একটি বহু-control-এর phase gate আর আবার H⊗n.
উপপাদ্য ৫.১ (Grover)

sin θ = 1/√N ধরুন। |s⟩ থেকে শুরু করে k-টি Grover iteration-এর পর মাপলে w পাওয়ার সম্ভাবনা ঠিক sin2((2k + 1)θ). k = ⌊π/(4θ)⌋ নিলে এই সম্ভাবনা ≥ 1 − 1/N, আর k ≤ (π/4)√N.

প্রমাণ।

  1. |s′⟩ = বাকি N − 1টি কোডের সমান superposition ধরুন। তাহলে |s⟩ = sin θ |w⟩ + cos θ |s′⟩, আর পুরো প্রক্রিয়া |w⟩ আর |s′⟩-এর দুই-মাত্রার সমতলে থাকে। — |w⟩ ⊥ |s′⟩
  2. এই সমতলে O হলো |s′⟩ অক্ষের সাপেক্ষে প্রতিফলন (|w⟩-এর অংশের চিহ্ন উল্টায়), আর D হলো |s⟩-এর সাপেক্ষে প্রতিফলন। — দুটির সংজ্ঞা
  3. দুটি অক্ষের মধ্যে কোণ θ হলে পরপর দুটি প্রতিফলন হলো 2θ ঘূর্ণন। তাই k iteration-এর পর অবস্থা sin((2k + 1)θ)|w⟩ + cos((2k + 1)θ)|s′⟩. — সমতলের জ্যামিতি
  4. (2k + 1)θ যত কাছে π/2-এর, সম্ভাবনা তত কাছে 1-এর। k = ⌊π/(4θ)⌋ নিলে (2k + 1)θ আর π/2-এর পার্থক্য ≤ θ, তাই সম্ভাবনা ≥ cos2 θ = 1 − 1/N. আর θ ≥ sin θ = 1/√N থেকে k ≤ (π/4)√N. ∎

বৈধ কোড একাধিক হলে, ধরুন t-টি, একই প্রমাণে sin θ = √(t/N), আর দরকার প্রায় (π/4)√(N/t) iteration. t জানা না থাকলে iteration-এর সংখ্যা এলোমেলোভাবে বাড়িয়ে বাড়িয়ে চেষ্টা করার একটি কৌশল আছে (Boyer, Brassard, Høyer আর Tapp, ১৯৯৮ সালের দিকে), যার প্রত্যাশিত খরচও O(√(N/t)). এই সাধারণ রূপকে বলে amplitude amplification: যেকোনো algorithm, যা p সম্ভাবনায় সফল, তাকে প্রায় 1/√p বার চালিয়েই উচ্চ সম্ভাবনায় সফল করা যায়, যেখানে classical পুনরাবৃত্তিতে লাগে প্রায় 1/p বার।

1s ← H⊗H⊗H |000⟩2O: a[101] ← −a[101]3D: a ← 2·গড় − a4২ আর ৩ আবার
sin θ = 1/√8, θ ≈ 20.7°
k
a[101]
অন্য ৭টি
P[101]
  1. শুরু. আটটি কোডের প্রতিটির amplitude 1/√8 ≈ 0.354; এখন মাপলে বৈধ কোড আসে 1/8 = 0.125 সম্ভাবনায়, অন্ধ অনুমানের মতো।
  2. Oracle. 101-এর amplitude −0.354. সম্ভাবনা বদলায়নি, কিন্তু গড় নেমে (7 · 0.354 − 0.354)/8 ≈ 0.265.
  3. Diffusion. গড়ের সাপেক্ষে প্রতিফলন: 101 → 2 · 0.265 + 0.354 ≈ 0.884, বাকিরা → 2 · 0.265 − 0.354 ≈ 0.177. P = 0.8842 ≈ 0.781, একটি query-তেই।
  4. দ্বিতীয় iteration. 101 → 0.972, বাকিরা −0.088 (ঋণাত্মক হয়ে গেল)। P ≈ 0.945. ⌊π/(4θ)⌋ = 2, তাই এখানেই থামা উচিত।
  5. তৃতীয় iteration — বাড়াবাড়ি. ঘূর্ণন π/2 পেরিয়ে গেছে: 101 → 0.575, P মাত্র 0.330. বেশি iteration মানে ভালো নয়; সংখ্যাটি আগে থেকে হিসাব করতে হয়।

নিচের ব্লক একই হিসাব করে, তারপর বড় N-এ k = ⌊(π/4)√N⌋ iteration-এর সাফল্যের সম্ভাবনা ছাপে। (এই N-গুলোতে ⌊(π/4)√N⌋ আর উপপাদ্যের ⌊π/(4θ)⌋ একই সংখ্যা দেয়।)

# Grover search on N = 2^n items, one marked item; amplitudes as a plain vector.
import numpy as np
from math import pi, sqrt, floor
def grover(N, marked, k):            # returns the state after k Grover iterations
    s = np.full(N, 1 / sqrt(N))      # H^n |0...0>
    for _ in range(k):
        s[marked] = -s[marked]       # oracle: flip the sign of the marked item
        s = 2 * s.mean() - s         # diffusion: reflect every amplitude about the mean
    return s
N, m = 8, 5                          # Bazarghar: 8 coupon slots, slot 5 (101) is valid
for k in range(5):
    s = grover(N, m, k)
    bars = "#" * round(40 * s[m] ** 2)
    print(f"N = 8, k = {k}: amp(marked) = {s[m]:+.3f}, other = {s[0]:+.3f},",
          f"P = {s[m] ** 2:.3f} {bars}")
print("   N   k = floor(pi/4*sqrt(N))   P[success]   classical avg (N+1)/2")
for n in (2, 4, 6, 8, 10, 12):
    N = 2 ** n; k = floor(pi / 4 * sqrt(N))
    print(f"{N:5}   {k:5}                    {grover(N, 1, k)[1] ** 2:.4f}       {(N + 1) / 2:7.1f}")

আসল আউটপুট (ব্রাউজারের Python):

N = 8, k = 0: amp(marked) = +0.354, other = +0.354, P = 0.125 #####
N = 8, k = 1: amp(marked) = +0.884, other = +0.177, P = 0.781 ###############################
N = 8, k = 2: amp(marked) = +0.972, other = -0.088, P = 0.945 ######################################
N = 8, k = 3: amp(marked) = +0.575, other = -0.309, P = 0.330 #############
N = 8, k = 4: amp(marked) = -0.110, other = -0.376, P = 0.012 
   N   k = floor(pi/4*sqrt(N))   P[success]   classical avg (N+1)/2
    4       1                    1.0000           2.5
   16       3                    0.9613           8.5
   64       6                    0.9966          32.5
  256      12                    0.9999         128.5
 1024      25                    0.9995         512.5
 4096      50                    0.9999        2048.5

প্রথম পাঁচ লাইন stepper-এর সংখ্যা মেলায়, আর k = 4-এ সম্ভাবনা প্রায় শূন্য (0.012): ঘূর্ণন অনেক দূর গেছে। সারণিতে N = 4-এ একটি iteration-এই সম্ভাবনা হুবহু 1; N = 4096-এ মাত্র ৫০টি query-তে 0.9999, যেখানে classical যন্ত্রের গড়ে প্রায় ২০৪৮টি লাগে। Query-র অনুপাত √N-এর মতো বাড়ে: N ৪ গুণ হলে k প্রায় ২ গুণ।

সত্যিকারের run, একই qiskit প্রকল্পে। এখানে oracle আর diffusion আসল gate দিয়ে বানানো (X, H আর Toffoli দিয়ে বহু-control-এর Z), তারপর statevector থেকে হুবহু সম্ভাবনা আর ১০০০টি নমুনা:

~/bazarghar-toc$ uv run python grover_dj.py
python 3.12.13 | qiskit 2.6.2 | numpy 2.5.5
Grover N=8, k=0: P[101] = 0.125
Grover N=8, k=1: P[101] = 0.781
Grover N=8, k=2: P[101] = 0.945
Grover N=8, k=3: P[101] = 0.330
k=2, 1000 shots: {'101': 945, '111': 10, '011': 10}
k=2 circuit: depth 22 | gate counts {'h': 23, 'x': 16, 'ccx': 4, 'measure': 3, 'barrier': 1}
…

Gate দিয়ে বানানো circuit-এর সম্ভাবনা ওপরের vector-হিসাবের সঙ্গে তিন দশমিক পর্যন্ত মেলে। ১০০০ বার মেপে 101 এসেছে ৯৪৫ বার। দুটি iteration-এ ৪টি Toffoli লেগেছে: প্রতিটি oracle আর প্রতিটি diffusion-এ একটি। N বাড়লে বহু-control gate-এর খরচ n-এর সঙ্গে বাড়ে, তাই মোট gate প্রায় √N · poly(n).

এর চেয়ে ভালো কি সম্ভব? না, black-box মডেলে। Bennett, Bernstein, Brassard আর Vazirani (প্রকাশ ১৯৯৭, BBBV নামে পরিচিত) দেখান, যেকোনো quantum algorithm-কে এই খোঁজে Ω(√N) query করতে হয়। এর সরাসরি অর্থ: n চলকের SAT-এ সব 2n মান-নির্ধারণ খুঁজে দেখার quantum রূপ প্রায় 2n/2 ধাপ নেয়, যা এখনো exponential. Grover বর্গমূলের লাভ দেয়, NP-complete সমস্যাকে polynomial করে না। ব্যবহারিক দিক থেকে এর একটি পরিচিত প্রভাব: symmetric key-এর brute-force খোঁজ বর্গমূলে নামে, তাই দীর্ঘমেয়াদি নিরাপত্তায় key-এর দৈর্ঘ্য বাড়ানোর পরামর্শ দেওয়া হয়।

৬ · Shor — factoring থেকে period খোঁজা

১৯৯৪ সালে Peter Shor দেখান, integer factorization আর discrete logarithm দুটিই quantum যন্ত্রে polynomial সময়ে করা যায়; এটিই Shor-এর algorithm নামে পরিচিত। N-এর bit-সংখ্যা n হলে gate-সংখ্যা সাধারণ গুণের পদ্ধতিতে মোটামুটি n3-এর ক্রমে; classical যন্ত্রে জানা সবচেয়ে ভালো পদ্ধতি (number field sieve) প্রায় exp(n1/3)-এর ক্রমে, subexponential কিন্তু polynomial নয়। Algorithm-এর মূল কৌশল একটি classical reduction: factoring-কে order finding-এ নামানো।

Reduction (factoring → order finding)

N বিজোড়, যৌগিক আর কোনো মৌলিকের ঘাত নয় (এগুলো classical-ভাবে সহজে ধরা যায়)। 1 < a < N এলোমেলো নিন। gcd(a, N) > 1 হলে সেটিই একটি উৎপাদক। নইলে a-এর order r = সবচেয়ে ছোট r ≥ 1, যাতে ar ≡ 1 (mod N). r জোড় আর h = ar/2 ≢ −1 (mod N) হলে N ভাগ করে (h − 1)(h + 1), কিন্তু কোনো একটিকে নয়, তাই gcd(h − 1, N) একটি প্রকৃত উৎপাদক। এলোমেলো a-তে এমন “ভালো” ঘটনার সম্ভাবনা অন্তত ½ (সংখ্যাতত্ত্বের একটি প্রমাণিত ফল; প্রমাণ এখানে বাদ)।

সংখ্যাতত্ত্বের দিকটি, অর্থাৎ gcd, modular ঘাত আর RSA-র গণিত, ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ২১ আর পর্ব ২৮-এ আছে। নিচের stepper ছোট N = 15-এ পুরো classical কাঠামো চালায়; শুধু ধাপ ২-এর r খোঁজাটাই quantum অংশ।

1a বাছা, gcd(a, N)2order r (quantum অংশ)3r জোড়? h = a^(r/2) ≠ −1?4gcd(h ± 1, N)
N = 15
a
aˣ mod 15
h
ফল
  1. a বাছা. a = 7, gcd(7, 15) = 1, তাই সরাসরি উৎপাদক মেলেনি; order খুঁজতে হবে।
  2. Order. 7x mod 15 = 1, 7, 4, 13, 1, …: ধারাটি period r = 4-এ ঘোরে। বড় N-এ এই period খোঁজাই কঠিন অংশ, আর এখানেই quantum যন্ত্র লাগে।
  3. শর্ত দেখা. r = 4 জোড়। h = 72 mod 15 = 49 mod 15 = 4, যা −1 ≡ 14 নয়। শর্ত পূরণ।
  4. উৎপাদক. (h − 1)(h + 1) = 3 · 5 = 15 ≡ 0 (mod 15). gcd(3, 15) = 3, gcd(5, 15) = 5, আর 3 · 5 = 15.
  5. খারাপ a. a = 14 নিলে 142 = 196 ≡ 1, তাই r = 2, কিন্তু h = 14 ≡ −1. gcd(13, 15) = 1 আর gcd(15, 15) = 15: কোনো প্রকৃত উৎপাদক নেই। নতুন a বেছে আবার চেষ্টা করতে হয়।

Quantum অংশের ধারণা। Q = 2q ≥ N2 নিয়ে প্রথম register-এ সব x-এর সমান superposition বানানো হয়, দ্বিতীয় register-এ ax mod N হিসাব করা হয় (classical গুণের reversible রূপ)। তারপর প্রথম register-এ quantum Fourier transform (QFT): এটি ঠিক Fourier transform, কিন্তু 2q-টি amplitude-এর ওপর মাত্র O(q2)টি gate দিয়ে। Period r-এর একটি ধারার Fourier transform-এর চূড়া পড়ে Q/r-এর গুণিতকের কাছে। মাপলে একটি y আসে, যেখানে y/Q ≈ c/r, আর continued fraction দিয়ে c/r পাওয়া যায়। নিচের JavaScript ব্লক N = 21, a = 2-এর জন্য এই সম্ভাবনাগুলো হুবহু হিসাব করে, তবে সাধারণ কম্পিউটারে, সব 512টি x ধরে: এটি একটি exponential খরচের নকল, quantum যন্ত্র নয়।

// Shor's period finding for N = 21, a = 2, simulated classically (exponential work!)
const N = 21, a = 2, Q = 512;            // Q = 2^9 >= N^2 = 441
const f = []; let v = 1;
for (let x = 0; x < Q; x++) { f.push(v); v = (v * a) % N; }
// P[y] = (1/Q^2) * sum over z of | sum over x with f(x) = z of e^(2 pi i x y / Q) |^2
const P = [];
for (let y = 0; y < Q; y++) {
  const re = {}, im = {};
  for (let x = 0; x < Q; x++) {
    const t = 2 * Math.PI * x * y / Q, z = f[x];
    re[z] = (re[z] || 0) + Math.cos(t); im[z] = (im[z] || 0) + Math.sin(t);
  }
  let s = 0; for (const z in re) s += re[z] ** 2 + im[z] ** 2;
  P.push(s / (Q * Q));
}
function denom(y) {                      // continued fractions of y/Q: last denominator < N
  let [p0, q0, p1, q1] = [0, 1, 1, 0], num = y, den = Q, best = 1;
  while (den !== 0) {
    const t = Math.floor(num / den); [num, den] = [den, num - t * den];
    [p0, q0, p1, q1] = [p1, q1, t * p1 + p0, t * q1 + q0];
    if (q1 < N) best = q1; else break;
  }
  return best;
}
const peaks = [...P.keys()].sort((i, j) => P[j] - P[i]).slice(0, 6).sort((i, j) => i - j);
console.log("  y    P[y]   bar                    y/512 -> r?  2^r mod 21");
for (const y of peaks) {
  const r = denom(y), check = Number((2n ** BigInt(r)) % 21n);
  console.log(String(y).padStart(3), P[y].toFixed(3).padStart(7), " " + "#".repeat(Math.round(P[y] * 100)).padEnd(22),
    String(r).padStart(4), String(check).padStart(9), check === 1 ? " period!" : "");
}
console.log("total probability of these 6 peaks:", peaks.reduce((s, y) => s + P[y], 0).toFixed(3));
const gcd = (u, w) => w ? gcd(w, u % w) : u, h = Number((2n ** 3n) % 21n);  // r = 6, so a^(r/2)
console.log(`r = 6: h = 2^3 mod 21 = ${h}; gcd(h-1, 21) = ${gcd(h - 1, 21)}, gcd(h+1, 21) = ${gcd(h + 1, 21)}`);

আসল আউটপুট (ব্রাউজারের JavaScript):

  y    P[y]   bar                    y/512 -> r?  2^r mod 21
  0   0.167  #################         1         2 
 85   0.114  ###########               6         1  period!
171   0.114  ###########               3         8 
256   0.167  #################         2         4 
341   0.114  ###########               3         8 
427   0.114  ###########               6         1  period!
total probability of these 6 peaks: 0.789
r = 6: h = 2^3 mod 21 = 8; gcd(h-1, 21) = 7, gcd(h+1, 21) = 3

2x mod 21-এর period 6, আর ছয়টি চূড়া পড়েছে 512/6 ≈ 85.3-এর গুণিতকের কাছে: 0, 85, 171, 256, 341, 427; একসাথে প্রায় ৭৯ শতাংশ সম্ভাবনা। y = 85 বা 427 মাপলে continued fraction সরাসরি r = 6 দেয় (85/512 ≈ 1/6). y = 171 বা 341 দেয় 3, আর 256 দেয় 2, যা r-এর ভাজক মাত্র; y = 0 কিছুই দেয় না। তাই algorithm প্রতিটি প্রার্থী r যাচাই করে (2r mod 21 = 1 কি না), দরকারে আবার চালায় বা কয়েকটি প্রার্থীর lcm নেয়। শেষে h = 8 থেকে gcd(7, 21) = 7 আর gcd(9, 21) = 3: 21 = 3 · 7.

Cryptography-র জন্য অর্থ। RSA-র নিরাপত্তা factoring-এর কঠিনতার ওপর, আর Diffie–Hellman ও elliptic-curve পদ্ধতিগুলোর নিরাপত্তা discrete log-এর ওপর নির্ভর করে (সাইবার সিকিউরিটি কোর্সের পর্ব ১০)। যথেষ্ট বড় আর ত্রুটি-সংশোধনক্ষম (fault-tolerant) quantum computer তৈরি হলে এগুলো ভাঙবে। এমন যন্ত্র কবে হবে, বা আদৌ হবে কি না, তা নিশ্চিত নয়; এখন পর্যন্ত Shor-এর পরীক্ষামূলক প্রদর্শন শুধু খুব ছোট সংখ্যায়। তবু আজকের এনক্রিপ্ট করা তথ্য কেউ জমিয়ে রেখে ভবিষ্যতে খুলতে পারে, তাই বাজারঘরের মতো প্রতিষ্ঠানও এখনই post-quantum cryptography-র দিকে যাওয়ার পরিকল্পনা করে: এমন পদ্ধতি, যা সাধারণ কম্পিউটারে চলে আর quantum আক্রমণেও নিরাপদ বলে মনে করা হয়, যেমন lattice-ভিত্তিক পদ্ধতি। এর complexity-র দিক পর্ব ৭৬ (cryptography-র complexity)-এ আসবে।

৭ · BQP-র মানচিত্র — কী জানা, কী অজানা

BQP আর চেনা শ্রেণিগুলো

তীর মানে “⊆, প্রমাণিত”. ড্যাশ দেওয়া রেখা মানে সম্পর্ক অজানা।

Map: P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE, P ⊆ NP ⊆ PP, BQP vs NP unknown PSPACE PP NP BQP BPP P অজানা NP-complete BQP-তে? অজানা FACTORING: NP ∩ coNP ∩ BQP
ছবি ৭৫.২ — প্রতিটি তীর একটি প্রমাণিত ⊆, কিন্তু কোনোটি কঠোর বলে প্রমাণিত নয়: P = PSPACE-ও কোনো জানা ফলের বিরোধী নয়। FACTORING-এর decision রূপ NP ∩ coNP-তে আর Shor-এর কারণে BQP-তে, কিন্তু BPP-তে আছে কি না অজানা।

BQP বনাম NP. কোনো দিকেই অন্তর্ভুক্তি জানা নেই। NP ⊆ BQP হলে quantum computer SAT দক্ষভাবে সমাধান করত; এর পক্ষে কোনো প্রমাণ বা algorithm নেই, আর বেশিরভাগ গবেষক মনে করেন এটি সত্য নয়। দুটি ইঙ্গিত: (১) BBBV-র ফল থেকে এমন একটি oracle আছে, যার সাপেক্ষে NP ⊄ BQP; তাই শুধু black-box কৌশলে এটি প্রমাণ করা যাবে না (পর্ব ৬৮-এর relativization-এর মতো)। (২) Shor-এর সাফল্য factoring-এর বিশেষ বীজগণিতীয় কাঠামো (period) থেকে, আর factoring NP-complete হওয়ার সম্ভাবনা কম, কারণ এটি NP ∩ coNP-তে: NP-complete হলে NP = coNP হতো (পর্ব ৬৩-এর NP-intermediate প্রার্থী)। উল্টো দিকে BQP ⊆ NP-ও জানা নেই; Raz আর Tal (২০১৮) একটি oracle দেখান, যার সাপেক্ষে BQP পুরো polynomial hierarchy-রও বাইরে।

BQP-তে কী কী জানা আছে. Factoring আর discrete log ছাড়াও কয়েকটি সংখ্যাতাত্ত্বিক সমস্যা (যেমন Pell-এর সমীকরণ, Hallgren-এর কাজ বলে পরিচিত) আর, সবচেয়ে স্বাভাবিকভাবে, quantum পদার্থবিজ্ঞানের ব্যবস্থার সময়-বিবর্তন নকল করা BQP-তে, যার classical দক্ষ পদ্ধতি জানা নেই। অন্যদিকে graph isomorphism-এর মতো NP-intermediate প্রার্থীর জন্য কোনো দক্ষ quantum algorithm জানা নেই, যদিও সেটিও একটি “লুকানো গঠন” খোঁজার সমস্যা। অর্থাৎ quantum লাভ এখন পর্যন্ত কয়েকটি নির্দিষ্ট কাঠামোয় সীমিত।

Extended Church–Turing thesis. পর্ব ৪৭-এর extended Church–Turing thesis বলে, যেকোনো বাস্তব গণনার মডেল একটি probabilistic Turing machine দিয়ে polynomial খরচে নকল করা যায়, অর্থাৎ দক্ষ গণনা মানে BPP-র গণনা। Shor-এর algorithm এর বিরুদ্ধে সবচেয়ে শক্ত সাক্ষ্য, তবে দুটি শর্তে: factoring BPP-তে নেই (অপ্রমাণিত), আর বড় quantum computer বাস্তবে বানানো যায় (প্রকৌশলের খোলা প্রশ্ন)। এটি Feynman-এর ১৯৮২ সালের পর্যবেক্ষণের সঙ্গে মেলে: quantum পদার্থবিজ্ঞানের classical simulation স্বাভাবিকভাবে exponential, তাই একটি quantum যন্ত্র দিয়েই তা করা উচিত।

“Quantum advantage”-এর দাবি. ২০১৯ সাল থেকে কয়েকটি গবেষক দল দাবি করেছে, তাদের যন্ত্র এমন একটি sampling কাজ করেছে (এলোমেলো circuit-এর output নমুনা), যা সেরা classical কম্পিউটারেও অবাস্তব সময় নেবে। এই দাবিগুলোর ভিত্তি একটি complexity অনুমান: এসব বণ্টন থেকে হুবহু নমুনা classical-ভাবে দক্ষভাবে নেওয়া গেলে polynomial hierarchy ভেঙে পড়ত। তবে পরে কয়েকটি দাবির বিপক্ষে উন্নত classical simulation পদ্ধতি এসেছে, কাজগুলোর ব্যবহারিক মূল্য সীমিত, আর ফল যাচাই করাও কঠিন। তাই এমন খবর পড়ার নিয়ম: কোন নির্দিষ্ট কাজ, কোন classical পদ্ধতির সঙ্গে তুলনা, আর কোন অনুমানের ওপর দাঁড়িয়ে। এখানে qubit-সংখ্যা বা সময়ের কোনো সংখ্যা দেওয়া হলো না, কারণ এগুলো দ্রুত পুরনো হয়।

আরও গভীরে: Black-box মডেলে quantum আর classical-এর পার্থক্য অনেক ভালোভাবে বোঝা গেছে: total Boolean function-এর জন্য deterministic আর quantum query complexity বড়জোর একটি polynomial গুণকে আলাদা (Beals, Buhrman, Cleve, Mosca আর de Wolf, ১৯৯৮ সালের দিকে, ছয় ঘাতের সীমা; পরে চার ঘাতে উন্নত বলে পরিচিত)। অর্থাৎ exponential ব্যবধানের জন্য একটি promise বা কাঠামো লাগে, যেমন Deutsch–Jozsa, Simon বা Shor-এ। Gottesman–Knill theorem বলে, শুধু H, S আর CNOT দিয়ে বানানো (Clifford) circuit classical যন্ত্রে দক্ষভাবে নকল করা যায়; T gate-এর মতো একটি বাড়তি gate-ই universality আনে। আর QMA, অর্থাৎ quantum certificate-এর NP, নিয়ে local Hamiltonian সমস্যা QMA-complete (Kitaev), যা quantum জগতের Cook–Levin.

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • BQP-র সংজ্ঞা দিন। Polynomial-time uniform, polynomial আকারের quantum circuit; w ∈ A হলে Pr[1] ≥ 2/3, w ∉ A হলে ≤ 1/3.
  • BQP-র জানা অবস্থান? BPP ⊆ BQP ⊆ PP ⊆ PSPACE; BQP আর NP-র সম্পর্ক অজানা।
  • Grover-এর query-সংখ্যা আর তা কেন সর্বোত্তম? প্রায় (π/4)√N; BBBV-র Ω(√N) নিম্নসীমা।
  • Deutsch–Jozsa-য় classical আর quantum query? Deterministic 2n−1 + 1, quantum 1, নিশ্চিত উত্তর; randomized কয়েকটি query-তে ছোট ভুলে।
  • Shor কীভাবে factor করে? Factoring → order finding (classical reduction), order quantum Fourier transform দিয়ে, তারপর gcd(ar/2 ± 1, N).

৮ · AI-এর যুগে quantum complexity

Quantum computing নিয়ে জনপ্রিয় লেখায় অতিরঞ্জন প্রচুর, আর AI assistant সেই ভাষা সহজেই নকল করে। বেশিরভাগ ভুল ধরা যায় দুটি অভ্যাসে: প্রতিটি দাবিকে “প্রমাণিত, অনুমান, না প্রকৌশলের প্রশ্ন” এই তিন ভাগে ফেলা, আর ছোট উদাহরণে state vector নিজে হিসাব করা।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
“Quantum computer সব উত্তর একসাথে চেষ্টা করে, তাই NP-complete সমস্যা সহজ”মাপলে একটিই ফল; Grover-এর √N সর্বোত্তম (BBBV); BQP বনাম NP অজানা
“Quantum computer halting problem সমাধান করতে পারে”BQP ⊆ PSPACE; প্রতিটি quantum circuit classical যন্ত্রে exponential সময়ে নকল করা যায়
“Deutsch–Jozsa সব classical algorithm-এর চেয়ে exponential দ্রুত”শুধু deterministic নির্ভুল যন্ত্রের বিপক্ষে; randomized কয়েকটি query-তে পারে
Grover-এ “যত বেশি iteration, তত ভালো”সম্ভাবনা sin2((2k + 1)θ), বাড়াবাড়িতে কমে; k ≈ (π/4)√N
“Shor RSA ভেঙে দিয়েছে” বা নির্দিষ্ট qubit-সংখ্যা ও সালAlgorithm প্রমাণিত, বড় fault-tolerant যন্ত্র নেই; সংখ্যা মূল সূত্রে মিলিয়ে নিন
Qiskit-এর qubit-ক্রম উল্টো পড়া (qubit 0 ডানদিকের bit)ছোট circuit-এ statevector ছেপে প্রতিটি ভিত্তি-অবস্থা মেলান
বানানো রেফারেন্স বা ভুল সাল (BBBV, Bernstein–Vazirani)Nielsen–Chuang, Arora–Barak বা মূল প্রবন্ধে নিজে দেখুন

AI-কে কাজে লাগানোর ভালো উপায়: সংজ্ঞা আর উপপাদ্য হুবহু চাওয়া, প্রতিটি দাবির পাশে “প্রমাণিত/অনুমান/খোলা” লেবেল চাওয়া, আর এমন একটি ছোট simulator চাওয়া, যার ফল হাতের হিসাবের সঙ্গে মেলানো যায়।

আমি গণনার তত্ত্ব শিখছি, quantum complexity নিয়ে প্রশ্ন। ১. BQP-র নিখুঁত সংজ্ঞা দাও (uniform circuit family, gate set, ভুলের সীমা), আর BPP-র সংজ্ঞার সঙ্গে পাশাপাশি তুলনা করো। ২. BPP ⊆ BQP ⊆ PSPACE-এর প্রমাণের রূপরেখা দাও; PSPACE অংশে জায়গার হিসাব স্পষ্ট লেখো। ৩. Grover-এর জন্য sin²((2k+1)θ) সূত্রটি জ্যামিতিক যুক্তিতে প্রমাণ করো, আর N = 8 ও N = 16-এ সেরা k আর সাফল্যের সম্ভাবনা হিসাব করো। ৪. শুধু numpy দিয়ে একটি ছোট state-vector simulator দাও, যা Deutsch–Jozsa (n = 2) আর Grover (N = 8) চালিয়ে সম্ভাবনা ছাপে। ৫. প্রতিটি দাবির পাশে লেখো: প্রমাণিত, অনুমান, না খোলা প্রশ্ন। BQP বনাম NP নিয়ে কী জানা আছে, সতর্কভাবে বলো; qubit-সংখ্যা বা hardware-এর দাবি দিও না, আর বানানো রেফারেন্স দিও না।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১“Quantum computer সব সম্ভাব্য উত্তর একসাথে চেষ্টা করে।” এই জনপ্রিয় ব্যাখ্যা কোথায় ভুল, আর NP-complete সমস্যায় quantum-এর কাছে আসলে কী আশা করা যায়?

ব্যাখ্যাটির সত্য অংশ এটুকু: H⊗n দিয়ে 2nটি x-এর সমান superposition বানিয়ে একটি oracle একবার চালালে প্রতিটি x-এর f(x) কোনো না কোনোভাবে state vector-এ “লেখা” হয়। কিন্তু সেই লেখা পড়ার উপায় একটিই, measurement, আর সেটি একটি এলোমেলো x দেয়, |αx|2 সম্ভাবনায়। SAT-এর একটিমাত্র সন্তোষজনক মান-নির্ধারণ থাকলে সরাসরি মেপে সেটি পাওয়ার সম্ভাবনা 2−n, এলোমেলো অনুমানের সমান। “সমান্তরাল চেষ্টা” তাই নিজে কোনো লাভ দেয় না।

লাভ আসে interference থেকে: ভুল উত্তরের amplitude-গুলো একে অপরকে কাটবে আর ঠিক উত্তরের amplitude বাড়বে, এমনভাবে circuit সাজাতে হয়। এটি করা যায় শুধু তখন, যখন সমস্যার কোনো কাঠামো তা অনুমতি দেয়। Shor-এ সেই কাঠামো হলো period: Fourier transform period-কে একটি তীক্ষ্ণ চূড়ায় বদলে দেয়। কাঠামোহীন খোঁজে Grover-এর amplitude amplification-ই সেরা, আর Bennett, Bernstein, Brassard ও Vazirani ১৯৯৭ সালে দেখান যে এখানে Ω(√N)-এর চেয়ে কম query সম্ভব নয়। অর্থাৎ black-box SAT-এ 2n থেকে প্রায় 2n/2, এখনো exponential.

তাহলে কি quantum যন্ত্র NP-complete সমস্যায় অকেজো? না, তবে প্রত্যাশা সংযত রাখতে হয়। বর্গমূলের লাভ বড় সংখ্যায় অর্থবহ হতে পারে, যদিও error correction-এর খরচ সেই লাভের অনেকটা খেয়ে ফেলতে পারে বলে অনেকে সতর্ক করেন। Adiabatic optimization বা quantum annealing-এর মতো heuristic নিয়ে গবেষণা চলছে, কিন্তু সাধারণ NP-complete সমস্যায় এদের exponential লাভের কোনো প্রমাণ নেই। আর NP ⊆ BQP অপ্রমাণিত শুধু নয়, এমন একটি oracle-ও আছে যার সাপেক্ষে এটি মিথ্যা, তাই black-box কৌশল দিয়ে এটি কখনো প্রমাণ হবে না।

Scott Aaronson-এর মতো গবেষকেরা বহু বছর ধরে এই বিষয়ে জনপ্রিয় লেখার ভুল ধরিয়ে দিয়ে আসছেন; তাঁদের একটি পরিচিত পরামর্শ হলো, “quantum” শব্দের সঙ্গে “সব একসাথে” শুনলে সতর্ক হোন।

মূল উপলব্ধি: Superposition একা কোনো লাভ দেয় না, কারণ measurement একটিই এলোমেলো ফল দেয়; লাভ আসে কাঠামো-নির্ভর interference থেকে, আর কাঠামোহীন NP খোঁজে তা শুধু বর্গমূলের, যা প্রমাণিতভাবে সর্বোত্তম।

প্র ০২Deutsch–Jozsa-র ব্যবধান randomized যন্ত্রের সামনে টেকে না। তাহলে এর ঐতিহাসিক গুরুত্ব কী, আর randomized classical যন্ত্রের সঙ্গে আসল exponential ব্যবধান কোথায় প্রথম দেখা গেল?

David Deutsch ১৯৮৫ সালে quantum Turing machine-এর ধারণা দেন আর n = 1-এর একটি ছোট সমস্যা দেখান: f: {0, 1} → {0, 1}-এর f(0) ⊕ f(1) একটি query-তে বের করা, যেখানে classical যন্ত্রের দুটি লাগে (তাঁর মূল সংস্করণ সব সময় সফল হতো না; পরের উন্নত রূপ নিশ্চিত)। Deutsch আর Richard Jozsa ১৯৯২ সালে এটিকে n bit-এ বাড়ান। গুরুত্ব ছিল ধারণাগত: প্রথমবার একটি সুনির্দিষ্ট গণনার কাজ দেখা গেল, যেখানে quantum যন্ত্র নিশ্চিতভাবে প্রমাণযোগ্য দক্ষতা দেখায়। কিন্তু অংশ ৪-এর সতর্কতার মতো, একটি randomized classical যন্ত্র কয়েকটি query-তেই ছোট ভুলে কাজটি পারে, তাই এটি BPP-র বিপক্ষে ব্যবধান নয়।

পরের ধাপ Bernstein আর Vazirani (১৯৯৩): একটি লুকানো string s খোঁজা, যেখানে f(x) = s · x mod 2. Quantum যন্ত্র একটি query-তে s পায়, classical যন্ত্রের (randomized হলেও) n-টি query লাগে; ব্যবধান polynomial, আর একটি পুনরাবৃত্ত সংস্করণে বড় ব্যবধান দেখান। তাঁদের প্রবন্ধেই BQP সংজ্ঞায়িত হয়।

আসল exponential ব্যবধান Daniel Simon-এর ১৯৯৪ সালের সমস্যায়: f: {0, 1}n → {0, 1}n এমন যে f(x) = f(y) ⇔ y = x বা y = x ⊕ s, একটি লুকানো s-এর জন্য। Quantum যন্ত্র O(n) query আর polynomial classical post-processing-এ s পায়; যেকোনো randomized classical যন্ত্রের প্রায় 2n/2 query লাগে, কারণ s জানতে একটি সংঘর্ষ (collision) পেতে হয়, birthday সীমায়। Simon-এর প্রবন্ধ পড়েই Shor period finding-এর ধারণা পান বলে প্রচলিত: Simon-এর লুকানো XOR-period আর Shor-এর লুকানো গুণনীয় period একই ছকের দুই রূপ, যাকে পরে hidden subgroup problem বলা হয়।

লক্ষ করার মতো বিষয়: এই সব ব্যবধান query মডেলে প্রমাণিত, যেখানে oracle একটি কালো বাক্স। Oracle-কে একটি স্পষ্ট circuit দিয়ে বদলালে প্রমাণগুলো আর খাটে না, আর তখন BPP ≠ BQP-র কোনো প্রমাণ নেই।

মূল উপলব্ধি: Deutsch–Jozsa দেখায় quantum নির্ভুলতার শক্তি, Simon দেখায় randomized classical-এর বিপক্ষে exponential query-ব্যবধান, আর Shor সেই ছককে একটি বাস্তব সমস্যায় আনে; তবু শর্তহীন BPP ≠ BQP আজও অপ্রমাণিত।

প্র ০৩বড় quantum computer এখনো নেই, তবু বাজারঘরের মতো একটি অনলাইন দোকানের নিরাপত্তা-পরিকল্পনায় Shor-এর algorithm আজই গুরুত্বপূর্ণ কেন? কোন অংশ ঝুঁকিতে, কোন অংশ তুলনামূলক নিরাপদ?

বাজারঘরের HTTPS সংযোগ, পেমেন্ট গেটওয়ের সঙ্গে key বিনিময় আর software update-এর digital signature, সবকিছুতে public-key cryptography চলে: RSA, Diffie–Hellman বা elliptic curve. এদের নিরাপত্তা factoring বা discrete log-এর কঠিনতার অনুমানের ওপর দাঁড়িয়ে, আর Shor-এর algorithm দুটিকেই quantum যন্ত্রে polynomial করে। তাই যথেষ্ট বড় fault-tolerant quantum computer এলে এই অংশগুলো ভাঙবে; key বড় করে বাঁচা যাবে না, কারণ খরচ polynomial হারে বাড়ে।

Symmetric cryptography (যেমন AES) আর hash function-এর অবস্থা আলাদা। এদের বিরুদ্ধে জানা সাধারণ quantum আক্রমণ Grover-ভিত্তিক brute force, যা শুধু বর্গমূলের লাভ দেয়। তাই key-এর দৈর্ঘ্য যথেষ্ট রাখলেই চলে বলে মনে করা হয়; Grover-এর সর্বোত্তমতার (BBBV) কারণে এর চেয়ে ভালো সাধারণ আক্রমণ black-box মডেলে নেই।

আজই কেন? “Harvest now, decrypt later”: প্রতিপক্ষ আজকের এনক্রিপ্ট করা যোগাযোগ জমিয়ে রাখতে পারে আর ভবিষ্যতে খুলতে পারে। গ্রাহকের তথ্য যদি দশ বছর পরেও গোপন থাকা দরকার, তাহলে ঝুঁকি এখনই শুরু। তাছাড়া বড় একটি ব্যবস্থার algorithm বদলাতে বহু বছর লাগে। এই কারণে NIST ২০২৪ সালে প্রথম post-quantum মানদণ্ডগুলো প্রকাশ করে: lattice-ভিত্তিক key বিনিময় ML-KEM আর signature ML-DSA, আর hash-ভিত্তিক signature SLH-DSA.

Complexity-র দৃষ্টিতে একটি সূক্ষ্মতা আছে: post-quantum পদ্ধতিগুলোও প্রমাণিতভাবে নিরাপদ নয়; এদের ভিত্তি lattice সমস্যার মতো কাঠামো, যার জন্য কোনো দক্ষ classical বা quantum algorithm জানা নেই। প্রস্তুতির সময় কিছু প্রার্থী পদ্ধতি classical আক্রমণেই ভেঙেছে, যা মনে করিয়ে দেয় যে নতুন অনুমান সময় নিয়ে যাচাই হয়। তাই ব্যবহারিক পরামর্শ: “crypto agility”, অর্থাৎ algorithm সহজে বদলানো যায় এমন নকশা, আর পরিচিত, পর্যালোচিত library ব্যবহার; নিজে cryptography বানানো নয়। পর্ব ৭৬-এ one-way function আর average-case কঠিনতার তত্ত্ব আসবে।

মূল উপলব্ধি: Shor ঝুঁকিতে ফেলে factoring ও discrete log-নির্ভর public-key অংশ, Grover symmetric অংশে শুধু বর্গমূলের চাপ দেয়; জমিয়ে রাখা তথ্য আর দীর্ঘ রূপান্তর-সময়ের কারণে post-quantum প্রস্তুতি আজকের কাজ।

প্র ০৪সংবাদে “quantum supremacy” বা “quantum advantage” অর্জনের দাবি আসে। একজন গণনার তত্ত্বের শিক্ষার্থী এমন দাবি কীভাবে বিচার করবেন?

“Quantum supremacy” শব্দটি John Preskill ২০১২ সালের দিকে চালু করেন বলে পরিচিত: এমন একটি কাজ, যা quantum যন্ত্র করতে পারে কিন্তু কোনো classical কম্পিউটার যুক্তিসংগত সময়ে পারে না, কাজটি কাজে লাগুক বা না লাগুক। পরে অনেকে “quantum advantage” শব্দ পছন্দ করেন। লক্ষ্য ছিল extended Church–Turing thesis-এর বিরুদ্ধে একটি পরীক্ষামূলক সাক্ষ্য, Shor-এর মতো বড় যন্ত্রের অপেক্ষা না করেই।

তাত্ত্বিক ভিত্তি কয়েকটি ফল থেকে আসে। Aaronson আর Arkhipov (২০১১) boson sampling, আর Bremner, Jozsa ও Shepherd (২০১১ সালের দিকে) সরল ধরনের commuting circuit নিয়ে দেখান: এসব quantum বণ্টন থেকে হুবহু নমুনা classical যন্ত্র দক্ষভাবে নিতে পারলে polynomial hierarchy ভেঙে পড়ত (পর্ব ৬৮)। আনুমানিক নমুনার ক্ষেত্রে একই সিদ্ধান্তে পৌঁছাতে বাড়তি, অপ্রমাণিত অনুমান লাগে। অর্থাৎ ভিত্তিটি একটি শর্তসাপেক্ষ complexity যুক্তি, শর্তহীন প্রমাণ নয়।

২০১৯ সাল থেকে কয়েকটি দল এলোমেলো circuit sampling আর boson sampling-এ এমন দাবি করেছে। কয়েকটি দাবির পর classical গবেষকেরা tensor network-এর মতো উন্নত simulation দিয়ে সময়ের হিসাব অনেক কমিয়ে এনেছেন, আবার নতুন পরীক্ষা ব্যবধান বাড়িয়েছে বলে দাবি করেছে। এই টানাপোড়েন বিজ্ঞানের স্বাভাবিক পথ, কিন্তু খবরের শিরোনামে প্রায়ই হারিয়ে যায়।

বিচারের প্রশ্নগুলো তাই: (১) ঠিক কোন কাজ, আর সেটি কি একটি decision সমস্যা না sampling? (২) তুলনা কোন classical পদ্ধতির সঙ্গে, আর সেটি কি সেরা জানা পদ্ধতি? (৩) ফল যাচাই কীভাবে হলো, যখন classical যন্ত্র নিজেই তা হিসাব করতে পারে না? (৪) কোন complexity অনুমানের ওপর দাবি দাঁড়িয়ে? (৫) কাজটির কোনো ব্যবহারিক মূল্য আছে কি? Hardware-এর সংখ্যা দ্রুত বদলায়, তাই এই প্রশ্নগুলো সংখ্যার চেয়ে দীর্ঘস্থায়ী।

মূল উপলব্ধি: Quantum advantage-এর দাবি একটি নির্দিষ্ট কাজ, একটি নির্দিষ্ট classical তুলনা আর একটি complexity অনুমানের ওপর দাঁড়িয়ে; এই তিনটি আলাদা করে দেখলে অতিরঞ্জন আর আসল অগ্রগতি দুটোই চেনা যায়।

প্র ০৫n qubit-এর অবস্থা লিখতে 2nটি amplitude লাগে, তবু n qubit থেকে n bit-এর বেশি তথ্য পড়া যায় না। এই দুটি সত্য একসাথে কীভাবে খাপ খায়, আর classical simulation আসলে কতটা কঠিন?

প্রথম সত্যটি বর্ণনার: একটি সাধারণ n-qubit অবস্থা সম্পূর্ণ লিখতে 2nটি complex সংখ্যা লাগে, আর তার বিবর্তন নকল করতে সাধারণভাবে সেগুলো সব হিসাব করতে হয়। Richard Feynman ১৯৮১ সালের একটি বক্তৃতায় (প্রকাশ ১৯৮২) এই পর্যবেক্ষণ থেকেই প্রস্তাব করেন, quantum ব্যবস্থা নকল করতে quantum যন্ত্রই ব্যবহার করা উচিত। আজও রসায়ন আর পদার্থবিজ্ঞানের simulation quantum কম্পিউটারের সবচেয়ে প্রত্যাশিত ব্যবহারগুলোর একটি।

দ্বিতীয় সত্যটি পড়ার: Alexander Holevo ১৯৭৩ সালে প্রমাণ করেন বলে পরিচিত, n qubit-এ এনকোড করা তথ্য থেকে measurement দিয়ে n classical bit-এর বেশি পারস্পরিক তথ্য বের করা যায় না। কারণ measurement প্রতিটি qubit থেকে একটি bit দেয় আর অবস্থা ভেঙে ফেলে। 2nটি amplitude তাই “গুপ্ত ভান্ডার” নয়; এরা বড়জোর গণনার মাঝপথে interference-এর মাধ্যমে কাজে লাগে।

দুটি মেলানোর উপায়: quantum গণনার শক্তি তথ্য জমানোয় নয়, বরং amplitude-গুলো সাজানোয়, যাতে শেষে কাঙ্ক্ষিত ফলের সম্ভাবনা বড় হয়। এই সাজানো classical যন্ত্রে নকল করা কঠিন হতে পারে, কারণ সব পথের যোগফল লাগে, আর অংশ ৩-এ দেখেছেন সেটি PP-র ক্ষমতার মধ্যে পড়ে, PSPACE-এর ভেতরে।

তবে সব quantum circuit নকল করা কঠিন নয়। Gottesman–Knill theorem (১৯৯৮ সালের দিকে) অনুসারে শুধু H, S, CNOT আর measurement দিয়ে বানানো circuit classical যন্ত্রে polynomial সময়ে নকল করা যায়, যদিও তারা Bell অবস্থার মতো entanglement তৈরি করে। কম entanglement-এর circuit tensor network বা matrix product state দিয়ে দক্ষভাবে নকল করা যায়। অর্থাৎ entanglement থাকা যথেষ্ট নয়; কঠিনতা আসে নির্দিষ্ট gate-মিশ্রণ আর ব্যাপক entanglement থেকে। এটিই quantum advantage-এর দাবি যাচাইয়ে classical simulation গবেষণার গুরুত্ব।

মূল উপলব্ধি: 2nটি amplitude বর্ণনার খরচ, পড়ার মতো তথ্য নয় (Holevo); quantum শক্তি আসে interference-এ amplitude সাজানো থেকে, আর সব circuit নয়, শুধু কিছু ধরনের circuit-ই classical-ভাবে কঠিন বলে মনে করা হয়।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। qsim.py আর grover.py বদলে নিজের circuit দিয়েও যাচাই করতে পারেন।

  1. নকশা: দুটি qubit |00⟩ থেকে শুরু। শুধু H, X, Z আর CNOT ব্যবহার করে এমন একটি circuit নকশা করুন, যা (|01⟩ − |10⟩)/√2 অবস্থা তৈরি করে, যেখানে বাঁয়ের bit প্রথম qubit-এর। প্রতিটি gate-এর পর অবস্থা লিখুন, আর দেখান যে শেষ অবস্থাটি entangled.

    একটি সমাধান: (১) প্রথম qubit-এ H: (|00⟩ + |10⟩)/√2. (২) CNOT, control প্রথম, target দ্বিতীয়: (|00⟩ + |11⟩)/√2. (৩) দ্বিতীয় qubit-এ X: (|01⟩ + |10⟩)/√2. (৪) প্রথম qubit-এ Z, যা প্রথম bit 1 হলে চিহ্ন উল্টায়: (|01⟩ − |10⟩)/√2. qsim.py-র apply আর cnot দিয়ে একই ক্রমে চালিয়ে scratch-এ যাচাই করা হয়েছে: amplitude (0, 0.707, −0.707, 0).

    Entangled: (a|0⟩ + b|1⟩) ⊗ (c|0⟩ + d|1⟩) হলে ac = 0 আর bd = 0 (|00⟩ আর |11⟩ নেই), অথচ ad ≠ 0 আর bc ≠ 0. ad ≠ 0 থেকে a ≠ 0, bc ≠ 0 থেকে c ≠ 0, তাহলে ac ≠ 0: বিরোধ। দাবি ২.১-এর একই যুক্তি। অন্য ক্রমও কাজ করে, যেমন শুরুতে দুটি qubit-এ X দিয়ে |11⟩ থেকে H আর CNOT.

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: NP ⊆ BQP. প্রমাণ: n চলকের একটি সূত্র φ নিন। H⊗n দিয়ে সব 2n মান-নির্ধারণের superposition বানাই, তারপর φ-এর একটি reversible circuit একবার চালিয়ে একটি বাড়তি qubit-এ φ(x) লিখি। এতে polynomial gate লাগে, আর একসাথে সব x পরীক্ষা হয়ে যায়। এবার মাপলে একটি সন্তোষজনক x পাই। তাই SAT ∈ BQP, আর Cook–Levin থেকে NP ⊆ BQP. ∎” ভুল কোথায়?

    প্রথম তিন ধাপ ঠিক, ভুল “মাপলে একটি সন্তোষজনক x পাই”-তে। মাপলে প্রতিটি x আসে সমান সম্ভাবনা 2−n-এ, φ(x)-এর মান যাই হোক; φ-এর একটিমাত্র সন্তোষজনক x থাকলে সেটি পাওয়ার সম্ভাবনা 2−n, যা BQP-র 2/3-এর ধারেকাছে নেই। বাড়তি qubit মেপে 1 পেলেও শুধু জানা যায় এই এলোমেলো x-টি ভালো ছিল।

    সম্ভাবনা বাড়াতে interference লাগে, আর কাঠামোহীন ক্ষেত্রে সেরা উপায় Grover: প্রায় 2n/2 iteration, যা exponential. BBBV অনুসারে black-box মডেলে এর চেয়ে ভালো সম্ভব নয়, তাই φ-কে কালো বাক্স ধরে কোনো প্রমাণ সফল হবে না। NP ⊆ BQP সত্য না মিথ্যা, তা অজানা; এই “প্রমাণ” কিছুই দেখায় না।

  3. Trace আর আগাম অনুমান: (ক) |0⟩-এ পরপর H, S, S, H দিলে অবস্থা কী, আর মাপলে কী আসবে? (S = diag(1, i).) (খ) N = 16, একটি বৈধ কোড। k = 2, 3 আর 4 Grover iteration-এর পর সাফল্যের সম্ভাবনা কত, আর কোন k বেছে নেবেন? (sin θ = 1/4, θ ≈ 14.48°.)

    (ক) S · S = diag(1, i2) = diag(1, −1) = Z, তাই circuit-টি H Z H. H|0⟩ = (|0⟩ + |1⟩)/√2, Z-এর পর (|0⟩ − |1⟩)/√2, আর H-এর পর |1⟩. মাপলে নিশ্চিত 1 (প্রথম stepper-এর শেষ ধাপ)। আসলে H Z H = X.

    (খ) সম্ভাবনা sin2((2k + 1)θ): k = 2 → sin2(72.4°) ≈ 0.908; k = 3 → sin2(101.3°) ≈ 0.961; k = 4 → sin2(130.3°) ≈ 0.582. সেরা k = 3 = ⌊(π/4) · 4⌋, যা grover.py-র সারণির N = 16 সারির 0.9613-এর সঙ্গে মেলে; বাকি দুটি মান scratch-এ একই সূত্রে হিসাব করা হয়েছে।

  4. হিসাব: Shor-এর classical কাঠামো N = 15-এ চালান। (ক) a = 2: order r কত, আর কোন উৎপাদক মেলে? (খ) a = 11 আর a = 14-এর ক্ষেত্রে কী হয়? (গ) a = 6 বাছলে কী হয়? (ঘ) একটি সাধারণ RSA modulus-এর bit-সংখ্যা দ্বিগুণ হলে Shor-এর gate-সংখ্যা মোটামুটি কত গুণ বাড়ে, n3 অনুমানে?

    (ক) 2x mod 15 = 1, 2, 4, 8, 1, তাই r = 4. h = 22 = 4 ≢ −1; gcd(3, 15) = 3, gcd(5, 15) = 5. (খ) a = 11: 112 = 121 ≡ 1, তাই r = 2, h = 11 ≢ 14; gcd(10, 15) = 5, gcd(12, 15) = 3, সফল। a = 14: r = 2, h = 14 ≡ −1, তাই gcd দুটি 1 আর 15, ব্যর্থ; নতুন a লাগে। সব মান scratch-এ যাচাই করা হয়েছে।

    (গ) gcd(6, 15) = 3, তাই order খোঁজার আগেই একটি উৎপাদক মিলে গেল: 15 = 3 · 5, আর অন্য উৎপাদক ভাগ করেই পাওয়া যায়। বড় N-এ এমন ভাগ্য খুবই বিরল। (ঘ) n3 অনুমানে (2n)3/n3 = 8 গুণ। Classical number field sieve-এ একই দ্বিগুণ হওয়া সময়কে অনেক বেশি গুণ বাড়ায়, কারণ সেটি subexponential, polynomial নয়; এই কারণেই key বড় করে Shor থেকে বাঁচা যায় না।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমShor-এর algorithm-এ N-এর একটি উৎপাদক খোঁজার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. এলোমেলো a বেছে gcd(a, N) দেখা; 1 না হলে সেটিই উৎপাদক
  2. প্রথম register-এ সব x-এর superposition বানিয়ে দ্বিতীয়টিতে ax mod N হিসাব করা
  3. প্রথম register-এ quantum Fourier transform চালিয়ে একটি y মাপা
  4. y/Q-এর continued fraction থেকে order r-এর প্রার্থী বের করে ar ≡ 1 যাচাই
  5. r জোড় আর ar/2 ≢ −1 হলে gcd(ar/2 − 1, N) হিসাব করা

BQP-র সংজ্ঞায় একটি ভাষা A-র জন্য polynomial-time uniform quantum circuit family {Cn} লাগে। ভুলের শর্ত কোনটি?

  • প্রতিটি w-এ সম্ভাবনা 1-এ সঠিক উত্তর
  • w ∈ A হলে Pr[accept] > 1/2, নইলে ≤ 1/2
  • w ∈ A হলে Pr[accept] ≥ 2/3, w ∉ A হলে ≤ 1/3
  • w ∈ A হলে Pr[accept] ≥ 1/2, w ∉ A হলে ঠিক 0

নিচের কোন বক্তব্যটি প্রমাণিত সত্য?

  • BPP ⊆ BQP ⊆ PSPACE
  • NP ⊆ BQP
  • BQP ⊆ NP
  • BQP = BPP

N = 220টি কোডের মধ্যে ঠিক একটি বৈধ, আর একটি oracle শুধু বলে কোনো কোড বৈধ কি না। Grover-এর algorithm মোটামুটি কতগুলো oracle query-তে উচ্চ সম্ভাবনায় কোডটি পায়?

  • প্রায় 20
  • প্রায় 804
  • প্রায় 219
  • মাত্র 1

f: {0, 1}n → {0, 1} সম্পর্কে প্রতিশ্রুতি: f হয় constant, নয় balanced. নিচের কোনটি সঠিক?

  • যেকোনো randomized classical algorithm-এরও exponential সংখ্যক query লাগে
  • Quantum algorithm এক query-তে শুধু 1/2 সম্ভাবনায় সঠিক
  • প্রতিশ্রুতি ছাড়াও quantum algorithm যেকোনো f-কে নিশ্চিতভাবে শ্রেণিবদ্ধ করে
  • Deterministic classical যন্ত্রের সবচেয়ে খারাপ ক্ষেত্রে 2n−1 + 1টি query লাগে, quantum যন্ত্রের একটি

Shor-এর algorithm-এ N = 15 আর a = 7 নিলে order r আর প্রাপ্ত উৎপাদক কী?

  • r = 2, উৎপাদক 3 আর 5
  • r = 3, উৎপাদক মেলে না
  • r = 4, উৎপাদক gcd(3, 15) = 3 আর gcd(5, 15) = 5
  • r = 4, কিন্তু h ≡ −1, তাই ব্যর্থ

“একটি বড় quantum computer halting problem decide করতে পারবে।” এই দাবি সম্পর্কে কোনটি সঠিক?

  • সত্য, কারণ quantum computer extended Church–Turing thesis ভাঙে
  • মিথ্যা, কারণ একটি classical Turing machine যেকোনো quantum circuit exponential সময়ে নকল করতে পারে
  • সত্য, কারণ superposition-এ সব input একসাথে চালানো যায়
  • অজানা, কারণ BQP বনাম NP খোলা প্রশ্ন

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. n qubit-এর অবস্থা 2nটি amplitude-এর একক vector; মাপলে x আসে |αx|2 সম্ভাবনায়, আর ঋণাত্মক amplitude interference-এ কাটে।
  2. Gate মানে unitary matrix, তাই উল্টানো যায়; {H, T, CNOT} universal, আর Bell অবস্থা entangled.
  3. BQP: uniform polynomial quantum circuit, ভুল ≤ 1/3; প্রমাণিত BPP ⊆ BQP ⊆ PP ⊆ PSPACE, তাই computability-র সীমা অটুট।
  4. Deutsch–Jozsa: deterministic 2n−1 + 1 বনাম quantum 1 query; Grover: (π/4)√N, সর্বোত্তম; Shor: factoring → order finding → QFT, polynomial সময়।
  5. BQP বনাম NP অজানা; NP-complete সমস্যার দক্ষ quantum algorithm জানা নেই, আর extended thesis-এর চ্যালেঞ্জ শর্তসাপেক্ষ।

পরের পর্বে: Cryptography-র complexity: one-way function কী, P ≠ NP কেন যথেষ্ট নয়, worst-case বনাম average-case কঠিনতা, আর lattice-ভিত্তিক post-quantum cryptography-র তাত্ত্বিক ভিত্তি।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান