Efficient Implementation of LIMDDs for Quantum Circuit Simulation

Lieuwe Vinkhuijzen, Thomas Grurl, Stefan Hillmich, Sebastiaan Brand, Robert Wille, Alfons Laarman

Research output: Chapter in Book/Report/Conference proceedingsConference contributionpeer-review

Abstract

Realizing the promised advantage of quantum computers over classical computers requires both physical devices and corresponding methods for the design, verification and analysis of quantum circuits. In this regard, decision diagrams have proven themselves to be an indispensable tool due to their capability to represent both quantum states and unitaries (circuits) compactly. Nonetheless, recent results show that decision diagrams can grow to exponential size even for the ubiquitous stabilizer states, which are generated by Clifford circuits. Since Clifford circuits can be efficiently simulated classically, this is surprising. Moreover, since Clifford circuits play a crucial role in many quantum computing applications, from networking, to error correction, this limitation forms a major obstacle for using decision diagrams for the design, verification and analysis of quantum circuits. The recently proposed Local Invertible Map Decision Diagram (LIMDD) solves this problem by combining the strengths of decision diagrams and the stabilizer formalism that enables efficient simulation of Clifford circuits. However, LIMDDs have only been introduced on paper thus far and have not been implemented yet—preventing an investigation of their practical capabilities through experiments. In this work, we present the first implementation of LIMDDs for quantum circuit simulation. A case study confirms the improved performance in both worlds for the Quantum Fourier Transform applied to a stabilizer state. The resulting package is available under a free license at https://github.com/cda-tum/ddsim/tree/limdd.

Original languageEnglish
Title of host publicationModel Checking Software - 29th International Symposium, SPIN 2023, Proceedings
EditorsGeorgiana Caltais, Christian Schilling
PublisherSpringer
Pages3-21
Number of pages19
ISBN (Print)9783031321566
DOIs
Publication statusPublished - 2023
Event29th International Symposium on Model Checking Software, SPIN 2023, co-located with European Joint Conferences on Theory and Practice of Software, ETAPS 2023 - Paris, France
Duration: 26 Apr 202327 Apr 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13872 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference29th International Symposium on Model Checking Software, SPIN 2023, co-located with European Joint Conferences on Theory and Practice of Software, ETAPS 2023
Country/TerritoryFrance
CityParis
Period26.04.202327.04.2023

Fingerprint

Dive into the research topics of 'Efficient Implementation of LIMDDs for Quantum Circuit Simulation'. Together they form a unique fingerprint.

Cite this