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 fingerprinting
11 Pith papers cite this work, alongside 952 external citations. Polarity classification is still indexing.
11
Pith papers citing it
952
external citations · Crossref
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.
citation-role summary
background 3
citation-polarity summary
roles
background 3polarities
background 3representative citing papers
A reduction framework from sample complexity yields matching time lower bounds for purity estimation, high-order functionals, productness testing, and related quantum protocols.
StoqMA(2) contains NP via Õ(√n)-qubit unentangled stoquastic proofs (nearly perfect completeness) and is contained in EXP, with ETH-optimal parameters matching a refined BKS Sum-of-Squares bound.
Stoquastic Sparse Hamiltonians is StoqMA-complete and its separable version is StoqMA(2)-complete.
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.
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 parameters with quasi-normalization.
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 testing reveals weak or no correlation between structural coverage and fault finding
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 via a spacetime generalization of quantum states.
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.
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.
citing papers explorer
-
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.
-
The power of unentanglement without destructive interference
StoqMA(2) contains NP via Õ(√n)-qubit unentangled stoquastic proofs (nearly perfect completeness) and is contained in EXP, with ETH-optimal parameters matching a refined BKS Sum-of-Squares bound.
-
The Complexity of Stoquastic Sparse Hamiltonians
Stoquastic Sparse Hamiltonians is StoqMA-complete and its separable version is StoqMA(2)-complete.
-
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 parameters with quasi-normalization.
-
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 testing reveals weak or no correlation between structural coverage and fault finding
-
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 via a spacetime generalization of quantum states.
-
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