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•19 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•48 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 Novel Heuristic Method for Linear Nearest Neighbour Realization of Reversible Circuits

Anirban Bhattacharjee, Chandan Bandyopadhyay, Hafizur Rahaman

With the advancement of technological footprints, high-end computation techniques, like quantum computation, have made significant progress in the design industry. Although quantum computation has proved itself as the next-generation computing paradigm, it is facing several design challenges, and one such design issue is in the form of the Nearest Neighbour (NN)t. This much-talked NN property demands the qubits in operating quantum gates to be adjacent, and a circuit should satisfy this NN property to be eligible for implementation. Considering the importance of NN enforcement in implementing circuits, we introduce a synthesis approach for the efficient transformation of reversible circuits to equivalent LNN representations. Our main focus in this work is to minimize the use of SWAP gates in designing NN-satisfied MCT-based reversible circuits. Towards transforming input circuits to LNN architecture, we have exploited a template matching scheme followed by two-qubit reordering policies, global and local, to improve the NN designs and reduce SWAP utilization. In finding the global solution, here we have used a dynamic programming algorithm where the initial order of qubit lines gets changed, while a heuristic-based SWAP placement function is used for finding a local qubit order sequence. The proposed synthesis workflow has been tested over an extensive set of benchmark functions, and comparison with the reported design approaches showed a substantial reduction in cost parameters.

IETE Journal of Research•Feb 8, 2022•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.
With the advancement of technological footprints, high-end computation techniques, like quantum computation, have made significant progress in the design industry. Although quantum computation has proved itself as the next-generation computing paradigm, it is facing several design challenges, and one such design issue is in the form of the Nearest Neighbour (NN)t. This much-talked NN property demands the qubits in operating quantum gates to be adjacent, and a circuit should satisfy this NN property to be eligible for implementation. Considering the importance of NN enforcement in implementing circuits, we introduce a synthesis approach for the efficient transformation of reversible circuits to equivalent LNN representations. Our main focus in this work is to minimize the use of SWAP gates in designing NN-satisfied MCT-based reversible circuits. Towards transforming input circuits to LNN architecture, we have exploited a template matching scheme followed by two-qubit reordering policies, global and local, to improve the NN designs and reduce SWAP utilization. In finding the global solution, here we have used a dynamic programming algorithm where the initial order of qubit lines gets changed, while a heuristic-based SWAP placement function is used for finding a local qubit order sequence. The proposed synthesis workflow has been tested over an extensive set of benchmark functions, and comparison with the reported design approaches showed a substantial reduction in cost parameters.