IEEE International Symposium on Multiple-Valued Logic (ISMVL)

Exact Synthesis of Elementary Quantum Gate Circuits for Reversible Functions with Don't Cares

Daniel J. Grosse, Robert Wille, Gerhard W. Dueck, Rolf Drechsler

Published May 1, 2008• 47 citations

Abstract

Compact realizations of reversible logic functions are of interest in the design of quantum computers. In this paper we present an exact synthesis algorithm, based on Boolean satisfiability (SAT), that finds the minimal elementary quantum gate realization for a given reversible function. Since these gates work in terms of qubits, a multi-valued encoding is proposed. Don't care conditions appear naturally in many reversible functions. Constant inputs are often required when a function is embedded into a reversible one. The proposed algorithm takes full advantage of don't care conditions and automatically sets the constant inputs to their optimal values. The effectiveness of the algorithm is shown on a set of benchmark functions.

DOI: 10.1109/ismvl.2008.42

Related papers

Exact Toffoli Network Synthesis of Reversible Logic Using Boolean Satisfiability

Daniel J. Grosse, Xiaobo Chen, Rolf Drechsler

Compact synthesis results for reversible logic is of major interest in low-power design and quantum computing. Such reversible functions are realized as a cascade of Toffoli gates. In this paper, we present the first exact synthesis algorithm for reversible functions using generalized Toffoli gates. Our iterative algorithm formulates the synthesis problem with d Toffoli gates as a sequence of Boolean Satisfiability (SAT) instances. Such an instance is satisfiable iff there exists a network representation with d gates. Thus we can guarantee minimality. For a set of benchmarks experimental results are given.

IEEE Dallas Circuits and Systems Conference (DCAS)Oct 1, 200610 citations

Realization of Deterministic Quantum Circuits for Non-Deterministic or Incompletely Specified Quantum State Machines

Manjith Kumar, Marek A. Perkowski

Abstract In classical logic design, there are machine learning methods based on converting a set of input-output traces to non-deterministic automata that are then converted to deterministic automata and synthesized using logic gates. This approach has not yet been extended to quantum automata. In this paper, we present a method to convert a set of input-output traces to a non-deterministic automaton, which is then converted to an incompletely specified multi-output Boolean function. The existing logic synthesis approaches for designing quantum circuits are insufficient to handle incompletely specified functions. So, we present a novel algorithm to synthesize logic functions with don’t cares using permutative quantum gates. The original MMD (D.M.Miller, D. Maslov, and G.W.Dueck) algorithm minimizes only completely specified reversible functions using cascades of reversible gates. In this paper, this algorithm is modified to allow for the inclusion of don’t cares within the given function’s truth table (reversible or irreversible). The distinguishing property of our presented algorithm QAS, is that it does not add any ancilla qubits if it is not necessary. This algorithm solves the problem of synthesizing deterministic and non-deterministic quantum state machines, both completely specified and incompletely specified.

Quantum Information and ComputationDec 1, 20250 citations

Exact sat-based toffoli network synthesis

Daniel J. Grosse, Xiaobo Chen, Gerhard W. Dueck +1 more

Compact realizations of reversible logic functions are of interest in the design of quantum computers. Such reversible functions are realized as a cascade of Toffoli gates. In this paper, we present the first exact synthesis algorithm for reversible functions using generalized Toffoligates. Our iterative algorithm formulates the synthesis problem with d Toffoli gates as a sequence of Boolean Satisfiability (SAT) instances. Such an instance is satisfiable if there exists a network representation with d gates. Thus, we can guarantee minimality. In addition to fully specified reversible functions, the algorithm can be applied to incompletely specified functions. For a set of benchmarks experimental results are given.

ACM Great Lakes Symposium on VLSI (GLSVLSI)Mar 11, 200750 citations

Optimal synthesis of multiple output Boolean functions using a set of quantum gates by symbolic reachability analysis

William N. N. Hung, Xiaoyu Song B, Guowu Yang +2 more

This paper proposes an approach to optimally synthesize quantum circuits by symbolic reachability analysis, where the primary inputs and outputs are basis binary and the internal signals can be nonbinary in a multiple-valued domain. The authors present an optimal synthesis method to minimize quantum cost and some speedup methods with nonoptimal quantum cost. The methods here are applicable to small reversible functions. Unlike previous works that use permutative reversible gates, a lower level library that includes nonpermutative quantum gates is used here. The proposed approach obtains the minimum cost quantum circuits for Miller gate, half adder, and full adder, which are better than previous results. This cost is minimum for any circuit using the set of quantum gates in this paper, where the control qubit of 2-qubit gates is always basis binary. In addition, the minimum quantum cost in the same manner for Fredkin, Peres, and Toffoli gates is proven. The method can also find the best conversion from an irreversible function to a reversible circuit as a byproduct of the generality of its formulation, thus synthesizing in principle arbitrary multi-output Boolean functions with quantum gate library. This paper constitutes the first successful experience of applying formal methods and satisfiability to quantum logic synthesis.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsAug 15, 2006261 citations

Quantified synthesis of reversible logic

Robert Wille, Hoang M. Le, Gerhard W. Dueck +1 more

In the last years synthesis of reversible logic functions has emerged as an important research area. Other fields such as low-power design, optical computing and quantum computing benefit directly from achieved improvements. Recently, several approaches for exact synthesis of Toffoli networks have been proposed. They all use Boolean satisfiability to solve the underlying synthesis problem. In this paper a new exact synthesis approach based on Quantified Boolean Formula (QBF) satisfiability - a generalization of Boolean satisfiability - is presented. Besides the application of QBF solvers, we propose Binary Decision Diagrams to solve the quantified problem formulation. This allows to easily support different gate libraries during synthesis. In addition, all minimal networks are found in a single step and the best one with respect to quantum costs can be chosen. Experimental results confirm that the new technique is faster than the best previously known approach and leads to cheaper realizations in terms of quantum costs.

Design, Automation, and Test in EuropeMar 10, 200842 citations

SAT-Guided Conversion of Boolean Functions into Reversible Quantum Logic: Minimal Embedding, Exact Synthesis, and Cost-Aware Mapping

Chandan Bandyopadhyay, Saibal Majumder, Haresh Kumar Sharma

A classical Boolean specification need not be one-to-one, whereas every reversible quantum network must preserve distinctions between basis states. SAT-Embed-Q handles this mismatch by first constructing a partial reversible embedding from output-preimage multiplicities and then searching for a compatible mixed-polarity Toffoli network. We implemented two bounded satisfiability encodings, one tracking complete intermediate states and the other tracking individual line values, and evaluated both with a deterministic reference DPLL solver. On the four-line example F(a,b,c)=ab¯∨bc, the minimum-depth CNF contains 42,234 clauses in the direct encoding and 34,194 in the bit-level encoding. The smaller clause set did not translate into faster execution: the direct representation required less time in our solver. A separate exhaustive study of the target-preserving oracle class covers every single-output function of two and three inputs. Within that restricted class, allowing negative controls lowers the summed minimum target-gate count by 34.38% and 46.39%, respectively. We also examine two four-input functions from RevLib, for which fixing the input-preserving oracle structure leads to different gate counts from embedding-optimized benchmark circuits. These experiments characterize bounded synthesis and control-polarity choices for small functions; fault-tolerant resource optimization and large-network scalability remain outside their scope.

Quantum ReportsOct 26, 20260 citations