EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3817. Exploiting symmetries in optimal quantum circuit design

Invited abstract in session WA-38: Recent advances in LP and SDP for discrete optimization problems, stream Conic Optimization: Theory, Algorithms, and Applications.

Wednesday, 8:30-10:00
Room: 34 (building: 306)

Authors (first author is the speaker)

1. Frank de Meijer
Delft Institute of Applied Mathematics, Delft University of Technology
2. Dion Gijswijt
Delft University of Technology
3. Renata Sotirov
Tilburg University

Abstract

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 neighbor 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 LP 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 analysis of the automorphism group of Cayley graphs generated by transpositions. 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%. This opens the way to solving NNCP instances on large quantum circuits that are far beyond the computational capacity when solving them without the exploitation of symmetries.

Keywords

Status: accepted

Back to the list of papers