Periodicity for the 3-state quantum walk on cycles (pp1081-1088)
          Takeshi Kajiwara, Norio Konno, Shohei Koyama, and Kei Saito
Dukes (2014) and Konno, Shimizu, and Takei (2017) studied the periodicity for 2-state quantum walks whose coin operator is the Hadamard matrix on cycle graph $C_N$ with $N$ vertices. The present paper treats the periodicity for 3-state quantum walks on $C_N$. Our results follow from a new method based on the cyclotomic field. This method gives a necessary condition for the coin operator for quantum walks to be periodic. Moreover, we reveal the period $T_N$ of typical two kinds of quantum walks, the Grover and Fourier walks. We prove that both walks do not have any finite period except for $N=3$, in which case $T_3=6$ (Grover), $=12$ (Fourier).

Fine-grained quantum computational supremacy (pp1089-1115)
          Tomoyuki Morimae and Suguru Tamaki
Output probability distributions of several sub-universal quantum computing models cannot be classically efficiently sampled unless some unlikely consequences occur in classical complexity theory, such as the collapse of the polynomial-time hierarchy. These results, so called quantum supremacy, however, do not rule out possibilities of super-polynomial-time classical simulations. In this paper, we study ``fine-grained" version of quantum supremacy that excludes some exponential-time classical simulations. First, we focus on two sub-universal models, namely, the one-clean-qubit model (or the DQC1 model) and the HC1Q model. Assuming certain conjectures in fine-grained complexity theory, we show that for any $a>0$ output probability distributions of these models cannot be classically sampled within a constant multiplicative error and in $2^{(1-a)N+o(N)}$ time, where $N$ is the number of qubits.  Next, we consider universal quantum computing. For example, we consider quantum computing over Clifford and $T$ gates, and show that under another fine-grained complexity conjecture, output probability distributions of Clifford-$T$ quantum computing cannot be classically sampled in $2^{o(t)}$ time within a constant multiplicative error, where $t$ is the number of $T$ gates.

Classical and quantum bounded depth approximation algorithms (pp1116-11040)
          Matthew B. Hastings
We consider some classical and quantum approximate optimization algorithms with bounded depth.  First, we define a class of ``local" classical optimization algorithms and show that a single step version of these algorithms can achieve the same performance as the single step QAOA on MAX-3-LIN-2.  Second, we show that this class of classical algorithms generalizes a class previously considered in the literature\cite{hirvonen2014large}, and also that a single step of the classical algorithm will outperform the single-step QAOA on all triangle-free MAX-CUT instances.  In fact, for all but $4$ choices of degree, existing single-step classical algorithms already outperform the QAOA on these graphs, while for the remaining $4$ choices we show that the generalization here outperforms it. Finally, we consider the QAOA and provide strong evidence that, for any fixed number of steps, its performance on MAX-3-LIN-2 on bounded degree graphs cannot achieve the same scaling as can be done by a class of ``global" classical algorithms.  These results suggest that such local classical algorithms are likely to be at least as promising as the QAOA for approximate optimization.

Cohomological framework for contextual quantum computations (pp1141-1170)
          Robert Raussendorf
We describe a cohomological framework for measurement-based quantum computation in which symmetry plays a central role. Therein, the essential information about the computation is contained in either of two topological invariants, namely two cohomology groups. One of them applies only to deterministic quantum computations, and the other to general probabilistic ones. Those invariants characterize the computational output, and at the same time witness quantumness in the form of contextuality. In result, they give rise to fundamental algebraic structures underlying quantum computation.