Finegrained quantum computational supremacy It is known that several subuniversal quantum computing models cannot be classically simulated in polynomialtime unless the polynomialtime hierarchy collapses. These results, however, do not rule out possibilities of exponential or subexponentialtime classical simulations. In this paper, we study finegrained quantum computational supremacy that excludes superpolynomialtime classical simulations. We first consider the DQC1 model. We show that for any au003e0 output probability distributions of the Nqubit DQC1 model cannot be classically sampled within a constant multiplicative error and in 2(1a)No(N) time (under certain conjectures in finegrained complexity theory). We next show similar finegrained quantum supremacy results for the HC1Q model, which is another subuniversal model with a classical circuit sandwiched by two Hadamard layers. Finally, we also consider universal quantum computing with Clifford and T gates. We first show that under the exponentialtime hypothesis (ETH), output probability distributions of CliffordT quantum computing cannot be calculated in 2o(t) time within an additive error smaller than 2frac3t147, where t is the number of T gates. We next show that under another finegrained complexity conjecture, output probability distributions of CliffordT quantum computing cannot be classically sampled in 2o(t) time within a constant multiplicative error. There is a classical algorithm that calculates output probability distributions of CliffordT quantum computing within a constant multiplicative error in sim2beta t time with a nontrivial factor betasimeq0.47 S. Bravyi and D. Gosset, Physical Review Letters 116, 250501 (2016). Our second result on CliffordT quantum computing therefore suggests that improving 2beta t to subexponential time, say 2sqrtt, is impossible.

Span programs and quantum space complexity While quantum computers hold the promise of significant computational speedups, the limited size of early quantum machines motivates the study of spacebounded quantum computation. We relate the quantum space complexity of computing a function f with onesided error to the logarithm of its span program size, a classical quantity that is wellstudied in attempts to prove formula size lower  the :59,more natural bounded error model, we show that the amount of space needed for a unitary quantum algorithm to compute f with bounded (twosided) error is lower bounded by the logarithm of its approximate span program size. Approximate span programs were introduced in the field of quantum algorithms but not studied classically. However, the approximate span program size of a function is a natural generalization of its span program  :130,no nontrivial lower bound is known on the span program size (or approximate span program size) of any concrete function, a number of lower bounds are known on the monotone span program size. We show that the approximate monotone span program size of f is a lower bound on the space needed by quantum algorithms of a particular form, called monotone phase estimation algorithms, to compute f. We then give the first nontrivial lower bound on the approximate span program size of an explicit function.