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

arXiv:2403.11598 · Leibniz international proceedings in informatics

Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits

Irfansha Shaik, Jaco van de Pol

Published Jan 1, 2024• 7 citations
arXivHTMLPDF

Abstract

Layout synthesis is mapping a quantum circuit to a quantum processor. SWAP gate insertions are needed for scheduling 2-qubit gates only on connected physical qubits. With the ever-increasing number of qubits in NISQ processors, scalable layout synthesis is of utmost importance. With large optimality gaps observed in heuristic approaches, scalable exact methods are needed. While recent exact and near-optimal approaches scale to moderate circuits, large deep circuits are still out of scope. In this work, we propose a SAT encoding based on parallel plans that apply 1 SWAP and a group of CNOTs at each time step. Using domain-specific information, we maintain optimality in parallel plans while scaling to large and deep circuits. From our results, we show the scalability of our approach which significantly outperforms leading exact and near-optimal approaches (up to 100x). For the first time, we can optimally map several 8, 14, and 16 qubit circuits onto 54, 80, and 127 qubit platforms with up to 17 SWAPs. While adding optimal SWAPs, we also report near-optimal depth in our mapped circuits.

DOI
10.4230/lipics.sat.2024.26

Related papers

Optimal Layout Synthesis for Quantum Circuits as Classical Planning (full version)

Irfansha Shaik, Jaco van de Pol

In Layout Synthesis, the logical qubits of a quantum circuit are mapped to the physical qubits of a given quantum hardware platform, taking into account the connectivity of physical qubits. This involves inserting SWAP gates before an operation is applied on distant qubits. Optimal Layout Synthesis is crucial for practical Quantum Computing on current error-prone hardware: Minimizing the number of SWAP gates directly mitigates the error rates when running quantum circuits. In recent years, several approaches have been proposed for minimizing the required SWAP insertions. The proposed exact approaches can only scale to a small number of qubits. Proving that a number of swap insertions is optimal is much harder than producing near optimal mappings. In this paper, we provide two encodings for Optimal Layout Synthesis as a classical planning problem. We use optimal classical planners to synthesize the optimal layout for a standard set of benchmarks. Our results show the scalability of our approach compared to previous leading approaches. We can optimally map circuits with 9 qubits onto a 14 qubit platform, which could not be handled before by exact methods.

arXiv:2304.12014•Apr 24, 2023•3 citations

Optimal Layout Synthesis for Quantum Circuits as Classical Planning

Irfansha Shaik, Jaco van de Pol

In Layout Synthesis, the logical qubits of a quantum circuit are mapped to the physical qubits of a given quantum hardware platform, taking into account the connectivity of physical qubits. This involves inserting SWAP gates before an operation is applied on distant qubits. Optimal Layout Synthesis is crucial for practical Quantum Computing on current error-prone hardware: Minimizing the number of SWAP gates directly mitigates the error rates when running quantum circuits. In recent years, several approaches have been proposed for minimizing the required SWAP insertions. The proposed exact approaches can only scale to a small number of qubits. In this paper, we provide two encodings for Optimal Layout Synthesis as a classical planning problem. We use optimal classical planners to synthesize the optimal layout for a standard set of benchmarks. Our results show the scalability of our approach compared to previous leading approaches. We can optimally map circuits with 9 qubits onto a 14 qubit platform, which could not be handled before by exact methods.

•Oct 28, 2023•14 citations

Scalable Optimal Layout Synthesis for NISQ Quantum Processors

Wan-Hsuan Lin, Jason Kimko, Daniel Bochen Tan +2 more

Due to its effect on the success rate of a quantum circuit, quantum layout synthesis is a crucial step for circuit compilation. As such, having a layout synthesis tool that provides high solution quality is important to maximize circuit performance and fidelity for NISQ application. Previous heuristic approaches have been shown to be far from optimal when evaluated on known-optimal benchmarks. Alternatively, exact layout synthesis tools can generate optimal results with the aid of constraint solvers but generally suffer from scalability issues because of inefficient encodings and slow optimization methods. In this paper, we propose a scalable optimal layout synthesis tool that improves upon previous works, through a more succinct problem formulation as well as better encoding techniques. Additionally, we implement a depth and SWAP count optimization feature that performs iterative refinement under a fixed time budget. Experimental results show that for depth optimization, our tool can achieve a 692× speedup over the state-of-the-art optimal layout synthesis, and for SWAP optimization, we can obtain a 6,957× speedup on average. Compared to a leading heuristic-based synthesizer, for depth optimization, we can solve circuits consisting of 54 program qubits and 1726 gates within 11 hours with an 18× depth reduction and by 12× SWAP count reduction on average.

ACM/IEEE Design Automation Conference (DAC)•Jul 9, 2023•36 citations

Depth-Optimal Quantum Layout Synthesis as SAT

