Grilling Quantum Circuits
Polynomial algebra turns up the heat
Amlan Chakrabarti is currently finishing a postdoc at Princeton University, while on leave from the University of Calcutta in India. He has been working in Niraj Jha’s group at the Engineering School. While we have been debating the theoretical feasibility of scalable quantum computers, Amlan and coworkers have been developing approaches to engineer them. This includes finding and comparing concrete realizations of elements for quantum circuits.
Today I describe ongoing work with Amlan on simulating quantum circuits by polynomial algebra—and what this may mean for the power of quantum.
The debate with Gil Kalai and Aram Harrow on this blog has focused on how hard is it to build quantum circuits in the real world, with real components, that work long enough to be useful. Here we are interested in a different but equally important question:
How hard is it to classically simulate a quantum circuit?
If there are efficient simulations, it may be moot whether quantum computers can be built or not. Many consider such efficient simulations unlikely because they would make factoring easy, among other reasons. But there is no proof today—let me repeat, no proof—that quantum circuits in are not easy to simulate classically.
My work with Amlan addresses this simulation issue by encoding quantum computations into multivariable polynomials. Of course this encoding only replaces exponentially large matrix evaluations by other potentially difficult computations. But by extending known work already connected with the important reduction from to , and by using the full power of polynomial algebra, we can hope that it will lead to new insights. It could yield simulation methods better than any currently known, along lines provisionally implemented by Vladimir Gerdt and Vasily Severyanov. It may generate theoretical ideas capable of putting into the polynomial hierarchy, which is considered by some to be a hard “holy grail” type problem. What it definitely does is provide several new ways to express a quantum circuit by polynomials placed in a grill mesh at its gate junctures. Does the simple algebra capture all of the quantum power? That is well worth a look.
The Grille
A quantum circuit has some number of qubit lines which go across like heating elements, and a finite number of gates. Typical gates involve at most three qubit lines, and gates on disjoint sets of qubit lines can be arranged in parallel. But let us space all the gates so there are column spaces between successive pairs, plus the left side which holds the input, and the right side which gives the output. Thus we can place a variable , and at every juncture, in the manner of a grill.
We can identify for with the inputs , supposing the other ancilla inputs have been set to zero, and with outputs for selected . Under the standardbasis representation, the circuit computes a linear operator applied to the (padded representation of the) input .
Known results show how to compute the acceptance probability of on input from the scalar values for certain target values . The game is to express using polynomial(s) in the variables.
In order to grill our quantum circuits evenly on all sides, we define:
Definition 1. A quantum gate is balanced if it is defined by a matrix (over the standard basis) in which every nonzero entry has the same absolute value .
Hadamard gates are balanced with , and CNOT and Toffoli and all other deterministic gates are balanced with . Hence can be defined via circuits of balanced gates. We call the balance factor.
High Versus Low Degree Grilling
Given a polynomial in many variables and a value , denote by the number of arguments such that . For a quantum circuit we can identify an integer such that is the greatest common divisor of the angular component of complexnumber matrix entries of gates in . Call the minphase of , and let stand for a primitive th root of unity. Our first theorem turns around like a rotisserie:
Theorem 2. Given a balanced quantum circuit with minphase and values , we can construct in polynomial time a polynomial with values in and a real number such that
Here is a product of terms for each gate, and is the product of the balance factors for each gate.
The product makes the degrees grow fast. For lowdegree cooking we can work additively in instead. My main innovation is using extra variables “” (shown later) to solve technical problems noted in an abovelinked paper when .
Theorem 3. Given a balanced quantum circuit with minphase and values , we can construct in polynomial time a polynomial with values in and real number such that
Here is a sum of terms for each gate, which keeps the total degree down but involves extra variables, while may be the same or greater depending on whether the domain of assignments is over or .
When , which suffices for the universal set of Hadamard and Toffoli gates, , and both formulas give a difference of solution counts. Since the solution count is a function even for the higherdegree polynomial, this recovers the result that reduces to the difference of two functions .
This raises the hope that Larry Stockmeyer’s factor approximation might put into the polynomial hierarchy, but there are two problems:
 Approximating to within need not approximate their difference to any similar factor.

The value is small, roughly the square root of the magnitudes attained by and , so that the property guaranteed by the theorems that
is actually a substantial promise condition observed by the quantum circuit itself.
The second factor makes the first issue “bite”—but also suggests recipes for getting simulations of into the hierarchy, or even into classical polynomial time especially for cases of the lowdegree polynomials . The recipes involve substitutions, special cases of complete problems that may be tractable, and possibly even tricks that are “illegal” in quantum mechanics but may be fine in algebra. This brings us right to the cookbook for representing gates by terms for and .
Cookbook of Gates
We use or in place of the variable of a gate input, and or similarly for outputs. For a singlequbit gate , the rows and columns are indexed like this:
and the corresponding term for the product polynomial is given by
For the NOT gate, also called , we have
For 01 arguments, note this gives when , which kills the whole product. Thus the solution sets are unchanged if we substitute . Then cancels down to , and we have saved a term in the product.
The identity gate is handled similarly: we can introduce the term , or just substitute and do nothing. Thus in the absence of gates along a qubit line we can just carry the variable forward.
Additive Case
Instead of multiplying by , we multiply by the log base of that entry, except that when , we introduce new variable(s) . Thus the NOT gate gives
Now when or the is left alone as an additive term. When is a power we can use many variables with multipliers to make an additive term that assumes all values in with equal weight given assignments in . The set of constraintviolating assignments in which this term survives is thus partitioned into equal subsets giving the different values. Since the sum of the th roots of unity is zero, these give a netzero contribution to the sum representation of .
Again we can substitute , and this dispenses with the variables leaving just zero. We can always do substitution for any deterministic gate, even one with imaginary entries such as the Phase Gate:
Hadamard Case
For Hadamard gates we pull the balance factor outside, and note that .
And is just . There is no substitution, so we have added a variable, and no constraint. The Hadamard case is thus translated into nondeterminism for the polynomials, which is allimportant.
MultiQubit Cases
A 2qubit gate with inputs has a matrix with rows indexed , , , , and columns similarly for the outputs . For example:
The polynomial for CNOT includes a term for the final ‘$1$’ in the third row, while the polynomial has twelve terms multiplied by but nothing else. They become and , respectively, under the substitution , , which represents the deterministic action. The Toffoli gate is similar for three inputs/outputs and an matrix.
For the CZ gate the bottomright entry contributes to but to . The substitution , is applicable, but does not leave in the case, but rather . In the additive case it leaves , which is equivalent to for 01 assignments. The additive case, of course, has a similar multiplied term as for CNOT.
See our draft paper for polynomial translations of many other gates, even the variablephase Shor gates. The net improvements over previous work are:
 Wider set of quantum gates handled directly.
 Multiplicative as well as additive representation.
 Single polynomial not set of polynomials.
 Extra “” variables avoid mixed arithmetic in additive case.
 Freedom to substitute or not.
 Wide choice of target ring allows encoding into many algebraic problems and exploring tradeoffs.
