Experimental demonstration of quantum advantage in communication complexity for Euclidean distance problem

• URL: http://arxiv.org/abs/2605.31516v1
• Date: Fri, 29 May 2026 16:34:34 GMT
• Title: Experimental demonstration of quantum advantage in communication complexity for Euclidean distance problem
• Abstract summary: We show a quantum advantage in transmitted information surpassing the best classical protocol for an input size of $108$.<n>Our results highlight the potential of quantum communication complexity for use in a broad set of applications.
• Score: 0.9055914643034456
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $10^8$, 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.

Related papers

• Exponential Advantage of Multipartite Entanglement over Quantum Communication with Applications to Bounded-Storage Cryptography [0.5862480696321741]
  We show that a shared Greenberger-Horne-Zeilinger state enables completion of a task using only logarithmically many bits of classical communication from each sender.<n>Without preshared entanglement, any protocol achieving high success probability requires communication from at least one sender.<n>As a cryptographic application, we construct a seeded two-source extractor and establish an exponential separation between entangled and unentangled quantum side-information.
  arXiv  Detail & Related papers  (2026-07-30T10:04:53Z)
• Communication Advantages from Quantum Dense Network Coding [1.7188280334580195]
  We introduce quantum dense network coding -- a protocol that transmits the output of a non-Boolean function to a receiver using provably half as many qubits as bits for each sender.<n>We show this advantage requires both shared entanglement and quantum communication, is robust to noise, and the gap in success probability between quantum and classical communication can be amplified exponentially.<n>We show that dense network coding gives rise to a novel, information-theoretically secure, quantum cryptographic protocol, which we call measurement-device-independent quantum key growing.
  arXiv  Detail & Related papers  (2026-07-09T06:08:43Z)
• An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
  Quantum machine learning (QML) is a discipline that seeks to transfer the advantages of quantum computing to data-driven tasks.<n>We propose an efficient approach that circumvents the costs associated with data encoding by mapping inputs to a finite set of Pauli strings.<n>We evaluate our approach on text and image classification tasks, against well-established classical and quantum models.
  arXiv  Detail & Related papers  (2025-04-13T11:49:53Z)
• Quantum stochastic communication via high-dimensional entanglement [5.009186332667873]
  In this work, we consider a natural quantum information primitive in which the message to be communicated is selected.<n>We introduce a protocol that leverages high-dimensional entanglement to perform this task perfectly.<n>We experimentally demonstrate the protocol's scalability in an optical setup using 8-dimensional entanglement and multi-outcome detection.
  arXiv  Detail & Related papers  (2025-02-07T12:47:49Z)
• Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement [0.0]
  Quantum resources offer advantages over classical methods in addressing this challenge. We show that when the receiver and the senders share a multi-qubit Greenberger-Horne-Zeilinger (GHZ) state, certain global functions of the distributed inputs can be computed with only one bit of classical communication from each sender. We also show that the entanglement-based protocol exhibits significant robustness under white noise.
  arXiv  Detail & Related papers  (2024-09-20T05:17:09Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Multimodal deep representation learning for quantum cross-platform verification [60.01590250213637]
  Cross-platform verification, a critical undertaking in the realm of early-stage quantum computing, endeavors to characterize the similarity of two imperfect quantum devices executing identical algorithms. We introduce an innovative multimodal learning approach, recognizing that the formalism of data in this task embodies two distinct modalities. We devise a multimodal neural network to independently extract knowledge from these modalities, followed by a fusion operation to create a comprehensive data representation.
  arXiv  Detail & Related papers  (2023-11-07T04:35:03Z)
• Multi-User Entanglement Distribution in Quantum Networks Using Multipath Routing [55.2480439325792]
  We propose three protocols that increase the entanglement rate of multi-user applications by leveraging multipath routing. The protocols are evaluated on quantum networks with NISQ constraints, including limited quantum memories and probabilistic entanglement generation.
  arXiv  Detail & Related papers  (2023-03-06T18:06:00Z)
• Oblivious Quantum Computation and Delegated Multiparty Quantum Computation [61.12008553173672]
  We propose a new concept, oblivious computation quantum computation, where secrecy of the input qubits and the program to identify the quantum gates are required. Exploiting quantum teleportation, we propose a two-server protocol for this task. Also, we discuss delegated multiparty quantum computation, in which, several users ask multiparty quantum computation to server(s) only using classical communications.
  arXiv  Detail & Related papers  (2022-11-02T09:01:33Z)
• Entanglement-assisted quantum communication with simple measurements [0.0]
  Dense coding is the seminal example of how entanglement can boost qubit communication. We show that measurements enable strong and sometimes even optimal entanglement-assisted qubit communication protocols. Our results reveal that there are scenarios in which the power of entanglement in enhancing quantum communication can be harvested in simple and scalable optical experiments.
  arXiv  Detail & Related papers  (2022-05-19T14:47:38Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  "Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation. We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-09T19:00:00Z)
• Multi-party quantum fingerprinting with weak coherent pulses: circuit design and protocol analysis [0.0]
  We introduce a novel multi-user quantum fingerprinting protocol that is ready to be implemented with existing technology. 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.
  arXiv  Detail & Related papers  (2020-06-01T04:28:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.