Optimizing Noisy-Intermediate Scale Quantum Circuits: A Block-Based Synthesis

The current phase of quantum computing is in the Noisy Intermediate-Scale Quantum (NISQ) era. On NISQ devices, two-qubit gates such as CNOTs are much noisier than single-qubit gates, so it is essential to minimize their count. Quantum circuit synthesis is a process of decomposing an arbitrary unitary into a sequence of quantum gates, and can be used as an optimization tool to produce shorter circuits to improve overall circuit fidelity. However, the time-to-solution of synthesis grows exponentially with the number of qubits. As a result, synthesis is intractable for circuits on a large qubit scale. In this paper, we propose a hierarchical, block-by-block optimization framework, QGo, for quantum circuit optimization. Our approach allows an exponential cost optimization to scale to large circuits. QGo uses a combination of partitioning and synthesis: 1) partition the circuit into a sequence of independent circuit blocks; 2) re-generate and optimize each block using quantum synthesis; and 3) re-compose the final circuit by stitching all the blocks together. We perform our analysis and show the fidelity improvements in three different regimes: small-size circuits on real devices, medium-size circuits on noise simulations, and large-size circuits on analytical models. Using a set of NISQ benchmarks, we show that QGo can reduce the number of CNOT gates by 29.9% on average and up to 50% when compared with industrial compilers such as t|ket>. When executed on the IBM Athens system, shorter depth leads to higher circuit fidelity. We also demonstrate the scalability of our QGo technique to optimize circuits of 60+ qubits. Our technique is the first demonstration of successfully employing and scaling synthesis in the compilation toolchain for large circuits. Overall, our approach is robust for direct incorporation in production compiler toolchains.The current phase of quantum computing is in the Noisy Intermediate-Scale Quantum (NISQ) era. On NISQ devices, two-qubit gates such as CNOTs are much noisier than single-qubit gates, so it is essential to minimize their count. Quantum circuit synthesis is a process of decomposing an arbitrary unitary into a sequence of quantum gates, and can be used as an optimization tool to produce shorter circuits to improve overall circuit fidelity. However, the time-to-solution of synthesis grows exponentially with the number of qubits. As a result, synthesis is intractable for circuits on a large qubit scale. In this paper, we propose a hierarchical, block-by-block optimization framework, QGo, for quantum circuit optimization. Our approach allows an exponential cost optimization to scale to large circuits. QGo uses a combination of partitioning and synthesis: 1) partition the circuit into a sequence of independent circuit blocks; 2) re-generate and optimize each block using quantum synthesis; and 3) re-compose the final circuit by stitching all the blocks together. We perform our analysis and show the fidelity improvements in three different regimes: small-size circuits on real devices, medium-size circuits on noise simulations, and large-size circuits on analytical models. Using a set of NISQ benchmarks, we show that QGo can reduce the number of CNOT gates by 29.9% on average and up to 50% when compared with industrial compilers such as t|ket>. When executed on the IBM Athens system, shorter depth leads to higher circuit fidelity. We also demonstrate the scalability of our QGo technique to optimize circuits of 60+ qubits. Our technique is the first demonstration of successfully employing and scaling synthesis in the compilation toolchain for large circuits. Overall, our approach is robust for direct incorporation in production compiler toolchains.

arXiv:2012.09835Dec 17, 202010 citations

Reoptimization of Quantum Circuits via Hierarchical Synthesis

Xin-Chuan Wu, Marc Grau Davis, Frederic T. Chong +1 more

