# Quantum Computing

Computation exploiting superposition and entanglement, promising asymptotic speedups on specific problem classes rather than general computing.

**Stands alone:** nothing in the curriculum requires this first, and nothing yet builds on it.

*Mathematical Foundations · Numerical Methods*


## Why learn this

You are learning this because it helps you separate fact from hype in news reports about quantum computers. It explains why these machines are not just 'faster PCs' and clarifies their real potential in fields like secure communications, complex system optimization, and materials science. After reading this, you will understand why a specific quantum method threatens current internet security standards—specifically, the ability to break the math that keeps your bank details safe—and why building reliable quantum machines is currently so difficult. You will also see why your laptop will never use quantum physics for everyday tasks like word processing. 

To make this concrete: consider the number 15. A normal computer finds its factors (3 and 5) by trying numbers one by one. This works fine for small numbers. But if the number has hundreds of digits, a normal computer would take longer than the age of the universe to find the factors. This is 'exponential time,' which means the work required grows explosively with each extra digit. A quantum computer can do this in 'polynomial time,' which means the work grows at a manageable rate, like $n^2$ or $n^3$. This difference is why quantum computers are not just 'fast'; they can solve certain problems that are practically impossible for any normal computer, no matter how powerful.


## The intuition

Imagine a standard coin. It lands either heads or tails. A normal computer works with bits that are exactly like coins: each one is definitively heads (0) or tails (1). Now imagine a spinning coin. While it spins, it is neither fully heads nor fully tails; it is a blur of both possibilities simultaneously. In quantum computing, this spinning state is called superposition. A qubit (the unit of quantum information) behaves like this spinning coin. It holds the potential for being heads or tails at the same time.

With one qubit, you have a mix of 0 and 1. With two qubits, you have a mix of all four combinations: 00, 01, 10, and 11. With ten qubits, you manage a blend of 1,024 possibilities at once. With just fifty qubits, the number of simultaneous possibilities exceeds the number of atoms in the observable universe. This allows quantum computers to process vast amounts of data in parallel.

However, there is a catch: you cannot simply look at the spinning coin and read the answer. When you measure it, the spin stops, and it collapses randomly into either heads or tails. The art of quantum computing lies in manipulating these spinning coins so that, when they finally stop, they are overwhelmingly likely to land on the correct answer.

This requires entanglement, a phenomenon where two qubits become linked such that the state of one instantly influences the other, no matter the distance between them. Entanglement allows the computer to coordinate its massive parallel processing power effectively. The key takeaway is not speed in the traditional sense, but the ability to shape probabilities so that the right answer emerges when measurement occurs.

Consider the problem of factoring large numbers. To secure your online banking, banks use a number that is the product of two huge prime numbers. For example, if we use small primes for clarity, $3 	imes 5 = 15$. A normal computer might try dividing by 2, then 3, then 4... until it finds the factors. If the number has 200 digits, trying every possibility is 'exponential time.' The time required doubles with every few extra digits. It becomes physically impossible. A quantum algorithm, such as Shor's algorithm, uses superposition and entanglement to explore these relationships all at once, reducing the task to 'polynomial time,' where the time grows slowly and predictably with the size of the number.


## An analogy

Think of a library where every book represents a possible solution to a problem. A classical computer is like a librarian who checks out books one by one, page by page, until finding the correct answer. If there are millions of books, this takes a long time. A quantum computer is like a magical librarian who can read all the books simultaneously in a superposition of states. This librarian does not get confused by reading everything at once because they use entanglement to keep track of how the books relate to each other. The magic trick is that this librarian can subtly adjust the 'weight' of each book—making incorrect answers fainter and correct answers louder—so that when they finally present the result, it is almost certainly the right one.

The analogy breaks down because, unlike a human librarian who can stop and think, a quantum system cannot be paused or inspected mid-calculation without collapsing the entire process. Also, the 'louder' or 'correct' answer is not guaranteed, only made highly probable.


## Definition

Quantum computing is a computational model that uses qubits in superposition to process multiple possibilities simultaneously and entanglement to coordinate them, producing probabilistic answers that are biased toward correct solutions for specific types of problems.


## How it connects

You may have encountered the Kalman Filter in your notes on numerical methods; this is a technique that uses noisy measurements to estimate the current state of a system by combining predictions with observations. It manages uncertainty through probability distributions, much like quantum computing manages potential outcomes, though it does so using classical arithmetic rather than quantum physics. You might also see references to asymptotic speedup in your research notes; this describes how the time required for an algorithm grows relative to the input size as the problem gets larger. Quantum computers offer asymptotic speedup by solving certain problems (like factoring large numbers) in polynomial time, whereas the best classical methods require exponential time.


