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

Facta universitatis - series Electronics and Energetics

Synthesis of quantum circuits in Linear Nearest neighbor Model using Positive Davio Lattices

Marek A. Perkowski, Martin Lukáč, Dipal Shah, Michitaka Kameyama

Published Jan 1, 2011• 32 citations
Publisher

Abstract

We present a logic synthesis method based on lattices that realize quantum arrays in One-Dimensional Ion Trap technology. This means that all gates are built from 2x2 quantum primitives that are located only on neighbor qubits in a one-dimensional space (called also vector of qubits or Linear Nearest Neighbor (LNN) architecture). The Logic circuits designed by the proposed method are realized only with 3*3 Toffoli, Feynman and NOT quantum gates and the usage of the commonly used multi-input Toffoli gates is avoided. This realization method of quantum circuits is different from most of reversible circuits synthesis methods from the literature that use only high level quantum cost based on the number of quantum gates. Our synthesis approach applies to both standard and LNN quantum cost models. It leads to entirely new CAD algorithms for circuit synthesis and substantially decreases the quantum cost for LNN quantum circuits. The drawback of synthesizing circuits in the presented LNN architecture is the addition of ancilla qubits.

DOI
10.2298/fuee1101071p

Related papers

Synthesis of quantum arrays with low quantum costs from Kronecker Functional Lattice Diagrams

Dipal Shah, Marek A. Perkowski

Reversible logic has many applications such as Quantum computing, low power CMOS circuit design, Optical computing. Hence reversible logic synthesis has attracted attention especially in quantum computing community. A logic function is reversible if it is a one-to-one mapping between input and output vectors. In this paper we present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams. Unlike other contemporary algorithms for synthesis of reversible function that use n × n Toffoli gates, our method invariably synthesizes functions using only 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost. Our method adds small cost by adding extra ancilla bits. Moreover, our circuits are always (4-neighbors) regular, which is an asset when they are mapped to 2-Dimensional arrays in Ion Trap (quantum) technology.

IEEE Congress on Evolutionary Computation (CEC)•Jul 1, 2010•4 citations

Synthesis of Linear Nearest Neighbor Quantum Circuits

Md. Mazder Rahman, Gerhard W. Dueck

This paper presents models for transforming standard reversible circuits into Linear Nearest Neighbor (LNN) architecture without inserting SWAP gates. Templates to optimize the transformed LNN circuits are proposed. All minimal LNN circuits for all 3-qubit functions have been generated to serve as benchmarks to evaluate heuristic optimization algorithms. The minimal results generated are compared with optimized LNN circuits obtained from the post synthesis algorithm --- template matching with LNN templates. Experiments show that the suggested synthesis flow significantly improves the quantum cost of circuits.

arXiv:1508.05430•Aug 21, 2015•19 citations

Linear Nearest Neighbor Synthesis of Reversible Circuits by Graph Partitioning

Amlan Chakrabarti, Susmita Sur‐Kolay, Ayan Chaudhury

Linear Nearest Neighbor (LNN) synthesis in reversible circuits has emerged as an important issue in terms of technological implementation for quantum computation. The objective is to obtain a LNN architecture with minimum gate cost. As achieving optimal synthesis is a hard problem, heuristic methods have been proposed in recent literature. In this work we present a graph partitioning based approach for LNN synthesis with reduction in circuit cost. In particular, the number of SWAP gates required to convert a given gate-level quantum circuit to its equivalent LNN configuration is minimized. Our algorithm determines the reordering of indices of the qubit line(s) for both single control and multiple controlled gates. Experimental results for placing the target qubits of Multiple Controlled Toffoli (MCT) library of benchmark circuits show a significant reduction in gate count and quantum gate cost compared to those of related research works.

arXiv:1112.0564•Dec 2, 2011•48 citations

Synthesis of Quantum Arrays from Kronecker Functional Lattice Diagrams

Martin Lukáč, Dipal Shah, Marek A. Perkowski +1 more

