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

Engineering letters

Nearest Neighbour based Synthesis of Quantum Boolean Circuits

Amlan Chakrabarti, Susmita Sur‐Kolay

Published Jan 1, 2007• 29 citations
OpenAlex

Abstract

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.

Related papers

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

Amlan Chakrabarti, Susmita Sur‐Kolay

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.

International Conference on Advanced Computing and Communications (ADCOM)•Dec 1, 2007•14 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 letters•Jan 1, 2008•33 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.04826•Physica Scripta•Nov 18, 2024•4 citations

A Quantum Logic Circuit For Generating Fixed-Polarity Reed-Muller Coefficients

Mozammel H. A. Khan

Logic function representation using fixed-polarity Reed-Muller (FPRM) expression has manifold advantages over classical SOP expression. Moreover, FPRM expression is a very useful representation for logic function realization using quantum logic circuits. In this paper, we present a quantum logic circuit for generating FPRM coefficients for a given polarity vector from the truth vector of the function

International Conference on Electrical and Computer Engineering (ICECE)•Dec 1, 2006•0 citations

Representation of Boolean quantum circuits as reed–Muller expansions

Ahmed Younes, Julian F. Miller

In this paper we show that there is a direct correspondence between Boolean quantum operations and certain forms of classical (non-quantum) logic known as Reed–Muller expansions. This allows us to readily convert Boolean circuits into their quantum equivalents. A direct result of this is that the problem of synthesis and optimization of Boolean quantum circuits can be tackled within the field of Reed–Muller logic.

International Journal of Electronics•Jul 1, 2004•37 citations

Representation of Boolean Quantum Circuits as Reed-Muller Expansions

Ahmed Younes, Julian Francis Miller

In this paper we show that there is a direct correspondence between quantum Boolean operations and certain forms of classical (non-quantum) logic known as Reed-Muller expansions. This allows us to readily convert Boolean circuits into their quantum equivalents. A direct result of this is that the problem of synthesis and optimization of quantum Boolean logic can be tackled within the field of Reed-Muller logic.

arXiv:quant-ph/0305134•May 22, 2003•0 citations
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.
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.
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.
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.