Quantum Computing & Algorithms
Twelve mathematically rigorous native algorithm units covering exact circuits, reversible oracles, phase kickback, quantum Fourier transform, phase estimation, Shor, Grover, Hamiltonian simulation, variational methods, QAOA, amplitude estimation and BQP complexity. Equations, worked calculations, verified circuit figures and embedded instructor lectures are placed within QuantumSpark lessons rather than replacing the lesson with outbound links.
Published syllabus
Course Units
Circuit model and universal gates
The circuit model represents a computation as an ordered sequence of unitary gates followed by measurements. Single-qubit gates combined with an entangling two-qubit gate form universal sets under suitable approximation. Exact gate matrices depend on basis and global phase convention, and an apparently simple unitary may require a large decomposition on restricted hardware connectivity. Circuit depth, two-qubit gate count and fault-tolerant T count are distinct costs.
Reversible computation and oracles
Classical Boolean logic often discards information, but embedding an oracle inside a quantum circuit requires a reversible map. The common bit oracle transforms |x,y> to |x,y⊕f(x)> and preserves orthogonality because it is a permutation of computational basis states. The function value can be transferred into phase by initializing the target in |->. Oracle queries are powerful abstractions but can hide substantial physical synthesis cost.
Phase kickback and interference
Phase kickback is a controlled-operation phenomenon: when the target is an eigenstate of a unitary U, controlled-U writes the corresponding eigenphase into a relative phase on the control qubit. The global phase of the target becomes observable as a relative phase of the entangled control-path alternatives. This mechanism underlies many black-box algorithms and phase estimation; eigenvalue conventions must be tracked carefully.
Quantum Fourier transform
The quantum Fourier transform maps computational basis vectors to discrete complex plane waves, using phases determined by modular arithmetic. Its efficient circuit factors into Hadamards and controlled rotations followed by a bit-order reversal. The QFT does not magically reveal all Fourier coefficients in a single measurement; it enables interference patterns that expose selected periodic or phase information when combined with a suitable promise problem.
Phase estimation
Phase estimation uses controlled powers U^{2^j} acting on an eigenstate to encode an eigenphase in a control register. An inverse QFT produces an estimate of the phase to finite binary precision. Precision costs controlled evolution time and coherent resources; 'more bits' is not free. When the input is not one eigenstate, the outcome distribution samples the spectral weights of the superposition.
Shor factoring
Shor's factoring algorithm reduces integer factorization to order finding for modular exponentiation. The quantum part estimates the periodicity of a function x↦a^x mod N; continued fractions recover a candidate order from a sufficiently precise phase estimate. The classical part checks gcd values and success conditions. Real resource estimates are dominated by fault-tolerant arithmetic, error correction, and logical qubit requirements, not just the high-level QFT circuit.
Grover search
Grover's search operates in the two-dimensional space spanned by marked and unmarked uniform superpositions. Alternating an oracle phase flip with reflection about the initial state rotates the amplitude vector toward marked solutions. The query complexity scales as the square root of search-space size divided by the number of marked states, subject to oracle assumptions. Too many iterations can overshoot the optimal success probability.
Hamiltonian simulation
Quantum Hamiltonian simulation aims to implement e^{-iHt} to controlled operator error. Product formulas exploit decomposition H=ΣH_j, while qubitization and block encoding produce alternative precision scaling under strong access models. Noncommuting terms lead to Trotter errors governed by nested commutators. A quantum simulation claim should specify normalization, time, error measure and how the Hamiltonian terms are accessed.
Variational quantum eigensolver
The variational quantum eigensolver minimizes the energy expectation of a parameterized state prepared by a quantum circuit. The variational principle bounds the energy from below by the true ground energy only when the target Hermitian Hamiltonian and trial-state assumptions are satisfied. The optimizer is classical, but gradient estimation and noisy expectation values can dominate total cost. Ansatz expressivity does not guarantee efficient trainability.
QAOA and hybrid optimization
QAOA alternates exponentials of a cost Hamiltonian and mixer for p layers. Its measured distribution yields candidate bit strings whose quality depends on parameters and problem structure. The cost Hamiltonian encodes a discrete objective, but constraints, penalties and normalization change the physical landscape. Approximation ratio, solution probability, shot cost, parameter-transfer performance and hardware runtime are distinct metrics.
Amplitude estimation and sampling
Amplitude estimation aims to infer a small success probability more efficiently than direct independent Bernoulli sampling when coherent amplitude-amplification access is available. Canonical methods use phase estimation; iterative variants avoid deep QFT circuits but still require structured coherent oracle calls. Claims about quadratic speedup should compare like-for-like accuracy, confidence and cost of state preparation.
Complexity, verification, and benchmarking
Complexity theory separates classes of computational tasks by resources and error conditions. BQP covers bounded-error uniform quantum polynomial-time computation; it is not the class of every optimization problem a QPU can sample. Complexity claims use formal reduction assumptions, and hardware benchmarks should measure total wall-clock resources, fidelity and reproducibility. A quantum circuit's depth alone cannot certify computational advantage.