Faster Born probability estimation via gate merging and frame optimisation

Understand

Outcome probability estimation via classical methods is an important task for validating quantum computing devices.

• Outcome probabilities of any quantum circuit can be estimated using Monte Carlo sampling, where the amount of negativity present in the circuit frame representation quantifies the overhead on the number of samples required to achieve a certain precision.
• In this paper, we propose two classical sub-routines: circuit gate merging and frame optimisation, which optimise the circuit representation to reduce the sampling overhead.
• We show that the runtimes of both sub-routines scale polynomially in circuit size and gate depth.