SciPost Submission Page
Polynomial computational complexity of matrix elements of finite-rank-generated single-particle operators in products of finite bosonic states
by Dmitri A. Ivanov
This Submission thread is now published as
Submission summary
| Authors (as registered SciPost users): | Dmitri Ivanov |
| Submission information | |
|---|---|
| Preprint Link: | https://arxiv.org/abs/2210.11568v2 (pdf) |
| Date accepted: | 2024-04-02 |
| Date submitted: | 2023-09-10 23:06 |
| Submitted by: | Ivanov, Dmitri |
| Submitted to: | SciPost Physics Core |
| Ontological classification | |
|---|---|
| Academic field: | Physics |
| Specialties: |
|
| Approach: | Theoretical |
Abstract
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.
Published as SciPost Phys. Core 7, 022 (2024)
Reports on this Submission
Strengths
1) Extremely clearly written
2) Short
3) All results are presented in a clear and concise manner
4) Results are important for the specific field of computational complexity of quantum amplitudes. However, the techniques used are universal and are of interest to wide audience.
5) Written as a self-contained article
Weaknesses
No weaknesses
Report
I think that the journal criteria are met. The manuscript is very nice and is a pleasure to read. It is based on the previous works of the author (Refs. 4,5) but significantly improves complexity estimates and generalizes them for a much wider class of quantum states.
I suggest to publish the manuscript in its current form.
Requested changes
No changes are requested.