A physical limitation in quantum circuit design is the fact that gates in a quantum system can only act on qubits that are physically adjacent in the architecture. To overcome this problem, SWAP gates need to be inserted to make the circuit physically realizable. The nearest neighbour compliance problem (NNCP) asks for an optimal embedding of qubits in a given architecture such that the total number of SWAP gates to be inserted is minimized. In this paper we study the NNCP on general quantum architectures. Building upon an existing linear programming formulation, we show how the model can be reduced by exploiting the symmetries of the graph underlying the formulation. The resulting model is equivalent to a generalized network flow problem and follows from an in-depth analysis of the automorphism group of specific Cayley graphs. As a byproduct of our approach, we show that the NNCP is polynomial time solvable for several classes of symmetric quantum architectures. Numerical tests on various architectures indicate that the reduction in the number of variables and constraints is on average at least 90%. In particular, NNCP instances on the star architecture can be solved for quantum circuits up to 100 qubits and more than 1000 quantum gates within a very short computation time. These results are far beyond the computational capacity when solving the instances without the exploitation of symmetries.

We prove new upper bounds on the smallest size of affine blocking sets, that is, sets of points in a finite affine space that intersect every affine subspace of a fixed codimension. We show an equivalence between affine blocking sets with respect to codimension-2 subspaces that are generated by taking a union of lines through the origin, and strong blocking sets in the corresponding projective space, which in turn are equivalent to minimal codes. Using this equivalence, we improve the current best upper bounds on the smallest size of a strong blocking set in finite projective spaces over fields of size at least 3. Furthermore, using coding theoretic techniques, we improve the current best lower bounds on a strong blocking set. Our main motivation for these new bounds is their application to trifferent codes, which are sets of ternary codes of length (Formula presented.) with the property that for any three distinct codewords there is a coordinate where they all have distinct values. Over the finite field (Formula presented.), we prove that minimal codes are equivalent to linear trifferent codes. Using this equivalence, we show that any linear trifferent code of length (Formula presented.) has size at most (Formula presented.), improving the recent upper bound of Pohoata and Zakharov. Moreover, we show the existence of linear trifferent codes of length (Formula presented.) and size at least (Formula presented.), thus (asymptotically) matching the best lower bound on trifferent codes. We also give explicit constructions of affine blocking sets with respect to codimension-2 subspaces that are a constant factor bigger than the best known lower bound. By restricting to (Formula presented.), we obtain linear trifferent codes of size at least (Formula presented.), improving the current best explicit construction that has size (Formula presented.).

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 distill <italic>n</italic> to <italic>k</italic> end-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.

In this paper we study the Cayley graph Cay(S_n, T) of the symmetric group S_n generated by a set of transpositions T. We show that for n ≥ 5 the Cayley graph is normal. As a corollary, we show that its automorphism group is a direct product of S_n and the automorphism group of the transposition graph associated to T. This provides an affirmative answer to a conjecture raised by A. Ganesan, Cayley graphs and symmetric interconnection networks, showing that Cay(S_n, T) is normal if and only if the transposition graph is not C₄ or K_n.

Consider a system of m balanced linear equations in k variables with coefficients in F_q. If k ⩾ 2m + 1, then a routine application of the slice rank method shows that there are constants β, γ ⩾ 1 with γ < q such that, for every subset S ⊆ Fⁿq of size at least β · γⁿ, the system has a solution (x₁, …, x_k) ∈ S^k with x₁, …, x_k not all equal. Building on a series of papers by Mimura and Tokushige and on a paper by Sauermann, this paper investigates the problem of finding a solution of higher non-degeneracy; that is, a solution where x₁, …, x_k are pairwise distinct, or even a solution where x₁, …, x_k do not satisfy any balanced linear equation that is not a linear combination of the equations in the system. In this paper, we focus on linear systems with repeated columns. For a large class of systems of this type, we prove that there are constants β, γ ⩾ 1 with γ < q such that every subset S ⊆ Fⁿq of size at least β · γⁿ contains a solution that is non-degenerate (in one of the two senses described above). This class is disjoint from the class covered by Sauermann’s result, and captures the systems studied by Mimura and Tokushige into a single proof. Moreover, a special case of our results shows that, if S ⊆ Fⁿp is a subset such that S − S does not contain a non-trivial k-term arithmetic progression (with p prime and 3 ⩽ k ⩽ p), then S must have exponentially small density.

Let ai1x1+・・・+aikxk = 0, i ∈ [m] be a balanced homogeneous system of linear equations with coefficients ai j from a finite field Fq. We say that a solution x = (x1, …,xk) with x1, …,xk ∈ (Formula presented) is generic if every homogeneous balanced linear equation satisfied by x is a linear combination of the given equations. We show that if the given system is tame, subsets S ⊆ (Formula presented) without generic solutions must have exponentially small density. Here, the system is called tame if for every implied system the number of equations is less than half the number of used variables. Using a subspace sampling argument this also gives a ‘supersaturation result’: there is a constant c such that for ε?> 0 sufficiently small, every subset S ⊆ (Formula presented) of size at least q(1−ε)n contains Ω(q(k−m−εc)n) solutions as n→∞. For q < 4 the tameness condition can be left out. Our main tool is a modification of the slice rank method to leverage the existence of many solutions in order to obtain high rank solutions.

Entanglement distillation is an essential building block in quantum communication protocols. Here, we study the class of near-term implementable distillation protocols that use bilocal Clifford operations followed by a single round of communication. We introduce tools to enumerate and optimise over all protocols for up to n = 5 (not necessarily equal) Bell-diagonal states using a commodity desktop computer. Furthermore, by exploiting the symmetries of the input states, we find all protocols for up to n = 8 copies of a Werner state. For the latter case, we present circuits that achieve the highest fidelity with perfect operations and no decoherence. These circuits have modest depth and number of two-qubit gates. Our results are based on a correspondence between distillation protocols and double cosets of the symplectic group, and improve on previously known protocols.

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.

An integer packing set is a set of non-negative integer vectors with the property that, if a vector x is in the set, then every non-negative integer vector y with y≤x is in the set as well. The main result of this paper is that integer packing sets, ordered by inclusion, form a well-quasi-ordering. This result allows us to answer a recently posed question: the k-aggregation closure of any packing polyhedron is again a packing polyhedron.

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.

We prove that the (divisorial) gonality of a finite connected graph is lower bounded by its treewidth. Graphs for which equality holds include the grid graphs and the complete multipartite graphs. We prove that the treewidth lower bound also holds for metric graphs (tropical curves) by constructing for any positive rank divisor on a metric graph a positive rank divisor of the same degree on a subdivision of the underlying combinatorial graph. Finally, we show that the treewidth lower bound also holds for a related notion of gonality defined by Caporaso and for stable gonality as introduced by Cornelissen et al.