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 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.
With the emergence of more and more applications for quantum computing, also the development of corresponding methods for design automation is receiving increasing interest. In this respect, decision diagrams provide a promising basis for many design tasks such as simulation, synthesis, verification, and more. However, users of the corresponding tools often do not have a proper background or an intuition about how these methods based on decision diagrams work and what their strengths and limits are. In an effort to make decision diagrams for quantum computing more accessible, we present a visualization tool which visualizes quantum decision diagrams and allows to explore their behavior when used in the design tasks mentioned above. The installation-free web-tool allows users to interactively learn how decision diagrams can be used in quantum computing, e.g., to (1) compactly represent quantum states and the functionality of quantum circuits, (2) to efficiently simulate quantum circuits, and (3) to verify the equivalence of two circuits. The tool is available at https://iic.jku.at/eda/research/quantum_dd/tool
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.
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 mechanical phenomena such as phase shifts, superposition, and entanglement show promise in use for computation. Suitable technologies for the modeling and design of quantum computers and other information processing techniques that exploit quantum mechanical principles are in the range of vision. Quantum algorithms that significantly speed up the process of solving several important computation problems have been proposed in the past. The most common representation of quantum mechanical phenomena are transformation matrices. However, the transformation matrices grow exponentially with the size of a quantum system and, thus, pose significant challenges for efficient representation and manipulation of quantum functionality. In order to address this problem, first approaches for the representation of quantum systems in terms of decision diagrams have been proposed. One very promising approach is given by Quantum Multiple-Valued Decision Diagrams (QMDDs) which are able to efficiently represent transformation matrices and also inherently support multiple-valued basis states offered by many physical quantum systems. However, the initial proposal of QMDDs was lacking in a formal basis and did not allow, e.g., the change of the variable order-an established core functionality in decision diagrams which is crucial for determining more compact representations. Because of this, the full potential of QMDDs or decision diagrams for quantum functionality in general has not been fully exploited yet. In this paper, we present a refined definition of QMDDs for the general quantum case. Furthermore, we provide significantly improved computational methods for their use and manipulation and show that the resulting representation satisfies important criteria for a decision diagram, i.e., compactness and canonicity. An experimental evaluation confirms the efficiency of QMDDs.
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 tradeoff 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 article, we describe and evaluate the effects of this tradeoff which clearly motivates the need for a solution that is perfectly accurate and compact at the same time. More precisely, we show that the tradeoff 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 tradeoff between accuracy and compactness that is present in current numerical solutions.
Quantum computation is a promising research field since it allows to conduct certain tasks exponentially faster than on conventional machines. As in the conventional domain, decision diagrams are heavily used in different design tasks for quantum computation like synthesis, verification, or simulation. However, unlike decision diagrams for the conventional domain, decision diagrams for quantum computation as of now suffer from a trade-off between accuracy and compactness that requires parameter fine-tuning on a case-by-case basis. In this work, we-for the first time-describe and evaluate the effects of this trade-off. Moreover, we propose an alternative approach that utilizes an algebraic representation of the occurring irrational numbers and outline how this can be incorporated in a decision diagram in order to overcome this trade-off.