
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.

The swap test is a central primitive in quantum information, providing an
efficient way of comparing two unknown quantum states. In this work, we
generalise this test for the case where one has access to multiple copies of a
reference state, but to only one copy of the tested state. We present a circuit
implementing this test and propose a simple linear optical implementation using
the Hadamard interferometer. We show that both the circuit and the
interferometer can be used as programmable projective measurement devices, with
a precision scaling with their size. This also leads to a natural
interpretation of the notion of projective measurement in quantum mechanics.

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.

As research on building scalable quantum computers advances, it is important
to be able to certify their correctness. Due to the exponential hardness of
classically simulating quantum computation, straightforward verification via
this means fails. However, we can classically simulate small scale quantum
computations and hence we are able to test that devices behave as expected in
this domain. This constitutes the first step towards obtaining confidence in
the anticipated quantumadvantage when we extend to scales that can no longer
be simulated.
Real devices have restrictions due to their architecture and limitations due
to physical imperfections and noise. In this paper we extend the usual ideal
simulations by considering those effects. We aim to provide a general
methodology and framework for constructing simulations which emulate the
physical system. These simulations should provide a benchmark for realistic
devices and guide experimental research in the quest for quantumadvantage.
To illustrate our methodology we give examples that involve networked
architectures and the noisemodel of the device developed by the Networked
Quantum Information Technologies Hub (NQIT). For our simulations we use, with
suitable modification, the classical simulator of Bravyi and Gosset while the
specific problems considered belong to the Instantaneous Quantum
Polynomialtime class. This class is believed to be hard for classical
computational devices, and is regarded as a promising candidate for the first
demonstration of quantumadvantage. We first consider a subclass of IQP,
defined by BermejoVega et al, involving twodimensional dynamical quantum
simulators, and then general instances of IQP, restricted to the architecture
of NQIT.

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 define the functionality of delegated pseudosecret random qubit generator
(PSRQG), where a classical client can instruct the preparation of a sequence of
random qubits at some distant party. Their classical description is
(computationally) unknown to any other party (including the distant party
preparing them) but known to the client. We emphasize the unique feature that
no quantum communication is required to implement PSRQG. This enables classical
clients to perform a class of quantum communication protocols with only a
public classical channel with a quantum server. A key such example is the
delegated universal quantum computing. Using our functionality one could
achieve for the first time a purely classicalclient computational secure
verifiable delegated universal quantum computing (also referred to as
verifiable blind quantum computation). We give a concrete protocol (QFactory)
implementing PSRQG, using the LearningWithErrors problem to construct a
trapdoor oneway function with certain desired properties (quantumsafe,
tworegular, collisionresistant). We then prove the security in the
QuantumHonestButCurious setting and briefly discuss the extension to the
malicious case.

We introduce a notion of contextuality for transformations in sequential
contexts, distinct from the BellKochenSpecker and Spekkens notions of
contextuality, which can arise even in a single qubit system. Within a
transformationbased model for quantum computation we show that strong
sequential transformation contextuality is necessary for deterministic
computation of nonlinear functions. For probabilistic computation, sequential
transformation contextuality is necessary for obtaining advantage over
classical implementations and the degree of advantage quantifiably relates to
the degree of contextuality.

We introduce a new family of quantum circuits in Continuous Variables and we
show that, relying on the widely accepted conjecture that the polynomial
hierarchy of complexity classes does not collapse, their output probability
distribution cannot be efficiently simulated by a classical computer. These
circuits are composed of input photonsubtracted (or photonadded) squeezed
states, passive linear optics evolution, and eightport homodyne detection. We
address the proof of hardness for the exact probability distribution of these
quantum circuits by exploiting mappings onto different architectures of
subuniversal quantum computers. We obtain both a worstcase and an
averagecase hardness result. Hardness of Boson Sampling with eightport
homodyne detection is obtained as the zero squeezing limit of our model. We
conclude with a discussion on the relevance and interest of the present model
in connection to experimental applications and classical simulations.

In this work, we demonstrate a new way to perform classical multiparty
computing amongst parties with limited computational resources. Our method
harnesses quantum resources to increase the computational power of the
individual parties. We show how a set of clients restricted to linear classical
processing are able to jointly compute a nonlinear multivariable function that
lies beyond their individual capabilities. The clients are only allowed to
perform classical XOR gates and singlequbit gates on quantum states. We also
examine the type of security that can be achieved in this limited setting.
Finally, we provide a proofofconcept implementation using photonic qubits,
that allows four clients to compute a specific example of a multiparty
function, the pairwise AND.

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.

