Algorithms - Quantum Computing

Introduction

Classical Computing and Physics

• Computing is deeply tied to physical laws.

• The computational stack:
1. Algorithms (Java, Python, etc.)
2. Virtual Machines/Interpreters
3. Processors (CPUs, microprocessors)
4. Digital Circuits (logic gates, flip-flops)
5. Analog Circuits (transistors, resistors)
6. Charge Manipulation (high & low voltages)

• Fundamental takeaway: Computing must be realized by physical devices.

Classical vs. Quantum Physics

• Classical physics (Newton, Maxwell):
• Governs macroscopic objects.
• Includes Newton’s Laws, Maxwell’s Equations, and electrodynamics.

• Quantum physics (Planck, Einstein, Bohr, Rutherford):
• Governs microscopic particles.
• Concepts such as quantization, wave-particle duality, and uncertainty.

Key Principles of Quantum Mechanics

• Certain properties (like energy levels in atoms) exist in discrete values rather than continuous ones.

• Example: Hydrogen atom has electrons that can occupy only specific orbits.

• A quantum system can exist in multiple states at the same time.

• Example: Double-slit experiment (single photon interferes with itself).

• Measurement destroys superposition.

• When observed, a quantum system collapses into a definite state.

• Example: Schrödinger’s Cat (simultaneously alive and dead until observed).

• It is impossible to simultaneously measure both position and momentum with perfect accuracy.

• Example: Stern-Gerlach experiment (measurement along one axis affects certainty of another).

• Two or more particles can become entangled, meaning their states are correlated instantaneously, regardless of distance.

Quantum Computing: The Big Idea

• Classical vs. Quantum Algorithms:
• Classical algorithms use bits (0 or 1).
• Quantum algorithms use qubits, which can exist in superpositions of 0 and 1.

• Quantum Parallelism:
• Computation occurs on all possible states simultaneously.
• Challenge: Measurement collapses this superposition to only one result.

• Solving Problems Using Quantum Mechanics
• The trick is to design quantum algorithms where correct answers have high probabilities.
• Repeating quantum computations can increase the chances of getting the right answer.

Conclusion

• Quantum mechanics introduces new principles that allow for a different kind of computing.

• The next step is understanding how these principles translate into quantum algorithms.

Qubits and Quantum Computing

1. What is a Qubit?

• A qubit is the fundamental unit of information in quantum computing.

• Analogous to a classical bit (0 or 1), but in the quantum world, it represents a quantum state.

• Examples of how classical bits are physically represented:
• Voltage levels in a circuit: 0 → Low voltage, 1 → High voltage.
• Optical computing: 0 → Absence of light, 1 → Presence of light.
• Magnetization direction of iron cores.

2. Quantum Representation of Qubits

• In quantum computing, qubits are realized through quantum states, such as:
• Electron spin up (0) or spin down (1).
• Photon polarization in different directions.

• The state of a quantum system is represented mathematically as a ket vector:
∣0⟩,∣1⟩| 0 \rangle, | 1 \rangle

• These states exist in a special mathematical space called Hilbert space.

3. Superposition of Qubits

• Unlike classical bits, a qubit can exist in both states (0 and 1) simultaneously.

• This is represented as: where α and β are complex numbers called amplitudes.
∣ψ⟩=α∣0⟩+β∣1⟩| \psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle

• Example: This means the qubit has a 50% probability of being 0 and 50% probability of being 1.
∣ψ⟩=12∣0⟩+12∣1⟩| \psi \rangle = \frac{1}{\sqrt{2}} | 0 \rangle + \frac{1}{\sqrt{2}} | 1 \rangle

• When a measurement is performed, the qubit collapses to either 0 or 1.

• The probability of measuring 0 is |α|², and the probability of measuring 1 is |β|².

• A valid qubit must satisfy:
∣α∣2+∣β∣2=1| \alpha |^2 + | \beta |^2 = 1

• Example:
∣ψ⟩=32∣0⟩−i2∣1⟩| \psi \rangle = \frac{\sqrt{3}}{2} | 0 \rangle - \frac{i}{2} | 1 \rangle
• Probability of 0:
(32)2=34\left(\frac{\sqrt{3}}{2}\right)^2 = \frac{3}{4}
• Probability of 1:
(12)2=14\left(\frac{1}{2}\right)^2 = \frac{1}{4}

4. Quantum Operators and Unitary Matrices

• Quantum operations transform qubits from one state to another.

• These transformations are represented by unitary matrices.

• A unitary matrix (U) satisfies: where is the conjugate transpose of U, and I is the identity matrix.
U†U=IU^\dagger U = I
U†U^\dagger

• This is called the Hadamard matrix, which creates superpositions.

• If U is a quantum operator and ψ is a qubit state:
U∣ψ⟩=∣ψ′⟩U | \psi \rangle = | \psi' \rangle

• Example: Applying the Hadamard matrix to |0⟩: This puts the qubit in equal superposition.
H∣0⟩=12(∣0⟩+∣1⟩)H | 0 \rangle = \frac{1}{\sqrt{2}} ( | 0 \rangle + | 1 \rangle )

5. Summary and Next Steps

• Qubits are quantum representations of bits that can be in superposition.

• Measurement collapses a qubit to a definite state based on probability amplitudes.

• Quantum operations (unitary transformations) manipulate qubits.

• Next topic: Quantum Gates (Hadamard, Pauli, and more) and Multi-Qubit Systems.