
We report a proofofprinciple experimental demonstration of the quantum
speedup for learning agents utilizing a smallscale quantum information
processor based on radiofrequencydriven trapped ions. The decisionmaking
process of a quantum learning agent within the projective simulation paradigm
for machine learning is implemented in a system of two qubits. The latter are
realized using hyperfine states of two frequencyaddressed atomic ions exposed
to a static magnetic field gradient. We show that the deliberation time of this
quantum learning agent is quadratically improved with respect to comparable
classical learning agents. The performance of this quantumenhanced learning
agent highlights the potential of scalable quantum processors taking advantage
of machine learning.

Markov chain methods are remarkably successful in computational physics,
machine learning, and combinatorial optimization. The cost of such methods
often reduces to the mixing time, i.e., the time required to reach the steady
state of the Markov chain, which scales as $\delta^{1}$, the inverse of the
spectral gap. It has long been conjectured that quantum computers offer nearly
generic quadratic improvements for mixing problems. However, except in special
cases, quantum algorithms achieve a runtime of $\mathcal{O}(\sqrt{\delta^{1}}
\sqrt{N})$, which introduces a costly dependence on the Markov chain size $N,$
not present in the classical case. Here, we readdress the problem of mixing of
Markov chains when these form a slowly evolving sequence. This setting is akin
to the simulated annealing setting and is commonly encountered in physics,
material sciences and machine learning. We provide a quantum memoryefficient
algorithm with a runtime of $\mathcal{O}(\sqrt{\delta^{1}} \sqrt[4]{N})$,
neglecting logarithmic terms, which is an important improvement for large state
spaces. Moreover, our algorithms output quantum encodings of distributions,
which has advantages over classical outputs. Finally, we discuss the runtime
bounds of mixing algorithms and show that, under certain assumptions, our
algorithms are optimal.

The intersection between the fields of machine learning and quantum
information processing is proving to be a fruitful field for the discovery of
new quantum algorithms, which potentially offer an exponential speedup over
their classical counterparts. However, many such algorithms require the ability
to produce states proportional to vectors stored in quantum memory. Even given
access to quantum databases which store exponentially long vectors, the
construction of which is considered a oneoff overhead, it has been argued that
the cost of preparing such amplitudeencoded states may offset any exponential
quantum advantage. Here we argue that specifically in the context of machine
learning applications it suffices to prepare a state close to the ideal state
only in the $\infty$norm, and that this can be achieved with only a constant
number of memory queries.

It was recently proposed to leverage the representational power of artificial
neural networks, in particular Restricted Boltzmann Machines, in order to model
complex quantum states of manybody systems [Science, 355(6325), 2017]. States
represented in this way, called Neural Network States (NNSs), were shown to
display interesting properties like the ability to efficiently capture
longrange quantum correlations. However, identifying an optimal neural network
representation of a given state might be challenging, and so far this problem
has been addressed with stochastic optimization techniques. In this work we
explore a different direction. We study how the action of elementary quantum
operations modifies NNSs. We parametrize a family of many body quantum
operations that can be directly applied to states represented by Unrestricted
Boltzmann Machines, by just adding hidden nodes and updating the network
parameters. We show that this parametrization contains a set of universal
quantum gates, from which it follows that the state prepared by any quantum
circuit can be expressed as a Neural Network State with a number of hidden
nodes that grows linearly with the number of elementary operations in the
circuit. This is a powerful representation theorem (which was recently obtained
with different methods) but that is not directly useful, since there is no
general and efficient way to extract information from this unrestricted
description of quantum states. To circumvent this problem, we propose a
stepwise procedure based on the projection of Unrestricted quantum states to
Restricted quantum states. In turn, two approximate methods to perform this
projection are discussed. In this way, we show that it is in principle possible
to approximately optimize or evolve Neural Network States without relying on
stochastic methods such as Variational Monte Carlo, which are computationally
expensive.

How useful can machine learning be in a quantum laboratory? Here we raise the
question of the potential of intelligent machines in the context of scientific
research. A major motivation for the present work is the unknown reachability
of various entanglement classes in quantum experiments. We investigate this
question by using the projective simulation model, a physicsoriented approach
to artificial intelligence. In our approach, the projective simulation system
is challenged to design complex photonic quantum experiments that produce
highdimensional entangled multiphoton states, which are of high interest in
modern quantum experiments. The artificial intelligence system learns to create
a variety of entangled states, and improves the efficiency of their
realization. In the process, the system autonomously (re)discovers experimental
techniques which are only now becoming standard in modern quantum optical
experiments  a trait which was not explicitly demanded from the system but
emerged through the process of learning. Such features highlight the
possibility that machines could have a significantly more creative role in
future research.

