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:2408.08857

Connecting quantum circuit amplitudes and matrix permanents through polynomials

Hugo Thomas, Pierre-Emmanuel Emeriau, Rawad Mezher

Published Aug 16, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2408.08857

Related papers

Combinatorial Matrix Functions in Ising Models and Quantum Circuit Representation

Minhyeok Kang, Gwonhak Lee, Youngrong Lim +1 more

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.

quant-pharXiv:2602.01868•Feb 3, 2026•0 citations

Analyzing Algebraic Quantum Circuits Using Exponential Sums

Dave BaconWim van Dam, Alexander C. Russell

We introduce and analyze circuits that are the quantum mechanical generalization of classical algebraic circuits. Using the algebraic operations of addition and multiplication, as well as the quantum Fourier transform, such circuits are well-defined for rings Z=mZ and finite fields Fq. The acceptance probabilities of such algebraic quantum circuits can be expressed as exponential sums Âx exp(2pi f(x)=m) where the multivariate polynomial f is determined by the circuit, while it is independent of the ring or field over which we interpret the circuit. Dawson et al. [Quantum Information & Computation, 5(2), pp. 102‐112 (2004)] introduced this “sum over paths” description as a discrete version of the path integral approach of standard quantum mechanics. From this perspective, the polynomial f should be interpreted as the “action” of a specific (classical) computational path between the input and output of the circuit. In this article we prove several properties of algebraic quantum circuits. Using the theory of exponential sums, we show that in the limit of large m or q, the acceptance probabilities of a circuit converge to zero or to one. Circuits that do not involve the multiplication operation are the algebraic generalization of Clifford circuits and we show how their acceptance probabilities can be calculated exactly in a classical efficient manner. For algebraic circuits that are defined over rings Z=p r Z we derive a “least action principle” that shows how the behaviour of such circuits is determined by those computational paths whose action polynomials are extremal.

•Jan 1, 2008•8 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

The trainability of photonic quantum circuits

Alexander Makarovskiy, Adam Taylor, Zhenghao Li +5 more

Variational quantum algorithms are a leading approach to near-term quantum computing, but their scalability can be limited by barren plateaus and the sampling cost of resolving small changes in the loss landscape. Here, we study the trainability of passive linear-optical quantum circuits and introduce a framework based on the ratio of sample variance to circuit variance. This ratio determines the number of circuit samples required to resolve local loss differences and gradients to proportional accuracy. We apply this framework to photon-number observables and identify both trainable and non-trainable regimes. Supported by analytic results and a numerically observed polynomial decay of the circuit variance, we find that fixed-order photon-number polynomials require only polynomially many samples as the system size grows, whereas high-order polynomials and observables based on output probabilities generally require exponentially many samples. Within the trainable regime, we further identify classes of observables in which quantum estimation achieves a polynomial speed-up over multiple classical methods. Within this family, neural network observables provide one practical construction that allow measurement outcomes to be efficiently processed into the desired polynomial. These results establish photonic variational quantum computing as a promising platform for near-term applications.

quant-pharXiv:2607.21544•Jul 24, 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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•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\ifmmode\times\else\texttimes\fi{}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 preprocessing 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.

Physical Review A•Sep 6, 2023•14 citations
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.
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(n2)O(n^2)O(n2) gates for a 2n×2n2n \times 2n2n×2n real symmetric matrix. Specifically, we propose a quantum circuit that maps the loop-hafnian state to a basis state with O(n2)O(n^2)O(n2) gates, and show that, by an adaptive measurement, the loop-hafnian states for all subsets of vertices can be measured simultaneously.
We introduce and analyze circuits that are the quantum mechanical generalization of classical algebraic circuits. Using the algebraic operations of addition and multiplication, as well as the quantum Fourier transform, such circuits are well-defined for rings Z=mZ and finite fields Fq. The acceptance probabilities of such algebraic quantum circuits can be expressed as exponential sums Âx exp(2pi f(x)=m) where the multivariate polynomial f is determined by the circuit, while it is independent of the ring or field over which we interpret the circuit. Dawson et al. [Quantum Information & Computation, 5(2), pp. 102‐112 (2004)] introduced this “sum over paths” description as a discrete version of the path integral approach of standard quantum mechanics. From this perspective, the polynomial f should be interpreted as the “action” of a specific (classical) computational path between the input and output of the circuit. In this article we prove several properties of algebraic quantum circuits. Using the theory of exponential sums, we show that in the limit of large m or q, the acceptance probabilities of a circuit converge to zero or to one. Circuits that do not involve the multiplication operation are the algebraic generalization of Clifford circuits and we show how their acceptance probabilities can be calculated exactly in a classical efficient manner. For algebraic circuits that are defined over rings Z=p r Z we derive a “least action principle” that shows how the behaviour of such circuits is determined by those computational paths whose action polynomials are extremal.
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.
Variational quantum algorithms are a leading approach to near-term quantum computing, but their scalability can be limited by barren plateaus and the sampling cost of resolving small changes in the loss landscape. Here, we study the trainability of passive linear-optical quantum circuits and introduce a framework based on the ratio of sample variance to circuit variance. This ratio determines the number of circuit samples required to resolve local loss differences and gradients to proportional accuracy. We apply this framework to photon-number observables and identify both trainable and non-trainable regimes. Supported by analytic results and a numerically observed polynomial decay of the circuit variance, we find that fixed-order photon-number polynomials require only polynomially many samples as the system size grows, whereas high-order polynomials and observables based on output probabilities generally require exponentially many samples. Within the trainable regime, we further identify classes of observables in which quantum estimation achieves a polynomial speed-up over multiple classical methods. Within this family, neural network observables provide one practical construction that allow measurement outcomes to be efficiently processed into the desired polynomial. These results establish photonic variational quantum computing as a promising platform for near-term applications.
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 boundedn×nn\times nn×nmatrixAAAinto a linear optical circuit with2n2n2nmodes. We then apply this encoding to the case whereAAAis a matrix containing information about a graphGGG. We show that a photonic quantum processor consisting of single-photon sources, a linear optical circuit encodingAAA, 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.
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\ifmmode\times\else\texttimes\fi{}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 preprocessing 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.