Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2602.01868

Combinatorial Matrix Functions in Ising Models and Quantum Circuit Representation

Minhyeok Kang, Gwonhak Lee, Youngrong Lim, Joonsuk Huh

quant-phSubmitted Feb 2, 2026• Announced Feb 3, 2026• 0 citations• Revised Oct 30, 2026 (v3)
v1 · Feb 2, 2026v2 · May 12, 2026v3 · Oct 30, 2026
arXivHTMLPDF

Abstract

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.

Comments
10 pages, 3 figures

Related papers

Connecting quantum circuit amplitudes and matrix permanents through polynomials

Hugo Thomas, Pierre-Emmanuel Emeriau, Rawad Mezher

In this paper, we strengthen the connection between qubit-based quantum circuits and photonic quantum computation. Within the framework of circuit-based quantum computation, the sum-over-paths interpretation of quantum probability amplitudes leads to the emergence of sums of exponentiated polynomials. In contrast, the matrix permanent is a combinatorial object that plays a crucial role in photonic by describing the probability amplitudes of linear optical computations. To connect the two, we introduce a general method to encode an $\mathbb F_2$-valued polynomial with complex coefficients into a graph, such that the permanent of the resulting graph's adjacency matrix corresponds directly to the amplitude associated the polynomial in the sum-over-path framework. This connection allows one to express quantum amplitudes arising from qubit-based circuits as permanents, which can naturally be estimated on a photonic quantum device.

arXiv:2408.08857•Aug 16, 2024•0 citations

Quantum experiments and graphs II: Quantum interference, computation, and state generation

Xuemei Gu, Manuel Erhard, Anton Zeilinger +1 more

We present an approach to describe state-of-the-art photonic quantum experiments using graph theory. There, the quantum states are given by the coherent superpositions of perfect matchings. The crucial observation is that introducing complex weights in graphs naturally leads to quantum interference. This viewpoint immediately leads to many interesting results, some of which we present here. First, we identify an experimental unexplored multiphoton interference phenomenon. Second, we find that computing the results of such experiments is #P-hard, which means it is a classically intractable problem dealing with the computation of a matrix function Permanent and its generalization Hafnian. Third, we explain how a recent no-go result applies generally to linear optical quantum experiments, thus revealing important insights into quantum state generation with current photonic technology. Fourth, we show how to describe quantum protocols such as entanglement swapping in a graphical way. The uncovered bridge between quantum experiments and graph theory offers another perspective on a widely used technology and immediately raises many follow-up questions.

arXiv:1803.10736•Proceedings of the National Academy of Sciences•Feb 15, 2019•71 citations

Quantum-inspired permanent identities

Ulysse Chabaud, Abhinav Deshpande, Saeed Adel Mehraban

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.

arXiv:2208.00327•Quantum•Dec 19, 2022•13 citations

Heisenberg picture tensor network formalism for optical circuits

Dario Cilluffo, Matthias Kost, Nicola Lorenzoni +1 more

Tensor network formalisms have emerged as powerful tools for simulating quantum state evolution. While widely applied in the study of optical quantum circuits, such as boson sampling, existing tensor network approaches fail to address the complexity mismatch between tensor contractions and the calculation of photon-counting probability amplitudes. Here, we present an alternative tensor network framework that exploits the input-output relations of quantum optical circuits encoded in the unitary interferometer matrix. Our approach bridges the complexity gap by enabling the computation of the permanent—central to boson sampling—with the same computational complexity as the best known classical algorithm based on a graphical representation of the operator-basis matrix product states that we introduce. Furthermore, we exploit the flexibility of tensor networks to extend our formalism to incorporate partial distinguishability and photon loss, two key imperfections in practical interferometry experiments. This work offers a significant step forward in the simulation of large-scale quantum optical systems and the understanding of their computational complexity.

arXiv:2502.01737•Physical Review Research•Mar 27, 2026•2 citations

Imperfect Graphs from Unitary Matrices -- I

Wesley Lewis, Darsh Pareek, Umesh Kumar +1 more

Matrix representations of quantum operators are computationally complete but often obscure the structural topology of information flow within a quantum circuit \cite{nielsen2000}. In this paper, we introduce a generalized graph-theoretic framework for analyzing quantum operators by mapping unitary matrices to directed graphs; we term these structures \emph{Imperfect Graphs} or more formally as \emph{Topological Structure of Superpositions}(TSS) as a tool to devise better Quantum Algorithms. In this framework, we represent computational basis states as vertices. A directed edge exists between two vertices if and only if there is a non-zero amplitude transition between them, effectively mapping the support of the unitary operator. In this paper we deliberately discard probability amplitudes and phase information to isolate the connectivity and reachability properties of the operator. We demonstrate how TSS intuitively helps describe gates such as the Hadamard, Pauli-(X,Y,Z) gates, etc \cite{nielsen2000}. This framework provides a novel perspective for viewing quantum circuits as discrete dynamical systems \cite{childs2009,aharonov2001} Keywords: Quantum Algorithms, Unitary Matrix Approach, Topological Structure of Superpositions (TSS), Graph Theory

quant-pharXiv:2602.21808•Feb 26, 2026•1 citation

Simulating lossy and partially distinguishable quantum optical circuits: theory, algorithms, and applications to experiment validation and state preparation

Jacob F. F. Bulmer, Javier Martínez-Cifuentes, Bryn A. Bell +1 more