Quantum information technologies, and intelligent learning systems, are both
emergent technologies that will likely have a transforming impact on our
society. The respective underlying fields of research  quantum information
(QI) versus machine learning (ML) and artificial intelligence (AI)  have
their own specific challenges, which have hitherto been investigated largely
independently. However, in a growing body of recent work, researchers have been
probing the question to what extent these fields can learn and benefit from
each other. QML explores the interaction between quantum computing and ML,
investigating how results and techniques from one field can be used to solve
the problems of the other. Recently, we have witnessed breakthroughs in both
directions of influence. For instance, quantum computing is finding a vital
application in providing speedups in ML, critical in our "big data" world.
Conversely, ML already permeates cuttingedge technologies, and may become
instrumental in advanced quantum technologies. Aside from quantum speedup in
data analysis, or classical ML optimization used in quantum experiments,
quantum enhancements have also been demonstrated for interactive learning,
highlighting the potential of quantumenhanced learning agents. Finally, works
exploring the use of AI for the very design of quantum experiments, and for
performing parts of genuine research autonomously, have reported their first
successes. Beyond the topics of mutual enhancement, researchers have also
broached the fundamental issue of quantum generalizations of ML/AI concepts.
This deals with questions of the very meaning of learning and intelligence in a
world that is described by quantum mechanics. In this review, we describe the
main ideas, recent developments, and progress in a broad spectrum of research
investigating machine learning and artificial intelligence in the quantum
domain.

Quantum metrology offers a quadratic advantage over classical approaches to
parameter estimation problems by utilizing entanglement and nonclassicality.
However, the hurdle of actually implementing the necessary quantum probe states
and measurements, which vary drastically for different metrological scenarios,
is usually not taken into account. We show that for a wide range of tasks in
metrology, 2D cluster states (a particular family of states useful for
measurementbased quantum computation) can serve as flexible resources that
allow one to efficiently prepare any required state for sensing, and perform
appropriate (entangled) measurements using only single qubit operations.
Crucially, the overhead in the number of qubits is less than quadratic, thus
preserving the quantum scaling advantage. This is ensured by using a
compression to a logarithmically sized space that contains all relevant
information for sensing. We specifically demonstrate how our method can be used
to obtain optimal scaling for phase and frequency estimation in local
estimation problems, as well as for the Bayesian equivalents with Gaussian
priors of varying widths. Furthermore, we show that in the paradigmatic case of
local phase estimation 1D cluster states are sufficient for optimal state
preparation and measurement.

We treat the problem of autonomous acquisition of manipulation skills where
problemsolving strategies are initially available only for a narrow range of
situations. We propose to extend the range of solvable situations by autonomous
playing with the object. By applying previouslytrained skills and behaviours,
the robot learns how to prepare situations for which a successful strategy is
already known. The information gathered during autonomous play is additionally
used to learn an environment model. This model is exploited for active learning
and the creative generation of novel preparatory behaviours. We apply our
approach on a wide range of different manipulation tasks, e.g. book grasping,
grasping of objects of different sizes by selecting different grasping
strategies, placement on shelves, and tower disassembly. We show that the
creative behaviour generation mechanism enables the robot to solve
previouslyunsolvable tasks, e.g. tower disassembly. We use success statistics
gained during realworld experiments to simulate the convergence behaviour of
our system. Experiments show that active improves the learning speed by around
9 percent in the book grasping scenario.

The emerging field of quantum machine learning has the potential to
substantially aid in the problems and scope of artificial intelligence. This is
only enhanced by recent successes in the field of classical machine learning.
In this work we propose an approach for the systematic treatment of machine
learning, from the perspective of quantum information. Our approach is general
and covers all three main branches of machine learning: supervised,
unsupervised and reinforcement learning. While quantum improvements in
supervised and unsupervised learning have been reported, reinforcement learning
has received much less attention. Within our approach, we tackle the problem of
quantum enhancements in reinforcement learning as well, and propose a
systematic scheme for providing improvements. As an example, we show that
quadratic improvements in learning efficiency, and exponential improvements in
performance over limited time periods, can be obtained for a broad class of
learning problems.

