How many copies are needed for state discrimination?

Abstract

Given a collection of states (rho_1, ..., rho_N) with pairwise fidelities F(rho_i, rho_j) <= F < 1, we show the existence of a POVM that, given rho_i^{otimes n}, will identify i with probability >= 1-epsilon, as long as n>=2(log N/eps)/log (1/F). This improves on previous results which were either dimension-dependent or required that i be drawn from a known distribution.

1 page, submitted to QCMC'06, answer is O(log # of states)

Cited by in corpus (15)

• Sample-optimal tomography of quantum states
• Quantum algorithms for hidden nonlinear structures
• Probe incompatibility in multiparameter noisy quantum metrology
• A lower bound on the probability of error in quantum state discrimination
• QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
• Pseudo-randomness and Learning in Quantum Computation
• Symmetric distinguishability as a quantum resource
• The Optimal Single Copy Measurement for the Hidden Subgroup Problem
• On the Power of Quantum Encryption Keys
• An invitation to the sample complexity of quantum hypothesis testing
• Pretty simple bounds on quantum state discrimination
• Lightweight Detection of a Small Number of Large Errors in a Quantum Circuit
• Efficient Quantum Algorithm for Identifying Hidden Polynomials
• Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size
• Quantum algorithms for shifted subset problems