## Problem Formulations: Max-SAT, Number Partitioning, and Knapsack ### Overview The image presents three different problem formulations: Max-SAT, Number Partitioning, and Knapsack. Each problem is described using a mathematical formulation, an invertible logic formulation, and an Ising model formulation. The image provides equations, logic diagrams, and heatmaps to represent each problem. ### Components/Axes **General Layout:** The image is divided into three vertical sections, one for each problem: Max-SAT (left), Number Partitioning (center), and Knapsack (right). Each section is further divided into three horizontal sections: Mathematical formulation (top), Invertible logic formulation (middle), and Ising model formulation (bottom). **Max-SAT (Left Section):** * **Mathematical formulation:** * Objective: maximize ∑(from c=1 to Nc) vc * Constraint: vc = yc1 ∨ yc2 ∨ ... ∨ ycn * Domain: vc ∈ {0, 1}, yx ∈ {0, 1} * **Invertible logic formulation:** * Logic gates: Probabilistic OR (red), Probabilistic AND (orange) * Inputs: y1 (green), y2 (cyan), y3 (magenta), y4 (brown) * Outputs: c1, c2, c3, and a final AND gate outputting 1. * Text: "Clamp missing 1 clauses to 1", "Clamp all clauses to 1" * **Ising model formulation:** * Heatmap: A square matrix with values ranging from -2 (red) to +2 (blue). * Colorbar: Ranges from -2 (red) to +2 (blue), with intermediate values of -1, 0, and +1. **Number Partitioning (Center Section):** * **Mathematical formulation:** * Objective: minimize |∑(from i=1 to N) sini| * Constraint: si ∈ {-1, +1} * **Invertible logic formulation:** * Components: 2-bit adders (light blue), Probabilistic XOR (purple) * Inputs: n1, s1, n2, s2 * Text: "2's complement", "Sign choice", "Clamp sum of sets to 0" * **Ising model formulation:** * Heatmap: A square matrix with values ranging from -2 (red) to +2 (blue). * Colorbar: Ranges from -2 (red) to +2 (blue), with intermediate values of -1, 0, and +1. **Knapsack (Right Section):** * **Mathematical formulation:** * Objective: maximize ∑(from i=1 to N) vixi * Constraint: ∑(from i=1 to N) wixi ≤ W * Domain: vi ≥ 0, wi ≥ 0, xi ∈ {0, 1} * **Invertible logic formulation:** * Components: 2-bit adders (light blue), Probabilistic AND (orange) * Inputs: v1, w1, x1, v2, w2, x2 * Text: "2's complement", "Clamp sum of values to MAX", "Clamp sum of weights to <W", "-W", "MAX" * **Ising model formulation:** * Heatmap: A square matrix with values ranging from -2 (red) to +2 (blue). * Colorbar: Ranges from -2 (red) to +2 (blue), with intermediate values of -1, 0, and +1. **Legend (Bottom):** Located at the bottom center of the image. * Probabilistic OR: Red gate symbol * Probabilistic AND: Orange gate symbol * Probabilistic XOR: Purple gate symbol * Probabilistic n-bit Adder: Light blue rectangle symbol ### Detailed Analysis or ### Content Details **Max-SAT:** * **Mathematical Formulation:** The goal is to maximize the sum of variables `vc`, where each `vc` is the logical OR of variables `yc1` through `ycn`. Both `vc` and `yx` are binary variables (0 or 1). * **Invertible Logic Formulation:** The logic circuit takes four inputs (y1 to y4) and uses OR gates to compute intermediate values (c1 to c3). These intermediate values are then combined using an AND gate to produce a final output. The circuit includes clamps to ensure certain conditions are met. * **Ising Model Formulation:** The heatmap shows a pattern, with a strong diagonal and off-diagonal elements. The diagonal elements are mostly positive (blue), while the off-diagonal elements show a mix of positive and negative (red) correlations. **Number Partitioning:** * **Mathematical Formulation:** The goal is to minimize the absolute value of the sum of variables `sini`, where each `si` can be either -1 or +1. * **Invertible Logic Formulation:** The logic circuit uses XOR gates and 2-bit adders to perform the partitioning. The circuit includes a sign choice component and clamps the sum of sets to 0. * **Ising Model Formulation:** The heatmap shows a strong diagonal pattern, with mostly positive (blue) correlations along the diagonal. There are also some off-diagonal correlations. **Knapsack:** * **Mathematical Formulation:** The goal is to maximize the sum of `vixi`, subject to the constraint that the sum of `wixi` is less than or equal to `W`. The variables `vi` and `wi` are non-negative, and `xi` is a binary variable (0 or 1). * **Invertible Logic Formulation:** The logic circuit uses AND gates and adders to perform the knapsack optimization. The circuit includes components for clamping the sum of values to MAX and the sum of weights to less than W. * **Ising Model Formulation:** The heatmap shows a diagonal pattern, with mostly positive (blue) correlations along the diagonal. There are also some off-diagonal correlations. ### Key Observations * Each problem is represented in three different ways: mathematically, logically, and using an Ising model. * The Ising model formulations result in heatmaps that show correlation patterns between variables. * The logic circuits use probabilistic gates to implement the problem constraints. ### Interpretation The image demonstrates how three different optimization problems (Max-SAT, Number Partitioning, and Knapsack) can be formulated using mathematical equations, logic circuits, and Ising models. The Ising model formulations allow these problems to be mapped onto physical systems that can potentially solve them efficiently. The heatmaps provide a visual representation of the correlations between variables in the Ising model. The logic circuits show how the problem constraints can be implemented using probabilistic gates.

