Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost

Abstract

Many synthesis approaches for reversible and quantum logic have been proposed so far. However, most of them generate circuits with respect to simple metrics, i.e. gate count or quantum cost. On the other hand, to physically realize reversible and quantum hardware, additional constraints exist. In this paper, we describe cost metrics beyond gate count and quantum cost that should be considered while synthesizing reversible and quantum logic for the respective target technologies. We show that the evaluation of a synthesis approach may differ if additional costs are applied. In addition, a new cost metric, namely Nearest Neighbor Cost (NNC) which is imposed by realistic physical quantum architectures, is considered in detail. We discuss how existing synthesis flows can be extended to generate optimal circuits with respect to NNC while still keeping the quantum cost small.

16 pages, 6 figures, 4 tables, International Workshop on Logic and Synthesis

References in corpus (6)

• Elementary gates for quantum computation
• Synthesis of Quantum Logic Circuits
• Techniques for the Synthesis of Reversible Toffoli Networks
• Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
• Shor's algorithm on a nearest-neighbor machine
• The simplified Toffoli gate implementation by Margolus is optimal

Cited by in corpus (6)

• Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
• Linear Nearest Neighbor Synthesis of Reversible Circuits by Graph Partitioning
• Reducing Quantum Cost in Reversible Toffoli Circuits
• Cayley graphs and analysis of quantum cost for reversible circuit synthesis
• Synthesizing Quantum Circuits for Simple Periodic Functions
• Fault Tolerant Synthesis of Reversible Circuits