How to Efficiently Handle Complex Values? Implementing Decision Diagrams for Quantum Computing
Authors:
- 1 November 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-7
Abstract
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.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- QMDDs: Efficient Quantum Function Representation and ManipulationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015
- Equivalence Checking in Multi-level Quantum Systems2014
- On the “Q” in QMDDs: Efficient Representation of Quantum Functionality in the QMDD Data-Structure2013
- Towards quantum chemistry on a quantum computerNature Chemistry, 2010
- DDMF: An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical RestrictionIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2008
- An XQDD-Based Verification Method for Quantum CircuitsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2008
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- Quantum computation and Shor's factoring algorithmReviews of Modern Physics, 1996
- A fast quantum mechanical algorithm for database search1996
- Efficient implementation of a BDD package1990