Gödel’s Lost Letter and P=NP

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 co-workers 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 multi-variable 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 standard-basis 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 complex-number matrix entries of gates in . Call the min-phase 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 min-phase 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 low-degree cooking we can work additively in instead. My main innovation is using extra variables “” (shown later) to solve technical problems noted in an above-linked paper when .

Theorem 3. Given a balanced quantum circuit with min-phase 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 higher-degree 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:

  1. Approximating to within need not approximate their difference to any similar factor.
  2. 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 low-degree 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 single-qubit 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 0-1 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 constraint-violating 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 net-zero 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 non-determinism for the polynomials, which is all-important.

Multi-Qubit Cases

A 2-qubit 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 bottom-right 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 0-1 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 variable-phase Shor gates. The net improvements over previous work are:

  1. Wider set of quantum gates handled directly.
  2. Multiplicative as well as additive representation.
  3. Single polynomial not set of polynomials.
  4. Extra “” variables avoid mixed arithmetic in additive case.
  5. Freedom to substitute or not.
  6. 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 earlier-linked 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, non-entangled, 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 non-entangled 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 Baur-Strassen 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 non-increasing 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 so-called 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 newly-motivated special cases of -complete counting problems to study.

Open Problems

Can polynomial algebra using our grilles out-perform other classical simulations of quantum circuits that have been programmed?

Is solution-counting 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 co-authored 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]