IEEE International Conference on Nanotechnology (IEEE-NANO)

The shortest path method for quantum Boolean circuits construction

Chin-Yung Lu, Shiou-An Wang

Published Aug 1, 2013• 2 citations

Abstract

At present, only the exhaustive synthesis algorithm can find all the optimal quantum Boolean circuits. It is more difficult to synthesize a more complicated quantum Boolean circuit. In this paper, we use the method of circuit bipartition to partition a more complicated quantum Boolean circuit into simpler circuits in order to reduce the difficulty of the more complicated quantum Boolean circuit synthesis. And find these partitioned quantum Boolean circuits by searched the database of quantum Boolean circuits according the method of the shortest path in the circuit. Finally, combine these partitioned circuits to become the more complicated quantum Boolean circuit. This approach can significantly reduce the synthesis complexity of a more complicated quantum Boolean circuit. We can see that the results are very close to the optimal circuits according to the experimental results of all the 3-variable reversible functions.

DOI: 10.1109/nano.2013.6721055

Related papers

An efficient method for improving the performance of quantum boolean circuit synthesis algorithms

Shiou-An Wang, Chin-Yung Lu

So far there are no synthesis algorithms that can find all the optimal quantum boolean circuits except an exhaustive algorithm. In this paper, we propose a method based on the divide and conquer approach which can significantly improve the performance of the existing synthesis algorithms to synthesize quantum boolean circuits. A quantum boolean circuit is first divided into two subcircuits. The subcircuit with fewer gates will input all possible combinations of m gates excluding those with the same function specification. The other subcircuit can be synthesized by using the existing algorithm. The two subcircuits are combined and then we can choose the most simplified quantum boolean circuit. According to the experimental results of all the 3-variable functions, we can see that the performance of the existing algorithms can be significantly improved by using our method. Therefore the synthesized quantum boolean circuits are much more simplified than previous results.

International Conference on Multimedia Technology (ICMT)Jul 1, 20110 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

Qubits Reversible Logic Circuits Synthesis Based on Bisection Method

Dong Wang

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.

Dianzi xuebaoJan 1, 20120 citations

A novel quantum Boolean circuit synthesis method using matrix elementary transformations

Guangjun Xie

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.

Chinese Journal of Quantum ElectronicsJan 1, 20110 citations

A Novel Hypercube-Based Heuristic for Quantum Boolean Circuit Synthesis

Yu-Chi Jiang, Kuo-Chun Tseng, Cheng-Yen Hua +3 more

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.

IEEE Journal on Emerging and Selected Topics in Circuits and SystemsAug 29, 20229 citations

Fast Algorithms for 4-qubit Reversible Logic Circuits Synthesis

Xiling Xue

Synthesis of quantum reversible logic circuits means to automatically construct desired quantum reversible logic circuit with minimal quantum cost.We present a novel and efficient algorithm which can construct almost all optimal 4-qubit reversible logic circuits with various types of gates and minimum length cost based on constructing the shortest coding and the specific topological compression, whose lossless compression ratios of the space of n-qubit circuits is near2×n!.We firstly have created all 3120218828 optimal 4-qubit circuits whose length is less than 9 for the Controlled-Not gate,NOT gate and Toffoli gate library,and our method can achieve 16 steps through cascading created circuits.Our algorithm can not only synthesizes all the 4-qubit benchmark circuits,but also runs extremely fast.

Dianzi xuebaoJan 1, 20085 citations