⚛️ quantum physics

Towards Tensor-Network SAT-Solvers for Quantum-Classical Workflows

This paper investigates tensor-network ground-state search as a classical surrogate for quantum-classical workflows in solving Max-3-SAT problems, finding that native higher-order representations outperform quadratised formulations and that simulated annealing generally surpasses density matrix renormalization group methods because the classical product-state optima of Boolean satisfiability problems negate the specific advantages of tensor networks.

Original authors: Benjamin Zec, Lukas Schmidbauer, Maja Franz, Wolfgang Mauerer

Published 2026-08-04

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Benjamin Zec, Lukas Schmidbauer, Maja Franz, Wolfgang Mauerer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, tangled knot of string. In the world of computing, this knot represents a difficult puzzle called an "optimization problem," where you want to find the absolute best arrangement of pieces to get the highest score. For decades, we've used super-fast classical computers to untangle these knots. But now, a new kind of machine called a "quantum computer" has entered the chat. These machines are incredibly powerful and work by playing by the strange rules of quantum physics, where things can be in many places at once.

However, quantum computers aren't magic wands that solve everything instantly. They are also fragile, expensive, and sometimes hard to control. This has led scientists to dream up "hybrid" systems: a team-up where a classical supercomputer and a quantum processor work side-by-side. But here's the tricky part: you can't just hand the quantum computer a task and hope for the best. Sometimes, the quantum machine might get stuck, or it might be too costly to use. So, the classical computer needs a "backup plan"—a smart way to guess the answer or check if the quantum machine is doing its job. This is where a clever mathematical trick called "tensor networks" comes in. Think of it as a super-efficient way for a classical computer to simulate what a quantum machine would do, without actually needing the quantum machine. The big question is: does this backup plan actually work better than just using the old, reliable methods we already have?

This paper dives into that exact question by testing a specific type of puzzle called "Max-3-SAT." Imagine you have a list of rules, like "If you wear a red hat, you can't wear blue shoes," and your goal is to find a combination of hats and shoes that breaks the fewest rules. The researchers wanted to see if using a tensor network method (specifically called DMRG) to solve these puzzles was a good idea for these hybrid systems, or if it was just a waste of time. They compared this fancy quantum-simulation method against two other things: a standard classical method called "Simulated Annealing" (which is like shaking a box of puzzle pieces until they settle into the right spot) and two different ways of translating the puzzle into a language the computer understands.

The researchers set up a race. They took the same puzzle and translated it into two different formats. The first format was a "native" version that kept the puzzle's natural, complex shape. The second format was a "simplified" version where they forced the puzzle into a simpler, two-piece-at-a-time structure by adding extra, fake pieces (called auxiliary variables) to make the math easier. They then ran both the fancy DMRG method and the standard Simulated Annealing method on these translated puzzles.

The results were surprising and quite clear. First, the "simplified" translation was actually a trap. By adding those extra fake pieces to make the puzzle look simpler, the quality of the answers dropped significantly. It was like trying to solve a maze by adding more walls; the path got messier, not easier. The native, complex version of the puzzle gave much better results.

Second, and perhaps more importantly, the fancy DMRG method didn't win the race. In fact, the standard Simulated Annealing method was consistently faster and often found better solutions. The researchers found that DMRG's special superpower—its ability to handle complex quantum entanglement—was useless here. Why? Because the best answers to these specific logic puzzles are actually simple, "classical" states. They don't need the complex quantum magic that DMRG is designed to simulate. It's like bringing a high-tech drone to deliver a letter across the street when a bicycle would get there faster and cheaper.

The paper suggests that for these types of logic puzzles, using a tensor network as a backup or a simulator isn't the best move. Instead, the "simplified" way of translating the problem (quadratisation) hurts performance, and the old-school Simulated Annealing method is often the champion. This tells us that if we want to build hybrid systems that mix classical and quantum computers, we can't just blindly swap in fancy simulators. We have to be very careful about how we translate the problems and which tools we pick for the job. The choice of how to write down the problem matters just as much as the tool used to solve it.

Technical Summary: Towards Tensor-Network SAT-Solvers for Quantum-Classical Workflows

