Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems

Andris Ambainis; William Gasarch; Aravind Srinivasan; Andrey Utis

doi:10.1007/11940128_63

Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems

Andris Ambainis^*
, William Gasarch
, Aravind Srinivasan
, Andrey Utis

^*Šī darba korespondējošais autors

University of Waterloo
University of Maryland, College Park

Zinātniskās darbības rezultāts: Nodaļa grāmatā/enciklopēdijā/konferences krājumā › Konferences zinātniskais raksts › Pētniecība › koleģiāli recenzēts

Kopsavilkums

Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on at most a bits? Let 0≤ a≤n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C ^* version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q^* quantum protocols. Our results are obtained by employing basic tools from combinatorics and calculus to lower-bound the ranks of the appropriate matrices.

Oriģinālvaloda	Angļu
Publikācijas avota nosaukums	Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings
Lapas	628-637
Lapu skaits	10
DOIs	https://doi.org/10.1007/11940128_63
Publikācijas statuss	Publicēts - 2006
Ārēji publicēts	Jā
Pasākums	17th International Symposium on Algorithms and Computation, ISAAC 2006 - Kolkata, Indija Ilgums: 18 dec. 2006 → 20 dec. 2006

Publikāciju sērijas

Nosaukums	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Sējums	4288 LNCS
ISSN (Drukātā versija)	0302-9743
ISSN (Elektroniskā versija)	1611-3349

Konference

Konference	17th International Symposium on Algorithms and Computation, ISAAC 2006
Valsts/Teritorija	Indija
Pilsēta	Kolkata
Periods	18/12/06 → 20/12/06

Piekļuve Dokumentiem

10.1007/11940128_63

Citi faili un saites

Saite uz publikāciju Scopus

Citēt šo

Ambainis, A., Gasarch, W., Srinivasan, A., & Utis, A. (2006). Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems. (gadā) Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings (lpp. 628-637). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Sēj. 4288 LNCS). https://doi.org/10.1007/11940128_63

Ambainis, Andris ; Gasarch, William ; Srinivasan, Aravind u.c. / Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems. Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. lpp. 628-637 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{31570366808d4ee494a7b30e3f615e89,

title = "Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems",

abstract = "Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on at most a bits? Let 0≤ a≤n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C * version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q* quantum protocols. Our results are obtained by employing basic tools from combinatorics and calculus to lower-bound the ranks of the appropriate matrices.",

author = "Andris Ambainis and William Gasarch and Aravind Srinivasan and Andrey Utis",

year = "2006",

doi = "10.1007/11940128\_63",

language = "English",

isbn = "3540496947",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "628--637",

booktitle = "Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings",

note = "17th International Symposium on Algorithms and Computation, ISAAC 2006 ; Conference date: 18-12-2006 Through 20-12-2006",

}

Ambainis, A, Gasarch, W, Srinivasan, A & Utis, A 2006, Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems. (kur) Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), sēj. 4288 LNCS, lpp. 628-637, 17th International Symposium on Algorithms and Computation, ISAAC 2006, Kolkata, Indija, 18/12/06. https://doi.org/10.1007/11940128_63

Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems. / Ambainis, Andris; Gasarch, William; Srinivasan, Aravind u.c.
Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. lpp. 628-637 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Sēj. 4288 LNCS).

Zinātniskās darbības rezultāts: Nodaļa grāmatā/enciklopēdijā/konferences krājumā › Konferences zinātniskais raksts › Pētniecība › koleģiāli recenzēts

TY - GEN

T1 - Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems

AU - Ambainis, Andris

AU - Gasarch, William

AU - Srinivasan, Aravind

AU - Utis, Andrey

PY - 2006

Y1 - 2006

N2 - Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on at most a bits? Let 0≤ a≤n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C * version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q* quantum protocols. Our results are obtained by employing basic tools from combinatorics and calculus to lower-bound the ranks of the appropriate matrices.

AB - Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on at most a bits? Let 0≤ a≤n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C * version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q* quantum protocols. Our results are obtained by employing basic tools from combinatorics and calculus to lower-bound the ranks of the appropriate matrices.

UR - https://www.scopus.com/pages/publications/77249083717

U2 - 10.1007/11940128_63

DO - 10.1007/11940128_63

M3 - Conference paper

AN - SCOPUS:77249083717

SN - 3540496947

SN - 9783540496946

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 628

EP - 637

BT - Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings

T2 - 17th International Symposium on Algorithms and Computation, ISAAC 2006

Y2 - 18 December 2006 through 20 December 2006

ER -

Ambainis A, Gasarch W, Srinivasan A, Utis A. Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems. (gadā) Algorithms and Computation - 17th International Symposium, ISAAC 2006, Proceedings. 2006. lpp. 628-637. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11940128_63

Lower bounds on the deterministic and quantum communication complexities of hamming-distance problems

Kopsavilkums

Publikāciju sērijas

Konference

Piekļuve Dokumentiem

Citi faili un saites

Nospiedums

Citēt šo