We present a security proof for establishing private entanglement by means of
recurrencetype entanglement distillation protocols. We consider protocols
where the apparatus is imperfect, and show that nonetheless a secure quantum
channel can be established, and used to e.g. perform distributed quantum
computation in a secure manner. We assume an ultimately powerful eavesdropper
distributing all pairs used in a subsequent distillation process by Alice and
Bob, and show that even if the apparatus leaks the information about all noise
processes that are realized during execution of the protocol to the
eavesdropper  which arguably is the most general setting besides device
independence  private entanglement is still achievable. We provide a proof of
security under general quantum attacks without assuming asymptotic scenarios,
by reducing such a general situation to an i.i.d. setting. Our approach relies
on nontrivial properties of distillation protocols which are used in
conjunction with deFinetti and postselectiontype techniques. As a side
result, we also provide entanglement distillation protocols for noni.i.d.
input states.

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.

Learning models of artificial intelligence can nowadays perform very well on
a large variety of tasks. However, in practice different task environments are
best handled by different learning models, rather than a single, universal,
approach. Most nontrivial models thus require the adjustment of several to
many learning parameters, which is often done on a casebycase basis by an
external party. Metalearning refers to the ability of an agent to autonomously
and dynamically adjust its own learning parameters, or metaparameters. In this
work we show how projective simulation, a recently developed model of
artificial intelligence, can naturally be extended to account for metalearning
in reinforcement learning settings. The projective simulation approach is based
on a random walk process over a network of clips. The suggested metalearning
scheme builds upon the same design and employs clip networks to monitor the
agent's performance and to adjust its metaparameters "on the fly". We
distinguish between "reflexive adaptation" and "adaptation through learning",
and show the utility of both approaches. In addition, a tradeoff between
flexibility and learningtime is addressed. The extended model is examined on
three different kinds of reinforcement learning tasks, in which the agent has
different optimal values of the metaparameters, and is shown to perform well,
reaching nearoptimal to optimal success rates in all of them, without ever
needing to manually adjust any metaparameter.

We present an experimental realization of a quantum digital signature
protocol which, together with a standard quantum key distribution link,
increases transmission distance to kilometre ranges, three orders of magnitude
larger than in previous realizations. The bitrate is also significantly
increased compared with previous quantum signature demonstrations. This work
illustrates that quantum digital signatures can be realized with optical
components similar to those used for quantum key distribution, and could be
implemented in existing optical fiber networks.

In this paper we provide a broad framework for describing learning agents in
general quantum environments. We analyze the types of classically specified
environments which allow for quantum enhancements in learning, by contrasting
environments to quantum oracles. We show that whether or not quantum
improvements are at all possible depends on the internal structure of the
quantum environment. If the environments are constructed and the internal
structure is appropriately chosen, or if the agent has limited capacities to
influence the internal states of the environment, we show that improvements in
learning times are possible in a broad range of scenarios. Such scenarios we
call luckfavoring settings. The case of constructed environments is
particularly relevant for the class of modelbased learning agents, where our
results imply a neargeneric improvement.

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.

The ability to generalize is an important feature of any intelligent agent.
Not only because it may allow the agent to cope with large amounts of data, but
also because in some environments, an agent with no generalization ability is
simply doomed to fail. In this work we outline several criteria for
generalization, and present a dynamic and autonomous machinery that enables
projective simulation agents to meaningfully generalize. Projective simulation,
a novel, physical, approach to artificial intelligence, was recently shown to
perform well, in comparison with standard models, on both simple reinforcement
learning problems, as well as on more complicated canonical tasks, such as the
"grid world" and the "mountain car problem". Both the basic projective
simulation model and the presented generalization machinery are based on very
simple principles. This simplicity allows us to provide a full analytical
analysis of the agent's performance and to illustrate the benefit the agent
gains by generalizing. Specifically, we show how such an ability allows the
agent to learn in rather extreme environments, in which learning is otherwise
impossible.

The preparation of the stationary distribution of irreducible,
timereversible Markov chains is a fundamental building block in many heuristic
approaches to algorithmically hard problems. It has been conjectured that
quantum analogs of classical mixing processes may offer a generic quadratic
speedup in realizing such stationary distributions. Such a speedup would also
imply a speedup of a broad family of heuristic algorithms.
However, a true quadratic speed up has thus far only been demonstrated for
special classes of Markov chains. These results often presuppose a regular
structure of the underlying graph of the Markov chain, and also a regularity in
the transition probabilities.
In this work, we demonstrate a true quadratic speedup for a class of Markov
chains where the restriction is only on the form of the stationary
distribution, rather than directly on the Markov chain structure itself. In
particular, we show efficient mixing can be achieved when it is beforehand
known that the distribution is monotonically decreasing relative to a known
order on the state space. Following this, we show that our approach extends to
a wider class of distributions, where only a fraction of the shape of the
distribution is known to be monotonic. Our approach is built on the
Szegedytype quantization of transition operators.

