Journal of Circuits Systems and Computers

Rotation-Based Design and Synthesis of Quantum Circuits

Mariam Zomorodi Moghadam, Keivan Navi

Published Jul 25, 2016• 9 citations

Abstract

In this paper, a new synthesis method for Boolean irreversible functions has been proposed which is based on rotation quantum operators. The primary motivation is that the implementation of these operators is commonly available in quantum technologies. We introduce an approach for synthesizing Boolean irreversible functions in quantum logic which is based on quantum rotation and CNOT operators and uses a prespecified fixed design where by changing the rotation angles a new functionality can be achieved. So this design can be viewed as a programmable array of rotation gates. If reduction in quantum cost is desired, after this step the optimization approach may be applied to reduce the number of gates by using some rules, which leads to a reduction of up to 48% in the quantum cost after optimization compared to the original nonoptimized design obtained from the synthesis method. The paper also introduces efficient designs with rotation operators for some important gates in the quantum circuit libraries. Our main contribution is introducing a novel and low complexity approach for synthesizing irreversible functions using elementary rotation operators with a regular fixed design. Also having as many functions as desired with the same inputs, the execution time just increases by one for each additional function and the circuit width is increased by one for each additional function. It is proved that our approach can always be applied to each Boolean function. We show the correctness of our approach and make an upper bound of the quantum cost of the circuit.

DOI: 10.1142/s0218126616501528

Related papers

On the controlled-NOT complexity of controlled-NOT–phase circuits

Matthew Amy, Parsiad Azimzadeh, Michele Mosca

Abstract We study the problem of CNOT -optimal quantum circuit synthesis over gate sets consisting of CNOT and Z -basis rotations of arbitrary angles. We show that the circuit-polynomial correspondence relates such circuits to Fourier expansions of pseudo-Boolean functions, and that for certain classes of functions this expansion uniquely determines the minimum CNOT cost of an implementation. As a corollary we prove that CNOT minimization over CNOT and phase gates is at least as hard as synthesizing a CNOT -optimal circuit computing a set of parities of its inputs. We then show that this problem is NP-complete for two restricted cases where all CNOT gates are required to have the same target, and where the circuit inputs are encoded in a larger state space. The latter case has applications to CNOT optimization over more general Clifford+ T circuits. We further present an efficient heuristic algorithm for synthesizing circuits over CNOT and Z -basis rotations with small CNOT cost. Our experiments show a 23% reduction of CNOT gates on average across a suite of Clifford+ T benchmark circuits, with a maximum reduction of 43%.

arXiv:1712.01859Quantum Science and TechnologyAug 8, 201883 citations

A novel optimization method for reversible logic circuit minimization

Matthew A. Morrison, Nagarajan Ranganathan

Programmable reversible logic is emerging as a prospective logic design style for implementation in modern nanotechnology and quantum computing with minimal impact on circuit heat generation. Recent advances in reversible logic using and quantum computer algorithms allow for improved computer architecture and arithmetic logic unit designs. We present an optimization method for reversible logic synthesis based on the Integrated Qubit (IQ) library. This method works in conjunction with existing methods to further improve quantum cost and delay of a synthesized reversible logic circuit. This algorithm runs in O(N) time, and reduces the quantum cost of synthesized circuit by up to 45 percent. In addition, the process of replacing the gates in the synthesized circuits with IQ gates uses a locally optimal technique whose major benefits include reduction of cost as well as delay.

IEEE Computer Society Annual Symposium on VLSIAug 1, 201314 citations

Efficient Algorithm for Synthesis of Optimal NCV 3-Qubit Reversible Circuits Using New Quantum Logic Gate Library

Xiao Fang-ying

Owing to the exponential nature of the memory or run-time complexity,many existing methods can only synthesize 3-qubit logic circuits using quantum logic gate library,however,a few can optimally synthesize 3-qubit logic circuits for quantum NOT,CNOT,Controlled-V and Controlled-V+(NCV)gates,the key approach reduces the NCV quantum circuit synthesis problem to four-valued logic synthesis.This paper proposes using NCV gates to create a new quantum logic gate library,which is exactly the same as NCV gate library in the synthesis of all optimal 3-qubit circuits,thus it also reduces the four-valued logic synthesis to easily solved two-valued logic synthesis.We present a 3-qubit efficient synthesis algorithms based on perfect hash function,which can quickly construct all optimal 3-qubit circuits——the average speed that synthesizes circuits with minimum cost is nearly 127 times faster than that of the best result of Maslov 2007.

Dianzi xuebaoJan 1, 20132 citations

Universal programmable quantum circuit schemes to emulate an operator

Ammar Daskin, Ananth Y. Grama, Giorgos Kollias +1 more

Unlike fixed designs, programmable circuit designs support an infinite number of operators. The functionality of a programmable circuit can be altered by simply changing the angle values of the rotation gates in the circuit. Here, we present a new quantum circuit design technique resulting in two general programmable circuit schemes. The circuit schemes can be used to simulate any given operator by setting the angle values in the circuit. This provides a fixed circuit design whose angles are determined from the elements of the given matrix-which can be non-unitary-in an efficient way. We also give both the classical and quantum complexity analysis for these circuits and show that the circuits require a few classical computations. For the electronic structure simulation on a quantum computer, one has to perform the following steps: prepare the initial wave function of the system; present the evolution operator U = e(-iHt) for a given atomic and molecular Hamiltonian H in terms of quantum gates array and apply the phase estimation algorithm to find the energy eigenvalues. Thus, in the circuit model of quantum computing for quantum chemistry, a crucial step is presenting the evolution operator for the atomic and molecular Hamiltonians in terms of quantum gate arrays. Since the presented circuit designs are independent from the matrix decomposition techniques and the global optimization processes used to find quantum circuits for a given operator, high accuracy simulations can be done for the unitary propagators of molecular Hamiltonians on quantum computers. As an example, we show how to build the circuit design for the hydrogen molecule.

arXiv:1204.3600The Journal of Chemical PhysicsDec 21, 201230 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 SystemsJan 1, 20143 citations

Multi-strategy based quantum cost reduction of quantum boolean circuits

Taghreed Ahmed, Ahmed Younes, Islam Elkabani

Abstract The construction of quantum computers is based on the synthesis of low-cost quantum circuits. The quantum circuit of any Boolean function expressed in a Positive Polarity Reed-Muller (PPRM) expansion can be synthesized using Multiple-Control Toffoli (MCT) gates. This paper proposes two algorithms to construct a quantum circuit for any Boolean function expressed in a PPRM expansion. The Boolean function can be expressed with various algebraic forms, so there are different quantum circuits can be synthesized for the Boolean function based on its algebraic form. The proposed algorithms aim to map the MCT gates into the NCV gates for any quantum circuit by generating a simple algebraic form for the Boolean function. The first algorithm generates a special algebraic form for any Boolean function by rearrangement of terms of the Boolean function according to a predefined degree of term d term , then synthesizes the corresponding quantum circuit. The second algorithm applies the decomposition methods to decompose MCT circuit into its elementary gates followed by applying a set of simplification rules to simplify and optimize the synthesized quantum circuit. The proposed algorithms achieve a reduction in the quantum cost of synthesized quantum circuits when compared with relevant work in the literature. The proposed algorithms synthesize quantum circuits that can applied on IBM quantum computer.

arXiv:2407.04826Physica ScriptaNov 18, 20244 citations