⚛️ quantum physics

NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

This paper establishes that the feasibility of each level of the NPA hierarchy for quantum isomorphism is equivalent to the equality of homomorphism counts from a specific class of planar graphs, thereby providing a new proof of the Mančinska-Roberson theorem and enabling a randomized polynomial-time algorithm for deciding the exact feasibility of these SDP relaxations.

Original authors: Prem Nigam Kar, David E. Roberson, Tim Seppelt, Peter Zeman

Published 2026-01-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Prem Nigam Kar, David E. Roberson, Tim Seppelt, Peter Zeman

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 have two complex puzzles, let's call them Graph A and Graph B. In the world of mathematics, these are just networks of dots (vertices) connected by lines (edges). The big question is: Are these two puzzles actually the same shape, just drawn differently?

In the classical world, we have a very strict test for this called "Isomorphism." If you can't rearrange the dots and lines of Puzzle A to perfectly match Puzzle B, they are different.

But in the quantum world (where particles can be entangled and exist in multiple states at once), the rules change. Two puzzles might look different to a classical eye but be "Quantum Isomorphic." This means two players, Alice and Bob, who share a secret quantum connection, could play a game proving the puzzles are the same, even if a classical computer says they aren't.

The problem is that checking for "Quantum Isomorphism" is incredibly hard. In fact, the paper says it's undecidable in the general case—meaning there is no single algorithm that can always give you a "yes" or "no" answer for every pair of puzzles.

This paper introduces a way to break this impossible problem down into manageable, smaller steps. Here is the simple explanation of what they did:

1. The "Ladder" of Approximations (The NPA Hierarchy)

Since we can't solve the whole quantum puzzle at once, the authors use a "ladder" called the NPA Hierarchy.

Think of this ladder as a series of increasingly strict tests.
Level 1 is a very loose test. It might say "Yes, they look similar," even if they aren't truly quantum isomorphic.
Level 2 is stricter.
Level 100 is even stricter.
If you climb high enough (to infinity), you eventually reach the perfect answer.

The paper's main job is to figure out exactly what it means to pass Level $k$ of this ladder without doing the heavy quantum math.

2. The "Guest List" Test (Homomorphism Indistinguishability)

The authors discovered a clever shortcut. Instead of solving complex quantum equations, you can check if the two puzzles look the same to a specific guest list of shapes.

Imagine you invite a specific group of "guests" (small, simple shapes) to visit Puzzle A and Puzzle B.
You count how many ways each guest can fit into Puzzle A and how many ways they can fit into Puzzle B.
If every single guest fits the same number of times into both puzzles, then the puzzles pass the test.

The paper proves that:

To pass Level $k$ of the quantum ladder, you only need to check a specific, limited guest list.
This guest list is made of Planar Graphs (shapes that can be drawn on a piece of paper without any lines crossing).
Specifically, for Level $k$ , the guests are a special subset of these planar shapes that aren't too "twisted" (they have low "treewidth," a measure of how tree-like they are).

3. The "Magic" Result: A New Proof

The paper connects these dots to prove a famous result by Mančinska and Roberson in a new, simpler way.

The Old Proof: Used heavy, abstract machinery called "Quantum Groups" (think of it as using a sledgehammer to crack a nut).
The New Proof: Shows that if you climb the entire NPA ladder (checking all levels), the "guest list" eventually grows to include ALL possible planar graphs.
Therefore, two graphs are Quantum Isomorphic if and only if they look the same to every possible planar shape.
This proves the old result without needing the sledgehammer of Quantum Groups.

4. The Practical Win: A Faster Algorithm

Because the authors figured out that passing Level $k$ is just about counting how well specific planar shapes fit into the graphs, they built a randomized algorithm (a computer program that uses a bit of luck to be fast).

Before: Checking if a graph passes Level $k$ of the quantum test required solving massive, complex math problems that were slow and only gave approximate answers.
Now: The computer just counts the "guests" (homomorphisms) from the specific planar shapes.
Speed: This new method is fast (polynomial time) and gives an exact "Yes" or "No" answer for any fixed level $k$ .

