Discrete Mathematics and Combinatorics Commons^™

32 - Nested Two Level Decomposition For Quantum Computing, Andrew Maciejunes, John Stenger, Dan Gunlycke, Nikos Chrisochoides

Undergraduate Research Symposium

Abstract—We present a two-level decomposition strategy for solving the Vehicle Routing Problem (VRP) using the Quantum Approximate Optimization Algorithm (QAOA). A Problem-Level Decomposition (PLD) partitions a 9-node (72-qubit) VRP into smaller Traveling Salesman Problem (TSP) instances. Each TSP is then further simplified via Circuit-Level Decomposition (CLD), enabling execution on near-term quantum devices. Our approach achieves up to 90% reductions in circuit depth and qubit count. These results demonstrate the feasibility of solving VRPs previously too complex for quantum simulators and provide early evidence of potential quantum utility.

Robust Spacecraft Autonomy For Deep Space Exploration In Special Euclidean Group Se(3), Matthew Wittal

Doctoral Dissertations and Master's Theses

Over the past half-century, humanity has gained extensive experience conducting manned spaceflight near Earth. Arguably, "near Earth" could even include the Moon — the most distant destination humans have reached. However, "near" in this work primarily refers low Earth orbit (LEO). One could argue that we have not truly left Earth since the Apollo, as spacecraft in some LEOs remain subject to atmospheric drag thus emphasizing their continued connection to Earth's immediate environment. Reflecting on this, it becomes clear that humanity has largely remained bound to Earth’s immediate vicinity since the Apollo missions reached the Moon. However, that is set …

Coloring Trivalent Graphs: A Defect Tft Approach, Amit Kumar

LSU Doctoral Dissertations

We show that the combinatorial matter of graph coloring is, in fact, quantum in the sense of satisfying the sum over all the possible intermediate state properties of a path integral. In our case, the topological field theory (TFT) with defects gives meaning to it. This TFT has the property that when evaluated on a planar trivalent graph, it provides the number of Tait-Coloring of it. Defects can be considered as a generalization of groups. With the Klein-four group as a 1-defect condition, we reinterpret graph coloring as sections of a certain bundle, distinguishing a coloring (global-sections) from a coloring …

Reducing Food Scarcity: The Benefits Of Urban Farming, S.A. Claudell, Emilio Mejia

Journal of Nonprofit Innovation

Urban farming can enhance the lives of communities and help reduce food scarcity. This paper presents a conceptual prototype of an efficient urban farming community that can be scaled for a single apartment building or an entire community across all global geoeconomics regions, including densely populated cities and rural, developing towns and communities. When deployed in coordination with smart crop choices, local farm support, and efficient transportation then the result isn’t just sustainability, but also increasing fresh produce accessibility, optimizing nutritional value, eliminating the use of ‘forever chemicals’, reducing transportation costs, and fostering global environmental benefits.

Imagine Doris, who is …

Strong Homotopy Lie Algebras And Hypergraphs, Samuel J. Bevins, Marco Aldi

UROP Posters

We study hypergraphs by attaching a nilpotent strong homotopy Lie algebra. We especially focus on hypergraph theoretic information that is encoded in the cohomology of the resulting strong homotopy Lie algebra.

Target Control Of Networked Systems, Isaac S. Klickstein

Mechanical Engineering ETDs

The control of complex networks is an emerging field yet it has already garnered interest from across the scientific disciplines, from robotics to sociology. It has quickly been noticed that many of the classical techniques from controls engineering, while applicable, are not as illuminating as they were for single systems of relatively small dimension. Instead, properties borrowed from graph theory provide equivalent but more practical conditions to guarantee controllability, reachability, observability, and other typical properties of interest to the controls engineer when dealing with large networked systems. This manuscript covers three topics investigated in detail by the author: (i) the …

A High Quality, Eulerian 3d Fluid Solver In C++, Lejon Anthony Mcgowan

Computer Science and Software Engineering

Fluids are a part of everyday life, yet are one of the hardest elements to properly render in computer graphics. Water is the most obvious entity when thinking of what a fluid simulation can achieve (and it is indeed the focus of this project), but many other aspects of nature, like fog, clouds, and particle effects. Real-time graphics like video games employ many heuristics to approximate these effects, but large-scale renderers aim to simulate these effects as closely as possible.

In this project, I wish to achieve effects of the latter nature. Using the Eulerian technique of discrete grids, I …

A Generalized Polynomial Identity Arising From Quantum Mechanics, Shashikant B. Mulay, John J. Quinn, Mark A. Shattuck

Applications and Applied Mathematics: An International Journal (AAM)