Anna Blume Jakobsen, Clausen, Anders B., Jaco van de Pol +1 more

Quantum circuits consist of gates applied to qubits. Current quantum hardware platforms impose connectivity restrictions on binary CX gates. Hence, Layout Synthesis is an important step to transpile quantum circuits before they can be executed. Since CX gates are noisy, it is important to reduce the CX count or CX depth of the mapped circuits. We provide a new and efficient encoding of Quantum-circuit Layout Synthesis in SAT. Previous SAT encodings focused on gate count and CX-gate count. Our encoding instead guarantees that we find mapped circuits with minimal circuit depth or minimal CX-gate depth. We use incremental SAT solving and parallel plans for an efficient encoding. This results in speedups of more than 10-100x compared to OLSQ2, which guarantees depth-optimality. But minimizing depth still takes more time than minimizing gate count with Q-Synth. We correlate the noise reduction achieved by simulating circuits after (CX)-count and (CX)-depth reduction. We find that minimizing for CX-count correlates better with reducing noise than minimizing for CX-depth. However, taking into account both CX-count and CX-depth provides the best noise reduction.

arXiv:2506.06752•Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

Optimizing Layout Synthesis for Quantum Computing Performance

Chi‐Chou Kao, Hung-Yi Lin

In recent years, the emergence of the Noisy Intermediate-Scale Quantum (NISQ) era has led to the development of a wide variety of quantum devices, marking a dynamic phase in the field of quantum computing. Despite these advancements, practical applications of quantum computers still face significant challenges, one of the most prominent being the limited connectivity between physical quantum bits (qubits). This limitation requires quantum circuits to be recompiled through layout synthesis before they can be executed on quantum devices. Layout synthesis determines the specific placement of quantum gates within the circuit on the physical hardware. When gates do not align with the connectivity constraints of the device, additional quantum gates must be inserted to remap the qubits, which can negatively affect the circuit’s efficiency and performance. To address this issue, the primary goal of this paper is to enhance the mapping process within layout synthesis, aiming to optimize both the layout and the circuit depth. Experimental results demonstrate that the proposed method effectively reduces the quantum circuit depth, outperforming other existing approaches in terms of efficiency.

Journal of Circuits Systems and Computers•Mar 6, 2025•0 citations

Optimal Layout-Aware CNOT Circuit Synthesis with Qubit Permutation

Irfansha Shaik, Jaco van de Pol

CNOT optimization plays a significant role in noise reduction for Quantum Circuits. Several heuristic and exact approaches exist for CNOT optimization. In this paper, we investigate more complicated variations of optimal synthesis by allowing qubit permutations and handling layout restrictions. We encode such problems into Planning, SAT, and QBF. We provide optimization for both CNOT gate count and circuit depth. For experimental evaluation, we consider standard T-gate optimized benchmarks and optimize CNOT sub-circuits. We show that allowing qubit permutations can further reduce up to 56% in CNOT count and 46% in circuit depth. In the case of optimally mapped circuits under layout restrictions, we observe a reduction up to 17% CNOT count and 19% CNOT depth.

