article

Classical and quantum fingerprinting with shared randomness and one-sided error

Authors:

Jonathan Walgate,

Barry C. SandersAuthors Info & Claims

Quantum Information & Computation, Volume 5, Issue 3

Pages 258 - 271

Published: 01 May 2005 Publication History

Abstract

Within the simultaneous message passing model of communication complexity, under a public-coin assumption, we derive the minimum achievable worst-case error probability of a classical fingerprinting protocol with one-sided error. We then present entanglement-assisted quantum fingerprinting protocols attaining worst-case error probabilities that breach this bound.

References

[1]

A. C.-C. Yao,"Some complexity questions related to distributive computing," in Proceedings of the 11th Annual ACM Symposium on Theory of Computing, Atlanta, 1979, edited by M. J. Fischer et al. (ACM, New York, 1979), p. 209.

[2]

E. Kushilevitz and N. Nisan, Communication Complexity (Cambridge University Press, Cambridge, 1997).

[3]

H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, "Quantum Fingerprinting," Phys. Rev. Lett. 87, 167902 (2001).

[4]

J. Niel de Beaudrap, "One-qubit fingerprinting schemes," Phys. Rev. A 69, 022307 (2004).

[5]

A. C.-C. Yao, "On the power of quantum fingerprinting," in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, Atlanta, 1999, edited by J. S. Vitter et al. (ACM, New York, 2003), p. 77.

[6]

A. Ambainis and Y. Shi, "Distributed construction of quantum fingerprints," e-print quant-ph/0305022.

[7]

D. Gavinsky, J. Kempe, and R. de Wolf, "Quantum Communication Cannot Simulate a Public Coin," e-print quant-ph/0411051.

[8]

H. Nishimura, "Quantum Simultaneous Protocol with Prior Entanglement," in Proceedings of the 2004 ERATO Conference on Quantum Information Science, Tokyo, 2004, p. 140.

[9]

A. Ambainis, "Communication Complexity in a 3-Computer Model," Algorithmica 16, 298 (1996).

[10]

I. Newman and M. Szegedy, "Public vs. private coin flips in one round communication games," in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, 1996, edited by G. L. Miller (ACM, New York, 1996), p. 561.

[11]

L. Babai and P. G. Kimmel, "Randomized simultaneous messages: solution of a problem of Yao in communication complexity," in Proceedings of the 12th Annual IEEE Conference on Computational Complexity, Ulm, Germany, 1997, (IEEE Comp. Soc., Los Alamitos CA, 1997), p. 239.

[12]

I. Newman, "Private vs. common random bits in communication complexity," Inf. Process. Lett. 39, 67 (1991).

Digital Library

[13]

R. T. Horn, S. A. Babichev, K.-P. Marzlin, A. I. Lvovsky, and B. C. Sanders, "Single-qubit optical quantum fingerprinting," e-print quant-ph/0410232.

[14]

J. Du, P. Zou, D. K. L. Oi, X. Peng, L. C. Kwek, C. H. Oh, and A. Ekert, "Experimental Demonstration of Quantum State Multi-meter and One-qubit Fingerprinting in a Single Quantum Device," e-print quant-ph/0411180.

[15]

L. R. Welch, "Lower bounds on the maximum cross correlation of signals," IEEE Trans. Inf. Theory 20, 397 (1974).

Digital Library

[16]

J. J. Benedetto and M. Fickus, "Finite Normalized Tight Frames," Adv. Comp. Math. 18, 357 (2003).

[17]

A. J. Scott, in preparation.

Cited By

Kawachi A(2021)Recent Progress in Private Simultaneous Messages Protocols2021 IEEE Information Theory Workshop (ITW)10.1109/ITW48936.2021.9611477(1-5)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1109/ITW48936.2021.9611477
Scott AWalgate JSanders B(2007)Optimal fingerprinting strategies with one-sided errorQuantum Information & Computation10.5555/2011717.20117227:3(243-264)Online publication date: 1-Mar-2007
https://dl.acm.org/doi/10.5555/2011717.2011722

Index Terms

Classical and quantum fingerprinting with shared randomness and one-sided error
1. Theory of computation
  1. Design and analysis of algorithms

Index terms have been assigned to the content through auto-classification.

Recommendations

Optimal fingerprinting strategies with one-sided error

Fingerprinting enables two parties to infer whether the messages they hold are the same or different when the cost of communication is high: each message is associated with a smaller fingerprint and comparisons between messages are made in terms of ...
New bounds on classical and quantum one-way communication complexity

In this paper we provide new bounds on classical and quantum distributional communication complexity in the two-party, one-way model of communication. In the classical one-way model, our bound extends the well known upper bound of Kremer, Nisan and Ron [...
Exponential Separation of Quantum and Classical One-Way Communication Complexity

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM$_n$: Alice gets as input a string ${\bf x}\in\{0, 1\}^n$, and Bob gets a ...

Comments

Information & Contributors

Information

Published In

cover image Quantum Information & Computation

Quantum Information & Computation Volume 5, Issue 3

May 2005

92 pages

ISSN:1533-7146

Issue’s Table of Contents

Publisher

Rinton Press, Incorporated

Paramus, NJ

Publication History

Revised: 10 May 2005

Published: 01 May 2005

Received: 04 January 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Aug 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kawachi A(2021)Recent Progress in Private Simultaneous Messages Protocols2021 IEEE Information Theory Workshop (ITW)10.1109/ITW48936.2021.9611477(1-5)Online publication date: 17-Oct-2021
https://dl.acm.org/doi/10.1109/ITW48936.2021.9611477
Scott AWalgate JSanders B(2007)Optimal fingerprinting strategies with one-sided errorQuantum Information & Computation10.5555/2011717.20117227:3(243-264)Online publication date: 1-Mar-2007
https://dl.acm.org/doi/10.5555/2011717.2011722

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents