Quantum Computing Basics: Qubits and Quantum Algorithms

The search problem hiding inside a billion-record database

When UIDAI enrolls a new resident into Aadhaar, it cannot simply add the fingerprint and iris scan to the database and move on. Before issuing a new number it must check that this biometric profile does not already belong to someone else — deduplication against roughly 1.3 billion existing records, run for every single new enrollment. This is a fundamentally different problem from looking up a PNR on IRCTC. A PNR lookup is a sorted search: the ten-digit number gives you a direct index, and the system finds it in essentially constant time. Biometric deduplication is an unsorted search: there is no ordering of fingerprint-minutiae vectors that lets you binary-search your way to a match, because "closeness" in that space does not collapse into a single linear order the way integers do. Classically, in the worst case, checking one new template against N existing ones costs O(N) comparisons — you may have to look at every record. This is precisely why biometric deduplication at Aadhaar's scale depends on enormous classical compute clusters running approximate nearest-neighbour search, not a clever indexing trick.

This chapter is about the one piece of quantum computing that speaks directly to this exact problem: Grover's algorithm, and the gate-model machinery — qubits, unitary gates, phase oracles, amplitude amplification — that makes it work. A companion chapter on quantum machine learning covers variational circuits and quantum kernels for training AI models; this chapter stays deliberately narrower and goes deeper into the mechanics of a single, provably optimal quantum search algorithm, built up from the linear algebra of a single qubit to a fully traced numerical example.

What a qubit actually is

A classical bit is an element of the set {0, 1}. A qubit is a unit vector in the two-dimensional complex vector space spanned by two orthonormal basis vectors written |0⟩ and |1⟩ (Dirac "ket" notation — just a column vector with a label). The general state of one qubit is

|ψ⟩ = α|0⟩ + β|1⟩,  where α, β ∈ ℂ and |α|² + |β|² = 1

The normalization constraint exists because of the Born rule: if you measure |ψ⟩ in the {|0⟩, |1⟩} basis, you get outcome 0 with probability |α|² and outcome 1 with probability |β|², and probabilities must sum to 1. This is the entire content of "superposition" — it is not that the qubit is secretly both 0 and 1 at once in some mystical sense; it is that the qubit's state is a vector with two complex components, and measurement is a probabilistic projection of that vector onto a basis. Crucially, measurement is destructive: after you measure and get 0, the state collapses to exactly |0⟩, and β's value is gone. You get one bit of classical information out per qubit measured, no matter how large α and β's internal structure was.

The power shows up when you combine qubits. Two qubits live in a 4-dimensional space spanned by |00⟩, |01⟩, |10⟩, |11⟩ (the tensor product of two 2-dimensional spaces), and n qubits live in a 2ⁿ-dimensional space. A register of n qubits can hold a superposition over all 2ⁿ basis states simultaneously, each with its own complex amplitude. This is real: the vector genuinely has 2ⁿ independent numbers in it, and a single quantum gate operation updates all of them in one step. What is not real, and is the single most consequential misconception about this whole subject, is the idea that you can therefore read out all 2ⁿ values — measurement still gives you exactly one n-bit string, chosen with probability equal to the squared magnitude of its amplitude. Section 6 below returns to this directly, after you have seen the algorithm that actually uses the 2ⁿ-dimensional structure productively.

Gates: reversible linear operators

A quantum gate on n qubits is a unitary matrix U (size 2ⁿ × 2ⁿ, satisfying U†U = I, where U† is the conjugate transpose). Unitarity is what keeps the total probability equal to 1 after the gate is applied, and it is also why every quantum gate is reversible — U⁻¹ = U† always exists — unlike a classical AND gate, which destroys information and cannot be run backward. Three gates matter for this chapter:

X = [[0, 1],       Z = [[1,  0],      H = (1/√2) [[1,  1],
     [1, 0]]            [0, -1]]                  [1, -1]]

X is the quantum NOT gate: X|0⟩ = |1⟩ and X|1⟩ = |0⟩. Z leaves |0⟩ alone and flips the sign of |1⟩ — a "phase flip" with no classical analogue, since classical bits have no sign. H, the Hadamard gate, is the superposition-builder: H|0⟩ = (|0⟩ + |1⟩)/√2 and H|1⟩ = (|0⟩ − |1⟩)/√2. Apply H to each of n qubits initialized to |0⟩ and you get the uniform superposition over all 2ⁿ basis states, each with amplitude 1/√(2ⁿ) — this single step is where the exponentially large state space gets populated, and it is the first line of every Grover circuit.

