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

Quantum Information and Computation

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

Zongyuan Zhang, Zhijin Guan, Hong Zhang, Haiying Ma, Weiping Ding

Published Nov 1, 2018• 3 citations
Publisher

Abstract

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.

DOI
10.26421/qic18.13-14-2

Related papers

An Algorithm of Optimization for Linear Nearest Neighbor Quantum Circuits by Parallel Processing

Zongyuan Zhang, Zhijin Guan, Hong Zhang

In order to realize the linear nearest neighbor(LNN) of quantum circuits and reduce the quantum cost of the linear reversible quantum circuits, a method of synthesizing and optimizing linear reversible quantum circuits based on matrix multiplication is proposed. This method shows the matrix representation of linear quantum circuits by proposing the matrix representation of the CNOT gate and the SWAP gate. The rule of judging whether a two-qubit quantum circuit is in LNN state is proposed. The LNN realization by adding SWAP gates is proposed and the equivalence of two ways of adding SWAP gates is proved. The elimination rules of 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 a particular algorithm to realize the LNN, which can effectively reduce the quantum cost and improve calculation efficiency by inserting the SWAP gates on parallel computing devices. 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.

International Conference on Instrumentation and Measurement, Computer, Communication and Control (IMCCC)•Jul 1, 2018•2 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•21 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

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•58 citations

Quantum State Analysis and Optimal Logic Synthesis for Linear Nearest Neighbor Architecture

Hai Cheng Xu, Zhijin Guan, Xueyun Cheng +1 more

Real quantum computing technologies have different restrictions and constraints which need to be considered during circuit synthesis. In certain technologies, only physically adjacent qubits can interact. It is common to use a pair of SWAP gates to bring the control and target qubits of any quantum gate to adjacent lines and maintain correct circuit functionality. This paper introduces a new method to synthesize linear nearest neighbor quantum circuit on the base of the analysis of quantum state in circuit. For all 3-qubit quantum circuit, experimental results shows that our algorithm can reduce the quantum cost by approximately 30% on average compared with one recent proposed method.

DEStech Transactions on Engineering and Technology Research•Mar 14, 2017•0 citations

A Fast Optimization Algorithm for Nearest Neighbor Architecture Based on Quantum Weight

Fei Ding, Zhijing Guau, Fuji Ren

Optimization based on QC (quantum cost) for quantum circuits and the LNN (Linear Nearest Neighbor) Architecture are the bases for mapping quantum logic circuits into physical systems. The correlation between the underlying optimization and the upper layer of quantum logic design is an important issue that needs to be emphasized during the mapping process. In order to improve the efficiency and robustness for the above problems, a fast optimization algorithm for LNN architecture based on quantum weight is proposed. Based on quantum priority, a wire sequence initialization method is designed. Then the neighboring arrangement rule of the NCV gate library circuit and the optimization algorithm are given. The experimental results show that the proposed strategies can effectively reduce the QC and the number of inserted SWAP gates. The average optimization rate reaches 12.3% compared to the corresponding results.

IEEE International Conference on Cloud Computing and Intelligence Systems (CCIS)•Dec 1, 2019•2 citations
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.
In order to realize the linear nearest neighbor(LNN) of quantum circuits and reduce the quantum cost of the linear reversible quantum circuits, a method of synthesizing and optimizing linear reversible quantum circuits based on matrix multiplication is proposed. This method shows the matrix representation of linear quantum circuits by proposing the matrix representation of the CNOT gate and the SWAP gate. The rule of judging whether a two-qubit quantum circuit is in LNN state is proposed. The LNN realization by adding SWAP gates is proposed and the equivalence of two ways of adding SWAP gates is proved. The elimination rules of 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 a particular algorithm to realize the LNN, which can effectively reduce the quantum cost and improve calculation efficiency by inserting the SWAP gates on parallel computing devices. 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.
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.
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.
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.
Real quantum computing technologies have different restrictions and constraints which need to be considered during circuit synthesis. In certain technologies, only physically adjacent qubits can interact. It is common to use a pair of SWAP gates to bring the control and target qubits of any quantum gate to adjacent lines and maintain correct circuit functionality. This paper introduces a new method to synthesize linear nearest neighbor quantum circuit on the base of the analysis of quantum state in circuit. For all 3-qubit quantum circuit, experimental results shows that our algorithm can reduce the quantum cost by approximately 30% on average compared with one recent proposed method.
Optimization based on QC (quantum cost) for quantum circuits and the LNN (Linear Nearest Neighbor) Architecture are the bases for mapping quantum logic circuits into physical systems. The correlation between the underlying optimization and the upper layer of quantum logic design is an important issue that needs to be emphasized during the mapping process. In order to improve the efficiency and robustness for the above problems, a fast optimization algorithm for LNN architecture based on quantum weight is proposed. Based on quantum priority, a wire sequence initialization method is designed. Then the neighboring arrangement rule of the NCV gate library circuit and the optimization algorithm are given. The experimental results show that the proposed strategies can effectively reduce the QC and the number of inserted SWAP gates. The average optimization rate reaches 12.3% compared to the corresponding results.