As Accurate as Needed, as Efficient as Possible: Approximations in DD-based Quantum Circuit Simulation
Stefan Hillmich1,a, Richard Kueng1,b, Igor L. Markov2 and Robert Wille1,3,c
1Institute for Integrated Circuits, Johannes Kepler University Linz, Austria
astefan.hillmich@jku.at
brichard.kueng@jku.at
2Department of EECS, University of Michigan, USA
imarkov@eecs.umich.edu
3Software Competence Center Hagenberg GmbH (SCCH), Austria
crobert.wille@jku.at
ABSTRACT
Quantum computers promise to solve important problems faster than conventional computers. However, unleashing this power has been challenging. In particular, design automation runs into (1) the probabilistic nature of quantum computation and (2) exponential requirements for computational resources on non-quantum hardware. In quantum circuit simulation, Decision Diagrams (DDs) have previously shown to reduce the required memory in many important cases by exploiting redundancies in the quantum state. In this paper, we show that this reduction can be amplified by exploiting the probabilistic nature of quantum computers to achieve even more compact representations. Specifically, we propose two new DD-based simulation strategies that approximate the quantum states to attain more compact representations, while, at the same time, allowing the user to control the resulting degradation in accuracy. We also analytically prove the effect of multiple approximations on the attained accuracy and empirically show that the resulting simulation scheme enables speed-ups up to several orders of magnitudes.
Keywords: Quantum Computing, Quantum Circuit Simulation, Decision Diagrams, Approximation.