Two-qubit gates create entanglement — correlations between qubits that cannot be reproduced by treating them as two separate, independently-random classical bits. The standard example: apply H to qubit 0 (giving (|0⟩+|1⟩)/√2 on that qubit, |0⟩ on qubit 1), then apply CNOT (flip qubit 1 if and only if qubit 0 is |1⟩). Tracing it through: H|0⟩⊗|0⟩ = (|00⟩+|10⟩)/√2, and CNOT sends |10⟩ → |11⟩ while leaving |00⟩ fixed, giving the Bell state (|00⟩+|11⟩)/√2. Measuring qubit 0 now forces qubit 1's outcome to match, even though neither qubit had a definite value beforehand. Grover's algorithm, as built below, does not strictly need this two-qubit entangling structure for its oracle in the simplified phase-oracle form used here, but the general n-qubit diffusion step is itself built from H gates and a multi-controlled phase gate that does entangle the register internally before disentangling it again — worth flagging so you don't conclude entanglement is irrelevant to search algorithms.

Grover's algorithm, derived

The problem: you have N = 2ⁿ items indexed by n-bit strings x, and a black-box function f(x) that equals 1 for exactly M "marked" items and 0 otherwise. You are given oracle access to f as a quantum gate — for this chapter, the phase oracle U_f: |x⟩ → (−1)^f(x)|x⟩, which flips the sign of marked amplitudes and leaves the rest untouched. Classically, finding a marked item needs Θ(N/M) queries to f on average. Grover, in a 1996 STOC paper ("A Fast Quantum Mechanical Algorithm for Database Search"), showed this can be done in O(√(N/M)) queries — a quadratic speedup, and, per Bennett, Bernstein, Brassard and Vazirani's 1997 lower-bound proof (SIAM Journal on Computing, 26(5)), this is provably the best any quantum algorithm can do against a black-box oracle. Quadratic, not exponential — a fact section 7 below returns to.

The algorithm, step by step:

1. |s⟩ = H^⊗n |0⟩^n                     (uniform superposition, amplitude 1/√N each)
2. Repeat k times:
     a. Apply U_f          (flip sign of marked amplitudes)
     b. Apply D = 2|s⟩⟨s| − I    (the "diffusion" or "inversion about the mean" operator)
3. Measure.

The diffusion operator is the part that is easy to misread as mysterious and is actually simple arithmetic. Written out on amplitude vector a = (a₁, …, a_N), (Da)ᵢ = 2·mean(a) − aᵢ — every amplitude gets reflected about the current average. Combined with the oracle's sign flip on marked items, one full iteration has a clean geometric picture: think of the state as living in the 2-D real plane spanned by |α⟩ (the normalized uniform superposition of all N−M unmarked states) and |β⟩ (the normalized uniform superposition of the M marked states). The initial state is |s⟩ = cos(θ/2)|α⟩ + sin(θ/2)|β⟩, where sin(θ/2) = √(M/N). One Grover iteration (oracle then diffusion) is exactly a rotation by angle θ toward |β⟩ within this plane — it does not just nudge the marked amplitude up by luck, it is a deterministic rotation, and that determinism is why the number of iterations has to be chosen precisely rather than "the more the better."

Fully worked example: N = 4, one marked item, traced by hand and in code

Take n = 2 qubits (N = 4 items: |00⟩, |01⟩, |10⟩, |11⟩), with |11⟩ the single marked item. Start from |00⟩ and apply H to both qubits:

|s⟩ = H⊗H |00⟩ = ½(|00⟩ + |01⟩ + |10⟩ + |11⟩)   → amplitude vector (0.5, 0.5, 0.5, 0.5)

Apply the oracle (flip the sign on |11⟩, index 3):

(0.5, 0.5, 0.5, −0.5)

Apply diffusion: mean of the vector = (0.5+0.5+0.5−0.5)/4 = 0.25, so 2·mean = 0.5, and each new amplitude is 0.5 minus the old one:

a₀ = 0.5 − 0.5 = 0
a₁ = 0.5 − 0.5 = 0
a₂ = 0.5 − 0.5 = 0
a₃ = 0.5 − (−0.5) = 1.0

After exactly one iteration the amplitude vector is (0, 0, 0, 1). Measuring now returns |11⟩ with probability 1 — certainty, in a single query, versus a classical expected 2.5 queries (average position of 1 marked item among 4, checked one at a time) or a worst case of 4. The geometric picture confirms this independently: sin(θ/2) = √(1/4) = 0.5, so θ/2 = 30° and θ = 60°. After k = 1 iteration the angle from the |α⟩ axis is (2k+1)(θ/2) = 3 × 30° = 90° — exactly aligned with |β⟩, i.e. certainty. Both routes — direct linear algebra and the rotation formula — agree exactly, which is the check you should always run when a "clean" numeric answer appears.

