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

International Forum on Mechanical, Control and Automation (IFMCA)

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

Yu Lu, Zhijin Guan, Xueyun Cheng, Keren Yu

Published Jan 1, 2017• 2 citations
Publisher

Abstract

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.

DOI
10.2991/ifmca-16.2017.13

Related papers

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

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

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 circuits in Linear Nearest neighbor Model using Positive Davio Lattices

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

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.

Facta universitatis - series Electronics and Energetics•Jan 1, 2011•32 citations
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.
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.
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.
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.
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.