Noisy hardware forms one of the main hurdles to the realization of a near-term quantum internet. Distillation protocols allows one to overcome this noise at the cost of an increased overhead. We consider here an experimentally relevant class of distillation protocols, which distillntokend-to-end entangled pairs using bilocal Clifford operations, a single round of communication and a possible final local operation depending on the observed measurement outcomes. In the case of permutationally invariant depolarizing noise on the input states, we find a correspondence between these distillation protocols and graph codes. We leverage this correspondence to find provably optimal distillation protocols in this class for several tasks important for the quantum internet. This correspondence allows us to investigate use cases for so-called non-trivial measurement syndromes. Furthermore, we detail a recipe to construct the circuit used for the distillation protocol given a graph code. We use this to find circuits of short depth and small number of two-qubit gates. Additionally, we develop a black-box circuit optimization algorithm, and find that both approaches yield comparable circuits. Finally, we investigate the teleportation of encoded states and find protocols which jointly improve the rate and fidelities with respect to prior art.

Abstract In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k, when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related notions: stable divisorial gonality and stable gonality.

There are several notions of gonality for graphs. The divisorial gonality dgon(G) of a graph G is the smallest degree of a divisor of positive rank in the sense of Baker–Norine. The stable gonality sgon(G) of a graph G is the minimum degree of a finite harmonic morphism from a refinement of G to a tree, as defined by Cornelissen, Kato and Kool. We show that computing dgon(G) and sgon(G) are NP-hard by a reduction from the maximum independent set problem and the vertex cover problem, respectively. Both constructions show that computing gonality is moreover APX-hard.

LetA(n,d) be the maximum number of 0, 1 words of lengthn, any two having Hamming distance at leastd. It is proved thatA(20,8)=256, which implies that the quadruply shortened Golay code is optimal. Moreover, it is shown thatA(18,6) ≤ 673,A(19,6) ≤ 1237,A(20,6) ≤ 2279,A(23,6) ≤ 13674,A(19,8) ≤ 135,A(25,8) ≤ 5421,A(26,8) ≤ 9275,A(27,8) ≤ 17099,A(21,10) ≤ 47,A(22,10) ≤ 84,A(24,10) ≤ 268,A(25,10) ≤ 466,A(26,10) ≤ 836,A(27,10) ≤ 1585,A(28,10) ≤ 2817,A(25,12) ≤ 55, andA(26,12) ≤ 96. The method is based on the positive semidefiniteness of matrices derived from quadruples of words. This can be put as constraint in a semidefinite program, whose optimum value is an upper bound forA(n,d). The order of the matrices involved is huge. However, the semidefinite program is highly symmetric, by which its feasible region can be restricted to the algebra of matrices invariant under this symmetry. By block diagonalizing this algebra, the order of the matrices will be reduced so as to make the program solvable with semidefinite programming software in the above range of values ofnandd.

We call a matrix A nearly totally unimodular if it can be obtained from a totally unimodular matrix $\tilde{A}$ by adding to each row of $\tilde{A}$ an integer multiple of some fixed row $a^{\transp}$ of $\tilde{A}$. For an integer vector b and a nearly totally unimodular matrix A, we denote by $P_{A,b}$ the integer hull of the set $\{x\in\mathbb{R}^n\mid Ax\leq b\}$. We show that $P_{A,b}$ has the integer decomposition property and that we can find a decomposition of a given integer vector $x\in kP_{A,b}$ in polynomial time. An interesting special case that plays a role in many cyclic scheduling problems is when A is a circular-ones matrix. In this case, we show that given a nonnegative integer k and an integer vector x, testing if $x\in kP_{A,b}$ and finding a decomposition of x into k integer vectors in $P_{A,b}$ can be done in time $O(n(n+m)+\text{size}(x))$, where A is an $m\times n$ matrix. We show that the method unifies some known results on coloring circular arc graphs and edge coloring nearly bipartite graphs. It also gives an efficient algorithm for a packet scheduling problem for smart antennas posed by Amaldi, Capone, and Malucelli in [Fourth ALIO/EURO Workshop on Applied Combinatorial Optimization, Pucón, Chile, 2002]; [Proceedings of the Second Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Vol. 1, 2003, pp. 1--4].

We prove that for a graph G=(V,E) without bad K 4 subdivision, and for $b\in {\bf Z}_{+}^{V\cup E}$, the b-stable set polytope is determined by the system of constraints determined by the vertices, edges, and odd circuits. We also prove that this system is totally dual integral. This relates to t-perfect graphs.