Philipp Niemann, Alwin Walter Zulehner, Rolf Drechsler, Robert Wille,
"Overcoming the Trade-off Between Accuracy and Compactness in Decision Diagrams for Quantum Computation"
, in IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems (TCAD), 2020

Original Titel:

Overcoming the Trade-off Between Accuracy and Compactness in Decision Diagrams for Quantum Computation

Sprache des Titels:

Englisch

Original Kurzfassung:

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 trade-off 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 work, we describe and evaluate the effects of this
trade-off which clearly motivates the need for a solution that is
perfectly accurate and compact at the same time. More precisely,
we show that the trade-off 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
trade-off between accuracy and compactness that is present in
current numerical solutions.

Sprache der Kurzfassung:

Englisch

Journal:

IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems (TCAD)