⚛️ quantum physics

Progress in the study of the (non)existence of genuinely unextendible product bases

By leveraging graph theory and forbidden induced subgraph characterizations, the authors prove that genuinely unextendible product bases of size thirteen in three-qutrit systems do not exist, while also providing partial characterizations for larger bases and systems with ququart subsystems.

Original authors: Maciej Demianowicz

Published 2026-02-16

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Maciej Demianowicz

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 build a perfect puzzle using special 3D blocks. These blocks have a very strange rule: they must fit together in a specific way, but there must be no empty space left over that can be filled by any other block of the same type.

In the world of quantum physics, these blocks are called Product States (simple, non-mixed quantum states). A collection of them that fills a space but leaves no room for another simple block is called an Unextendible Product Basis (UPB).

But here is the twist: The scientists in this paper were looking for a "Super UPB." They wanted a set of blocks that is so perfectly arranged that even if you tried to combine two blocks from different sides of the room (a "biproduct" move), you still couldn't fit anything new in. They call this a Genuinely Unextendible Product Basis (GUPB).

The Big Question

The researchers asked: "Does the smallest possible version of this 'Super Puzzle' actually exist?"

Specifically, they were looking at a system with three parts (like three dice), where each part can show three different faces (a "qutrit"). Mathematical rules suggested that if such a puzzle exists, it must be made of exactly 13 blocks.

The Detective Work: Graph Theory as a Map

Instead of trying to build the puzzle with actual quantum blocks (which is incredibly hard), the author, Maciej Demianowicz, decided to map the puzzle onto a graph (a network of dots and lines).

The Dots: Represent the 13 blocks.
The Lines: Connect blocks that are "orthogonal" (meaning they are perfectly perpendicular to each other, like the x, y, and z axes).

The problem became: "Can we draw a map with 13 dots where every dot is connected to exactly 4 others, such that we can assign a 3D vector to every dot without breaking the rules?"

The "Forbidden Subgraph" Strategy

Imagine you are a city planner trying to build a new neighborhood. You have a list of 10,786 possible blueprints for the layout of the streets. Checking every single one would take forever.

Instead, the author used a clever trick called "Forbidden Induced Subgraph Characterization."

Think of it like this:

"If a house blueprint contains a broken window (a specific small pattern of lines), then the entire house is unsafe and must be demolished. We don't need to check the rest of the house; the broken window kills the deal."

The author identified a small list of "broken windows" (tiny, specific graph patterns like a House, a Kite, or a Diamond shape). He proved that if any of these tiny shapes appear inside a larger blueprint, that blueprint is impossible to build in 3D space.

The Results: A House of Cards Collapses

Using this "broken window" filter, the author swept through the 10,786 possible blueprints:

The Filter: He removed thousands of blueprints instantly because they contained one of the forbidden shapes.
The Survivors: Only two blueprints survived the filter. They looked "clean" and didn't have the forbidden broken windows.
The Final Check: The author then tried to actually build the 3D vectors for these two survivors.
- Survivor #1 (Disconnected): It required using the exact same block twice in a way that broke the rules of the puzzle.
- Survivor #2 (Connected): It also required repeating blocks in a way that made the puzzle "collapse" (the vectors didn't span the full space needed).

The Conclusion

The 13-block "Super Puzzle" does not exist.

It's like looking for a specific type of snowflake that is supposed to be the smallest possible one. You find a few candidates, but when you look closely, you realize they are either melting or just regular snowflakes. The specific "perfect" one you were hunting for simply cannot be made.

Why Does This Matter?

This might sound like a niche math problem, but it's actually about the fundamental limits of the universe.

Entanglement: These puzzles are related to "entanglement," the spooky connection between particles.
No-Go Theorems: Proving that something doesn't exist is just as important as proving it does. It tells us that nature has strict boundaries. We can't just make any kind of quantum state we want; there are "forbidden zones" in the landscape of quantum mechanics.

In short: The author used a "banned shapes" list to filter out millions of impossible quantum puzzles, proving that the smallest, most perfect version of this specific quantum puzzle is a myth. It doesn't exist.

1. Problem Statement

The paper addresses the open problem of the existence of Genuinely Unextendible Product Bases (GUPBs).

Definition: A GUPB is a set of mutually orthogonal product vectors in a multipartite Hilbert space that cannot be extended by any product vector, even when considering bipartitions of the system (i.e., no biproduct vector is orthogonal to the entire set).
Significance: If a GUPB exists, its orthogonal complement is a Genuinely Entangled Subspace (GES), containing only genuinely multipartite entangled (GME) states. This is a stronger condition than standard Unextendible Product Bases (UPBs), which only guarantee entanglement with respect to the full multipartite split.
The Specific Challenge: While bounds on the size of GUPBs have been established, their actual existence in simple systems remains unknown. The paper focuses on the smallest theoretically possible candidate: a GUPB in a three-qutrit system ( $N=3$ parties, local dimension $d=3$ ) with the minimal cardinality of 13.

2. Methodology

The author employs a rigorous graph-theoretic approach, leveraging the connection between UPBs and Orthogonality Graphs (OGs).

