Fine-grained quantum computational supremacy

No ratings

Presented at Tokyo Crypto Day 2019 by

It is known that several sub-universal quantum computing models cannot be classically simulated in polynomial-time unless the polynomial-time hierarchy collapses. These results, however, do not rule out possibilities of exponential- or sub-exponential-time classical simulations. In this paper, we study fine-grained quantum computational supremacy that excludes superpolynomial-time classical simulations. We first consider the DQC1 model. We show that for any a>0 output probability distributions of the N-qubit DQC1 model cannot be classically sampled within a constant multiplicative error and in 2^{(1–a)N+o(N)} time (under certain conjectures in fine-grained complexity theory). We next show similar fine-grained quantum supremacy results for the HC1Q model, which is another sub-universal 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 exponential-time hypothesis (ETH), output probability distributions of Clifford-T quantum computing cannot be calculated in 2^{o(t)} time within an additive error smaller than 2^{(–3t+14)/7}, where t is the number of T gates. We next 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. There is a classical algorithm that calculates output probability distributions of Clifford-T quantum computing within a constant multiplicative error in ∼2^{βt} time with a non-trivial factor β ≅ 0.47 [S. Bravyi and D. Gosset, Physical Review Letters 116, 250501 (2016)]. Our second result on Clifford-T quantum computing therefore suggests that improving 2^{βt} to sub-exponential time, say 2^{√t}, is impossible.