The current phase of quantum computing is in the Noisy Intermediate-Scale Quantum (NISQ) era. On NISQ devices, two-qubit gates such as CNOTs are much noisier than single-qubit gates, so it is essential to minimize their count. Quantum circuit synthesis is a process of decomposing an arbitrary unitary into a sequence of quantum gates, and can be used as an optimization tool to produce shorter circuits to improve overall circuit fidelity. However, the time-to-solution of synthesis grows exponentially with the number of qubits. As a result, synthesis is intractable for circuits on a large qubit scale. In this paper, we propose a hierarchical, block-by-block opti-mization framework, QGo, for quantum circuit optimization. Our approach allows an exponential cost optimization to scale to large circuits. QGo uses a combination of partitioning and synthesis: 1) partition the circuit into a sequence of independent circuit blocks; 2) re-generate and optimize each block using quantum synthesis; and 3) re-compose the final circuit by stitching all the blocks together. We perform our analysis and show the fidelity improvements in three different regimes: small-size circuits on real devices, medium-size circuits on noisy simulations, and large-size circuits on analytical models. Our technique can be applied after existing optimizations to achieve higher circuit fidelity. Using a set of NISQ benchmarks, we show that QGo can reduce the number of CNOT gates by 29.9% on average and up to 50% when compared with industrial compiler optimizations such as t|ket). When executed on the IBM Athens system, shorter depth leads to higher circuit fidelity. We also demonstrate the scalability of our QGo technique to optimize circuits of 60+ qubits, Our technique is the first demonstration of successfully employing and scaling synthesis in the compilation tool chain for large circuits. Overall, our approach is robust for direct incorporation in production compiler toolchains to further improve the circuit fidelity.The current phase of quantum computing is in the Noisy Intermediate-Scale Quantum (NISQ) era. On NISQ devices, two-qubit gates such as CNOTs are much noisier than single-qubit gates, so it is essential to minimize their count. Quantum circuit synthesis is a process of decomposing an arbitrary unitary into a sequence of quantum gates, and can be used as an optimization tool to produce shorter circuits to improve overall circuit fidelity. However, the time-to-solution of synthesis grows exponentially with the number of qubits. As a result, synthesis is intractable for circuits on a large qubit scale. In this paper, we propose a hierarchical, block-by-block opti-mization framework, QGo, for quantum circuit optimization. Our approach allows an exponential cost optimization to scale to large circuits. QGo uses a combination of partitioning and synthesis: 1) partition the circuit into a sequence of independent circuit blocks; 2) re-generate and optimize each block using quantum synthesis; and 3) re-compose the final circuit by stitching all the blocks together. We perform our analysis and show the fidelity improvements in three different regimes: small-size circuits on real devices, medium-size circuits on noisy simulations, and large-size circuits on analytical models. Our technique can be applied after existing optimizations to achieve higher circuit fidelity. Using a set of NISQ benchmarks, we show that QGo can reduce the number of CNOT gates by 29.9% on average and up to 50% when compared with industrial compiler optimizations such as t|ket). When executed on the IBM Athens system, shorter depth leads to higher circuit fidelity. We also demonstrate the scalability of our QGo technique to optimize circuits of 60+ qubits, Our technique is the first demonstration of successfully employing and scaling synthesis in the compilation tool chain for large circuits. Overall, our approach is robust for direct incorporation in production compiler toolchains to further improve the circuit fidelity.

IEEE International Conference on Rebooting Computing (ICRC)Nov 1, 202119 citations

Scalable multi-objective genetic algorithm for quantum circuit optimization

Roumaissa Ghlib, Rania Bouhadouza, Faicel Hnaien

Abstract Designing compact and efficient quantum circuits that are compatible with Noisy Intermediate-Scale Quantum (NISQ) hardware remains a central challenge in quantum computing. Most existing optimization approaches rely on fidelity-based fitness functions that require computing the full unitary matrix of the circuit. However, this quickly becomes computationally intractable beyond 10–12 qubits due to the exponential memory and time complexity $O(2^{2n})$ . In this work, we propose a scalable multi-objective genetic algorithm for quantum circuit optimization tailored to NISQ devices. Although evolutionary algorithms have demonstrated strong potential for circuit synthesis, current methods generally depend on full-unitary fidelity evaluation, which severely limits scalability. To address this bottleneck, we introduce two complementary strategies: (1) an independent block-based evaluation using graph partitioning, and (2) an overlapping sliding-window decomposition approach. Both strategies reduce computational complexity from $O(2^{2n})$ to $O(2^{2k})$ , where $k \ll n$ , making it possible to optimize circuits with more than 20 qubits in practice. Our methods are integrated into the NSGA-II multi-objective framework, enabling simultaneous optimization of fidelity, circuit depth, and gate cost, while maintaining structural compatibility with NISQ hardware–without requiring full-unitary simulation. Experimental results on benchmark circuits demonstrate high fidelity (above 0.94 for small circuits up to 8 qubits, above 0.85 for medium-scale circuits of 10–16 qubits, and above 0.80 for large-scale circuits up to 32 qubits), up to $45\%$ reduction in circuit depth, and a $10\times$ speedup compared to exact evaluation at 14 qubits.Abstract Designing compact and efficient quantum circuits that are compatible with Noisy Intermediate-Scale Quantum (NISQ) hardware remains a central challenge in quantum computing. Most existing optimization approaches rely on fidelity-based fitness functions that require computing the full unitary matrix of the circuit. However, this quickly becomes computationally intractable beyond 10–12 qubits due to the exponential memory and time complexity $$O(2^{2n})$$ . In this work, we propose a scalable multi-objective genetic algorithm for quantum circuit optimization tailored to NISQ devices. Although evolutionary algorithms have demonstrated strong potential for circuit synthesis, current methods generally depend on full-unitary fidelity evaluation, which severely limits scalability. To address this bottleneck, we introduce two complementary strategies: (1) an independent block-based evaluation using graph partitioning, and (2) an overlapping sliding-window decomposition approach. Both strategies reduce computational complexity from $$O(2^{2n})$$ to $$O(2^{2k})$$ , where $$k \ll n$$ , making it possible to optimize circuits with more than 20 qubits in practice. Our methods are integrated into the NSGA-II multi-objective framework, enabling simultaneous optimization of fidelity, circuit depth, and gate cost, while maintaining structural compatibility with NISQ hardware–without requiring full-unitary simulation. Experimental results on benchmark circuits demonstrate high fidelity (above 0.94 for small circuits up to 8 qubits, above 0.85 for medium-scale circuits of 10–16 qubits, and above 0.80 for large-scale circuits up to 32 qubits), up to $$45\%$$ reduction in circuit depth, and a $$10\times$$ speedup compared to exact evaluation at 14 qubits.

