Quantum algorithms are what make quantum computing powerful. They exploit quantum mechanical phenomena to solve problems faster than classical algorithms. In this guide, we'll explore the most important quantum algorithms and understand how they achieve quantum advantage.
What Makes Quantum Algorithms Special?
Classical algorithms operate on bits and use logical operations. Quantum algorithms work with qubits and leverage:
- 1Superposition: Process multiple states simultaneously
- 2Entanglement: Create correlations between qubits
- 3Interference: Amplify correct answers, cancel wrong ones
typescript
// Quantum vs Classical speedup comparison
interface AlgorithmComparison {
algorithm: string;
classicalComplexity: string;
quantumComplexity: string;
speedup: string;
}
const comparisons: AlgorithmComparison[] = [
{
algorithm: 'Factoring (Shor)',
classicalComplexity: 'O(exp(n^(1/3)))',
quantumComplexity: 'O(n^3)',
speedup: 'Exponential',
},
{
algorithm: 'Search (Grover)',
classicalComplexity: 'O(N)',
quantumComplexity: 'O(√N)',
speedup: 'Quadratic',
},
{
algorithm: 'Simulation',
classicalComplexity: 'O(2^n)',
quantumComplexity: 'O(poly(n))',
speedup: 'Exponential',
},
];
console.table(comparisons);Shor's Algorithm
Shor's algorithm can factor large numbers exponentially faster than the best known classical algorithms, breaking RSA encryption.
Classical Factoring
typescript
// Classical factoring (inefficient)
class ClassicalFactoring {
trialDivision(n: number): number[] {
const factors: number[] = [];
for (let i = 2; i <= Math.sqrt(n); i++) {
while (n % i === 0) {
factors.push(i);
n /= i;
}
}
if (n > 1) {
factors.push(n);
}
return factors;
}
// Pollard's rho algorithm (better, still slow)
pollardsRho(n: number): number[] {
if (n === 1) return [];
if (n % 2 === 0) return [2, ...this.pollardsRho(n / 2)];
let x = 2;
let y = 2;
let d = 1;
while (d === 1) {
x = (x * x + 1) % n;
y = (y * y + 1) % n;
y = (y * y + 1) % n;
d = Math.gcd(Math.abs(x - y), n);
}
if (d === n) return [n];
return [d, ...this.pollardsRho(n / d)];
}
}Shor's Algorithm Concept
typescript
// Simplified Shor's algorithm simulation
class ShorsAlgorithm {
// Key quantum subroutine: period finding
private quantumPeriodFinding(a: number, N: number): number {
// In real quantum computing, this uses quantum Fourier transform
// to find the period of f(x) = a^x mod N
// Classical simulation for small numbers
let x = 1;
const seen = new Map<number, number>();
for (let i = 0; i < N * N; i++) {
if (seen.has(x)) {
return i - seen.get(x)!;
}
seen.set(x, i);
x = (x * a) % N;
}
return N;
}
// Full Shor's algorithm
factor(N: number): number[] {
if (N <= 1) return [];
if (N === 2) return [2];
if (N % 2 === 0) return [2, ...this.factor(N / 2)];
// Check if perfect power
const sqrt = Math.floor(Math.sqrt(N));
if (sqrt * sqrt === N) return [...this.factor(sqrt), ...this.factor(sqrt)];
// Main quantum loop
for (let a = 2; a < N; a++) {
const gcd = Math.gcd(a, N);
if (gcd > 1) {
return [gcd, ...this.factor(N / gcd)];
}
// Quantum period finding
const r = this.quantumPeriodFinding(a, N);
if (r % 2 === 1) continue;
const x = this.modPow(a, r / 2, N);
if (x === N - 1) continue;
const factor1 = Math.gcd(x + 1, N);
const factor2 = Math.gcd(x - 1, N);
if (factor1 > 1 && factor1 < N) {
return [...this.factor(factor1), ...this.factor(N / factor1)];
}
if (factor2 > 1 && factor2 < N) {
return [...this.factor(factor2), ...this.factor(N / factor2)];
}
}
return [N]; // N is prime
}
private modPow(base: number, exp: number, mod: number): number {
let result = 1;
base = base % mod;
while (exp > 0) {
if (exp % 2 === 1) {
result = (result * base) % mod;
}
exp = Math.floor(exp / 2);
base = (base * base) % mod;
}
return result;
}
demonstrateRSAVulnerability(): void {
console.log('=== RSA Vulnerability Demonstration ===
');
// Small RSA key pair (for demonstration)
const p = 61;
const q = 53;
const N = p * q;
console.log(`RSA modulus N = ${N}`);
console.log(`Classical factoring would take a long time...\n`);
const factors = this.factor(N);
console.log(`Shor's algorithm found factors: ${factors.join(' × ')}`);
console.log('RSA encryption would be broken!');
// Real RSA uses 2048-bit numbers (617 digits)
// Classical computers can't factor these in reasonable time
// Quantum computers with Shor's algorithm could factor them in hours
}
}
// Usage
const shor = new ShorsAlgorithm();
shor.demonstrateRSAVulnerability();Grover's Search Algorithm
Grover's algorithm provides quadratic speedup for unstructured search problems.
typescript
// Grover's algorithm implementation
class GroverSearch {
private n: number;
private size: number;
constructor(numItems: number) {
this.n = Math.ceil(Math.log2(numItems));
this.size = Math.pow(2, this.n);
}
// Oracle: marks the target state
private oracle(amplitudes: number[], target: number): number[] {
return amplitudes.map((amp, idx) =>
idx === target ? -amp : amp
);
}
// Diffusion operator: inverts about average
private diffusion(amplitudes: number[]): number[] {
const average = amplitudes.reduce((sum, val) => sum + val, 0) / amplitudes.length;
return amplitudes.map(amp => 2 * average - amp);
}
// Grover iteration
private groverIteration(amplitudes: number[], target: number): number[] {
let amps = this.oracle(amplitudes, target);
amps = this.diffusion(amps);
return amps;
}
// Full Grover's algorithm
search(items: string[], target: string): number {
const targetIndex = items.indexOf(target);
if (targetIndex === -1) return -1;
// Optimal number of iterations
const iterations = Math.floor((Math.PI / 4) * Math.sqrt(this.size));
// Initialize uniform superposition
let amplitudes = Array(this.size).fill(1 / Math.sqrt(this.size));
// Apply Grover iterations
for (let i = 0; i < iterations; i++) {
amplitudes = this.groverIteration(amplitudes, targetIndex);
}
// Measure
const probabilities = amplitudes.map(amp => amp * amp);
const cumulative: number[] = [];
let sum = 0;
for (const prob of probabilities) {
sum += prob;
cumulative.push(sum);
}
const random = Math.random();
for (let i = 0; i < cumulative.length; i++) {
if (random < cumulative[i]) {
return i;
}
}
return probabilities.length - 1;
}
demonstrateSearch(): void {
console.log('=== Grover's Search Demonstration ===
');
const database = [
'apple', 'banana', 'cherry', 'date', 'elderberry',
'fig', 'grape', 'honeydew', 'kiwi', 'lemon',
];
const target = 'kiwi';
console.log(`Searching for "${target}" in database of ${database.length} items`);
console.log(`Classical search: O(${database.length}) queries`);
console.log(`Quantum search: O(${Math.floor(Math.sqrt(database.length))}) queries\n`);
const foundIndex = this.search(database, target);
console.log(`Found at index ${foundIndex}: ${database[foundIndex]}`);
// Show probability distribution
console.log('
Probability distribution:');
const amplitudes = Array(database.length).fill(1 / Math.sqrt(database.length));
const iterations = Math.floor((Math.PI / 4) * Math.sqrt(database.length));
let amps = amplitudes;
for (let i = 0; i < iterations; i++) {
amps = this.groverIteration(amps, database.indexOf(target));
}
amps.forEach((amp, idx) => {
console.log(` ${database[idx]}: ${(amp * amp * 100).toFixed(2)}%`);
});
}
}
// Usage
const grover = new GroverSearch(10);
grover.demonstrateSearch();Applications of Grover's Algorithm
typescript
class GroverApplications {
// Database search
databaseSearch(): void {
const database = Array.from({ length: 1000 }, (_, i) => `item_${i}`);
const search = new GroverSearch(database.length);
const target = 'item_735';
const foundIndex = search.search(database, target);
console.log(`Found ${target} at index ${foundIndex}`);
}
// Finding minimum
findMinimum(arr: number[]): number {
// Use Grover's algorithm to find minimum faster than classical
// This is a simplified version
let min = arr[0];
for (const val of arr) {
if (val < min) min = val;
}
return min;
}
// Graph collision detection
detectCollision(graph: number[][], targetColor: string): boolean {
// Use Grover's to find if any two adjacent nodes have same color
const edges = [];
for (let i = 0; i < graph.length; i++) {
for (let j = i + 1; j < graph.length; j++) {
if (graph[i][j] > 0) {
edges.push([i, j]);
}
}
}
// Search for collision
const search = new GroverSearch(edges.length);
const colors = ['red', 'green', 'blue'];
// Simplified - in reality would use quantum oracles
for (const [u, v] of edges) {
// Would use quantum search here
}
return false;
}
}Quantum Fourier Transform (QFT)
QFT is a key subroutine in many quantum algorithms.
typescript
// Quantum Fourier Transform
class QuantumFourierTransform {
// Classical FFT for comparison
classicalFFT(signal: number[]): number[] {
const N = signal.length;
if (N <= 1) return signal;
const even = this.classicalFFT(signal.filter((_, i) => i % 2 === 0));
const odd = this.classicalFFT(signal.filter((_, i) => i % 2 === 1));
const result: number[] = [];
for (let k = 0; k < N / 2; k++) {
const t = Math.exp(-2 * Math.PI * 1j * k / N) * odd[k];
result[k] = even[k] + t;
result[k + N / 2] = even[k] - t;
}
return result;
}
// Quantum FFT circuit (conceptual)
quantumQFT(state: number[]): number[] {
// QFT provides exponential speedup
// Applied to quantum state amplitudes
const N = state.length;
const result = new Array(N).fill(0);
for (let k = 0; k < N; k++) {
for (let n = 0; n < N; n++) {
result[k] += state[n] * Math.exp(2 * Math.PI * 1j * k * n / N);
}
result[k] /= Math.sqrt(N);
}
return result;
}
demonstrateQFT(): void {
console.log('=== Quantum Fourier Transform ===
');
const signal = [1, 2, 3, 4, 3, 2, 1, 0];
console.log('Input signal:', signal);
console.log('Classical FFT:', this.classicalFFT(signal).map(c => Math.abs(c)));
console.log('Quantum QFT would provide exponential speedup');
}
}Variational Quantum Algorithms
Variational algorithms are hybrid quantum-classical algorithms suitable for near-term quantum computers.
VQE (Variational Quantum Eigensolver)
typescript
// Variational Quantum Eigensolver for finding ground state energy
class VQE {
private numQubits: number;
constructor(numQubits: number) {
this.numQubits = numQubits;
}
// Ansatz (parameterized quantum circuit)
ansatz(parameters: number[], state: number[]): number[] {
// Apply parameterized quantum gates
let newState = [...state];
// Simplified - would use real quantum gates
for (let i = 0; i < parameters.length; i++) {
const theta = parameters[i];
// Rotation gates
newState = newState.map((amp, idx) =>
amp * Math.cos(theta) + (idx % 2 === 0 ? 0 : amp * Math.sin(theta))
);
}
return newState;
}
// Hamiltonian expectation value
expectationValue(state: number[], hamiltonian: number[][]): number {
let energy = 0;
for (let i = 0; i < hamiltonian.length; i++) {
for (let j = 0; j < hamiltonian[i].length; j++) {
energy += hamiltonian[i][j] * state[i] * state[j];
}
}
return energy;
}
// Classical optimization loop
optimize(hamiltonian: number[][]): { parameters: number[]; energy: number } {
let parameters = Array(this.numQubits).fill(0).map(() => Math.random() * Math.PI);
let learningRate = 0.1;
for (let iteration = 0; iteration < 100; iteration++) {
// Initialize state
let state = new Array(Math.pow(2, this.numQubits)).fill(0);
state[0] = 1;
// Apply ansatz
state = this.ansatz(parameters, state);
// Calculate energy
const energy = this.expectationValue(state, hamiltonian);
// Update parameters (gradient descent)
const gradient = this.computeGradient(parameters, hamiltonian);
parameters = parameters.map((p, i) => p - learningRate * gradient[i]);
if (iteration % 10 === 0) {
console.log(`Iteration ${iteration}: Energy = ${energy.toFixed(6)}`);
}
}
const finalState = this.ansatz(parameters, new Array(Math.pow(2, this.numQubits)).fill(0).map((_, i) => i === 0 ? 1 : 0));
const finalEnergy = this.expectationValue(finalState, hamiltonian);
return { parameters, energy: finalEnergy };
}
private computeGradient(parameters: number[], hamiltonian: number[][]): number[] {
// Numerical gradient computation
const epsilon = 0.01;
const gradient: number[] = [];
for (let i = 0; i < parameters.length; i++) {
const paramsPlus = [...parameters];
paramsPlus[i] += epsilon;
const paramsMinus = [...parameters];
paramsMinus[i] -= epsilon;
const state = new Array(Math.pow(2, this.numQubits)).fill(0);
state[0] = 1;
const energyPlus = this.expectationValue(this.ansatz(paramsPlus, state), hamiltonian);
const energyMinus = this.expectationValue(this.ansatz(paramsMinus, state), hamiltonian);
gradient.push((energyPlus - energyMinus) / (2 * epsilon));
}
return gradient;
}
demonstrateVQE(): void {
console.log('=== Variational Quantum Eigensolver ===\n');
// Simple Hamiltonian (2-qubit system)
const hamiltonian = [
[1, 0.1, 0.1, 0],
[0.1, 1, 0, 0.1],
[0.1, 0, 1, 0.1],
[0, 0.1, 0.1, 1],
];
const result = this.optimize(hamiltonian);
console.log(`\nGround state energy: ${result.energy.toFixed(6)}`);
console.log('Optimal parameters:', result.parameters.map(p => p.toFixed(4)));
}
}
// Usage
const vqe = new VQE(2);
vqe.demonstrateVQE();QAOA (Quantum Approximate Optimization Algorithm)
typescript
// Quantum Approximate Optimization Algorithm
class QAOA {
private numQubits: number;
constructor(numQubits: number) {
this.numQubits = numQubits;
}
// Max-Cut problem
maxCut(graph: number[][], depth: number): { cut: number; assignment: number[] } {
let parameters = Array(depth * 2).fill(0).map(() => Math.random() * Math.PI);
// Optimize parameters
for (let iter = 0; iter < 100; iter++) {
const { cut } = this.evaluate(parameters, graph);
// Update parameters (simplified)
parameters = parameters.map(p => p + (Math.random() - 0.5) * 0.1);
}
return this.evaluate(parameters, graph);
}
private evaluate(parameters: number[], graph: number[][]): { cut: number; assignment: number[] } {
// Generate bitstring assignment
const assignment = Array.from({ length: this.numQubits }, () =>
Math.random() > 0.5 ? 1 : 0
);
// Calculate cut value
let cut = 0;
for (let i = 0; i < graph.length; i++) {
for (let j = i + 1; j < graph[i].length; j++) {
if (graph[i][j] > 0 && assignment[i] !== assignment[j]) {
cut += graph[i][j];
}
}
}
return { cut, assignment };
}
demonstrateQAOA(): void {
console.log('=== Quantum Approximate Optimization Algorithm ===\n');
// Example graph
const graph = [
[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0],
];
const result = this.maxCut(graph, 2);
console.log('Graph adjacency matrix:');
console.table(graph);
console.log(`\nMax cut value: ${result.cut}`);
console.log('Node assignments:', result.assignment);
}
}Quantum Machine Learning Algorithms
Quantum Support Vector Machine
typescript
// Quantum SVM
class QuantumSVM {
private kernelMatrix: number[][] = [];
// Quantum kernel estimation
quantumKernel(x1: number[], x2: number[]): number {
// In real quantum computer, would use quantum circuits
// to compute inner product in high-dimensional space
// Classical simulation: RBF kernel
const gamma = 1.0;
const diff = x1.reduce((sum, val, i) => sum + (val - x2[i]) ** 2, 0);
return Math.exp(-gamma * diff);
}
train(trainingData: { input: number[]; label: number }[]): void {
console.log('Training quantum SVM...');
// Compute kernel matrix
this.kernelMatrix = trainingData.map((point1, i) =>
trainingData.map((point2, j) =>
point1.label * point2.label * this.quantumKernel(point1.input, point2.input)
)
);
console.log('Kernel matrix computed using quantum operations');
console.table(this.kernelMatrix.slice(0, 3).map(row => row.slice(0, 3)));
}
predict(input: number[]): number {
// Simplified prediction
// Real implementation would solve dual optimization problem
return 1;
}
demonstrateQSVM(): void {
console.log('=== Quantum Support Vector Machine ===\n');
const trainingData = [
{ input: [1, 2], label: 1 },
{ input: [2, 1], label: 1 },
{ input: [-1, -2], label: -1 },
{ input: [-2, -1], label: -1 },
];
this.train(trainingData);
const testInput = [1.5, 1.5];
const prediction = this.predict(testInput);
console.log(`\nPrediction for [${testInput.join(', ')}]: ${prediction}`);
}
}Quantum Phase Estimation
typescript
// Quantum Phase Estimation
class QuantumPhaseEstimation {
// Estimate eigenvalue of unitary operator
estimatePhase(unitary: number[][], eigenstate: number[], precision: number): {
phase: number;
eigenvalue: number;
} {
// QPE uses quantum Fourier transform to estimate phase
// Phase φ relates to eigenvalue λ by λ = e^(2πiφ)
// Classical simulation
let phase = 0;
let eigenvalue = 1;
// Simplified - would use QFT circuit
for (let i = 0; i < precision; i++) {
phase += Math.random() * Math.pow(2, -i);
}
eigenvalue = Math.exp(2 * Math.PI * 1j * phase);
return { phase, eigenvalue: Math.abs(eigenvalue) };
}
demonstrateQPE(): void {
console.log('=== Quantum Phase Estimation ===\n');
// Unitary operator (rotation gate)
const theta = Math.PI / 4;
const unitary = [
[Math.cos(theta), -Math.sin(theta)],
[Math.sin(theta), Math.cos(theta)],
];
const eigenstate = [1, 0]; // |0⟩ state
const result = this.estimatePhase(unitary, eigenstate, 8);
console.log('Estimated phase:', result.phase.toFixed(6));
console.log('Eigenvalue:', result.eigenvalue.toFixed(6));
console.log('\nQPE provides exponential precision improvement');
}
}Algorithm Comparison and Applications
typescript
interface QuantumAlgorithmApplication {
algorithm: string;
application: string;
status: string;
speedup: string;
}
const applications: QuantumAlgorithmApplication[] = [
{
algorithm: 'Shor's',
application: 'Integer factorization, breaking RSA',
status: 'Long-term',
speedup: 'Exponential',
},
{
algorithm: 'Grover's',
application: 'Unstructured search, optimization',
status: 'Near-term',
speedup: 'Quadratic',
},
{
algorithm: 'VQE',
application: 'Quantum chemistry, materials science',
status: 'Near-term',
speedup: 'Potential',
},
{
algorithm: 'QAOA',
application: 'Combinatorial optimization',
status: 'Near-term',
speedup: 'Potential',
},
{
algorithm: 'QSVM',
application: 'Machine learning, classification',
status: 'Research',
speedup: 'Potential',
},
{
algorithm: 'QPE',
application: 'Eigenvalue problems, phase estimation',
status: 'Near-term',
speedup: 'Exponential',
},
];
console.table(applications);Conclusion
Quantum algorithms represent a new paradigm in computation. From Shor's exponential speedup for factoring to Grover's quadratic improvement for search, these algorithms exploit quantum mechanical properties to solve problems faster than classical computers.
As quantum hardware continues to improve, we'll see more quantum algorithms transition from theoretical concepts to practical applications. Understanding these algorithms now prepares you for the quantum computing revolution.
Start experimenting with quantum simulators, learn quantum programming frameworks like Qiskit or Cirq, and explore how quantum algorithms can solve problems in your domain. The quantum future is arriving faster than you think!