## The mathematics

The mathematics behind quantum computing is linear algebra over complex numbers. That is the branch of mathematics that deals with lists of numbers (vectors) and tables of numbers (matrices), and with the rules for combining them. It is the same branch that underlies the Kalman filter and every neural network — but here the numbers are complex (they include the square root of minus one), and the operations have a probabilistic interpretation.

Before we touch quantum computing, you need to understand two operations from linear algebra. The first is the dot product of two vectors. A vector is just an ordered list of numbers, like [2, 3] or [1, 0, -1]. To compute the dot product of two vectors of the same length, you multiply each pair of entries and then add up all the products. For example, the dot product of [2, 3] and [4, 5] is 2*4 + 3*5 = 8 + 15 = 23. The dot product measures how much the two vectors point in the same direction.

The second operation is matrix multiplication. A matrix is a rectangular table of numbers. When you multiply a matrix by a vector, you get a new vector, where each entry is the dot product of a row of the matrix with the vector. For example, if the matrix is [ [1, 2], [3, 4] ] and the vector is [5, 6], then the first entry of the result is 1*5 + 2*6 = 17, the second entry is 3*5 + 4*6 = 39, so the result is [17, 39].

In quantum computing, a qubit is a vector with two complex-number entries, representing the amplitudes of '0' and '1'. A measurement picks one with a probability equal to the squared magnitude of the amplitude. A quantum operation is a matrix that must be unitary — it preserves total probability — and it transforms the vector. Entanglement is when two qubits share a state that cannot be written as two separate qubit vectors.

To see how the mathematics applies, we will work through a simple example with real numbers, ignoring the complex part for clarity.

For a qubit in state |ψ⟩ = α|0⟩ + β|1⟩, the probabilities of measuring 0 and 1 are |α|² and |β|², respectively, and they must sum to 1. Applying a unitary matrix U (such as the X gate [[0,1],[1,0]]) transforms the state to |ψ'⟩ = U|ψ⟩. More generally, a system of n qubits has 2^n amplitudes, and a measurement is a projection onto one of the basis states.


## A worked example

We will use a single qubit with two amplitudes, written as a vector [a0, a1]. Initially, the qubit is in the state [1, 0] (definitely 0). We apply a quantum operation that creates a superposition: it transforms the state to [0.8, 0.6] (both amplitudes are nonzero). The probability of measuring 0 is 0.8^2 = 0.64, and the probability of measuring 1 is 0.6^2 = 0.36. We will now verify that these probabilities sum to 1, and see what happens if we apply a second operation.

Step 1: 0.8^2 = 0.64   # Probability of measuring 0.
Step 2: 0.6^2 = 0.36   # Probability of measuring 1.
Step 3: 0.64 + 0.36 = 1.00   # Total probability is 1, as required.

Now we apply the X gate. The X gate is a specific matrix that swaps the two entries of a vector. Its rows are [0, 1] and [1, 0]. To find the new state, we multiply this matrix by our current state vector [0.8, 0.6].

Step 4: Calculate the first entry of the new state. This is the dot product of the first row of the X gate, which is [0, 1], with the state vector [0.8, 0.6]. We multiply corresponding entries and add them: (0 * 0.8) + (1 * 0.6). This equals 0 + 0.6 = 0.6.

Step 5: Calculate the second entry of the new state. This is the dot product of the second row of the X gate, which is [1, 0], with the state vector [0.8, 0.6]. We multiply corresponding entries and add them: (1 * 0.8) + (0 * 0.6). This equals 0.8 + 0 = 0.8.

Step 6: The new state vector is [0.6, 0.8]. The amplitudes have been swapped.

Step 7: Calculate the new probabilities. The probability of measuring 0 is now the square of the first entry: 0.6^2 = 0.36. The probability of measuring 1 is the square of the second entry: 0.8^2 = 0.64.

Result: The X gate flipped the probabilities: before it, 0 was more likely (64%); after it, 1 is more likely (64%). This shows how a quantum operation changes the state and thus the probabilities of measurement outcomes.


## From scratch, in Python