A scheme that successfully employs quantum mechanics in the design of
autonomous learning agents has recently been reported in the context of the
projective simulation (PS) model for artificial intelligence. In that approach,
the key feature of a PS agent, a specific type of memory which is explored via
random walks, was shown to be amenable to quantization. In particular,
classical random walks were substituted by Szegedytype quantum walks, allowing
for a speedup. In this work we propose how such classical and quantum agents
can be implemented in systems of trapped ions. We employ a generic construction
by which the classical agents are `upgraded' to their quantum counterparts by
nested coherent controlization, and we outline how this construction can be
realized in ion traps. Our results provide a flexible modular architecture for
the design of PS agents. Furthermore, we present numerical simulations of
simple PS agents which analyze the robustness of our proposal under certain
noise models.

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.

Digital signatures guarantee the authenticity and transferability of
messages, and are widely used in modern communication. The security of
currently used classical digital signature schemes, however, relies on
computational assumptions. In contrast, quantum digital signature (QDS) schemes
offer informationtheoretic security guaranteed by the laws of quantum
mechanics. We present two QDS protocols which have the same experimental
requirements as quantum key distribution, which is already commercially
available. We also present the first security proof for any QDS scheme against
coherent forging attacks.

Delegating difficult computations to remote large computation facilities,
with appropriate security guarantees, is a possible solution for the
evergrowing needs of personal computing power. For delegated computation
protocols to be usable in a larger contextor simply to securely run two
protocols in parallelthe security definitions need to be composable. Here,
we define composable security for delegated quantum computation. We distinguish
between protocols which provide only blindnessthe computation is hidden from
the serverand those that are also verifiablethe client can check that it
has received the correct result. We show that the composable security
definition capturing both these notions can be reduced to a combination of
several distinct "tracedistancetype" criteriawhich are, individually,
noncomposable security definitions.
Additionally, we study the security of some known delegated quantum
computation protocols, including Broadbent, Fitzsimons and Kashefi's Universal
Blind Quantum Computation protocol. Even though these protocols were originally
proposed with insufficient security criteria, they turn out to still be secure
given the stronger composable definitions.

Can quantum mechanics help us in building intelligent robots and agents? One
of the defining characteristics of intelligent behavior is the capacity to
learn from experience. However, a major bottleneck for agents to learn in any
reallife situation is the size and complexity of the corresponding task
environment. Owing to, e.g., a large space of possible strategies, learning is
typically slow. Even for a moderate task environment, it may simply take too
long to rationally respond to a given situation. If the environment is
impatient, allowing only a certain time for a response, an agent may then be
unable to cope with the situation and to learn at all. Here we show that
quantum physics can help and provide a significant speedup for active learning
as a genuine problem of artificial intelligence. We introduce a large class of
quantum learning agents for which we show a quadratic boost in their active
learning efficiency over their classical analogues. This result will be
particularly relevant for applications involving complex task environments.

In this paper we investigate the entanglement properties of the class of
$\pi$locally maximally entanglable ($\pi$LME) states, which are also known as
the "real equally weighted states" or the "hypergraph states". The $\pi$LME
states comprise wellstudied classes of quantum states (e.g. graph states) and
exhibit a large degree of symmetry. Motivated by the structure of LME states,
we show that the capacity to (efficiently) determine if a $\pi$LME state is
entangled would imply an efficient solution to the boolean satisfiability (SAT)
problem. More concretely, we show that this particular problem of entanglement
detection, phrased as a decision problem, is $\mathsf{NP}$complete. The
restricted setting we consider yields a technically uninvolved proof, and
illustrates that entanglement detection, even when quantum states under
consideration are highly restricted, still remains difficult.

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.

Digital signatures are widely used to provide security for electronic
communications, for example in financial transactions and electronic mail.
Currently used classical digital signature schemes, however, only offer
security relying on unproven computational assumptions. In contrast, quantum
digital signatures (QDS) offer informationtheoretic security based on laws of
quantum mechanics (e.g. Gottesman and Chuang 2001). Here, security against
forging relies on the impossibility of perfectly distinguishing between
nonorthogonal quantum states. A serious drawback of previous QDS schemes is
however that they require longterm quantum memory, making them unfeasible in
practice. We present the first realisation of a scheme (Dunjko et al 2013) that
does not need quantum memory, and which also uses only standard linear optical
components and photodetectors. To achieve this, the recipients measure the
distributed quantum signature states using a new type of quantum measurement,
quantum state elimination (e.g. Barnett 2009, Bandyopadhyay et al 2013). This
significantly advances QDS as a quantum technology with potential for real
applications.