Problem Statement
Integrated High-Performance Computing/Quantum Computing (HPC/QC) systems require more than simple dispatch mechanisms for quantum kernels; they necessitate classical surrogates for observability, fallback execution, and cost-aware decision-making. However, classical surrogates must navigate the inescapable exponential worst-case complexity of classical simulation. This work investigates the efficacy of tensor-network methods, specifically the Density Matrix Renormalization Group (DMRG), as a surrogate for solving Boolean satisfiability (SAT) problems within hybrid workflows. The study focuses on how problem encoding transformations—specifically the reduction of higher-order problems to quadratic forms—affect the performance of these classical surrogates compared to native representations and classical baselines like Simulated Annealing (SA).

Methodology
The authors implemented an end-to-end execution pipeline to benchmark DMRG against Simulated Annealing (SA) on Max-3-SAT instances. The experimental workflow involved:

Instance Generation: Uniform Max-3-SAT instances were generated with varying numbers of variables ( $n$ ) and clauses ( $m$ ).
Transformation Paths: Two distinct compilation paths were compared:
- Native Path: Max-3-SAT $\rightarrow$ Pseudo-Boolean Function (PUBO) $\rightarrow$ Higher-Order Ising Model $\rightarrow$ Matrix Product Operator (MPO).
- Quadratised Path: Max-3-SAT $\rightarrow$ PUBO $\rightarrow$ Quadratised to Quadratic Unconstrained Binary Optimization (QUBO) via Local Structure Reduction (LSR) $\rightarrow$ Quadratic Ising Model $\rightarrow$ MPO.
Optimization: Both paths were encoded as MPOs and optimized using a two-site DMRG algorithm. A vanilla DMRG setup was used with randomized hyperparameters (sweeps, truncation error, bond dimension) across 100 independent trials per instance.
Baseline: SA was employed as a classical performance baseline with stochastic cooling schedules.
Metrics: Performance was evaluated based on runtime and deviation from the exact ground state (GS) energy, derived from the PUBO energy landscape.

Key Contributions and Findings

Impact of Quadratisation: The study demonstrates that quadratisation is not a neutral transformation step. Converting native higher-order PUBO formulations to QUBO via auxiliary variables and pairwise couplings substantially degrades solution quality. In the QUBO (quadratic) regime, both DMRG and SA exhibited monotonically increasing deviations from the ground state as problem size grew, with deviations exceeding 10–15% for larger instances.
Superiority of Native Encoding: In contrast, the native higher-order Ising (PUBO) representation maintained near-zero deviation across the entire tested range for both solvers. This suggests that the overhead introduced by auxiliary variables in the quadratisation process negatively impacts the efficiency of tensor-network contraction and variational sweeping.
Solver Performance: Simulated Annealing consistently matched or outperformed DMRG across all tested instances and encodings. DMRG's runtime scaled with the number of variables in both encodings, often exceeding SA's runtime significantly.
Nature of the Solution Space: The authors attribute DMRG's lack of advantage to the nature of SAT-derived problems. Since the optimal solutions for Boolean satisfiability are classical product states (unentangled), DMRG's primary strength—efficiently representing many-body entanglement at bounded bond dimensions—does not materialize in this context.

Significance and Claims
The paper posits that surrogate selection in HPC/QC runtimes must be "encoding- and instance-aware." The findings challenge the assumption that tensor-network methods are universally superior classical surrogates for quantum optimization tasks. Instead, the authors argue that:

Compiler and Runtime Design: Representation choices (e.g., native vs. quadratised) dominate solver behavior and must be treated as first-class decisions in compiler design.
Role of Surrogates: DMRG should be regarded not as a universal solver but as a bounded classical surrogate. Its value in integrated systems lies in providing observability and reproducible references for debugging quantum subroutines—tasks impossible with pure quantum approaches, especially under NISQ imperfections—rather than in outperforming classical heuristics for specific problem classes like SAT.
Decision Framework: The empirical data provided serves as a baseline for developing cost-aware offloading policies, helping systems decide when to replace quantum tasks with classical surrogates based on the specific encoding and instance characteristics.

Technical Summary: Towards Tensor-Network SAT-Solvers for Quantum-Classical Workflows

More like this