Permanents in linear optical networks
Open accessAbstract
We develop an abstract look at linear optical networks from the viewpoint of combinatorics and permanents. In particular we show that calculation of matrix elements of unitarily transformed photonic multi-mode states is intimately linked to the computation of permanents. An implication of this remarkable fact is that all calculations that are based on evaluating matrix elements are generically computationally hard. Moreover, quantum mechanics provides simpler derivations of certain matrix analysis results which we exemplify by showing that the permanent of any unitary matrix takes its values across the unit disk in the complex plane.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Correlations resulting from quantum interference of multiple indistinguishable non-interacting bosons in large linear optical circuits cannot be efficiently simulated with classical computers.
“Correlations resulting from quantum interference of multiple indistinguishable non-interacting bosons in large linear optical circuits cannot be efficiently simulated with classical computers192021.”
From Observing fermionic statistics with photons in arbitrary processes (2013) · cites this paper as [19]
The Introduction (p. 1) says that calculating matrix elements for transformed multi-mode photonic states, and calculations based on them, is computationally expensive and cannot be done in polynomial time. Section III (p. 3) links that difficulty to computing permanents. These passages support the difficulty of calculating optical-network outcomes, but do not establish the broader claim that the resulting correlations cannot be efficiently simulated classically. (LLM, conf=0.83)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 2
- [9]W. Vogel, D.-G. Welsch, and S. Wallentowitz, Quantum Optics, An Introduction (Wiley-VCH, Berlin, 2001).
- [12]J. Eisert, K. Jacobs, P. Papadopoulos, and M.B. Plenio, Phys. Rev. A 62 , 052317 (2000); P. Zanardi, C. Zalka, and L. Faoro, Phys. Rev. A 62 , 030301(R) (2000); M.A. Nielsen, C.M. Dawson, J.L. Dodd, A. Gilchrist, D. Mortimer, T.J. Osborne, M.J. Bremner, A.W. Harrow, and A. Hines, Phys. Rev. A 67 , 052301 (2003); C.H. Bennett, A.W. Harrow, D.W. Leung, J.A. Smolin, IEEE Trans. Inf. Theory, 49 , 1895 (2003).
Cited by
Sorted by citations
The computational complexity of linear optics
Aaronson, S., & Arkhipov, A. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993682 · Cited by 874 · see citing works
Integrated multimode interferometers with arbitrary designs for photonic boson sampling
Crespi, A., Osellame, R., Ramponi, R., Brod, D. J., Galvão, E. F., Spagnolo, N., Vitelli, C., Maiorino, E., Mataloni, P., & Sciarrino, F. (2013) · Nature Photonics · doi:10.1038/nphoton.2013.112 · Cited by 662 · see citing works
Hamilton, C. S., Kruse, R., Sansoni, L., Barkhofen, S., Silberhorn, C., & Jex, I. (2017) · Physical Review Letters · doi:10.1103/physrevlett.119.170501 · Cited by 503 · see citing works
Boson sampling for molecular vibronic spectra
Huh, J., Guerreschi, G. G., Peropadre, B., McClean, J. R., & Aspuru-Guzik, A. (2015) · Nature Photonics · doi:10.1038/nphoton.2015.153 · Cited by 341 · see citing works
Multimode quantum interference of photons in multiport integrated devices
Peruzzo, A., Laing, A., Politi, A., Rudolph, T., & O'Brien, J. L. (2011) · Nature Communications · doi:10.1038/ncomms1228 · Cited by 212 · see citing works
Photonic implementation of boson sampling: a review
Brod, D. J., Galvão, E. F., Crespi, A., Osellame, R., Spagnolo, N., & Sciarrino, F. (2019) · Advanced Photonics · doi:10.1117/1.ap.1.3.034001 · Cited by 159 · see citing works
Computational advantage of quantum random sampling
Hangleiter, D., & Eisert, J. (2023) · Reviews of Modern Physics · doi:10.1103/revmodphys.95.035001 · Cited by 145 · see citing works
Observing fermionic statistics with photons in arbitrary processes
Matthews, J. C. F., Poulios, K., Meinecke, J. D. A., Politi, A., Peruzzo, A., Ismail, N., Wörhoff, K., Thompson, M. G., & O'Brien, J. L. (2013) · Scientific Reports · doi:10.1038/srep01539 · Cited by 98 · see citing works
“Correlations resulting from quantum interference of multiple indistinguishable non-interacting bosons in large linear optical circuits cannot be efficiently simulated with classical computers [19–21].”
BackgroundGeneralized Hong–Ou–Mandel experiments with bosons and fermions
Lim, Y. L., & Beige, A. (2005) · New Journal of Physics · doi:10.1088/1367-2630/7/1/155 · Cited by 90 · see citing works
- Authors
- Scheel, S.
- Affiliations
- Imperial College London (GB)
- Corresponding author
- Scheel, Stefan
- ORCID
- Scheel, Stefan
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2004
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- quant-ph/0406127
- OpenAlex
- W1596617327
- Cited by
- 94
- References
- 0
- Citations by year
- 2026: 3 · 2025: 1 · 2024: 4 · 2023: 10 · 2022: 6 · 2021: 11 · 2020: 3 · 2019: 8 · 2018: 7 · 2017: 9 · 2016: 4 · 2015: 8 · 2014: 7 · 2013: 3 · 2012: 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Engineering and Physical Sciences Research Council
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
- Keywords
- permanent, linear optical networks, unitary matrices, matrix elements, computational hardness, quantum mechanics
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
