Quantum-inspired permanent identities
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.
Additional Information
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. U. C. thanks Atul Singh Arora and Pierre-Emmanuel Emeriau for interesting discussions. U. C, A. D, and S. M. acknowledge funding provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907). A. D. also acknowledges support from the National Science Foundation RAISE-TAQS 1839204 and Amazon Web Services, AWS Quantum Program.Attached Files
Published - q-2022-12-19-877.pdf
Files
| Name | Size | Download all |
|---|---|---|
|
md5:1589986846708123f65463052b199a2a
|
886.4 kB | Preview Download |
Additional details
- Eprint ID
- 119534
- Resolver ID
- CaltechAUTHORS:20230227-87934600.10
- NSF
- PHY-1733907
- NSF
- CCF-1839204
- Amazon Web Services
- AWS Quantum Program
- Created
-
2023-04-28Created from EPrint's datestamp field
- Updated
-
2023-04-28Created from EPrint's last_modified field
- Caltech groups
- Institute for Quantum Information and Matter