From what I understood, EM is mostly post-processing and does not affect quantum circuit complexity whereas QEC has overheads and integrates as part of a quantum circuit. Is this correct? Also, which method is better or more promising? Could you give a trivial example of EM vs QEC?
The basic difference is that QEC involves the detection and correction of errors that occur during computation, while EM schemes allow errors to occur and try to compensate for the negative effects of these uncorrected errors in various ways.
A few high-level differences between QEC and EM are:
- Fault-tolerance: It is widely believed that with QEC, for low enough error rates you can arbitrarily reduce the failure probability of a circuit with additional gate overhead i.e. the threshold theorem. Without QEC, the failure probability increases with the size of the circuit, and the role of EM is to reduce this rate of increase with respect to circuit size/depth. Given any nonzero error rate, no one reasonably expects EM to work for arbitrarily wide or deep circuits.
- Logical qubits: QEC involves protecting qubits by encoding them into larger groups of qubits (logical qubits), EM generally does not.
- Gate restrictions: EM usually doesn't impose restrictions on the types of gates available in the circuit, while QEC uses fault-tolerant gates (in a restricted gateset, e.g. Clifford+T) to approximate arbitrary logical operations (with some overhead - see Solovay-Kitaev). An error-mitigated quantum circuit implements $R_x(\theta)$ using a single gate regardless of $\theta$, while the number of gates required for a fault-tolerant implementation actually depends on $\theta$.
Based on the first bullet above, QEC is the only promising approach out of the two. For any problem you can solve on a quantum computer, there is no evidence that any amount of EM can guarantee a useful result of the computation for a large enough problem and a fixed error rate (there is not threshold theorem for EM). Conversely, EM can only be competitive if the error rates can be made arbitrarily small (not just below some threshold) while the desired circuits are not allowed to exceed a certain size. EM is not a long-term strategy for quantum computing involving many qubits.
However, EM is very useful for near-term devices that are too small or too noisy for fault-tolerant implementations, and could possibly allow quantum devices to demonstrate advantages over purely classical computation on interesting tasks involving few qubits.
Error correction: make each shot good
Error mitigation: extract good signal from bad shots
Error mitigation focuses on techniques for noticing that a shot is bad, or for quantifying how a shot is bad. You run lots and lots of shots, and use the good-vs-bad signals to get better estimates of some quantity. This has relatively low upfront cost but, as circuits get bigger, it hits an exponential cost wall. The problem is that as circuits get bigger there are fewer and fewer mostly-good shots where by chance no serious error occurred. So you have to take more and more and more and more shots as circuit size increases. Improving error mitigation is about pushing back that exponential wall. For scale, if your physical gate error rate is around 1e-3, error mitigation will be very effective on quantum circuits with a thousand operations. But it will be utterly hopeless for circuits with a million operations.
Error correction focuses on techniques for making every single shot good. It has much higher upfront costs, but it doesn't have an exponential cost wall. For scale, if your physical gate error rate is around 1e-3 and you use the surface code, the upfront cost of error correction is to multiply the number of qubits you need by 1000. But once you've paid that cost you can take good shots from circuits with trillions of operations.
Here is a partial answer for the questions you've made.
Quantum Error Mitigation is a way of mitigating errors in NISQ devices. When full Quantum Error Correction will be possible there will be no real need to mitigating any further errors the way QEM proceeds since QEC will be more efficient. However, for NISQ devices QEM is truly relevant. Quantum Error Mitigation is then a set of different techniques for mitigating errors for those near term not error-corrected devices.
A simple idea in QEM is to take the small circuit of interest and introduce identity operations on the gates that provide the largest amount of noise. For instance, usually CNOTs provide the most relevant source of noise in a device, so one maps this noise enlarging the original circuit in such a way that every CNOT gets mapped to 3-CNOTs applied consecutively. Ideally, two CNOT operations are an identity, however due to error in the device one can make many consecutive runs of this enlarged circuit to map the errors the CNOTs are causing. This mapping allows mitigating the errors in the data.
Some companies are focused on error mitigation now because this could allow us to reach useful advantages with NISQ devices (this is still speculative).
Also, which method is better or more promising?
Each method will depend in the different error rates for the specific gates your device apply.