Just Like the Real Thing: Fast Weak Simulation of Quantum Computation
arXiv:2007.15285 · doi:10.1109/DAC18072.2020.9218555
Abstract
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.
arXiv comment6 pages, 4 figures
References in corpus (8)
- Quantum Computing in the NISQ era and beyond
- Quantum Chemistry in the Age of Quantum Computing
- Characterizing Quantum Supremacy in Near-Term Devices
- Quantum algorithms: an overview
- Simulation of quantum circuits by low-rank stabilizer decompositions
- Low Depth Quantum Simulation of Electronic Structure
- QuEST and High Performance Simulation of Quantum Computers
- qHiPSTER: The Quantum High Performance Software Testing Environment