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:quant-ph/0512064 · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

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

Vladimir P. Gerdt, Vasily M. Severyanov

Published May 24, 2006• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1117/12.683121

Related papers

A C# package for assembling quantum circuits and generating associated polynomial sets

Vladimir P. Gerdt, Vasily M. Severyanov

Recently it has been shown that elements of the unitary matrix determined by a quantum circuit can be computed by counting the number of common roots in the finite field ℤ 2 for a certain set of multivariate polynomials over ℤ 2 . In this paper we present a C# package that allows a user to assemble a quantum circuit and to generate the multivariate polynomial set associated with the circuit. The generated polynomial system can further be converted to the canonical triangular involutive basis form, which is appropriate for counting the number of common roots of the polynomials.

Physics of Particles and Nuclei Letters•Mar 1, 2007•2 citations

An algorithmic approach to solving polynomial equations associated with quantum circuits

Vladimir P. Gerdt, M. V. Zinin

In this paper we present two algorithms for reducing systems of multivariate polynomial equations over the finite field F 2 to the canonical triangular form called lexicographical Gröbner basis. This triangular form is the most appropriate for finding solutions of the system. On the other hand, the system of polynomials over F 2 whose variables also take values in F 2 (Boolean polynomials) completely describes the unitary matrix generated by a quantum circuit. In particular, the matrix itself can be computed by counting the number of solutions (roots) of the associated polynomial system. Thereby, efficient construction of the lexicographical Gröbner bases over F 2 associated with quantum circuits gives a method for computing their circuit matrices that is alternative to the direct numerical method based on linear algebra. We compare our implementation of both algorithms with some other software packages available for computing Gröbner bases over F 2.

Physics of Particles and Nuclei Letters•Nov 19, 2009•1 citation

A mathematica program for constructing quantum circuits and computing their unitary matrices

Vladimir P. Gerdt, Robert Kragler, Alexander N. Prokopenya

In this paper we briefly describe a Mathematica program for simulation of quantum circuits and illustrate some of its facilities by simple examples. Unlike other Mathematica-based quantum simulators, our program provides a user-friendly graphical interface for generating quantum circuits and computing the circuit unitary matrices. In addition to standard linear algebra-based tools, our program implements special computer-algebra technique for constructing the multivariate polynomial system that, for a circuit composed from the Toffoli and Hadamard gates, uniquely defines the circuit matrix.

Physics of Particles and Nuclei Letters•Nov 19, 2009•12 citations

Quantum computing and polynomial equations over the finite field Z_2

Christopher M. Dawson, Henry L. Haselgrove, Andrew P. Hines +3 more

What is the computational power of a quantum computer? We show that determining the output of a quantum computation is equivalent to counting the number of solutions to an easily computed set of polynomials defined over the finite field Z_2. This connection allows simple proofs to be given for two known relationships between quantum and classical complexity classes.

arXiv:quant-ph/0408129•Aug 20, 2004•44 citations

Quantum computing and polynomial equations over Z_2

Christopher M. Dawson, Henry L. Haselgrove, Andrew P. Hines +3 more

What is the computational power of a quantum computer? We show that determining the output of a quantum computation is equivalent to counting the number of solutions to an easily computed set of polynomials defined over the finite field Z_2. This connection allows simple proofs to be given for two known relationships between quantum and classical complexity classes, namely BQP/P/\#P and BQP/PP.

Quantum Information and Computation•May 1, 2005•26 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
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.
Recently it has been shown that elements of the unitary matrix determined by a quantum circuit can be computed by counting the number of common roots in the finite field ℤ 2 for a certain set of multivariate polynomials over ℤ 2 . In this paper we present a C# package that allows a user to assemble a quantum circuit and to generate the multivariate polynomial set associated with the circuit. The generated polynomial system can further be converted to the canonical triangular involutive basis form, which is appropriate for counting the number of common roots of the polynomials.
In this paper we present two algorithms for reducing systems of multivariate polynomial equations over the finite field F 2 to the canonical triangular form called lexicographical Gröbner basis. This triangular form is the most appropriate for finding solutions of the system. On the other hand, the system of polynomials over F 2 whose variables also take values in F 2 (Boolean polynomials) completely describes the unitary matrix generated by a quantum circuit. In particular, the matrix itself can be computed by counting the number of solutions (roots) of the associated polynomial system. Thereby, efficient construction of the lexicographical Gröbner bases over F 2 associated with quantum circuits gives a method for computing their circuit matrices that is alternative to the direct numerical method based on linear algebra. We compare our implementation of both algorithms with some other software packages available for computing Gröbner bases over F 2.
In this paper we briefly describe a Mathematica program for simulation of quantum circuits and illustrate some of its facilities by simple examples. Unlike other Mathematica-based quantum simulators, our program provides a user-friendly graphical interface for generating quantum circuits and computing the circuit unitary matrices. In addition to standard linear algebra-based tools, our program implements special computer-algebra technique for constructing the multivariate polynomial system that, for a circuit composed from the Toffoli and Hadamard gates, uniquely defines the circuit matrix.
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.