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• 11 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•Oct 20, 2022•0 citations

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.

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•3 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•4 citations

Counting interacting electrons in one dimension

Oleksiy Kashuba, Thomas L. Schmidt, Fabian Hassler +2 more

The calculation of the full counting statistics of the charge within a finite interval of an interacting one-dimensional system of electrons is a fundamental, yet as of now unresolved problem. Even in the non-interacting case, charge counting turns out to be more difficult than anticipated because it necessitates the calculation of a nontrivial determinant and requires regularization. Moreover, interactions in a one-dimensional system are best described using bosonization. However, this technique rests on a long-wavelength approximation and is a priori inapplicable for charge counting due to the sharp boundaries of the counting interval. To mitigate these problems, we investigate the counting statistics using several complementary approaches. To treat interactions, we develop a diagrammatic approach in the fermionic basis, which makes it possible to obtain the cumulant generating function up to arbitrary order in the interaction strength. Importantly, our formalism preserves charge quantization in every perturbative order. We derive an exact expression for the noise and analyze its interaction-dependent logarithmic cutoff. We compare our fermionic formalism with the results obtained by other methods, such as the Wigner crystal approach and numerical calculations using the density-matrix renormalization group. Surprisingly, we show good qualitative agreement with the Wigner crystal for weak interactions, where the latter is in principle not expected to apply.

arXiv:2305.15906•May 25, 2023•0 citations

Full counting statistics of charge in quenched quantum gases

Dávid X. Horváth, Colin Rylands

Unless constrained by symmetry, measurement of an observable on an ensemble of identical quantum systems returns a distribution of values which are encoded in the full counting statistics. While the mean value of this distribution is important for determining certain properties of a system, the full distribution can also exhibit universal behavior. In this paper we study the full counting statistics of particle number in one-dimensional interacting Bose and Fermi gases which have been quenched far from equilibrium. In particular, we consider the time evolution of the Lieb-Liniger and Gaudin-Yang models quenched from a Bose-Einstein condensate initial state and calculate the full counting statistics of the particle number within a subsystem. We show that the scaled cumulants of the charge in the initial state and at long times are simply related and, in particular, the latter are independent of the model parameters. Using the quasiparticle picture we obtain the full time evolution of the cumulants and find that although their end points are fixed, the finite-time dynamics depends strongly on the model parameters. We go on to construct the scaled cumulant generating functions and from this determine the limiting charge probability distributions at long time which are shown to exhibit distinct, nontrivial, and non-Gaussian fluctuations and large deviations. Published by the American Physical Society 2024

arXiv:2312.02929•Physical Review A•Apr 1, 2024•16 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+A1+A1+A, where AAA 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.
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.
The calculation of the full counting statistics of the charge within a finite interval of an interacting one-dimensional system of electrons is a fundamental, yet as of now unresolved problem. Even in the non-interacting case, charge counting turns out to be more difficult than anticipated because it necessitates the calculation of a nontrivial determinant and requires regularization. Moreover, interactions in a one-dimensional system are best described using bosonization. However, this technique rests on a long-wavelength approximation and is a priori inapplicable for charge counting due to the sharp boundaries of the counting interval. To mitigate these problems, we investigate the counting statistics using several complementary approaches. To treat interactions, we develop a diagrammatic approach in the fermionic basis, which makes it possible to obtain the cumulant generating function up to arbitrary order in the interaction strength. Importantly, our formalism preserves charge quantization in every perturbative order. We derive an exact expression for the noise and analyze its interaction-dependent logarithmic cutoff. We compare our fermionic formalism with the results obtained by other methods, such as the Wigner crystal approach and numerical calculations using the density-matrix renormalization group. Surprisingly, we show good qualitative agreement with the Wigner crystal for weak interactions, where the latter is in principle not expected to apply.
Unless constrained by symmetry, measurement of an observable on an ensemble of identical quantum systems returns a distribution of values which are encoded in the full counting statistics. While the mean value of this distribution is important for determining certain properties of a system, the full distribution can also exhibit universal behavior. In this paper we study the full counting statistics of particle number in one-dimensional interacting Bose and Fermi gases which have been quenched far from equilibrium. In particular, we consider the time evolution of the Lieb-Liniger and Gaudin-Yang models quenched from a Bose-Einstein condensate initial state and calculate the full counting statistics of the particle number within a subsystem. We show that the scaled cumulants of the charge in the initial state and at long times are simply related and, in particular, the latter are independent of the model parameters. Using the quasiparticle picture we obtain the full time evolution of the cumulants and find that although their end points are fixed, the finite-time dynamics depends strongly on the model parameters. We go on to construct the scaled cumulant generating functions and from this determine the limiting charge probability distributions at long time which are shown to exhibit distinct, nontrivial, and non-Gaussian fluctuations and large deviations. Published by the American Physical Society 2024