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:2207.06199

Recursive Methods for Synthesizing Permutations on Limited-Connectivity Quantum Computers

Cynthia Chen, Bruno de O. Schmitt, Helena Zhang, Lev S. Bishop, Ali Javadi-Abhari

Published Jul 13, 2022• 0 citations
arXivHTMLPDF

Abstract

We describe a family of recursive methods for the synthesis of qubit permutations on quantum computers with limited qubit connectivity. Two objectives are of importance: circuit size and depth. In each case we combine a scalable heuristic with a non-scalable, yet exact, synthesis. Our algorithms are applicable to generic connectivity constraints, scale favorably, and achieve close-to-optimal performance in many cases. We demonstrate the utility of these algorithms by optimizing the compilation of Quantum Volume circuits, and to disprove an old conjecture on reversals being the hardest permutation on a path.

DOI
10.48550/arxiv.2207.06199

Related papers

Optimizing quantum circuit synthesis for permutations using recursion

Cynthia Chen, Bruno de O. Schmitt, Helena Zhang +2 more

We describe a family of recursive methods for the synthesis of qubit permutations on quantum computers with limited qubit connectivity. Two objectives are of importance: circuit size and depth. In each case we combine a scalable heuristic with a non-scalable, yet exact, synthesis.

ACM/IEEE Design Automation Conference (DAC)•Jul 10, 2022•3 citations

Tackling the Qubit Mapping Problem with Permutation-Aware Synthesis

Ji Liu, Ed Younis, Mathias Weiden +3 more

We propose a scalable, hierarchical qubit mapping and routing algorithm that harnesses the power of circuit synthesis. First, we decompose large circuits into subcircuits small enough to be directly resynthesized. For each block, we pre-synthesize them for all permutations of its input and output qubits. Following this offline step, we employ a permutation-aware, block-based generalization of the popular SABRE mapping algorithm. This mapping step stitches together blocks by choosing an input-output permutation that minimizes intrablock gate count and required inter-block communication (SWAP and bridge gates). Our approach has a twofold advantage: 1) circuit synthesis may eliminate more two-qubit gates than other optimizing compilers; 2) considering all permutations of input and output qubits eliminates communication operations transparently. In contrast, other mapping algorithms can only introduce communication operations. We show that we can produce better-quality circuits than commercial compilers: shorter by up to 68% (18% on average) fewer gates than Qiskit, up to 36% (9% on average) fewer gates than Tket. We outperform BQSkit, a permutation-unaware, synthesis-based compiler, by up to 67% (21% on average) fewer gates. We also exceed experimental optimal mappers such as OLSQ in quality (10.7% shorter circuits) and time to solution. Our scalable, heuristic approach can be seamlessly integrated into any quantum circuit compiler or optimization infrastructure, and it applies well to any qubit technology, such as superconducting and trapped ions.

arXiv:2305.02939•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•27 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

Compiling Permutations for Superconducting QPUs

Mathias Soeken, Fereshte Mozafari, Bruno de O. Schmitt +1 more

In this paper we consider the compilation of quantum state permutations into quantum gates for physical quantum computers. A sequence of generic single-target gates, which realize the input permutation, are extracted using a decomposition based reversible logic synthesis algorithm. We present a compilation algorithm that translates single-target gates into a quantum circuit composed of the elementary quantum gate sets that are supported by IBM's 5-qubit and 16-qubit, and Rigetti's 8-qubit and 19-qubit superconducting transmon QPUs. Compared to generic state-of-the-art compilation techniques, our technique improves gate volume and gate depth by up to 59% and 53%, respectively.

Design, Automation, and Test in Europe•Mar 1, 2019•15 citations

Synthesis of the Optimal 4-bit Reversible Circuits

Oleg Golubitsky, Sean M. Falconer, Maslov, Dmitri

Optimal synthesis of reversible functions is a non-trivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a huge search space (16!~2^44 functions). The output of such a search alone, counting only the space required to list Toffoli gates for every function, would require over 100 terabytes of storage. In this paper, we present an algorithm that synthesizes an optimal circuit for any 4-bit reversible specification. We employ several techniques to make the problem tractable. We report results from several experiments, including synthesis of random 4-bit permutations, optimal synthesis of all 4-bit linear reversible circuits, synthesis of existing benchmark functions, and distribution of optimal circuits. Our results have important implications for the design and optimization of quantum circuits, testing circuit synthesis heuristics, and performing experiments in the area of quantum information processing.

arXiv:1003.1914•Mar 9, 2010•0 citations

A Study of Optimal 4-Bit Reversible Toffoli Circuits and Their Synthesis

Oleg Golubitsky, Dmitri A Maslov

