Design, Automation, and Test in Europe
High-performance QuIDD-based simulation of quantum circuits
George F. Viamontes, Igor L. Markov, John P. Hayes
Abstract
Simulating quantum computation on a classical com-puter is a difficult problem. The matrices representing quantum gates, and vectors modeling qubit states grow ex-ponentially with the number of qubits. It has been shown ex-perimentally that the QuIDD (Quantum Information Deci-sion Diagram) datastructure greatly facilitates simulations using memory and runtime that are polynomial in the num-ber of qubits. In this paper, we present a complexity analysis which formally describes this class of matrices and vectors. We also present an improved implementation of QuIDDs which can simulate Grover’s algorithm for quantum search with the asymptotic runtime complexity of an ideal quantum computer up to negligible overhead. 1.