Transactions on Computational Science XXXI by Marina L. Gavrilova C. J. Kenneth Tan Nabendu Chaki & Khalid Saeed

Author:Marina L. Gavrilova, C. J. Kenneth Tan, Nabendu Chaki & Khalid Saeed
Language: eng
Format: epub
Publisher: Springer Berlin Heidelberg, Berlin, Heidelberg

: , but since is 0–1 valued we can add instead.

: .

Thus is a sum of monomials of the form 2xy or . Modulo 4, both of these terms are invariant under replacing x by . Hence solution counts in where t is the total number of variables and the count in are related by a fixed factor of . We can thus use the theorem of [36] directly to count solutions in to , .

Now, however, notice that also produces an additive quadratic term, namely . Thus any circuit C composed of and (which simulate and ) also has of degree 2. If the theorem of [36, 37] applied to counting binary solutions then would follow. The nub is that the term xy is not invariant under . Counting 0–1 solutions for quadratic polynomials with such terms is shown -complete in general by [38]. The difference between and reflects the linear-versus-quadratic difference in [16], but here we have isolated the jump in complexity to the latter’s coefficient being 1 not 2. This happens entirely within a setting where counting the number of solutions of quadratic polynomials modulo is easy—but counting the number of binary solutions is hard.

Since our proof of Theorem 4 can yield amplitude information at any stage of the circuit we speak of simulation not just emulation here. The general algorithm in [36, 37] does not run in time. It remains to be seen whether its specialization to sums of 2xy or can be honed to rival the nearly linear running time of Jozsa [39]. The Toffoli, , and gates all introduce terms of degree 3 into . It is interesting to ask whether circuits obtained by adding one of these gates have with a simply-expressed structure that resists the “dichotomy” phenomenon (problems being either in or -complete, nothing in-between) in these papers.

Note that we avoided the constraint involved with . That or propagating the annotation along line j would lead to terms of degree 3 or higher, while still giving polynomials that are functionally equivalent to the ones of degree 2 above. This leads to the broad question of recognizing such equivalence, and whether algebraic and Boolean solvers may even go beyond it by finding simplifications that do not have direct analogues at the level of quantum gates. The simplest identity involving a nondeterministic gate, namely , already shows some challenges. Substituting and gives the diagram:

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.