2012/03/06 by Rahul Jain, Jain, Rahul, Yaoyun Shi +5 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Computational Complexity (cs.CC) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1203.1153
openalex publication_date 2012/03/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the correlation complexity (or equivalently, the communication complexity) of generating a bipartite quantum state ρ. When ρ is a pure state, we completely characterize the complexity for approximately generating ρ by a corresponding approximate rank, closing a gap left in Ambainis, Schulman, Ta-Shma, Vazirani and Wigderson (SIAM Journal on Computing, 32(6):1570-1585, 2003). When ρ is a classical distribution P(x,y), we tightly characterize the complexity of generating P by the psd-rank, a measure recently proposed by Fiorini, Massar, Pokutta, Tiwary and de Wolf (STOC 2012). We also present a characterization of the complexity of generating a general quantum state ρ.