Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Synthesis of quantum circuits vs. synthesis of classical reversible circuits
De Vos A., De Baerdemacker S., Van Rentergem Y., Morgan&Claypool Publishers, 2018. 125 pp.  Type: Book (978-1-681733-81-4)
Date Reviewed: Sep 30 2019

Quantum computing is gaining momentum these days with the innovation of practical quantum computers. Therefore, a synthesis mechanism for more complex logic machines using quantum logic gates is of immense importance. In contrast, reversible computing is an elusive topic for idealistic circuits that could be optimally energy efficient as per the second law of thermodynamics, and initially borrowed from the physical systems domain. Reversible computers could be highly effective for optimization, cryptography, signal processing, reversible debugging, quantum computation, and last but not least as per the pure theoretical development of reversible Turing machines.

Reversible computing is made possible by using additional outputs along with the desired ones. The additional outputs ensure that one-to-one mapping (that is, an injective relationship) is present between input and output. The one-to-one relationship ensures that it is possible to go back to the input state from only the output state. However, it also complicates the design process, as the possible number of functions increases exponentially. The number of functions is important, as they define the search space during the synthesis phase for search-based algorithms.

This book, however, takes a heuristic-based approach to synthesis and employs a group-theory-based mathematical approach. It is shown that the approach is able to find almost optimal logic circuits and hence holds great significance for quantum and reversible logic synthesis. On the flip side, some reviews [1] report that heuristic-based approaches still lag behind more established (transformation or search-based) approaches.

Chapter 1 is a concise summary of the foundations for logic design and synthesis from a mathematical point of view. It quickly touches on the different functional representations for classical circuits using permutation groups and their decomposition. It also briefs readers on matrix groups, subgroups, and the representation of quantum logic using matrices.

The synthesis of classical reversible circuits is then presented in chapter 2. It is a robust technique, as the solution is designed using pure mathematics. It also establishes a smooth transition from reversible to quantum computing using complex variables instead of Boolean ones. The authors present three different techniques: a primal matrix decomposition, a dual matrix decomposition, and a refined matrix decomposition. The refined approach needs only a linear number of gates in terms of number of inputs and is therefore almost optimally efficient.

Chapter 3 provides the transitional foundation from classical to quantum computing. The controlled NOT gates are replaced by controlled NEGATOR gates and controlled PHASOR gates. These are subsequently utilized in chapter 4 for quantum circuit synthesis using primal and dual matrix decompositions, analogous to the classical synthesis of chapter 2. Both methods are claimed to be optimally efficient, as they need a number of gates equal to the square of all possible input combinations.

The universality of primal decomposition is further verified in chapter 5, where the binary primal permutation decomposition is established as a special case of the primal unitary decomposition of chapter 4. On the other hand, universality for dual decomposition cannot be established. The authors give much attention to classifying the algorithms using group theories and generating a hierarchical group diagram mentioning the generalization-specialization of the circuits.

This is a good read for students and researchers of reversible and quantum computing. As computer architecture is bound to change in the coming decade or so, this work has the potential to become the foundation for next-generation computing systems.

Reviewer:  Mohammed Ziaur Rahman Review #: CR146710 (1912-0410)
1) Saeedi, M.; Markov, I. Synthesis and optimization of reversible circuits—a survey. ACM Computing Surveys 45, (2013), Article No. 21.
Bookmark and Share
  Editor Recommended
Processor Architectures (C.1 )
Information Theory (H.1.1 ... )
Would you recommend this review?
Other reviews under "Processor Architectures": Date
Traleika Glacier
Cavé V., Clédat R., Griffin P., More A., Seshasayee B., Borkar S., Chatterjee S., Dunning D., Fryman J.  Parallel Computing 64 33-49, 2017. Type: Article
Dec 4 2017
Understanding co-running behaviors on integrated CPU/GPU architectures
Zhang F., Zhai J., He B., Zhang S., Chen W.  IEEE Transactions on Parallel and Distributed Systems 28(3): 905-918, 2017. Type: Article
Aug 8 2017
Dynamic coalescing for 16-bit instructions
Krishnaswamy A., Gupta R.  ACM Transactions on Embedded Computing Systems 4(1): 3-37, 2005. Type: Article
Aug 15 2006

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2020 ThinkLoud, Inc.
Terms of Use
| Privacy Policy