Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2406.11959 · IEEE International Conference on Quantum Software (QSW)

Stripping Quantum Decision Diagrams of their Identity

Aaron Sander, Ioan-Albert Florea, Lukas Burgholzer, Robert Wille

Published Jul 7, 2024• 2 citations
arXivHTMLPDF

Abstract

Classical representations of quantum states and operations as vectors and matrices are plagued by an exponential growth in memory and runtime requirements for increasing system sizes. Based on their use in classical computing, an alternative data structure known as Decision Diagrams (DDs) has been proposed, which, in many cases, provides both a more compact representation and more efficient computation. In the classical realm, decades of research have been conducted on DDs and numerous variations tailored for specific applications exist. However, DDs for quantum computing are just in their infancy and there is still room for tailoring them to this new technology. In particular, existing representations of DDs require extending all operations in a quantum circuit to the full system size through extension by nodes representing identity matrices. In this work, we make an important step forward for quantum DDs by stripping these identity structures from quantum operations. This significantly reduces the number of nodes required to represent them as well as eases the pressure on key building blocks of their implementation. As a result, we obtain a structure that is more natural for quantum computing and significantly speeds up computations—with a runtime improvement of up to 70 × compared to the state-of-the-art.

DOI
10.1109/qsw62656.2024.00032

Related papers

Approximating Decision Diagrams for Quantum Circuit Simulation

Stefan Hillmich, Alwin Zulehner, Richard Kueng +2 more

Quantum computers promise to solve important problems faster than conventional computers ever could. Underneath is a fundamentally different computational primitive that introduces new challenges for the development of software tools that aid designers of corresponding quantum algorithms. The different computational primitives render classical simulation of quantum circuits particularly challenging. While the logic simulation of conventional circuits is comparatively simple with linear complexity with respect to the number of gates, quantum circuit simulation has to deal with the exponential memory requirements to represent quantum states on non-quantum hardware with respect to the number of qubits. Decision Diagrams (DDs) address this challenge through exploitation of redundancies in matrices and vectors to provide significantly more compact representations in many cases. Moreover, the probabilistic nature of quantum computations enables another angle to tackle the complexity: Quantum algorithms are resistant to some degree against small inaccuracies in the quantum state as these only lead to small changes in the outcome probabilities. We propose to exploit this resistance against (small) errors to gain even more compact decision diagrams. In this work, we investigate the potential of approximation in quantum circuit simulation in detail. To this end, we first present four dedicated schemes that exploit the error resistance and efficiently approximate quantum states represented by decision diagrams. Subsequently, we propose two simulation strategies that utilize those approximations schemes in order to improve the efficiency of DD-based quantum circuit simulation, while, at the same time, allowing the user to control the resulting degradation in accuracy. We empirically show that the proposed approximation schemes reduce the size of decision diagrams substantially and also analytically prove the effect of multiple approximations on the attained accuracy. Eventually, this enables speed-ups of the resulting approximate quantum circuit simulation of up to several orders of magnitudes—again, while controlling the fidelity of the result.

ACM Transactions on Quantum Computing•Apr 25, 2022•14 citations

Towards Hamiltonian Simulation with Decision Diagrams

Aaron Sander, Lukas Burgholzer, Robert Wille

This paper proposes a novel approach to Hamiltonian simulation using Decision Diagrams (DDs), which are an exact representation based on exploiting redundancies in representations of quantum states and operations. While the simulation of Hamiltonians has been studied extensively, scaling these simulations to larger or more complex systems is often challenging and may require approximations or new simulation methods altogether. DDs offer such an alternative that has not yet been applied to Hamiltonian simulation. In this work, we investigate the behavior of DDs for this task. To this end, we review the basics of DDs such as their construction and present how the relevant operations for Hamiltonian simulation are implemented in this data structure-leading to the first DD-based Hamiltonian simulation approach. Based on several series of evaluations and comparisons, we then discuss insights about the performance of this complementary approach. Overall, these studies show that DDs indeed may offer a promising new data structure which, for certain examples, can provide orders of magnitudes of improvement compared to the state-of-the-art, yet also comes with its own, fundamentally different, limitations.

