Reversible and Quantum Circuits: Optimization and Complexity Analysis

ISBN-13: 9783319319353 / Angielski / Twarda / 2016 / 186 str.

Nabila Abdessaied; Rolf Drechsler

Opis

This bookpresents a new optimization flow for quantum circuits realization. Then, new mapping approaches to decompose reversible circuits to quantumcircuits using different quantum libraries are described. Finally, optimizationtechniques to reduce the quantum cost or the delay are applied to the resultingquantum circuits.

Spis treści

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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52