2022/09/04 by Kalai, Gil
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2209.01648
More than ten years ago the author described a parameter K(ρ) for the complexity of n-qubit quantum state ρ and raised the conjecture (referred to as "Conjecture C") that when this parameter is superpolynomial in n, the state ρ is not experimentally feasible (and will not be experimentally achieved without quantum fault-tolerance). Shortly afterward [6] (arXiv:1204.3404), Steve Flammia and Aram Harrow claimed that the simple easy-to-construct W states are counterexamples to "Conjecture C." We point out that Flammia and Harrow's argument regarding W-states is incomplete. Moreover, the emergent picture from experimental progress of the past decade on noisy intermediate scale quantum (NISQ) computers suggests that W-states, as simple as they appear, cannot be achieved experimentally by NISQ computers, and can not be constructed without quantum fault-tolerance.