Grilling Quantum Circuits

July 8, 2012

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 ${\mathsf{BQP}}$ 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 ${\mathsf{BQP}}$ to ${\mathsf{\#P}}$ , 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 ${\mathsf{BQP}}$ 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 ${N}$ of qubit lines which go across like heating elements, and a finite number ${s}$ 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 ${s-1}$ 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 ${z_{i,j}}$ , ${1 \leq i \leq N}$ and ${0 \leq j \leq s}$ at every juncture, in the manner of a grill.

We can identify ${z_{i,0}}$ for ${1 \leq i \leq n \leq N}$ with the inputs ${x_i}$ , supposing the ${N-n}$ other ancilla inputs have been set to zero, and ${z_{i,s}}$ with outputs ${y_i}$ for selected ${i}$ . Under the standard-basis representation, the circuit ${C}$ computes a ${2^N \times 2^N}$ linear operator ${U_C}$ applied to the (padded representation of the) input ${x \in \{0,1\}^n 0^{N-n}}$ .

Known results show how to compute the acceptance probability of ${C}$ on input ${x}$ from the scalar values ${u = x U_C y}$ for certain target values ${y}$ . The game is to express ${u}$ using polynomial(s) in the ${z}$ -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 ${c}$ .

Hadamard gates are balanced with ${c = 1/\sqrt{2}}$ , and CNOT and Toffoli and all other deterministic gates are balanced with ${c = 1}$ . Hence ${\mathsf{BQP}}$ can be defined via circuits of balanced gates. We call ${1/c}$ the balance factor.

High Versus Low Degree Grilling

Given a polynomial ${p}$ in ${r}$ -many variables and a value ${v}$ , denote by ${N[p:v]}$ the number of arguments ${z \in \{0,1\}^{r}}$ such that ${p(z) = v}$ . For a quantum circuit ${C}$ we can identify an integer ${m > 0}$ such that ${2\pi/m}$ is the greatest common divisor of the angular component of complex-number matrix entries of gates in ${C}$ . Call ${2\pi/m}$ the min-phase of ${C}$ , and let ${\omega}$ stand for a primitive ${m}$ th root of unity. Our first theorem turns ${\omega}$ around like a rotisserie:

Theorem 2. Given a balanced quantum circuit ${C}$ with min-phase ${2\pi/m}$ and values ${x,y}$ , we can construct in polynomial time a polynomial ${p}$ with values in ${\{0\} \cup \{\omega^k\}}$ and a real number ${R \geq 1}$ such that

$\displaystyle y U_C x = \frac{1}{R} \sum_{k = 0}^{m-1} \omega^{k} N[p:\omega^k].$

Here ${p = \prod_g p_g}$ is a product of terms for each gate, and ${R}$ 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 ${\mathbb{Z}_m}$ instead. My main innovation is using extra variables “ ${w}$ ” (shown later) to solve technical problems noted in an above-linked paper when ${m > 2}$ .

Theorem 3. Given a balanced quantum circuit ${C}$ with min-phase ${2\pi/m}$ and values ${x,y}$ , we can construct in polynomial time a polynomial ${q}$ with values in ${\mathbb{Z}_m}$ and real number ${R \geq 1}$ such that

$\displaystyle y U_C x = \frac{1}{R} \sum_{k = 0}^{m-1} \omega^{k} N[q: k].$

Here ${q = \sum_g q_g}$ is a sum of terms for each gate, which keeps the total degree down but involves extra variables, while ${R}$ may be the same or greater depending on whether the domain of assignments is over ${\mathbb{Z}_m}$ or ${\{0,1\}}$ .

When ${m=2}$ , which suffices for the universal set of Hadamard and Toffoli gates, ${\omega = -1}$ , and both formulas give a difference of solution counts. Since the solution count is a ${\mathsf{\#P}}$ function even for the higher-degree ${p}$ polynomial, this recovers the result that ${\mathsf{BQP}}$ reduces to the difference of two ${\mathsf{\#P}}$ functions ${f_0,f_1}$ .

This raises the hope that Larry Stockmeyer’s ${(1 + \epsilon)}$ factor approximation might put ${\mathsf{BQP}}$ into the polynomial hierarchy, but there are two problems:

Approximating ${f_0,f_1}$ to within ${(1 + \epsilon)}$ need not approximate their difference to any similar factor.
The value ${R}$ is small, roughly the square root of the magnitudes attained by ${f_0}$ and ${f_1}$ , so that the property guaranteed by the theorems that
$\displaystyle \left|\frac{1}{R}(f_0 - f_1)\right| \leq 1$

is actually a substantial promise condition observed by the quantum circuit ${C}$ itself.

The second factor makes the first issue “bite”—but also suggests recipes for getting simulations of ${C}$ into the hierarchy, or even into classical polynomial time especially for cases of the low-degree polynomials ${q}$ . The recipes involve substitutions, special cases of ${\mathsf{\#P}}$ -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 ${g}$ by terms for ${p}$ and ${q}$ .

Cookbook of Gates

We use ${y}$ or ${y_i}$ in place of the ${z_{i,j}}$ -variable of a gate input, and ${z}$ or ${z_i}$ similarly for outputs. For a single-qubit gate ${g}$ , the rows and columns are indexed like this:

$\displaystyle \begin{array}{rcc} & (1-z) & z\\ (1-y) & a_{11} & a_{12}\\ y & a_{21} & a_{22}, \end{array}$

and the corresponding term ${p_g}$ for the product polynomial ${p}$ is given by

$\displaystyle p_g = a_{11}(1-y)(1-z) + a_{12}(1-y)z + a_{21}y(1-z) + a_{22}yz.$

For the NOT gate, also called ${X}$ , we have

$\displaystyle \left[\begin{array}{cc} 0 & 1\\ 1 & 0 \end{array}\right];\quad p_g = (1-y)z + y(1-z) = y + z - 2yz.$

For 0-1 arguments, note this gives ${0}$ when ${y = z}$ , which kills the whole product. Thus the solution sets are unchanged if we substitute ${z = 1 - y}$ . Then ${p_g}$ cancels down to ${1}$ , and we have saved a term in the product.

The identity gate is handled similarly: we can introduce the term ${2yz - y - z + 1}$ , or just substitute ${z = y}$ 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 ${a_{i,j}}$ , we multiply by the log base ${\omega}$ of that entry, except that when ${a_{i,j} = 0}$ , we introduce new variable(s) ${w}$ . Thus the NOT gate gives

$\displaystyle q_g = (1-y)(1-z)w + (1-y)z\cdot 0 + y(1-z)\cdot 0 + yzw = w(2yz - y - z + 1).$

Now when ${z = y = 0}$ or ${z = y = 1}$ the ${w}$ is left alone as an additive term. When ${m}$ is a power ${2^\ell}$ we can use ${\ell}$ -many ${w}$ -variables with multipliers to make an additive term that assumes all values in ${0\dots m-1}$ with equal weight given assignments in ${\{0,1\}^{\ell}}$ . The set of constraint-violating assignments in which this ${w}$ -term survives is thus partitioned into ${m}$ equal subsets giving the ${m}$ different values. Since the sum of the ${m}$ th roots of unity is zero, these give a net-zero contribution to the sum representation of ${x U_C y}$ .

Again we can substitute ${z = 1 - y}$ , and this dispenses with the ${w}$ -variables leaving just zero. We can always do substitution for any deterministic gate, even one with imaginary entries such as the Phase Gate:

$\displaystyle S = \left[\begin{array}{cc} 1 & 0\\ 0 & i\end{array}\right]\;\quad p_g = (1-y)(1-z) + iyz;\quad q_g = w(y+z-2yz) + \frac{m}{4}yz.$

Hadamard Case

For Hadamard gates we pull the balance factor ${\sqrt{2}}$ outside, and note that ${-1 = \omega^{m/2}}$ .

$\displaystyle \left[\begin{array}{cc} 1 & 1\\ 1 & -1\end{array}\right];\quad p_g = (1-y)(1-z+z) + y(1-z) - yz = 1-yz.$

And ${q_g}$ is just ${\frac{m}{2}yz}$ . 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 ${y_1,y_2}$ has a ${4 \times 4}$ matrix with rows indexed ${(1-y_1)(1-y_2)}$ , ${(1-y_1)y_2}$ , ${y_1(1-y_2)}$ , ${y_1 y_2}$ , and columns similarly for the outputs ${z_1,z_2}$ . For example:

$\displaystyle \text{CNOT} = \left[\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\end{array}\right],\quad \text{CZ} = \left[\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & -1\end{array}\right].$

The ${p}$ -polynomial for CNOT includes a term ${y_1(1 - y_2)z_1 z_2}$ for the final ‘$1$’ in the third row, while the ${q}$ -polynomial has twelve terms multiplied by ${w}$ but nothing else. They become ${1}$ and ${0}$ , respectively, under the substitution ${z_1 = y_1}$ , ${z_2 = y_1 + y_2 - 2 y_1 y_2}$ , which represents the deterministic action. The Toffoli gate is similar for three inputs/outputs and an ${8 \times 8}$ matrix.

For the CZ gate the bottom-right ${-1}$ entry contributes ${-y_1 y_2 z_1 z_2}$ to ${p}$ but ${\frac{m}{2}y_1 y_2 z_1 z_2}$ to ${q}$ . The substitution ${z_1 = y_1}$ , ${z_2 = y_2}$ is applicable, but does not leave ${1}$ in the ${p}$ -case, but rather ${(1 - 2y_1 y_2)}$ . In the additive case it leaves ${\frac{m}{2}y_1^2 y_2^2}$ , which is equivalent to ${\frac{m}{2}y_1 y_2}$ for 0-1 assignments. The additive case, of course, has a similar ${w}$ -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:

Wider set of quantum gates handled directly.
Multiplicative as well as additive representation.
Single polynomial not set of polynomials.
Extra “ ${w}$ ” variables avoid mixed arithmetic in additive case.
Freedom to substitute or not.
Wide choice of target ring allows encoding ${\mathsf{BQP}}$ into many algebraic problems and exploring tradeoffs.

Circuit Simulations and Invariants

To compute ${u = x U_C y}$ exactly, we need to calculate ${N[p:v]}$ or ${N[q:v]}$ for some finite set of values ${v}$ . Gerdt and Severyanov outline a procedure for solution counting using Gröbner bases and triangular forms. But to simulate ${\mathsf{BQP}}$ we need not compute exactly—we need only distinguish accepting from rejecting cases, which basically means distinguishing ${|u|}$ near zero from ${|u|}$ near ${1}$ . This may motivate new methods for approximate counting.

Here is a circuit previously used as an example in the earlier-linked papers, treating ${a_i}$ and ${b_j}$ as variables to be filled from ${x}$ and ${y}$ , followed by the ${p}$ and ${q}$ polynomials.

The Hadamard and Toffoli gates are arranged so as to produce entangled states. On input ${|000\rangle}$ , the state in the middle after the first Toffoli gate is

$\displaystyle \frac{1}{2}(|000\rangle + |010\rangle + |100\rangle + |111\rangle).$

It is not meaningful to assign the separate values ${\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)}$ to the first two qubits and ${\frac{1}{2}(\sqrt{3}|0\rangle + |1\rangle)}$ 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 ${q}$ -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 ${p(x_1,\dots,x_n)}$ : allocate new variables ${y_1,\dots,y_n}$ and form the polynomial ideal ${J(p)}$ generated by the polynomials

$\displaystyle y_1 - \frac{\partial p}{\partial x_1},\dots, y_n - \frac{\partial p}{\partial x_n}.$

The graph of this mapping in the ${2n}$ -dimensional ${x}$ – ${y}$ space is topologically irreducible and hence has an unambiguously defined geometric degree ${\delta(p)}$ . The Baur-Strassen quantity ${\gamma(p) = \log_2\delta(p)}$ is their famous lower bound on circuits for ${p}$ , as we covered here.

What makes ${\gamma(\cdot)}$ 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 ${N}$ 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 ${S}$ phase gate, and the CZ gate. Over ${\mathbb{Z}_4}$ the ${q}$ -polynomials for circuits built from these gates are incredibly simple.

Each term is either a variable squared, ${y^2}$ , or a product ${2yz}$ .

These terms are invariant under changing ${y}$ from ${1}$ to ${3}$ and are zeroed out by ${y=0}$ and ${y=2}$ , so for ${r}$ variables the domains ${\{0,1\}^r}$ and ${\mathbb{Z}_4^r}$ are essentially the same. Can we inductively compute the quantities ${N[q:0],N[q:1],N[q:2],N[q:3]}$ 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 ${\mathsf{\#P}}$ -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 ${\mathbb{Z}_4}$ all of whose terms have the form ${y^2}$ or ${2yz}$ in ${\mathsf{P}}$ ? Or is this restricted problem still ${\mathsf{\#P}}$ -complete, so that our simulation would need to find additional structure in the polynomials? Update: It is indeed in ${\mathsf{P}}$ , 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]

Grilling Quantum Circuits

Grilling Quantum Circuits

The Grille

High Versus Low Degree Grilling

Cookbook of Gates

Additive Case

Hadamard Case

Multi-Qubit Cases

Circuit Simulations and Invariants

Open Problems

Like this:

Recommend

Stevö John

31省区市新增本土确诊30例

minimal%20apis%20at%20a%20glance%20in%20.net%206

欧盟提议强制所有设备使用 USB-C

美国与欧盟将在监管科技巨头方面紧密合作

安全研究员披露三个 iOS 0day 漏洞

Regarding the security advisory for Canon digital cameras related to PTP (Pictur...

FedEx 首次使用自动驾驶卡车运货

Can You Hear the Shape of a Quantum Computer?

加州通过针对亚马逊劳工算法的法律

About Joyk