Quantum computing has seen tremendous progress in the past years. However,
due to limitations in scalability of quantum technologies, it seems that we are
far from constructing universal quantum computers for everyday users. A more
feasible solution is the delegation of computation to powerful quantum servers
on the network. This solution was proposed in previous studies of Blind Quantum
Computation, with guarantees for both the secrecy of the input and of the
computation being performed. In this work, we further develop this idea of
computing over encrypted data, to propose a multiparty delegated quantum
computing protocol in the measurementbased quantum computing framework.

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.

The application and analysis of the CutandChoose technique in protocols
secure against quantum adversaries is not a straightforward transposition of
the classical case, among other reasons due to the difficulty to use rewinding
in the quantum realm. We introduce a Quantum Computation CutandChoose (QCCC)
technique which is a generalisation of the classical CutandChoose in order to
build quantum protocols secure against quantum covert adversaries. Such
adversaries can deviate arbitrarily provided that their deviation is not
detected. As an application of the QCCC we give a protocol for securely
performing twoparty quantum computation with classical input/output. As basis
we use secure delegated quantum computing (Broadbent et al 2009), and in
particular the garbled quantum computation of (Kashefi et al 2016) that is
secure against only a weak specious adversaries, defined in (Dupuis et al
2010). A unique property of these protocols is the separation between classical
and quantum communications and the asymmetry between client and server, which
enables us to sidestep the quantum rewinding issues. This opens the prospect of
using the QCCC to other quantum protocols with this separation. In our proof
of security we adapt and use (at different parts) two quantum rewinding
techniques, namely Watrous' oblivious qrewinding (Watrous 2009) and Unruh's
special qrewinding (Unruh 2012). Our protocol achieves the same functionality
as in previous works (e.g. Dupuis et al 2012), however using the QCCC
technique on the protocol from (Kashefi et al 2016) leads to the following key
improvements: (i) only oneway offline quantum communication is necessary ,
(ii) only one party (server) needs to have involved quantum technological
abilities, (iii) only minimal extra cryptographic primitives are required,
namely one oblivious transfer for each input bit and quantumsafe commitments.

The universal blind quantum computation protocol (UBQC) (Broadbent,
Fitzsimons, Kashefi 2009) enables an almost classical client to delegate a
quantum computation to an untrusted quantum server (in form of a garbled
quantum computation) while the security for the client is unconditional. In
this contribution we explore the possibility of extending the verifiable UBQC
(Fitzsimons, Kashefi 2012), to achieve further functionalities as was done for
classical garbled computation. First, exploring the asymmetric nature of UBQC
(client preparing only single qubits, while the server runs the entire quantum
computation), we present a "Yao" type protocol for secure two party quantum
computation. Similar to the classical setting (Yao 1986) our quantum Yao
protocol is secure against a specious (quantum honestbutcurious) garbler, but
in our case, against a (fully) malicious evaluator. Unlike the protocol in
(Dupuis, Nielsen, Salvail 2010), we do not require any onlinequantum
communication between the garbler and the evaluator and thus no extra
cryptographic primitive. This feature will allow us to construct a simple
universal onetime compiler for any quantum computation using onetime memory,
in a similar way with the classical work of (Goldwasser, Kalai, Rothblum 2008)
while more efficiently than the previous work of (Broadbent, Gutoski, Stebila
2013).

The question of whether a fully classical client can delegate a quantum
computation to an untrusted quantum server while fully maintaining privacy
(blindness) is one of the big open questions in quantum cryptography. Both yes
and no answers have important practical and theoretical consequences, and the
question seems genuinely hard. The stateoftheart approaches to securely
delegating quantum computation, without exception, rely on granting the client
modest quantum powers, or on additional, noncommunicating, quantum servers. In
this work, we consider the single server setting, and push the boundaries of
the minimal devices of the client, which still allow for blind quantum
computation. Our approach is based on the observation that, in many blind
quantum computing protocols, the "quantum" part of the protocol, from the
clients perspective, boils down to the establishing classicalquantum
correlations (independent from the computation) between the client and the
server, following which the steering of the computation itself requires only
classical communication. Here, we abstract this initial preparation phase,
specifically for the Universal Blind Quantum Computation protocol of Broadbent,
Fitzsimons and Kashefi. We identify sufficient criteria on the powers of the
client, which still allow for secure blind quantum computation. We work in a
universally composable framework, and provide a series of protocols, where each
step reduces the number of differing states the client needs to be able to
prepare. As the limit of such reductions, we show that the capacity to prepare
just two pure states, which have an arbitrarily high overlap (thus are
arbitrarily close to identical), suffices for efficient and secure blind
quantum computation.

