The research devised efficient methods for simulating 3-qubit Quantum Fourier Transform (QFT) circuits using Quick Quantum Circuit Simulation (QQCS). The hybrid methodologies suggested as a solution for efficiently simulating the circuit involve the combination of decision diagrams and property exploitation techniques. This paper incorporated two methods based on decision diagrams: the reordering trick and decision diagram approximations, template-based optimization, and linear reversible circuit synthesis for property exploitation. The proposed approaches significantly improved and optimized quantum algorithms and hardware by aiming to simulate quantum circuits accurately and quickly. Simulations using QQCS proved the effectiveness of these strategies, which were then compared to the original circuit. The results yielded valuable insights into enhancing simulation efficiency while upholding circuit accuracy.
The research devised efficient methods for simulating 3-qubit Quantum Fourier Transform (QFT) circuits using Quick Quantum Circuit Simulation (QQCS). The hybrid methodologies suggested as a solution for efficiently simulating the circuit involve the combination of decision diagrams and property exploitation techniques. This paper incorporated two methods based on decision diagrams: the reordering trick and decision diagram approximations, template-based optimization, and linear reversible circuit synthesis for property exploitation. The proposed approaches significantly improved and optimized quantum algorithms and hardware by aiming to simulate quantum circuits accurately and quickly. Simulations using QQCS proved the effectiveness of these strategies, which were then compared to the original circuit. The results yielded valuable insights into enhancing simulation efficiency while upholding circuit accuracy.
Quantum computing is a hotspot technology for its potential to accelerate specific applications by exploiting quantum parallelism. However, current physical quantum computers are limited to a relatively small scale, simulators based on conventional machines are significantly relied on to perform quantum computing research. The straightforward array-based simulators require a tremendous amount of memory that increases exponentially with respect to the number of qubits. To mitigate such computing resource concerns, decision diagram based simulators were proposed that can efficiently exploit data redundancies in quantum states and operations. In this paper, we study two classes of quantum circuits on which the state-of-the-art decision diagram based simulators failed to perform well in terms of simulation time. We also propose a simple and powerful reorder trick to boost the simulation of such quantum circuits. Preliminary evaluation results demonstrate the usefulness of the proposed trick. Especially, for the Quantum Phase Estimation circuits, the proposed trick achieved speedups up to 313.6x compared to a state-of-the-art approach that relies on an auxiliary tool to optimize simulation order.
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.
Classical simulation remains essential for the development of quantum algorithms; however, traditional matrix-based methods struggle with scalability. While the Fast Tensor Decision Diagram (FTDD) framework offers a hybrid approach by combining the strengths of Tensor Networks and Decision Diagrams (DDs) for memory-efficient simulation, its core operations are often bottlenecked by memory management structures. Our primary motivation is to address the high computational and spatial cost associated with the hash tables, as well as to simplify the complexity of the simulation workflow. This work introduces systematic, low-level optimizations to the framework. Our main contribution is the enhancement of the memory management layer for the internal tables. We implemented a node reuse mechanism and designed a controlled strategy for hash table growth. These improvements minimize the memory footprint and reduce the costly hashing overhead inherent in DD-based simulators. We performed a thorough experimental analysis using a diverse set of quantum circuits, which were characterized by well-established metrics. Experimental results demonstrate that our enhancements improve the tool's performance and scalability. Notably, these advancements enable the simulation of complex circuits, such as Quantum Fourier Transform, with hundreds of qubits, on a standard server with 2-Tb of memory.
Quantum Multiple-Valued Decision Diagrams have proven their utility in efficiently representing and manipulating reversible and quantum functions. This work, acting as a mini-review of the topic, aims to provide a comprehensive guide for implementing reversible and quantum circuit simulators using such diagrams by integrating existing methodologies into a single cohesive framework. The operation and purpose of all relevant algorithms and routines are explained, and pseudo-code schematics are also detailed for each. A proof-of-concept implementation is presented at the end, made openly available to facilitate comprehension and research in the field of decision-diagram-based simulation of Quantum Computing.
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.
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.