arXiv:2305.02337•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•8 citations

How to Efficiently Handle Complex Values? Implementing Decision Diagrams for Quantum Computing

Alwin Zulehner, Stefan Hillmich, Robert Wille

Quantum computing promises substantial speedups by exploiting quantum mechanical phenomena such as superposition and entanglement. Corresponding design methods require efficient means of representation and manipulation of quantum functionality. In the classical domain, decision diagrams have been successfully employed as a powerful alternative to straightforward means such as truth tables. This motivated extensive research on whether decision diagrams provide similar potential in the quantum domain-resulting in new types of decision diagrams capable of substantially reducing the complexity of representing quantum states and functionality. From an implementation perspective, many concepts and techniques from the classical domain can be re-used in order to implement decision diagrams packages for the quantum realm. However, new problems-namely how to efficiently handle complex numbers-arise. In this work, we propose a solution to overcome these problems. Experimental evaluations confirm that this yields improvements of orders of magnitude in the runtime needed to create and to utilize these decision diagrams. The resulting implementation is publicly available as a quantum DD package at http://iic.jku.at/eda/research/quantum_dd.

arXiv:1911.12691•Nov 1, 2019•75 citations

As Accurate as Needed, as Efficient as Possible: Approximations in DD-based Quantum Circuit Simulation

Stefan Hillmich, Richard Kueng, Igor L. Markov +1 more

Quantum computers promise to solve important problems faster than conventional computers. However, unleashing this power has been challenging. In particular, design automation runs into (1) the probabilistic nature of quantum computation and (2) exponential requirements for computational resources on non-quantum hardware. In quantum circuit simulation, Decision Diagrams (DDs) have previously shown to reduce the required memory in many important cases by exploiting redundancies in the quantum state. In this paper, we show that this reduction can be amplified by exploiting the probabilistic nature of quantum computers to achieve even more compact representations. Specifically, we propose two new DD-based simulation strategies that approximate the quantum states to attain more compact representations, while, at the same time, allowing the user to control the resulting degradation in accuracy. We also analytically prove the effect of multiple approximations on the attained accuracy and empirically show that the resulting simulation scheme enables speed-ups up to several orders of magnitudes.

arXiv:2012.05615•Design, Automation, and Test in Europe•Feb 1, 2021•17 citations

Mixed-Dimensional Quantum Circuit Simulation with Decision Diagrams

Kevin Mato, Stefan Hillmich, Robert Wille

Quantum computers promise to solve several categories of problems faster than classical computers ever could. Current research mostly focuses on qubits, i.e., systems where the unit of information can assume only two levels. However, the underlying physics of most (if not all) of the technological platforms supports more than two levels, commonly referred to as qudits. Performing computations with qudits increases the overall complexity while, at the same time, reducing the number of operations and providing a lower error rate. Furthermore, qudits with different number of levels can be mixed in one system to ease the experimental control and keep representations as compact as possible. Exploiting these capabilities requires dedicated software support to tackle the increased complexity in an automated and efficient fashion. In this paper, we present a qudit simulator that handles mixed-dimensional systems based on Decision Diagrams (DDs). More precisely, we discuss the type of decision diagram introduced as underlying data structure as well as the resulting implementation. Experimental evaluations demonstrate that the proposed solution is capable of efficiently simulating mixed-dimensional quantum circuits, with specific use cases including more than 100 qudits in one circuit. The source code of the simulator is available via github.com/cda-tdum/MiSiM under the MIT license.

arXiv:2308.12332•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•2 citations

Parallelizing quantum simulation with decision diagrams

Shaowen Li, Yusuke Kimura, Hiroyuki Sato +2 more

