pith. sign in

arxiv: 2602.01868 · v2 · submitted 2026-02-02 · 🪐 quant-ph

Quantum Circuit Representation of Combinatorial Matrix Functions

Pith reviewed 2026-05-16 08:35 UTC · model grok-4.3

classification 🪐 quant-ph
keywords permanentshafniansloop-hafniansIsing modelsquantum circuitsboson samplinggraph matchingscombinatorial functions
0
0 comments X

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.

The paper establishes that the three combinatorial matrix functions arise as transition amplitudes in one family of Ising models whose interaction graphs belong to nested classes. Bipartite graphs without loops recover the permanent, general graphs without loops recover the hafnian, and graphs with self-loops recover the loop-hafnian. Because every case uses only two-body XX interactions, the full spin dynamics—including preparation of the required output state for the loop-hafnian—map directly onto a quantum circuit whose gate count scales as O(N²).

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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

Figures reproduced from arXiv: 2602.01868 by Gwonhak Lee, Joonsuk Huh, Minhyeok Kang, Youngrong Lim.

Figure 1
Figure 1. Figure 1: FIG. 1: Graphical summary of the correspondences between matrix functions, graph structures, bosonic networks, [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2: Diagram of our quantum spin model with [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3: (a) the quantum circuit for the operator [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

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)
  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

1 responses · 0 unresolved

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
  1. 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

0 steps flagged

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

0 free parameters · 2 axioms · 0 invented entities

The abstract invokes two domain assumptions about how Ising interactions encode graphs and how superposition produces the combinatorial sums; no free parameters or new physical entities are introduced.

axioms (2)
  • domain assumption The Ising model reflects the underlying graph structure
    Invoked to justify extending the interaction graph beyond bipartite cases while preserving XX couplings.
  • domain assumption Each matrix function arises naturally from quantum superposition
    Used to argue that the spin amplitudes directly encode the permanent, hafnian, or loop-hafnian sums.

pith-pipeline@v0.9.0 · 5536 in / 1447 out tokens · 30187 ms · 2026-05-16T08:35:01.702053+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

50 extracted references · 50 canonical work pages

  1. [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 ...

  2. [2]

    Hangleiter and J

    D. Hangleiter and J. Eisert, Computational advantage of quantum random sampling, Rev. Mod. Phys.95, 035001 (2023)

  3. [3]

    Aaronson and A

    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

  4. [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)

  5. [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)

  6. [6]

    Tillmann, B

    M. Tillmann, B. Dakić, R. Heilmann, S. Nolte, A. Sza- meit,andP.Walther,Experimentalbosonsampling,Nat. Photonics7, 540 (2013)

  7. [7]

    Crespi, R

    A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvão,N.Spagnolo,C.Vitelli,E.Maiorino,P.Mataloni, and F. Sciarrino, Integrated multimode interferometers with arbitrary designs for photonic boson sampling, Nat. Photonics7, 545 (2013)

  8. [8]

    Carolan, C

    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)

  9. [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)

  10. [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)

  11. [11]

    C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, Gaussian boson sampling, Phys. Rev. Lett.119, 170501 (2017)

  12. [12]

    Quesada, J

    N. Quesada, J. M. Arrazola, and N. Killoran, Gaussian boson sampling using threshold detectors, Phys. Rev. A 98, 062322 (2018)

  13. [13]

    Zhong, H

    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)

  14. [14]

    Zhong, L.-C

    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)

  15. [15]

    Paesani, Y

    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

  16. [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)

  17. [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...

  18. [18]

    Fefferman, M

    B. Fefferman, M. Foss-Feig, and A. V. Gorshkov, Exact sampling hardness of ising spin models, Phys. Rev. A96, 032324 (2017)

  19. [19]

    C.-Y. Park, P. A. M. Casares, J. M. Arrazola, and J. Huh, The hardness of quantum spin dynamics (2023), arXiv:2312.07658 [quant-ph]

  20. [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)

  21. [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)

  22. [22]

    Boixo, S

    S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Characterizing quantum supremacy in near- term devices, Nat. Phys.14, 595 (2018)

  23. [23]

    Arute, K

    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...

  24. [24]

    Valiant, The complexity of computing the permanent, Theor

    L. Valiant, The complexity of computing the permanent, Theor. Comput. Sci.8, 189 (1979)

  25. [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)

  26. [26]

    Aaronson and D

    S. Aaronson and D. J. Brod, Bosonsampling with lost photons, Phys. Rev. A93, 012335 (2016)

  27. [27]

    García-Patrón, J

    R. García-Patrón, J. J. Renema, and V. Shchesnovich, Simulating boson sampling in lossy architectures, Quan- tum3, 169 (2019)

  28. [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)

  29. [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)

  30. [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)

  31. [31]

    Brádler, S

    K. Brádler, S. Friedland, J. Izaac, N. Killoran, and D. Su, Graph isomorphism and gaussian boson sampling, Spec. Matrices9, 166 (2021)

  32. [32]

    Banchi, M

    L. Banchi, M. Fingerhuth, T. Babej, C. Ing, and J. M. Arrazola, Molecular docking with gaussian boson sam- pling, Sci. Adv.6, eaax1950 (2020)

  33. [33]

    Deng, S.-Q

    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)

  34. [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)

  35. [35]

    J. M. Arrazola and T. R. Bromley, Using gaussian boson sampling to find dense subgraphs, Phys. Rev. Lett.121, 030503 (2018)

  36. [36]

    J. M. Arrazola, T. R. Bromley, and P. Rebentrost, Quan- tum approximate optimization with gaussian boson sam- pling, Phys. Rev. A98, 012322 (2018)

  37. [37]

    Sempere-Llagostera, R

    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)

  38. [38]

    Schuld, K

    M. Schuld, K. Brádler, R. Israel, D. Su, and B. Gupt, Measuring the similarity of graphs with a gaussian boson sampler, Phys. Rev. A101, 032314 (2020)

  39. [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)

  40. [40]

    N.QuesadaandJ.M.Arrazola,Exactsimulationofgaus- sian boson sampling in polynomial space and exponential time, Phys. Rev. Res.2, 023005 (2020)

  41. [41]

    P.CliffordandR.Clifford,Theclassicalcomplexityofbo- son sampling, inProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms(SIAM,

  42. [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)

  43. [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

  44. [44]

    Björklund, B

    A. Björklund, B. Gupt, and N. Quesada, A faster hafnian formula for complex matrices and its benchmarking on a supercomputer (2019)

  45. [45]

    Bärtschi and S

    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

  46. [46]

    Blatt and C

    R. Blatt and C. F. Roos, Quantum simulations with trapped ions, Nat. Phys.8, 277 (2012)

  47. [47]

    Monroe, W

    C. Monroe, W. C. Campbell, L.-M. Duan, Z.-X. Gong, A. V. Gorshkov, P. W. Hess, R. Islam, K. Kim, N. M. Linke, G. Pagano, P. Richerme, C. Senko, and N. Y. Yao, Programmable quantum simulations of spin systems with trapped ions, Rev. Mod. Phys.93, 025001 (2021)

  48. [48]

    Wright, K

    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...

  49. [49]

    Debnath, N

    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)

  50. [50]

    M. Kang, W. Chen, H. Kwon, K. Kim, and J. Huh, Dou- bling Qubits in a Trapped-Ion System via Vibrational Dual-Rail Encoding, arXiv:2505.12937 (2025)