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•61 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•11 citations

Low depth quantum circuits for Ising models

S. Iblisdir, Mauro Cirio, Octavi Boada +1 more

A scheme for measuring complex temperature partition functions of Ising models is introduced. In the context of ordered qubit registers this scheme finds a natural translation in terms of global operations, and single particle measurements on the edge of the array. Two applications of this scheme are presented. First, through appropriate Wick rotations, those amplitudes can be analytically continued to yield esti-mates for partition functions of Ising models. Bounds on the estimation error, valid with high confidence, are provided and shown to be compatible with previous results. Interestingly, the kind of state prepa-rations and measurements involved in this application can in principle be made “instantaneous", i.e. independent of the system size or the parameters being simulated. Second, the scheme allows to accu-rately estimate some non-trivial invariants of links. A third result concerns the computational power of estimations of partition functions for real temperature classical ferromagnetic Ising models on a square lattice. We provide conditions under which estimating such partition functions allow to reconstruct scat-tering amplitudes of quantum circuits making the problem BQP-hard. Using this mapping, we show that wavefunction overlaps for ground states of quantum Hamiltonians, which can serve as a witness to quantum phase transitions, can be estimated from classical Ising model partition functions. Finally, we show that the ability to accurately measure corner magnetisations on thermal states of two-dimensional Ising models with magnetic field leads to fully polynomial random approximation schemes (FPRAS) for the partition function. Each of these results corresponds to a section of the text that can be essentially read independently. 1

•Jan 1, 2014•12 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•0 citations

Solving graph problems with single-photons and linear optics

Rawad Mezher, Ana Filipa Carvalho, Shane Mansfield

An important challenge for current and near-term quantum devices is finding useful tasks that can be preformed on them. We first show how to efficiently encode a bounded $n \times n$ matrix $A$ into a linear optical circuit with $2n$ modes. We then apply this encoding to the case where $A$ is a matrix containing information about a graph $G$. We show that a photonic quantum processor consisting of single-photon sources, a linear optical circuit encoding $A$, and single-photon detectors can solve a range of graph problems including finding the number of perfect matchings of bipartite graphs, computing permanental polynomials, determining whether two graphs are isomorphic, and the $k$-densest subgraph problem. We also propose pre-processing methods to boost the probabilities of observing the relevant detection events and thus improve performance. Finally we present both numerical simulations and implementations on Quandela's Ascella photonic quantum processor to validate our findings.

arXiv:2301.09594•Jan 23, 2023•0 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.
A scheme for measuring complex temperature partition functions of Ising models is introduced. In the context of ordered qubit registers this scheme finds a natural translation in terms of global operations, and single particle measurements on the edge of the array. Two applications of this scheme are presented. First, through appropriate Wick rotations, those amplitudes can be analytically continued to yield esti-mates for partition functions of Ising models. Bounds on the estimation error, valid with high confidence, are provided and shown to be compatible with previous results. Interestingly, the kind of state prepa-rations and measurements involved in this application can in principle be made “instantaneous", i.e. independent of the system size or the parameters being simulated. Second, the scheme allows to accu-rately estimate some non-trivial invariants of links. A third result concerns the computational power of estimations of partition functions for real temperature classical ferromagnetic Ising models on a square lattice. We provide conditions under which estimating such partition functions allow to reconstruct scat-tering amplitudes of quantum circuits making the problem BQP-hard. Using this mapping, we show that wavefunction overlaps for ground states of quantum Hamiltonians, which can serve as a witness to quantum phase transitions, can be estimated from classical Ising model partition functions. Finally, we show that the ability to accurately measure corner magnetisations on thermal states of two-dimensional Ising models with magnetic field leads to fully polynomial random approximation schemes (FPRAS) for the partition function. Each of these results corresponds to a section of the text that can be essentially read independently. 1
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
An important challenge for current and near-term quantum devices is finding useful tasks that can be preformed on them. We first show how to efficiently encode a bounded n×nn \times nn×n matrix AAA into a linear optical circuit with 2n2n2n modes. We then apply this encoding to the case where AAA is a matrix containing information about a graph GGG. We show that a photonic quantum processor consisting of single-photon sources, a linear optical circuit encoding AAA, and single-photon detectors can solve a range of graph problems including finding the number of perfect matchings of bipartite graphs, computing permanental polynomials, determining whether two graphs are isomorphic, and the kkk-densest subgraph problem. We also propose pre-processing methods to boost the probabilities of observing the relevant detection events and thus improve performance. Finally we present both numerical simulations and implementations on Quandela's Ascella photonic quantum processor to validate our findings.