Optimizing Quantum Compilers: Efficient and Effective Algorithms

Quantum computing has made significant progress in recent years, with Google and IBM releasing quantum computers with 72 and 50 qubits, respectively. Google has also achieved quantum supremacy with its 54-qubit device, and IBM has announced the release of the Osprey quantum computer with 433 qubits. These developments suggest that quantum computers with even greater qubit counts may be available in the near future.This upcoming period is termed Noisy Intermediate Scale Quantum (NISQ) era, because of the noisy characteristics of near-term devices.Computation on NISQ hardware is modeled using a library of supported quantum gates which can be directly implemented on it and a coupling graph that specifies available qubits interactions for multi-qubit quantum gates. While improvements to quantum hardware are continuously being made by experimentalists, quantum computing experts can contribute to the utility of quantum devices by developing software. This software would aim to adapt textbook quantum algorithms (e.g., for factoring or quantum simulation) to hardware constraints, that include: (1) limited number of qubits, (2) limited connectivity between qubits, (3) limited hardware-specific gate sets, and (4) limited circuit depth due to noise. Algorithms adapted to these constraints will likely look dramatically different from their textbook counterparts. Such software, which performs the task of translating quantum algorithms into quantum circuits according to hardware constraints, is called a quantum compiler. In conclusion, without a good compiler, most quantum algorithms are not applicable in practice.Quantum compilers typically undertake three primary tasks: quantum state preparation, circuit synthesis, and qubit mapping. Quantum state preparation involves preparing the initial state of the quantum system before running the algorithm. The preparation of such a state itself requires a computation performed by a quantum circuit. This task can be challenging, as quantum algorithms assume some specific initial states in superposition before performing the desired application-specific computations. Circuit synthesis involves the process of constructing a quantum circuit that implements the desired quantum algorithm. Qubit mapping is another important task for quantum compilers, which involves mapping the logical qubits of the algorithm to the physical qubits of the quantum computer. In this thesis, I focus on the first two tasks of quantum compilers, quantum state preparation, and circuit synthesis. These tasks are essential for the successful execution of quantum algorithms, and developing efficient and effective algorithms for these tasks is crucial for the continued advancement of quantum computing.