Overcoming the Tradeoff between Accuracy and Compactness in Decision Diagrams for Quantum Computation

Philipp Niemann, Alwin Zulehner, Rolf Drechsler, Robert Wille

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


Quantum computation promises to solve many hard or infeasible problems substantially faster than classical solutions. The involvement of big players like Google, IBM, Intel, Rigetti, or Microsoft furthermore led to a momentum which increases the demand for automated design methods for quantum computations. In this context, decision diagrams for quantum computation provide a major pillar as they allow to efficiently represent quantum states and quantum operations which, otherwise, have to be described in terms of exponentially large state vectors and unitary matrices. However, current decision diagrams for the quantum domain suffer from a tradeoff between accuracy and compactness, since: 1) small errors that are inevitably introduced by the limited precision of floating-point arithmetic can harm the compactness (i.e., the size of the decision diagram) significantly and 2) overcompensating these errors (to increase compactness) may lead to an information loss and introduces numerical instabilities. In this article, we describe and evaluate the effects of this tradeoff which clearly motivates the need for a solution that is perfectly accurate and compact at the same time. More precisely, we show that the tradeoff indeed weakens current design automation approaches for quantum computation (possibly leading to corrupted results or infeasible run-times). To overcome this, we propose an alternative approach that utilizes an algebraic representation of the occurring complex and irrational numbers and outline how this can be incorporated in a decision diagram which is suited for quantum computation. Evaluations show that - at the cost of an overhead which is moderate in many cases - the proposed algebraic solution indeed overcomes the tradeoff between accuracy and compactness that is present in current numerical solutions.

Original languageEnglish
Article number9023381
Pages (from-to)4657-4668
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number12
StatePublished - Dec 2020
Externally publishedYes


  • Algebraic number representation
  • clifford + T
  • decision diagrams
  • quantum computing


Dive into the research topics of 'Overcoming the Tradeoff between Accuracy and Compactness in Decision Diagrams for Quantum Computation'. Together they form a unique fingerprint.

Cite this