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.

In the quadratic minimum spanning tree problem (QMSTP) one wants to find the minimizer of a quadratic function over all possible spanning trees of a graph. We present a formulation of the QMSTP as a mixed-integer semidefinite program exploiting the algebraic connectivity of a graph. Based on this formulation, we derive a doubly nonnegative relaxation for the QMSTP and investigate classes of valid inequalities to strengthen the relaxation using the Chvátal-Gomory procedure for mixed-integer conic programming. Solving the resulting relaxations is out of reach for off-the-shelf software. We therefore develop and implement a version of the Peaceman-Rachford splitting method that allows to compute the new bounds for graphs from the literature. The computational results demonstrate that our bounds significantly improve over existing bounds from the literature in both quality and computation time, in particular for graphs with more than 30 vertices. This work is further evidence that semidefinite programming is a valuable tool to obtain high-quality bounds for problems in combinatorial optimization, in particular for those that can be modelled as a quadratic problem.

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.

It is well known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a comprehensive study on discrete positive semidefinite matrices, we introduce a generic approach to derive mixed-integer SDP (MISDP) formulations of binary quadratically constrained quadratic programs and binary quadratic matrix programs. Applying a problem-specific approach, we derive more compact MISDP formulations of several problems, such as the quadratic assignment problem, the graph partition problem, and the integer matrix completion problem. We also show that several structured problems allow for novel compact MISDP formulations through the notion of association schemes. Complementary to the recent advances on algorithmic aspects related to MISDP, this work opens new perspectives on solution approaches for the here considered problems.