2004 · 85 citations · 20 references
ComputingComputer EngineeringComputer ScienceAlgorithmsQuantum ComputingTheory Of ComputationBoolean AlgebraLogic SynthesisQuantum CircuitsQuantum ComputationQuantum GatesElementary Quantum GatesFormal Hardware VerificationQuantum Circuit SynthesisQuantum Gate SynthesisReachability AnalysisReversible Circuit DesignReversible Quantum GatesToffoli Gate
Reversible quantum logic plays an important role in quantum computing. In this paper, we propose an approach to optimally synthesize quantum circuits by symbolic reachability analysis where the primary inputs are purely binary. we use symbolic reachability analysis, a technique most commonly used in model checking (a way of formal verification), to synthesize the optimum quantum circuits. We present an exact synthesis method with optimal quantum cost and a speedup method with non-optimal quantum cost. Both our methods guarantee the synthesizeability of all reversible circuits. Unlike previous works which use permutative reversible gates, we use a lower level library which includes non-permutative quantum gates. For the first time, problems in quantum logic synthesis have been reduced to those of multiple-valued logic synthesis thus reducing the search space and algorithm complexity. We synthesized quantum circuits for gate, half-adder, full-adder, etc. with the smallest cost.. Our approach obtains the minimum cost quantum circuits for Miller's gate, half-adder, and full-adder, which are better than previous results. In addition, we prove the minimum quantum cost (using our elementary quantum gates) for Fredkin, Peres, and Toffoli gates. Our work constitutes the first successful experience of applying satisfiability with formal methods to quantum logic synthesis.
20
<i>Quantum Computation and Quantum Information</i>
Michael A. Nielsen, Isaac L. Chuang, Lov K. Grover · American Journal of Physics · 2002 · 22.7K citations
Quantum computation and quantum information
Jim Law · ACM SIGSOFT Software Engineering Notes · 2001 · 19.2K citations
Computing, Computer Science, Physics +13
Graph-Based Algorithms for Boolean Function Manipulation
Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text
Elementary gates for quantum computation
Adriano Barenco, Charles H. Bennett, Richard Cleve et al. · Physical Review A · 1995 · 4.4K citations · Full text
Edward Fredkin, Tommaso Toffoli · International Journal of Theoretical Physics · 1982 · 1.8K citations