Demonstration of sequential processors with quantum advantage and analysis of classical performance limits

In this paper, we theoretically and experimentally analyze sequential processors with limited communication between parts. We compare the expressivity of sequential quantum and classical processors under the same constraints. They consist of three or four modules, each of which processes local data. The modules of the quantum processor are linked through one-qubit or one-qutrit communication, while those of the classical processor communicate through one bit or one trit. For the classical processor, we prove bounds on its performance in terms of inequalities on correlations of the output with a target function. We theoretically show that the quantum processor violates these inequalities. We show this violation experimentally on a silicon photonics setup. We describe how to find the classical bound on correlations with arbitrary target function by reducing the problem to the minimization of an Ising-type spin-glass Hamiltonian. Our theory is applicable in general problems, such as the low-rank binary matrix approximation.