To understand quantum optics experiments, we must perform calculations that consider the principal sources of noise, such as losses, spectral impurity, and partial distinguishability. In both discrete and continuous variable systems, these can be modeled as mixed Gaussian states over multiple modes. The modes are not all resolved by photon-number measurements and so require calculations on coarse-grained photon-number distributions. Existing methods can lead to a combinatorial explosion in the time complexity, making this task unfeasible for even moderately sized experiments of interest. We prove that the computation of this type of distribution can be done in exponential time, providing a combinatorial speed-up. We develop numerical techniques that allow us to determine coarse-grained photon number distributions of Gaussian states, as well as density matrix elements of heralded non-Gaussian states prepared in the presence of spectral impurity and partial distinguishability. These results offer significant speed-up and accuracy improvements to validation tests of both Fock and Gaussian boson samplers that rely on binned probability distributions. Moreover, they pave the way to a more efficient simulation of realistic photonic circuits, unlocking the ability to perform exact calculations at scales that were previously out of reach. In addition, our results, including loop Hafnian master theorems, may be of interest to the fields of combinatorics and graph theory.

arXiv:2412.17742•Advanced Photonics•Feb 18, 2026•15 citations
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.
In this paper, we strengthen the connection between qubit-based quantum circuits and photonic quantum computation. Within the framework of circuit-based quantum computation, the sum-over-paths interpretation of quantum probability amplitudes leads to the emergence of sums of exponentiated polynomials. In contrast, the matrix permanent is a combinatorial object that plays a crucial role in photonic by describing the probability amplitudes of linear optical computations. To connect the two, we introduce a general method to encode an F2\mathbb F_2F2​-valued polynomial with complex coefficients into a graph, such that the permanent of the resulting graph's adjacency matrix corresponds directly to the amplitude associated the polynomial in the sum-over-path framework. This connection allows one to express quantum amplitudes arising from qubit-based circuits as permanents, which can naturally be estimated on a photonic quantum device.
We present an approach to describe state-of-the-art photonic quantum experiments using graph theory. There, the quantum states are given by the coherent superpositions of perfect matchings. The crucial observation is that introducing complex weights in graphs naturally leads to quantum interference. This viewpoint immediately leads to many interesting results, some of which we present here. First, we identify an experimental unexplored multiphoton interference phenomenon. Second, we find that computing the results of such experiments is #P-hard, which means it is a classically intractable problem dealing with the computation of a matrix function Permanent and its generalization Hafnian. Third, we explain how a recent no-go result applies generally to linear optical quantum experiments, thus revealing important insights into quantum state generation with current photonic technology. Fourth, we show how to describe quantum protocols such as entanglement swapping in a graphical way. The uncovered bridge between quantum experiments and graph theory offers another perspective on a widely used technology and immediately raises many follow-up questions.
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.
Tensor network formalisms have emerged as powerful tools for simulating quantum state evolution. While widely applied in the study of optical quantum circuits, such as boson sampling, existing tensor network approaches fail to address the complexity mismatch between tensor contractions and the calculation of photon-counting probability amplitudes. Here, we present an alternative tensor network framework that exploits the input-output relations of quantum optical circuits encoded in the unitary interferometer matrix. Our approach bridges the complexity gap by enabling the computation of the permanent—central to boson sampling—with the same computational complexity as the best known classical algorithm based on a graphical representation of the operator-basis matrix product states that we introduce. Furthermore, we exploit the flexibility of tensor networks to extend our formalism to incorporate partial distinguishability and photon loss, two key imperfections in practical interferometry experiments. This work offers a significant step forward in the simulation of large-scale quantum optical systems and the understanding of their computational complexity.
Matrix representations of quantum operators are computationally complete but often obscure the structural topology of information flow within a quantum circuit \cite{nielsen2000}. In this paper, we introduce a generalized graph-theoretic framework for analyzing quantum operators by mapping unitary matrices to directed graphs; we term these structures \emph{Imperfect Graphs} or more formally as \emph{Topological Structure of Superpositions}(TSS) as a tool to devise better Quantum Algorithms. In this framework, we represent computational basis states as vertices. A directed edge exists between two vertices if and only if there is a non-zero amplitude transition between them, effectively mapping the support of the unitary operator. In this paper we deliberately discard probability amplitudes and phase information to isolate the connectivity and reachability properties of the operator. We demonstrate how TSS intuitively helps describe gates such as the Hadamard, Pauli-(X,Y,Z) gates, etc \cite{nielsen2000}. This framework provides a novel perspective for viewing quantum circuits as discrete dynamical systems \cite{childs2009,aharonov2001} Keywords: Quantum Algorithms, Unitary Matrix Approach, Topological Structure of Superpositions (TSS), Graph Theory
To understand quantum optics experiments, we must perform calculations that consider the principal sources of noise, such as losses, spectral impurity, and partial distinguishability. In both discrete and continuous variable systems, these can be modeled as mixed Gaussian states over multiple modes. The modes are not all resolved by photon-number measurements and so require calculations on coarse-grained photon-number distributions. Existing methods can lead to a combinatorial explosion in the time complexity, making this task unfeasible for even moderately sized experiments of interest. We prove that the computation of this type of distribution can be done in exponential time, providing a combinatorial speed-up. We develop numerical techniques that allow us to determine coarse-grained photon number distributions of Gaussian states, as well as density matrix elements of heralded non-Gaussian states prepared in the presence of spectral impurity and partial distinguishability. These results offer significant speed-up and accuracy improvements to validation tests of both Fock and Gaussian boson samplers that rely on binned probability distributions. Moreover, they pave the way to a more efficient simulation of realistic photonic circuits, unlocking the ability to perform exact calculations at scales that were previously out of reach. In addition, our results, including loop Hafnian master theorems, may be of interest to the fields of combinatorics and graph theory.