Quantum Communication Complexity on Near-Term Networks

Abstract

Quantum computers allow us to solve certain problems that are unsolvable using classical computers. In this study we focus on solving the equality problem by simulating a three quantum computer network and using the communication complexity to determine if our theoretical quantum advantage is still there in practice. We want to know how the noise from realistic quantum networks that already exist affect this communication complexity. We found that we can beat the classical solution when simulating a laboratory setup in which the quantum computers are in close proximity to each other and when using only a small bit strings. However, when moving to setups in which there are kilometres between quantum computers instead of metres or when using larger bit strings as input to our problem we see that the noise becomes too much to simulate.