We study the computational complexity of quantum-mechanical expectation values of single-particle operators in bosonic and fermionic multiparticle product states. Such expectation values appear, in particular, in full-counting-statistics problems. Depending on the initial multiparticle 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 multiparticle product states as a resource for quantum computing.
We study the computational complexity of quantum-mechanical expectation values of single-particle operators in bosonic and fermionic multiparticle product states. Such expectation values appear, in particular, in full-counting-statistics problems. Depending on the initial multiparticle 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 multiparticle product states as a resource for quantum computing.
It is known that computing the permanent of the matrix 1+A, where A is a finite-rank matrix, requires a number of operations polynomial in the matrix size. Motivated by the boson-sampling proposal of restricted quantum computation, I extend this result to a generalization of the matrix permanent: An expectation value in a product of a large number of identical bosonic states with a bounded number of bosons. This result complements earlier studies on the computational complexity in boson sampling and related setups. The proposed technique based on the Gaussian averaging is equally applicable to bosonic and fermionic systems. This also allows us to improve an earlier polynomial complexity estimate for the fermionic version of the same problem.
Noninteracting bosons were proposed to be used for a demonstration of quantum-computing supremacy in a boson-sampling setup. A similar demonstration with fermions would require that the fermions are initially prepared in an entangled state. I suggest that pairwise entanglement of fermions would be sufficient for this purpose. Namely, it is shown that computing multiparticle scattering amplitudes for fermions entangled pairwise in groups of four single-particle states is #P-hard. In linear algebra, such amplitudes are expressed as exterior products of two-forms of rank 2. In particular, a permanent of a $N\ifmmode\times\else\texttimes\fi{}N$ matrix may be expressed as an exterior product of N2 two forms of rank 2 in dimension 2N2, which establishes the #P-hardness of the latter.
We revisit the problem of full counting statistics of particles on a segment of a one-dimensional gas of free fermions. Using a combination of analytical and numerical methods, we study the crossover between the counting of discrete particles and of the continuous particle density as a function of smoothing in the counting procedure. In the discrete-particle limit, the result is given by the Fisher-Hartwig expansion for Toeplitz determinants, while in the continuous limit we recover the bosonization results. This example of full counting statistics with smoothing is also related to orthogonality catastrophe, Fermi-edge singularity and non-equilibrium bosonization.
Full counting statistics (FCS) provides a powerful framework to access the statistical information of a system from the characteristic function. However, applications of FCS for generic interacting quantum systems are often hindered by the intrinsic difficulty of classical simulation of quantum many-body problems. Here we propose a quantum algorithm for FCS that can obtain both the particle distribution and cumulants of interacting systems. The algorithm evaluates the characteristic functions by quantum computing and then extracts the distribution and cumulants with classical postprocessing. With digital signal processing theory, we analyze the dependence of accuracy with the number of sampling points for the characteristic functions. We show that the desired number of sampling points for accurate FCS can be reduced by filtering some components of the quantum state that are not of interest. By numeral simulation, we demonstrate the FCS of domain walls for several representative models. Remarkably, we show that the accuracy of our algorithm does not significantly change with the system size for a given number of measurements. The algorithm suggests an avenue for studying full counting statistics on quantum computers.
Free fermions are some of the best studied quantum systems. However, little is known about the complexity of learning free-fermion distributions. In this work we establish the hardness of this task in the particle number non-preserving case. In particular, we give an information theoretical hardness result for the general task of learning from expectation values and, in the more general case when the algorithm is given access to samples, we give a computational hardness result based on the LPN assumption for learning the probability density function.
We consider the problem of learning expectation values of particle-preserving operators with respect to an unknown η-particle n-mode fermionic state via classical shadows. Our main application is to estimating overlaps with arbitrary Slater determinant states: While it is known that such overlaps can, in the average case, be learnt to a fixed additive precision with a constant number of samples, the best-known worst case bound is O(nlogn); here we improve this to O(ηlogη), achieving a mode-independent sample cost. Our procedure is also computationally efficient, requiring only classical post-processing which for a generic dense orbital runs in time O(nη2). For the task of estimating the expectation value of a general particle-preserving quadratic fermionic observable h, we prove a sample complexity bound of O(η∥h0∥22), where h0 is the traceless component of h; the associated classical post-processing scales as O(n2η). Finally, we discuss implementation of the required randomization: in a first-quantized encoding, approximate unitary designs give circuit depths polylogarithmic in the number of modes, contrasting with linear-depth requirements for nearest-neighbor second-quantized matchgate implementations. On the technical side, our proof reduces the extremal shadow variance to harmonic analysis on the AIII symmetric space U(n)/(U(η)×U(n−η)) and evaluates the resulting integral using techniques from the theories of Jacobi ensembles and orthogonal polynomials, in a calculation which may be of independent interest.