arXiv:2408.04349•Frontiers in artificial intelligence and applications•Oct 16, 2024•4 citations
Layout synthesis is mapping a quantum circuit to a quantum processor. SWAP gate insertions are needed for scheduling 2-qubit gates only on connected physical qubits. With the ever-increasing number of qubits in NISQ processors, scalable layout synthesis is of utmost importance. With large optimality gaps observed in heuristic approaches, scalable exact methods are needed. While recent exact and near-optimal approaches scale to moderate circuits, large deep circuits are still out of scope. In this work, we propose a SAT encoding based on parallel plans that apply 1 SWAP and a group of CNOTs at each time step. Using domain-specific information, we maintain optimality in parallel plans while scaling to large and deep circuits. From our results, we show the scalability of our approach which significantly outperforms leading exact and near-optimal approaches (up to 100x). For the first time, we can optimally map several 8, 14, and 16 qubit circuits onto 54, 80, and 127 qubit platforms with up to 17 SWAPs. While adding optimal SWAPs, we also report near-optimal depth in our mapped circuits.
In Layout Synthesis, the logical qubits of a quantum circuit are mapped to the physical qubits of a given quantum hardware platform, taking into account the connectivity of physical qubits. This involves inserting SWAP gates before an operation is applied on distant qubits. Optimal Layout Synthesis is crucial for practical Quantum Computing on current error-prone hardware: Minimizing the number of SWAP gates directly mitigates the error rates when running quantum circuits. In recent years, several approaches have been proposed for minimizing the required SWAP insertions. The proposed exact approaches can only scale to a small number of qubits. Proving that a number of swap insertions is optimal is much harder than producing near optimal mappings. In this paper, we provide two encodings for Optimal Layout Synthesis as a classical planning problem. We use optimal classical planners to synthesize the optimal layout for a standard set of benchmarks. Our results show the scalability of our approach compared to previous leading approaches. We can optimally map circuits with 9 qubits onto a 14 qubit platform, which could not be handled before by exact methods.
In Layout Synthesis, the logical qubits of a quantum circuit are mapped to the physical qubits of a given quantum hardware platform, taking into account the connectivity of physical qubits. This involves inserting SWAP gates before an operation is applied on distant qubits. Optimal Layout Synthesis is crucial for practical Quantum Computing on current error-prone hardware: Minimizing the number of SWAP gates directly mitigates the error rates when running quantum circuits. In recent years, several approaches have been proposed for minimizing the required SWAP insertions. The proposed exact approaches can only scale to a small number of qubits. In this paper, we provide two encodings for Optimal Layout Synthesis as a classical planning problem. We use optimal classical planners to synthesize the optimal layout for a standard set of benchmarks. Our results show the scalability of our approach compared to previous leading approaches. We can optimally map circuits with 9 qubits onto a 14 qubit platform, which could not be handled before by exact methods.
Due to its effect on the success rate of a quantum circuit, quantum layout synthesis is a crucial step for circuit compilation. As such, having a layout synthesis tool that provides high solution quality is important to maximize circuit performance and fidelity for NISQ application. Previous heuristic approaches have been shown to be far from optimal when evaluated on known-optimal benchmarks. Alternatively, exact layout synthesis tools can generate optimal results with the aid of constraint solvers but generally suffer from scalability issues because of inefficient encodings and slow optimization methods. In this paper, we propose a scalable optimal layout synthesis tool that improves upon previous works, through a more succinct problem formulation as well as better encoding techniques. Additionally, we implement a depth and SWAP count optimization feature that performs iterative refinement under a fixed time budget. Experimental results show that for depth optimization, our tool can achieve a 692× speedup over the state-of-the-art optimal layout synthesis, and for SWAP optimization, we can obtain a 6,957× speedup on average. Compared to a leading heuristic-based synthesizer, for depth optimization, we can solve circuits consisting of 54 program qubits and 1726 gates within 11 hours with an 18× depth reduction and by 12× SWAP count reduction on average.
Quantum circuits consist of gates applied to qubits. Current quantum hardware platforms impose connectivity restrictions on binary CX gates. Hence, Layout Synthesis is an important step to transpile quantum circuits before they can be executed. Since CX gates are noisy, it is important to reduce the CX count or CX depth of the mapped circuits. We provide a new and efficient encoding of Quantum-circuit Layout Synthesis in SAT. Previous SAT encodings focused on gate count and CX-gate count. Our encoding instead guarantees that we find mapped circuits with minimal circuit depth or minimal CX-gate depth. We use incremental SAT solving and parallel plans for an efficient encoding. This results in speedups of more than 10-100x compared to OLSQ2, which guarantees depth-optimality. But minimizing depth still takes more time than minimizing gate count with Q-Synth. We correlate the noise reduction achieved by simulating circuits after (CX)-count and (CX)-depth reduction. We find that minimizing for CX-count correlates better with reducing noise than minimizing for CX-depth. However, taking into account both CX-count and CX-depth provides the best noise reduction.
In recent years, the emergence of the Noisy Intermediate-Scale Quantum (NISQ) era has led to the development of a wide variety of quantum devices, marking a dynamic phase in the field of quantum computing. Despite these advancements, practical applications of quantum computers still face significant challenges, one of the most prominent being the limited connectivity between physical quantum bits (qubits). This limitation requires quantum circuits to be recompiled through layout synthesis before they can be executed on quantum devices. Layout synthesis determines the specific placement of quantum gates within the circuit on the physical hardware. When gates do not align with the connectivity constraints of the device, additional quantum gates must be inserted to remap the qubits, which can negatively affect the circuit’s efficiency and performance. To address this issue, the primary goal of this paper is to enhance the mapping process within layout synthesis, aiming to optimize both the layout and the circuit depth. Experimental results demonstrate that the proposed method effectively reduces the quantum circuit depth, outperforming other existing approaches in terms of efficiency.
CNOT optimization plays a significant role in noise reduction for Quantum Circuits. Several heuristic and exact approaches exist for CNOT optimization. In this paper, we investigate more complicated variations of optimal synthesis by allowing qubit permutations and handling layout restrictions. We encode such problems into Planning, SAT, and QBF. We provide optimization for both CNOT gate count and circuit depth. For experimental evaluation, we consider standard T-gate optimized benchmarks and optimize CNOT sub-circuits. We show that allowing qubit permutations can further reduce up to 56% in CNOT count and 46% in circuit depth. In the case of optimally mapped circuits under layout restrictions, we observe a reduction up to 17% CNOT count and 19% CNOT depth.