Quantum fingerprinting
read the original abstract
Classical fingerprinting associates with each string a shorter string (its fingerprint), such that, with high probability, any two distinct strings can be distinguished by comparing their fingerprints alone. The fingerprints can be exponentially smaller than the original strings if the parties preparing the fingerprints share a random key, but not if they only have access to uncorrelated random sources. In this paper 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: we give a scheme where the quantum fingerprints are exponentially shorter than the original strings and we give a test that distinguishes any two unknown quantum fingerprints with high probability. Our scheme implies an exponential quantum/classical gap for the equality problem in the simultaneous message passing model of communication complexity. We optimize several aspects of our scheme.
This paper has not been read by Pith yet.
Forward citations
Cited by 7 Pith papers
-
The Complexity of Stoquastic Sparse Hamiltonians
Stoquastic Sparse Hamiltonians is StoqMA-complete and its separable version is StoqMA(2)-complete.
-
Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference
StoqMA(2) contains NP with Õ(√n)-qubit proofs and completeness error 2^{-polylog(n)}, is contained in EXP, and satisfies StoqMA(k)=StoqMA(2) for k≥2 when completeness error is negligible.
-
Quantum Randomized Subspace Iteration
QRSI spans degenerate quantum eigenspaces almost surely by conjugating the Hamiltonian with random unitaries on g parallel branches and using subspace estimation, while exactly preserving the spectral gap.
-
GHZ is All You Need: Quantum Sensing with VISTA
VISTA achieves near-Heisenberg scaling in moderately noisy quantum magnetometry by passively evolving a probe, comparing it via swap test to a physics-informed quantum twin circuit, and optimizing only physical parame...
-
Probabilistic Condition, Decision and Path Coverage of Circuit-based Quantum Programs
Quantum circuits show high average condition (97.56%) and decision (97.63%) coverage but lower path coverage (71.84%), with probabilistic versions adding confidence levels (averages 88.87%, 88.65%, 37.18%); mutation t...
-
From quantum time to manifestly covariant QFT: On the need for a quantum-action-based quantization
A quantum-action-based quantization resolves inconsistencies in second-quantizing quantum time schemes by introducing spacetime classical mechanics and a no-go theorem, yielding manifestly covariant interacting QFT vi...
-
Are controlled unitaries helpful?
Controlled unitaries can be decontrolled into standard unitaries with random phase, showing they do not help beyond global phase information for a large class of quantum problems.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.