A Software Package to Construct Polynomial Sets over Z_2 for Determining the Output of Quan.pdf

a r X i v : q u a n t - p h / 0 5 0 9 0 6 4 v 2 8 D e c 2 0 0 5 A Software Package to Construct Polynomial Sets over Z2 for Determining the Output of Quantum Computations Vladimir P. Gerdta?, Vasily M. Severyanova? aLaboratory of Information Technologies, Joint Institute for Nuclear Research, 141980 Dubna, Russia A C# package is presented that allows a user for an input quantum circuit to generate a set of multivariate polynomials over the finite field Z2 whose total number of solutions in Z2 determines the output of the quantum computation defined by the circuit. The generated polynomial system can further be converted to the canonical Gro?bner basis form which provides a universal algorithmic tool for counting the number of common roots of the polynomials. 1. INTRODUCTION One important aspect of quantum computation is estimation of computational power of quantum logical circuits. As it was recently shown in [1], determining the output of a quantum computa- tion is equivalent to counting the number of solu- tions of a certain set of polynomials defined over the finite field Z2. Using ideas published in [1], we have written a C# program enabling one to assemble an ar- bitrary quantum circuit in a particular universal gate basis and to construct the corresponding set of polynomial equations over Z2. The number of solutions of the set defines the matrix elements of the circuit and therefore its output value for any input value. The generated polynomial system can further be converted into the canonical Gro?bner basis form by applying efficient involutive algorithms described in [2]. A triangular Gro?bner basis for the pure lexicographical order on the polynomial variables is generally most appropriate for count- ing the number of common roots of the polyno- mials. Our program has a user-friendly graphical in- terface and a built-in base of the elementary gates representing certain quantum gates and wires. A user can easily assemble an input circuit from ?gerdt@ji