Quantum communication has been the most successful aspect of quantum computation in terms of applications and physical implementations. We focus on aspects that have direct impact on the overarching objectives of this proposal. Communication complexity is an indispensable tool for analysing informational bottlenecks in computation. As a transversal theme, we study channel capacities in networks, where our main goal is to establish trade-offs between noise and achievable transmission rates that are practically useful. Finally, we will study how susceptible classical cryptosystems are to quantum attacks.
Workpackage Leader: Sophie Laplante (Université Paris Diderot-Paris 7)
Significant achievements
- Two implementations experimentally validated the theoretical results of this workpackage, the first one concerning communication complexity. The Sampling Matching problem is inspired by the Hidden Matching problem and features an exponential gap between quantum and classical protocols in the one-way communication model. Its advantage is that it allows a photonic implementation based on encoding in the phase of coherent states of light, the use of a fixed size linear optic circuit, and single-photon detection. In a proof-of-principle experiment, an advantage has been demonstrated in the transmitted information resource beyond a threshold input size, which would have been impossible to reach for the original Hidden Matching problem.
- The second experimentally validated theoretical result concerns quantum networks. Networking is an integral part of quantum communication and has significant potential for upscaling quantum computer technologies. Sensing of multiple spatially distributed parameters may also benefit from an entangled quantum network. UPCH experimentally demonstrated how sensing of an averaged phase shift among four distributed nodes benefits from an entangled quantum network. Using a four-mode entangled continuous variable (CV) state, they demonstrated deterministic quantum phase sensing with a precision beyond what is attainable with unentangled probes.
- CWI made a theoretical breakthrough about the log rank conjecture, which is a long-standing open question in communication complexity since it was formulated in the late 1970s by Yao. CWI instigated the study of the sink function and showed that it has logarithmic approximate log rank. They first showed that it has polynomial randomized communication complexity, thus giving an exponential separation between randomized communication complexity and logarithm of the approximate rank, refuting the log-approximate-rank conjecture. In follow-up work, they show that even the quantum communication complexity of the sink function is polynomial, thus also refuting the quantum log-approximate-rank conjecture. Their lower bound is based on the fooling distribution method introduced by Rao and Sinha for the classical case, and extended by Anshu, Touchette, Yao and Yu for the quantum case.
- UPD proposed a new public-key cryptosystem whose security is based on the computational intractability of the following problem: Given a Mersenne number p = 2n − 1, where n is a prime, a positive integer h, and two n-bit integers T and R, find two n-bit integers F and G, each of Hamming weight at most h such that T = F R + G modulo p, under the promise that they exist. This is a new candidate for post-quantum cryptography as it is surmised that it is also hard to break with quantum algorithms.
- Besides this new cryptographic protocol, LU proposed a new technical tool applicable to multiple cryptosystems. More precisely, they studied the security of cryptographic schemes against quantum attacks in the random oracle model. They presented a new transformation of a one-way time-release encryption scheme to one that is secure in the random oracle model. This new transformation (called one-way to hiding) gives higher flexibility in its applicability, as well as tighter bounds. It provides better security bounds in several public-key encryption schemes. It makes use of a new variant of quantum oracles, semi- classical oracles, where queries are partially measured.