We establish a general identity that expresses a Pfaffian of a certain matrix as a quotient of homogeneous polynomials. This identity arises in the study of weakly interacting many-body systems and its proof provides another way of realizing the equivalence of two proposed types of trial wave functions used to describe such systems. In the proof of our identity, we make use of only elementary linear algebra and combinatorics and thereby avoid use of more advanced conformal field theory in establishing the aforementioned equivalence.

Nullification Of Torus Knots And Links, Zachary S. Bettersworth

Masters Theses & Specialist Projects

Knot nullification is an unknotting operation performed on knots and links that can be used to model DNA recombination moves of circular DNA molecules in the laboratory. Thus nullification is a biologically relevant operation that should be studied.

Nullification moves can be naturally grouped into two classes: coherent nullification, which preserves the orientation of the knot, and incoherent nullification, which changes the orientation of the knot. We define the coherent (incoherent) nullification number of a knot or link as the minimal number of coherent (incoherent) nullification moves needed to unknot any knot or link. This thesis concentrates on the study …

A Potential Foundation For Emergent Space-Time, Kevin H. Knuth, Newshaw Bahreyni

Physics Faculty Scholarship

We present a novel derivation of both the Minkowski metric and Lorentz transformations from the consistent quantification of a causally ordered set of events with respect to an embedded observer. Unlike past derivations, which have relied on assumptions such as the existence of a 4-dimensional manifold, symmetries of space-time, or the constant speed of light, we demonstrate that these now familiar mathematics can be derived as the unique means to consistently quantify a network of events. This suggests that space-time need not be physical, but instead the mathematics of space and time emerges as the unique way in which an …

Physics: Rethinking The Foundations, Kevin H. Knuth

Physics Faculty Scholarship

Physics is traditionally conceived of as a set of laws that universally governs the behavior of physical systems. These laws, however they are decreed, are believed to govern the behavior of not only everything in the universe, but the form of the universe itself. However, this traditional concept of physics as a universal governance is at odds with our modern theories of quantum mechanics and relativity, which place the observer and information in a central role. In this talk, I aim to rethink the foundations and attempt to build physics from the bottom up based on a very simple foundational …

Information-Based Physics: An Intelligent Embedded Agent's Guide To The Universe, Kevin H. Knuth

Physics Faculty Scholarship

In this talk, I propose an approach to understanding the foundations of physics by considering the optimal inferences an intelligent agent can make about the universe in which he or she is embedded. Information acts to constrain an agent’s beliefs. However, at a fundamental level, any information is obtained from interactions where something influences something else. Given this, the laws of physics must be constrained by both the nature of such influences and the rules by which we can make inferences based on information about these influences. I will review the recent progress we have made in this direction. This …

The Quantum Dialectic, Logan Kelley

Pitzer Senior Theses

A philosophic account of quantum physics. The thesis is divided into two parts. Part I is dedicated to laying the groundwork of quantum physics, and explaining some of the primary difficulties. Subjects of interest will include the principle of locality, the quantum uncertainty principle, and Einstein's criterion for reality. Quantum dilemmas discussed include the double-slit experiment, observations of spin and polarization, EPR, and Bell's theorem. The first part will argue that mathematical-physical descriptions of the world fall short of explaining the experimental observations of quantum phenomenon. The problem, as will be argued, is framework of the physical descriptive schema. Part …

Coalitions And Cliques In The School Choice Problem, Sinan Aksoy, Alexander Adam Azzam, Chaya Coppersmith, Julie Glass, Gizem Karaali, Xueying Zhao, Xinjing Zhu

Pomona Faculty Publications and Research

The school choice mechanism design problem focuses on assignment mechanisms matching students to public schools in a given school district. The well-known Gale Shapley Student Optimal Stable Matching Mechanism (SOSM) is the most efficient stable mechanism proposed so far as a solution to this problem. However its inefficiency is well-documented, and recently the Efficiency Adjusted Deferred Acceptance Mechanism (EADAM) was proposed as a remedy for this weakness. In this note we describe two related adjustments to SOSM with the intention to address the same inefficiency issue. In one we create possibly artificial coalitions among students where some students modify their …

Nonlinear Dynamics In Combinatorial Games: Renormalizing Chomp, Eric J. Friedman, Adam S. Landsberg

WM Keck Science Faculty Papers

We develop a new approach to combinatorial games that reveals connections between such games and some of the central ideas of nonlinear dynamics: scaling behaviors, complex dynamics and chaos, universality, and aggregation processes. We take as our model system the combinatorial game Chomp, which is one of the simplest in a class of "unsolved" combinatorial games that includes Chess, Checkers, and Go. We discover that the game possesses an underlying geometric structure that "grows" (reminiscent of crystal growth), and show how this growth can be analyzed using a renormalization procedure adapted from physics. In effect, this methodology allows one to …