Shortest path on a hypergraph with no leftovers

Question

In quantum computing, determining the code distance of a stabilizer code is similar to the shortest path problem on a hypergraph. Each node in the graph would be some sort of parity check performed by the code, and each hyperedge would be a set of parity checks a particular physical error flips. If you construct the graph correctly, paths between certain nodes will correspond to logical errors and the code distance will correspond to a shortest path because the shortest path corresponds to the minimum number of errors. So that's the motivation for being interested in the shortest path problem on a hypergraph.

I did some preliminary searching for existing algorithms that solve this problem. Unfortunately, it seems that existing research is actually referring to a slightly different problem than what I had in mind. In particular, existing work seems to be happy to pass through edges that touch unrelated nodes an odd number of times. In the context of a code distance calculation this would be a bad idea, because it would cause parity check violations elsewhere in the graph. The "minimum length path" wouldn't successfully get back into the desired codespace.

The variant of the shortest hyperpath problem that I care about is as follows. Let $n$ and $m$ be the start and end nodes. Let $E$ be a set of hyperedges. $E$ is a hyperpath between $n$ and $m$ if $n$ appears in an odd number of the hyperedges of $E$, $m$ also appears in an odd number of the hyperedges of $E$, and all other nodes appear an even number of times in the hyperedges of $E$. I want $n$ and $m$ to be the only nodes whose corresponding parity check triggers when the corresponding errors from $E$ are applied. The goal is to find the hyperpath with the minimum number of hyperedges.

Has there been previous work on this problem? Note that I'm mostly interested in the case where the hyperedge degree is bounded (e.g. the error graph of the surface code typically has no hyperedges with degree larger than 4, even with circuit level noise and two qubit gate errors).

Answer 1

This answer doesn't answer the question about previous work, but it does show the problem is NP-complete.

Lemma 1. Finding a shortest $s$-$t$ hyperpath (as defined in the post) in a given hypergraph is NP-complete, even in hypergraphs of hyperedge degree 3.

Proof. Clearly the problem is in NP. It is NP-hard by the following reduction from 3D-matching.

Fix an instance of 3D matching -- a set of triples $X$ from universe $U=\{1,2,\ldots,3n\}$. Given the instance, the reduction outputs the instance of Shortest $s$-$t$ Hyperpath in the hypergraph $G=(V,E)$ defined as follows.

First create the vertex set $V=\{b_0, a_1, b_1, a_2, b_2, a_3, b_3, \ldots, a_{3n}, b_{3n}\}$. Define the hyperpath source and destination to be $s=b_0$ and $t=b_{3n}$. Next, add $3n$ "path" hyperedges $$(b_0,a_1,b_1), (b_1,a_2,b_2), (b_2, a_3, b_3), \ldots, (b_{3n-1}, a_{3n}, b_{3n}).$$ Finally, for each triple $(i, j, k)$ in $X$, add hyperedge $(a_i, a_j, a_k)$. This completes the reduction.

We'll show that there is an $s$-$t$ hyperpath of length at most $4n$ if and only if there is a 3D matching.

First suppose that there is a 3D matching $M$ (that is, an $n$-subset of $X$ such that each element in $\{1,\ldots,3n\}$ occurs in exactly one triple in $M$). Then the $3n$ "path" hyperedges, together with the $n$ hyperedges $\{(a_i, a_j, a_k) : (i, j, k) \in M\}$ form the desired hyperpath.

Conversely, suppose there is such a hyperpath (from $b_0$ to $b_{3n}$). By induction on the $b_i$ vertices, each of the $3n$ path hyperedges $(b_i, a_{i+1}, b_{i+1})$ must be in the hyperpath. Then, since each vertex $a_1,\ldots,a_{3n}$ is in one such path hyperedge, each such vertex must also be in an odd number of other hyperedges in the hyperpath. Those hyperedges must correspond to triples in $X$. Each such hyperedge contains $3$ of the $a_i$ vertices, and the hyperpath has length $4n$ (or less), so there must be $n$ such hyperedges, and their corresponding triples must form a 3D matching. $~~\Box$

I suspect that even determining whether there exists any $s$-$t$ hyperpath is also NP-complete.

EDIT: I think the existence of an $s$-$t$ hyperpath can be determined in polynomial time by checking feasibility of this set of linear equations over $\mathbb{Z}_2$: introduce an indicator variable $x_e$ for each hyperedge $e$, then, for every vertex $v$ constrain $$\sum_{e \ni v} x_e = \begin{cases} 1 & \text{if } v\in\{s,t\} \\ 0 & \text{otherwise}.\end{cases}$$