Quantum Boolean circuit is an interdisciplinary subject between classical reversible computing and quantum computing.It is of great significance to find a synthesis method of quantum Boolean circuit. A novel hybrid synthesis method is proposed which is based on the elementary transformation of matrices. Toffoli gate set is chosen as the basis gate library.Each logic gate in the library is a unitary matrix that can be decomposed into a product of a series of elementary transformation which is referred to a transformation path.Combined with some heuristics,the circuit structure composing of Toffoli gates can be constructed from the transformation path.In the end,a 3-qubit Boolean circuit is synthesized through the new method.
Quantum Boolean circuit is an interdisciplinary subject between classical reversible computing and quantum computing.It is of great significance to find a synthesis method of quantum Boolean circuit. A novel hybrid synthesis method is proposed which is based on the elementary transformation of matrices. Toffoli gate set is chosen as the basis gate library.Each logic gate in the library is a unitary matrix that can be decomposed into a product of a series of elementary transformation which is referred to a transformation path.Combined with some heuristics,the circuit structure composing of Toffoli gates can be constructed from the transformation path.In the end,a 3-qubit Boolean circuit is synthesized through the new method.
Abstract Boolean matrices and operations on Boolean matrices have become increasingly popular in quantum computing and quantum information because they can be used to represent quantum states and the corresponding operations. In this paper, we first give a quantum circuit direct synthesis of general Boolean matrix multiplication using Toffoli gates. We assign a qubit to each element of the matrix and add Toffoli gates at the corresponding positions where the matrix elements are multiplied according to the arithmetic of matrix multiplication. For n × p dimensional matrix A multiplied by p × m dimensional matrix B, np + pm + nm qubits and at most pmn Toffoli gates are used in total. Then, an improved heuristic algorithm based on matrix Hamming distance selection of CNOT gate is proposed to synthesize the quantum circuit of a matrix, without using wire switching and SWAP gates, using only CNOT gates. The results show that our method is as good as or better than the classical synthesis. Finally, the quantum circuit of Boolean matrix multiplication with at least one invertible or full-rank matrix using only CNOT gates is given, which is divided into five cases for discussion and analysis. For n × n dimensional invertible matrix A multiplied by n × m dimensional matrix B, nm qubits and at most mn 2 CNOT gates are used in total. For n × p dimensional column full-rank matrix A multiplied by p × m dimensional matrix B, nm qubits and at most pmn CNOT gates are used in total. The results show that this method uses less quantum resources to synthesize the quantum circuit of Boolean matrix multiplication. The correctness of the quantum circuits was verified by the Aer simulator of the IBM Quantum platform.
To build a general-purpose quantum computer, it is crucial for the quantum devices to implement classical boolean logic. A straightforward realization of quantum boolean logic is to use auxiliary qubits as intermediate storage. This inefficient implementation causes a large number of auxiliary qubits to be used. In this paper, we have derived a systematic way of realizing any general m-to-n bit combinational boolean logic using elementary quantum gates. Our approach transforms the m-to-n bit classical mapping into a t-bit unitary quantum operation with minimum number of auxiliary qubits, then a variation of Toffoli gate is used as the basic building block to construct the unitary operation. Finally, each of these building blocks can be decomposed into one-bit rotation and two-bit control-U gates. The efficiency of the network is taken into consideration by formulating it as a constrained set partitioning problem.
Abstract — This paper investigates a universal approach of synthesizing arbitrary ternary logic circuits in quantum computation based on the truth table technology. It takes into account of the relationship of classical logic and quantum logic circuits. By adding inputs with constant value and garbage outputs, the classical non-reversible logic can be transformed into reversible logic. Combined with group theory, it provides an algorithm using the ternary Swap gate, ternary NOT gate and ternary Toffoli gate library. Simultaneously, the main result shows that the numbers of qutrits we use are minimal compared to other methods. We also illustrate with two examples to test our approach. Index Terms — ternary quantum computation, reversible logic, circuit synthesis, group theory I.
In the last decade, the synthesis of reversible logic circuits has become a trending topic because of its future necessity and importance. Many methods have been studied and proposed, for instance, transformation-based, search-based, cycle-based, ESOP-based and BDD-based methods. Each of them has its limitation related to time processing, ancilla and garbage line, quantum cost. This study develops an algorithm that could synthesize quantum circuits based on mixed-polarity Toffoli gate and a variant of binary decision diagram (BDD) called reduced-ordered-complemented edge-bdd (ROCBDD). It is an optimized method of BDD to reduce nodes in the representation of Boolean functions, which leads to adding more lines and quantum gates in the reversible circuit. First, the differences between synthesis using ROCBDD, the traditional BDD and others methods are introduced. Then, we define a new structure consisting of mixed-polarity Toffoli gates relied on nodes of ROCBDD. An efficient algorithm to match BDD representation to the reversible logic circuit is also mentioned. Finally, the experimental results show that our algorithm has better synthesizing costs than previous BDD-based methods.
In order to efficiently automatically construct quantum reversible logic circuits with low cost,a novel method for quantum circuit's synthesis is proposed.Through the line topology transformation and truth table permutation,it converts an n-qubit circuit synthesis problem into single quantum circuit synthesis using traditional recursive thought.Then directly generate relevant circuit.After optimization,the quantum reversible logic circuit is synthesized finally.All 3-qubit reversible logic circuits have been synthesized by this method.The average number of EGT gates is only 6.41,and the number is down to 5.22 after optimization.Experimental results show that the number of gates to construct reversible logic circuits is less than other methods.For any n-qubit binary logic function,the number of EGT gates is less than n2n-1.Meanwhile,it voids the exponential nature of the memory or run-time complexity,and is very simple to implement in classical computer.
Quantum computation has extraordinary capabilities for solving complicated problems. As quantum computations are reversible by nature, reversible circuits are important for the development of quantum computation techniques. Designing an effective and efficient method for synthesizing reversible circuits to reduce costs and stabilize circuit efficiency is crucial. The traditional synthesis methods of solving reversible circuits focus on the conversion efficiency rather than discussing the properties of the reversible function. Thus, this paper aims to propose a novel synthesis method that directly and efficiently optimizes reversible circuit synthesis with the properties of the reversible circuit. The proposed method converts the reversible function into a hypercube, allowing visual observations of the overall circuit. Two new indicators, the adjacent Hamming distance (AHD) and total cycle distance (TCD), aid in effective decision-making, generating shorter circuits. Furthermore, we use the generalized Toffoli gate set, which without requiring any additional ancilla bits and has applications in error correction and fault tolerance. The experimental results show that our method can find better solutions than traditional methods, significantly reducing the gate count, while the hypercube assists in synthesizing the reversible circuit.