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.
","abstract_html":"<p>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.</p>","abstract_has_math":false,"creators":["Cao, Yudong"],"institution":null,"degree_name":"Doctor of Philosophy (PhD)","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Sabre Kais","Mikhail J. Atallah","David Gleich","Ahmed Sameh"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-12-01T08:00:00Z","date_published":"2016-12-01T08:00:00Z","updated_at":"2026-07-24T03:54:09Z","subjects":["Pure sciences","Applied sciences","Cellular automata","Computational complexity","Many-body interactions","Perturbation theory","Quantum mechanics","Symmetric polynomials","Computer Sciences","Quantum Physics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://docs.lib.purdue.edu/open_access_dissertations/908","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Sabre Kais","Mikhail J. Atallah","David Gleich","Ahmed Sameh"]},{"key":"dc:creator","label":"Author","values":["Cao, Yudong"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Pure sciences","Applied sciences","Cellular automata","Computational complexity","Many-body interactions","Perturbation theory","Quantum mechanics","Symmetric polynomials","Computer Sciences","Quantum Physics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://docs.lib.purdue.edu/open_access_dissertations/908"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:title","label":"Title","values":["Combinatorial algorithms for perturbation theory and application on quantum computing"]}]}],"canonical_facts":{"dc:contributor":["Sabre Kais","Mikhail J. Atallah","David Gleich","Ahmed Sameh"],"dc:creator":["Cao, Yudong"],"dc:description.abstract":["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.
"],"dc:identifier":["https://docs.lib.purdue.edu/open_access_dissertations/908"],"dc:subject":["Pure sciences","Applied sciences","Cellular automata","Computational complexity","Many-body interactions","Perturbation theory","Quantum mechanics","Symmetric polynomials","Computer Sciences","Quantum Physics"],"dc:title":["Combinatorial algorithms for perturbation theory and application on quantum computing"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-24T03:54:09Z"}