Kordonowy, S. (CS) – The Role of Circuits in Near-Term Quantum Computation

As quantum computing transitions from theory to practice, understanding which algorithms suit near-term devices becomes critical. Current quantum computers are severely constrained by limited qubit counts, short coherence times, and high error rates that quickly degrade computation into noise. This thesis addresses two interconnected questions: what non-trivial computational tasks can near-term devices execute and how should algorithms be implemented to exploit available hardware? We examine circuit design as the bridge between these concerns, analyzing how gate choices determine algorithmic efficiency and computational hardness. By deriving explicit circuit constructions, we obtain tangible cost estimates for practical quantum computation, enabling precise comparisons to classical approaches and identification of break-even points in system size and error rates. Understanding these trade-offs is essential for near-term quantum computing, where experiments are expensive and error-prone.

We apply these ideas to three domains:
1. Streaming: we provide circuit implementations for the Boolean Hidden Matching problem, a combinatorial problem which exhibits exponential space separation compared to classical algorithms. We give explicit resource estimates and experimentally validate on Quantinuum’s trapped-ion hardware. We demonstrate that quantum advantage persists even when accounting for error correction overhead.

2. Variational eigensolving: We examine how gate set choices influence trainability of variational quantum eigensolvers and provide Lie algebraic decompositions for differing gate sets. These decompositions are in turn used as a warm-starting heuristic to overcome barren plateaus, a common problem in quantum machine learning tasks, and improve convergence. We apply this technique to three combinatorial problems with primary focus on portfolio optimization.

3. Cryptography: We develop a digital signature scheme based on circuit learning hardness and classical shadows. Error detection plays a direct role in the circuits considered, with a focus on practical implementation for near-term devices.

These case studies demonstrate how careful circuit design can either mitigate near-term
constraints or expose where error correction becomes necessary to achieve quantum
advantage.

Event Host: Steven Kordonowy, Ph.D. Candidate, Computer Science 

Advisor: Alexandra Kolla 

Zoom: https://ucsc.zoom.us/j/9524731001?pwd=MzdrNmhidVBsTXNFbktBcjEvNmZIQT09&omn=96338496668 

Passcode: J29XGi