A Rank Problem

[ The Daily Grail ]

Ken Regan just wrote about his paper with Chaowen Guan (GR). The paper is titled, “Stabilizer Circuits, Quadratic Forms, and Computing Matrix Rank.”

Today I thought I would add some additional comments on their result.

The post Ken wrote is thorough, detailed, and geared for an expert in quantum computation. I think he did a service to the field of quantum complexity theory with his write-up. But I thought too that there some things that he neglected to say: things that could be interesting to a wider community. So with all due respect I hope this short discussion is useful.

Quantum Circuits

In studying classic computations, we can restrict our attention to Boolean circuits. Moreover, these circuits can be assumed to consist of one type of gate. A formal way to say this is: Circuits that use NAND gates are universal. Any computation can be converted into a circuit that only uses this type of gate. It is now viewed as a trivial observation, but was not obvious in the beginning. Note, AND and OR and NOT can be implemented with just NAND gates.

The understanding of what gate types are universal is not only of interest to theorists. Some technologies support directly some types of gates, while others support different types. For example the dominant CMOS technology efficiently implements NAND gates.

[ Wikipedia ]

In studying quantum computations, we can also restrict our attention to quantum circuits. These circuits need only use gates from a small family. These gate types are more complex than just NAND gates, as you might expect since quantum circuits manipulate qubits and not just bits. I believe that it is fair to say that the fact that there are universal gates for quantum circuits is not trivial. There are many types of gates that are studied: Clifford, NOT, Fredkin, Hadamard, Toffoli, and many others.

Again the understanding of what gate types are universal is not only of interest to theorists. Quantum circuits are not easy to build, the technology is still evolving. There is yet no CMOS answer to the question: How do we build quantum hardware? Errors may be the limiting factor for large quantum circuits. We will see. One consequence of the difficulty of building universal quantum circuits is the interest in circuits that use gates that are from a family that is not universal.

The hope is several fold:

• Perhaps understanding gates that are not universal will help us understand general quantum computations.

• Perhaps some important problems in chemistry, for example, may be solvable with these non-universal circuits.

• Perhaps the mathematics of these restricted circuits will be interesting in its own right.

The third point is where GR’s work falls.

Stabilizer Circuits

The class of quantum circuits that GR studied are the stabilizer circuits. See this for an earlier discussion on these circuits. The key is that these circuits are not universal. And more importantly they can be simulated by classical computers in polynomial time. In the upside-down world of quantum complexity theory, the ability to efficiently simulate them is bad. In order to show that quantum computations are new and exciting, being able to simulate them on your laptop is not good.

The punch-line is: how efficient is this simulation? There are polynomial algorithms and there are useful polynomial algorithms. The 2004 paper by Scott Aaronson and Daniel Gottesman (AG) says that the time complexity is . Looks good.

A Breakthrough?

For a few hours, maybe days, GR thought they could show that stabilizer circuits solve the matrix rank problem. In part this was based on a misunderstanding, but it was also based on not needing the full generality of maintaining the system between single-qubit measurements. If they could calculate or even estimate the probability of just one all-qubits measurement in time then the same time would apply to computing matrix rank over the field . This would have been an immense result. The best known is that the rank of a matrix can be computed in where is the current exponent for multiplying matrices—over or any field. Today stands at .

Clearly, they were excited. I still recall Ken calling me with the possible news. I thought that it was not a crazy idea. Their plan was:

1. Reduce matrix rank to a quantum problem;

2. Show that problem could be computed by stabilizer circuits;

3. Then invoke the simulation theorem for these circuits to get a classical algorithm.

Wow. This trip from a classic problem, to a quantum one, and back was intriguing.

Saving Grace

Quickly GR figured out the issue. They could in total time determine the probability of each individual qubit being . That probability would be either or since their reduction from rank gives a circuit in which the probability of getting all s is guaranteed to be positive. If values are that does not make the answer , because of entanglements. They had thought that the Aaronson-Gottesman algorithm took care of the entanglement bookkeeping in time, but it services only one qubit in that time. Ironically, AG expressly note that they improved Gottesman’s earlier time for this task to —exactly what GR thought they would get—but AG still only get time for operations involving all the qubits.

GR worked out the full picture from a more-recent paper by Héctor García-Ramírez and Igor Markov of Michigan, which describes detailed software for simulating stabilizer circuits. Thus the quantum method would only put matrix rank into cubic time—not new. But then they realized that the goalposts for a result in the other direction were only . This they could beat with most of their hard work already done. Thus they can improve cases by AG and some subsequent papers to . In theory, that is—the algorithms are galactic. But what GR also have is a pretty result that is not galactic at all:

Theorem 1 If membership in a certain class of undirected -vertex graphs can be decided in time, then the following problems all have the same time complexity:

1. The strong simulation of quantum stabilizer circuits;

2. The computation of the rank of matrices over ;

3. The counting of solutions to classical quadratic forms modulo .

Note that all these problems have upper bounds of by GR; the point is that their bounds would coincide even if matrix rank turns out to be easier than matrix multiplication. The next post will talk about the class of graphs. Just to be clear:

• If the graphs are in time, this does not mean the problems are all in time—they could still need time.

• The graphs are in time. This is for dense graphs with order- edges.

• The reductions from rank to the other problems run in time unconditionally—the graphs involved are all bipartite so their status is known.

Open Problems

I hope that this discussion helps shed some light on the new result of GR. I hope that raising the covers on how they found their theorem is useful. Research is not smooth, is not a straight-line from start to finish, and their journey is not atypical.

[Edited wrong word: thorough and fixed qubits]