The same computation, run as code rather than by hand:

import numpy as np

H = (1/np.sqrt(2)) * np.array([[1, 1], [1, -1]])
H2 = np.kron(H, H)                        # Hadamard on both qubits, 4x4

state = np.array([1.0, 0.0, 0.0, 0.0])    # |00>
state = H2 @ state                        # [0.5, 0.5, 0.5, 0.5]

oracle = np.eye(4)
oracle[3, 3] = -1                         # flip sign of |11> (index 3)
state = oracle @ state                    # [0.5, 0.5, 0.5, -0.5]

s = np.array([0.5, 0.5, 0.5, 0.5])
diffusion = 2 * np.outer(s, s) - np.eye(4)
state = diffusion @ state

print(state)                              # [0. 0. 0. 1.]
print(state**2)                           # probabilities: [0. 0. 0. 1.]

Tracing the matrix multiplication by hand confirms the printed result: diffusion has −0.5 on the diagonal and 0.5 everywhere else (since 2×outer(s,s) is 0.5 in every cell, minus the identity). Multiplying that matrix by (0.5, 0.5, 0.5, −0.5) gives 0 for the first three rows (by symmetry — each is −0.25+0.25+0.25−0.25) and 1.0 for the last row (0.25+0.25+0.25+0.25), matching the hand derivation and the code's printed output exactly.

Common misconception, corrected

The claim you will hear most often about quantum computers is some version of: "it checks every possible answer at the same time and instantly knows which one is right." This is wrong, and the Grover derivation above shows exactly where it breaks. Step 1 does put the register into a superposition touching all N basis states at once — that part is true. But step 3 is a measurement, and a measurement returns exactly one basis state, sampled with probability equal to the squared amplitude on that state. If you measured immediately after step 1, before any oracle or diffusion step, you would get a uniformly random item — no better than a classical guess, because every amplitude is equally 1/√N. The entire point of Grover's algorithm is steps 2a–2b: using the oracle's sign flip and the diffusion operator's "reflect about the mean" arithmetic to rotate the state vector so that the marked item's amplitude grows and the unmarked items' amplitudes shrink, over a precisely counted number of iterations, before you ever measure. Superposition gives you a state with many amplitudes; interference (the oracle-then-diffusion combination) is the mechanism that reshapes those amplitudes toward a useful answer; only then does measurement collapse to something informative. A quantum computer with n qubits does not evaluate f on all 2ⁿ inputs and hand you all 2ⁿ results — it runs one interference-shaped superposition through one measurement and gets one answer, with elevated probability of being the one you want.

The number of iterations matters precisely because the mechanism is a rotation, not a monotonic "confidence builder." Consider N = 4 again, but now with M = 2 marked items — say |01⟩ and |11⟩. Here sin(θ/2) = √(2/4) = √0.5, so θ/2 = 45° and θ = 90°. The uniform superposition already sits at 45° from the |α⟩ axis, meaning a single classical guess already succeeds with probability 0.5 (2 marked out of 4). Running the oracle and diffusion once rotates the state by 90° — but starting from 45° and rotating 90° lands you back at −45° from |β⟩ (equivalently, at 135° from |α⟩), which is just as far from full alignment as you started, only on the other side. Working the amplitudes through directly: starting vector (0.5, 0.5, 0.5, 0.5), oracle flips indices 1 and 3 to give (0.5, −0.5, 0.5, −0.5), and applying the same diffusion matrix as before produces (−0.5, 0.5, −0.5, 0.5) — the marked-item probabilities (index 1 and index 3, each 0.25) are completely unchanged from before the iteration. Running Grover here bought nothing; a student who assumes "more Grover iterations always help" would be caught out by exactly this case, and would be caught out worse by continuing for extra iterations, which can actively rotate the state past alignment and reduce the success probability below where it started. Grover's algorithm has an optimum iteration count, not a "more is better" property, precisely because it is a bounded rotation.

Grover vs. Shor: two different sources of speedup

