Robert Wille, Professor at the Technical University of Munich and CSO at the Software Competence Center, Hagenberg, considers the classical simulation of quantum circuits
Electronic systems permeate our world today: from personal computers to smartphones, from cars to industrial machines. The groundwork for this has been laid down by engineers and scientists several decades ago who built the first electronic circuits. Over time, those circuits became smaller and more powerful – eventually leading to their ubiquitous presence in all areas of our lives. Today, those systems are made out of millions (often billions) of components which is why we need computer scientists and efficient tools to properly design them. Without dedicated programming languages, compilers, synthesis tools, verification and testing methods, as well as debuggers, the development of your next smartphone or the next artificial intelligence (AI) solution would not be possible.
Developing quantum algorithms
Quantum computers have the potential to solve many of today’s important problems that are intractable to solve with conventional computers. These include the possibility of more accurate simulation of chemical reactions for catalysts or the physiological effects of drugs, as well as the famous Shor’s algorithm to factorize number and subsequently break most of the cryptography that secures the internet today. Unleashing this power requires the development of dedicated algorithms because quantum computing operates with fundamentally different computational primitives and comes with new challenges. One such challenge is the impossibility of “peeking” into the computation itself on quantum hardware. Another one is the high cost of running experiments on physical quantum computers. Especially for early development and testing of new algorithms on a smaller scale, both challenges can be addressed with classical simulation.
Classical simulation is one of the core tasks in design automation, next to compilation and verification. While simulation is comparatively easy for conventional digital systems, the straightforward description of superposition and entanglement in quantum states scale exponentially with the number of considered quantum bits – leading to a memory complexity, which even brings today’s biggest supercomputers to its limits. For quantum operations and the consideration of noise in the simulation, the memory requirements are even higher.
Efficient simulation of quantum circuits
The simulation of quantum circuits will require prohibiting amounts of memory in the worst case scenario. Curiously, most of the real-world problems have an inherent structure in their description that we can exploit to efficiently conduct the simulation. Sophisticated data structures, such as decision diagrams and tensor networks drastically reduce the required memory in many cases by exploiting exactly the aforementioned structure in those descriptions.
Decision diagrams achieve the compaction in the description of quantum states and quantum operations by utilising redundancies in the underlying vectors and matrices, respectively. Experiments showed that, for certain quantum algorithms, this can cut the required memory by multiple orders of magnitude – including instances in which a simulation could be optimised from requiring 32 gigabytes of memory to just 50 megabytes. Figure 1 illustrates the savings on a smaller scale, still showing the potential decision diagrams have to offer.
The research teams at the Johannes Kepler University Linz, the Technical University of Munich and the Software Competence Center Hagenberg are working on new approaches that utilise decision diagrams to cover different aspects of classical quantum circuit simulation, especially to mimic physical quantum computers as faithfully as possible. An important such aspect is the consideration of noise models to accurately evaluate the possible errors that may occur in a physical quantum computer. While scientists and engineers work relentlessly on reducing the probability of errors, error-free or fault-tolerant quantum computers will not be available shortly and errors have to be considered when developing quantum algorithms. On the other hand, the very fact that physical quantum computers work probabilistically can be exploited to increase the performance of the simulation. Accepting a tiny loss in the precision of the simulation allows us to remove parts of the quantum state that have a small impact on the quantum state as a whole and the smaller the description of the quantum state, the higher the performance of the simulation.
In summary, the computational primitives in quantum computing introduce many new challenges for simulation in the context of design automation compared to classical systems, such as the exponential memory complexity. However, they also enable new opportunities to exploit for a more efficient simulation, such as the probabilistic nature of quantum computing and inherent structure in many real-world problems.
This is only the beginning
The software to achieve the results has been published and incorporated into several open-source tools available to all researchers and engineers in the field (see box on the right-hand side). While the results are promising, the corresponding evaluations and case studies also unveiled further challenges and obstacles to overcome – motivating us to continue the work towards utilising design automation for quantum computing. The final goal is to get a comprehensive software stack to aid designers in efficiently realising their quantum application. At the same time, we are aiming to build bridges between the design automation community and the quantum computing community to establish a common language and facilitate exchange between both communities. We hope to lay the foundation today, so we can avoid the design gap in the future.
Open-source software tools
The tools described in this article are publicly available in open-source at https://github.com/cda-tum/. Furthermore, a web-based graphical interface showcasing a lightweight visualisation of quantum circuit simulation with decision diagrams can be accessed at https://iic.jku.at/eda/research/quantum_dd/tool/.
Please note: This is a commercial profile
