Matthew Gibson-Lopez

Quantum computing promises computational speedups, but understanding when and why quantum algorithms outperform classical ones requires building the right intuition. Last semester, we explored Deutsch's algorithm—a simple quantum algorithm that solves a particular function evaluation problem with just one query, whereas classical approaches require two. This talk begins by examining the natural generalization commonly taught in textbooks: the Deutsch-Jozsa algorithm, which extends the same quantum technique to functions on n-bit inputs. We'll then push further by relaxing the strict constant-versus-balanced restriction to see what happens when we estimate the majority class size through repeated quantum measurements. Surprisingly, this provides no advantage over classical random sampling—a result that helps clarify the boundaries of quantum speedup. However, this raises a compelling question: when does repeated quantum sampling help? We'll introduce amplitude estimation, a powerful generalization of Grover's algorithm that achieves a quadratic speedup for certain estimation problems, demonstrating where quantum coherence can reduce sampling variance in ways classical approaches cannot. Throughout, we'll maintain our discrete math perspective. No background in quantum mechanics assumed.

A lattice L is an additive discrete subgroup of ℝⁿ. A set of linearly independent vectors B = {b₁, ..., b_n} ⊆ ℝⁿ is called a basis of L if L = ℤb₁ + ⋯ + ℤb_n. When n ≥ 2, L has infinitely many possible bases. Bases consisting of relatively short and nearly orthogonal vectors are considered good bases, while others are regarded as bad bases. The lattice reduction theory studies how to obtain a good basis from a given one. In this talk, we will explore several lattice basis reduction methods and algorithms, along with their applications in cryptography and number theory.

Abstract to be announced.

Abstract to be announced.

Abstract to be announced.

Abstract to be announced.

Abstract to be announced.