Graph Theoretic Algorithms Adaptable to Quantum Computing
dc.contributor.author | Srivastava, Siddhartha | |
dc.date.accessioned | 2021-06-08T23:17:38Z | |
dc.date.available | 2021-06-08T23:17:38Z | |
dc.date.issued | 2021 | |
dc.identifier.uri | https://hdl.handle.net/2027.42/168116 | |
dc.description.abstract | Computational methods are rapidly emerging as an essential tool for understanding and solving complex engineering problems, which complement the traditional tools of experimentation and theory. When considered in a discrete computational setting, many engineering problems can be reduced to a graph coloring problem. Examples range from systems design, airline scheduling, image segmentation to pattern recognition, where energy cost functions with discrete variables are extremized. However, using discrete variables over continuous variables introduces some complications when defining differential quantities, such as gradients and Hessians involved in scientific computations within solid and fluid mechanics. Consequently, graph techniques are under-utilized in this important domain. However, we have recently witnessed great developments in quantum computing where physical devices can solve discrete optimization problems faster than most well-known classical algorithms. This warrants further investigation into the re-formulation of scientific computation problems into graph-theoretic problems, thus enabling rapid engineering simulations in a soon-to-be quantum computing world. The computational techniques developed in this thesis allow the representation of surface scalars, such as perimeter and area, using discrete variables in a graph. Results from integral geometry, specifically Cauchy-Crofton relations, are used to estimate these scalars via submodular functions. With this framework, several quantities important to engineering applications can be represented in graph-based algorithms. These include the surface energy of cracks for fracture prediction, grain boundary energy to model microstructure evolution, and surface area estimates (of grains and fibers) for generating conformal meshes. Combinatorial optimization problems for these applications are presented first. The last two chapters describe two new graph coloring algorithms implemented on a physical quantum computing device: the D-wave quantum annealer. The first algorithm describes a functional minimization approach to solve differential equations. The second algorithm describes a realization of the Boltzmann machine learning algorithm on a quantum annealer. The latter allows generative and discriminative learning of data, which has vast applications in many fields. Theoretical aspects and the implementation of these problems are outlined with a focus on engineering applications. | |
dc.language.iso | en_US | |
dc.subject | Quantum Annealing | |
dc.subject | Computational Solid Mechanics | |
dc.subject | Numerical Method for Differential Equations | |
dc.subject | Polycrystalline Materials | |
dc.subject | Boltzmann Machines | |
dc.subject | Fracture Mechanics | |
dc.title | Graph Theoretic Algorithms Adaptable to Quantum Computing | |
dc.type | Thesis | |
dc.description.thesisdegreename | PhD | en_US |
dc.description.thesisdegreediscipline | Aerospace Engineering | |
dc.description.thesisdegreegrantor | University of Michigan, Horace H. Rackham School of Graduate Studies | |
dc.contributor.committeemember | Sundararaghavan, Veera | |
dc.contributor.committeemember | Veerapaneni, Shravan Kumar | |
dc.contributor.committeemember | Gorodetsky, Alex Arkady | |
dc.contributor.committeemember | Inman, Daniel J | |
dc.contributor.committeemember | Waas, Anthony | |
dc.subject.hlbsecondlevel | Aerospace Engineering | |
dc.subject.hlbtoplevel | Engineering | |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/168116/1/sidsriva_1.pdf | |
dc.identifier.doi | https://dx.doi.org/10.7302/1543 | |
dc.identifier.orcid | 0000-0002-4684-4423 | |
dc.identifier.name-orcid | Srivastava, Siddhartha; 0000-0002-4684-4423 | en_US |
dc.working.doi | 10.7302/1543 | en |
dc.owningcollname | Dissertations and Theses (Ph.D. and Master's) |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.