Quantum Computation

Quantum Computation 

Quantum Circuits

Quantum circuits are the basic computational model of quantum computing, similar to logic circuits in classical computers.

A quantum circuit is a sequence of quantum gates applied to qubits to perform a computation.

Key Components

• Qubits: Quantum bits that can exist in superposition.
• Quantum Gates: Operations that change the state of qubits.
• Measurement: Converts quantum state into classical information.

Representation

• Qubits are represented by horizontal lines.
• Gates are shown as symbols applied to the lines.

Example Circuit Flow: Input Qubits → Quantum Gates → Entanglement → Measurement → Output

Advantages

• Enables parallel computation through superposition.
• Uses entanglement for complex operations.

Quantum Algorithms

Quantum algorithms are algorithms designed to run on quantum computers that solve problems faster than classical algorithms.

Important Characteristics

• Use superposition
• Use quantum interference
• Exploit entanglement

Famous Quantum Algorithms

1. Shor’s Algorithm – Integer factorization
2. Grover’s Algorithm – Database search
3. Quantum Fourier Transform
4. Phase Estimation Algorithm

Benefits

• Exponential speedup in some problems.
• Quadratic speedup in search problems.

Single Qubit Operations

Single qubit operations manipulate one qubit at a time.

A qubit state is represented as:

$$\mathrm{\mid }\psi ⟩=\alpha \mathrm{\mid }0⟩+\beta \mathrm{\mid }1⟩$$

$|\psi\rangle = \alpha |0\rangle + \beta |1\rangle$

Where:

• α and β are complex probability amplitudes.
• |α|² + |β|² = 1

Common Single Qubit Gates

Gate	Function
Pauli-X	Bit flip
Pauli-Y	Rotation
Pauli-Z	Phase flip
Hadamard (H)	Creates superposition

Example:

|0> --H--> (|0> + |1>) / √2

Importance

• Fundamental operations in quantum circuits.
• Used to create superposition states.

Controlled Operations

Controlled operations involve two or more qubits, where one qubit controls the operation applied to another.

Most common controlled gate

CNOT Gate (Controlled NOT)

• If control qubit = 1 → target qubit flips
• If control qubit = 0 → no change

Truth Table:

Control	Target	Output
0	0	00
0	1	01
1	0	11
1	1	10

Applications

• Creating entanglement
• Used in quantum teleportation
• Important in many quantum algorithms

Measurement in Quantum Computing

Measurement is the process of observing a quantum state, converting it into classical information.

Example:

$$\mathrm{\mid }\psi ⟩=\alpha \mathrm{\mid }0⟩+\beta \mathrm{\mid }1⟩$$

After measurement:

• Probability of 0 = |α|²
• Probability of 1 = |β|²

Important Properties

• Measurement collapses the wavefunction.
• After measurement, the system remains in the measured state.

Example:

State before measurement:
(|0> + |1>) / √2

After measurement:
Either |0> or |1>

Universal Quantum Gates

Universal quantum gates are gates that can build any quantum computation.

Similar to NAND gate in classical computing.

Universal Gate Sets

Common universal sets:

1. Hadamard (H)
2. Phase gate (S)
3. T gate
4. CNOT gate

These gates together can approximate any quantum algorithm.

Simulation of Quantum Systems

One of the most important applications of quantum computing is simulating quantum systems.

Classical computers struggle because quantum systems grow exponentially complex.

Example applications:

Field	Use
Chemistry	Molecule simulation
Physics	Particle interactions
Material Science	New material discovery
Drug Discovery	Protein simulation

Example: Simulation of molecular structures.

Feynman (1982) proposed quantum computers mainly for this purpose.

Quantum Fourier Transform (QFT)

Quantum Fourier Transform is the quantum version of the classical discrete Fourier transform.

$QFT(|x\rangle)=\frac{1}{\sqrt{N}}\sum_{y=0}^{N-1} e^{2\pi ixy/N}|y\rangle$

Characteristics

• Works exponentially faster than classical FFT in many quantum algorithms.
• Core part of Shor’s Algorithm.

Applications

• Period finding
• Phase estimation
• Cryptography breaking

Phase Estimation Algorithm

Phase estimation determines the phase (eigenvalue) of a quantum state.

If a unitary operator U acts on eigenvector |ψ⟩:

$$U\mathrm{\mid }\psi ⟩=e^{2\pi i\varphi }\mathrm{\mid }\psi ⟩$$

$U|\psi\rangle = e^{2\pi i\phi}|\psi\rangle$

Where:

• φ is the phase value.

Steps

1. Prepare superposition.
2. Apply controlled unitary operations.
3. Apply Quantum Fourier Transform.
4. Measure to estimate phase.

Applications

• Shor’s algorithm
• Quantum simulations
• Eigenvalue problems

Applications of Quantum Computing

Quantum computing has many powerful applications.

Field	Application
Cryptography	Breaking RSA encryption
Artificial Intelligence	Quantum machine learning
Optimization	Logistics optimization
Chemistry	Molecule simulation
Finance	Risk modeling
Medicine	Drug discovery

Companies working on quantum computing:

• IBM
• Google
• Microsoft
• Intel

Quantum Search Algorithms

Quantum search algorithms search unsorted databases faster than classical methods.

Classical Search Complexity

$$O(N)$$

Quantum Search (Grover’s Algorithm)

$$O(\sqrt{N})$$

Steps

1. Initialize superposition.
2. Apply oracle.
3. Apply diffusion operator.
4. Repeat √N times.

Benefit

• Quadratic speed improvement.

Quantum Counting

Quantum counting is an extension of Grover’s search algorithm.

It estimates how many solutions exist in a database.

Formula approximation:

$$M=N{\sin }^2(\theta )$$

Where:

• M = number of solutions
• N = total elements

Uses

• Counting valid database entries
• Estimating solution probability

Speeding Up NP-Complete Problems

NP-complete problems are extremely difficult for classical computers.

Examples:

• Traveling Salesman Problem
• Boolean satisfiability problem (SAT)
• Graph coloring

Quantum computing may provide faster solutions through:

• Quantum parallelism
• Grover’s algorithm
• Quantum annealing

However:

• No proven exponential solution yet for all NP-complete problems.

Quantum Search for an Unstructured Database

Unstructured database means data without indexing or ordering.

Example:

List of 1 million numbers
Find number 728193

Classical Search:

• Average complexity = O(N)

Quantum Search (Grover's Algorithm):

• Complexity = O(√N)

Example:

Database Size	Classical Steps	Quantum Steps
1,000,000	500,000 avg	~1000

Impact

• Much faster searching in large datasets.

Summary

Topic	Key Idea
Quantum Circuits	Model for quantum computation
Quantum Algorithms	Faster algorithms using quantum mechanics
Single Qubit Operations	Manipulate individual qubits
Controlled Operations	Multi-qubit conditional operations
Measurement	Converts quantum data to classical
Universal Gates	Can build any quantum computation
Quantum Simulation	Simulating molecules and physics
QFT	Core transform used in many algorithms
Phase Estimation	Finds phase of eigenvalues
Applications	AI, cryptography, chemistry
Quantum Search	Faster database search
Quantum Counting	Counts number of solutions
NP-Complete Speedup	Potential faster solutions
Unstructured Search	Grover’s √N speedup