REVIEW 7 cited by
Quantum fingerprinting
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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.
Forward citations
Cited by 7 Pith papers
-
Dense Hamiltonians at the Parseval Limit: The Noncommutative BH Constant is Exponential and the Quantum FEI Conjecture is False
A new construction of flat degree-d Hamiltonians with exp(Theta(d^2)) nonzero Pauli terms makes the noncommutative Bohnenblust-Hille constant exponential and refutes the quantum Fourier Entropy-Influence conjecture.
-
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.
-
An Optimal Analysis of the Product Test
For every n >= 2, the product test's worst-case acceptance probability equals (1 + mω^2 + (1−mω)^2)/2 with m = floor(1/ω), where ω is the maximum squared overlap with a product state.
-
On estimating operator norm distance, with optimal trace distance estimation when one state is pure
Rank-independent quantum estimators achieve Θ(1/ε) queries for operator-norm (and trace) distance when one state is pure, and Õ(1/ε^{3/2}) queries for general states, proving BQP-completeness.
-
A lower bound on the classical simulation cost of star-network correlations
A star-network exclusion game is won perfectly with quantum d-level messages, but classically needs a message of at least n^{d-1} symbols, so no fixed-size classical qubit description can simulate joint measurements o...
-
Quantum computation of hadron scattering in a lattice gauge theory
On a trapped-ion quantum computer, the authors prepared multiple meson wave packets and simulated their early-time collisions in a 1+1D Z2 lattice gauge theory.
-
Quantum encodings that preserve persistent homology
Investigates which quantum encodings of classical datasets preserve persistent homology so that quantum algorithms can extract topological features directly from the data.
Discussion (0). Continue with ORCID to comment.