Summary Analogy

Imagine you want to know if two secret recipes are identical.

The Hard Way: Try to taste every possible ingredient combination in the universe (Undecidable/Impossible).
The Ladder (NPA): You start by tasting just salt, then salt and pepper, then salt, pepper, and sugar. Each step gets you closer to the truth.
The Paper's Discovery: You don't need to taste the ingredients directly. Instead, you just need to see if a specific list of "taste testers" (planar shapes) react to both recipes in the exact same way.
The Result: If you use the right list of testers for Step $k$ , you can instantly know if the recipes pass that step. If you use the list of all planar testers, you know if the recipes are truly identical in the quantum sense. And best of all, you can run this test on a computer very quickly.

What the paper does NOT claim:

It does not claim this solves the general Graph Isomorphism problem for all graphs (that's a different, classical problem).
It does not claim this has immediate medical or clinical applications.
It does not claim to build a physical quantum computer; it is purely a mathematical and algorithmic breakthrough in understanding how these quantum tests work.

Technical Summary: NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

1. Problem Statement and Motivation

The paper addresses the computational and structural characterization of quantum isomorphism between graphs. Two graphs $G$ and $H$ are quantum isomorphic ( $G \cong_q H$ ) if there exists a perfect quantum strategy for the graph isomorphism game, involving shared entanglement and local measurements.

While classical graph isomorphism is decidable (solvable in quasipolynomial time), Mančinska and Roberson [FOCS'20] proved that deciding quantum isomorphism is undecidable in general. This motivates the study of relaxations of quantum isomorphism, specifically the NPA hierarchy (Named after Navascués, Pironio, and Acín), which provides a sequence of semidefinite programming (SDP) relaxations to approximate quantum correlations.

A central question in the emerging theory of homomorphism indistinguishability is whether the feasibility of each level of these SDP relaxations can be characterized combinatorially. Specifically, the authors ask: Is the feasibility of the $k$ -th level of the NPA hierarchy for the $(G, H)$ -isomorphism game equivalent to $G$ and $H$ being homomorphism indistinguishable over a specific class of graphs?

2. Methodology and Proof Techniques

The paper employs a synthesis of algebraic combinatorics, operator theory, and graph theory. The core methodology relies on the correspondence between bilabelled graphs and homomorphism tensors.

Key Tools

Bilabelled Graphs and Homomorphism Tensors: A $(k, l)$ -bilabelled graph $F = (F, u, v)$ is associated with a tensor $F^G \in \mathbb{C}^{V(G)^k \times V(G)^l}$ , where entries count homomorphisms mapping input labels $u$ to $x$ and output labels $v$ to $y$ . Combinatorial operations on bilabelled graphs (series composition, parallel composition, cyclic permutation of labels) correspond to algebraic operations on these tensors (matrix multiplication, Schur product, permutation).
NPA Hierarchy Reformulation: The authors reformulate the existence of a certificate for the $k$ -th level of the NPA hierarchy as the existence of a level- $k$ quantum isomorphism map. This is a completely positive map between matrix algebras that preserves specific structural properties related to homomorphism tensors.
Algebraic $k$ -Equivalence: They introduce the concept of algebraic $k$ -equivalence, defined as an algebra isomorphism between subalgebras generated by homomorphism tensors of specific atomic graphs, satisfying trace-preserving and unital conditions.

Proof Structure

The proof of the main theorem proceeds through a chain of equivalences:

NPA Feasibility $\iff$ Quantum Isomorphism Map: A principal submatrix of an NPA certificate is interpreted as the Choi matrix of a completely positive map. The constraints of the NPA hierarchy are shown to be equivalent to the axioms of a level- $k$ quantum isomorphism map (Theorem 3.6).
Quantum Isomorphism Map $\iff$ Algebraic $k$ -Equivalence: The quantum isomorphism map is shown to restrict to an isomorphism between the algebras generated by homomorphism tensors of a specific set of atomic graphs, $Q_k$ (Theorem 3.9).
Algebraic $k$ -Equivalence $\iff$ Homomorphism Indistinguishability: Using the correspondence between graph operations and tensor algebra, the existence of such an algebra isomorphism is shown to be equivalent to $G$ and $H$ having equal homomorphism counts from a constructed class of graphs, $P_k$ (Theorem 4.4).

3. Key Contributions and Results

Main Theorem (Theorem 1.1)

For graphs $G$ and $H$ and an integer $k \ge 1$ , the following are equivalent:

The $k$ -th level of the NPA hierarchy for the $(G, H)$ -isomorphism game is feasible.
There exists a level- $k$ quantum isomorphism map from $G$ to $H$ .
$G$ and $H$ are algebraically $k$ -equivalent.
$G$ and $H$ are homomorphism indistinguishable over the graph class $P_k$ .

Here, $P_k$ is a class of planar bilabelled graphs constructed inductively from atomic graphs $Q_k$ using series composition, parallel composition with specific atomic graphs, and cyclic label permutations.

Properties of the Graph Class $P_k$

Planarity: Every graph in $P_k$ is planar (Lemma 4.7).
Bounded Treewidth: The underlying graphs of $P_k$ have treewidth at most $3k-1$ (Lemma 4.5).
Minor-Closed: The class $P_k$ is closed under taking minors (Lemma 4.8).
Union: The union of the underlying unlabelled graphs of all $P_k$ (for $k \in \mathbb{N}$ ) is exactly the set of all planar graphs (Corollary 4.12).

Algorithmic Result (Theorem 1.2)

The paper presents a randomized polynomial-time algorithm to decide the exact feasibility of the $k$ -th level of the NPA hierarchy for fixed $k$ .

Runtime: $n^{O(k)} k^{O(1)}$ , where $n = \max\{|V(G)|, |V(H)|\}$ .
Method: Instead of solving the SDP, the algorithm checks homomorphism indistinguishability over $P_k$ modulo a randomly chosen prime $p$ . It computes a basis for the vector space spanned by homomorphism tensors of graphs in $P_k$ over a finite field.
Significance: This avoids the approximation issues inherent in standard SDP solvers (like the ellipsoid method) and provides an exact decision procedure for fixed levels.

Alternative Proof of Mančinska and Roberson [FOCS'20]

By combining the main theorem with the convergence of the NPA hierarchy and the fact that $\bigcup_k P_k$ is the set of all planar graphs, the authors derive a new proof that $G \cong_q H$ if and only if $G$ and $H$ are homomorphism indistinguishable over all planar graphs.

Distinction: Unlike the original proof in [FOCS'20], which relied heavily on the theory of compact quantum groups and intertwiners, this proof is purely combinatorial and algebraic, utilizing the NPA hierarchy and homomorphism tensors.

4. Significance and Claims

The paper claims to provide a homomorphism indistinguishability characterization for the NPA hierarchy, placing quantum isomorphism relaxations within the broader theoretical framework of homomorphism indistinguishability relations.

Theoretical Unification: It bridges the gap between the non-commutative NPA hierarchy and the classical Lasserre hierarchy (which was previously characterized by Roberson and Seppelt [ICALP'23] using graph classes $L_k$ ).
Computational Advantage: It establishes that exact feasibility for fixed levels of the NPA hierarchy is decidable in randomized polynomial time, a result that is not immediately obvious from the SDP formulation alone.
Simplification of Quantum Isomorphism Theory: The paper offers a proof of the fundamental characterization of quantum isomorphism (via planar graphs) that avoids the "heavy machinery" of quantum groups, relying instead on the combinatorial structure of the NPA constraints.

The authors note that while $P_k$ is a subclass of planar graphs with bounded treewidth, the precise structural relationship between $P_k$ and the graph classes $L_k$ (used for classical isomorphism relaxations) remains an open problem (Problem 6.1). They also pose the question of whether there exists a graph class where quantum isomorphism is determined by a fixed level of the NPA hierarchy but differs from classical isomorphism (Problem 6.2).