Scientific ReportsApr 18, 20260 citations

Development of a multi-technology, template-based quantum circuits compilation toolchain

Manfredi Avitabile, Giovanni Amedeo Cirillo, Mario Simoni +2 more

Abstract With noisy intermediate scale quantum computers (NISQ) becoming larger in scale and more reliable, quantum circuits are growing in size and complexity. In order to face the challenge of achieving optimal circuits, design automation approaches for improving and mapping quantum circuits on different architectures have been proposed, each one characterized by a specific optimization strategy. In this article, the use of a template-based approach for quantum circuits optimization purposes is explored, and the proposal of a modular compilation toolchain, which supports three quantum technologies (nuclear magnetic resonance, trapped ions and superconducting qubits), is presented. The toolchain tackles the task of implementing logic synthesis for single-qubit and multi-qubit gates in the compilation process and it is structured with multiple steps and modular libraries. The toolchain was tested through a benchmarking procedure, and the results for a subset of complex quantum circuits as inputs are here reported, alongside a comparison with those provided by the compilers of IBM’s Qiskit and Cambridge Quantum Computing’s $\mathrm{\left. {t|ket} \right\rangle }$ t|ket . The current toolchain prototype was crafted to be an easily expandable and reliable core for future developments, which could lead it to support even more quantum technologies and a fully fledged layout synthesis. Nonetheless, the obtained results are quite encouraging, and they prove that in certain conditions the Toolchain can be competitive in quantum circuits optimization, especially when dealing with single-qubit gates.Abstract With noisy intermediate scale quantum computers (NISQ) becoming larger in scale and more reliable, quantum circuits are growing in size and complexity. In order to face the challenge of achieving optimal circuits, design automation approaches for improving and mapping quantum circuits on different architectures have been proposed, each one characterized by a specific optimization strategy. In this article, the use of a template-based approach for quantum circuits optimization purposes is explored, and the proposal of a modular compilation toolchain, which supports three quantum technologies (nuclear magnetic resonance, trapped ions and superconducting qubits), is presented. The toolchain tackles the task of implementing logic synthesis for single-qubit and multi-qubit gates in the compilation process and it is structured with multiple steps and modular libraries. The toolchain was tested through a benchmarking procedure, and the results for a subset of complex quantum circuits as inputs are here reported, alongside a comparison with those provided by the compilers of IBM’s Qiskit and Cambridge Quantum Computing’s $$ \mathrm{\left. {t|ket} \right\rangle } $$ t|ket . The current toolchain prototype was crafted to be an easily expandable and reliable core for future developments, which could lead it to support even more quantum technologies and a fully fledged layout synthesis. Nonetheless, the obtained results are quite encouraging, and they prove that in certain conditions the Toolchain can be competitive in quantum circuits optimization, especially when dealing with single-qubit gates.

Quantum Information ProcessingNov 12, 20224 citations

Quantum Circuit Partitioning for Scalable Noise-Aware Quantum Circuit Re-Synthesis

Mohammad Walid Charrwi, Georgios Ioannou, Ed Younis +2 more

Re-synthesis techniques are utilized to optimize the quantum circuit. To enable scalable re-synthesis a divide-and-conquer approach is adopted that partitions the circuit into smaller blocks, which are optimized independently. Several algorithms have been proposed to minimize the block number while maximizing the gate count of each block. However, they vary in their performance and may not yield the highest output fidelity. We propose a reinforcement learning-based quantum circuit partitioning framework that incorporates the physical properties of the quantum hardware to maximize the output fidelity post-quantum circuit optimization. To accelerate the training, we also propose a noise injection method that enables on-the-fly optimization in the reinforcement learning environment, independent of the adopted optimization/re-synthesis method at the block level. We evaluate our approach compared to different partitioning techniques using various quantum benchmarks executed on IBM Q Hanoi quantum computer.Re-synthesis techniques are utilized to optimize the quantum circuit. To enable scalable re-synthesis a divide-and-conquer approach is adopted that partitions the circuit into smaller blocks, which are optimized independently. Several algorithms have been proposed to minimize the block number while maximizing the gate count of each block. However, they vary in their performance and may not yield the highest output fidelity. We propose a reinforcement learning-based quantum circuit partitioning framework that incorporates the physical properties of the quantum hardware to maximize the output fidelity post-quantum circuit optimization. To accelerate the training, we also propose a noise injection method that enables on-the-fly optimization in the reinforcement learning environment, independent of the adopted optimization/re-synthesis method at the block level. We evaluate our approach compared to different partitioning techniques using various quantum benchmarks executed on IBM Q Hanoi quantum computer.

