Quantum-inspired permanent identities
arXiv:2208.00327 · doi:10.22331/q-2022-12-19-877
Abstract
The permanent is pivotal to both complexity theory and combinatorics. In quantum computing, the permanent appears in the expression of output amplitudes of linear optical computations, such as in the Boson Sampling model. Taking advantage of this connection, we give quantum-inspired proofs of many existing as well as new remarkable permanent identities. Most notably, we give a quantum-inspired proof of the MacMahon master theorem as well as proofs for new generalizations of this theorem. Previous proofs of this theorem used completely different ideas. Beyond their purely combinatorial applications, our results demonstrate the classical hardness of exact and approximate sampling of linear optical quantum computations with input cat states.
arXiv comment33 pages, comments are welcome!
References in corpus (22)
- Gaussian Quantum Information
- Microwave photonics with superconducting quantum circuits
- Gaussian Boson Sampling
- Classical simulation of noninteracting-fermion quantum circuits
- Boson Sampling from Gaussian States
- Gaussian Boson Sampling using threshold detectors
- Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
- Partial indistinguishability theory for multi-photon experiments in multiport devices
- What can quantum optics say about computational complexity theory?
- A Linear-Optical Proof that the Permanent is #P-Hard
- Microwave Boson Sampling
- Boson sampling with Gaussian measurements
- Superposition of two-mode squeezed states for quantum information processing and quantum sensing
- Sampling arbitrary photon-added or photon-subtracted squeezed states is in the same complexity class as boson sampling
- Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
- Sampling generalized cat states with linear optics is probably hard
- Generalized concurrence in boson sampling
- Exact Boson Sampling using Gaussian continuous variable measurements
- A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices
- coherent states and a Gaussian de Finetti theorem
- Boson Sampling for Generalized Bosons
- Generalized Interference of Fermions and Bosons
Cited by in corpus (5)
- Simulation of quantum optics by coherent state decomposition
- Approximating outcome probabilities of linear optical circuits
- Entanglement in the full state vector of boson sampling
- Quantum estimation bound of Gaussian matrix permanent
- Boson-fermion complementarity in a linear interferometer: An identity relating the determinant and permanent of a matrix