Recent developments make the possibility of achieving scalable quantum
networks and quantum devices closer. From the computational point of view these
emerging technologies become relevant when they are no longer classically
simulatable. Hence a pressing challenge is the construction of practical
methods to verify the correctness of the outcome produced by universal or
nonuniversal quantum devices. A promising approach that has been extensively
explored is the scheme of verification via encryption through blind quantum
computing initiated by Fitzsimons and Kashefi. We present here a new
construction that simplifies the required resources for any such verifiable
blind quantum computating protocol. We obtain an overhead that is linear in the
size of the input, while the security parameter remains independent of the size
of the computation and can be made exponentially small. Furthermore our
construction is generic and could be applied to any nonuniversal scheme with a
given underlying graph.

Blind Quantum Computing (BQC) allows a client to have a server carry out a
quantum computation for them such that the client's input, output and
computation remain private. A desirable property for any BQC protocol is
verification, whereby the client can verify with high probability whether the
server has followed the instructions of the protocol, or if there has been some
deviation resulting in a corrupted output state. A verifiable BQC protocol can
be viewed as an interactive proof system leading to consequences for complexity
theory. The authors, together with Broadbent, previously proposed a universal
and unconditionally secure BQC scheme where the client only needs to be able to
prepare single qubits in separable states randomly chosen from a finite set and
send them to the server, who has the balance of the required quantum
computational resources. In this paper we extend that protocol with new
functionality allowing blind computational basis measurements, which we use to
construct a new verifiable BQC protocol based on a new class of resource
states. We rigorously prove that the probability of failing to detect an
incorrect output is exponentially small in a security parameter, while resource
overhead remains polynomial in this parameter. The new resource state allows
entangling gates to be performed between arbitrary pairs of logical qubits with
only constant overhead. This is a significant improvement on the original
scheme, which required that all computations to be performed must first be put
into a nearest neighbour form, incurring linear overhead in the number of
qubits. Such an improvement has important consequences for efficiency and
faulttolerance thresholds.

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.

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.

A longstanding question is whether it is possible to delegate computational
tasks securely. Recently, both a classical and a quantum solution to this
problem were found. Here, we study the interplay of classical and quantum
approaches and show how coherence can be used as a tool for secure delegated
classical computation. We show that a client with limited computational
capacity  restricted to an XOR gate  can perform universal classical
computation by manipulating information carriers that may occupy superpositions
of two states. Using single photonic qubits or coherent light, we
experimentally implement secure delegated classical computations between an
independent client and a server. The server has access to the light sources and
measurement devices, whereas the client may use only a restricted set of
passive optical devices to manipulate the light beams. Thus, our work
highlights how minimal quantum and classical resources can be combined and
exploited for classical computing.

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.

The question of which and how a particular class of entangled resource states
(known as graph states) can be used for measurement based quantum computation
(MBQC) recently gave rise to the notion of Flow and its generalisation gFlow.
That is a causal structure for measurements guaranteeing deterministic
computation. Furthermore, gFlow has proven itself to be a powerful tool in
studying the difference between the measurementbased and circuit models for
quantum computing, as well as analysing cryptographic protocols. On the other
hand, entanglement is known to play a crucial role in MBQC. In this paper we
first show how gFlow can be used to directly give a bound on the classical
simulation of an MBQC. Our method offers an interpretation of the gFlow as
showing how information flows through a computation, giving rise to an
information light cone. We then establish a link between entanglement and the
existence of gFlow for a graph state. We show that the gFlow can be used to
bound the entanglement width and what we call the \emph{structural
entanglement} of a graph state. In turn this gives another method relating the
gFlow to bounds on how efficiently a computation can be simulated classically.
These two methods of getting bounds on the difficulty of classical simulation
are different and complementary and several known results follow. In particular
known relations between the MBQC and the circuit model allow these results to
be translated across models.

The way entanglement influences the power of quantum and classical
multiprover interactive proof systems is a longstanding open question. We
show that the class of languages recognized by quantum multiprover interactive
proof systems, QMIP, is equal to MIP*, the class of languages recognized by
classical multiprover interactive proof systems where the provers share
entanglement. After the recent result by Jain, Ji, Upadhyay and Watrous showing
that QIP=IP, our work completes the picture from the verifier's perspective by
showing that also in the setting of multiple provers with shared entanglement,
a quantum verifier is no more powerful than a classical one: QMIP=MIP*. Our
techniques are based on the adaptation of universal blind quantum computation
(a protocol recently introduced by us) to the context of interactive proof
systems. We show that in the multiprover scenario, shared entanglement has a
positive effect in removing the need for a quantum verifier. As a consequence,
our results show that the entire power of quantum information in multiprover
interactive proof systems is captured by the shared entanglement and not by the
quantum communication.