Reversible logic is becoming more and more popular due to the fact that many novel technologies such as quantum computing, low power CMOS circuit design or quantum optical computing are becoming more and more realistic. In quantum computing, reversible computing is the main venue for the realization and design of classical functions and circuits. We present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams (KFLD). Unlike many of contemporary algorithms for synthesis of reversible functions that use n×n Toffoli gates, our method synthesizes functions using 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost of the designed circuit but adds additional ancilla bits. The resulting circuits are always regular in a 4-neighbor model and all connections are predictable. Consequently resulting circuits can be directly mapped in to a quantum device such as quantum FPGA [14]. This is a significant advantage of our method, as it allows us to design optimum circuits for a given quantum technology.

IEICE Transactions on Information and Systems•Jan 1, 2014•3 citations

Quantum Circuit Synthesis for Linear Nearest Neighbor Based on the Vector Transformation

Yu Lu, Zhijin Guan, Xueyun Cheng +1 more

In this paper, a synthesis method is proposed based on vector transformation for linear nearest neighbor quantum circuits.Its aim is to construct a linear nearest neighbor quantum circuit, and to reduce the quantum cost of the linear reversible circuit.The vector representation of the sequence of the circuit lines and qubits of quantum gate is given in this method.It realizes the nearest neighbor of the quantum circuit by moving the position of the qubits vector elements, and it does not cause confusion due to comparison and transformation of two vector elements in the circuit.The number of SWAP gates needed to make the quantum circuit nearest neighbors is given, and its correctness is proven.Compared with the current quantum circuit synthesis algorithms, the average optimization rate of the quantum cost is 39.69% for typical benchmark circuits.The algorithm can be applied to all quantum circuits of 2-qubit quantum gates, and can be used in large quantum circuits.

International Forum on Mechanical, Control and Automation (IFMCA)•Jan 1, 2017•2 citations

A method for synthesis and optimization for linear nearest neighbor quantum circuits by parallel processing

Zongyuan Zhang, Zhijin Guan, Hong Zhang +2 more

In order to realize the linear nearest neighbor{(LNN)} of the quantum circuits and reduce the quantum cost of linear reversible quantum circuits, a method for synthesizing and optimizing linear reversible quantum circuits based on matrix multiplication of the structure of the quantum circuit is proposed. This method shows the matrix representation of linear quantum circuits by multiplying matrices of different parts of the whole circuit. The LNN realization by adding the SWAP gates is proposed and the equivalence of two ways of adding the SWAP gates is proved. The elimination rules of the SWAP gates between two overlapped adjacent quantum gates in different cases are proposed, which reduce the quantum cost of quantum circuits after realizing the LNN architecture. We propose an algorithm based on parallel processing in order to effectively reduce the time consumption for large-scale quantum circuits. Experiments show that the quantum cost can be improved by 34.31\% on average and the speed-up ratio of the GPU-based algorithm can reach 4 times compared with the CPU-based algorithm. The average time optimization ratio of the benchmark large-scale circuits in RevLib processed by the parallel algorithm is {95.57\%} comparing with the serial algorithm.

