RMDDS: Reed-muller decision diagram synthesis of reversible logic circuits

Chia Chun Lin, Niraj K. Jha

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


In this article, we propose a flexible and efficient reversible logic synthesizer. It exploits the complementary advantages of two methods: Reed-Muller Reversible Logic Synthesis (RMRLS) and Decision Diagram Synthesis (DDS), and is thus called Reed-Muller Decision Diagram Synthesis (RMDDS). RMRLS does not scale to a large number of qubits (i.e., quantum bits). DDS tools, even though efficient, add a large number of ancillary qubits and typically incur much higher quantum cost than necessary. RMDDS overcomes these obstacles. It is flexible in the sense that users can either optimize the number of qubits or the quantum cost in the circuit implementation. It is also efficient because the circuits can be synthesized within user-defined CPU times. This combination of flexibility and efficiency has been missing from synthesizers presented earlier. When used to synthesize reversible functions, RMDDS reduces the number of qubits by up to 79.2% (average of 54.6%) when the synthesis objective is to minimize the number of qubits and the quantum cost by up to 71.5% (average of 35.7%) when the synthesis objective is to minimize quantum cost, relative to DDS methods. For irreversible functions (which are automatically embedded in reversible functions), the corresponding best (average) reductions in the number of qubits is 42.1% (22.5%) when minimizing the number of qubits, and in quantum cost, it is 63.0% (25.9%) when minimizing quantum cost.

Original languageEnglish (US)
Article number14
JournalACM Journal on Emerging Technologies in Computing Systems
Issue number2
StatePublished - Feb 2014

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering


  • Decision diagram
  • Quantum computing
  • Reversible logic


Dive into the research topics of 'RMDDS: Reed-muller decision diagram synthesis of reversible logic circuits'. Together they form a unique fingerprint.

Cite this