## Multi-Panel Figure: Formulations of Combinatorial Optimization Problems ### Overview This image is a multi-panel figure illustrating three common combinatorial optimization problems—Max-SAT, Number partitioning, and Knapsack—each presented through three different formulation paradigms: Mathematical, Invertible logic, and Ising model. The figure is structured as a 3x3 grid, with problem types as columns and formulation types as rows. A legend for the invertible logic gates is provided at the bottom-center. ### Components/Axes The figure is divided into three main vertical panels, each dedicated to a problem, and three main horizontal panels, each dedicated to a formulation type. **Vertical Panels (Problem Types, from left to right):** 1. **Max-SAT** 2. **Number partitioning** 3. **Knapsack** **Horizontal Panels (Formulation Types, from top to bottom):** 1. **Mathematical formulation** 2. **Invertible logic formulation** 3. **Ising model formulation** **Legend (positioned below the "Invertible logic formulation" row, spanning Max-SAT and Number partitioning columns):** * **Red, D-shaped gate:** "Probabilistic OR" * **Orange, D-shaped gate with flat back:** "Probabilistic AND" * **Purple, D-shaped gate with curved back and internal arc:** "Probabilistic XOR" * **Light blue, rectangular block:** "Probabilistic n-bit Adder" **Ising Model Formulation Color Scale (vertical bar on the right of each heatmap):** * **Dark Blue:** +2 * **Light Blue:** +1 * **White/Light Grey:** +0 * **Light Red:** -1 * **Dark Red:** -2 A horizontal color bar below each heatmap also visually represents this gradient from red (-2) to blue (+2). ### Detailed Analysis #### Max-SAT Column **Mathematical formulation (Top-left panel):** * **Objective:** "maximize $\sum_{c=1}^{N_c} v_c$" * **Constraint/Definition:** "with $v_c = y_{c1} \lor y_{c2} \lor \dots \lor y_{cn}$" * **Variable domains:** "$v_c \in \{0,1\} \quad y_x \in \{0,1\}$" **Invertible logic formulation (Middle-left panel):** * **Inputs (from left to right, top to bottom):** $y_4$ (brown square), $y_3$ (magenta square), $y_2$ (light blue square), $y_1$ (green square). * **Circuit Description:** * Three "Probabilistic OR" gates (red, D-shaped) are present. * The top OR gate takes inputs $y_4$ and $y_3$, producing output $c_3$. * The middle OR gate takes inputs $y_2$ and $y_3$, producing output $c_2$. * The bottom OR gate takes inputs $y_1$ and $y_2$, producing output $c_1$. * Three "Probabilistic AND" gates (orange, D-shaped with flat back) are present. * The top AND gate takes inputs $c_3$ and $c_2$. * The middle AND gate takes inputs $c_2$ and $c_1$. * The outputs of these two AND gates feed into a final AND gate. * **Output:** The final output of the circuit is clamped to "1". * **Labels:** * "Clamp missing clauses to 1" (positioned above the top AND gate). * "Clamp all clauses to 1" (positioned below the final output "1"). **Ising model formulation (Bottom-left panel):** * **Visual Trend:** This is a heatmap (matrix) of approximately 15x15 elements. The diagonal elements are predominantly dark blue, indicating strong positive coupling (+2). Off-diagonal elements show a structured pattern of light blue (+1), white (0), and some light red (-1) and dark red (-2) squares. There are visible blocks of red and blue values, particularly in the upper-left and lower-right quadrants, and some scattered blue points. #### Number partitioning Column **Mathematical formulation (Top-center panel):** * **Objective:** "minimize $\left| \sum_{i=1}^{N} s_i n_i \right|$" * **Variable domain:** "with $s_i \in \{-1, +1\}$" **Invertible logic formulation (Middle-center panel):** * **Circuit Description:** * Two identical sub-circuits, each enclosed in a dashed box labeled "Sign choice". * The left "Sign choice" sub-circuit has inputs $n_1$ (grey circle) and $s_1$ (grey circle). It contains two "Probabilistic XOR" gates (purple) whose outputs feed into a "Probabilistic n-bit Adder" (light blue, 2-bit). * The right "Sign choice" sub-circuit has inputs $n_2$ (grey circle) and $s_2$ (grey circle). It also contains two "Probabilistic XOR" gates (purple) whose outputs feed into a "Probabilistic n-bit Adder" (light blue, 2-bit). * The outputs of both 2-bit adders feed into a larger "Probabilistic n-bit Adder" (light blue, 2-bit). This larger adder also has an input labeled "2's complement" on its top-left. * **Output:** The final output of the circuit is clamped to "0". * **Labels:** * "2's complement" (input to the final adder). * "Sign choice" (label for the dashed boxes around the XOR/adder sub-circuits). * "Clamp sum of sets to 0" (positioned below the final output "0"). **Ising model formulation (Bottom-center panel):** * **Visual Trend:** This is a heatmap (matrix) of approximately 15x15 elements. Similar to Max-SAT, the diagonal elements are predominantly dark blue (+2). The off-diagonal elements also show a structured pattern, with distinct blocks of light blue (+1) and light red (-1) values, particularly in the upper-left and lower-right, and some scattered blue points. The pattern appears more symmetric and block-like than Max-SAT. #### Knapsack Column **Mathematical formulation (Top-right panel):** * **Objective:** "maximize $\sum_{i=1}^{N} v_i x_i$" * **Constraint:** "subject to $\sum_{i=1}^{N} w_i x_i \le W$" * **Variable domains:** "with $v_i \ge 0 \quad w_i \ge 0 \quad x_i \in \{0,1\}$" **Invertible logic formulation (Middle-right panel):** * **Circuit Description:** * The circuit shows two parallel paths, likely representing two items. * **Top Path:** Inputs $V_1, W_1, X_1$. * A "Probabilistic AND" gate (orange) takes $V_1$ and $X_1$. * Another "Probabilistic AND" gate (orange) takes $W_1$ and $X_1$. * **Bottom Path:** Inputs $V_2, W_2, X_2$. * A "Probabilistic AND" gate (orange) takes $V_2$ and $X_2$. * Another "Probabilistic AND" gate (orange) takes $W_2$ and $X_2$. * The outputs of the $V_i X_i$ AND gates (from both paths) feed into a "Probabilistic n-bit Adder" (light blue, 2-bit) on the far left, labeled "MAX". * The outputs of the $W_i X_i$ AND gates (from both paths) feed into a "Probabilistic n-bit Adder" (light blue, 2-bit) on the right. This adder also receives an input "-W" (grey circle) and "2's complement". * The output of this right-side 2-bit adder feeds into a "Probabilistic n-bit Adder" (light blue, 3-bit) which also has an input "000" (three grey circles). * **Output:** The final output of the 3-bit adder is labeled "$\nabla$". * **Labels:** * "2's complement" (input to the right 2-bit adder). * "MAX" (label for the left 2-bit adder). * "Clamp sum of values to MAX" (positioned below the left 2-bit adder). * "Clamp sum of weights to <W" (positioned below the right 3-bit adder). **Ising model formulation (Bottom-right panel):** * **Visual Trend:** This is a heatmap (matrix) of approximately 15x15 elements. The diagonal elements are predominantly dark blue (+2). The off-diagonal elements show a more distributed and complex pattern compared to the other two problems. There are scattered light blue (+1), white (0), light red (-1), and dark red (-2) points across the matrix, without clear large blocks, suggesting a more intricate and less localized interaction structure. ### Key Observations * All three problems are presented with their standard mathematical formulations, followed by their representation using a common set of "Probabilistic" logic gates (OR, AND, XOR, n-bit Adder). * The "Invertible logic formulation" consistently uses "clamping" to enforce conditions or objectives (e.g., "Clamp all clauses to 1", "Clamp sum of sets to 0", "Clamp sum of values to MAX", "Clamp sum of weights to <W"). * "2's complement" is used in the invertible logic circuits for Number Partitioning and Knapsack, indicating operations involving signed numbers or subtractions. * The "Ising model formulation" for all problems shows a heatmap where diagonal elements consistently represent strong positive coupling (+2, dark blue). * The off-diagonal patterns in the Ising model heatmaps are distinct for each problem, visually representing the unique interaction structures: * Max-SAT: Structured blocks of red/blue, some scattering. * Number Partitioning: More symmetric and pronounced blocks of red/blue. * Knapsack: More scattered and complex distribution of red/blue points, suggesting a less localized interaction. ### Interpretation This figure effectively demonstrates the versatility of representing complex combinatorial optimization problems across different computational paradigms. 1. **Bridging Paradigms:** It shows how a problem, initially defined mathematically, can be translated into a physical implementation (invertible logic circuit) and then further mapped onto a statistical physics model (Ising model). This translation is crucial for leveraging different computational architectures, such as quantum computers or specialized annealing hardware, which often operate on principles related to reversible logic or Ising Hamiltonians. 2. **Invertible Logic for Energy Efficiency/Quantum Computing:** The use of "Probabilistic" invertible logic gates suggests an approach relevant to energy-efficient computing (where information loss is minimized) or quantum computing (where operations must be reversible). The "clamping" operations highlight how constraints and objective functions are integrated into these reversible circuits. 3. **Ising Model for Annealing:** The Ising model formulations provide a visual representation of the problem's energy landscape. The heatmaps depict the coupling matrix (J matrix) of the Ising Hamiltonian, where colors indicate the strength and sign of interactions between variables. * The strong positive diagonal elements (+2) typically represent self-energy terms or local fields that favor a particular state. * The off-diagonal elements represent interactions between variables. The distinct patterns for each problem (structured blocks for Max-SAT and Number Partitioning vs. scattered for Knapsack) reveal the underlying complexity and connectivity of the problem's variables. A more scattered pattern, like in Knapsack, implies a denser or more irregular interaction graph, potentially making the problem harder to solve for certain annealing algorithms. In essence, the figure illustrates the journey of a problem from abstract mathematical definition to concrete physical implementation and a statistical physics model, providing insights into how these problems can be tackled using advanced computational techniques.