Design Automation and Software Tools for Quantum Computing

Quantum computers have the potential to solve certain tasks that would take millenia to complete even with the fastest (conventional) supercomputer. Numerous quantum computing applications with a near-term perspective (e.g., for finance, chemistry, machine learning, optimization) and with a long-term perspective (i.e., cryptography, database search) are currently investigated. However, while impressive accomplishments can be observed in the physical realization of quantum computers, the development of automated methods and software tools that provide assistance in the design and realization of applications for those devices is at risk of not being able to keep up with this development anymore. This may lead to a situation where we might have powerful quantum computers but hardly any proper means to actually use them.

Our Work

In our group, we conduct design automation for quantum computers and develop methods and software tools dedicated to the design and realization of quantum algorithms/circuits. We see oursevles as an “interface” between the stakeholders building corresponding quantum computers and the ones using them. Our research is mainly focused on (but not limited to) the following topics (clicking on the links provide more details):

• Efficient representation and core methods: In principle, quantum states and operations are represented on a classical computer with an exponential number of complex amplitudes. We aim for a more compact representation with a dedicated type of decision diagram that exploits certain redundancies in the quantum states to gain an efficient representation to be used as basis for many design task.
• Simulation of quantum circuits: Efficient simulators are essential for the validation of future quantum computers. Furthermore, simulators are required for designing quantum algorithms even though real and sophisticated quantum computers are not available yet. Our advanced simulation technique is based on decision diagrams and significantly outperforms simulators of well-known companies like Microsoft or Intel by conducting simulations in minutes instead of weeks or month for many cases. For our work on this issue, we got awarded with a Google Faculty Award.
• Noise-aware quantum circuit simulation: Quantum circuit simulators allow simulating the execution of quantum computers on classical hardware. In doing so, they help to validate real quantum computers and support researchers in developing new quantum algorithms. Yet, real quantum computers are often affected by noise effects, which cause errors during their computation. To faithfully simulate their execution those errors have to be considered. This, however, makes a hard problem even harder. In our work, we are researching efficient approaches for simulating with consideration to errors.
• Synthesis of quantum (and reversible) circuits: Since quantum circuits are inherently reversible, their large Boolean components have to be modeled in reversible fashion - by reversible circuits. Since these circuits are completely different than classical circuits, dedicated design flows and methodologies are required. This includes tasks like making non-reversible functions reversible (i.e. embedding) as well as the actual synthesis. In fact, we have designed several approaches for synthesis of reversible circuits, several optimizations, and also recently developed a new design flow which combines embedding and synthesis (called one-pass design of reversible circuits).
• Mapping of quantum circuits to real architectures: After synthesizing a quantum circuit (i.e. a quantum algorithm), it has to be mapped to a physical quantum computer. This constitutes a non-trivial task since the real architectures require certain constraints to be satisfied. In particular, we have developed (among others) a mapping algorithm that maps quantum circuits to IBM’s QX architectures that is also integrated into IBM’s Python SDK Qiskit.
• Verification of quantum circuits: It is of utmost importance that the originally intended functionality is indeed preserved throughout all levels of abstraction when compiling a quantum circuit for execution on an actual device. This motivated methods for equivalence checking of quantum circuits. We have developed an equivalence checking methodology that is capable of efficiently verifying the results of compilation flows within seconds, whereas state-of-the-art techniques frequently time-out or require substantially more runtime.

To make our research more accessible, we provide the open-source Munich Quantum Toolkit (MQT) and our installation-free web-tool MQT DDVis that visualizes how decision diagrams can be used for design tasks such as simulation, synthesis, and verification.

Furthermore, software tools and methods for quantum computing such as those described above require practical and relevant benchmarks to empirically evaluate and compare them to the current state of the art. In order to aid researchers and developers in this task, we provide MQT Bench—a cross-level benchmark suite comprising more than 50,000 benchmark circuits ranging from 2 up to 130 qubits on four abstraction levels.

More Information

Mainstream article introducing our ERC Project “Design Automation for Quantum Computing”	Book (published by Springer) covering some of our methods
Web-based version of some of our tools (including visualization)	Website to easily access our benchmark suite MQT Bench

Selected Papers

We developed several methods and tools which are specialized for design of quantum computation. In the following, you can find a selected set of the resulting publications. A full list of papers is available.

• L. Burgholzer, R. Raymond, and R. Wille. Verifying Results of the IBM Qiskit Quantum Circuit Compilation Flow. In IEEE International Conference on Quantum Computing (QCE), 2020. PDF (see also the implementation of the equivalence checking methodology)

• S. Hillmich, I. Markov, and R. Wille. Just Like the Real Thing: Fast Weak Simulation of Quantum Computation. In Design Automation Conference (DAC), 2020. PDF (see also the implementation of the simulator).

• A. Zulehner and R. Wille. Advanced Simulation of Quantum Computations. In IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems (TCAD), 2019. PDF (see also the implementation of the simulator).

• A. Zulehner, A. Paler, and R. Wille. An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures. In IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems (TCAD), 2018. PDF (see also the implementation of the mapping algorithm).

• A. Zulehner and R. Wille. One-pass Design of Reversible Circuits: Combining Embedding and Synthesis for Reversible Logic. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems (TCAD), 2017. PDF (see also the implementation of the one-pass synthesis).

• P. Niemann, R. Wille, and R. Drechsler. Improved Synthesis of Clifford+T Quantum Functionality. In Design, Automation and Test in Europe (DATE), 2018. PDF

• A. Zulehner and R. Wille. Exploiting Coding Techniques for Logic Synthesis of Reversible Circuits. In Asia and South Pacific Design Automation Conference (ASP-DAC), 2018. PDF

• A. Zulehner and R. Wille. Taking One-to-one Mappings for Granted: Advanced Logic Design of Encoder Circuits. In Design, Automation and Test in Europe (DATE), 818-823, 2017. PDF

• A. Zulehner and R. Wille. Make It Reversible: Efficient Embedding of Non-reversible Functions. In Design, Automation and Test in Europe (DATE), 458-463, 2017. PDF

• P. Niemann, R. Wille, D. M. Miller, M. A. Thornton, and R. Drechsler. QMDDs: Efficient Quantum Function Representation and Manipulation. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems (TCAD), 35(1):86-99, 2016. DOI

• R. Wille, A. Lye, and R. Drechsler. Exact Reordering of Circuit Lines for Nearest Neighbor Quantum Architectures. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems (TCAD), 33(12):1818-1831, 2014. DOI

Awards and Accomplishments (Selection)

• ERC Consolidator Grant 2020 (for “Design Automation for Quantum Computing”)
• Third place at the IBM Quantum Challenge 2019
• Google Research Award in 2018 for our work on simulation of quantum computations
• Winner of the IBM Qiskit Developer Challenge in 2018
• Software developed by us has been integrated into tools such as IBM’s SDK Qiskit or Atos' QLM.
• Several PhD Student Awards

Contact

In case you have any problems with or questions feel free to contact us via quantum.cda@xcit.tum.de.