Abstract Currently, there is an ongoing “race” to build the first practically useful quantum computer that provides substantial speed-ups for certain problems compared to conventional computers. In addition to the development of such devices, this also requires the development of automated tools and methods that provide assistance in the simulation and design of corresponding applications. Otherwise, a situation might be reached where we have powerful quantum computers but hardly any proper means to actually use them. This work provides an overview of corresponding solutions for the task of quantum circuit simulation, the task of quantum circuit design, as well as corresponding mapping tasks. The covered solutions utilise expertise on efficient data structures and algorithms gained in the design of conventional circuits and systems over the last decades. While the respective descriptions are kept brief and mainly convey the general ideas, references to further readings are provided for a more detailed treatment.
Abstract Currently, there is an ongoing “race” to build the first practically useful quantum computer that provides substantial speed-ups for certain problems compared to conventional computers. In addition to the development of such devices, this also requires the development of automated tools and methods that provide assistance in the simulation and design of corresponding applications. Otherwise, a situation might be reached where we have powerful quantum computers but hardly any proper means to actually use them. This work provides an overview of corresponding solutions for the task of quantum circuit simulation, the task of quantum circuit design, as well as corresponding mapping tasks. The covered solutions utilise expertise on efficient data structures and algorithms gained in the design of conventional circuits and systems over the last decades. While the respective descriptions are kept brief and mainly convey the general ideas, references to further readings are provided for a more detailed treatment.
In the effort to develop useful quantum computers, simulating quantum machines with conventional classical computing resources is a key capability. Such simulations will always face limits, preventing the emulation of quantum computers at substantial scale; however, by pushing the envelope through optimal choices of algorithms and hardware, the value of simulator tools can be maximized. This work reviews state-of-the-art numerical simulation methods, i.e., classical algorithms that emulate quantum computer evolution under specific operations. We focus on the mainstream state-vector and tensor-network paradigms, while briefly mentioning alternative methods. Moreover, we review the diverse applications of simulation across different facets of quantum computer development, including understanding the fundamental differences between quantum and classical computations, exploring algorithmic design for quantum advantage, predicting quantum processor performance at the design stage, and efficiently characterizing fabricated devices for rapid iterations. This review complements recent surveys of current tools and implementations; here, we aim to provide readers with an essential understanding of the theoretical basis of classical simulation methods, a detailed discussion of their advantages and limitations, and an overview of the demands and challenges arising from practical use cases.
With quantum computers promising advantages even in the near-term NISQ era, there is a lively community that develops software and toolkits for the design of corresponding quantum circuits. Although the underlying problems are different, expertise from the design automation community, which developed sophisticated design solutions for the conventional realm in the past decades, can help here. In this respect, decision diagrams provide a promising foundation for tackling many design tasks such as simulation, synthesis, and verification of quantum circuits. 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 this work, we first review the concepts of how decision diagrams can be employed, e.g., for the simulation and verification of quantum circuits. Afterwards, in an effort to make decision diagrams for quantum computing more accessible, we then present a visualization tool for quantum decision diagrams, which allows users to explore the behavior of decision diagrams in the design tasks mentioned above. Finally, we present decision diagram-based tools for simulation and verification of quantum circuits using the methods discussed above as part of the open-source Munich Quantum Toolkit (MQT)—a set of tools for quantum computing developed at the Technical University of Munich and the Johannes Kepler University Linz and released under the MIT license. More information about the corresponding tools is available at https://github.com/cda-tum/ddsim . By this, we provide an introduction of the concepts and tools for potential users who would like to work with them as well as potential developers aiming to extend them.
After decades of continuous improvements and shrinking feature sizes, the development of conventional computing technologies faces enormous challenges. In particular, power dissipation in today's computer chips becomes crucial. Reversible computation is a promising alternative to these technologies, where power dissipation can be reduced or even eliminated. Furthermore, reversible logic builds the basis for quantum computation - a completely new way of processing which enables to solve certain problems exponentially faster compared to conventional methods. However, the design of reversible and quantum circuits is significantly different. Thus, new methods e.g. for synthesis, optimization, or verification are needed. This paper provides a brief introduction into reversible circuits and their respective design methods that have been proposed within the last years.
Although the concept of quantum computing has existed for decades, the technology needed to successfully implement a quantum computing system has not yet reached the level of sophistication, reliability, and scalability necessary for commercial viability until very recently. Significant progress on this front was made in the past few years, with IBM planning to create a 1000-qubit chip by the end of 2023, and Google already claiming to have achieved quantum supremacy. Other major industry players such as Intel and Microsoft have also invested significant amounts of resources into quantum computing research. Any viable computing system requires both hardware and software to work together harmoniously in order to perform useful computations. While the achievements of IBM and other companies represent a large step forward for quantum hardware, many gaps remain to be filled with respect to the corresponding software. Specifically, there is currently no clear path towards a complete process for translating quantum algorithms into physical operations that are directly executable on quantum hardware. Such a process is analogous to a compiler that translates programs written in a high-level language into executable machine instructions on a conventional digital computer, and it is necessary if quantum computers are to be harnessed to perform practically useful computations. Existing work has addressed individual components of this process, but so far no unified method for translating the whole of a quantum algorithm into executable operations has been described. I make substantial progress towards filling this gap by describing a set of high-level and low-level quantum circuit design techniques, which when taken together reduce the need of a circuit designer to be concerned with low-level details. On the high-level side, I describe an approach or strategy to designing quantum oracles for Grover's algorithm that allows it to be applied to several types of problems. This approach involves designing oracles in terms of high-level blocks such as counters, multiplexers, comparators, and arbitrary Boolean functions. The implementations of these blocks in terms of lower-level quantum gates are demonstrated in a way that makes it clear that scaled-up versions of them can be generated in a completely automated fashion. For a specific class of problems, which I call state-space path planning problems, I also introduce a paradigm for quantum oracle design that involves representing the problem in terms of individual states and moves. Problems of this sort have applications in robotics and games. Low-level techniques that I introduce
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.