Similar to classical programming, high-level quantum programming languages generate code that cannot be executed directly by quantum hardware and must be compiled. However, unlike classical code, quantum programs must be compiled before each execution, making the trade-off between compilation time and execution time particularly significant. In this paper, we address the first step of quantum compilation: multi-qubit gate decomposition. We analyze the trade-offs of state-of-the-art decomposition algorithms by implementing them in the Ket quantum programming platform and collecting numerical performance data. This is the first study to both implement and analyze the current state-of-the-art decomposition methods within a single platform. Based on our findings, we propose two compilation profiles: one optimized for minimizing compilation time and another for minimizing quantum execution time. Our results provide valuable insights for both quantum compiler developers and quantum programmers, helping them make informed decisions about gate decomposition strategies and their impact on overall performance.
Similar to classical programming, high-level quantum programming languages generate code that cannot be executed directly by quantum hardware and must be compiled. However, unlike classical code, quantum programs must be compiled before each execution, making the trade-off between compilation time and execution time particularly significant. In this paper, we address the first step of quantum compilation: multi-qubit gate decomposition. We analyze the trade-offs of state-of-the-art decomposition algorithms by implementing them in the Ket quantum programming platform and collecting numerical performance data. This is the first study to both implement and analyze the current state-of-the-art decomposition methods within a single platform. Based on our findings, we propose two compilation profiles: one optimized for minimizing compilation time and another for minimizing quantum execution time. Our results provide valuable insights for both quantum compiler developers and quantum programmers, helping them make informed decisions about gate decomposition strategies and their impact on overall performance.
With the increasing capabilities of quantum systems, the efficient, practical execution of quantum programs is becoming more critical. Each execution includes compilation time, which accounts for substantial overhead of the overall program runtime. To address this challenge, proposals that leverage precompilation techniques have emerged, whereby entire circuits or select components are precompiled to mitigate the compilation time spent during execution. Considering the impact of compilation time on quantum program execution, identifying the contribution of each individual compilation task to the execution time is necessary in directing the community’s research efforts towards the development of an efficient compilation and execution pipeline. In this work, we perform a preliminary analysis of the quantum circuit compilation process in Qiskit, examining the cumulative runtime of each individual compilation task and identifying the tasks that most strongly impact the overall compilation time. Our results indicate that, as the desired level of optimization increases, circuit optimization and gate synthesis passes become the dominant tasks in compiling a Quantum Fourier Transform, with individual passes consuming up to 87% of the total compilation time. Mapping passes require the most compilation time for a GHZ state preparation circuit, accounting for over 99% of total compilation time.
Traditional compiler optimization focuses on maximizing performance within the constraints of classical architectures. However, quantum computing presents a fundamentally different paradigm, demanding a new approach to software optimization. This paper proposes a hardware-aware compiler optimization technique, inspired by quantum computing principles, to bridge the gap between high-level programming languages and the specific characteristics of quantum hardware. The core idea is to translate high-level code into quantum circuits while explicitly considering factors like qubit connectivity, gate fidelity, and decoherence. This approach allows for optimization strategies tailored to the unique limitations and opportunities of quantum devices, potentially leading to significant performance improvements compared to generic quantum compilation methods. The compiler operates by analyzing the algorithmic complexity, identifying quantum-native operations, and strategically mapping them onto the available quantum hardware, thereby minimizing the impact of hardware constraints. This paper outlines the framework, key components, and potential optimizations within this hardware-aware compiler.
We present a method for optimizing quantum circuit compilation by automating the allocation of auxiliary qubits for multi-qubit gate decompositions. This approach is implemented and evaluated within the high-level quantum programming platform Ket. Our results indicate that the decomposition of multi-qubit gates is more effectively handled by the compiler, which has access to all circuit parameters, rather than through a quantum programming API. To evaluate the approach, we compared our implementation against Qiskit, a widely used quantum programming platform, by analyzing two quantum algorithms. Using a 16-qubit QPU, we observed a reduction of 87% in the number of CNOT gates in Grover's algorithm for 9 qubits. For a state preparation algorithm with 7 qubits, the number of CNOT gates was reduced from 2.8×107 to 5.7×103, leveraging additional Ket optimizations for high-level quantum program constructions. Overall, a quadratic reduction in the number of CNOT gates in the final circuit was observed, with greater improvements achieved when more auxiliary qubits were available. These findings underscore the importance of automatic resource management, such as auxiliary qubit allocation, in optimizing quantum applications and improving their suitability for near-term quantum hardware.
This paper presents novel methods for optimizing multi-controlled quantum gates, which naturally arise in high-level quantum programming. Our primary approach involves rewriting U ( 2 ) gates as S U ( 2 ) gates, utilizing one auxiliary qubit for phase correction. This reduces the number of CNOT gates required to decompose any multi-controlled quantum gate from O ( n 2 ) to at most 32 n . Additionally, we can reduce the number of CNOTs for multi-controlled Pauli gates from 16 n to 12 n and propose an optimization to reduce the number of controlled gates in high-level quantum programming. We have implemented these optimizations in the Ket quantum programming platform and demonstrated significant reductions in the number of gates. For instance, for a Grover's algorithm layer with 114 qubits, we achieved a reduction in the number of CNOTs from 101,252 to 2,684. This reduction in the number of gates significantly impacts the execution time of quantum algorithms, thereby enhancing the feasibility of executing them on NISQ computers.
Unitary decomposition is a widely used method to map quantum algorithms to an arbitrary set of quantum gates. Efficient implementation of this decomposition allows for the translation of bigger unitary gates into elementary quantum operations, which is key to executing these algorithms on existing quantum computers. The decomposition can be used as an aggressive optimization method for the whole circuit, as well as to test part of an algorithm on a quantum accelerator. For the selection and implementation of the decomposition algorithm, perfect qubits are assumed. We base our decomposition technique on Quantum Shannon Decomposition, which generates O(344n) controlled-not gates for an n-qubit input gate. In addition, we implement optimizations to take advantage of the potential underlying structure in the input or intermediate matrices, as well as to minimize the execution time of the decomposition. Comparing our implementation to Qubiter and the UniversalQCompiler (UQC), we show that our implementation generates circuits that are much shorter than those of Qubiter and not much longer than the UQC. At the same time, it is also up to 10 times as fast as Qubiter and about 500 times as fast as the UQC.
Abstract Before executing a quantum algorithm, one must first decompose the algorithm into machine-level instructions compatible with the architecture of the quantum computer, a process known as quantum compiling. There are many different quantum circuit decompositions for the same algorithm but it is desirable to compile leaner circuits. A fundamentally important cost metric is the T count—the number of T gates in a circuit. For the single qubit case, optimal compiling is essentially a solved problem. However, multi-qubit compiling is a harder problem with optimal algorithms requiring classical runtime exponential in the number of qubits. Here, we present and compare several efficient quantum compilers for multi-qubit Clifford + T circuits. We implemented our compilers in C++ and benchmarked them on random circuits, from which we determine that our TODD compiler yields the lowest T counts on average. We also benchmarked TODD on a library of reversible logic circuits that appear in quantum algorithms and found that it reduced the T count for 97% of the circuits with an average T -count saving of 20% when compared against the best of all previous circuit decompositions.