Circuit Simulations and Invariants
To compute exactly, we need to calculate or for some finite set of values . Gerdt and Severyanov outline a procedure for solution counting using Gröbner bases and triangular forms. But to simulate we need not compute exactly—we need only distinguish accepting from rejecting cases, which basically means distinguishing near zero from near . This may motivate new methods for approximate counting.
Here is a circuit previously used as an example in the earlierlinked papers, treating and as variables to be filled from and , followed by the and polynomials.
The Hadamard and Toffoli gates are arranged so as to produce entangled states. On input , the state in the middle after the first Toffoli gate is
It is not meaningful to assign the separate values to the first two qubits and to the third, because those could also come from the different, nonentangled, state that is the tensor product of those three values. However, the polynomial annotations at those three points do have separate values, and preserve the information—the nonentangled state would have different polynomials in any realization. This is the intuitive point of using the grill.
Hence the polynomials must be telling us something about entanglements. How can we better quantify this? The degree of the polynomial is not much indication, since this depends on substitution and is always bounded for the polynomial. However, polynomial invariant theory gives other notions of degree.
One notion is the same used by Walter Baur and Volker Strassen to obtain the best known lower bounds on arithmetic complexity for explicit polynomials : allocate new variables and form the polynomial ideal generated by the polynomials
The graph of this mapping in the dimensional – space is topologically irreducible and hence has an unambiguously defined geometric degree . The BaurStrassen quantity is their famous lower bound on circuits for , as we covered here.
What makes a plausible component of an entanglement measure is that it is additive for disjoint systems, i.e. for products of polynomials on disjoint sets of variables, and is nonincreasing under projections hence amenable to substitutions. Multiway entanglement measures on qubits are notoriously difficult to define, but we may hope the polynomial representations provide a salient measure that also bounds the true complexity of building and operating the circuit.
Last, polynomials may help us identify subsets of gates and restricted kinds of circuits that are classically simulable. This is known for socalled stabilizer circuits which can be characterized by the Hadamard gate, the phase gate, and the CZ gate. Over the polynomials for circuits built from these gates are incredibly simple.
Each term is either a variable squared, , or a product .
These terms are invariant under changing from to and are zeroed out by and , so for variables the domains and are essentially the same. Can we inductively compute the quantities as the circuit is built up? This would at least replicate classical theorems about these circuits. In any event we get a wealth of newlymotivated special cases of complete counting problems to study.
Open Problems
Can polynomial algebra using our grilles outperform other classical simulations of quantum circuits that have been programmed?
Is solutioncounting for polynomials over all of whose terms have the form or in ? Or is this restricted problem still complete, so that our simulation would need to find additional structure in the polynomials? Update: It is indeed in , for any quadratic polynomial, via this paper coauthored by Dick.
What properties of quantum circuits (besides entanglement) can we approach this way? Can this inform the debate over feasibility of quantum computers?
[fixed “3” to “\sqrt{3}” near end]
Trackbacks
 The Viewpoint Skeptics of Quantum Computers Don’t Want You To Hear  Pontiff++
 Michigan Coding, Complexity, and Sparsity Workshop « Gödel’s Lost Letter and P=NP
 Polynomials Behaving Badly « Gödel’s Lost Letter and P=NP
 Interstellar Quantum Computation  Gödel's Lost Letter and P=NP
 Practically P=NP?  Gödel's Lost Letter and P=NP
 Quantum Algorithms Via Linear Algebra  Gödel's Lost Letter and P=NP
 Cancellation is a Pain  Gödel's Lost Letter and P=NP
 UB Theory Weekly – Final Week  Code for Food
 Quantum Supremacy and Complexity  Gödel's Lost Letter and P=NP
 Progress On Modular Computation  Gödel's Lost Letter and P=NP
 A Magic Madison Visit  Gödel's Lost Letter and P=NP
 Doing Mod N Via Mod R  Gödel's Lost Letter and P=NP
 A Quantum Connection For Matrix Rank  Gödel's Lost Letter and P=NP
 A Rank Problem  Gödel's Lost Letter and P=NP
 A Rank Problem  Gödel's Lost Letter and P=NP
 A Rank Problem  Gödel's Lost Letter and P=NP
 NetZero Graphs  Gödel's Lost Letter and P=NP