Quantum Information and Computation•Nov 1, 2018•3 citations
We present a logic synthesis method based on lattices that realize quantum arrays in One-Dimensional Ion Trap technology. This means that all gates are built from 2x2 quantum primitives that are located only on neighbor qubits in a one-dimensional space (called also vector of qubits or Linear Nearest Neighbor (LNN) architecture). The Logic circuits designed by the proposed method are realized only with 3*3 Toffoli, Feynman and NOT quantum gates and the usage of the commonly used multi-input Toffoli gates is avoided. This realization method of quantum circuits is different from most of reversible circuits synthesis methods from the literature that use only high level quantum cost based on the number of quantum gates. Our synthesis approach applies to both standard and LNN quantum cost models. It leads to entirely new CAD algorithms for circuit synthesis and substantially decreases the quantum cost for LNN quantum circuits. The drawback of synthesizing circuits in the presented LNN architecture is the addition of ancilla qubits.
Reversible logic has many applications such as Quantum computing, low power CMOS circuit design, Optical computing. Hence reversible logic synthesis has attracted attention especially in quantum computing community. A logic function is reversible if it is a one-to-one mapping between input and output vectors. In this paper we present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams. Unlike other contemporary algorithms for synthesis of reversible function that use n × n Toffoli gates, our method invariably synthesizes functions using only 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost. Our method adds small cost by adding extra ancilla bits. Moreover, our circuits are always (4-neighbors) regular, which is an asset when they are mapped to 2-Dimensional arrays in Ion Trap (quantum) technology.
This paper presents models for transforming standard reversible circuits into Linear Nearest Neighbor (LNN) architecture without inserting SWAP gates. Templates to optimize the transformed LNN circuits are proposed. All minimal LNN circuits for all 3-qubit functions have been generated to serve as benchmarks to evaluate heuristic optimization algorithms. The minimal results generated are compared with optimized LNN circuits obtained from the post synthesis algorithm --- template matching with LNN templates. Experiments show that the suggested synthesis flow significantly improves the quantum cost of circuits.
Linear Nearest Neighbor (LNN) synthesis in reversible circuits has emerged as an important issue in terms of technological implementation for quantum computation. The objective is to obtain a LNN architecture with minimum gate cost. As achieving optimal synthesis is a hard problem, heuristic methods have been proposed in recent literature. In this work we present a graph partitioning based approach for LNN synthesis with reduction in circuit cost. In particular, the number of SWAP gates required to convert a given gate-level quantum circuit to its equivalent LNN configuration is minimized. Our algorithm determines the reordering of indices of the qubit line(s) for both single control and multiple controlled gates. Experimental results for placing the target qubits of Multiple Controlled Toffoli (MCT) library of benchmark circuits show a significant reduction in gate count and quantum gate cost compared to those of related research works.
Reversible logic is becoming more and more popular due to the fact that many novel technologies such as quantum computing, low power CMOS circuit design or quantum optical computing are becoming more and more realistic. In quantum computing, reversible computing is the main venue for the realization and design of classical functions and circuits. We present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams (KFLD). Unlike many of contemporary algorithms for synthesis of reversible functions that use n×n Toffoli gates, our method synthesizes functions using 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost of the designed circuit but adds additional ancilla bits. The resulting circuits are always regular in a 4-neighbor model and all connections are predictable. Consequently resulting circuits can be directly mapped in to a quantum device such as quantum FPGA [14]. This is a significant advantage of our method, as it allows us to design optimum circuits for a given quantum technology.
In this paper, a synthesis method is proposed based on vector transformation for linear nearest neighbor quantum circuits.Its aim is to construct a linear nearest neighbor quantum circuit, and to reduce the quantum cost of the linear reversible circuit.The vector representation of the sequence of the circuit lines and qubits of quantum gate is given in this method.It realizes the nearest neighbor of the quantum circuit by moving the position of the qubits vector elements, and it does not cause confusion due to comparison and transformation of two vector elements in the circuit.The number of SWAP gates needed to make the quantum circuit nearest neighbors is given, and its correctness is proven.Compared with the current quantum circuit synthesis algorithms, the average optimization rate of the quantum cost is 39.69% for typical benchmark circuits.The algorithm can be applied to all quantum circuits of 2-qubit quantum gates, and can be used in large quantum circuits.
In order to realize the linear nearest neighbor{(LNN)} of the quantum circuits and reduce the quantum cost of linear reversible quantum circuits, a method for synthesizing and optimizing linear reversible quantum circuits based on matrix multiplication of the structure of the quantum circuit is proposed. This method shows the matrix representation of linear quantum circuits by multiplying matrices of different parts of the whole circuit. The LNN realization by adding the SWAP gates is proposed and the equivalence of two ways of adding the SWAP gates is proved. The elimination rules of the SWAP gates between two overlapped adjacent quantum gates in different cases are proposed, which reduce the quantum cost of quantum circuits after realizing the LNN architecture. We propose an algorithm based on parallel processing in order to effectively reduce the time consumption for large-scale quantum circuits. Experiments show that the quantum cost can be improved by 34.31\% on average and the speed-up ratio of the GPU-based algorithm can reach 4 times compared with the CPU-based algorithm. The average time optimization ratio of the benchmark large-scale circuits in RevLib processed by the parallel algorithm is {95.57\%} comparing with the serial algorithm.