Quantum-inspired permanent identities

Ulysse Chabaud1, Abhinav Deshpande1, and Saeed Mehraban2

1Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, USA
2Computer Science, Tufts University, Medford, MA 02155, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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.

Some mathematical quantities are ubiquitous in mathematics, physics, and computer science. This is the case of a combinatorial object named the permanent.

By exploiting relations between the permanent and amplitudes of linear optical quantum circuits, we show that quantum-inspired techniques provide swift proofs of many important theorems about the permanent, such as the MacMahon Master Theorem.

Our quantum-inspired proofs provide new insight for the quantum scientist on combinatorial theorems and uncover new results in quantum complexity.

► BibTeX data

► References

[1] H. Minc, ``Permanents,'', vol. 6. Cambridge University Press, 1984.

[2] J. K. Percus, ``Combinatorial methods,'', vol. 4. Springer Science & Business Media, 2012.

[3] L. G. Valiant, ``The complexity of computing the permanent,'' Theoretical computer science 8, 189–201 (1979).

[4] E. R. Caianiello, ``On quantum field theory—I: explicit solution of Dyson’s equation in electrodynamics without use of Feynman graphs,'' Il Nuovo Cimento (1943-1954) 10, 1634–1652 (1953).

[5] S. Scheel, ``Permanents in linear optical networks,'' quant-ph/​0406127.

[6] S. Aaronson and A. Arkhipov, ``The computational Complexity of Linear Optics,'' Theory of Computing 9, 143 (2013), arXiv:1011.3245.

[7] S. Aaronson, ``A linear-optical proof that the permanent is# P-hard,'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 3393–3405 (2011).

[8] S. Rahimi-Keshari, A. P. Lund, and T. C. Ralph, ``What can quantum optics say about computational complexity theory?,'' Physical review letters 114, 060501 (2015).

[9] D. Grier and L. Schaeffer, ``New hardness results for the permanent using linear optics,'' arXiv:1610.04670.

[10] P. P. Rohde, D. W. Berry, K. R. Motes, and J. P. Dowling, ``A Quantum Optics Argument for the $\#$P-hardness of a Class of Multidimensional Integrals,'' arXiv:1607.04960.

[11] L. Chakhmakhchyan, N. J. Cerf, and R. Garcia-Patron, ``Quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices,'' Physical Review A 96, 022329 (2017).

[12] A. Meiburg, ``Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography,'' arXiv:2111.03142.

[13] P. A. MacMahon, ``Combinatory Analysis, Volumes I and II,'', vol. 137. American Mathematical Soc., 2001.

[14] I. Good, ``Proofs of some ‘binomial’identities by means of MacMahon's ‘Master Theorem’,'' in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, pp. 161–162, Cambridge University Press. 1962.

[15] L. Carlitz, ``An application of MacMahon’s master theorem,'' SIAM Journal on Applied Mathematics 26, 431–436 (1974).

[16] L. Carlitz, ``Some expansions and convolution formulas related to MacMahon’s master theorem,'' SIAM Journal on Mathematical Analysis 8, 320–336 (1977).

[17] H. J. Ryser, ``Combinatorial mathematics,'', vol. 14. American Mathematical Soc., 1963.

[18] K. Balasubramanian, Combinatorics and diagonals of matrices. PhD thesis, Indian Statistical Institute-Kolkata, 1980.

[19] E. T. Bax, Finite-difference algorithms for counting problems. PhD thesis, California Institute of Technology, 1998.

[20] D. G. Glynn, ``The permanent of a square matrix,'' European Journal of Combinatorics 31, 1887–1891 (2010).

[21] P. P. Rohde, K. R. Motes, P. A. Knott, J. Fitzsimons, W. J. Munro, and J. P. Dowling, ``Evidence for the conjecture that sampling generalized cat states with linear optics is hard,'' Physical Review A 91, 012342 (2015).

[22] C. Weedbrook, S. Pirandola, R. García-Patrón, N. J. Cerf, T. C. Ralph, J. H. Shapiro, and S. Lloyd, ``Gaussian quantum information,'' Reviews of Modern Physics 84, 621 (2012).

[23] A. Leverrier, ``$SU(p, q)$ coherent states and a Gaussian de Finetti theorem,'' Journal of Mathematical Physics 59, 042202 (2018).

[24] T. Jiang and Y. Ma, ``Distances between random orthogonal matrices and independent normals,'' arXiv:1704.05205.

[25] A. C. Dixon, ``On the sum of the cubes of the coefficients in a certain expansion by the binomial theorem,'' Messenger of mathematics 20, 79–80 (1891).

[26] I. Good, ``A short proof of MacMahon's ‘Master Theorem’,'' in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, pp. 160–160, Cambridge University Press. 1962.

[27] S. Garoufalidis, T. T. Lê, and D. Zeilberger, ``The quantum MacMahon master theorem,'' Proceedings of the National Academy of Sciences 103, 13928–13931 (2006).

[28] M. Konvalinka and I. Pak, ``Non-commutative extensions of the MacMahon Master Theorem,'' Advances in Mathematics 216, 29–61 (2007).