IEEE International Conference on Quantum Computing and Engineering (QCE)Sep 15, 20244 citations

Quantum circuit synthesis on noisy intermediate-scale quantum devices

Shuai Yang, Guojing Tian, Jialin Zhang +1 more

In the near future of the noisy intermediate-scale quantum (NISQ) era, almost all quantum computing devices will be restricted to a specific fixed qubits connectivity architecture. Thus, the synthesis of quantum circuits with limited connectivity is urgent. We design quantum circuit synthesis algorithms for basic and essential synthesis problems, such as quantum state preparation, general unitary synthesis, and quantum isometries. For any architecture, the controlled not (cnot) count is at most 5/3 times the state-of-the-art result on complete-graph architecture. For some specific architectures, such as square-grid ones, the ratio is reduced to 1.126. The numerical simulation result is confirmatory of theoretical conclusions. Our algorithms significantly reduce by more than $50%$ additional cnot count compared to mapping algorithms. These algorithms help to implement the larger-scale algorithm in the physics device. Our results illustrate that well-designed synthesis algorithms can mitigate the problem of limited qubit connectivity in the NISQ era and may suggest the design of large-scale quantum devices.In the near future of the noisy intermediate-scale quantum (NISQ) era, almost all quantum computing devices will be restricted to a specific fixed qubits connectivity architecture. Thus, the synthesis of quantum circuits with limited connectivity is urgent. We design quantum circuit synthesis algorithms for basic and essential synthesis problems, such as quantum state preparation, general unitary synthesis, and quantum isometries. For any architecture, the controlled not (cnot) count is at most 5/3 times the state-of-the-art result on complete-graph architecture. For some specific architectures, such as square-grid ones, the ratio is reduced to 1.126. The numerical simulation result is confirmatory of theoretical conclusions. Our algorithms significantly reduce by more than $50%$ additional cnot count compared to mapping algorithms. These algorithms help to implement the larger-scale algorithm in the physics device. Our results illustrate that well-designed synthesis algorithms can mitigate the problem of limited qubit connectivity in the NISQ era and may suggest the design of large-scale quantum devices.

Physical Review AJan 2, 20247 citations

O(2^{2n})

. In this work, we propose a scalable multi-objective genetic algorithm for quantum circuit optimization tailored to NISQ devices. Although evolutionary algorithms have demonstrated strong potential for circuit synthesis, current methods generally depend on full-unitary fidelity evaluation, which severely limits scalability. To address this bottleneck, we introduce two complementary strategies: (1) an independent block-based evaluation using graph partitioning, and (2) an overlapping sliding-window decomposition approach. Both strategies reduce computational complexity from

O(2^{2n})

O(2^{2k})

, where

k \ll n

, making it possible to optimize circuits with more than 20 qubits in practice. Our methods are integrated into the NSGA-II multi-objective framework, enabling simultaneous optimization of fidelity, circuit depth, and gate cost, while maintaining structural compatibility with NISQ hardware–without requiring full-unitary simulation. Experimental results on benchmark circuits demonstrate high fidelity (above 0.94 for small circuits up to 8 qubits, above 0.85 for medium-scale circuits of 10–16 qubits, and above 0.80 for large-scale circuits up to 32 qubits), up to

45\%

reduction in circuit depth, and a

10\times

speedup compared to exact evaluation at 14 qubits.

\mathrm{\left. {t|ket} \right\rangle }

t|ket . The current toolchain prototype was crafted to be an easily expandable and reliable core for future developments, which could lead it to support even more quantum technologies and a fully fledged layout synthesis. Nonetheless, the obtained results are quite encouraging, and they prove that in certain conditions the Toolchain can be competitive in quantum circuits optimization, especially when dealing with single-qubit gates.

50%

additional cnot count compared to mapping algorithms. These algorithms help to implement the larger-scale algorithm in the physics device. Our results illustrate that well-designed synthesis algorithms can mitigate the problem of limited qubit connectivity in the NISQ era and may suggest the design of large-scale quantum devices.