Quantum fingerprinting.

By Harry Buhrman, Richard Cleve, John Watrous, Ronald de Wolf. Physical Review Letters, 2001

1,104 citations recorded by the source corpus.

Classical fingerprinting associates with each string a shorter string (its fingerprint), such that any two distinct strings can be distinguished with small error by comparing their fingerprints alone. The fingerprints cannot be made exponentially smaller than the original strings unless the parties preparing the fingerprints have access to correlated random sources. We show that fingerprints consisting of quantum information can be made exponentially smaller than the original strings without any correlations or entanglement between the parties. This implies an exponential quantum/classical gap for the equality problem in the simultaneous message passing model of communication complexity.

Subfields: Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/252fa5546715d5ef6868437df2f41302ac55dff3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS (2006, methodology): “We will focus on the equality problem and, more precisely, on its solution by means of the ﬁngerprinting protocol studied in [16].”
Quantum Digital Signatures (2001, methodology): “In other words, even though Charlie and Diane have not interacted directly, the gap between sC and sD is still bounded, but by twice the margin between two recipients in the same group.”
Quantum computing for finance: Overview and prospects (2018, background): “[57], to efficiently estimate the classical distance |〈a|b〉| between states |a〉, |b〉 by repeatedly performing swap tests.”
An introduction to quantum machine learning (2014, background): “The fidelity can be obtained through a simple quantum routine sometimes referred to as a swap test [39] (see Figure 5).”
Quantum algorithm for linear systems of equations. (2008, methodology): “[5] H.”
Quantum Arthur–Merlin games (2004, background): “In the quantum case, however, this argument does not work, as one may construct exponentially large sets of pairwise nearly-orthogonal quantum states on a logarithmic number of qubits, such as those used in quantum fingerprinting [5].”
Quantum variational algorithms are swamped with traps (2022, positive): “As a second example, this time in the unitary compiling setting of qUSQ, we can evaluate the commonly used procedure of measuring the inner product or average fidelity of n-qubit states between a target unitary U∗ and a variationally chosen unitary V (θ) using statistical queries analogous to a swap”
Variational quantum algorithms (2020, background): “The first term here is evaluated as in VQE, while the second term can be obtained by computing the state overlap between |ψ̃G〉 and |ψ(θ)〉 [91, 92].”
Development of Quantum Interconnects (QuICs) for Next-Generation Information Technologies (2021, background): “There are now numerous quantum communication and cryptographic protocols identified, including security distribution for encryption [36]–[43], quantum-certified random number generation in the form of random number beacons and personal devices, secret-sharing [44], [45], quantum fingerprinting ”
Black holes as mirrors: Quantum information in random subsystems (2007, background): “But in principle Bob could do a quantum computation that maps M ′ to a compact system M̂ localized in his laboratory.”