```python
# Plain Python, no frameworks, runnable.
# We'll represent a qubit as a list of two real numbers (ignoring complex for simplicity).
# The state is [amplitude0, amplitude1].

# Initial state: definitely 0
state = [1.0, 0.0]

# Define the X gate (NOT gate) as a 2x2 matrix, as a list of lists
X_gate = [[0.0, 1.0],
          [1.0, 0.0]]

# Function to multiply a matrix by a vector (list of numbers)
def matrix_vector_multiply(matrix, vector):
    result = []
    for row in matrix:
        # dot product of this row with the vector
        total = 0.0
        for i in range(len(vector)):
            total += row[i] * vector[i]
        result.append(total)
    return result

# Apply the X gate to the state
new_state = matrix_vector_multiply(X_gate, state)
print("Before measurement, state:", new_state)

# Probabilities are squares of amplitudes
prob0 = new_state[0] ** 2
prob1 = new_state[1] ** 2
print("Probability of measuring 0:", prob0)
print("Probability of measuring 1:", prob1)

# Simulate a measurement using random choice
import random
outcome = random.choices([0, 1], weights=[prob0, prob1])[0]
print("Measured outcome:", outcome)
```


## The same thing, with a framework

```python
import numpy as np

# Represent state as a NumPy array
state = np.array([1.0, 0.0])

# Define X gate
X = np.array([[0, 1], [1, 0]])

# Apply gate: matrix multiplication
new_state = np.dot(X, state)
print(new_state)

# Probabilities
probs = np.abs(new_state)**2
print(probs)

# Sample an outcome (using NumPy's random)
outcome = np.random.choice([0, 1], p=probs)
print(outcome)

# Underneath, np.dot does exactly the same loops we wrote — multiplying
# entries and adding them up.
```


## What the code does

We start with the variable `state`, which is a list of two numbers — our qubit's amplitudes. A list is like a row of boxes, each holding a value; you can change what is in a box afterwards. We then define `X_gate` as a list of lists — that is a table with two rows and two columns, exactly like the matrix we wrote on paper. The function `matrix_vector_multiply` is the heart of it: it loops over each row of the matrix, and inside that loop it computes the dot product of that row with the vector. The dot product is the sum of products we did by hand. The function appends each result to a new list, which becomes the new state. Then we print the new state and compute probabilities by squaring each amplitude. Finally, the `random.choices` line picks an outcome — 0 or 1 — with the probabilities we calculated. This is exactly what a quantum computer would do, but we are using a normal computer to simulate it, so it is just a random pick.


## Common misconceptions

**Quantum computers are just faster versions of normal computers** — Quantum computers will make all programs run faster, like going from a single-core to a multi-core CPU.

Quantum speedups are only for specific algorithms (e.g., factoring, search). For most tasks — like adding two numbers or running a text editor — quantum computers are slower, due to overhead and the need for error correction. They are not a general-purpose speed booster. In fact: Quantum computing offers asymptotic speedups only on certain problem classes where you can exploit superposition and entanglement. It is a different computational model, not a faster transistor.

**Quantum computers can try all answers at once and pick the right one** — A quantum computer with 300 qubits can check all 2^300 possibilities simultaneously and always output the correct one.

Quantum computers do hold a superposition of all possible answers, but when you measure, you get a random outcome. Only cleverly designed algorithms (like Grover's) increase the probability of the right answer, but they still require many repetitions to be reliable. They do not magically 'pick' the correct answer. In fact: Quantum algorithms shape the probabilities so that the correct answer is more likely to be measured. The art is in designing the operations to amplify the right amplitude.

**Entanglement is like teleporting information faster than light** — Entanglement lets you send information instantly across any distance, so it could be used for faster-than-light communication.

Entanglement does correlate measurements, but you cannot use it to send a message without also sending classical information. This is the no-communication theorem. If you try to use it for communication, you still need a classical signal to interpret the results, and that signal is limited by the speed of light. In fact: Entanglement is a resource for computation and cryptography, but it does not allow faster-than-light communication. It is about correlation, not causation.

**Quantum error correction is a minor technical detail** — Sooner or later we will fix the qubits and quantum computers will just work.

Qubits are extremely fragile; they decohere in microseconds. To build a reliable logical qubit, you need thousands of physical qubits, and the overhead grows with the size of the computation. Error correction is the dominant obstacle, not a small tweak. In fact: Quantum error correction uses many physical qubits to encode one logical qubit, and that overhead is the main reason large-scale quantum computers are still years away.

**Quantum computers will break all encryption, so we should panic** — As soon as a quantum computer is built, all our bank accounts and passwords will be exposed.

Shor's algorithm breaks RSA and ECC, but not all encryption. Symmetric encryption (AES) can be made quantum-safe by doubling key sizes, and post-quantum cryptography (lattice-based, etc.) is already being standardized. The threat is real for certain algorithms, but the migration is already underway. In fact: Quantum computers threaten certain public-key cryptosystems, but there are replacements that are believed to be quantum-resistant. The main near-term impact is indeed forcing cryptographic migration, as your notes say.


## In short

Quantum computing is a different way of computing, using qubits in superposition and entanglement to manipulate probabilities. It offers speedups only for specific problems (like factoring and search), not for everything. The main practical obstacle is error correction, and the near-term impact on the AI world is mostly about cryptography, not faster ML models. Remember: a quantum computer is like a clever restaurant that prepares all dishes at once but can only ever serve one — so the trick is to make the right dish the most likely to be served.


## Where this is used

Where is quantum computing actually used in building AI systems, and how? The honest answer is: not yet in production, but there are concrete research directions and a major indirect effect on security.

In large language models: Today's LLMs run on classical hardware — GPUs and TPUs — and quantum computing does not accelerate the transformer architecture itself. However, researchers are exploring quantum algorithms for specific subroutines, such as matrix multiplication (the core of attention) using quantum linear algebra. These are experimental and far from practical, but they show what a quantum speedup might look like. For example, quantum matrix multiplication could theoretically reduce the complexity from O(N^3) to something like O(N^2 log N), but the overhead of encoding the data into quantum states and reading out the result usually cancels the gain. So, for LLMs, the answer is: no practical impact yet, but it is an active research area.

In small models on devices: On a phone or a laptop, you need inference to run quickly and with low energy. Quantum computing has no relevance here today — quantum computers are huge, cryogenically cooled machines, not something in your pocket. The promise of quantum machine learning (QML) is for training models on quantum data (e.g., from quantum chemistry simulations), but again, not for edge devices.

In retrieval-augmented generation (RAG): RAG relies on embedding vectors and similarity search — classical operations. Quantum computers do not help with that either. However, there is a theoretical idea of quantum nearest-neighbour search using Grover's algorithm, which can find an item in an unsorted database in O(√N) time instead of O(N). For a vector database with millions of embeddings, √N would be a speedup, but the overhead of building the superposition and the error correction costs make it impractical. Also, a classical approximate nearest neighbour search is already very fast. So: not used.

In agentic systems: Agents plan, call tools, and act in loops. That is classical software engineering. Quantum computers do not help with planning or tool calling. The only speculative angle is using quantum computers to solve combinatorial optimization problems (like the traveling salesman problem) that might appear in a planner's subroutines, but again, current quantum hardware (NISQ) is too noisy, and the speedup is not there for practical sizes.

In everyday applied machine learning — recommendation, vision, forecasting, fraud detection: None of these use quantum computing in production. Anyone selling 'quantum AI' for fraud detection today is overpromising. The real impact of quantum computing on everyday ML is an indirect one: the threat to current cryptography. If a large-scale fault-tolerant quantum computer is ever built, Shor's algorithm could break RSA and elliptic curve encryption. That would affect every system that relies on secure communication — including all AI services that transmit sensitive data. The response is already underway: NIST has standardized post-quantum cryptographic algorithms, so developers are migrating. This is the 'forcing cryptographic migration' from your notes.

What does a developer actually write? A developer building a quantum algorithm uses a framework like Qiskit (IBM) or Cirq (Google). You define a quantum circuit: you create qubits, apply gates (like the X gate we simulated), and measure. For example:

```python
from qiskit import QuantumCircuit, Aer, execute

qc = QuantumCircuit(1, 1)
qc.x(0)  # apply X gate to qubit 0
qc.measure(0, 0)

backend = Aer.get_backend('qasm_simulator')
job = execute(qc, backend, shots=1024)
result = job.result()
counts = result.get_counts()
print(counts)  # {'1': 1024} — always 1
```

This implements the X gate we did by hand. Underneath, the simulator does exactly what our plain Python code did: it applies the matrix to the state vector and samples.

What breaks when it is done badly? The biggest failure is quantum decoherence: the qubits interact with the environment and lose their superposition. If you do not handle error correction, the calculation is garbage. Also, if you design an algorithm that does not account for the probabilistic nature of measurement, you might get the wrong answer with high probability. The practical lesson for an AI practitioner is: understand what quantum computers can and cannot do, and be skeptical of claims of 'quantum speedup' — the overhead of encoding, decoding, and error correction often eats the advantage, especially for small problems. The only near-term impact that affects you directly is the cryptographic migration, which you should track.


---

Read this on the web: https://basavapurushottam.com/learn-ai/quantum-computing