You might be interested in some work that Wim van Dam did on this approach: http://www.cs.ucsb.edu/~vandam/LeastAction.pdf I don’t think it was ever published. The cool thing is that your balanced condition, i.e. that all the magnitudes of the amplitudes are the same, is sort of related to the idea of path integral in physics.
In its most common form the path integral is a way to think about the amplitude for particle to go from position x0 and time t0 to position x1 and time t1 as a sum over all possible paths from these two events, weighted by a phase related to the action of the path. The cool thing here is that the magnitudes of the amplitudes are all the same. One motivation for the thinking about quantum computers this way is that there are some cool tricks physicists have dreamed up to sometimes efficiently calculate these path integrals, and it might be useful to bring these over into the CS regime.
Oh, and, p.s. there is also no proof that classical circuits can’t solve NPcomplete problems efficiently, but for some reason I don’t see that in all of your posts on classical computers 😉
Thanks! I may have been told about van Dam’s incipient work at Complexity’08, but did not go further. I did know about the pathintegral connection—indeed, I’ve asked around about whether there are geometric/topological invariants associated to it. The image in the CS regime are all these restricted cases of #Pcomplete solutioncounting problems, and I’ve asked both JinYi Cai and Les Valiant whether they may fall into their “gap”theorem schemes. I hope to get time to bring this out more fully…
As for “no proof”, Dick provided some thoughts which I merged into my intro; I pondered upgrading that line to add “…, nor even a convincing hardness argument”—but thought that better leftalone in the post. 😎
Ken: indeed you and I talked about this at Computational Complexity in Maryland. The ‘action polynomial’ (which is related to the polynomial that is defined above) that Dave, Alex Russell and I defined does indeed have various interesting geometric properties.
In the case of stabilizer circuits the action polynomial F is of degree 2, which allowed us to use quadratic forms to efficiently compute all possible properties of the quantum circuit. It turns out that the crucial quantity of the surface F=0 is the dimension of the collection of its its singular points. The conjecture is that for general quantum circuits this dimension keeps on playing an important role.
Wim’s notion of an “action polynomial” is very attractive (to me). There is a considerable literature that is devoted to the geometric properties of these objects, viewed as algebraic varieties. Please post more, Wim!
Right—you have the same expression grouped a different way, and say more simply that A_C^2 (in my terms, u^2) is the acceptance probability. I see your algorithm for the stabilizer case has more powerful tools than what I was trying—albeit my y^2, 2yz form is more particular than “degree 2”—including using the Jacobian ideal without the mapping variables y_i. Does it achieve Richard Jozsa’s nearlylinear time? That’s what I hope to match, but I suspect this needs to use more information about how the gates are connected. I’ll look to see if your ftog transformation takes care of that (too), thanks! The gdeg of the Jacobian ideal (with or without the y_i mapping) may include the info you use about the singular points.
John—just saw your comment; I’d indeed be interested in pointers about action polynomials [as] algebraic varieties!
Be cautious about wading in these waters, Ken … the ocean of algebraic varieties is infinitely deep … and yet, it has grillable Salmon in it (arXiv:1009.6181v2 [math.AG]). 🙂
That ocean also has volcanic heat vents with growthindeep, or rather Grothendieck. 😉
Ouch! 🙂 OK, give me a a secant (second) to think of an answering pun! 🙂
Seriously, these varieties can be viewed as quantum dynamical statespaces, upon which pullback of FTQC dynamics yields conjectures that are midway between Gil Kalai’s skepticism and Aram Harrow’s faith.
The above link is to a Coimbra lecture by Anthony Geramita, that provides a (relatively) accessible introduction to an ocean of literature that is Grothendieckdeep and Landsbergwide.
Regarding the notions of “path integral” and “quantum computing”, what is striking about the preprints on the arxiv server is how popular these terms are individually, yet how relatively seldom they appear together. E.g. for the year 2011, with a full record arxiv search:
• “quantum computing”: 366 preprints
• “path integral”: 229 preprints
• “quantum computing” AND “path integral”: 0 preprints
It is natural to enquire whether there is some mathematical obstruction to simultaneous application of these two toolsets. In this regard a tutorial by Zia, Redish, and McKay titled “Making sense of the Legendre transform” (American Journal of Physics, 2009) is commended.
As I presently (partially) appreciate it, one obstruction may be that the expressing propagators as functional integrals over a Lagrangian action, which is natural for free particles, is *not* natural for qubits. For example, a Lagrangian for classical particles arises naturally via a Lagendre transform of the convex kinetic term in the Hamiltonian, but for classical (Blochian) qubits the Hamiltonian in general has no natural convex kinetic function.
We wonder, what mathematical element(s) is/are natural for qubits, in the sense that the Lagrangian action is natural for particles? Perhaps Ken Regan’s essay is correct to suggest that a polynomial algebra may in some sense (that admittedly is not entirely clear to me) provide these natural elements?
As it turns out, there is a very readable, and very interesting (but unpublished?) manuscript by Dave Bacon, Wim van Dam, and Alexander Russell titled “Analyzing Algebraic Quantum Circuits Using Exponential Sums” (2008?) that for a broad class of quantum circuits constructs precisely the “action polynomials” that the above comment had inmind (a Google search finds the manuscript)
Along with Dickens’ character Oliver Twist, I hope it’s OK to voice a sentiment that this manuscript inspires: “Please, sirs, we want some more!” 🙂
… and systematically checking through the links of this GLL+PvsNP thread, I find that that the abovementioned manuscript “Analyzing Algebraic Quantum Circuits Using Exponential Sums” is identical to the PDF file that Dave Bacon’s comment linkedto above.
A very nice, very thoughtprovoking manuscript!
Works about quantum computing and path integral do exist. Even I myself had such work (http://arxiv.org/abs/quantph/0308017 rejected as “not clear”, because Lagrangian approach in discrete case is indeed not trivial).
Random Guess (hopefully polynomially testable). Hypothesis – the classical measurement device provides boundary condition for the state of the quantum device. Corollary – the output qubit state (the pair of variables representing qubit amplitudes) can only accept real vectors [0,1] or [1,0]. These qubit states are linked to the initial state via unitary matrix (circuit Hamiltonian). The initial states are amplitude norm one and are entangled (that what experimental preparation requires). The entanglement is easily implemented via . The only problem is amplitude norm one for the initial state of qubit variable (as far as I understand this is not analytical, and thus could not be implemented polynomially (the possible solution is to work in as this post suggest, although this may be too restrictive on the input space ) ). This tells that the possible values of output states are interfering with each other via the Hamiltonian and entanglement.
As a further resource in regard to the ultrarich relationship between geometry, algebra, quantum dynamics, path integrals, computation, and simulation, please let me commend Tony Zee’s discussion of FadeevPopov methods in his studentfriendly Quantum Field Theory in a Nutshell. Slowly and inexorably, Zee’s book developes the aggregate notion that path integrals in gauge theories span a nonflat statespace, and that the quantum dynamical consequences of that curvature can be effectively simulated as arising from (nonphysical) ghost particles acting on a flat statespace.
It is indicative of the immense breadth and depth of this geometricdynamical duality — yet regrettable too — that working through its consequences occupies Prof. Zee for pretty much the entirely of his book.
This can be viewed as a fieldtheoretic instance of John Preskill’s principle, as state in his “Quantum computing and the entanglement frontier” (arXiv:1203.5813v2) that
As with Zee’s statespace restriction, it is natural to describe Preskill’s statespace restriction too, with all the mathematical tools at our disposal: informatic, differential, algebraic, stochastic, and geometric. Indeed, the lesson of field theory (per Tony Zee) is that a mature understanding will both enable us and compel us to freely translate our understanding among all of these mathematical toolsets (and more).
Surely (and fortunately!) we are a long way from achieving *that*.
We can extend the preceeding comments a bit, by envisioning two very hopeful, very progressive impacts that the ideas of Faddeev and Popov might exert on the future evolution of ideas QM/QIT/QSE/FTQSE (etc.).
By way of Tony Zee’s Quantum Field Theory in a Nutshell, the teaching of Faddeev and Popov’s pathintegral formalism is that restrictions of quantum dynamics to lowerdimension nonflat subspaces can be equivalently described as nonlinear dynamics associated to interactions with “ghost” particles
This insight authorizes us to envision two hopeful futures for QM/QIT/QSE/FTQSE.
Future A (Aram Harrow’s hopeful future): FP ghosts do *not* exist in QM/QIT/QSE/FTQSE, and yet for purposes of practical simulation it is convenient to pretend that they *do* exist (analogous to von Neumann’s method of introducing artificial viscosity to render the NavierStokes equations computationally tractable).
Future B (Gil Harrow’s hopeful future): FP ghosts *do* exist in QM/QIT/QSE/FTQSE, in the sense that experiments to induce highorder quantum correlations will (eventually) observe effects that can be ascribed equivalently to “ghost” particles that decohere quantum states (per Roger Penrose’ notion of gravitational decoherence), or alternatively to Nature’s embrace of nonlinear statespaces (per Abhay Ashtekar and Troy Schilling’s geometric formulations of quantum dynamics).
We can even envision a supremely optimistic oscillation of ideas, in which Kalai’s Future B dominates for a few decades (decades that focus upon efficient quantum simulation with classical computational resources), then Harrow’s Future A dominates for a few decades (in which practical quantum computers are realized), following which Kalai’s Future B is reborn (as M theory, what else!).
Has there ever been a more exciting time for mathematicians, scientists, and engineers alike, to embark on wonderful quests and conceive great enterprises? 🙂
For further references, the concise review “FaddeevPopov ghost” in Encyclopedia of Mathematics (European Mathematical Society/Springer) provides a reasonable startingpoint. Needless to say, best and/or most natural approach to generalize these beautiful geometric ideas to the finitedimensional algebraic statespaces of quantum computation and/or quantum simulation is far from evident to me (or anyone AFAICT).
I have a problem with how can one count possible exponentially many solutions in polynomial time, if symmetries are not involved. I even have a problem of expressing myself. In algebraic case a monomial basis should encode all possible solutions in the null space, and to distinguish the solutions one need to expand the basis that each solution has unique encoding, e.g. one needs exponentially dimensional basis, unless symmetries (or direct product, or separation of variables, which lead to direct product) are involved. For example, the system has exponentially many recognizable solutions because each equation has 2 solutions, and the solution space is a direct product of 1D solutions. The same problem I have for the quantum computer, encoding exponentially many possible solutions that are possibly encoded in the different paths with polynomially many states, unless again some (possibly hidden) symmetries are involved. Therefore, it seems to be important to recognize symmetries in both quantum and classical cases. Question: do people consider automation of the symmetry finding in the system of polynomial equations. I do not see how to formulate the analogous question about quantum computers. The former question can be reformulated in the following way – is there any known efficient procedure to rewrite system of polynomial equations that guarantee to recognize separation of variables, or almost a separation of variables. By the almost separation, I mean exponentially small number of “brigde” variables – the variables which, when removed, lead to separable set of equations. If yes, than one can solve separable systems for each set of values for bridge variables, and use the procedure recurrently.
mkatkov,
Somewhat a sidetrack– do you believe a symmetry exits in the set of perfect matchings of any bipartite graph? After all, each instance is a subset of asymmetric group.
Javaid, the symmetry is certainly exist for some bipartite graphs in the sence that permuting vertices in one part leads to the same graph. It is possible that not all graphs have symmetries. The interesting question here if there is a nonsymmetric instances that have exponentialy many solutions for some problem, and the number of solution can be counted in polynomial time. Do you have something specific in mind?
Side comment about symmetries. There is an interesting presentation by David A. Cox http://www.cs.amherst.edu/~dac/lectures/EACA.pdf Read to the end to get the point. It is not hard to encode many decision problems where optimization is not involved (satisfability problems) into system of polynomials over . For instance one can encode binary variables as if one needs 0 and 1, or if one needs . Next, one can encode the problem by adding constraint equations. For example, partition problem: given a vector we add ; SAT: for each clause add where or for negation in clause . The set of solution is given by the Groebner basis, which is hard to compute. On the other hand, if some symmetries exist, they somehow should help in computation. In particular, it is interesting in the David A. Cox presentation that one can automatically construct theorem – discovery of the symmetry. That is not that expensive for very small system. The question here whether it is possible to construct the hierarchy of theorems automatically, and what is the computational cost for this. By the way, 2SAT would have many quadratic equations, and in particular for any constraint or there are 2 complimentary equations , so the full square can be formed, from which one can get a linear constraint, from which it would be easy to compute Groebner basis.
mkatkov,
I was trying to relate people’s belief in NP!=P and enumerability of bipartite perfect matchings.
I suppose the main reason that permutation groups can be enumerated in polynomial time is because of the symmetries inherent in these groups.
For those who believe NP !=P, must also believe that certain subsets of these groups exhibit asymmetry responsible for the exponential enumeration time for the associated perfect matchings in those bipartite graphs.
Or else, #P=[F]P.
Of course, the question of classically similating some fragments of quantum computation is very basic and exciting. Since it is not known even that BQP is in NP (and it is quite reasonable to believe that BQP is not in NP) I wonder if there are some results on fragments of quantum computers which can be simulated in NP.
The following paper by Dorit Aharobnov and Umesh Vazirani Is Quantum Mechanics Falsifiable? A computational perspective on the foundations of Quantum Mechanics is related to the discussion in the post “Is this a quantum computer.“ Dorit and Umesh argue that in order to test QM in a regime where classical computers are too weak to simulate one needs to extend the scientific paradigm to include interactive experiments.