Physics & Astronomy ETDs
Publication Date
Summer 7-28-2026
Abstract
This dissertation studies problems at the interplay of classical and quantum computation in the settings of optimization, complexity, and sampling. In most chapters, we start from a classical combinatorial or algorithmic notion and develop its quantum counterpart or apply it to solve a quantum problem. We do this either by introducing a new model, proving a new hardness result, designing a new algorithm or proving that a known algorithm is efficient. The contributions of this dissertation split along two broad directions. The first concerns the optimization and complexity of ground state energy problems for physically motivated quantum Hamiltonians, most of which arise as natural quantum extensions of classical combinatorial problems. We introduce quantum generalizations of Vertex Cover, characterize their computational hardness, and obtain a deterministic linear time approximation algorithm by adapting the classical local ratio method to the quantum setting for the first time. We then define a fermionic version of the Independent Set problem and prove a computational hardness result about the problem. A small modification of the same proof resolves an open conjecture about a natural problem in topological data analysis, namely the hardness of detecting topological holes in graph structured data. Next, we consider the Quantum Max-Cut problem and design a family of convex relaxations adapted to its natural symmetry. We prove results about exactness of these relaxations on several new families of graphs for Quantum Max-Cut that include well known condensed matter spin models. The second direction develops sampling based methods for extracting information about quantum systems. We propose a Bayesian framework for measurements on a quantum device that incorporates the physical constraints relating expectation values of different observables, and demonstrate numerically that it gives substantially tighter uncertainty bars than standard estimators. We also prove that a widely used operator-loop Quantum Monte Carlo algorithm, a workhorse classical algorithm for quantum simulation that has enjoyed decades of empirical success, runs in provably polynomial time on the full class of stoquastic XY Hamiltonians with arbitrary longitudinal and stoquastic transverse fields, providing the first such guarantee in the transverse field regime.
Degree Name
Physics
Level of Degree
Doctoral
Department Name
Physics & Astronomy
First Committee Member (Chair)
Milad Marvian
Second Committee Member
Ojas Parekh
Third Committee Member
Tameem Albash
Fourth Committee Member
Akimasa Miyake
Language
English
Keywords
Hamiltonian Complexity, Approximation algorithms, Markov chains
Document Type
Dissertation
Recommended Citation
Rayudu, Sankara Sai Chaithanya. "Classical to Quantum: Optimization and Sampling." (2026). https://digitalrepository.unm.edu/phyc_etds/375