Complexity of full counting statistics of free quantum particles in product states

Abstract

We study the computational complexity of quantum-mechanical expectation values of single-particle operators in bosonic and fermionic multi-particle product states. Such expectation values appear, in particular, in full-counting-statistics problems. Depending on the initial multi-particle product state, the expectation values may be either easy to compute (the required number of operations scales polynomially with the particle number) or hard to compute (at least as hard as a permanent of a matrix). However, if we only consider full counting statistics in a finite number of final single-particle states, then the full-counting-statistics generating function becomes easy to compute in all the analyzed cases. We prove the latter statement for the general case of the fermionic product state and for the single-boson product state (the same as used in the boson-sampling proposal). This result may be relevant for using multi-particle product states as a resource for quantum computing.

8 pages, published version

References in corpus (1)

• Quantum information with Gaussian states

Cited by in corpus (6)

• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Spoofing cross entropy measure in boson sampling
• Threshold detection statistics of bosonic states
• A Photonic Parameter-shift Rule: Enabling Gradient Computation for Photonic Quantum Computers
• Efficient validation of Boson Sampling from binned photon-number distributions
• Classical algorithms for measurement-adaptive Gaussian circuits