Reversible and Quantum Circuits

During the last decades, the number of transistors in integrated circuits has been doubled approximately every 18 months (also known as “Moore’s Law”). Even if this procedure may continue in the upcoming years, the conventional computer hardware technologies are going to reach their limits in the near future. In particular, the power dissipation is going to become crucial. While nowadays the power dissipation is particularly caused, e.g., by nonideal behavior of transistors and materials, a more fundamental limit (namely “Landauers Barrier” [69]) will be approached. Landauer stated that each time information is lost during computation, the energy is dissipated. Extrapolating the recent achievements in the development of classical CMOS technologies, this amount of power dissipation will halt further miniaturization in the near future [157].

To keep the book self-contained, this chapter briefly introduces the basics on reversible logic, quantum circuits, and other required concepts. The chapter consists of seven parts: the first section introduces the basic definitions and notations of Boolean functions while the second section reviews existing Boolean decomposition. The third and the fourth sections give an overview of exclusive sum of products and Boolean satisfiability, respectively. The fifth section provides a summary on the principles of reversible logic required later in this book. Similarly, the sixth section gives an introduction on quantum computation and quantum circuits. The later section details the different metrics used as a quality-measure of reversible and quantum realizations. Finally, decision diagrams are reviewed.

In this chapter, we aim at reducing the quantum cost and studying the complexity analysis of circuits in the reversible level. This chapter is structured as follows. Section 3.1 reviews the related work. Then, in Sects. 3.2 and3.3, we give two approaches for the optimization of reversible circuits regarding the quantum cost metric. Section 3.4 describes a study for complexity analysis of reversible circuits and the chapter is concluded in Sect. 3.5.

The common gate library for the synthesis of reversible circuits consists of mixed-polarity multiple-control Toffoli gates or single target gates. Such gates offer a convenient representation to model the functionality of a reversible circuit but are not universal for quantum operations. Many aspects, particularly those considering fault tolerance and error correction properties, cannot be considered effectively at this abstraction level. Consequently, after deriving and optimizing a reversible circuit for a given function as it is explained in the previous chapter, the next step consists of mapping the circuit into a quantum circuit. For this purpose, the following steps are usually applied: (1) Performing circuit transformation such that the circuit consists only of NCT gates. (2) Mapping each 2-control Toffoli gate to an optimum quantum circuit composed of gates from a given library. Many algorithms have been proposed to accomplish the first step, i.e., to map an MPMCT circuit to an NCT circuit. In the following section we review the different mapping strategies for MPMCT or ST based circuits. Then, in Sect. 4.2 we introduce an enhanced mapping approach for the ST based circuits. Later, in Sect. 4.3 we propose an efficient mapping methodology targeting the Clifford + T library based circuits in order to minimize their T-depth. Finally, we study the complexity of mapped circuits, i.e., reversible circuits based on the NCT gate library in Sect. 4.4.

After mapping a reversible circuit into a functionally equivalent quantum circuit, the resulting circuit is not optimal with respect to considered cost metrics due to the existing non-optimal synthesis as well as mapping approaches, particularly for large circuits. Moreover, physical developments for emerging technologies constantly lead to new constraints, e.g., the depth and the NNC. For that reason, post-mapping optimizations are applied to optimize the value of the cost metrics with respect to the used library. In particular, many existing optimization methods target the reduction of the quantum cost and the depth [83, 128] of quantum circuits. In the following section, related work is summarized. Afterwards, a depth optimization approach is given in Sect. 5.2. Then, in Sect. 5.3 an algorithm for reducing the quantum cost is explained. Finally a study of the complexity of quantum implementations is given in Sect. 5.4.

In this book several approaches have been presented to optimize quantum circuits as well as to analyze their complexity on the three major level of the design flow depicted in Fig. 6.1. The achieved contributions on each level have been described in separate chapters. Accordingly, on each level of the design flow, two approaches have been described to improve the cost of the final realization. Besides, an extensive study of the complexity of implementing a given function has been outlined.