## 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.

\n ## Diagram: Combinatorial Optimization Problems and Ising Model Formulation ### Overview The image presents a comparative analysis of three combinatorial optimization problems – Max-SAT, Number Partitioning, and Knapsack – illustrating their mathematical formulations, invertible logic implementations, and corresponding Ising model formulations visualized as heatmaps. The diagram is structured into three columns, each dedicated to one problem, with two rows: the top row showing the mathematical and logical representation, and the bottom row displaying the Ising model formulation as a heatmap. ### Components/Axes Each column (problem) is divided into two sections: * **Mathematical Formulation:** Contains equations defining the optimization problem. * **Invertible Logic:** Shows a circuit diagram representing the problem's logic. * **Ising Model Formulation:** Displays a heatmap representing the Ising model, with a color scale ranging from -2 to +2. The x-axis represents the spin configuration, and the y-axis is not explicitly labeled but appears to represent the energy level or state of the system. The three problems are: 1. **Max-SAT:** Maximizes the number of satisfied clauses. 2. **Number Partitioning:** Minimizes the difference between the sums of two subsets. 3. **Knapsack:** Maximizes the value of items selected within a weight constraint. ### Detailed Analysis or Content Details **1. Max-SAT (Left Column)** * **Mathematical Formulation:** * `maximize Σvc` where `c` ranges from 1 to `Nc` * `vc = yc1 ∨ yc2 ∨ ... ∨ ycn` * `vc ∈ {0,1}` and `yc ∈ {0,1}` * **Invertible Logic:** A circuit with inputs `y1`, `y2`, `y3`, `y4` and clauses `c1`, `c2`, `c3`. The circuit includes OR gates and a final output of 1. Text states "Clamp missing 1 clauses to 1" and "Clamp all clauses to 1". * **Ising Model Formulation:** The heatmap shows a pattern of red and blue squares. The color intensity varies, with some squares approaching +2 (red) and others -2 (blue). There's a clear diagonal pattern. **2. Number Partitioning (Middle Column)** * **Mathematical Formulation:** * `minimize Σ si*ni` where `i` ranges from 1 to `N` * `si ∈ {-1, +1}` * **Invertible Logic:** Includes 2-bit sign choice blocks, 2's complement operations, and a MAX function. Text states "Clamp sum of sets to 0" and "Clamp sum of values to MAX". * **Ising Model Formulation:** The heatmap shows a more dispersed pattern than Max-SAT, with a mix of red and blue squares. The diagonal pattern is less pronounced. **3. Knapsack (Right Column)** * **Mathematical Formulation:** * `maximize Σ vi*xi` where `i` ranges from 1 to `N` * `subject to Σ wi*xi ≤ W` where `i` ranges from 1 to `N` * `vi > 0`, `wi > 0`, `xi ∈ {0,1}` * **Invertible Logic:** Includes 2-bit adders, 3-5 bit adders, 2's complement operations, and a MAX function. Text states "Clamp sum of weights to <W". * **Ising Model Formulation:** The heatmap shows a complex pattern with a mix of red and blue squares. The diagonal pattern is visible but less distinct than in Max-SAT. **Color Scale (Common to all Ising Model Formulations):** * -2 (Dark Blue) * -1 (Blue) * 0 (White) * +1 (Red) * +2 (Dark Red) ### Key Observations * Each problem has a distinct Ising model representation, suggesting that the energy landscape differs for each optimization task. * The Max-SAT Ising model exhibits the most pronounced diagonal pattern, potentially indicating a simpler energy landscape. * The Number Partitioning and Knapsack Ising models show more complex and dispersed patterns, suggesting more challenging optimization landscapes. * The mathematical formulations clearly define the objective function and constraints for each problem. * The invertible logic diagrams provide a hardware-oriented view of the problems. ### Interpretation The diagram demonstrates a powerful connection between combinatorial optimization problems, their logical implementations, and their representation as Ising models. The Ising model formulation allows these problems to be tackled using techniques from statistical physics, such as simulated annealing or quantum annealing. The differences in the Ising model heatmaps suggest that the computational complexity of each problem varies. Max-SAT, with its clear diagonal pattern, might be easier to solve than Number Partitioning or Knapsack, which have more complex energy landscapes. The use of invertible logic highlights the potential for building specialized hardware to solve these problems efficiently. The diagram suggests that the Ising model provides a unifying framework for understanding and solving a wide range of combinatorial optimization challenges. The clamping operations in the invertible logic diagrams suggest a method for handling constraints within the Ising model framework. The diagram is a conceptual illustration, and does not provide specific numerical data for the Ising model parameters or performance metrics.