It is worth being precise about what kind of speedup this chapter has been building toward, because "quantum speedup" is not one thing. Grover's algorithm attacks unstructured search and gets a quadratic speedup: O(√N) oracle queries instead of O(N), and — per the Bennett–Bernstein–Brassard–Vazirani bound cited above — this is the best possible for a generic black-box function with no exploitable structure. Shor's algorithm (Peter Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring," Proc. 35th FOCS, 1994, pp. 124–134) attacks a structured problem — integer factorization — and gets an exponential speedup, running in time polynomial in the number of digits of the integer, versus the best known classical factoring algorithms, which run in sub-exponential but still super-polynomial time. The difference is structure: factoring reduces to finding the period of a specific modular-exponentiation function, and Shor's algorithm finds that period using the quantum Fourier transform, exploiting periodicity in a way unstructured search offers no analogue for.

This distinction is why quantum computing is treated as a serious near-term threat to some cryptography and only a minor one to other cryptography, a distinction directly relevant to systems like UPI that lean on both. RSA and elliptic-curve cryptography (used for TLS handshakes and digital signatures across Indian banking and payment rails) rely on factoring or discrete-log hardness — exactly the structured problems Shor's algorithm breaks in polynomial time, given a large enough fault-tolerant quantum computer. Symmetric-key algorithms like AES rely on brute-force key search — the unstructured problem Grover's algorithm only quadratically speeds up, which halves the effective security level (AES-256 against a quantum attacker is roughly as hard as AES-128 against a classical one — still enormous) rather than breaking it outright. This asymmetry is precisely why the US NIST post-quantum cryptography standardization process finalized new public-key replacements in August 2024 — FIPS 203 (ML-KEM, from CRYSTALS-Kyber) for key exchange and FIPS 204 (ML-DSA, from CRYSTALS-Dilithium) for signatures — while leaving AES itself essentially untouched, just recommending longer keys where feasible.

From algorithm to hardware: why √N queries still isn't free

Everything above assumed a perfect oracle and perfect gates. Real qubits decohere — environmental noise randomizes their phase and state over a characteristic timescale (T2, the dephasing time), and every gate applied has some error rate. Superconducting-qubit processors of the kind IBM and Google have built in the early 2020s typically report T2 dephasing times in roughly the 50–150 microsecond range, with two-qubit entangling gates (CNOT or CZ) taking roughly 200–400 nanoseconds to execute — illustrative figures representative of the published literature on these platforms, not a claim about one specific chip. Take round numbers of T2 = 100,000 ns and a gate time of 350 ns: a qubit can support roughly 100,000/350 ≈ 286 sequential two-qubit gates before decoherence has scrambled its state past usefulness.

Now scale Grover up to something realistic: N = 2²⁰ (roughly a million items, the order of magnitude of a mid-sized enrollment database), searching for one marked item. The optimal iteration count is k ≈ (π/4)√N ≈ 804. Each iteration's oracle-plus-diffusion pair requires on the order of several multi-controlled gates per qubit — a conservative estimate of roughly 2n = 40 two-qubit-equivalent gates per iteration for n = 20 qubits. Total gate count: 804 × 40 = 32,160 — about 112 times more sequential gates than the ≈286-gate decoherence budget allows on raw, unprotected qubits. This is precisely why the qubits actually being used for algorithms at this scale have to be logical qubits protected by quantum error correction (many physical qubits encoding one error-corrected logical qubit, per the fault-tolerance threshold theorem), not the bare physical qubits available on today's NISQ (noisy intermediate-scale quantum) devices — a term coined by John Preskill in "Quantum Computing in the NISQ Era and Beyond" (Quantum 2, 79, 2018), which argues that NISQ-era devices, lacking full error correction, cannot yet run algorithms like Grover or Shor at cryptographically or industrially relevant scale. Google's 53-qubit Sycamore experiment (Arute et al., "Quantum Supremacy Using a Programmable Superconducting Processor," Nature 574, 505–510, 2019) demonstrated that a specific, deliberately hard-for-classical-computers sampling task could be run on physical NISQ qubits at all — the paper's own estimate put the classical-supercomputer runtime at roughly 10,000 years against 200 seconds on Sycamore, a figure IBM's researchers publicly contested, arguing a better-optimized classical simulation could complete the same task in about 2.5 days rather than millennia. Even taking IBM's more conservative rebuttal at face value, the gap between "run one demonstration circuit on noisy physical qubits" and "run a million-item Grover search reliably" remains the central open engineering problem in the field, not a solved one.

Active recall

Attempt each question before reading its answer.

1. For N = 8 (3 qubits) with exactly 1 marked item, what is θ/2, and what is the optimal number of Grover iterations?
2. What is the success probability after that many iterations for N = 8, M = 1? What happens if you run one extra iteration beyond the optimum?
3. Starting from the N = 4, M = 1 worked example, suppose instead 3 of the 4 items are marked (M = 3). Compute sin(θ/2), θ, and determine whether running any Grover iterations at all is worth it here.
4. True or false, with justification: "A quantum computer with 20 qubits evaluates a function at all 2²⁰ inputs simultaneously and can report all 2²⁰ results in one run."
5. Grover's algorithm gives O(√N) instead of O(N) queries. Does this turn an NP-complete brute-force search (over N = 2ⁿ candidate solutions, n = input size in bits) into a polynomial-time algorithm? Justify with the actual exponent.
6. Using the illustrative hardware numbers from the systems section (T2 ≈ 100,000 ns, gate time ≈ 350 ns), how many Grover iterations' worth of gates (at ≈ 40 gates/iteration) can raw physical qubits sustain before decoherence, and how does that compare to N = 2¹⁰ (1,024 items)?

Answers

1. sin(θ/2) = √(1/8) ≈ 0.3536, so θ/2 ≈ 20.70° and θ ≈ 41.41°. The closed-form estimate k ≈ (π/4)√(N/M) − 0.5 = (π/4)√8 − 0.5 ≈ 1.72, which rounds to k = 2.

2. At k = 2, the rotation angle is (2×2+1)×20.70° = 103.52°, giving success probability sin²(103.52°) ≈ 0.945 (94.5%) — this matches the standard textbook figure for this exact case. One iteration further (k = 3) gives angle 144.93°, success probability sin²(144.93°) ≈ 0.330 — worse than a single classical guess (1/8 = 0.125 is the classical floor, but 0.330 is far below the 0.945 achieved one iteration earlier). This directly confirms the non-monotonicity point from the misconception section: overshooting the optimum actively hurts.

3. sin(θ/2) = √(3/4) ≈ 0.866, so θ/2 = 60° and θ = 120°. The uniform superposition already sits at 60° from |α⟩, meaning a single classical guess already succeeds with probability M/N = 0.75. The closed-form estimate k ≈ (π/4)√(N/M) − 0.5 = (π/4)√(4/3) − 0.5 ≈ 0.407, which rounds to k = 0 — i.e., run zero Grover iterations and just measure the uniform superposition directly, for 75% success. Running even a single iteration here is actively catastrophic, not merely diminishing returns: with the unmarked item at index 0 and marked items at indices 1, 2, 3, the oracle turns (0.5, 0.5, 0.5, 0.5) into (0.5, −0.5, −0.5, −0.5), and diffusion (mean = −0.25, so 2·mean = −0.5) sends it to (−1.0, 0, 0, 0) — success probability collapses from 75% to 0%, landing certainty entirely on the unmarked item. The rotation formula confirms this independently: the angle after k = 1 is (2×1+1)(θ/2) = 3×60° = 180°, and sin²(180°) = 0. This is the general pattern that Grover's speedup is largest when marked items are rare (M ≪ N) and shrinks toward nothing — and can actively hurt — as M approaches N.

4. False. The superposition after state preparation does have 2²⁰ independent amplitudes, but a single measurement collapses the register to exactly one 20-bit string, sampled with probability equal to that string's squared amplitude — you never observe more than one outcome per run of the circuit. Getting useful information about many inputs at once requires an algorithm (like Grover's oracle-plus-diffusion loop) that uses interference to reshape the amplitude distribution toward a useful answer before that single measurement, not a claim that all answers are simultaneously readable.

