Faster Born probability estimation via gate merging and frame optimisation

Abstract

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. Our methods are applicable to general circuits, regardless of generating gate sets, qudit dimensions and the chosen frame representations for the circuit components. We numerically demonstrate that our methods provide improved scaling in the negativity overhead for all tested cases of random circuits with Clifford+$T$ and Haar-random gates, and that the performance of our methods compares favourably with prior quasi-probability simulators as the number of non-Clifford gates increases.

15 pages, 5 figures. Comments welcome

References in corpus (20)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Variational Quantum Algorithms
• Probing many-body dynamics on a 51-atom quantum simulator
• Quantum computational advantage using photons
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Mitigating measurement errors in multi-qubit experiments
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• The XZZX Surface Code
• Novel constructions for the fault-tolerant Toffoli gate
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Frame representations of quantum mechanics and the necessity of negativity in quasi-probability representations
• Framed Hilbert space: hanging the quasi-probability pictures of quantum theory
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Quasiprobability distribution functions for periodic phase-spaces: I. Theoretical Aspects
• Improved upper bounds on the stabilizer rank of magic states
• Fast estimation of outcome probabilities for quantum circuits
• Computational power of matchgates with supplementary resources
• Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
• Efficient classical simulation and benchmarking of quantum processes in the Weyl basis

Cited by in corpus (5)

• Quantifying nonstabilizerness of matrix product states
• Measuring nonstabilizerness via multifractal flatness
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations
• Ideal stochastic process modeling with post-quantum quasiprobabilistic theories