Quantum Circuit Representation of Combinatorial Matrix Functions
Pith reviewed 2026-05-16 08:35 UTC · model grok-4.3
The pith
A single Ising spin model generates permanents, hafnians, and loop-hafnians as quantum amplitudes and runs on O(N²)-gate circuits.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
By extending the Ising interaction structure beyond the bipartite case, transition amplitudes in the corresponding quantum spin systems become proportional to the hafnian or loop-hafnian of the interaction matrix, placing all three functions inside one unified framework based on the nested inclusion relations among the associated graph classes. The construction preserves the two-body XX form even when self-loops are present for the loop-hafnian case, and the resulting quantum spin dynamics can be simulated on a quantum circuit using only O(N²) gates.
What carries the argument
the Ising interaction graph whose adjacency encodes the matrix entries and whose quantum superposition yields the matching count as an amplitude
If this is right
- All three functions emerge from the same Ising-model family by changing only the allowed graph class.
- The full dynamics, including nontrivial state preparation for loop-hafnians, remain simulable with quadratic gate count.
- The construction directly links the combinatorial functions to observable spin-transition probabilities.
Where Pith is reading between the lines
- The mapping may allow quantum hardware to evaluate these functions on instances where classical exact computation is intractable.
- Because boson sampling hardness rests on these functions, the circuits offer a concrete route to test related quantum advantage claims on near-term devices.
- Small-N experiments comparing circuit outputs to exact classical values would directly validate or refute the amplitude correspondence.
Load-bearing premise
Self-loops required for the loop-hafnian can be added to the graph while the model still uses only pairwise XX interactions and no higher-body terms.
What would settle it
Implement the circuit for a small explicit matrix, measure the output amplitudes, and check whether they numerically equal the classically computed permanent, hafnian, or loop-hafnian of that matrix.
Figures
read the original abstract
Permanents, hafnians, and loop-hafnians are combinatorial matrix functions closely related to perfect matchings in graphs. These matrix functions arise in the quantum amplitudes of boson configurations in bosonic networks, and the classical hardness of computing them has been used to establish hardness arguments for boson sampling and Gaussian boson sampling. Remarkably, these matrix functions also appear in quantum spin systems. Previous work has shown that transition amplitudes in bipartite Ising and Heisenberg models are proportional to the permanent of the corresponding interaction matrix. Here, we extend the Ising interaction structure beyond the bipartite case to generate hafnians and loop-hafnians. This extension relies on the fact that the Ising model reflects the underlying graph structure and that each matrix function arises naturally from quantum superposition. In particular, since the graph corresponding to the loop-hafnian involves self-loops, we design the interaction structure to incorporate them while preserving the two-body XX form. Through this construction, we unify the three matrix functions within a single Ising-model framework, based on the nested inclusion relations among the corresponding classes of graphs. We further show that the quantum spin dynamics of our model, including the preparation of the nontrivial output state for the loop-hafnian case, can be simulated on a quantum circuit using only $\mathcal{O}(N^2)$ gates.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper constructs a unified Ising-model framework for permanents, hafnians, and loop-hafnians by extending bipartite XX interactions to non-bipartite graphs that include self-loops while preserving two-body form. It maps the combinatorial functions to quantum spin amplitudes via graph inclusion relations and claims that the full dynamics, including preparation of the nontrivial loop-hafnian output state, can be realized on a quantum circuit with only O(N²) gates.
Significance. If the constructions and gate-count bounds hold, the work provides a concrete quantum-circuit representation that unifies three classically hard matrix functions inside a single spin Hamiltonian. This could enable efficient simulation of specific instances and offer new routes to quantum algorithms for counting problems. The explicit preservation of two-body XX interactions and the O(N²) scaling are the strongest potential contributions.
major comments (1)
- [Quantum circuit simulation section] Abstract and § on quantum circuit simulation: the O(N²) gate bound for preparing the nontrivial output state that encodes self-loops is asserted without an explicit circuit construction, Trotterization analysis, or depth count. Because the state is a non-product superposition whose support grows with possible loops, it is unclear whether the two-body XX Hamiltonian can be realized without effective multi-qubit terms or a super-quadratic subroutine; this is load-bearing for the central simulation claim.
Simulated Author's Rebuttal
We thank the referee for their careful reading of the manuscript and for highlighting the need for greater detail on the quantum circuit construction. We address the major comment below and will incorporate the requested clarifications in the revised version.
read point-by-point responses
-
Referee: [Quantum circuit simulation section] Abstract and § on quantum circuit simulation: the O(N²) gate bound for preparing the nontrivial output state that encodes self-loops is asserted without an explicit circuit construction, Trotterization analysis, or depth count. Because the state is a non-product superposition whose support grows with possible loops, it is unclear whether the two-body XX Hamiltonian can be realized without effective multi-qubit terms or a super-quadratic subroutine; this is load-bearing for the central simulation claim.
Authors: We agree that an explicit construction strengthens the central claim. The O(N²) bound follows directly from the two-body XX interaction graph: each edge (including self-loops realized as diagonal XX terms via an ancillary qubit or on-site phase gates) corresponds to one two-qubit gate, and a dense N-vertex graph has O(N²) edges. The output state is prepared by starting from the all-zero product state and applying a fixed sequence of these XX gates (plus single-qubit rotations for phases) whose total count is bounded by the number of edges; no effective multi-qubit terms arise because the Hamiltonian remains strictly two-body. For the dynamics, first-order Trotterization of the XX Hamiltonian requires O(N²) gates per time step with depth linear in the number of steps. In the revised manuscript we will add an explicit circuit diagram, the precise gate sequence for the loop-hafnian state, and a short Trotter error analysis confirming the quadratic scaling. revision: yes
Circularity Check
Derivation self-contained with no circular reductions
full rationale
The paper extends the Ising interaction to non-bipartite graphs for hafnians and loop-hafnians by designing two-body XX couplings that incorporate self-loops while preserving the Hamiltonian form, then unifies the three matrix functions via nested graph-class inclusions. The O(N²) gate bound for simulating the full spin dynamics and preparing the loop-hafnian output state follows from standard quantum-circuit encodings of the XX Hamiltonian (e.g., Trotterization or matchgate decompositions) without any parameter fitting or redefinition of the target amplitudes. No equation equates a claimed prediction to its own input by construction, and the bipartite permanent reference is treated as external prior support rather than a self-citation chain that bears the new result. The derivation therefore remains independent of the quantities it derives.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption The Ising model reflects the underlying graph structure
- domain assumption Each matrix function arises naturally from quantum superposition
Reference graph
Works this paper leans on
-
[1]
In graph theory,haf(M) is the sum of the products of the edge weights over all perfect matchings in a simple graph with the adjacency matrixM. Thus, the transition amplitude of ˆH N between the states|ϕ 0⟩=|∅⟩and|ϕ 1⟩=|I⟩is given by ⟨ϕ1| ˆH N |ϕ0⟩=N! haf(A).(10) When the2N×2Nreal symmetric matrixAhas the form: A= O B BT O ,(11) whereOis theN×Nzero matrix ...
work page 2023
-
[2]
D. Hangleiter and J. Eisert, Computational advantage of quantum random sampling, Rev. Mod. Phys.95, 035001 (2023)
work page 2023
-
[3]
S. Aaronson and A. Arkhipov, The computational com- plexity of linear optics, inProceedings of the Forty- Third Annual ACM Symposium on Theory of Comput- ing, STOC ’11 (Association for Computing Machinery, New York, NY, USA, 2011) p. 333–342
work page 2011
-
[4]
M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White, Photonic boson sampling in a tunable circuit, Science339, 794 (2013)
work page 2013
-
[5]
J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X.-M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walms- ley, Boson sampling on a photonic chip, Science339, 798 (2013)
work page 2013
-
[6]
M. Tillmann, B. Dakić, R. Heilmann, S. Nolte, A. Sza- meit,andP.Walther,Experimentalbosonsampling,Nat. Photonics7, 540 (2013)
work page 2013
- [7]
-
[8]
J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Mat- suda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thomp- son, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, Universal linear optics, Science349, 711 (2015)
work page 2015
-
[9]
H. Wang, Y. He, Y.-H. Li, Z.-E. Su, B. Li, H.-L. Huang, X. Ding, M.-C. Chen, C. Liu, J. Qin, J.-P. Li, Y.-M. He, C. Schneider, M. Kamp, C.-Z. Peng, S. Höfling, C.-Y. Lu, and J.-W. Pan, High-efficiency multiphoton boson sampling, Nat. Photonics11, 361 (2017)
work page 2017
-
[10]
H. Wang, J. Qin, X. Ding, M.-C. Chen, S. Chen, X. You, Y.-M. He, X. Jiang, L. You, Z. Wang, C. Schneider, J. J. Renema,S.Höfling,C.-Y.Lu,andJ.-W.Pan,Bosonsam- pling with 20 input photons and a 60-mode interferome- ter in a1014-dimensional hilbert space, Phys. Rev. Lett. 123, 250503 (2019)
work page 2019
-
[11]
C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, Gaussian boson sampling, Phys. Rev. Lett.119, 170501 (2017)
work page 2017
-
[12]
N. Quesada, J. M. Arrazola, and N. Killoran, Gaussian boson sampling using threshold detectors, Phys. Rev. A 98, 062322 (2018)
work page 2018
-
[13]
H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, P. Hu, X.-Y. Yang, W.-J. Zhang, H. Li, Y. Li, X. Jiang, L. Gan, G. Yang, L. You, Z. Wang, L. Li, N.-L. Liu, C.-Y. Lu, and J.-W. Pan, Quantum computational advantage using photons, Science370, 1460 (2020)
work page 2020
-
[14]
H.-S. Zhong, L.-C. Peng, Y. Li, Y. Hu, W. Li, J. Qin, D. Wu, W. Zhang, H. Li, L. Zhang, Z. Wang, L. You, X. Jiang, L. Li, N.-L. Liu, J. P. Dowling, C.-Y. Lu, and J.-W. Pan, Experimental gaussian boson sampling, Sci. Bull.64, 511 (2019)
work page 2019
-
[15]
S. Paesani, Y. Ding, R. Santagati, L. Chakhmakhchyan, C. Vigliar, K. Rottwitt, L. K. Oxenløwe, J. Wang, M. G. Thompson, and A. Laing, Generation and sampling of quantum states of light in a silicon chip, Nat. Phys.15, 925 (2019). 10
work page 2019
-
[16]
Y. Li, L. Gan, M. Chen, Y. Chen, H. Lu, C. Lu, J. Pan, H. Fu, and G. Yang, Benchmarking 50-photon gaussian boson sampling on the sunway taihulight, IEEE Trans. Parallel Distrib. Syst.33, 1357 (2022)
work page 2022
-
[17]
J. M. Arrazola, V. Bergholm, K. Brádler, T. R. Brom- ley, M. J. Collins, I. Dhand, A. Fumagalli, T. Gerrits, A. Goussev, L. G. Helt, J. Hundal, T. Isacsson, R. B. Israel, J. Izaac, S. Jahangiri, R. Janik, N. Killoran, S. P. Kumar, J. Lavoie, A. E. Lita, D. H. Mahler, M. Menotti, B. Morrison, S. W. Nam, L. Neuhaus, H. Y. Qi, N. Que- sada, A. Repingon, K. K...
work page 2021
-
[18]
B. Fefferman, M. Foss-Feig, and A. V. Gorshkov, Exact sampling hardness of ising spin models, Phys. Rev. A96, 032324 (2017)
work page 2017
- [19]
-
[20]
Huh, Quantum estimation bound of the gaussian ma- trix permanent, Phys
J. Huh, Quantum estimation bound of the gaussian ma- trix permanent, Phys. Rev. A111, 012418 (2025)
work page 2025
-
[21]
M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations, Phys. Rev. Lett. 117, 080501 (2016)
work page 2016
- [22]
-
[23]
F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S...
work page 2019
-
[24]
Valiant, The complexity of computing the permanent, Theor
L. Valiant, The complexity of computing the permanent, Theor. Comput. Sci.8, 189 (1979)
work page 1979
-
[25]
Toda, Pp is as hard as the polynomial-time hierarchy, SIAM J
S. Toda, Pp is as hard as the polynomial-time hierarchy, SIAM J. Comput.20, 865 (1991)
work page 1991
-
[26]
S. Aaronson and D. J. Brod, Bosonsampling with lost photons, Phys. Rev. A93, 012335 (2016)
work page 2016
-
[27]
R. García-Patrón, J. J. Renema, and V. Shchesnovich, Simulating boson sampling in lossy architectures, Quan- tum3, 169 (2019)
work page 2019
-
[28]
J. Huh, G. G. Guerreschi, B. Peropadre, J. R. McClean, and A. Aspuru-Guzik, Boson sampling for molecular vi- bronic spectra, Nat. Photonics9, 615 (2015)
work page 2015
-
[29]
Y. Shen, Y. Lu, K. Zhang, J. Zhang, S. Zhang, J. Huh, and K. Kim, Quantum optical emulation of molecular vibronic spectroscopy using a trapped-ion device, Chem. Sci.9, 836 (2018)
work page 2018
-
[30]
C. S. Wang, J. C. Curtis, B. J. Lester, Y. Zhang, Y. Y. Gao, J. Freeze, V. S. Batista, P. H. Vaccaro, I. L. Chuang, L. Frunzio, L. Jiang, S. M. Girvin, and R. J. Schoelkopf, Efficient multiphoton sampling of molecular vibronic spectra on a superconducting bosonic processor, Phys. Rev. X10, 021060 (2020)
work page 2020
-
[31]
K. Brádler, S. Friedland, J. Izaac, N. Killoran, and D. Su, Graph isomorphism and gaussian boson sampling, Spec. Matrices9, 166 (2021)
work page 2021
- [32]
-
[33]
Y.-H. Deng, S.-Q. Gong, Y.-C. Gu, Z.-J. Zhang, H.-L. Liu, H. Su, H.-Y. Tang, J.-M. Xu, M.-H. Jia, M.-C. Chen, H.-S. Zhong, H. Wang, J. Yan, Y. Hu, J. Huang, W.-J. Zhang, H. Li, X. Jiang, L. You, Z. Wang, L. Li, N.-L. Liu, C.-Y. Lu, and J.-W. Pan, Solving graph problems using gaussian boson sampling, Phys. Rev. Lett.130, 190601 (2023)
work page 2023
-
[34]
S.Yu,Z.-P.Zhong,Y.Fang,R.B.Patel,Q.-P.Li,W.Liu, Z. Li, L. Xu, S. Sagona-Stophel, E. Mer, S. E. Thomas, Y. Meng, Z.-P. Li, Y.-Z. Yang, Z.-A. Wang, N.-J. Guo, W.-H. Zhang, G. K. Tranmer, Y. Dong, Y.-T. Wang, J.- S. Tang, C.-F. Li, I. A. Walmsley, and G.-C. Guo, A universal programmable gaussian boson sampler for drug discovery, Nat. Comput. Sci.3, 839 (2023)
work page 2023
-
[35]
J. M. Arrazola and T. R. Bromley, Using gaussian boson sampling to find dense subgraphs, Phys. Rev. Lett.121, 030503 (2018)
work page 2018
-
[36]
J. M. Arrazola, T. R. Bromley, and P. Rebentrost, Quan- tum approximate optimization with gaussian boson sam- pling, Phys. Rev. A98, 012322 (2018)
work page 2018
-
[37]
S. Sempere-Llagostera, R. B. Patel, I. A. Walmsley, and W. S. Kolthammer, Experimentally finding dense sub- graphsusingatime-binencodedgaussianbosonsampling device, Phys. Rev. X12, 031045 (2022)
work page 2022
- [38]
-
[39]
H. Qi, D. J. Brod, N. Quesada, and R. García-Patrón, Regimes of classical simulability for noisy gaussian boson sampling, Phys. Rev. Lett.124, 100502 (2020)
work page 2020
-
[40]
N.QuesadaandJ.M.Arrazola,Exactsimulationofgaus- sian boson sampling in polynomial space and exponential time, Phys. Rev. Res.2, 023005 (2020)
work page 2020
-
[41]
P.CliffordandR.Clifford,Theclassicalcomplexityofbo- son sampling, inProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms(SIAM,
-
[42]
H. H. Zhu, H. Sen Chen, T. Chen, Y. Li, S. B. Luo, M. F. Karim, X. S. Luo, F. Gao, Q. Li, H. Cai, L. K. Chin, L. C. Kwek, B. Nordén, X. D. Zhang, and A. Q. Liu, Large- scale photonic network with squeezed vacuum states for molecular vibronic spectroscopy, Nat. Commun.15, 6057 (2024)
work page 2024
-
[43]
J. C. Aulicino, T. Keen, and B. Peng, State prepara- tion and evolution in quantum computing: A perspective from hamiltonian moments, Int. J. Quantum Chem.122, e26853 (2022). 11
work page 2022
-
[44]
A. Björklund, B. Gupt, and N. Quesada, A faster hafnian formula for complex matrices and its benchmarking on a supercomputer (2019)
work page 2019
-
[45]
A. Bärtschi and S. Eidenbenz, Deterministic preparation of dicke states, inFundamentals of Computation Theory, edited by L. A. Gąsieniec, J. Jansson, and C. Levcopou- los (Springer International Publishing, Cham, 2019) pp. 126–139
work page 2019
-
[46]
R. Blatt and C. F. Roos, Quantum simulations with trapped ions, Nat. Phys.8, 277 (2012)
work page 2012
- [47]
-
[48]
K. Wright, K. M. Beck, S. Debnath, J. M. Amini, Y. Nam, N. Grzesiak, J.-S. Chen, N. C. Pisenti, M. Chmielewski, C. Collins, K. M. Hudek, J. Mizrahi, J. D. Wong-Campos, S. Allen, J. Apisdorf, P. Solomon, M.Williams,A.M.Ducore,A.Blinov,S.M.Kreikemeier, V. Chaplin, M. Keesan, C. Monroe, and J. Kim, Bench- marking an 11-qubit quantum computer, Nat. Commun. 10...
work page 2019
-
[49]
S. Debnath, N. M. Linke, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe, Demonstration of a small programmable quantum computer with atomic qubits, Nature536, 63 (2016)
work page 2016
- [50]
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.