Title: Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy,
Abstract: We introduce a simple sub-universal quantum computing model, which we call
the Hadamard-classical circuit with one-qubit (HC1Q) model. It consists of a
classical reversible circuit sandwiched by two layers of Hadamard gates, and
therefore it is in the second level of the Fourier hierarchy. We show that
output probability distributions of the HC1Q model cannot be classically
efficiently sampled within a multiplicative error unless the polynomial-time
hierarchy collapses to the second level. The proof technique is different from
those used for previous sub-universal models, such as IQP, Boson Sampling, and
DQC1, and therefore the technique itself might be useful for finding other
sub-universal models that are hard to classically simulate. We also study the
classical verification of quantum computing in the second level of the Fourier
hierarchy. To this end, we define a promise problem, which we call the
probability distribution distinguishability with maximum norm (PDD-Max). It is
a promise problem to decide whether output probability distributions of two
quantum circuits are far apart or close. We show that PDD-Max is BQP-complete,
but if the two circuits are restricted to some types in the second level of the
Fourier hierarchy, such as the HC1Q model or the IQP model, PDD-Max has a
Merlin-Arthur system with quantum polynomial-time Merlin and classical
probabilistic polynomial-time Arthur.