5. No. N = 2ⁿ, so √N = √(2ⁿ) = 2^(n/2) — still exponential in n, just with the exponent halved. An NP-complete problem with n = 100 input bits has N = 2¹⁰⁰ candidate solutions; classical brute force is O(2¹⁰⁰), Grover-accelerated brute force is O(2⁵⁰) — astronomically faster in absolute terms, but 2⁵⁰ is still exponential, not polynomial in n. Grover's algorithm does not place NP inside BQP (the quantum-polynomial-time class) for generic instances; it only halves the exponent of an already-exponential search.

6. Max sustainable gates ≈ 100,000 / 350 ≈ 286. For N = 2¹⁰ = 1,024, k ≈ (π/4)√1024 ≈ 25 iterations, needing roughly 25 × 40 = 1,000 gates — about 3.5 times more than the ≈286-gate budget. Even a 1,024-item search already exceeds what raw, error-uncorrected physical qubits with these illustrative coherence numbers can sustain, reinforcing that Grover's quadratic query advantage is necessary but not sufficient — it has to be paired with error-corrected logical qubits before it becomes a usable algorithm at any realistic database size, not just the million-item case worked through in the systems section.

Think About It

Think about this: How would you explain quantum computing basics: qubits and quantum algorithms to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where quantum computing basics: qubits and quantum algorithms is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting quantum computing basics: qubits and quantum algorithms to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind quantum computing basics: qubits and quantum algorithms, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.