Decision Diagrams for Quantum Computation

The current momentum of accomplishments in quantum computation yields a steadily increasing demand for methods that allow for the efficient representation and manipulation of corresponding circuits. While state vectors and unitary matrices provide an established means, they inherently suffer from their exponential size (with respect to the number of qubits). Decision diagrams for quantum computation provide a promising alternative to them. On this page, we briefly summarize our work in this direction and provide links to our current implementation as well as applications.

Description

A detailed description of decision diagrams for quantum computation co-developed by our group is available through the following papers:

For the representation of unitary matrices and state vectors (with a particular focus on simulation and measurement):
A. Zulehner and R. Wille. Advanced Simulation of Quantum Computations. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems (TCAD), 2019. PDF
For the representation and manipulation of unitary matrices (including proof of canonicity, multi-qubit systems, etc):
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
A detailed description of the implementation of this decision diagram package is available through the following paper (with a special focus on the representation of complex numbers):
A. Zulehner, S. Hillmich and R. Wille. How to Efficiently Handle Complex Values? Implementing Decision Diagrams for Quantum Computing. The IEEE/ACM International Conference on Computer-Aided Design (ICCAD). 2019 PDF

Implementation

An implementation of the concepts described in these papers is available on GitHub.

Note that this package can also be used as a black box, i.e. as a pure interface to conduct quantum operations and with no need of understanding the internal working described in the papers above. In case you have any problems with or questions about the package, feel free to contact us.

If you use the DD package for your research, we will be thankful if you refer to it by citing the following publication:

@inproceedings{zulehner2019package,
    title={How to Efficiently Handle Complex Values? Implementing Decision Diagrams for Quantum Computing},
    author={Zulehner, Alwin and Hillmich, Stefan and Wille, Robert},
    booktitle={{IEEE/ACM} International Conference on Computer-Aided Design},
    year={2019}
}

Applications

We have used these decision diagrams for several design tasks and/or applications. In the following, we provide a brief list of some selected work showcasing the applicability with respect to

Simulation of Quantum Circuits

A. Zulehner and R. Wille. Advanced Simulation of Quantum Computations. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems (TCAD), 2018. PDF
See also the corresponding webpage (including a link to an implementation).

Noise-Aware Quantum Circuit Simulation

T. Grurl, J. Fuß, and R. Wille. Considering Decoherence Errors in the Simulation of Quantum Circuits Using Decision Diagrams. In International Conference on Computer Aided Design (ICCAD), 2020. PDF
See also the corresponding webpage.

Synthesis of Reversible Circuits

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 page on one-pass design (including a link to an implementation).
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 is available.

Synthesis of Quantum Circuits

P. Niemann, R. Wille, and R. Drechsler. Improved Synthesis of Clifford+T Quantum Functionality. In Design, Automation and Test in Europe (DATE), 2018. PDF
P. Niemann, R. Wille, and R. Drechsler. Efficient Synthesis of Quantum Circuits Implementing Clifford Group Operations. In Asia and South Pacific Design Automation Conference (ASP-DAC), pages 483-488, 2014. PDF
P. Niemann, R. Datta, and R. Wille. Logic Synthesis for Quantum State Generation. In International Symposium on Multiple-Valued Logic (ISMVL), 2016. PDF

Verification of Reversible and Quantum Circuits

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
L. Burgholzer and R. Wille. Advanced Equivalence Checking for Quantum Circuits. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems (TCAD), 2021. PDF
See also the corresponding webpage (including a link to an implementation).
P. Niemann, R. Wille, and R. Drechsler. Equivalence Checking in Multi-level Quantum Systems. In Conference on Reversible Computation, pages 201-215, 2014. PDF
R. Wille, D. Große, D.M. Miller, and R. Drechsler. Equivalence Checking of Reversible Circuits. In International Symposium on Multiple-Valued Logic (ISMVL), pages 324-330, 2009. PDF

MQT DDVis Online Tool

In an effort to make decision diagrams for quantum computing more accessible, we present MQT DDVis—an installation-free web-tool which visualizes quantum decision diagrams and allows to explore their behavior when used in design tasks such as simulation, synthesis, and verification.

Open MQT DDVis to explore quantum decision diagrams

Contact

If you have questions or encounter problems, feel free to contact us via quantum.cda@xcit.tum.de.