Synopsis
1 Introduction . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . .. . . 1
1.1 Book Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Optimization of Quantum Circuits . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7
2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1 Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Boolean Function Decomposition . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Ashenhurst Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 Curtis Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.3 Bi-decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.4 Multiplexer Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Exclusive-OR Sum Of Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Boolean Satisfiability and SAT Modulo Theory . . . . . . . . . . . . . . . . . 14
2.5 Reversible Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5.1 Reversible Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.5.2 Reversible Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5.3 Reversible Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.6 Quantum Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6.1 Quantum Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6.2 Quantum Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6.3 Quantum Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.7 Cost Metrics for Reversible and Quantum Circuits . . . . . . . . . . . . . . . 32
2.7.1 Quantum Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7.2 Number of Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.7.3 Number of Lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.7.4 Depth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.7.5 Nearest Neighbor Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.8 Decision Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.8.1 Binary Decision Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.8.2 Quantum Multiple-valued Decision Diagrams . . . . . . . . . . . . 38
3 Optimizations and Complexity Analysis on the Reversible Level . . . . . 45
3.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.1 Optimization Approaches of Reversible Circuits . . . . . . . . . . 45
3.1.2 Complexity of Reversible Circuits . . . . . . . . . . . . . . . . . . . . . . 51
3.2 Exact Quantum Cost Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.2.1 General Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2.2 Encoding Using SMT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . .
Les informations fournies dans la section « Synopsis » peuvent faire référence à une autre édition de ce titre.
