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

Quantum Circuit Representation of Bosonic Matrix Functions

Minhyeok Kang, Gwonhak Lee, Youngrong Lim, Joonsuk Huh

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

Abstract

Bosonic counting problems can be framed as estimation tasks of matrix functions such as the permanent, hafnian, and loop-hafnian, depending on the underlying bosonic network. Remarkably, the same functions also arise in spin models, including the Ising and Heisenberg models, where distinct interaction structures correspond to different matrix functions. This correspondence has been used to establish the classical hardness of simulating interacting spin systems by relating their output distributions to #P-hard quantities. Previous works, however, have largely been restricted to bipartite spin interactions, where transition amplitudes, which provide the leading-order contribution to the output probabilities, are proportional to the permanent. In this work, we extend the Ising model construction to arbitrary interaction networks and show that transition amplitudes of the Ising Hamiltonian are proportional to the hafnian and the loop-hafnian. The loop-hafnian generalizes both the permanent and hafnian, but unlike these cases, loop-hafnian-based states require Dicke-like superpositions, making the design of corresponding quantum circuits non-trivial. Our results establish a unified framework linking bosonic networks of single photons and Gaussian states with quantum spin dynamics and matrix functions. This unification not only broadens the theoretical foundation of quantum circuit models but also highlights new, diverse, and classically intractable applications.

Comments
11 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
Bosonic counting problems can be framed as estimation tasks of matrix functions such as the permanent, hafnian, and loop-hafnian, depending on the underlying bosonic network. Remarkably, the same functions also arise in spin models, including the Ising and Heisenberg models, where distinct interaction structures correspond to different matrix functions. This correspondence has been used to establish the classical hardness of simulating interacting spin systems by relating their output distributions to #P-hard quantities. Previous works, however, have largely been restricted to bipartite spin interactions, where transition amplitudes, which provide the leading-order contribution to the output probabilities, are proportional to the permanent. In this work, we extend the Ising model construction to arbitrary interaction networks and show that transition amplitudes of the Ising Hamiltonian are proportional to the hafnian and the loop-hafnian. The loop-hafnian generalizes both the permanent and hafnian, but unlike these cases, loop-hafnian-based states require Dicke-like superpositions, making the design of corresponding quantum circuits non-trivial. Our results establish a unified framework linking bosonic networks of single photons and Gaussian states with quantum spin dynamics and matrix functions. This unification not only broadens the theoretical foundation of quantum circuit models but also highlights new, diverse, and classically intractable applications.
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.