
Blind delegation protocols allow a client to delegate a computation to a
server so that the server learns nothing about the input to the computation
apart from its size. For the specific case of quantum computation we know that
blind delegation protocols can achieve informationtheoretic security. In this
paper we prove, provided certain complexitytheoretic conjectures are true,
that the power of informationtheoretically secure blind delegation protocols
for quantum computation (ITSBQC protocols) is in a number of ways constrained.
In the first part of our paper we provide some indication that ITSBQC
protocols for delegating $\sf BQP$ computations in which the client and the
server interact only classically are unlikely to exist. We first show that
having such a protocol with $O(n^d)$ bits of classical communication implies
that $\mathsf{BQP} \subset \mathsf{MA/O(n^d)}$. We conjecture that this
containment is unlikely by providing an oracle relative to which $\mathsf{BQP}
\not\subset \mathsf{MA/O(n^d)}$. We then show that if an ITSBQC protocol
exists with polynomial classical communication and which allows the client to
delegate quantum sampling problems, then there exist nonuniform circuits of
size $2^{n  \mathsf{\Omega}(n/log(n))}$, making polynomiallysized queries to
an $\sf NP^{NP}$ oracle, for computing the permanent of an $n \times n$ matrix.
The second part of our paper concerns ITSBQC protocols in which the client and
the server engage in one round of quantum communication and then exchange
polynomially many classical messages. First, we provide a complexitytheoretic
upper bound on the types of functions that could be delegated in such a
protocol, namely $\mathsf{QCMA/qpoly \cap coQCMA/qpoly}$. Then, we show that
having such a protocol for delegating $\mathsf{NP}$hard functions implies
$\mathsf{coNP^{NP^{NP}}} \subseteq \mathsf{NP^{NP^{PromiseQMA}}}$.

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.

With experimental quantum computing technologies now in their infancy, the
search for efficient means of testing the correctness of these quantum
computations is becoming more pressing. An approach to the verification of
quantum computation within the framework of interactive proofs has been
fruitful for addressing this problem. Specifically, an untrusted agent (prover)
alleging to perform quantum computations can have his claims verified by
another agent (verifier) who only has access to classical computation and a
small quantum device for preparing or measuring single qubits. However, when
this quantum device is prone to errors, verification becomes challenging and
often existing protocols address this by adding extra assumptions, such as
requiring the noise in the device to be uncorrelated with the noise on the
prover's devices. In this paper, we present a simple protocol for verifying
quantum computations, in the presence of noisy devices, with no extra
assumptions. This protocol is based on post hoc techniques for verification,
which allow for the prover to know the desired quantum computation and its
input. We also perform a simulation of the protocol, for a onequbit
computation, and find the error thresholds when using the qubit repetition code
as well as the Steane code.

The relationship between correlations and entanglement has played a major
role in understanding quantum theory since the work of Einstein, Podolsky and
Rosen (1935). Tsirelson (1980) proved that Bell states, shared among two
parties, when measured suitably, achieve the maximum nonlocal correlations
allowed by quantum mechanics. Conversely, Reichardt, Unger and Vazirani (2013)
showed that observing the maximal correlation value over a sequence of repeated
measurements, implies that the underlying quantum state is close to a tensor
product of maximally entangled states and, moreover, that it is measured
according to an ideal strategy. However, this strong rigidity result comes at a
high price, requiring a large number of entangled pairs to be tested. In this
paper, we present a significant improvement in terms of the overhead by instead
considering quantum steering where the device of the one side is trusted. We
first demonstrate a robust onesided deviceindependent version of
selftesting, which characterises the shared state and measurement operators of
two parties up to a certain bound. We show that this bound is optimal up to
constant factors and we generalise the results for the most general attacks.
This leads us to a rigidity theorem for maximal steering correlations. As a key
application we give a onesided deviceindependent protocol for verifiable
delegated quantum computation, and compare it to other existing protocols, to
highlight the cost of trust assumptions. Finally, we show that under reasonable
assumptions, the states shared in order to run a certain type of verification
protocol must be unitarily equivalent to perfect Bell states.

Recent advances in theoretical and experimental quantum computing bring us
closer to scalable quantum computing devices. This makes the need for protocols
that verify the correct functionality of quantum operations timely and has led
to the field of quantum verification. In this paper we address key challenges
to make quantum verification protocols applicable to experimental
implementations. We prove the robustness of the single server verifiable
universal blind quantum computing protocol of Fitzsimons and Kashefi (2012) in
the most general scenario. This includes the case where the purification of the
deviated input state is in the hands of an adversarial server. The proved
robustness property allows the composition of this protocol with a
deviceindependent state tomography protocol that we give, which is based on
the rigidity of CHSH games as proposed by Reichardt, Unger and Vazirani (2013).
The resulting composite protocol has lower round complexity for the
verification of entangled quantum servers with a classical verifier and, as we
show, can be made fault tolerant.