REVIEW 12 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
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.
Forward citations
Cited by 12 Pith papers
-
Towards Minimax Estimation of High-Order Functionals by Quantum Arguments
Quantum-inspired estimators for F_alpha(P) and F_alpha(rho) achieve optimal sample complexity n ~ alpha and minimax MSE rate alpha/n, improving prior O(alpha^2) bounds.
-
Quantum Time Lower Bounds by Permutation Invariance
A reduction framework from sample complexity yields matching time lower bounds for purity estimation, high-order functionals, productness testing, and related quantum protocols.
-
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.
-
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.
-
Continuous-Variable Quantum State Tomography Enabled by Quantum Mirrors
Quantum mirrors transfer complete photonic continuous-variable state information to an atomic control system, enabling tomography via atom measurements alone using kernel functions and Wigner reconstruction.
-
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)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.