[29] M. P. Tuite, ``Some generalizations of the MacMahon Master Theorem,'' Journal of Combinatorial Theory, Series A 120, 92–101 (2013).

[30] V. V. Kocharovsky, V. V. Kocharovsky, and S. V. Tarasov, ``The Hafnian Master Theorem,'' Linear Algebra and its Applications 144–161 (2022).

[31] W. Y. Chen, H. Galbraith, and J. Louck, ``Angular momentum theory, umbral calculus, and combinatorics,'' Computers & Mathematics with Applications 41, 1199–1214 (2001).

[32] B. M. Terhal and D. P. DiVincenzo, ``Classical simulation of noninteracting-fermion quantum circuits,'' Physical Review A 65, 032325 (2002).

[33] V. Shchesnovich, ``Partial indistinguishability theory for multiphoton experiments in multiport devices,'' Physical Review A 91, 013844 (2015).

[34] D. Spivak, M. Y. Niu, B. C. Sanders, and H. de Guise, ``Generalized interference of fermions and bosons,'' Physical Review Research 4, 023013 (2022).

[35] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin, and M. Hafezi, ``Boson Sampling for Generalized Bosons,'' arXiv:2204.08389.

[36] A. Clément, N. Heurtel, S. Mansfield, S. Perdrix, and B. Valiron, ``LO$_\text{v}$-Calculus: A Graphical Language for Linear Optical Quantum Circuits,'' arXiv:2204.11787.

[37] G. De Felice and B. Coecke, ``Quantum Linear Optics via String Diagrams,'' arXiv:2204.12985.

[38] B. Peropadre, G. G. Guerreschi, J. Huh, and A. Aspuru-Guzik, ``Proposal for microwave boson sampling,'' Physical review letters 117, 140505 (2016).

[39] S. Girvin, ``Schrödinger cat states in circuit qed,'' arXiv:1710.03179.

[40] X. Gu, A. F. Kockum, A. Miranowicz, Y.-x. Liu, and F. Nori, ``Microwave photonics with superconducting quantum circuits,'' Physics Reports 718, 1–102 (2017).

[41] J. Huh, ``A fast quantum algorithm for computing matrix permanent,'' arXiv:2205.01328.

[42] S. Aaronson and T. Hance, ``Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent,'' Quantum Info. Comput. 14, 541–559 (2014).

[43] S. Chin and J. Huh, ``Generalized concurrence in boson sampling,'' Scientific reports 8, 1–9 (2018).

[44] M.-H. Yung, X. Gao, and J. Huh, ``Universal bound on sampling bosons in linear optics and its computational implications,'' National science review 6, 719–729 (2019).

[45] V. S. Shchesnovich, ``On the classical complexity of sampling from quantum interference of indistinguishable bosons,'' International Journal of Quantum Information 18, 2050044 (2020).

[46] D. M. Jackson, ``The unification of certain enumeration problems for sequences,'' Journal of Combinatorial Theory, Series A 22, 92–96 (1977).

[47] F. R. Cardoso, D. Z. Rossatto, G. P. Fernandes, G. Higgins, and C. J. Villas-Boas, ``Superposition of two-mode squeezed states for quantum information processing and quantum sensing,'' Physical Review A 103, 062405 (2021).

[48] A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph, ``Boson sampling from a Gaussian state,'' Physical review letters 113, 100502 (2014).

[49] J. P. Olson, K. P. Seshadreesan, K. R. Motes, P. P. Rohde, and J. P. Dowling, ``Sampling arbitrary photon-added or photon-subtracted squeezed states is in the same complexity class as boson sampling,'' Physical Review A 91, 022317 (2015).

[50] C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, ``Gaussian boson sampling,'' Physical review letters 119, 170501 (2017).

[51] A. Lund, S. Rahimi-Keshari, and T. Ralph, ``Exact boson sampling using Gaussian continuous-variable measurements,'' Physical Review A 96, 022301 (2017).

[52] L. Chakhmakhchyan and N. J. Cerf, ``Boson sampling with Gaussian measurements,'' Physical Review A 96, 032326 (2017).

[53] U. Chabaud, T. Douce, D. Markham, P. van Loock, E. Kashefi, and G. Ferrini, ``Continuous-variable sampling from photon-added or photon-subtracted squeezed states,'' Physical Review A 96, 062307 (2017).

[54] N. Quesada, J. M. Arrazola, and N. Killoran, ``Gaussian boson sampling using threshold detectors,'' Physical Review A 98, 062322 (2018).

[55] A. Deshpande, A. Mehta, T. Vincent, N. Quesada, M. Hinsche, M. Ioannou, L. Madsen, J. Lavoie, H. Qi, J. Eisert, et al., ``Quantum computational advantage via high-dimensional Gaussian boson sampling,'' Science advances 8, 7894 (2022).

Cited by

[1] Erik Panzer and Karen Yeats, "Feynman symmetries of the Martin and $c_2$ invariants of regular graphs", arXiv:2304.05299, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2023-06-08 08:50:45). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2023-06-08 08:50:44).