Quantum Swap Optimizer

This project aims to optimize the use of SWAP gates in quantum circuits composed of interdependent modules by applying a topological approach. It specifically addresses the challenge of minimizing SWAP gate insertions when deploying circuits on a 2D grid topology. This work is conducted as part of the "Code Transformation and Optimization" course for the 2023-2024 academic year.

Authors

• Daniel Comotti
• Giorgio Miani
• Francesco Micucci

Table of Contents

• Overview
• Implementation Overview
• Repository Structure
• Installation
• References

Overview

The repository optimizes the mapping of quantum circuit modules using a compatibility graph and a maximum clique search. The mapping order is determined based on module dependencies and an ASAP (As Soon As Possible) scheduling approach. A compatibility graph is constructed for each timestep to identify the best layouts on a 2D grid. In this graph, modules and their possible layouts are represented as vertices, with edges linking layouts associated to distinct modules that do not overlap. The edge weights are determined by two factors: Common Dependence Distance, which prioritizes layouts with shared future dependencies to be close, and Input SWAPs Distance, which minimizes the need for SWAP operations to align input-output connections. The algorithm then identifies the optimal layouts by finding the maximum clique within the graph.

Implementation Overview

• Circuit Generation: Creates a quantum circuit with interconnected modules.
• Backend Simulation: Develops a custom backend to simulate a grid-based topology.
• Scheduling: Employs an ASAP scheduler to map modules according to dependency sequence.
• Compatibility Graph: Builds a compatibility graph to optimize module placement and minimize SWAP gate usage.
• Maximal Clique Search: Uses exact or heuristic techniques to identify maximal cliques and reduce SWAP gate insertions.
• Optimizations: Introduces optimizations to reduce computation time on large topologies.

For additional implementation details, see the report document (documents/report.pdf).

Repository Structure

• 'documents/' - Holds all project-related documents, including the report.
• 'plots/' - Contains visual outputs such as plots, charts, and graphs created during the project analysis.
• 'results/' - Stores the data output generated by the project.
• 'scripts/' - Includes executable scripts for generating visualizations of the results.
• 'src/' - Contains the core source code, including primary logic, functions, and modules for the project.
• 'testing/' - Stores scripts for testing the project’s features and functionality.

Installation

1. Clone the repository:

   git clone https://github.com/Giorgio-Miani/quantum-swap-optimizer.git
   cd quantum-swap-optimizer

2. Install the required dependencies:

   pip install -r requirements.txt

References

1. D. Bhoumik, R. Majumdar, and S. Sur-Kolay, Resource-aware scheduling of multiple quantum circuits on a hardware device, 2024.
2. R. Boppana and M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, 1992.
3. C. Bron and J. Kerbosch, Algorithm 457: Finding all cliques of an undirected graph, Commun. ACM, 1973.