Recent technological advancements show promise in leveraging quantum mechanical phenomena for computation. This brings substantial speed-ups to problems that are once considered to be intractable in the classical world. However, the physical realization of quantum computers is still far away from us, and a majority of research work is done using quantum simulators running on classical computers. Classical computers face a critical obstacle in simulating quantum algorithms. Quantum states reside in a Hilbert space whose size grows exponentially to the number of subsystems, i.e., qubits. As a result, the straightforward statevector approach does not scale due to the exponential growth of the memory requirement. Decision diagrams have gained attention in recent years for representing quantum states and operations in quantum simulations. The main advantage of this approach is its ability to exploit redundancy. However, mainstream quantum simulators still rely on statevectors or tensor networks. We consider the absence of decision diagrams due to the lack of parallelization strategies. This work explores several strategies for parallelizing decision diagram operations, specifically for quantum simulations. We propose optimal parallelization strategies. Based on the experiment results, our parallelization strategy achieves a 2-3 times faster simulation of Grover’s algorithm and random circuits than the state-of-the-art single-thread DD-based simulator DDSIM.

arXiv:2312.01570•IEEE International Conference on Quantum Software (QSW)•Jul 1, 2023•5 citations
Classical representations of quantum states and operations as vectors and matrices are plagued by an exponential growth in memory and runtime requirements for increasing system sizes. Based on their use in classical computing, an alternative data structure known as Decision Diagrams (DDs) has been proposed, which, in many cases, provides both a more compact representation and more efficient computation. In the classical realm, decades of research have been conducted on DDs and numerous variations tailored for specific applications exist. However, DDs for quantum computing are just in their infancy and there is still room for tailoring them to this new technology. In particular, existing representations of DDs require extending all operations in a quantum circuit to the full system size through extension by nodes representing identity matrices. In this work, we make an important step forward for quantum DDs by stripping these identity structures from quantum operations. This significantly reduces the number of nodes required to represent them as well as eases the pressure on key building blocks of their implementation. As a result, we obtain a structure that is more natural for quantum computing and significantly speeds up computations—with a runtime improvement of up to 70 × compared to the state-of-the-art.
Quantum computers promise to solve important problems faster than conventional computers ever could. Underneath is a fundamentally different computational primitive that introduces new challenges for the development of software tools that aid designers of corresponding quantum algorithms. The different computational primitives render classical simulation of quantum circuits particularly challenging. While the logic simulation of conventional circuits is comparatively simple with linear complexity with respect to the number of gates, quantum circuit simulation has to deal with the exponential memory requirements to represent quantum states on non-quantum hardware with respect to the number of qubits. Decision Diagrams (DDs) address this challenge through exploitation of redundancies in matrices and vectors to provide significantly more compact representations in many cases. Moreover, the probabilistic nature of quantum computations enables another angle to tackle the complexity: Quantum algorithms are resistant to some degree against small inaccuracies in the quantum state as these only lead to small changes in the outcome probabilities. We propose to exploit this resistance against (small) errors to gain even more compact decision diagrams. In this work, we investigate the potential of approximation in quantum circuit simulation in detail. To this end, we first present four dedicated schemes that exploit the error resistance and efficiently approximate quantum states represented by decision diagrams. Subsequently, we propose two simulation strategies that utilize those approximations schemes in order to improve the efficiency of DD-based quantum circuit simulation, while, at the same time, allowing the user to control the resulting degradation in accuracy. We empirically show that the proposed approximation schemes reduce the size of decision diagrams substantially and also analytically prove the effect of multiple approximations on the attained accuracy. Eventually, this enables speed-ups of the resulting approximate quantum circuit simulation of up to several orders of magnitudes—again, while controlling the fidelity of the result.
This paper proposes a novel approach to Hamiltonian simulation using Decision Diagrams (DDs), which are an exact representation based on exploiting redundancies in representations of quantum states and operations. While the simulation of Hamiltonians has been studied extensively, scaling these simulations to larger or more complex systems is often challenging and may require approximations or new simulation methods altogether. DDs offer such an alternative that has not yet been applied to Hamiltonian simulation. In this work, we investigate the behavior of DDs for this task. To this end, we review the basics of DDs such as their construction and present how the relevant operations for Hamiltonian simulation are implemented in this data structure-leading to the first DD-based Hamiltonian simulation approach. Based on several series of evaluations and comparisons, we then discuss insights about the performance of this complementary approach. Overall, these studies show that DDs indeed may offer a promising new data structure which, for certain examples, can provide orders of magnitudes of improvement compared to the state-of-the-art, yet also comes with its own, fundamentally different, limitations.
Quantum computing promises substantial speedups by exploiting quantum mechanical phenomena such as superposition and entanglement. Corresponding design methods require efficient means of representation and manipulation of quantum functionality. In the classical domain, decision diagrams have been successfully employed as a powerful alternative to straightforward means such as truth tables. This motivated extensive research on whether decision diagrams provide similar potential in the quantum domain-resulting in new types of decision diagrams capable of substantially reducing the complexity of representing quantum states and functionality. From an implementation perspective, many concepts and techniques from the classical domain can be re-used in order to implement decision diagrams packages for the quantum realm. However, new problems-namely how to efficiently handle complex numbers-arise. In this work, we propose a solution to overcome these problems. Experimental evaluations confirm that this yields improvements of orders of magnitude in the runtime needed to create and to utilize these decision diagrams. The resulting implementation is publicly available as a quantum DD package at http://iic.jku.at/eda/research/quantum_dd.
Quantum computers promise to solve important problems faster than conventional computers. However, unleashing this power has been challenging. In particular, design automation runs into (1) the probabilistic nature of quantum computation and (2) exponential requirements for computational resources on non-quantum hardware. In quantum circuit simulation, Decision Diagrams (DDs) have previously shown to reduce the required memory in many important cases by exploiting redundancies in the quantum state. In this paper, we show that this reduction can be amplified by exploiting the probabilistic nature of quantum computers to achieve even more compact representations. Specifically, we propose two new DD-based simulation strategies that approximate the quantum states to attain more compact representations, while, at the same time, allowing the user to control the resulting degradation in accuracy. We also analytically prove the effect of multiple approximations on the attained accuracy and empirically show that the resulting simulation scheme enables speed-ups up to several orders of magnitudes.
Quantum computers promise to solve several categories of problems faster than classical computers ever could. Current research mostly focuses on qubits, i.e., systems where the unit of information can assume only two levels. However, the underlying physics of most (if not all) of the technological platforms supports more than two levels, commonly referred to as qudits. Performing computations with qudits increases the overall complexity while, at the same time, reducing the number of operations and providing a lower error rate. Furthermore, qudits with different number of levels can be mixed in one system to ease the experimental control and keep representations as compact as possible. Exploiting these capabilities requires dedicated software support to tackle the increased complexity in an automated and efficient fashion. In this paper, we present a qudit simulator that handles mixed-dimensional systems based on Decision Diagrams (DDs). More precisely, we discuss the type of decision diagram introduced as underlying data structure as well as the resulting implementation. Experimental evaluations demonstrate that the proposed solution is capable of efficiently simulating mixed-dimensional quantum circuits, with specific use cases including more than 100 qudits in one circuit. The source code of the simulator is available via github.com/cda-tdum/MiSiM under the MIT license.
Recent technological advancements show promise in leveraging quantum mechanical phenomena for computation. This brings substantial speed-ups to problems that are once considered to be intractable in the classical world. However, the physical realization of quantum computers is still far away from us, and a majority of research work is done using quantum simulators running on classical computers. Classical computers face a critical obstacle in simulating quantum algorithms. Quantum states reside in a Hilbert space whose size grows exponentially to the number of subsystems, i.e., qubits. As a result, the straightforward statevector approach does not scale due to the exponential growth of the memory requirement. Decision diagrams have gained attention in recent years for representing quantum states and operations in quantum simulations. The main advantage of this approach is its ability to exploit redundancy. However, mainstream quantum simulators still rely on statevectors or tensor networks. We consider the absence of decision diagrams due to the lack of parallelization strategies. This work explores several strategies for parallelizing decision diagram operations, specifically for quantum simulations. We propose optimal parallelization strategies. Based on the experiment results, our parallelization strategy achieves a 2-3 times faster simulation of Grover’s algorithm and random circuits than the state-of-the-art single-thread DD-based simulator DDSIM.