Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.02673 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918114046771200 |
|---|---|
| author | Brand, Sebastiaan Quist, Arend-Jan van Dijk, Richard M. K. Laarman, Alfons |
| author_facet | Brand, Sebastiaan Quist, Arend-Jan van Dijk, Richard M. K. Laarman, Alfons |
| contents | Decision diagrams (DDs) are a powerful data structure that is used to tackle the state-space explosion problem, not only for discrete systems, but for probabilistic and quantum systems as well. While many of the DDs used in the probabilistic and quantum domains make use of floating-point numbers, this is not without challenges. Floating-point computations are subject to small rounding errors, which can affect both the correctness of the result and the effectiveness of the DD's compression. In this paper, we investigate the numerical stability, i.e. the robustness of an algorithm to small numerical errors, of matrix-vector multiplication with multi-terminal binary decision diagrams (MTBDDs). Matrix-vector multiplication is of particular interest because it is the function that computes successor states for both probabilistic and quantum systems. We prove that the MTBDD matrix-vector multiplication algorithm can be made numerically stable under certain conditions, although in many practical implementations of MTBDDs these conditions are not met. Additionally, we provide a case study of the numerical errors in the simulation of quantum circuits, which shows that the extent of numerical errors in practice varies greatly between instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02673 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Numerical Errors in Quantitative System Analysis With Decision Diagrams Brand, Sebastiaan Quist, Arend-Jan van Dijk, Richard M. K. Laarman, Alfons Computational Engineering, Finance, and Science Numerical Analysis Quantum Physics Decision diagrams (DDs) are a powerful data structure that is used to tackle the state-space explosion problem, not only for discrete systems, but for probabilistic and quantum systems as well. While many of the DDs used in the probabilistic and quantum domains make use of floating-point numbers, this is not without challenges. Floating-point computations are subject to small rounding errors, which can affect both the correctness of the result and the effectiveness of the DD's compression. In this paper, we investigate the numerical stability, i.e. the robustness of an algorithm to small numerical errors, of matrix-vector multiplication with multi-terminal binary decision diagrams (MTBDDs). Matrix-vector multiplication is of particular interest because it is the function that computes successor states for both probabilistic and quantum systems. We prove that the MTBDD matrix-vector multiplication algorithm can be made numerically stable under certain conditions, although in many practical implementations of MTBDDs these conditions are not met. Additionally, we provide a case study of the numerical errors in the simulation of quantum circuits, which shows that the extent of numerical errors in practice varies greatly between instances. |
| title | Numerical Errors in Quantitative System Analysis With Decision Diagrams |
| topic | Computational Engineering, Finance, and Science Numerical Analysis Quantum Physics |
| url | https://arxiv.org/abs/2508.02673 |