Just like the real thing: Fast weak simulation of quantum computation

Stefan Hillmich, Igor L. Markov, Robert Wille

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

12 Scopus citations


Quantum computers promise significant speedups in solving problems intractable for conventional computers but, despite recent progress, remain limited in scaling and availability. Therefore, quantum software and hardware development heavily rely on simulation that runs on conventional computers. Most such approaches perform strong simulation in that they explicitly compute amplitudes of quantum states. However, such information is not directly observable from a physical quantum computer because quantum measurements produce random samples from probability distributions defined by those amplitudes. In this work, we focus on weak simulation that aims to produce outputs which are statistically indistinguishable from those of error-free quantum computers. We develop algorithms for weak simulation based on quantum state representation in terms of decision diagrams. We compare them to using state-vector arrays and binary search on prefix sums to perform sampling. Empirical validation shows, for the first time, that this enables mimicking of physical quantum computers of significant scale.

Original languageEnglish
Title of host publication2020 57th ACM/IEEE Design Automation Conference, DAC 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781450367257
StatePublished - Jul 2020
Externally publishedYes
Event57th ACM/IEEE Design Automation Conference, DAC 2020 - Virtual, San Francisco, United States
Duration: 20 Jul 202024 Jul 2020

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X


Conference57th ACM/IEEE Design Automation Conference, DAC 2020
Country/TerritoryUnited States
CityVirtual, San Francisco


  • Quantum computing
  • Sampling
  • Simulation
  • Weak simulation


Dive into the research topics of 'Just like the real thing: Fast weak simulation of quantum computation'. Together they form a unique fingerprint.

Cite this