Reversible and Quantum Circuits: Optimization and Complexity Analysis

1 Introduction . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . .. . . 11.1 Book Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.1 Optimization of Quantum Circuits . . . . . . . . . . . . . . . . . . . . . . 41.1.2 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.1 Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Boolean Function Decomposition . . . . . . . . . . . . . . . . . . . . . . . . 102.2.1 Ashenhurst Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2.2 Curtis Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2.3 Bi-decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2.4 Multiplexer Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3 Exclusive-OR Sum Of Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.4 Boolean Satisfiability and SAT Modulo Theory . . . . . . . . . . . . . . . . . 142.5 Reversible Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.5.1 Reversible Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.5.2 Reversible Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.5.3 Reversible Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.6 Quantum Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.6.1 Quantum Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.6.2 Quantum Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.6.3 Quantum Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.7 Cost Metrics for Reversible and Quantum Circuits . . . . . . . . . . . . . . . 322.7.1 Quantum Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.7.2 Number of Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.7.3 Number of Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.7.4 Depth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.7.5 Nearest Neighbor Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.8 Decision Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.8.1 Binary Decision Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.8.2 Quantum Multiple-valued Decision Diagrams . . . . . . . . . . . . 383 Optimizations and Complexity Analysis on the Reversible Level . . . . . 453.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.1.1 Optimization Approaches of Reversible Circuits . . . . . . . . . . 453.1.2 Complexity of Reversible Circuits . . . . . . . . . . . . . . . . . . . . . . 513.2 Exact Quantum Cost Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.2.1 General Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.2.2 Encoding Using SMT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533.2.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . .