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

Analyzing Algebraic Quantum Circuits Using Exponential Sums

Dave BaconWim van Dam, Alexander C. Russell

Published Jan 1, 2008• 8 citations
OpenAlex

Abstract

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.

Related papers

Quantum circuit dynamics via path integrals: Is there a classical action for discrete-time paths?

Mark D Penney, Dax Enshan Koh, Robert W Spekkens

It is straightforward to compute the transition amplitudes of a quantum circuit using the sum-over-paths methodology when the gates in the circuit are balanced, where a balanced gate is one for which all non-zero transition amplitudes are of equal magnitude. Here we consider the question of whether, for such circuits, the relative phases of different discrete-time paths through the configuration space can be defined in terms of a classical action, as they are for continuous-time paths. We show how to do so for certain kinds of quantum circuits, namely, Clifford circuits where the elementary systems are continuous-variable systems or discrete systems of odd-prime dimension. These types of circuit are distinguished by having phase-space representations that serve to define their classical counterparts. For discrete systems, the phase-space coordinates are also discrete variables. We show that for each gate in the generating set, one can associate a symplectomorphism on the phase-space and to each of these one can associate a generating function, defined on two copies of the configuration space. For discrete systems, the latter association is achieved using tools from algebraic geometry. Finally, we show that if the action functional for a discrete-time path through a sequence of gates is defined using the sum of the corresponding generating functions, then it yields the correct relative phases for the path-sum expression. These results are likely to be relevant for quantizing physical theories where time is fundamentally discrete, characterizing the classical limit of discrete-time quantum dynamics, and proving complexity results for quantum circuits.

arXiv:1604.07452•New Journal of Physics•Feb 21, 2017•10 citations

Computing quopit Clifford circuit amplitudes by the sum-over-paths technique

Dax Enshan Koh, Mark D Penney, Robert W. Spekkens

By the Gottesman-Knill Theorem, the outcome probabilities of Clifford circuits can be computed efficiently. We present an alternative proof of this result for quopit Clifford circuits (i.e., Clifford circuits on collections of p-level systems, where p is an odd prime) using Feynman’s sum-over-paths technique, which allows the amplitudes of arbitrary quantum circuits to be expressed in terms of a weighted sum over computational paths. For a general quantum circuit, the sum over paths contains an exponential number of terms, and no efficient classical algorithm is known that can compute the sum. For quopit Clifford circuits, however, we show that the sum over paths takes a special form: it can be expressed as a product of Weil sums with quadratic polynomials, which can be computed efficiently. This provides a method for computing the outcome probabilities and amplitudes of such circuits efficiently, and is an application of the circuit-polynomial correspondence which relates quantum circuits to low-degree polynomials.

arXiv:1702.03316•Quantum Information and Computation•Nov 1, 2017•16 citations

Towards Large-scale Functional Verification of Universal Quantum Circuits

Matthew Amy

We introduce a framework for the formal specification and verification of quantum circuits based on the Feynman path integral. Our formalism, built around exponential sums of polynomial functions, provides a structured and natural way of specifying quantum operations, particularly for quantum implementations of classical functions. Verification of circuits over all levels of the Clifford hierarchy with respect to either a specification or reference circuit is enabled by a novel rewrite system for exponential sums with free variables. Our algorithm is further shown to give a polynomial-time decision procedure for checking the equivalence of Clifford group circuits. We evaluate our methods by performing automated verification of optimized Clifford+T circuits with up to 100 qubits and thousands of T gates, as well as the functional verification of quantum algorithms using hundreds of qubits. Our experiments culminate in the automated verification of the Hidden Shift algorithm for a class of Boolean functions in a fraction of the time it has taken recent algorithms to simulate.

arXiv:1805.06908•Electronic Proceedings in Theoretical Computer Science•Jan 31, 2019•119 citations

An algorithm for constructing polynomial systems whose solution space characterizes quantum circuits

Vladimir P. Gerdt, Vasily M. Severyanov

An algorithm and its first implementation in C# are presented for assembling arbitrary quantum circuits on the base of Hadamard and Toffoli gates and for constructing multivariate polynomial systems over the finite field Z_2 arising when applying the Feynman's sum-over-paths approach to quantum circuits. The matrix elements determined by a circuit can be computed by counting the number of common roots in Z_2 for the polynomial system associated with the circuit. To determine the number of solutions in Z_2 for the output polynomial system, one can use the Groebner bases method and the relevant algorithms for computing Groebner bases.

arXiv:quant-ph/0512064•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 24, 2006•3 citations

Symbolic Synthesis of Clifford Circuits and Beyond

Matthew Amy, Owen Bennett-Gibbs, Neil J. Ross

Path sums are a convenient symbolic formalism for quantum operations with applications to the simulation, optimization, and verification of quantum protocols.Unlike quantum circuits, path sums are not limited to unitary operations, but can express arbitrary linear ones.Two problems, therefore, naturally arise in the study of path sums: the unitarity problem and the extraction problem.The former is the problem of deciding whether a given path sum represents a unitary operator.The latter is the problem of constructing a quantum circuit, given a path sum promised to represent a unitary operator.In this paper, we show that the unitarity problem is co-NP-hard in general, but that it is in P when restricted to Clifford path sums.We then provide an algorithm to synthesize a Clifford circuit from a unitary Clifford path sum.The circuits produced by our extraction algorithm are of the form C 1 HC 2 , where C 1 and C 2 are Hadamard-free circuits and H is a layer of Hadamard gates.We also provide a heuristic generalization of our extraction algorithm to arbitrary path sums.While this algorithm is not guaranteed to succeed, it often succeeds and typically produces natural looking circuits.Alongside applications to the optimization and decompilation of quantum circuits, we demonstrate the capability of our algorithm by synthesizing the standard quantum Fourier transform directly from a path sum.

arXiv:2204.14205•Electronic Proceedings in Theoretical Computer Science•Nov 14, 2023•6 citations

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
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.
It is straightforward to compute the transition amplitudes of a quantum circuit using the sum-over-paths methodology when the gates in the circuit are balanced, where a balanced gate is one for which all non-zero transition amplitudes are of equal magnitude. Here we consider the question of whether, for such circuits, the relative phases of different discrete-time paths through the configuration space can be defined in terms of a classical action, as they are for continuous-time paths. We show how to do so for certain kinds of quantum circuits, namely, Clifford circuits where the elementary systems are continuous-variable systems or discrete systems of odd-prime dimension. These types of circuit are distinguished by having phase-space representations that serve to define their classical counterparts. For discrete systems, the phase-space coordinates are also discrete variables. We show that for each gate in the generating set, one can associate a symplectomorphism on the phase-space and to each of these one can associate a generating function, defined on two copies of the configuration space. For discrete systems, the latter association is achieved using tools from algebraic geometry. Finally, we show that if the action functional for a discrete-time path through a sequence of gates is defined using the sum of the corresponding generating functions, then it yields the correct relative phases for the path-sum expression. These results are likely to be relevant for quantizing physical theories where time is fundamentally discrete, characterizing the classical limit of discrete-time quantum dynamics, and proving complexity results for quantum circuits.
By the Gottesman-Knill Theorem, the outcome probabilities of Clifford circuits can be computed efficiently. We present an alternative proof of this result for quopit Clifford circuits (i.e., Clifford circuits on collections of p-level systems, where p is an odd prime) using Feynman’s sum-over-paths technique, which allows the amplitudes of arbitrary quantum circuits to be expressed in terms of a weighted sum over computational paths. For a general quantum circuit, the sum over paths contains an exponential number of terms, and no efficient classical algorithm is known that can compute the sum. For quopit Clifford circuits, however, we show that the sum over paths takes a special form: it can be expressed as a product of Weil sums with quadratic polynomials, which can be computed efficiently. This provides a method for computing the outcome probabilities and amplitudes of such circuits efficiently, and is an application of the circuit-polynomial correspondence which relates quantum circuits to low-degree polynomials.
We introduce a framework for the formal specification and verification of quantum circuits based on the Feynman path integral. Our formalism, built around exponential sums of polynomial functions, provides a structured and natural way of specifying quantum operations, particularly for quantum implementations of classical functions. Verification of circuits over all levels of the Clifford hierarchy with respect to either a specification or reference circuit is enabled by a novel rewrite system for exponential sums with free variables. Our algorithm is further shown to give a polynomial-time decision procedure for checking the equivalence of Clifford group circuits. We evaluate our methods by performing automated verification of optimized Clifford+T circuits with up to 100 qubits and thousands of T gates, as well as the functional verification of quantum algorithms using hundreds of qubits. Our experiments culminate in the automated verification of the Hidden Shift algorithm for a class of Boolean functions in a fraction of the time it has taken recent algorithms to simulate.
An algorithm and its first implementation in C# are presented for assembling arbitrary quantum circuits on the base of Hadamard and Toffoli gates and for constructing multivariate polynomial systems over the finite field Z_2 arising when applying the Feynman's sum-over-paths approach to quantum circuits. The matrix elements determined by a circuit can be computed by counting the number of common roots in Z_2 for the polynomial system associated with the circuit. To determine the number of solutions in Z_2 for the output polynomial system, one can use the Groebner bases method and the relevant algorithms for computing Groebner bases.
Path sums are a convenient symbolic formalism for quantum operations with applications to the simulation, optimization, and verification of quantum protocols.Unlike quantum circuits, path sums are not limited to unitary operations, but can express arbitrary linear ones.Two problems, therefore, naturally arise in the study of path sums: the unitarity problem and the extraction problem.The former is the problem of deciding whether a given path sum represents a unitary operator.The latter is the problem of constructing a quantum circuit, given a path sum promised to represent a unitary operator.In this paper, we show that the unitarity problem is co-NP-hard in general, but that it is in P when restricted to Clifford path sums.We then provide an algorithm to synthesize a Clifford circuit from a unitary Clifford path sum.The circuits produced by our extraction algorithm are of the form C 1 HC 2 , where C 1 and C 2 are Hadamard-free circuits and H is a layer of Hadamard gates.We also provide a heuristic generalization of our extraction algorithm to arbitrary path sums.While this algorithm is not guaranteed to succeed, it often succeeds and typically produces natural looking circuits.Alongside applications to the optimization and decompilation of quantum circuits, we demonstrate the capability of our algorithm by synthesizing the standard quantum Fourier transform directly from a path sum.
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.