Breaking the communication barrier

Karl Svozil

Correlations in an Einstein-Podolsky-Rosen-Bohm experiment can be made stronger than quantum correlations by allowing a single bit of classical communication between the two sides of the experiment.

Charles H. Bennett

Taisuke Izumi, François Le Gall

The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(łog n) bits in synchronous rounds, the best known general algorithm for APSP uses Õ(n1/3) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a Õ(n1/4)-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication.

Mariette DiChristina

Riku Jäntti, Ruifeng Duan, Jari Lietzén +2 more

The recent advances in the field of microwave superconducting circuits open the way for a multitude of engineering applications that revolutionize the field of classical communications. To exploit this new technology, we propose a novel microwave quantum-enhanced backscattering system based on the laws of quantum physics. Both the transmitter and the receiver are quantum mechanical in nature and are accommodated at the infrastructure side, while the backscattering device is classical. The advocated system breaks the performance barrier of the classical backscattering systems and approaches the ultimate attainable receiver sensitivity. Finally, our quantum solution outperforms the classical solutions in terms of its level of security.

Paolo Facchi A, Giancarlo Garnero, Giuseppe Marmo +2 more