Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1904.06069 · Physical Review A

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

Dmitri A. Ivanov, Leonid Gurvits

Published Jan 7, 2020• 13 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.101.012303

Related papers

Polynomial computational complexity of matrix elements of finite-rank-generated single-particle operators in products of finite bosonic states

Dmitri A. Ivanov

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.

arXiv:2210.11568•SciPost Physics Core•Apr 22, 2024•0 citations

Computational complexity of exterior products and multiparticle amplitudes of noninteracting fermions in entangled states

Dmitri A. Ivanov

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 ${N}^{2}$ two forms of rank 2 in dimension $2{N}^{2}$, which establishes the #P-hardness of the latter.

arXiv:1603.02724•Physical Review A•Jul 17, 2017•5 citations

Fermionic full counting statistics with smooth boundaries: From discrete particles to bosonization

Dmitri A. Ivanov, Ivan P. Levkivskyi

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.

arXiv:1507.07896•Europhysics Letters (EPL)•Jan 1, 2016•6 citations

Full counting statistics of particle distribution on a digital quantum computer

Yun-Zhuo Fan, Dan-Bo Zhang

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.

arXiv:2308.01255•Physical Review A•Jan 8, 2024•3 citations

Free Fermion Distributions Are Hard to Learn

Alexander Nietner

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.

arXiv:2306.04731•Jun 7, 2023•5 citations

Particle-preserving fermionic shadows with mode-independent sample complexity

Maxwell West, M. Cerezo, Martin Larocca

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 $\mathcal{O}(\sqrt n \log n)$; here we improve this to $\mathcal{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 $\mathcal{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 $\mathcal{O}(η\|h_0\|_2^2)$, where $h_0$ is the traceless component of $h$; the associated classical post-processing scales as $\mathcal{O}(n^2η)$. 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(η)\times 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.

quant-pharXiv:2606.27254•Jun 26, 2026•10 citations
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{N}^{2}N2 two forms of rank 2 in dimension 2N22{N}^{2}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 nnn-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(nlog⁡n)\mathcal{O}(\sqrt n \log n)O(n​logn); here we improve this to O(ηlog⁡η)\mathcal{O}(η\logη)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)\mathcal{O}(nη^2)O(nη2). For the task of estimating the expectation value of a general particle-preserving quadratic fermionic observable hhh, we prove a sample complexity bound of O(η∥h0∥22)\mathcal{O}(η\|h_0\|_2^2)O(η∥h0​∥22​), where h0h_0h0​ is the traceless component of hhh; the associated classical post-processing scales as O(n2η)\mathcal{O}(n^2η)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−η))U(n)/(U(η)\times U(n-η))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.