David Zuckerman FOCS 2019 PC Chair Review #72A =========================================================================== Paper summary ------------- The paper claims as its contribution the following: (1) A n^omega algorithm to simulate Stabilizer quantum circuits. (2) A reduction from rank computation of a matrix over GF(2) to simulating a stabilizer quantum circuit. Matrix rank computation is reduced to amplitude computation of a quantum circuit. Strengths --------- The route through quadratic forms seems to give an alternate proof of Gottesman-Knill theorem. Weaknesses ---------- While Gottesman-Knill might not have been very careful with the exponent, I believe that there approach can be made to fit into the n^omega bound. So I do not see much in the technique. The basic ideas/ motivation are not discussed up front. Eg. classically n^omega time is trivial, so why should one care about the quantum analogue? Summary recommendation ---------------------- I would therefore recommend the rejection of this paper. Comments for authors -------------------- While I think the paper is correct I do not think there is sufficient strength in results here. The n^omega simulation result although new, is not too surprising --- Gaussian elimination can often be converted to determinant calculation and inversion which can easily be achieved in n^omega. The writing needs to be tightened up. Many of the initial sections where the quadratic form qC is constructed could be easily condensed which would give space to include the proofs that are currently in the appendix. Authors my also explore if using the Dirac notation instead of explicit matrices could have made the presentation easier. For example, the "update" of the qC polynomial as q += 2u_iy_ell could easily be seen had all the operators and states been written in Dirac notation: The hadamard sends the state |u> -> \sum_y (-1)^uy |y> and hence Also the mixing of the quadratic forms over GF(2) and Z/2Z lead to quite a bit of confusion. It might be good if the authors clean this bit up. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Review #72B =========================================================================== Paper summary ------------- The study of classical simulation of quantum computation deals with the following central question: given a class of quantum circuits, what is the fastest classical algorithm that can simulate it? In this paper, the class of quantum circuits considered is the class of stabilizer circuits. In prior works, the best known asymptotic running time for (strongly) simulating stabilizer circuits on a classical computer (when n qubits are measured) was O(n^3). The main result of this paper is an algorithm that improves on this bound, and shows that such a strong simulation can be performed in O(n^w), where w < 2.3729 is the matrix-multiplication exponent. A caveat is that this running time holds only for stabilizer circuits satisfying certain conditions, namely circuits that have 'typical' size and indeterminism. The paper also shows a linear-time reduction from matrix rank over F_2 to strong simulation. Strengths --------- I found the paper to be well-written, detailed and well-organized. The problem chosen is well-motivated and important to the goal of understanding the classical simulability of stabilizer circuits. The techniques used also illustrate an important connection between quantum circuits and quadratic forms. Weaknesses ---------- One limitation of this result is that the advantage over previous results applies to a fairly restrictive class of circuits, namely stabilizer circuits satisfying 'typical' size and indeterminism, and strong simulation where all n qubits are measured. While this is an important class of circuits, it would be nice to see a discussion about whether the techniques used here can also be applied to more general settings. Summary recommendation ---------------------- The paper is interesting but the a bit too specialized and incremental for FOCS. Comments for authors -------------------- Some suggestions/feedback/typos are as follows: 1. In the abstract, it is stated that a form of strong simulation of stabilizer circuits is computable in O(s+n^w) time. However, s was not defined in the abstract. 2. Line below Theorem 2.2: There is a reference to Lemma 5.1(d). However, Lemma 5.1 has only 3 parts and does not have a part (d). 3. Page 12, 25: extra semicolon for the b=2 case. 4. The main result applies to the case when all n qubits of the stabilizer circuit are measured. Can this result be extended to the case when only a fraction of the output registers is measured? 5. I'm confused by Definition 6.3. What do z and y refer to? * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Review #72C =========================================================================== Paper summary ------------- This paper considers the task of classical strong simulation for quantum stabilizer circuits--computing probabilities p=|<0|C|0>|^2 where C is a Clifford unitary. It is shown that this task can be reduced to a linear algebra task over F2 which requires the same number of operations n^{\omega} as matrix multiplication. Likewise it is shown that the task of computing the rank of a matrix over F2 can be reduced to the above strong simulation task. The main technique in the paper is to express p as a sum-over-paths (by expanding each Hadamard in the Clifford circuit) and thus obtain an expression for p as proportional to a sum \sum_{y} i^{q(y)} where the sum runs over bit strings y (of length equal to the number of Hadamards in the circuit) and the function q(y) is a Z4-valued quadratic form. The authors use linear algebra to affect a change of basis in F2^{n} which permits the evaluation of the above sum. The analysis is mostly linear algebra and is also based on the known canonical forms for Z4-valued quadratic forms. Strengths --------- The paper contains a very nice review of Schmidt's treatment of Z4-vaued quadratic forms. The connection between quadratic forms and stabilizer circuits is well known but perhaps in the current literature has not been pushed as far as it can go. Weaknesses ---------- The fact that Clifford circuits can be simulated (strongly or weakly) using linear algebra is of course well known. As the authors point out, it does not seem that anyone has shown that these (slightly nonstandard) linear algebra tasks can be performed in the same number of operations as matrix multiplication, so the results appear to be new, although not very surprising. Summary recommendation ---------------------- This is a solid paper which would be reasonable to accept, but I would not argue that it is a "must" accept, given the high bar of acceptance for FOCS. Therefore I believe it is borderline, and would be nice to have at FOCS if space allows. Comments for authors -------------------- I wonder if the results in this paper could be obtained in a more direct way along the following lines. This is speculative, and I leave it here for the authors in case it is helpful: Let p=|<0|C|0>|^2 and suppose our goal is to compute p. Each stabilizer of the state C|0> can be written as i^{w_j} Z(a_j) X(b_j) for some n-bit strings a_j,b_j and integer w_j\in {0,1,2,3}. The stabilizer group is the group generated by all such stabilizers of C|0>. Let us say that an element of the stabilizer group is a Z-type stabilizer if b_j=0. It is easy to see that p is nonzero if and only if the Z-type stabilizers all have w_j=0. Suppose there are m Z-type stabilizers in the stabilizer group. Then, if it is nonzero I believe the value of p should be 1/2^(n-m). It seems to me that both of these problems can be easily related to questions about quadratic forms (generated in the phase when stabilizers of the above form are multiplied) and linear algebra.