Rapid progress in quantum technology in this decade has dramatically increased the coherence time of qubits (quantum bits) and the fidelity of operations on qubits.Although currently available quantum computers are noisy and intermediate in scale, it is believed that they will be used in some specific applications such as quantum chemistry, machine learning, optimization, and sampling in the near future.Along with progress in quantum computing hardware, development of the software stack has also become more active.A quantum compiler, which translates a quantum program into a sequence of control instructions, is one of the most essential software components to provide a human-friendly programming interface for quantum algorithms.In quantum compilers, optimizing the output instructions is very important: For noisy quantum computers, it increases the probability of completing all the operations before any qubit decoheres, yielding computational results with higher fidelity.Even for fault-tolerant quantum computers, optimization increases the throughput.In this thesis, we address two important optimization tasks in quantum compilers: quantum circuit mapping and quantum circuit scheduling.We provide their formulations as classical optimization problems considering commutation between quantum gates, which are not fully considered in previous studies.We also provide exact and heuristic algorithms for solving them.We examine how considering gate commutation in our algorithms improves the quality of solutions by computational experiments in practical settings.The thesis is organized as follows.After reviewing studies on quantum compilers, we consider the problem of mapping quantum circuits to quantum computers, whose operations are limited by their coupling architecture, with as few additional gates as possible.We propose exact and heuristic algorithms for quantum circuit mapping, which use gate commutation rules and a gate transformation rule of Bridge gate.We compare these algorithms with the state-of-the-art algorithms by computational experiments with circuits of a commonly used benchmark dataset.Next, we consider the problem of scheduling operations in a given circuit with the shortest total execution time.We demonstrate that quantum circuit scheduling can be seen as an optimization problem only when we consider gate commutation and can be interpreted as a special type of job-shop problem.We provide Constraint Programming and Mixed Integer Programming formulations and show how solving circuit scheduling independently improved the schedule length through experiments with real circuits and a compiler.We believe that our algorithms are useful in practical quantum compilers and the developed techniques provide new insight into optimization in quantum compilers.We hope that they will be helpful to advance software stack development and improve the utility of quantum computers.
Abstract Optimizing the
(T)-depth of quantum circuits is a central challenge in fault-tolerant quantum computation, where non-Clifford resources dominate implementation cost. Graph-based abstractions provide lower bounds on achievable
(T)-depth by grouping commuting gates into parallel layers, typically computed via graph coloring. In this work, we investigate the extent to which such graph-optimal
(T)-layerings can be realized using a fixed, replayable local-commutation transformation framework. We introduce a formal distinction between graph-optimal depth, obtained via SAT-based certification, and the depth produced by a concrete transformation procedure. This leads to the notion of an observed construction gap.A replayable local-commutation constructor is defined, providing verifiable transformation sequences and a deterministic mapping from circuits to transformed circuit representations. Empirical evaluation across multiple circuit families indicates that the constructor frequently fails to realize graph-optimal layerings, even in structurally simple cases. In particular, positive observed construction gaps are found in a substantial fraction of benchmark instances.These results highlight a systematic discrepancy between graph-level optimality and realizability under local transformation constraints. The findings suggest that graph-optimal
(T)-depth should be interpreted with caution when used as a proxy for achievable circuit performance under fixed replayable construction procedures.
In the era of noisy intermediate-scale quantum (NISQ) computing, the limited connectivity between qubits is one of the common physical limitations faced by current quantum computing devices. Quantum circuit mapping methods transform quantum circuits into equivalent circuits that satisfy physical connectivity constraints by remapping logical qubits, making them executable. The optimization problem of quantum circuit mapping has NP-hard computational complexity, and existing heuristic mapping algorithms still have significant potential for optimization in terms of the number of quantum gates generated. To reduce the number of SWAP gates inserted during mapping, the solution space of the mapping problem is represented as a tree structure, and the mapping process is equivalent to traversing this tree structure. To effectively and efficiently complete the search process, a beam search framework (BSF) is proposed for solving quantum circuit mapping. By iteratively selecting, expanding, and making decisions, high-quality target circuits are generated. Experimental results show that this method can significantly reduce the number of inserted SWAP gates on medium to large circuits, achieving an average reduction of 44% compared to baseline methods, and is applicable to circuits of various sizes and complexities.