QRC Seminar Series - Daniel Stilck-França

Title:

Limitations imposed by noise on near-term quantum algorithms for optimization

Abstract:

The impressive progress in quantum hardware in the last years has raised the quantum computing community's interest in harvesting such devices' computational power. However, in the absence of error correction, these devices can only reliably implement very shallow circuits or comparatively deeper circuits at the expense of a nontrivial density of errors. In this talk, I will discuss how this constrains the power of near-term quantum devices to solve hard combinatorial optimization problems, such as finding the ground state of an Ising model.

I will discuss a framework based on entropic inequalities that allows transparently comparing the potential of noisy quantum devices to outperform classical solvers. Based on this framework, I will show that for unitary quantum circuits with a local gate failure rate of p, quantum advantage is lost at depths 1/p regardless of the circuit we implement orthe number of qubits. Furthermore, I will construct large families of quantum circuits for which advantage is lost at constant depth if the gate failure rate does not decrease at least linearly with the system's size. I will then extend this discussion also to include the impact of error mitigation techniques on these conclusions.