Just Like the Real Thing: Fast Weak Simulation of Quantum Computation.
Sprache des Titels:
Design Automation Conference (DAC)
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.