Combinatorial Matrix Functions in Ising Models and Quantum Circuit Representation
summary
The gist
Permanents, hafnians, and loop-hafnians are combinatorial matrix functions closely related to perfect matchings in graphs.
In short
The paper extends Ising models beyond bipartite interactions to unify three combinatorial matrix functions: permanents, hafnians, and loop-hafnians. It shows these functions arise from nested graph structures and provides a quantum circuit simulation for the loop-hafnian state using only $O(N^2)$ gates.
Key concepts
- Permanents
- A permanent is a combinatorial function calculated by summing the products of all edge weights over every perfect matching in a graph. It is known to be computationally hard, which has been used to prove hardness for boson sampling.
- Hafnians and Loop-Hafnians
- These are other combinatorial matrix functions related to perfect matchings, generalized from the permanent. The paper shows they can all emerge within a single Ising model framework by extending the graph structure beyond bipartite constraints, unifying them through nested inclusion relations.
- Quantum Simulation Complexity
- The paper demonstrates that the quantum dynamics of this extended Ising model can be simulated on a quantum circuit using only $O(N^2)$ gates. This efficiency is achieved by mapping the loop-hafnian state to a basis state and utilizing adaptive measurements for simultaneous state extraction.
Terminology used across episodes
This episode discusses
- Combinatorial Matrix Functions in Ising Models and Quantum Circuit Representation · Paper Radio
- The hardness of quantum spin dynamics
- Doubling Qubits in a Trapped-Ion System via Vibrational Dual-Rail Encoding
The paper
Combinatorial Matrix Functions in Ising Models and Quantum Circuit Representation · Read on arXiv
Minhyeok Kang, Gwonhak Lee, Youngrong Lim, ŽJoonsuk Huh
SKKU Advanced Institute of Nanotechnology at Sungkyunkwan University · IBM Quantum · Department of Physics at Chungbuk National University Department of Chemistry at Yonsei University Department of Quantum Information at Yonsei University
Permanents, hafnians, and loop-hafnians are combinatorial matrix functions defined on the perfect matchings of graphs. These matrix functions arise in the quantum amplitudes for output photon configurations in linear optical networks, which has led both to sampling hardness results and to a variety of applications. The same matrix functions also appear in Ising models, since Ising models naturally encode graphs, and the matrix functions emerge from quantum interference. However, previous results have been restricted to balanced bipartite graphs, and hence to the permanent. In this paper, we extend the graph structure of the Ising model so that all three matrix functions can be obtained. In particular, self-loops can be encoded by introducing additional spins, and the loop-hafnian is obtained from a superposition of spin states, which we call the loop-hafnian state. We show how to recover the hafnian and permanent cases as the number of self-loops decreases. Moreover, we show that the Ising dynamics we consider can be simulated on a quantum circuit with O(n 2) gates for a 2n times 2n real symmetric matrix. Specifically, we propose a quantum circuit that maps the loop-hafnian state to a basis state with O(n 2) gates, and show that, by an adaptive measurement, the loop-hafnian states for all subsets of vertices can be measured simultaneously.
Transcript
Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.
Kai: We're looking at the paper: "Combinatorial Matrix Functions in Ising Models and Quantum Circuit Representation".
Mira: Here's the gist of the paper. Permanents, hafnians, and loop-hafnians are combinatorial matrix functions closely related to perfect matchings in graphs.
Kai: 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.
Mira: Remarkably, these matrix functions also appear in quantum spin systems.
Kai: Here, we extend the Ising interaction structure beyond the bipartite case to generate hafnians and loop-hafnians.
Paper summary: Kai: So, looking at the whole paper, what should we take away about this work on Combinatorial Matrix Functions in Ising Models and Quantum Circuit Representation?
Mira: The main thing is the unification. They successfully show how they can unify permanents, hafnians, and loop-hafnians within a single Ising model framework based on graph structure <ref:2602.01868#pg2>.
Lev: And the simulation aspect is concrete because they give us an O N squared gate count for the quantum circuit used to prepare the loop-hafnian state <ref:2602.01868#pg3>. That’s a tangible number for hardware planning.
Kai: It means that even with these more complex functions, we have a way to simulate them on current or near-future quantum computers using that level of gate count <ref:2602.01868#pg3>.
Mira: And they show how this relates back to the original problems in bosonic networks and quantum spin systems, tying the theoretical hardness results to physical models we already study <ref:2602.01868#pg1>.
Lev: The limitation is that for the loop-hafnian case, you have to deal with those extra spins and a nontrivial output state <ref:2602.01868#pg2>. That means real hardware will face overhead from preparing that specific state <ref:2602.01868#pg3>.
Kai: So, the paper gives us a unified view of these matrix functions and shows a circuit simulation path for them, even if it requires those extra spins for the loop-hafnian version <ref:2602.01868#pg3>.
Conclusion: Kai: So, we've been looking at how permanents, hafnians, and loop-hafnians show up in these spin models today <ref:2602.01868#pg1>. Now we're wrapping up with the conclusion and what this whole paper actually means for us.
Mira: It boils down to them taking these three different mathematical structures—permanents, hafnians, and loop-hafnians—and showing they all come from the same underlying graph idea <ref:2602.01868#pg2>. They build this unified framework using the nested inclusion relationships between the types of graphs involved.
Lev: And then they show that even though you have these complex states like the loop-hafnian, you can prepare them on a quantum circuit using only big O of n squared gates <ref:2602.01868#pg3>. That's the simulation part for us.
Kai: So what does this mean in practice for someone building hardware? It means that if we want to simulate these kinds of complex quantum dynamics, we have a path that scales with n squared gates, which is manageable <ref:2602.01868#pg3>. But the loop-hafnian part still needs those extra spins and a specific state preparation routine <ref:2602.01868#pg2>.
Mira: The implication is that we can move beyond just bipartite graphs, which was the old limitation, to model more realistic physical systems using this unified Ising setup. It connects the theoretical hardness of these functions to actual quantum spin dynamics.
Lev: For error correction, this helps us understand the complexity of simulating those dynamics because they've mapped out a way to get there efficiently in terms of circuit depth <ref:2602.01868#pg3>. But we still need to figure out how much overhead that state preparation actually adds to our physical system.
Kai: It suggests that the output state doesn't have to be some simple computational basis state, which is a big deal for how we think about what a quantum computer can actually produce <ref:2602.01868#pg4>. This opens up new ways to look at things like IQP circuits, which is where they point next.
More episodes
- 2603.29754-Coherent and dissipative energy transfer in driven open quantum systems: a driven quantum master equation approach
- 2604.01157-Thermal Entanglement and Out-of-Equilibrium Thermodynamics in 1D Bose Gases
- 2604.06410-Directional and correlated optical emission from a waveguide-engineered molecule with local control
- 2604.07214-Quantum Gibbs sampling through the detectability lemma
- 2604.13165-Finite-size Entanglement Certification via Third-Order Local Randomized Measurements
- 2604.18542-Dissipative Preparation of Correlated Quantum States in Dipolar Rydberg Arrays
- 2605.00096-Scalable spin-nematic squeezing in multi-level dipole-interacting Rydberg atom arrays
- 2605.02565-Sample-Based Quantum Diagonalization with Amplitude Amplification
- 2605.20111-Mechanism of wavefunction collapse in measurements of separated quantum subsystems
- 2606.05097-No-Go Theorem for Gaussian Quantum Repeaters from Fractional Extendibility