Quantum communication holds the promise of creating disruptive technologies that will play an essential role in future communication networks. For example, the study of quantum communication complexity has shown that quantum communication allows exponential reductions in the information that must be transmitted to solve distributed computational tasks. Recently, protocols that realize this advantage using optical implementations have been proposed. Here we report a proof-of-concept experimental demonstration of a quantum fingerprinting system that is capable of transmitting less information than the best-known classical protocol. Our implementation is based on a modified version of a commercial quantum key distribution system using off-the-shelf optical components over telecom wavelengths, and is practical for messages as large as 100 Mbits, even in the presence of experimental imperfections. Our results provide a first step in the development of experimental quantum communication complexity.
Quantum communication holds the promise of creating disruptive technologies that will play an essential role in future communication networks. For example, the study of quantum communication complexity has shown that quantum communication allows exponential reductions in the information that must be transmitted to solve distributed computational tasks. Recently, protocols that realize this advantage using optical implementations have been proposed. Here we report a proof-of-concept experimental demonstration of a quantum fingerprinting system that is capable of transmitting less information than the best-known classical protocol. Our implementation is based on a modified version of a commercial quantum key distribution system using off-the-shelf optical components over telecom wavelengths, and is practical for messages as large as 100 Mbits, even in the presence of experimental imperfections. Our results provide a first step in the development of experimental quantum communication complexity.
Current communication networks are based on classical physics and classical information-processing. However, for nearly a century, we have known that at its most fundamental level, the universe is governed by the laws of quantum mechanics. With quantum communication, new possibilities arise in our capabilities to transmit and process information which, in many cases, lead to advantages compared to what is classically possible. The entire scope of tasks for which quantum communication can offer improvements has not yet been fully explored, but several quantum protocols are known that can either perform tasks which are impossible with classical resources or can outperform classical protocols. These quantum protocols are well understood from a theoretical point of view, but many of them have never been demonstrated in practice. Thus, in the context of quantum communication, there is a significant gap between theory and experiment that must be removed in order to harness the advantages provided by quantum mechanics in a practical setting. \n \nIn this thesis, we develop a series of tools for developing and testing practical quantum communication protocols. Our main technique is a theoretical reformulation of existing quantum communication protocols that converts them into a form in which they can be demonstrated with existing experimental techniques. More precisely, they can be implemented using only coherent states of light and linear optics circuits while still retaining the crucial properties of the original abstract protocols. We use this result to construct practical protocols for the Hidden Matching problem and quantum fingerprinting. \n \n \nIn the case of quantum fingerprinting, we make a thorough analysis of the role played by experimental errors and show that our practical protocol can still be implemented in the presence of these imperfections. In fact, we report a proof of concept experimental demonstration of a quantum fingerprinting system that is capable of transmitting less information than the best known classical protocol for this problem. Our implementation is based on a modified version of a commercial quantum key distribution system using off-the-shelf optical components over telecom wavelengths, and is practical for messages as large as 100 Mbits, even in the presence of experimental imperfections. \n \nSimilarly, in the context of cryptography, we propose a multiparty quantum signature protocol that can be implemented from any point-to-point quantum key distribution network, proving its security against forging, repudiation and non-transferability. Crucially, since quantum key distribution is already a practical technology, so is this protocol. However, unlike other tasks in quantum communication, there has not been significant theoretical work on establishing a security model for quantum signature schemes. Consequently, we also constructed a security framework for these schemes and proved several properties that these protocols must satisfy in order to achieve their security goals. \n \nFinally, in addition to proposing new practical protocols, we provide a reliable data analysis technique to verify an important property of many quantum communication protocols: the presence of entanglement. Our technique is based on entanglement witnesses and it does not require the specification of a prior distribution nor the assumption of independent measurements. The technique is suitable to be used with nonlinear entanglement witnesses, which we show can be constructed from any linear witness and evaluated from the same experimental data. We also develop numerical tools necessary to employ this approach in practice, rendering the procedure ready to be applied to current experiments. We demonstrate this by analyzing the data of a photonic experiment generating two-photon states whose entanglement is verified with the use of an accessible nonlinear witness.
Quantum communication has historically been at the forefront of advancements, from fundamental tests of quantum physics to utilizing the quantum-mechanical properties of physical systems for practical applications. In the field of communication complexity, quantum communication allows the advantage of an exponential reduction in the transmitted information over classical communication to accomplish distributed computational tasks. However, to date, demonstrating this advantage in a practical setting continues to be a central challenge. Here, we report a proof-of-principle experimental demonstration of a quantum fingerprinting protocol that for the first time surpasses the ultimate classical limit to transmitted information. Ultralow noise superconducting single-photon detectors and a stable fiber-based Sagnac interferometer are used to implement a quantum fingerprinting system that is capable of transmitting less information than the classical proven lower bound over 20 km standard telecom fiber for input sizes of up to 2 Gbits. The results pave the way for experimentally exploring the advanced features of quantum communication and open a new window of opportunity for research in communication complexity and testing the foundations of physics.
Quantum fingerprinting (QF) promises exponential reduction of information transmission in executing communication complexity tasks. Practicality and quantum advantage of this novel protocol has been recently demonstrated using weak coherent pulses to carry the fingerprinting information. However, all coherent QF implementations rely upon a direct optical link to maintain coherence between the users, which does not comply with the protocol's rule that the users must not have any access to a shared randomness. To close this loophole, we propose, and experimentally demonstrate, a novel protocol based on asynchronous coincidence pairing from the interference result between coherent optical fields that are remotely and independently prepared. Over a length of 20 km telecom fiber, our QF setup has outperformed the best-known classical algorithm, for the first time without being susceptible to shared randomness. Our result paves the way toward practical applications of QF in communication complexity.
When considering the complexity of communication protocols, the aim is to perform a certain task with the minimum amount of communication resources, such as time and transmitted information. The use of quantum states may lead to an exponential advantage in the use of such resources. Here, we are interested in the task of calculating the Euclidean distance between two vectors representing real data sets. It has been previously shown that it is possible to obtain an advantage for this task based on quantum fingerprinting. This protocol is defined in the simultaneous message passing model of communication complexity, where the two parties do not communicate with each other but send data to a third party, and exploits practical fingerprints generated using trains of coherent state pulses instead of highly entangled qubit states that are hard to generate for large input sizes needed to demonstrate an exponential advantage. We perform a proof-of-principle experimental demonstration of the Euclidean distance protocol using amplitude modulation techniques for encoding non-binary data sets and high-performance superconducting nanowire single-photon detectors required to increase the accessible input size. We show a quantum advantage in transmitted information surpassing the best classical protocol for an input size of 108, for diverse types of data sets, including those corresponding to real grayscale images, and with reasonable precision and error bounds. Our results highlight the potential of quantum communication complexity for use in a broad set of applications.
Abstract Quantum communication has been leading the way of many remarkable theoretical results and experimental tests in physics. In this context, quantum communication complexity (QCC) has recently drawn earnest research attention as a tool to optimize the amounts of transmitted qubits and energy that are required to implement distributed computational tasks. On this matter, we introduce a novel multi-user quantum fingerprinting (QF) protocol that is ready to be implemented with existing technology. Particularly, we extend to the multi-user framework a well-known two-user coherent-state fingerprinting scheme. This generalization is highly non-trivial for a twofold reason, as it requires not only to extend the set of protocol rules but also to specify a procedure for designing the optical devices intended for the generalized protocol. Much of the importance of our work arises from the fact that the obtained QCC figures of merit allow direct comparison with the best-known classical multi-user fingerprinting protocol, of significance in the field of computer technologies and networking. Furthermore, as one of the main contributions of the manuscript, we deduce innovative analytical upper bounds on the amount of transmitted quantum information that are even valid in the two-user protocol as a particular case. These original analytical bounds are of interest for estimating the realistic protocol performance prior to experimental realizations. Ultimately, comparative results are provided to contrast different protocol implementation strategies and, importantly, to show that, under realistic circumstances, the multi-user protocol can achieve tasks that are impossible by using classical communication alone. Our work provides relevant contributions towards understanding the nature and the limitations of QF and, on a broader scope, also the limitations and possibilities of quantum-communication networks embracing a node that is accessed by multiple users at the same time.
Quantum communication complexity explores the minimum amount of communication required to achieve certain tasks using quantum states. One representative example is quantum fingerprinting, in which the minimum amount of communication could be exponentially smaller than the classical fingerprinting. Here, we propose a quantum fingerprinting protocol where coherent states and channel multiplexing are used, with simultaneous detection of signals carried by multiple channels. Compared with an existing coherent quantum fingerprinting protocol, our protocol could consistently reduce communication time and the amount of communication by orders of magnitude by increasing the number of channels. Our proposed protocol can even beat the classical limit without using superconducting-nanowire single photon detectors. We also report a proof-of-concept experimental demonstration with six wavelength channels to validate the advantage of our protocol in the amount of communication. The experimental results clearly prove that our protocol not only surpasses the best-known classical protocol, but also remarkably outperforms the existing coherent quantum fingerprinting protocol.