## [Technical Diagram]: Comparative Optimization Problem Formulations (Max-SAT, Number Partitioning, Knapsack) ### Overview The image is a **comparative technical diagram** illustrating three classic optimization problems—**Max-SAT**, **Number Partitioning**, and **Knapsack**—across three formulation layers: *Mathematical*, *Invertible Logic*, and *Ising Model*. Each problem is presented in a vertical column, with horizontal rows for each formulation type. A legend defines logic gate symbols used in the Invertible Logic layer. ### Components/Axes - **Columns (Problems):** - Left: *Max-SAT* (maximizing clause satisfaction). - Middle: *Number Partitioning* (minimizing partition imbalance). - Right: *Knapsack* (maximizing value under weight constraints). - **Rows (Formulations):** - **Top:** *Mathematical Formulation* (formulas, variable definitions). - **Middle:** *Invertible Logic Formulation* (logic gates, clamping operations). - **Bottom:** *Ising Model Formulation* (heatmaps with color bars). - **Legend (Bottom Middle):** - Red: *Probabilistic OR* - Orange: *Probabilistic AND* - Purple: *Probabilistic XOR* - Blue: *Probabilistic n-bit Adder* - **Color Bars (Bottom Row):** Each heatmap has a vertical color bar (blue → red) labeled with values `-2, -1, 0, +1, +2` (indicating Ising model spin interactions/energy terms). ### Detailed Analysis #### 1. Mathematical Formulation (Top Row) - **Max-SAT (Left):** - Objective: Maximize \( \sum_{c=1}^{N_c} v_c \), where \( v_c = y_{c1} \lor y_{c2} \lor \dots \lor y_{cn} \) (logical OR of binary variables \( y_x \in \{0,1\} \)). - Variables: \( v_c \in \{0,1\} \), \( y_x \in \{0,1\} \). - **Number Partitioning (Middle):** - Objective: Minimize \( \sum_{i=1}^{N} |s_i n_i| \), where \( s_i \in \{-1, +1\} \) (signs for partitioning). - **Knapsack (Right):** - Objective: Maximize \( \sum_{i=1}^{N} v_i x_i \), subject to \( \sum_{i=1}^{N} w_i x_i \leq W \) (weight constraint). - Variables: \( v_i \geq 0 \), \( w_i \geq 0 \), \( x_i \in \{0,1\} \) (binary selection). #### 2. Invertible Logic Formulation (Middle Row) - **Max-SAT (Left):** - Logic Gates: *Probabilistic OR* (red) for clause satisfaction, *Probabilistic AND* (orange) for combining clauses. - Clamping: “Clamp missing clauses to 1” (top), “Clamp all clauses to 1” (bottom). - Flow: Inputs \( y_{c1}, y_{c2}, y_{c3} \) → OR gates → AND gate → clamping. - **Number Partitioning (Middle):** - Logic Gates: *Probabilistic XOR* (purple) for sign handling, *Probabilistic n-bit Adder* (blue) for summing. - Clamping: “2’s complement” (top), “Clamp sum of sets to 0” (bottom). - Flow: Signs \( s_1, s_2 \) and numbers \( n_1, n_2 \) → XOR → Adder → clamping. - **Knapsack (Right):** - Logic Gates: *Probabilistic XOR* (purple) for value/weight handling, *Probabilistic n-bit Adders* (blue) for summing values/weights. - Clamping: “2’s complement” (top), “Clamp sum of values to MAX” (left), “Clamp sum of weights to <W” (bottom). - Flow: Values \( v_i \), weights \( w_i \), and selections \( x_i \) → XOR → Adders → clamping. #### 3. Ising Model Formulation (Bottom Row, Heatmaps) Each heatmap (Max-SAT, Number Partitioning, Knapsack) uses a color scale from **blue (-2)** to **red (+2)**, representing Ising model spin interactions or energy terms. - **Max-SAT Heatmap (Left):** Diagonal/off-diagonal elements with red (positive) and blue (negative) squares (clause-variable interactions). - **Number Partitioning Heatmap (Middle):** Symmetric diagonal pattern (balanced partitioning interactions). - **Knapsack Heatmap (Right):** Diagonal structure (value-weight tradeoff interactions). ### Key Observations - **Formulation Consistency:** Each problem is mapped across mathematical, logic, and Ising layers, showing cross-paradigm representation. - **Logic Gate Usage:** Probabilistic gates (OR, AND, XOR, Adder) model constraints/objectives, with clamping enforcing feasibility. - **Ising Model Patterns:** Heatmaps show distinct diagonal structures (e.g., Max-SAT: clause-variable; Number Partitioning: sign-number balance; Knapsack: value-weight tradeoffs). - **Color Coding:** Legend colors (red=OR, orange=AND, purple=XOR, blue=Adder) are consistent across the Invertible Logic row. ### Interpretation This diagram demonstrates how three classic optimization problems can be reformulated across **mathematical**, **logic-based**, and **Ising model** frameworks: - The *mathematical layer* defines the problem’s objective/constraints. - The *logic layer* uses probabilistic gates to encode logical/arithmetic operations (e.g., clause satisfaction, partition signs, knapsack selection) with clamping for feasibility. - The *Ising layer* visualizes the problem’s energy landscape (via heatmaps) to show interaction strengths (e.g., Max-SAT’s clause-variable interactions, Knapsack’s value-weight tradeoffs). This multi-formulation approach highlights the versatility of optimization problems and their representation in different computational paradigms (e.g., quantum-inspired Ising models, probabilistic logic gates), aiding in solver development and problem structure analysis. (Note: All text is in English; no non-English text is present.)

## Heatmap Diagram: Optimization Problem Visualizations ### Overview The image presents three distinct optimization problem visualizations (Max-SAT, Number Partitioning, Knapsack) with corresponding mathematical formulations, logic diagrams, and heatmaps. Each section includes probabilistic logic gates, constraint diagrams, and 2D heatmaps with color-coded values. ### Components/Axes #### Mathematical Formulations 1. **Max-SAT** - **Objective**: Maximize ∑ₐ=1^N v_c with v_c = y_c1 ∨ y_c2 ∨ ... ∨ y_cn - **Variables**: v_c ∈ {0,1}, y_x ∈ {0,1} - **Logic Diagram**: Probabilistic OR gates with clamps (missing clauses set to 1). 2. **Number Partitioning** - **Objective**: Minimize |∑ᵢ=1^N s_i n_i| with s_i ∈ {-1, +1} - **Components**: 2-bit adders, sign choice modules, and clamping to 0. 3. **Knapsack** - **Objective**: Maximize ∑ᵢ=1^N v_i x_i subject to ∑ᵢ=1^N w_i x_i ≤ W - **Constraints**: v_i ≥ 0, w_i ≥ 0, x_i ∈ {0,1} - **Logic Diagram**: MAX gates, 2-bit adders, and weight clamping. #### Heatmap Details - **Axes**: - X-axis: Unlabeled (likely represents variable indices or clauses). - Y-axis: Unlabeled (likely represents variable indices or clauses). - **Color Scale**: - Red: -2 (low probability/value) - Blue: +2 (high probability/value) - White: 0 (neutral/undefined). - **Legend**: - Positioned at the bottom of the heatmaps. - Colors: - Red: Probabilistic OR/AND/XOR gates. - Blue: Probabilistic n-bit adder. ### Detailed Analysis #### Max-SAT Heatmap - **Trend**: Diagonal bands of red and blue squares suggest variable dependencies. - **Values**: - Top-left: Red (-2) dominates, indicating low clause satisfaction. - Bottom-right: Blue (+2) appears, suggesting high clause satisfaction. #### Number Partitioning Heatmap - **Trend**: Symmetric red-blue diagonal pattern implies balanced partitioning. - **Values**: - Center: White (0) indicates neutral sums. - Edges: Red (-2) and blue (+2) show extreme imbalances. #### Knapsack Heatmap - **Trend**: Diagonal red-blue gradient reflects trade-offs between value and weight. - **Values**: - Top-right: Blue (+2) indicates high-value, low-weight solutions. - Bottom-left: Red (-2) shows low-value, high-weight solutions. ### Key Observations 1. **Diagonal Patterns**: All heatmaps exhibit diagonal trends, suggesting variable interactions (e.g., clauses, weights, sums). 2. **Clamping Effects**: Logic diagrams show clamps forcing values to 0/1 or MAX, aligning with heatmap extremes. 3. **Color Consistency**: Red (-2) and blue (+2) consistently represent minima/maxima across all heatmaps. ### Interpretation - **Max-SAT**: The heatmap visualizes clause satisfaction probabilities, with red/blue diagonals indicating variable interactions. Clamping ensures all clauses are satisfied (set to 1). - **Number Partitioning**: The symmetric heatmap reflects the challenge of balancing subsets, with clamping to 0 enforcing equality. - **Knapsack**: The gradient highlights the trade-off between maximizing value and minimizing weight, with clamping ensuring constraints are met. - **Uncertainty**: Axis labels are unlabeled, making precise variable indexing ambiguous. The heatmaps lack explicit numerical annotations, relying on color scales for interpretation. ## Conclusion The image demonstrates how probabilistic logic and constraint diagrams map to optimization problems, with heatmaps providing intuitive visualizations of solution distributions. The diagonal patterns and clamping mechanisms are critical for understanding variable dependencies and constraint satisfaction.