Title: The Quantum Wasserstein Distance of Order 1
Speaker: Giacomo De Palma (University of Bologna, Italy)
Abstract: We propose a generalization of the Wasserstein distance of order 1 to the quantum states of n qudits. The proposal recovers the Hamming distance for the vectors of the canonical basis and more generally the classical Wasserstein distance for quantum states diagonal in the canonical basis. We prove a continuity bound for the von Neumann entropy with respect to the proposed distance, which significantly strengthens the best continuity bound with respect to the trace distance. We also propose a generalization of the Lipschitz constant to quantum observables. The notion of quantum Lipschitz constant allows us to compute the proposed distance with a semidefinite program. We prove a Gaussian concentration inequality for the spectrum of quantum Lipschitz observables and a quadratic concentration inequality for quantum Lipschitz observables measured on product states. We apply such inequalities to obtain extremely tight limitation bounds for standard NISQ proposals in both the noisy and noiseless regimes. The bounds limit the performance of both circuit-model algorithms, such as QAOA, and continuous-time algorithms, such as quantum annealing. In the noisy regime with local depolarizing noise p, we prove that at depth O(p^-1) it is exponentially unlikely that the outcome of a noisy quantum circuit outperforms efficient classical algorithms for combinatorial optimization problems like Max-Cut.