Optimal synthesis of reversible functions is a nontrivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a huge search space (16! ≈ 244functions). The output of such a search alone, counting only the space required to list Toffoli gates for every function, would require over 100 terabytes of storage. In this paper, we present two algorithms: one, that synthesizes an optimal circuit for any 4-bit reversible specification, and another that synthesizes all optimal implementations. We employ several techniques to make the problem tractable. We report results from several experiments, including synthesis of all optimal 4-bit permutations, synthesis of random 4-bit permutations, optimal synthesis of all 4-bit linear reversible circuits, and synthesis of existing benchmark functions; we compose a list of the hardest permutations to synthesize, and show distribution of optimal circuits. We further illustrate that our proposed approach may be extended to accommodate physical constraints via reporting LNN-optimal reversible circuits. Our results have important implications in the design and optimization of reversible and quantum circuits, testing circuit synthesis heuristics, and performing experiments in the area of quantum information processing.

arXiv:1103.2686•IEEE Transactions on Computers•Aug 3, 2011•105 citations
We describe a family of recursive methods for the synthesis of qubit permutations on quantum computers with limited qubit connectivity. Two objectives are of importance: circuit size and depth. In each case we combine a scalable heuristic with a non-scalable, yet exact, synthesis. Our algorithms are applicable to generic connectivity constraints, scale favorably, and achieve close-to-optimal performance in many cases. We demonstrate the utility of these algorithms by optimizing the compilation of Quantum Volume circuits, and to disprove an old conjecture on reversals being the hardest permutation on a path.
We propose a scalable, hierarchical qubit mapping and routing algorithm that harnesses the power of circuit synthesis. First, we decompose large circuits into subcircuits small enough to be directly resynthesized. For each block, we pre-synthesize them for all permutations of its input and output qubits. Following this offline step, we employ a permutation-aware, block-based generalization of the popular SABRE mapping algorithm. This mapping step stitches together blocks by choosing an input-output permutation that minimizes intrablock gate count and required inter-block communication (SWAP and bridge gates). Our approach has a twofold advantage: 1) circuit synthesis may eliminate more two-qubit gates than other optimizing compilers; 2) considering all permutations of input and output qubits eliminates communication operations transparently. In contrast, other mapping algorithms can only introduce communication operations. We show that we can produce better-quality circuits than commercial compilers: shorter by up to 68% (18% on average) fewer gates than Qiskit, up to 36% (9% on average) fewer gates than Tket. We outperform BQSkit, a permutation-unaware, synthesis-based compiler, by up to 67% (21% on average) fewer gates. We also exceed experimental optimal mappers such as OLSQ in quality (10.7% shorter circuits) and time to solution. Our scalable, heuristic approach can be seamlessly integrated into any quantum circuit compiler or optimization infrastructure, and it applies well to any qubit technology, such as superconducting and trapped ions.
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.
In this paper we consider the compilation of quantum state permutations into quantum gates for physical quantum computers. A sequence of generic single-target gates, which realize the input permutation, are extracted using a decomposition based reversible logic synthesis algorithm. We present a compilation algorithm that translates single-target gates into a quantum circuit composed of the elementary quantum gate sets that are supported by IBM's 5-qubit and 16-qubit, and Rigetti's 8-qubit and 19-qubit superconducting transmon QPUs. Compared to generic state-of-the-art compilation techniques, our technique improves gate volume and gate depth by up to 59% and 53%, respectively.
Optimal synthesis of reversible functions is a non-trivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a huge search space (16!~2^44 functions). The output of such a search alone, counting only the space required to list Toffoli gates for every function, would require over 100 terabytes of storage. In this paper, we present an algorithm that synthesizes an optimal circuit for any 4-bit reversible specification. We employ several techniques to make the problem tractable. We report results from several experiments, including synthesis of random 4-bit permutations, optimal synthesis of all 4-bit linear reversible circuits, synthesis of existing benchmark functions, and distribution of optimal circuits. Our results have important implications for the design and optimization of quantum circuits, testing circuit synthesis heuristics, and performing experiments in the area of quantum information processing.
Optimal synthesis of reversible functions is a nontrivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a huge search space (16! ≈ 244functions). The output of such a search alone, counting only the space required to list Toffoli gates for every function, would require over 100 terabytes of storage. In this paper, we present two algorithms: one, that synthesizes an optimal circuit for any 4-bit reversible specification, and another that synthesizes all optimal implementations. We employ several techniques to make the problem tractable. We report results from several experiments, including synthesis of all optimal 4-bit permutations, synthesis of random 4-bit permutations, optimal synthesis of all 4-bit linear reversible circuits, and synthesis of existing benchmark functions; we compose a list of the hardest permutations to synthesize, and show distribution of optimal circuits. We further illustrate that our proposed approach may be extended to accommodate physical constraints via reporting LNN-optimal reversible circuits. Our results have important implications in the design and optimization of reversible and quantum circuits, testing circuit synthesis heuristics, and performing experiments in the area of quantum information processing.