Entanglement Complexity in Many-body Systems from Positivity Scaling Laws

This paper introduces a framework based on $p$-particle positivity conditions from reduced density matrix theory to establish a general complexity bound proving that if a quantum system is solvable with level-$p$ positivity independent of size, its entanglement complexity scales polynomially, thereby providing a rigorous method to certify the computational tractability of many-body simulations.

The Gist

Imagine you are trying to solve a massive, incredibly complex jigsaw puzzle. In the world of quantum physics, this puzzle represents a "many-body system"—a group of particles (like electrons) that are all interacting with each other at the same time. The more particles you add, the harder the puzzle becomes. In fact, for many systems, the difficulty grows so fast that even the world's most powerful supercomputers can't solve them. This difficulty is called computational complexity.

For a long time, scientists have used a rule called the "Area Law" to guess how hard a puzzle is. Think of the Area Law like checking the size of the puzzle's border. If the difficulty of solving the puzzle only depends on the size of the border (the surface area) rather than the total number of pieces inside (the volume), then the puzzle is "easy" enough for computers to solve efficiently. If the difficulty depends on the total volume, it's usually too hard.

However, the authors of this paper, Anna O. Schouten and David A. Mazziotti, say there is a better, more direct way to measure this difficulty. They introduce a new tool based on "positivity scaling laws."

The New Tool: The "Positivity Ladder"

Instead of looking at the puzzle's border, the authors look at the puzzle through a series of magnifying glasses, which they call $p$-positivity conditions.

• The Concept: Imagine you are checking if a group of friends (particles) is behaving "properly" according to the rules of physics.
  • Level 1 ($p=1$): You check if individual friends are behaving well.
  • Level 2 ($p=2$): You check if pairs of friends are behaving well together.
  • Level 3 ($p=3$): You check if groups of three friends are behaving well together.
  • And so on, up to level $p$.

These checks are called positivity conditions. They ensure that the mathematical description of the system (the Reduced Density Matrix, or RDM) makes physical sense.

The Big Discovery: The "Fixed Level" Rule

The paper proves a very important theorem about these levels:

If you can solve the entire quantum puzzle by only looking at groups of size $p$ (and this number $p$ doesn't need to grow as the system gets bigger), then the puzzle is "easy" (solvable in polynomial time).

Here is the analogy:
Imagine you are trying to predict the traffic flow in a giant city.

• The Hard Way: You try to track every single car's interaction with every other car in the city. As the city grows, this becomes impossible.
• The Authors' Way: They ask, "Do we only need to look at how cars interact in groups of 2 to understand the whole traffic jam?"
  • If the answer is yes (you only need to look at pairs, $p=2$, no matter how big the city gets), then the traffic pattern is simple and predictable. The "entanglement complexity" (how tangled the relationships are) is low.
  • If the answer is no (you need to look at groups of 10, or 100, or eventually the whole city), then the traffic is chaotic and incredibly hard to simulate.

The Proof in Action: The Extended Hubbard Model

To prove their idea, the authors tested it on a famous quantum puzzle called the Extended Hubbard Model. This model simulates electrons hopping around on a grid, repelling each other.

1. The Easy Case (No Hopping): When the electrons cannot move (they are stuck in place), the authors found that they only needed to check pairs of electrons ($p=2$) to get the exact answer. Even though the system was huge, the "complexity" stayed low. The computer solved it perfectly using a method called Semidefinite Programming (a type of advanced math optimization).
2. The Harder Case (With Hopping): When the electrons are allowed to move, the interactions get messier. The authors found that checking just pairs wasn't enough; they had to check slightly larger groups (partial 3-particle groups) to get a good answer. The "complexity" increased, but it was still manageable in certain regions.

Why This Matters

The paper doesn't just say "this is a new math trick." It establishes a strict link between structure and difficulty:

• Structure: If a quantum system's rules can be described by checking small groups of particles (a fixed $p$), the system is "simple" in terms of entanglement.
• Difficulty: If the system is "simple" in structure, it can be solved by computers efficiently (in polynomial time).
• The Limit: If the system is so complex that you need to check groups that grow as big as the system itself (like checking the whole city at once), then the system is exponentially hard to solve.

Summary

Think of the authors as providing a new complexity meter. Instead of guessing if a quantum system is hard to solve based on its size, you can now check: "What is the smallest group size ($p$) I need to understand to solve this?"

• If $p$ stays small and fixed, the system is solvable and efficient.
• If $p$ has to grow with the system, the system is complex and likely unsolvable for large sizes.

This gives scientists a rigorous way to know exactly when their computer simulations will work and when they will hit a wall, specifically for systems involving electrons and materials.

Technical Summary

1. Problem Statement

The paper addresses the challenge of quantifying entanglement complexity in quantum many-body systems and determining the computational tractability of simulating them.

• Limitations of Area Laws: While "area laws" (where entanglement entropy scales with surface area rather than volume) are widely used to characterize entanglement and suggest polynomial solvability (e.g., via Matrix Product States in DMRG), they do not provide a direct, rigorous measure of computational complexity or a specific framework for certifying when Reduced Density Matrix (RDM) methods will succeed.
• The Gap: There is a need for a framework that directly links the structural constraints of RDMs to the computational cost of solving the many-body problem, specifically determining the minimum level of correlation required to solve a system efficiently.

2. Methodology

The authors introduce a framework based on $p$-positivity conditions derived from RDM theory.

• $p$-Positivity Hierarchy:

  • For an $N$-particle system, the Reduced Density Matrix (RDM) must satisfy $N$-representability conditions to correspond to a valid physical state.
  • The authors utilize a hierarchy of constraints known as $p$-positivity conditions. These require that all metric matrices associated with the $p$-body RDM (and lower orders) are positive semidefinite.
  • Mathematically, for a set of polynomials $\hat{C}_i$ of order $p$ in fermionic creation/annihilation operators, the condition is:
    $$\text{Tr}(\hat{C}_i \hat{C}_i^\dagger \, ^p\text{D}) \geq 0$$
  • This can be enforced on lower-order RDMs (e.g., the 2-RDM) via contraction or by generating convex combinations of constraints, known as $(q, p)$-positivity conditions.

• Variational 2-RDM (V2RDM) Theory:

  • The energy of the system is minimized as a functional of the 2-RDM subject to these positivity constraints.
  • The problem is formulated as a Semidefinite Program (SDP), which can be solved efficiently.

• Duality and Hamiltonian Structure:

  • The paper establishes a duality: If a system is solvable at level $p$, the Hamiltonian (shifted by the energy, $\hat{H}-E$) can be expressed as a convex combination of positive semidefinite $p$-particle operators.
  • This structure is analogous to the Sum-of-Squares (SOS) framework in polynomial optimization (Lasserre's hierarchy).

3. Key Contributions

A. Theoretical Theorem: Complexity Bound

The authors prove a fundamental theorem connecting solvability to entanglement complexity:

Theorem: If a quantum system is solvable at a fixed level of $p$-positivity conditions that is independent of the system size ($N$), then:

1. The solution complexity is polynomial in $N$ (specifically $O(p)$).
2. The entanglement complexity is bounded by $O(p)$.

• Implication: If a fixed $p$ suffices to represent the Hamiltonian regardless of system size, the system's correlations are limited to $p$ particles (or $p$ holes). Consequently, the problem can be solved exactly or with high precision using polynomial-time SDP algorithms.

B. Lemma on Polynomial Solvability

The paper proves that any problem expressible exactly at a fixed level of $p$-positivity can be solved in polynomial time because it reduces to a Semidefinite Program, which is known to be solvable in polynomial time.

C. Extension to Phase Transitions

The framework provides a mechanism to detect changes in complexity. If the required level of $p$-positivity increases with system size (e.g., near critical points), the problem transitions from polynomial to exponential complexity, indicating a violation of area laws and high entanglement.

4. Results: The Extended Hubbard Model

The authors validate their theory using the Extended Hubbard Model:
$$\hat{H} = -t \sum \hat{a}^\dagger \hat{a} + U \sum n_{i\uparrow}n_{i\downarrow} + V \sum n_i n_j$$

• Case 1: $t = 0$ (No Hopping)

  • The Hamiltonian is diagonal and consists purely of two-body interactions.
  • Result: The system is exactly solvable at the level of 2-positivity (independent of system size).
  • The V2RDM method with 2-positivity constraints reproduces the exact ground-state energy, including the phase transition between Charge-Density Wave (CDW) and Spin-Density Wave (SDW) states.
  • Conclusion: Entanglement complexity is $O(2)$, confirming the theorem.

• Case 2: $t > 0$ (With Hopping)

  • The system exhibits continuous phase transitions.
  • Result: 2-positivity alone is insufficient for exact solutions. However, adding partial 3-positivity (specifically the $T_2$ condition, involving 3-body RDMs) significantly improves accuracy.
  • Error Analysis:
    • In the region $U/V > 2$, the error is relatively constant but non-zero, suggesting the complexity order exceeds 2 and partial 3-positivity.
    • In the region $U/V < 2$, the error drops sharply as $U/V$ decreases, indicating the system's complexity reduces toward the level of partial 3-positivity.
  • Conclusion: The framework successfully identifies regions where the complexity is low enough to be captured by finite $p$ levels, even if not exactly solvable at $p=2$.

5. Significance and Impact

• New Metric for Complexity: The paper establishes positivity scaling laws as a rigorous alternative to area laws for characterizing entanglement complexity. It shifts the focus from entropy scaling to the structural constraints required to represent the Hamiltonian.
• Certification of Efficiency: It provides a theoretical "certificate" for when RDM-based methods (like V2RDM, one-electron RDM, and bootstrapping approaches) can efficiently simulate correlated quantum matter. If a system is solvable at fixed $p$, it is computationally tractable.
• Bridge Between Optimization and Physics: By linking $N$-representability to Semidefinite Programming and the Sum-of-Squares hierarchy, the work bridges quantum many-body physics with convex optimization theory.
• Practical Application: The results suggest that even for complex systems (like amorphous polymers or exciton condensates mentioned in the references), a finite level of $p$-positivity may yield high-accuracy solutions, guiding the development of efficient simulation algorithms for materials science and quantum chemistry.

In summary, Schouten and Mazziotti demonstrate that the computational cost of simulating a quantum system is directly determined by the minimum order of positivity ($p$) required to represent its Hamiltonian, offering a powerful tool for predicting and certifying the efficiency of many-body simulations.