Date of Award


Degree Type


Degree Name

Doctor of Philosophy (PhD)


Computer Science

First Advisor

Sabre Kais

Second Advisor

Mikhail J. Atallah

Committee Chair

Sabre Kais

Committee Co-Chair

Mikhail J. Atallah

Committee Member 1

David Gleich

Committee Member 2

Ahmed Sameh


Quantum computing is an emerging area between computer science and physics. Numerous problems in quantum computing involve quantum many-body interactions. This dissertation concerns the problem of simulating arbitrary quantum many-body interactions using realistic two-body interactions. To address this issue, a general class of techniques called perturbative reductions (or perturbative gadgets) is adopted from quantum complexity theory and in this dissertation these techniques are improved for experimental considerations. The idea of perturbative reduction is based on the mathematical machinery of perturbation theory in quantum physics. A central theme of this dissertation is then to analyze the combinatorial structure of the perturbation theory as it is used for perturbative reductions.