dorsal/arxiv
View SchemaThe Communication Complexity of the Hamming Distance Problem
| Authors | Wei Huang, Yaoyun Shi, Shengyu Zhang, Yufan Zhu |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0509181 |
| URL | https://arxiv.org/abs/quant-ph/0509181 |
| DOI | 10.1016/j.ipl.2006.01.014 |
Abstract
We investigate the randomized and quantum communication complexity of the Hamming Distance problem, which is to determine if the Hamming distance between two n-bit strings is no less than a threshold d. We prove a quantum lower bound of \Omega(d) qubits in the general interactive model with shared prior entanglement. We also construct a classical protocol of O(d \log d) bits in the restricted Simultaneous Message Passing model, improving previous protocols of O(d^2) bits (A. C.-C. Yao, Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 77-81, 2003), and O(d\log n) bits (D. Gavinsky, J. Kempe, and R. de Wolf, quant-ph/0411051, 2004).
{
"annotation_id": "67748644-6e61-4c2e-ad58-15d5c545a042",
"date_created": "2026-03-02T18:02:19.959000Z",
"date_modified": "2026-03-02T18:02:19.959000Z",
"file_hash": "c27b2e9d8d6ed7fad062399940b773f414c657c00782ad0e2958a61b5c07dae1",
"private": false,
"record": {
"abstract": "We investigate the randomized and quantum communication complexity of the\nHamming Distance problem, which is to determine if the Hamming distance between\ntwo n-bit strings is no less than a threshold d. We prove a quantum lower bound\nof \\Omega(d) qubits in the general interactive model with shared prior\nentanglement. We also construct a classical protocol of O(d \\log d) bits in the\nrestricted Simultaneous Message Passing model, improving previous protocols of\nO(d^2) bits (A. C.-C. Yao, Proceedings of the Thirty-Fifth Annual ACM Symposium\non Theory of Computing, pp. 77-81, 2003), and O(d\\log n) bits (D. Gavinsky, J.\nKempe, and R. de Wolf, quant-ph/0411051, 2004).",
"arxiv_id": "quant-ph/0509181",
"authors": [
"Wei Huang",
"Yaoyun Shi",
"Shengyu Zhang",
"Yufan Zhu"
],
"categories": [
"quant-ph"
],
"doi": "10.1016/j.ipl.2006.01.014",
"title": "The Communication Complexity of the Hamming Distance Problem",
"url": "https://arxiv.org/abs/quant-ph/0509181"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "8c6f4174-10de-42c4-9577-d914a3339437",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}