Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Great Lakes Symposium on VLSI (GLSVLSI)

Search Space Reduction for Efficient Quantum Compilation

Amisha Srivastava, Chao Lu, Navnil Choudhury, Ayush Arunachalam, Kanad Basu

Published May 31, 2023• 0 citations
Publisher

Abstract

Quantum computers have demonstrated exponential speedup for certain computational tasks like integer factorization, molecular simulation, and machine learning, compared to the classical computers. One of the most challenging problems in quantum computing is quantum compilation, which involves the translation of a quantum circuit into a representation that adheres to the constraints imposed by the quantum hardware. However, this process of mapping the logical qubits to physical qubits incurs a significantly large search space, which needs to be analyzed to obtain the optimal mapping. A non-optimal mapping or compilation strategy introduces additional hardware overhead, thereby rendering inefficiency. Recently, researchers have proposed a technique to reduce the search space for efficient quantum compilation. However, this approach focuses on a generic solution involving only the physical architecture, and hence, as shown in our paper, often fails to incorporate the optimal solution in the reduced search space. To this end, we propose PERM and SGO (PAS), which, to the best of our knowledge, is the first quantum compilation strategy that facilitates a reduced search space comprising a more optimal solution in terms of additional CNOT gates compared to the existing technique. Our experimental evaluation using the MQT benchmarks demonstrates the efficacy of our approach, which furnishes up to 428x reduction compared to the unoptimized search space, and 57.1x reduction compared to existing research, while providing savings in terms of additional CNOT gates by up to 53.85%.

DOI
10.1145/3583781.3590223

Related papers

Limiting the Search Space in Optimal Quantum Circuit Mapping

Lukas Burgholzer, Sarah Schneider, Robert Wille

Executing quantum circuits on currently available quantum computers requires compiling them to a representation that conforms to all restrictions imposed by the targeted architecture. Due to the limited connectivity of the devices' physical qubits, an important step in the compilation process is to map the circuit in such a way that all its gates are executable on the hardware. Existing solutions delivering optimal solutions to this task are severely challenged by the exponential complexity of the problem. In this paper, we show that the search space of the mapping problem can be limited drastically while still preserving optimality. The proposed strategies are generic, architecture-independent, and can be adapted to various mapping methodologies. The findings are backed by both, theoretical considerations and experimental evaluations. Results confirm that, by limiting the search space, optimal solutions can be determined for instances that timeouted before or speed-ups of up to three orders of magnitude can be achieved.

arXiv:2112.00045•Springer eBooks•Jan 17, 2022•25 citations

Quantum-Inspired Hardware-Aware Compiler Optimization

Jincheng Zhang

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.

•Aug 28, 2026•0 citations

Invited: Leveraging Machine Learning for Quantum Compilation Optimization

Xiangyu Ren, Tianyu Zhang, Xiong Xu +2 more

The design of quantum algorithms typically assumes the availability of an ideal quantum computer, characterized by full connectivity, noiseless operation, and unlimited coherence time. However, Noisy Intermediate-Scale Quantum (NISQ) devices present a stark contrast, with a limited number of qubits, non-negligible quantum operation errors, and stringent constraints on the connectivity of physical qubits within a Quantum Processing Unit (QPU). This necessitates the dynamic remapping of logical qubits to physical qubits within the compiler to facilitate the execution of two-qubit gates in the algorithm. However, this introduces additional operations, consequently reducing the fidelity of the algorithm. Therefore, minimizing the number of added gates becomes crucial. Finding such an optimal routing problem is NP-hard, and the task is conventionally addressed using human-crafted heuristics to search for SWAP sequences, but these lack performance guarantees. In this study, we employ a Seq2Seq machine learning model for the qubit routing task, incorporating a Transformer neural network to learn the routing information in the gate and SWAP sequence. Compared to heuristic search-based algorithms, our approach significantly reduces the overhead of quantum computing resources required to adapt logical circuits to physical circuits executable on specific quantum backend hardware.

ACM/IEEE Design Automation Conference (DAC)•Jun 23, 2024•5 citations

An efficient quantum compiler that reduces T count

Luke Heyfron, Earl T. Campbell

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.

Quantum Science and Technology•Jul 26, 2018•96 citations

An Efficient Quantum Compiler that reduces TTT count

Luke Heyfron, Earl T. Campbell

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.

arXiv:1712.01557•Dec 5, 2017•11 citations

Enhancing Quantum Circuit Compilation with Modular Floorplanning

Giacomo Lancellotti, Giovanni Agosta, Alessandro Barenghi +1 more

Quantum circuit compilation is a multi-stage process that translates a high-level quantum circuit representation into a sequence of quantum gates that can be directly executed by a quantum machine. One of the core steps in quantum compilation is mapping, a procedure that transforms a quantum circuit into a semantically equivalent circuit while inserting additional gates to comply with the architectural constraints of the underlying quantum hardware. Current mapping techniques exhibit significant performance degradation—in terms of circuit depth and gate count—when applied to large-scale circuits containing hundreds of thousands of gates or more. In this work, we propose a novel methodology to enhance quantum compiler capabilities by adapting general principles from classical Electronic Design Automation. We model the quantum hardware as being composed of standard cells, onto which portions of the circuit are mapped using a floorplanning-based technique. This contrasts with current state-of-the-art solutions, which perform mapping at the gate level without considering any form of hierarchical abstraction. We use the ChaCha20 stream cipher as a running example to validate and explain our strategy. We evaluate our methodology using two well-known, industrial-grade quantum compilers: IBM Qiskit and Quantinuum TKET. Compared to these compilers, our approach achieves an average circuit depth reduction of 59.78% and 68.85%, respectively, and a gate count reduction of 4.07 % and 6.20 %, respectively. These results are obtained across a large set of randomly generated quantum circuit descriptions in the range of millions of gates, with varying input and output connectivity for each block in the circuit.

