  Quantum error mitigation techniques can reduce noise on current quantum
hardware without the need for fault-tolerant quantum error correction. For
instance, the quasiprobability method simulates a noise-free quantum computer
using a noisy one, with the caveat of only producing the correct expected
values of observables. The cost of this error mitigation technique manifests as
a sampling overhead which scales exponentially in the number of corrected
gates. In this work, we present a new algorithm based on mathematical
optimization that aims to choose the quasiprobability decomposition in a
noise-aware manner. This directly leads to a significantly lower basis of the
sampling overhead compared to existing approaches. A key element of the novel
algorithm is a robust quasiprobability method that allows for a tradeoff
between an approximation error and the sampling overhead via semidefinite
programming.
