Classical simulations of quantum computations are vital for the future development of this emerging technology. To this end, decision diagrams have been proposed as a complementary technique which frequently allows to tackle the inherent exponential complexity of these simulations. In the worst case, however, they still cannot escape this complexity. Additionally, while other techniques make use of all the available processing power, decision diagram-based simulation to date cannot exploit the many processing units of today’s systems. In this work, we show that both problems can be tackled together by employing a hybrid Schrödinger-Feynman scheme for the simulation. More precisely, we show that realizing such a scheme with decision diagrams is indeed possible, we discuss the resulting problems in its realization, and propose solutions how they can be handled. Experimental evaluations confirm that this significantly advances the state of the art in decision diagram-based simulation— allowing to simulate certain hard circuits within minutes that could not be simulated in a whole day thus far.
Classical simulations of quantum computations are vital for the future development of this emerging technology. To this end, decision diagrams have been proposed as a complementary technique which frequently allows to tackle the inherent exponential complexity of these simulations. In the worst case, however, they still cannot escape this complexity. Additionally, while other techniques make use of all the available processing power, decision diagram-based simulation to date cannot exploit the many processing units of today’s systems. In this work, we show that both problems can be tackled together by employing a hybrid Schrödinger-Feynman scheme for the simulation. More precisely, we show that realizing such a scheme with decision diagrams is indeed possible, we discuss the resulting problems in its realization, and propose solutions how they can be handled. Experimental evaluations confirm that this significantly advances the state of the art in decision diagram-based simulation— allowing to simulate certain hard circuits within minutes that could not be simulated in a whole day thus far.
Since quantum computers can solve important problems faster than classical computers, many resources have gone into the development of this technology in recent decades. Despite the tremendous progress that has already been made toward the development of quantum computers, they are still an emerging technology, which restricts access and reliability. Thus, research on quantum algorithms still heavily relies on quantum circuit simulators that run on classical hardware. However, simulating the execution of a quantum computer on conventional hardware is exponentially difficult, which is also the reason why quantum computing is an interesting technology in the first place. Particularly complex is noise-aware simulation of quantum computers, i.e., the consideration of noise effects that are common in today’s quantum hardware during quantum circuit simulation. In this work, we investigate the use of decision diagrams for this task. To this end, we present two distinct approaches for noise-aware quantum circuit simulation, investigate how they can be realized using decision diagrams, and implement decision diagram-based solutions for each of the presented noise-aware simulation schemes. In an extensive evaluation, we unveil potential for further improvements and also demonstrate substantial speed-ups compared to the current state of the art.
By using quantum mechanical effects, quantum computers promise significant speedups in solving problems intractable for conventional computers. However, despite recent progress they remain limited in scaling and availability---making quantum software and hardware development heavily reliant on quantum simulators running on conventional hardware. However, most of those simulators mimic perfect quantum computers and, hence, ignore the fragile nature of quantum mechanical effects which frequently yield to decoherence errors in real quantum devices. Considering those errors during the simulation is complex, but necessary in order to tailor quantum algorithms for specific devices. Thus far, most state-of-the-art simulators considering decoherence errors rely on (exponentially) large array representations. As an alternative, simulators based on decision diagrams have been shown very promising for simulation of quantum circuits in general, but have not supported decoherence errors yet. In this work, we are closing this gap. We investigate how the consideration of decoherence errors affects the simulation performance of approaches based on decision diagrams and propose advanced solutions to mitigate negative effects. Experiments confirm that this yields improvements of several orders of magnitudes compared to a naive consideration of errors.
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.
Despite the recent progress in the physical implementation of quantum computers, a significant amount of research still depends on the use of quantum circuit simulators running on classical hardware. While there are several techniques for quantum circuit simulation, many state-of-the-art simulators rely on an array-based simulation approach. However, this array-based approach has exponential memory complexity with respect to the number of simulated qubits. To address this drawback, complementary approaches based on decision diagrams have been proposed. While these approaches allow simulating circuits that could not be simulated before, they come with their own drawbacks. Unfortunately, no detailed case study has been conducted to date, which compares those complementary approaches and their respective strengths and weaknesses. In this work, we are addressing this by providing a survey on both approaches as well as a detailed case study on their respective performances.
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.
Quantum computation is a promising emerging technology which, compared to conventional computation, allows for substantial speed-ups, e.g., for integer factorization or database search. However, since physical realizations of quantum computers are in their infancy, a significant amount of research in this domain still relies on simulations of quantum computations on conventional machines. This causes a significant complexity which current state-of-the-art simulators try to tackle with a rather straight forward array-based representation and by applying massive hardware power. There also exist solutions based on decision diagrams (i.e., graph-based approaches) that try to tackle the exponential complexity by exploiting redundancies in quantum states and operations. However, these existing approaches do not fully exploit redundancies that are actually present. In this paper, we revisit the basics of quantum computation, investigate how corresponding quantum states and quantum operations can be represented even more compactly, and, eventually, simulated in a more efficient fashion. This leads to a new graph-based simulation approach which outperforms state-of-the-art simulators (array-based as well as graph-based). Experimental evaluations show that the proposed solution is capable of simulating quantum computations for more qubits than before, and in significantly less run-time (several magnitudes faster compared to previously proposed simulators). An implementation of the proposed simulator is publicly available online at http://iic.jku.at/eda/research/quantum_simulation.