IEEE International Conference on Quantum Software (QSW)•Jul 7, 2025•0 citations
Quantum computers have demonstrated exponential speedup for certain computational tasks like integer factorization, molecular simulation, and machine learning, compared to the classical computers. One of the most challenging problems in quantum computing is quantum compilation, which involves the translation of a quantum circuit into a representation that adheres to the constraints imposed by the quantum hardware. However, this process of mapping the logical qubits to physical qubits incurs a significantly large search space, which needs to be analyzed to obtain the optimal mapping. A non-optimal mapping or compilation strategy introduces additional hardware overhead, thereby rendering inefficiency. Recently, researchers have proposed a technique to reduce the search space for efficient quantum compilation. However, this approach focuses on a generic solution involving only the physical architecture, and hence, as shown in our paper, often fails to incorporate the optimal solution in the reduced search space. To this end, we propose PERM and SGO (PAS), which, to the best of our knowledge, is the first quantum compilation strategy that facilitates a reduced search space comprising a more optimal solution in terms of additional CNOT gates compared to the existing technique. Our experimental evaluation using the MQT benchmarks demonstrates the efficacy of our approach, which furnishes up to 428x reduction compared to the unoptimized search space, and 57.1x reduction compared to existing research, while providing savings in terms of additional CNOT gates by up to 53.85%.
Executing quantum circuits on currently available quantum computers requires compiling them to a representation that conforms to all restrictions imposed by the targeted architecture. Due to the limited connectivity of the devices' physical qubits, an important step in the compilation process is to map the circuit in such a way that all its gates are executable on the hardware. Existing solutions delivering optimal solutions to this task are severely challenged by the exponential complexity of the problem. In this paper, we show that the search space of the mapping problem can be limited drastically while still preserving optimality. The proposed strategies are generic, architecture-independent, and can be adapted to various mapping methodologies. The findings are backed by both, theoretical considerations and experimental evaluations. Results confirm that, by limiting the search space, optimal solutions can be determined for instances that timeouted before or speed-ups of up to three orders of magnitude can be achieved.
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.
The design of quantum algorithms typically assumes the availability of an ideal quantum computer, characterized by full connectivity, noiseless operation, and unlimited coherence time. However, Noisy Intermediate-Scale Quantum (NISQ) devices present a stark contrast, with a limited number of qubits, non-negligible quantum operation errors, and stringent constraints on the connectivity of physical qubits within a Quantum Processing Unit (QPU). This necessitates the dynamic remapping of logical qubits to physical qubits within the compiler to facilitate the execution of two-qubit gates in the algorithm. However, this introduces additional operations, consequently reducing the fidelity of the algorithm. Therefore, minimizing the number of added gates becomes crucial. Finding such an optimal routing problem is NP-hard, and the task is conventionally addressed using human-crafted heuristics to search for SWAP sequences, but these lack performance guarantees. In this study, we employ a Seq2Seq machine learning model for the qubit routing task, incorporating a Transformer neural network to learn the routing information in the gate and SWAP sequence. Compared to heuristic search-based algorithms, our approach significantly reduces the overhead of quantum computing resources required to adapt logical circuits to physical circuits executable on specific quantum backend hardware.
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.
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 TTT count -- the number of TTT 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 + TTT circuits. We implemented our compilers in C++ and benchmarked them on random circuits, from which we determine that our TODD compiler yields the lowest TTT 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 TTT count for 97\% of the circuits with an average TTT-count saving of 20\% when compared against the best of all previous circuit decompositions.
Quantum circuit compilation is a multi-stage process that translates a high-level quantum circuit representation into a sequence of quantum gates that can be directly executed by a quantum machine. One of the core steps in quantum compilation is mapping, a procedure that transforms a quantum circuit into a semantically equivalent circuit while inserting additional gates to comply with the architectural constraints of the underlying quantum hardware. Current mapping techniques exhibit significant performance degradation—in terms of circuit depth and gate count—when applied to large-scale circuits containing hundreds of thousands of gates or more. In this work, we propose a novel methodology to enhance quantum compiler capabilities by adapting general principles from classical Electronic Design Automation. We model the quantum hardware as being composed of standard cells, onto which portions of the circuit are mapped using a floorplanning-based technique. This contrasts with current state-of-the-art solutions, which perform mapping at the gate level without considering any form of hierarchical abstraction. We use the ChaCha20 stream cipher as a running example to validate and explain our strategy. We evaluate our methodology using two well-known, industrial-grade quantum compilers: IBM Qiskit and Quantinuum TKET. Compared to these compilers, our approach achieves an average circuit depth reduction of 59.78% and 68.85%, respectively, and a gate count reduction of 4.07 % and 6.20 %, respectively. These results are obtained across a large set of randomly generated quantum circuit descriptions in the range of millions of gates, with varying input and output connectivity for each block in the circuit.