International Conference on Advanced Computing and Communications (ADCOM)

Rules for Synthesizing Quantum Boolean Circuits Using Minimized Nearest-Neighbour Templates

Amlan Chakrabarti, Susmita Sur‐Kolay

Published Dec 1, 2007• 14 citations

Abstract

Quantum Boolean circuit (QBC) synthesis issues are becoming a key area of research in the domain of quantum computing. While Minterm gate based synthesis and Reed-Muller based canonical decomposition techniques are adopted commonly, nearest neighbor synthesis technique for QBC utilizes the quantum logic gates involving only the adjacent target and control qbits for a given quantum network. Instead of Quantum Boolean circuit synthesis using (SNOT gate, we have chosen the template-based technique for synthesis of QBC. This work defines new minimization rules using nearest neighbor templates, which results in reduced number of quantum gates and circuit levels. The need of proper relative placements of the quantum gates in order to achieve the minimum gate configuration has also been discussed.

DOI: 10.1109/adcom.2007.83

Related papers

Nearest Neighbour based Synthesis of Quantum Boolean Circuits

Amlan Chakrabarti, Susmita Sur‐Kolay

Abstract—Quantum Boolean circuit synthesis issues are becoming a key area of research in the domain of quantum computing. For gate-level synthesis, minterm based and Reed-Muller canonical decomposition techniques are adopted as common approaches. Physical implementation of quantum circuits have inherent constraints and hence nearest neighbour template of input lines is gaining importance. In this work, we present a brief analysis of the various Fixed Polarity Reed Muller (FPRM) expressions for a given quantum Boolean circuit and also introduce the rules for the nearest neighbour template-based synthesis of these forms. The corresponding circuit costs are evaluated.

Engineering lettersJan 1, 200729 citations

Cost Reduction in Nearest Neighbour Based Synthesis of Quantum Boolean Circuits.

Mozammel H. A. Khan

Abstract—Quantum computer algorithms require an ‘oracle’ as an integral part. An oracle is a reversible quantum Boolean circuit, where the inputs are kept unchanged at the outputs and the functional outputs are realized along ancillary input constants (0 or 1). Recently, a nearest neighbour template based synthesis method of quantum Boolean circuits has been proposed to overcome the adjacency requirement of the input qubits of physical quantum gates. The method used SWAP gates to bring the input qubits of quantum CNOT or C 2 NOT gates adjacent. In this paper, we propose cost reduction techniques such as ancillary constant determination to reduce the number of NOT gates and variable ordering and product grouping to reduce the number of SWAP gates required in nearest neighbour template based synthesis. The proposed approach significantly reduces the quantum realization cost of the synthesized quantum Boolean circuit than that of the original nearest neighbour template based synthesis. Index Terms — Ancillary constant determination, nearest neighbour template, product grouping, quantum Boolean circuit, fixed polarity Reed-Muller expression, reversible logic, variable ordering I.

Engineering lettersJan 1, 200833 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 ResearchMar 14, 20170 citations

Quantum Circuit Simplification and Level Compaction

Dmitri A Maslov, Gerhard W. Dueck, D. Michael Miller +1 more

Quantum circuits are time-dependent diagrams describing the process of quantum computation. Usually, a quantum algorithm must be mapped into a quantum circuit. Optimal synthesis of quantum circuits is intractable, and heuristic methods must be employed. With the use of heuristics, the optimality of circuits is no longer guaranteed. In this paper, we consider a local optimization technique based on templates to simplify and reduce the depth of nonoptimal quantum circuits. We present and analyze templates in the general case and provide particular details for the circuits composed of NOT, CNOT, and controlled-sqrt-of-NOT gates. We apply templates to optimize various common circuits implementing multiple control Toffoli gates and quantum Boolean arithmetic circuits. We also show how templates can be used to compact the number of levels of a quantum circuit. The runtime of our implementation is small, whereas the reduction in the number of quantum gates and number of levels is significant.

arXiv:quant-ph/0604001IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsFeb 21, 2008252 citations

An efficient algorithm to synthesize quantum circuits and optimization

Ömercan Susam, Mustafa Altun

Quantum computers, more specifically quantum circuits, take on the eyes with their computational promises such as reversibility. In this paper, we perform synthesis and optimization of quantum circuits. In the first part, we propose a fast synthesis algorithm that implements any given reversible Boolean function with quantum gates. Instead of an exhaustive search on every given function, our algorithm creates a library of essential functions and performs sorting. As an example, to implement 4 bit circuits we only use 120 essential functions out of all 20922789888000 functions. In the second part, we optimize our circuits by using new templates. The proposed templates mainly consist of Toffoli gates with negative and positive controlling lines. These templates also show us that optimum area solutions proposed in the literature are not actually optimum; they can be improved.

IEEE International Conference on Electronics, Circuits and Systems (ICECS)Dec 1, 20142 citations

A Transformation-Based Quantum Physical Synthesis Approach for Nearest-Neighbor Architectures

Golriz Hoseinimanesh, Naser Mohammadzadeh

The physical synthesis concept for quantum circuits, the interaction between synthesis and physical design processes, was first introduced in our previous work. This concept inspires us to propose some techniques that can minimize the number of extra inserted SWAP operations required to run a circuit on a nearest-neighbor architecture. Minimizing the number of SWAP operations potentially decreases the latency and error probability of a quantum circuit. Focusing on this concept, we present a physical synthesis technique based on transformation rules to decrease the number of SWAP operations in nearest-neighbor architectures. After the qubits of a circuit are mapped onto the physical qubits provided by the target architecture, our procedure is fed by this mapping information. Our method uses the obtained placement and scheduling information to apply some transformation rules to the original netlist to decrease the number of extra SWAP gates required for running the circuit on the architecture. We follow two policies in applying a transformation rule, greedy and simulated-annealing-based policies. Simulation results show that the proposed technique decreases the average number of extra SWAP operations by about 20.6% and 24.1% based on greedy and simulated-annealing-based policies, respectively, compared with the best in the literature.

Quantum ReportsAug 15, 20212 citations