Graph Representation:
- A set of product vectors corresponds to a set of Local Orthogonality Graphs (LOGs), $G_i$ , one for each subsystem.
- For a minimal GUPB of size $k=13$ in a three-qutrit system, the LOGs must be 4-regular graphs with 13 vertices (derived from the lower bound formula $G \geq \frac{Nd^{N-1}-1}{N-1}$ ).
- The union of these LOGs must form a complete graph $K_{13}$ .
Constraints:
1. Faithful Orthogonal Representation (FOR): The LOGs must admit a faithful orthogonal representation in dimension $d=3$ (vectors assigned to vertices are orthogonal iff vertices are connected).
2. Spanning (Saturation) Property (Fact 1): For any subsystem, any subset of $k - d^{N-1} + 1 = 5$ local vectors must span the full 3-dimensional Hilbert space. This implies that no 5 vectors in the representation can be linearly dependent (specifically, they cannot span a subspace of dimension $<3$ ).
Core Technique: Forbidden Induced Subgraph Characterization:
- Instead of brute-forcing all 10,786 non-isomorphic 4-regular graphs on 13 vertices, the author identifies a small set of "obstruction graphs" (small subgraphs) that cannot admit a FOR(3).
- Observation 1: If a graph $H$ is an induced subgraph of a graph $G$ , and $H$ has no FOR(3), then $G$ also has no FOR(3).
- The author constructs an obstruction set $\mathcal{O}_3 = \{C_4, H_5, K_5, A_6\}$ (4-clique, House graph, Kite graph, A-graph) and proves via Lemma 2 that none of these admit a FOR(3).
- By systematically checking which of the 10,786 candidate graphs contain these forbidden subgraphs, the search space is drastically pruned.

3. Key Contributions and Results

A. Classification and Pruning of Candidate Graphs

The study analyzed all 10,786 non-isomorphic 4-regular graphs with 13 vertices, dividing them into:

Disconnected Graphs (8 candidates):
- Analyzed based on component sizes (e.g., 5+8, 6+7).
- Most were eliminated because their components (like $C_5$ or $D_{7,b}$ ) lacked a FOR(3).
- One candidate ( $D_6 + D_{7,a}$ ) admitted a FOR(3) but was discarded because the representation required repeated vectors, violating the Spanning Property (Fact 1).
Connected Graphs (10,778 candidates):
- Using the obstruction set $\mathcal{O}_3$ , the author eliminated 10,776 graphs.
- Only one connected graph, $M_{5057}$ , remained that admitted a FOR(3).

B. Analysis of the Final Candidate ( $M_{5057}$ )

The graph $M_{5057}$ was found to admit a FOR(3).
However, a detailed analysis of its structure (specifically Lemma 3) revealed that any FOR(3) for this graph necessarily contains repeated vectors (e.g., $|v_3\rangle = |v_4\rangle$ and $|v_9\rangle = |v_{10}\rangle = |v_{11}\rangle$ ).
Consequently, the span of the set $\{|v_3\rangle, |v_4\rangle, |v_9\rangle, |v_{10}\rangle, |v_{11}\rangle\}$ is only 2-dimensional.
This violates Fact 1 (the requirement that any 5 local vectors must span the full 3D space).

C. Main Conclusion

Theorem: There does not exist a three-qutrit GUPB with a cardinality of 13.
This resolves the existence question for the smallest theoretically possible GUPB.

D. Extensions to Larger Systems

The paper also provides preliminary results for larger systems:

14-vertex 4-regular graphs (Three-qutrit, size 14): Identified a larger obstruction set including an 11-vertex graph ( $\hat{N}_{11}$ ). Several candidates were eliminated, but the status of the remaining graphs remains undecided.
Ququart systems ( $d=4$ ): Analyzed minimal GUPBs for three-ququart systems (size 24). The author identified new forbidden subgraphs (e.g., Envelope graphs, Balloon graphs) and showed that even if a FOR(4) exists, the spanning conditions often fail due to the structure of complete multipartite graphs.

4. Significance

Resolution of an Open Problem: The paper definitively proves the non-existence of the minimal GUPB in the simplest non-trivial setting (three qutrits). This narrows the search space for GUPBs significantly.
Methodological Advancement: The introduction of forbidden induced subgraph characterization to the study of UPBs/GUPBs provides a powerful, efficient tool for pruning the search space of high-dimensional combinatorial objects. It moves beyond brute-force optimization to structural graph theory.
Implications for Quantum Information:
- Since minimal GUPBs do not exist in this setting, constructing GESs via minimal UPBs in three-qutrit systems is impossible.
- The results suggest that GUPBs, if they exist, must be significantly larger or exist in higher-dimensional systems, implying that the "gap" between bipartite unextendibility and genuine multipartite unextendibility is harder to bridge than previously hoped.
- The work highlights the deep interplay between graph theory (regularity, girth, subgraphs) and quantum entanglement properties (spanning, orthogonality).

5. Limitations and Future Work

Computational Complexity: While effective for small systems ( $N=3, d=3$ ), the method becomes computationally intractable as the number of vertices and local dimensions increase (e.g., the number of graphs grows exponentially).
Undecided Cases: The existence of GUPBs with size $>13$ in three-qutrit systems, or in systems with $d \geq 4$ , remains an open problem. The paper provides partial characterizations but no definitive "non-existence" proofs for these larger cases yet.
Need for New Tools: The author suggests that future progress will require combining this graph-theoretic pruning with advanced analytical tools and potentially new graph characterizations to handle the massive search spaces of larger systems.