
Quantum samplers are believed capable of sampling efficiently from
distributions that are classically hard to sample from. We consider a sampler
inspired by the classical Ising model. It is nonadaptive and therefore
experimentally amenable. Under a plausible conjecture, classical sampling upto
additive errors from this model is known to be hard. We present a trapbased
verification scheme for quantum supremacy that only requires the verifier to
prepare singlequbit states. The verification is done on the same model as the
original sampler, a square lattice, with only a constant overhead. We next
revamp our verification scheme in two distinct ways using fault tolerance that
preserves the nonadaptivity. The first has a lower overhead based on error
correction with the same threshold as universal quantum computation. The second
has a higher overhead but an improved threshold (1.97\%) based on error
detection. We show that classically sampling upto additive errors is likely
hard in both these schemes. Our results are applicable to other sampling
problems such as the Instantaneous Quantum Polynomialtime (IQP) computation
model. They should also assist nearterm attempts at experimentally
demonstrating quantum supremacy and guide longterm ones.

We present two verification protocols where the correctness of a "target"
computation is checked by means of "trap" computations that can be efficiently
simulated on a classical computer. Our protocols rely on a minimal set of
noisefree operations (preparation of eight singlequbit states or measurement
of four observables, both on a single plane of the Bloch sphere) and achieve
linear overhead. To the best of our knowledge, our protocols are the least
demanding techniques able to achieve linear overhead. They represent a step
towards further reducing the quantum requirements for verification.

Quantum computers promise to efficiently solve not only problems believed to
be intractable for classical computers, but also problems for which verifying
the solution is also considered intractable. This raises the question of how
one can check whether quantum computers are indeed producing correct results.
This task, known as quantum verification, has been highlighted as a significant
challenge on the road to scalable quantum computing technology. We review the
most significant approaches to quantum verification and compare them in terms
of structure, complexity and required resources. We also comment on the use of
cryptographic techniques which, for many of the presented protocols, has proven
extremely useful in performing verification. Finally, we discuss issues related
to fault tolerance, experimental implementations and the outlook for future
protocols.

The efficient certification of classically intractable quantum devices has
been a central research question for some time. However, to observe a "quantum
advantage", it is believed that one does not need to build a large scale
universal quantum computer, a task which has proven extremely challenging.
Intermediate quantum models that are easier to implement, but which also
exhibit this quantum advantage over classical computers, have been proposed. In
this work, we present a certification technique for such a subuniversal
quantum server which only performs commuting gates and requires very limited
quantum memory. By allowing a verifying client to manipulate single qubits, we
exploit properties of measurement based blind quantum computing to give them
the tools to test the "quantum superiority" of the server.

We propose a new composable and informationtheoretically secure protocol to
verify that a server has the power to sample from a subuniversal quantum
machine implementing only commuting gates. By allowing the client to manipulate
single qubits, we exploit properties of Measurement based Blind Quantum
Computing to prove security against a malicious Server and therefore certify
quantum supremacy without the need for a universal quantum computer.

In the absence of any efficient classical schemes for verifying a universal
quantum computer, the importance of limiting the required quantum resources for
this task has been highlighted recently. Currently, most of efficient quantum
verification protocols are based on cryptographic techniques where an almost
classical verifier executes her desired encrypted quantum computation remotely
on an untrusted quantum prover. In this work we present a new protocol for
quantum verification by incorporating existing techniques in a nonstandard
composition to reduce the required quantum communications between the verifier
and the prover.

We present a quantumlyenhanced protocol to achieve unconditionally secure
delegated classical computation where the client and the server have both
limited classical and quantum computing capacity. We prove the same task cannot
be achieved using only classical protocols. This extends the work of Anders and
Browne on the computational power of correlations to a security setting.
Concretely, we present how a client with access to a nonuniversal classical
gate such as a parity gate could achieve unconditionally secure delegated
universal classical computation by exploiting minimal quantum gadgets. In
particular, unlike the universal blind quantum computing protocols, the
restriction of the task to classical computing removes the need for a full
universal quantum machine on the side of the server and makes these new
protocols readily implementable with the currently available quantum technology
in the lab.

While building a universal quantum computer remains challenging, devices of
restricted power such as the socalled one pure qubit model have attracted
considerable attention. An important step in the construction of these limited
quantum computational devices is the understanding of whether the verification
of the computation within these models could be also performed in the
restricted scheme. Encoding via blindness (a cryptographic protocol for
delegated computing) has proven successful for the verification of universal
quantum computation with a restricted verifier. In this paper, we present the
adaptation of this approach to the one pure qubit model, and present the first
feasible scheme for the verification of delegated one pure qubit model of
quantum computing.