# Provable Advantage in Quantum PAC Learning

Wilfred Salmon  DAMTP, Centre for Mathematical Sciences, University of
Cambridge<EMAIL_ADDRESS>Sergii Strelchuk  DAMTP, Centre for Mathematical
Sciences, University of Cambridge  Tom Gur  Department of Computer Science and
Technology, University of Cambridge

###### Abstract

We revisit the problem of characterising the complexity of Quantum PAC
learning, as introduced by Bshouty and Jackson [SIAM J. Comput. 1998, 28,
1136–1153]. Several quantum advantages have been demonstrated in this setting,
however, none are generic: they apply to particular concept classes and
typically only work when the distribution that generates the data is known. In
the general case, it was recently shown by Arunachalam and de Wolf [JMLR, 19
(2018) 1-36] that quantum PAC learners can only achieve constant factor
advantages over classical PAC learners.

We show that with a natural extension of the definition of quantum PAC
learning used by Arunachalam and de Wolf, we can achieve a generic advantage
in quantum learning. To be precise, for any concept class $\mathcal{C}$ of VC
dimension $d$, we show there is an $(\epsilon,\delta)$-quantum PAC learner
with sample complexity

$O\left(\frac{1}{\sqrt{\epsilon}}\left[d+\log(\frac{1}{\delta})\right]\log^{9}(1/\epsilon)\right).$

Up to polylogarithmic factors, this is a square root improvement over the
classical learning sample complexity. We show the tightness of our result by
proving an $\Omega(d/\sqrt{\epsilon})$ lower bound that matches our upper
bound up to polylogarithmic factors.

##  1 Introduction

Probably approximately correct (PAC) learning [1] is a fundamental model of
machine learning. One is given a set of functions
$\mathcal{C}\subseteq\\{0,1\\}^{\mathcal{X}}=\\{f:\mathcal{X}\to\\{0,1\\}\\}$,
called a concept class, that encodes the structure of a learning problem (for
example, functions that only depend on the hamming weight of their input).
Given labelled examples from an unknown concept $c\in\mathcal{C}$, we are
tasked with learning an approximation to $c$.

We model the data that the learning algorithm receives by an unknown
probability distribution $\mathcal{D}$ on $\mathcal{X}$, and say that a
hypothesis $h:\mathcal{X}\to\\{0,1\\}$ is $\epsilon$-approximately correct if
the probability that it differs from $c$ is at most $\epsilon$. To be precise,
A hypothesis $h\in\\{0,1\\}^{\mathcal{X}}$ is said to be
$\epsilon$-approximately correct if

$\mathbb{P}_{X\sim\mathcal{D}}\left[h(X)\neq c(X)\right]\leq\epsilon.$ (1)

A learning algorithm $\mathcal{A}$ draws independent samples $(X,c(X))$, where
$X$ is distributed according to $\mathcal{D}$, and then outputs a hypothesis
$h$. The algorithm $\mathcal{A}$ is an $(\epsilon,\delta)$-learner if, with
probability at least $1-\delta$ over the random samples, it outputs a
$\epsilon$-approximately correct hypothesis.

The amount of “structure” possessed by $\mathcal{C}$ is characterised by its
Valiant-Chapernikis (VC) dimension [2], denoted $d$. For a subset $Y\subseteq
X$, we define $\mathcal{C}|_{Y}:=\\{c|_{Y}:c\in\mathcal{C}\\}$ as the
restriction of the concept class to $Y$. We say that $\mathcal{C}$ shatters
$Y$ if $\mathcal{C}|_{Y}=\\{0,1\\}^{Y}$, i.e., if all possible labellings of
$Y$ appear in concepts in $\mathcal{C}$. Then, $d$ is the maximum size of a
shattered set, that is

$d=\max\\{|Y|:Y\text{ is shattered by }\mathcal{C}\\}.$ (2)

Over a period of 27 years [3, 4], the exact asymptotic scaling of the minimum
number of samples required by an ($\epsilon,\delta$)-learner was found to be

$\Theta\left[\frac{1}{\epsilon}\left(d+\log(\frac{1}{\delta})\right)\right],$
(3)

thereby characterising the complexity of classical PAC learning.

In 1995, Bshouty and Jackson [5] considered a generalisation of PAC learning
to the quantum setting [6]. Here, instead of receiving independent identically
distributed samples $(X,C(X))$, one receives independent copies of a quantum
state

$\ket{\psi_{c}}=\sum_{x\in\mathcal{X}}\sqrt{\mathcal{D}(x)}\ket{x\;c(x)},$ (4)

known as a _quantum sample_. In particular, measuring such a state in the
computational basis gives a sample $(X,C(X))$. In turn, instead of counting
the number of samples, the quantum sample complexity is the number of copies
of the state given to the quantum learning algorithm.

The Quantum PAC model is instrumental in understanding the limits of other
quantum cryptographic and computational tasks. For instance, in [7], a
connection between differential privacy and PAC learnability of quantum states
was established, and recently [8] used the PAC framework to investigate the
complexity of learning parameterised quantum circuits, which are ubiquitous in
variational quantum algorithms where they are used for quantum state
preparation.

In the special case of quantum PAC learning under the uniform distribution, it
has been shown that one can obtain quantum sample complexity advantages in
specific learning tasks, such as learning Fourier basis functions [9], DNF
formulae [5], and $k$-juntas [10]. These advantages rely on Fourier sampling,
in which one applies the Hadamard transform on every qubit followed by a
measurement of the resulting state in the computational basis. One observes a
bit string $s$ with probability given by its squared Fourier coefficient
$|\hat{c}_{s}|^{2}$ and can thus directly infer properties of the Fourier
spectrum of the unknown function. However, such advantages rely on the
distributions $\mathcal{D}$ being (approximately) uniform.

The general quantum PAC learning model, with an arbitrary and unknown
distribution $\mathcal{D}$, was studied by Arunachalam and de Wolf [6, 11],
who showed that the quantum sample complexity has exactly the same asymptotic
scaling as the classical learning complexity, ruling out everything but
constant factor prospective advantages.

Thus, most recent literature has focused identifying advantages only in
suitably restricted versions of the quantum PAC model [10, 12]. Nevertheless,
such models have demonstrated remarkable utility when assessing the complexity
of learning quantum states, channels [13, 14, 15], and measurements [16, 17]
in quantum theory with lower bounds on query complexity established in [18].

Here, we consider a natural and less restrictive version of the quantum PAC
learning model. Instead of access to copies of the state $\ket{\psi_{c}}$, we
assume that we have access to the quantum circuit that generates it, similarly
in spirit to [19, 20]. That is, we assume one has access to a quantum circuit
$Q_{c}$ that generates a quantum sample $\ket{\psi_{c}}$ (for example, as a
decomposition into one and two-qubit gates) and thus can implement $Q_{c}$ and
$Q_{c}^{\dagger}$. Given this natural adjustment to the input access of
quantum PAC learning algorithms, we can revisit the question of whether strong
generic (beyond constant-factor) quantum advantages are possible for quantum
PAC learning.

###  1.1 Our results

In this paper, we show that there is a square root advantage (up to
polylogarithmic factors) for quantum PAC learning over classical PAC learning
in the full, general model. Our main result (see Section 5) is summarised by
the following theorem.

###### Theorem 1.1

Let $\mathcal{C}$ be a concept class with VC dimension $d$. Then, for every
$\epsilon,\delta>0$, there exists a $(\epsilon,\delta)$-quantum PAC learner
for $\mathcal{C}$ that makes at most

$O\left(\frac{1}{\sqrt{\epsilon}}\left[d+\log(\frac{1}{\delta})\right]\log^{9}(1/\epsilon)\right),$
(5)

calls to an oracle that generates a quantum sample ($Q_{c}$) or its inverse
($Q_{c}^{\dagger})$.

In comparison, the optimal classical PAC learning complexity (and quantum PAC
complexity given access to copies of $\ket{\psi_{c}}$ [11]) is given in
equation (8). Thus, our upper bound is a square root improvement (up to
polylogarithmic factors) over the best possible classical learning algorithm.
In fact, we show that this upper bound is essentially tight, up to
polylogarithmic factors, as captured by the following theorem.

###### Theorem 1.2

Let $\mathcal{C}$ be a concept class with VC dimension $d$. Then, for a
sufficiently small constant $\delta>0$ and for all $\epsilon>0$, any quantum
$(\epsilon,\delta)$-learner for $\mathcal{C}$ makes at least

$\Omega\left(\frac{d}{\sqrt{\epsilon}}\right)$ (6)

calls to an oracle that generates a quantum sample ($Q_{c}$) or its inverse
($Q_{c}^{\dagger})$.

###  1.2 Technical overview

Our starting point is the observation that the lower bound of Arunachalam and
de Wolf [11] implicitly rests on the assumption that a quantum learning
algorithm must not depend on the underlying concept, and it can thus be
represented by a (concept independent) POVM. They then reduce the problem of
PAC learning to that of state discrimination (where the POVM is state-
independent). However, if we allow for the common assumption that the
algorithm has access to an oracle $Q_{c}$ generating $\ket{\psi_{c}}$, the
proof of the lower bound no longer holds111Since the state $\ket{\psi_{c}}$
must be produced by some process, this assumption is quite minimal.. If the
POVM describing the algorithm calls the oracle, it, by definition, depends on
the underlying concept. Thus, one cannot reduce the problem to that of state
discrimination, where it is assumed that the POVM is independent of the input
state.

If one implements $Q_{c}$ on some physical device (for example, as a series of
one and two-qubit gates), it is natural to assume that one can also implement
the inverse process $Q_{c}^{\dagger}$ (for example, by reversing the order of
the gates and replacing each by its inverse). Thus, we argue that if one has
access to the state $\ket{\psi_{c}}$ it is natural to also consider the
situation in which one also has access to $Q_{c}$ and $Q_{c}^{\dagger}$.
Indeed, this setting has recently received significant attention [20, 21].

Given access to $Q_{c}$ and $Q_{c}^{\dagger}$, it is tempting to attempt
techniques such as Grover search and amplitude amplification, which often
achieve quadratic quantum advantages. Consider, for example, the simplest
possible concept class $\mathcal{C}=\\{0,1\\}^{\mathcal{X}}$: the set of all
possible classifiers. It is known that a classical worst-case distribution for
this class is a “perturbed” delta-function [11], where there is a marked
element $x_{0}\in\mathcal{X}$ with probability
$\mathcal{D}(x_{0})=1-4\epsilon$, and all other elements have equal
probability. Roughly speaking, to $(\epsilon,\delta)$-learn $\mathcal{C}$, one
must learn a fraction of $3/4$ of the values of $c$. However, it takes on
average $O(1/\epsilon)$ samples to return an $x$ that isn’t $x_{0}$ and thus
the classical learning query complexity is $\Omega(|\mathcal{X}|/\epsilon)$.
In this case, one could repeatedly run Grover’s search, marking any state
$\ket{x\;b}$ as good if we have not yet learnt $c(x)$. With Grover search, it
only takes $O(1/\sqrt{\epsilon})$ oracle calls to return an $x$ that is not
$x_{0}$ and thus we see the quantum query complexity is
$O(|\mathcal{X}|/\sqrt{\epsilon})$, the desired quadratic improvement.
Therefore, we already outperform the lower bound of Arunachalam and de Wolf
[11].

Note that the method above does not immediately generalise to other concept
classes. For example, consider the concept class

$\mathcal{C}=\\{c\in\\{0,1\\}^{\mathcal{X}}:|c^{-1}(\\{1\\})|=d\\}\;,$

the class of classifiers with exactly $d$ inputs that map to 1, and take
$\mathcal{D}$ to be the uniform distribution on $\mathcal{X}$. If
$|\mathcal{X}|$ is very large, then most unseen $x$’s will have $c(x)=0$ and
thus the above approach is uninformative. Instead, instead, one should mark a
state $\ket{x\;b}$ as good if $b=1$. In this way, one can search for the
inputs $x\in\mathcal{X}$ that have $c(x)=1$ and hence deduce $c$. This will
also lead to a quadratic quantum advantage.

However, for general concept classes, it is less clear what to search for. One
could run the Halving algorithm, where we mark a state $\ket{x\;y}$ as good if
the majority of the concepts $h\in\mathcal{C}$ that are consistent with the
data so far have $h(x)=1-y$. In this case, every time the Grover algorithm
succeeds, one would eliminate at least half of the concepts in $\mathcal{C}$.
However, this leads to a $\log|\mathcal{C}|$ factor in the learning
complexity, which can be as large as $d\log|\mathcal{X}|$, i.e., arbitrarily
larger than $d$ (the VC dimension of $\mathcal{C}$). Thus, even under the
simplifying assumption of the uniform distribution, it is unclear how to
attempt to use Grover’s search to obtain a quantum advantage.

Nevertheless, we show that one can achieve a square root quantum advantage in
the general case. As a first step, we use the technique of equivalence queries
[22] (also known as random counterexamples). An equivalence query is an
alternative learning oracle to the traditional PAC oracle, in which one
submits a candidate hypothesis $h\in\\{0,1\\}^{\mathcal{X}}$. If $h=c$, then
the oracle outputs $YES$, otherwise it produces a labelled counterexample
$(X,c(X))$ where

  1. (i)

$h(X)\neq c(X)$.

  2. (ii)

$X$ is distributed according to
$\mathbb{P}(y)=\mathcal{D}(y)/\mathcal{D}(\\{x:c(x)\neq h(x)\\})$.

Observe that by marking a state $\ket{x\;y}$ as good if $h(x)=1-y$, we can see
how to implement an equivalence query using Grover search, and thus one can
hope to use this tool from classical learning theory to achieve an advantage.
However, when one removes the simplifying assumption of a known distribution,
further problems arise.

For a generic distribution, we do not know $\mathcal{D}(x)$ for any
$x\in\mathcal{X}$ and therefore one cannot run exact Grover search. Instead,
we consider a well-studied technique [23], in which one makes a random number
of $M$ queries to the Grover oracle, where $M$ is uniformly distributed
between 0 and a chosen threshold $T_{G}$. This search succeeds with non-
negligible probability if the amplitude of the projection of the initial state
onto the subspace spanned by the “good” states (the “good” subspace) is
$\Omega(1/T_{G})$. For an equivalence query $h$, this amplitude is
$\sqrt{\mathcal{D}(\\{x:c(x)\neq h(x)\\})}$, which could be arbitrarily small
(as $\mathcal{D}$ is arbitrary). Hence, it may take an arbitrarily large
(expected) number of iterations of Grover’s search (and hence oracle calls) to
run a classical equivalence query learning algorithm.

To solve this issue, we show how to use equivalence queries that succeed with
a constant probability, called imperfect equivalence queries, to PAC learn a
concept. We can then run these imperfect equivalence queries using Grover
search. We use a classical (ideal) equivalence query algorithm, replacing
equivalence queries with repeated imperfect equivalence queries, but with a
maximum imperfect equivalence query budget $R$. Suppose that the algorithm
requires equivalence queries to hypotheses $h_{1},\dots h_{k}$. If all of the
successfully run an equivalence query for every hypothesis, then the classical
algorithm succeeds, and we use its output. Otherwise, we hit the imperfect
equivalence query budget $R$ and must terminate the classical algorithm early.
By choosing $R$ sufficiently large, we can be sure that if we hit the budget,
most of the imperfect equivalence queries were spent on hypotheses $h_{i}$
that are “close” to $c$ (and hence have a low chance of the Grover search
succeeding). Thus if we take the “average” of the hypotheses $h_{i}$ weighted
by the number of imperfect equivalence queries spent on each hypothesis, we
also output a classifier close to $c$.

To conclude the section, we sketch a proof of our lower bound. We consider an
arbitrary concept class $\mathcal{C}$ of VC dimension $d$. We note that there
is a shattered set $Y\subseteq\mathcal{X}$ of size $d$, and take $\mathcal{D}$
to be a “perturbed” delta-function distribution on $Y$. We can thus think of
concepts $c$ in $\mathcal{C}$ as bit strings of length $d$, where the bit
string describes $c$’s action on $Y$. Since $Y$ is shattered by $\mathcal{C}$,
all possible bit strings will appear. Any candidate PAC algorithm must be able
to recover most of the bit string with high probability. We reduce to a known
problem by introducing a weak phase-kickback oracle for the bit string, which
we use to implement the PAC oracle. We can then use a standard lower bound
[20] on recovering a bit string with high probability using a weak phase
kickback oracle.

###  1.3 Open problems

This work leaves several interesting avenues for further research. Firstly,
one could attempt to tighten the upper bound (5) to remove polylogarithmic
factors and prove a tight matching lower bound. The removal of a
$\log(1/\epsilon)$ factor in the query complexity for classical PAC learning
took 27 years [3, 4]; we hope that the quantum case will be simpler. Moreover,
in order to achieve $1/\sqrt{\epsilon}$ scaling with our method, one would
require the optimal classical equivalence query learning complexity to have no
$\epsilon$ dependence and thus, a different approach is likely to be required.

It is interesting to consider the power of quantum learning algorithms with
access to the oracle $Q_{c}$, but not its inverse $Q_{c}^{\dagger}$. The
inverse oracle seems necessary for Grover’s search, and thus it is unclear if
a quantum advantage is possible. The lack of such an advantage would have
interesting implications for understanding what makes quantum computing more
powerful than classical computation.

Finally, one could consider the implications of this work to generic
advantages in more practical models of quantum machine learning, such as
quantum neural networks.

###  1.4 Organisation

We first cover all required technical preliminaries in Section 2. In Section
3, we cover our Grover subroutine that leads to the quadratic advantage.
Equivalence queries and how to use imperfect equivalence queries in a
classical learning algorithm are both described in Section 4. Using the
results of these two sections, we derive the upper bound (5) in Section 5; we
prove an almost matching lower bound on our quantum model in Section 6, using
a reduction to a phase oracle problem. Finally, we consider the application of
our algorithm to learning $k-$juntas in Section 7.

##  2 Preliminaries

We will only consider functions defined on finite sets. We first introduce the
standard, classical model of PAC learning [1]. For a finite set $\mathcal{X}$,
let $\\{0,1\\}^{\mathcal{X}}=\\{f:\mathcal{X}\to\\{0,1\\}\\}$, an element
$f\in\\{0,1\\}^{\mathcal{X}}$ is called a classifier. We wish to approximately
learn an unknown classifier $c$ from a known subset of classifiers
$\mathcal{C}\subseteq\\{0,1\\}^{\mathcal{X}}$, where $\mathcal{C}$ is called a
concept class.

There is an unknown distribution $\mathcal{D}$ on $\mathcal{X}$, where
$\mathcal{D}(x)$ denotes the probability of drawing $x$ from $\mathcal{X}$.
The distance between two classifiers is defined as the probability they
disagree: $d(h_{1},h_{2}):=\mathbb{P}_{X\sim\mathcal{D}}\left[h_{1}(X)\neq
h_{2}(X)\right]$. For a fixed tolerance $\epsilon>0$ we say a classifier
$h\in\\{0,1\\}^{\mathcal{X}}$ is $\epsilon$-approximately correct if
$d(h,c)\leq\epsilon$.

A learning algorithm $\mathcal{A}$ has access to some oracle that gives
information about $c$. Traditionally, one assumes that the oracle generates a
labelled example $(X,c(X))$ at random, where $X$ is distributed according to
$\mathcal{D}$. We will consider an additional type of oracle in section 4. The
sample complexity of $\mathcal{A}$ is the number of labelled examples it
receives.

For a fixed error probability $\delta$, we say that an algorithm $\mathcal{A}$
is an $(\epsilon,\delta)$ learner if, with probability at least $1-\delta$
(over the randomness of the algorithm), the algorithm outputs an
$\epsilon$-approximately correct hypothesis, for every possible $c$ and
$\mathcal{D}$.

For a fixed concept class $\mathcal{C}$ and $\epsilon,\delta>0$, one wishes to
find an $(\epsilon,\delta)$-learner with minimum sample complexity. The
optimal sample complexity will depend on $\epsilon,\delta$ and some measure of
complexity of the class $\mathcal{C}$, which we now define. For a subset
$Y\subseteq\mathcal{X}$, we define
$\mathcal{C}|_{Y}:=\\{c|_{Y}:c\in\mathcal{C}\\}$ as the restriction of the
concept class to $Y$. We say that $\mathcal{C}$ shatters $Y$ if
$\mathcal{C}|_{Y}=\\{0,1\\}^{Y}$, i.e., if all possible labellings of $Y$
appear in concepts in $\mathcal{C}$. The Valiant-Chapernikis (VC) dimension
[2] of $\mathcal{C}$, denoted $d$, is the maximum size of a shattered set,
that is

$d=\max\\{|Y|:Y\text{ is shattered by }\mathcal{C}\\}.$ (7)

In [3, 4], it was shown that the optimal sample complexity using labelled
examples, denoted $T_{C}(\epsilon,\delta,d)$ scales as

$T_{C}=\Theta\left[\frac{1}{\epsilon}\left(d+\log(\frac{1}{\delta})\right)\right].$
(8)

In the quantum PAC setting [5], one assumes that the data is stored
coherently, i.e., one considers the state

$\ket{\psi_{c}}:=\sum_{x\in\mathcal{X}}\sqrt{\mathcal{D}(x)}\ket{x\;c(x)},$
(9)

chosen so that measuring $\ket{\psi_{c}}$ in the computational basis gives a
random labelled example. Instead of the classical sample complexity, one
considers the minimum number of copies $T_{S}(\epsilon,\delta,d)$ of
$\ket{\psi_{c}}$ required to PAC learn $\mathcal{C}$. Since one can always
measure the state in place of a call to a classical oracle, $T_{S}$ is, at
worst, the optimal sample complexity of a classical algorithm. In fact,
Arunachalam and de Wolf [11] showed that there is no (asymptotic) quantum
advantage from using states instead of oracle calls - the optimal $T_{S}$
grows exactly as in equation (8).

We assume a stronger model, in which one has access to an oracle $Q_{c}$
(which depends on the underlying concept), defined by its action on a fixed
known input state $\ket{\text{IN}}$ (independent of the underlying concept):

$Q_{c}\ket{\text{IN}}=\ket{\psi_{c}}=\sum_{x\in\mathcal{X}}\sqrt{\mathcal{D}(x)}\ket{x\;c(x)}.$
(10)

This is similar in spirit to the recent work [20], which deals with state
tomography with a state preparation unitary. We also assume that the algorithm
has access to the inverse of the oracle, $Q_{c}^{\dagger}$. This is relevant
if, for example, $Q_{c}$ is given as a quantum circuit of one or two-qubit
gates; in this case, $Q_{c}^{\dagger}$ may be constructed by reversing the
order of the gates and replacing each with its inverse. We define the learning
complexity of any algorithm as the total number of queries to $Q_{c}$ or
$Q_{c}^{\dagger}$. The minimum learning complexity of any
($\epsilon,\delta$)-learner is denoted $T_{O}(\epsilon,\delta,\mathcal{C})$.

The lower bound of [11] does not apply to a model with access to $Q_{c}$, as
it assumes the quantum algorithm is described by a POVM that is independent of
the underlying concept $c$. However, $Q_{c}$ explicitly depends on $c$ and
thus, any algorithm (or POVM) that calls $Q_{c}$ will violate the assumptions
in [11]. Hence, one can hope for quantum advantage in this setting.

We recap all of the different learning models considered in Table 1.

Model |  Quantum or Classical |  Learning resource |  Optimal $(\epsilon,\delta)$ learner complexity |  Bounds on optimal learner complexity
---|---|---|---|---
Labelled examples |  Classical |  Sample $(X,C(X))$ where $X\sim\mathcal{D}$ |  $T_{C}$ |  $\Theta\left[\frac{1}{\epsilon}\left(d+\log(\frac{1}{\delta})\right)\right]$
Equivalence queries |  Classical |  See Section 4 |  $T_{E}$ |  $O\left(\left[d+\log(\frac{1}{\delta})\right]\log^{9}\left(\frac{1}{\epsilon}\right)\right)$
Imperfect equivalence queries |  Classical |  See Section 4 |  $T_{IE}$ |  $O(T_{E})$
Quantum samples |  Quantum |  Copy of $\ket{\psi_{c}}$ |  $T_{S}$ |  $\Theta(T_{C})$
Quantum oracle calls |  Quantum |  Application of $Q_{c}$ or $Q_{c}^{\dagger}$ |  $T_{O}$ |  $O(\frac{1}{\sqrt{\epsilon}}T_{IE})$, $\Omega(\frac{d}{\sqrt{\epsilon}})$
Table 1: Different learning models considered in our work. $T_{M}$ corresponds
to the minimum number of resources needed by any $(\epsilon,\delta)$-learner
in model $M$.

We end the preliminaries section with a recap of Grover’s algorithm. For a
subspace $\mathcal{V}$ of a Hilbert space $\mathcal{H}$, let
$\Pi_{\mathcal{V}}$ be the orthogonal projection map onto $\mathcal{V}$.
Furthermore, let $I_{\mathcal{V}}$ be the reflection operator in
$\mathcal{V}^{\perp}$, given by

$I_{\mathcal{V}}=\mathbbm{1}-2\Pi_{\mathcal{V}}.$ (11)

For a state $\ket{\psi}$, let $I_{\ket{\psi}}$ be the reflection operator when
$\mathcal{V}=$ span$\\{\ket{\psi}\\}$.

Grover search takes as its input a “good” subspace
$\mathcal{G}\subseteq\mathcal{H}$, and an input state $\ket{\psi}$. One then
implements the Grover operator:

$D=-I_{\ket{\psi}}I_{\mathcal{G}}.$ (12)

The state $\ket{\psi}$ can be decomposed as

$\ket{\psi}=\sin(\theta)\ket{g}+\cos(\theta)\ket{b},$ (13)

where $\ket{g},\ket{b}$ are orthonormal, $\theta\in[0,\pi/2]$,
$\ket{g}\in\mathcal{G},\ket{b}\in\mathcal{G}^{\perp}$. It is well-known [24]
that

$D^{n}\ket{\psi}=\sin((2n+1)\theta)\ket{g}+\cos((2n+1)\theta)\ket{b}.$ (14)

and thus if one knows $\theta$ exactly, one can apply $D^{n}$ such that
$\sin((2n+1)\theta)\approx 1$.

##  3 Grover Subroutine

An essential subroutine for our quantum advantage is to use calls to $Q_{c}$
and $Q_{c}^{\dagger}$ to run a Grover search [24, 25]. This leads to a
quadratic improvement in learning complexity (up to polylogarithmic factors)
over classical PAC learning. In this section, we describe our Grover
subroutine.

Our Grover subroutine takes as an input a “good” subset
$G\subseteq\\{(x,b):x\in\mathcal{X},b\in\\{0,1\\}\\}$, where we wish to find
an $x$ such that $(x,c(x))\in G$. We define a corresponding “good” subspace by

$\mathcal{G}=\text{span}\\{\ket{x\;b}:(x,b)\in G\\}.$ (15)

In order to implement Grover’s search, we need to implement the Grover
operator, as defined in equation (12). We show that implementing $D$ requires
a constant number of queries.

###### Lemma 3.1

One can implement the Grover operator $D$ with one call to $Q_{c}$ and one to
$Q_{c}^{\dagger}$.

Proof: Note that $I_{\mathcal{G}}$ is independent of $c$ and, therefore, may
be implemented by a (possibly exponentially sized circuit) without any
queries. To implement $I_{\ket{\psi_{c}}}$, note that $\displaystyle
I_{\ket{\psi_{c}}}$
$\displaystyle=\mathbbm{1}-2\outerproduct{\psi_{c}}{\psi_{c}},$ (16)
$\displaystyle=Q_{c}(\mathbbm{1}-2\outerproduct{\text{IN}}{\text{IN}})Q_{c}^{\dagger},$
(17) $\displaystyle=Q_{c}I_{\ket{\text{IN}}}Q_{c}^{\dagger}.$ (18) Note that
$I_{\ket{\text{IN}}}$ is independent of $c$ and, therefore, may be implemented
by a (possibly exponentially sized circuit) without any queries. ∎

We decompose

$\ket{\psi_{c}}=\sin(\theta)\ket{g}+\cos(\theta)\ket{b},$ (19)

where $\ket{g},\ket{b}$ are orthonormal, $\theta\in[0,\pi/2]$,
$\ket{g}\in\mathcal{G},\ket{b}\in\mathcal{G}^{\perp}$. If we knew $\theta$
exactly, we could apply $D^{n}$ such that $\sin((2n+1)\theta)\approx 1$.
However, since $\theta$ depends on $\mathcal{D}$, which is unknown, this is
impossible. Instead, we use the well-established [23] version of Grover’s
search for an unknown number of items. Our exact subroutine is given below;
Algorithm 1.

Algorithm 1:
Input: $G\subseteq\\{(x,b):x\in\mathcal{X},b\in\\{0,1\\}\\}$ a good subspace,
$\epsilon>0$ a tolerance
Output:  labelled example $(x,c(x))$. Succeeds if $(x,c(x))\in G$ 1. Produce
$\ket{\psi_{c}}=Q_{c}\ket{\text{IN}}$ 2. Pick $N$ from $0,1\dots,\lceil
2/\sqrt{\epsilon}\rceil-1$ uniformly at random 3. Apply $D$, the Grover
operator, $N$ times to $\ket{\psi_{c}}$ 4. Measure the resulting state in the
computational basis

The properties of our algorithm are summarised in the following theorem

###### Theorem 3.2

Let $G\subseteq\\{(x,b):x\in\mathcal{X},b\in\\{0,1\\}\\}$ be a good subset,
$\epsilon>0$ be a fixed tolerance. Suppose that we run Algorithm 1 with these
inputs, then

  1. (i)

In the worst case, the algorithm makes $O(1/\sqrt{\epsilon})$ oracle (or
inverse oracle) calls

  2. (ii)

If $\mathbb{P}_{X\sim\mathcal{D}}\left[(X,c(X))\in G\right]\geq\epsilon$ then
the algorithm succeeds, i.e., returns $(x,c(x))\in G$, with probability at
least $p=0.09$.

  3. (iii)

Conditional on succeeding, the output of the algorithm $(X,c(X))$ is
distributed according to

$\mathbb{P}\left[(X,c(X))|\text{algorithm
succeeds}\right]=\frac{\mathbb{P}_{X\sim\mathcal{D}}\left[X\right]}{\mathbb{P}_{X\sim\mathcal{D}}\left[(X,c(X))\in
G\right]}.$ (20)

Proof:
Part $(i)$: From the definition of the algorithm and Lemma 3.1, the worst case
number of oracle calls is $1+2(\lceil
2/\sqrt{\epsilon}\rceil-1)=O(1/\sqrt{\epsilon})$.
Part $(ii)$: Let $M=\lceil 2/\sqrt{\epsilon}\rceil$, let $\theta$ be as in
equation (19) and let $p_{s}(\theta)$ be the probability that the algorithm
succeeds. Note that $\mathbb{P}_{X\sim\mathcal{D}}\left[(X,c(X))\in
G\right]\geq\epsilon\Leftrightarrow\sin(\theta)\geq\sqrt{\epsilon}$. We use
Lemma 2 (section 6) from [23], which claims
$p_{s}(\theta)=\frac{1}{2}-\frac{1}{4M}\frac{\sin(4M\theta)}{\sin(2\theta)}.$
(21) For $\sin(\theta)\in[\sqrt{\epsilon},1/\sqrt{2}]$:
$\displaystyle M$ $\displaystyle\geq\frac{2}{\sin(\theta)},$ (22)
$\displaystyle\geq\frac{1}{\sin(2\theta)},$ (23) and thus
$p_{s}(\theta)\geq\frac{1}{2}-\frac{1}{4}=\frac{1}{4}>0.09.$ (24) Note that
for $\theta\in[\pi/4,\pi/2]$, $\sin(2\theta)\geq\frac{\pi/2-\theta}{\pi/4},$
(25) Thus for $\theta\in[\pi/4,(1/2-1/4M)\pi]$, we have that $\displaystyle
p_{s}(\theta)$
$\displaystyle\geq\frac{1}{2}-\frac{1}{4M}\cdot\frac{4/\pi}{\pi/2-(1/2-1/4M)\pi},$
(26) $\displaystyle=\frac{1}{2}-\frac{4}{\pi^{2}}>0.09.$ (27) Finally, for
$\theta\in[(1/2-1/4M)\pi,\pi/2]$, note that $\sin(2\theta)\geq 0$ and
$\sin(4M\theta)\leq 0$ so that $p_{s}(\theta)\geq 1/2>0.09$.
Part $(iii)$. This follows from the form of $D^{n}\ket{\psi_{c}}$; the
relative magnitude of the amplitudes in $\ket{g}$ is unchanged by the Grover
operator $D$. ∎

We discuss how to combine the Grover subroutine with the algorithm of section
4 to achieve a quantum learning complexity of equation (5) in section 5.

##  4 Learning with imperfect equivalence queries

Equivalence queries are an alternative learning model for PAC learning. It was
recently shown [22] that PAC learning with equivalence queries gives an
exponential advantage over learning with labelled examples. In this section,
we show how to use imperfect equivalence queries to PAC learn a concept class.

###### Definition 4.1

An (ideal) equivalence query consists of submitting a candidate hypothesis $h$
for an underlying true concept $c$. If $h=c$ then we are told YES. Otherwise,
we receive a labelled example $(x,c(x))$ where $c(x)\neq h(x)$ at random
according to the distribution
$\mathbb{P}(y)=\mathcal{D}(y)/\mathcal{D}(\\{x:c(x)\neq h(x)\\})$. Such a
labelled example where $h(x)\neq c(x)$ is called a counterexample.

Equivalence queries are a very strong learning model, which is perhaps
unrealistic. Thus, we assume we can only implement them probabilistically:

###### Definition 4.2

An imperfect equivalence query consists of submitting a candidate hypothesis
$h$ for the underlying concept $c$. In return we receive some labelled example
$(x,c(x))$ with the following promises

  * •

The distribution of $(X,c(X))$ conditional on being a counterexample is the
same as an ideal equivalence query.

  * •

If $d(h,c)\geq\epsilon$ then with some constant probability $p$ we receive a
counterexample.

Note that we can tell whether our imperfect equivalence query failed or not -
we can look at the result $(x,c(x))$ and check whether $h(x)=c(x)$. If they
are equal, the equivalence query failed. Otherwise, it succeeded. Classically,
we can implement an imperfect equivalence query using $1/\epsilon$ random
labelled examples - we just sample $1/\epsilon$ times and see whether
$c(x)\neq h(x)$ for any of our samples. On a quantum computer we can do this
in $1/\sqrt{\epsilon}$ time using Grover’s algorithm, as described in section
3 in Theorem 3.2.

We need one additional tool from classical learning theory to run our
algorithm:

###### Definition 4.3

Suppose we have a set of classifiers
$\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ and a distribution $\rho$ on
$\mathcal{H}$. Then the weighted majority vote [26],
$\text{WMV}_{\mathcal{H},\,\rho}\in\\{0,1\\}^{\mathcal{X}}$ is defined such
that it maximises

$\mathbb{P}_{h\sim\rho}\left[\text{WMV}_{\mathcal{H},\,\rho}(x)=h(x)\right],$
(28)

for every $x$ (ties can be broken arbitrarily).

Suppose we have a classical algorithm $\mathcal{A}$ that uses
$T_{E}(\epsilon,\delta,d)$ (ideal) equivalence queries to PAC learn a concept
class $\mathcal{C}$. We show how to use $O(T_{E}+\log(1/\delta))$ imperfect
equivalence queries to PAC learn the same concept class.

The full detail of the algorithm is given below in algorithm 4. It works by
running $\mathcal{A}$, replacing every equivalence query with repeated
imperfect equivalence queries until one succeeds. We terminate if the learning
algorithm $\mathcal{A}$ terminates or if we make a total of $R(T_{E},\delta)$
imperfect equivalence queries.

We give some rough intuition for why the algorithm works before moving to
prove so. If $\mathcal{A}$ terminates, then with high probability, it outputs
an approximately correct hypothesis. If we pick $R$ large enough, then with
high probability $T_{E}$ ideal queries to hypotheses $h_{i}$ with
$d(h_{i},c)\geq\epsilon$ would all succeed in $<R/3$ imperfect equivalence
queries. Thus, if the algorithm $\mathcal{A}$ does not terminate and we make
$R$ total imperfect equivalence queries, with high probability, we spent
$>2/3$ of our imperfect equivalence queries on hypotheses $h_{i}$ with
$d(h_{i},c)<\epsilon$. Hence, if we take the weighted majority vote of all of
the hypotheses we queried, weighted by the number of imperfect equivalence
queries spent on each hypothesis, most of the vote will be decided by
hypotheses that are close to the concept $c$. Thus, the weighted majority vote
will also be close to $c$.

The full proof of why algorithm 4 works is given as two lemmas. Before these,
we introduce some terminology.

###### Definition 4.4

A transcript of a run of algorithm 4 is given by the list of hypotheses
$\mathcal{H}=\\{h_{i}\\}$ that the algorithm queried along with a
corresponding collection of natural numbers $n_{i}>0$, where $n_{i}$ is the
number of imperfect equivalence queries spent on $h_{i}$.

The time-spent distribution $\rho$ is the probability distribution on
$\mathcal{H}$ given by $\rho(h_{i})=n_{i}/\sum_{i}n_{i}$.

Finally, $F=\\{i:d(h_{i},c)\geq\epsilon\\}$ is called the “feasible” set,
where our imperfect equivalence query succeeds with probability at least $p$.
Correspondingly $I=\\{i:d(h_{i},c)<\epsilon\\}$ is the “infeasible” set, where
there is no promise on the probability of success.

Firstly, we show that with high probability that a bounded number of queries
is spent on the feasible set

###### Lemma 4.5

With probability $\geq 1-\delta$ the total number of imperfect equivalence
queries to feasible hypotheses is at most

$2T_{E}/p+(1/2p^{2})\log(1/\delta).$ (29)

Proof: A imperfect equivalence query of a feasible hypothesis has (by
definition) a chance $\geq p$ of succeeding, and the individual imperfect
equivalence queries are independent. Additionally, there are at most $T_{E}$
feasible hypotheses to query (since the classical algorithm makes at most
$T_{E}$ total equivalence queries). Thus, the probability that we succeed on
all the feasible hypotheses using at most $m$ imperfect queries feasible
hypotheses is lower bounded by the probability of getting at least $T_{E}$
successes from a binomial distribution $B(m,p)$. Thus, the chance of failure
is lower bounded by the chance of fewer than $T_{E}$ successes from $B(m,p)$.
Let $X\sim B(m,p)$. Applying Hoeffding’s inequality [27], for $m\geq T_{E}/p$
we see that $\mathbb{P}\left[X<t\right]\leq e^{-2m(p-T_{E}/m)^{2}}.$ (30) Thus
it is sufficient for $2m\left(p-\frac{T_{E}}{m}\right)^{2}\geq\log(1/\delta).$
(31) In turn, it is sufficient that $2mp^{2}-4pT_{E}\geq\log(1/\delta),$ (32)
whence we deduce our bound.
∎

Next we prove that if we make enough imperfect equivalence queries on
infeasible hypotheses, the weighted majority vote of the transcript must be
close to the underlying concept $c$

###### Lemma 4.6

Suppose we spend at least $2R/3$ imperfect equivalence queries on infeasible
hypotheses. Then the weighted majority vote $M$ of the transcript with the
time-spent distribution has $d(M,c)<4\epsilon$.

Proof: Fix the transcript $h_{1},\dots h_{k}$. Let $\rho$ be the time-spent
distribution and let $\rho^{\prime}$ be the time-spent distribution
conditioned on the infeasible set. That is, for $i\in I$,
$\rho^{\prime}(h_{i})=\rho(h_{i})/\rho(I)$. Similarly let $\tilde{\rho}$ the
the time-spent distribution conditioned on the feasible set. We first show
that if the infeasible set overwhelmingly votes for a bit $y$, then the whole
transcript must also vote for that $y$. To be precise, suppose that
$\mathbb{P}_{h\sim\rho^{\prime}}\left[h(x)=y\right]>3/4$, then
$\displaystyle\mathbb{P}_{h\sim\rho}\left[h(x)=y\right]$
$\displaystyle=\mathbb{P}_{h\sim\rho^{\prime}}\left[h(x)=y\right]\mathbb{P}_{h\sim\rho}\left[h\in
I\right]+\mathbb{P}_{h\sim\tilde{\rho}}\left[h(x)=y\right]\mathbb{P}_{h\sim\rho}\left[h\in
F\right],$ (33) $\displaystyle>\frac{3}{4}\cdot\frac{2}{3},$ (34)
$\displaystyle=\frac{1}{2}.$ (35) Letting $M=\text{WMV}_{\mathcal{H},\,\rho}$,
we deduce (inspired by [26]) that
$\displaystyle\mathbb{P}_{X\sim\mathcal{D}}\left[M(X)\neq c(X)\right]$
$\displaystyle\leq\mathbb{P}_{X\sim\mathcal{D}}\left[\mathbb{P}_{h\sim\rho^{\prime}}\left[h(X)\neq
c(X)\right]\geq\frac{1}{4}\right],$ (36) Markov’s inequality,
$\displaystyle\leq
4\mathbb{E}_{X\sim\mathcal{D}}\mathbb{E}_{h\sim\rho^{\prime}}[\mathbbm{1}_{\\{h(X)\neq
c(X)\\}}],$ (37) $\displaystyle=4\mathbb{E}_{h\sim\rho^{\prime}}[d(h,c)],$
(38) definition of infeasible set, $\displaystyle<4\epsilon$ (39) ∎

We can now prove the performance of our algorithm

###### Theorem 4.7

Let the maximum number of imperfect equivalence queries of algorithm 4 be

$R(T_{E}(\epsilon,\delta,d),\delta)=6T_{E}(\epsilon,\delta,d)/p++(3/2p^{2})\log(1/\delta),$
(40)

then algorithm 4 produces a hypothesis $h$ with $d(h,c)\leq 4\epsilon$ with
probability at least $1-2\delta$.

Proof: By Lemma 4.5, with probability $\geq 1-\delta$ we spend at most $R/3$
imperfect equivalence queries on feasible hypotheses - suppose this happens.
If we succeed in an equivalence query for every hypothesis required by
$\mathcal{A}$ then with probability at least $1-\delta$, $\mathcal{A}$ outputs
a hypothesis $h$ with $d(h,c)\leq\epsilon$. Otherwise, we spend at least
$2R/3$ imperfect equivalence queries on infeasible hypotheses (as we assumed
the feasible ones took at most $R/3$ imperfect equivalence queries) and then
by Lemma 4.6 the weighted majority vote $\text{WMV}_{\mathcal{H},\,\rho}$ has
$d(\text{WMV}_{\mathcal{H},\,\rho},c)<4\epsilon$. Thus algorithm 4 outputs a
$4\epsilon$-approximately correct hypothesis with probability at least
$(1-\delta)^{2}\geq 1-2\delta$. ∎

Algorithm 2:
Input: $\delta>0,\epsilon>0$ (the usual PAC parameters) and $\mathcal{A}$ a
classical equivalence query learning algorithm with worst case query
complexity $T_{E}>0$
Output:  Hypothesis $h\in\\{0,1\\}^{\mathcal{X}}$ 1. Set the maximum imperfect
equivalence query budget as $R=6T_{E}/p+(3/2p^{2})\log(1/\delta)$. If $R$
total imperfect equivalence queries have ever been made, go to step 3 2. Run
$\mathcal{A}$, whenever it requires an equivalence query to a hypothesis $h$,
repeatedly make imperfect equivalence queries until one succeeds. If
$\mathcal{A}$ terminates, output the output of $\mathcal{A}$ 3. Let
$\mathcal{H}=\\{h_{1},\dots,h_{k}\\}$ be the set of hypothesis we ran
imperfect equivalence queries on (so that $k\leq T_{E}$). Suppose we spent
$n_{i}$ imperfect equivalence queries on $h_{i}$ (so that $\sum n_{i}=R$). Let
$\rho(h_{i})=n_{i}/N$ and output $h=\text{WMV}_{\mathcal{H},\,\rho}$

##  5 Upper bound on quantum learning complexity

Here, we combine the results of sections 3 and 4 to give an upper bound on
$T_{O}$, the learning complexity of PAC learning with a state preparation
oracle $Q_{c}$ (and its inverse).

Suppose that it takes $E(\epsilon)$ queries to perform an imperfect
equivalence query for a hypothesis $h$. If we have a classical equivalence
learning algorithm $\mathcal{A}$ with a query complexity of
$T_{E}(\epsilon,\delta,d)$, then we can use algorithm 4 of section 4 to get a
quantum PAC learning algorithm with learning complexity

$E(\epsilon/4)R(T_{E}(\epsilon/4,\delta/2,d),\delta/2).$ (41)

The current best known $T_{E}$ [22] has a worst-case query complexity of

$T_{E}=O\left(\left[d+\log(\frac{1}{\delta})\right]\log^{9}\left(\frac{1}{\epsilon}\right)\right).$
(42)

If we use the Grover subroutine (section 3 algorithm 1) with
$G=\\{(x,1-h(x)):x\in\mathcal{X}\\}$ to implement the imperfect equivalence
queries, we find $E(\epsilon)=O(1/\sqrt{\epsilon})$. Substituting these
$T_{E}$ and $E$ into the bound from equation (41), we get an upper bound of

$T_{O}=O\left(\frac{1}{\sqrt{\epsilon}}\left[d+\log(\frac{1}{\delta})\right]\log^{9}\left(\frac{1}{\epsilon}\right)\right),$
(43)

which is a square-root improvement (up to polylogarithmic factors) over the
classical PAC learning sample complexity of equation (8).

##  6 Lower bound on quantum learning complexity

In this section, we prove a lower bound on quantum PAC learning with a state
preparation oracle (and its inverse). We show that $\Omega(d/\sqrt{\epsilon})$
oracle calls are necessary.

Suppose we have a concept class $\mathcal{C}$ with VC dimension $d+1$. Then
there is a set $Z$ of size $d+1$ in $\mathcal{X}$ which is shattered by
$\mathcal{C}$. We pick a marked element $x_{0}\in Z$ and let
$Y=Z\setminus\\{x_{0}\\}$. We define our distribution $\mathcal{D}$ as a
perturbed delta-function, the standard distribution used to prove lower bounds
in learning:

$\mathcal{D}(x)=\begin{cases}0,&\text{if }x\notin Z,\\\ 1-4\epsilon,&\text{if
}x=x_{0},\\\ 4\epsilon/d,&\text{if }x\in Y.\end{cases}$ (44)

We also restrict our concept class to
$\widetilde{\mathcal{C}}=\\{c\in\mathcal{C}:c(x_{0})=0\\}$. If our PAC
algorithm works on $\mathcal{C}$, it will certainly work on
$\widetilde{\mathcal{C}}$. Since our distribution is restricted to $Z$ we need
only identify the behaviour of our concept on $Z$. Thus, we can index our
concepts by bit-strings $u\in\\{0,1\\}^{d}$ and index them with elements of
$Y$. To be precise, we identify a concept $c\in\widetilde{\mathcal{C}}$ with a
bit-string $u\in\\{0,1\\}^{d}$, where $u_{y}=c(y)$.

For a given bit-string $u\in\\{0,1\\}^{d}$, the state preparation oracle acts
as

$Q_{u}\ket{\text{IN}}=\sqrt{1-4\epsilon}\ket{x_{0}\;0}+\sqrt{\frac{4\epsilon}{d}}\sum_{x\in
Y}\ket{x\;u_{x}}.$ (45)

Our main approach is to reduce to the following fact from Lemma 51 in [20].

###### Lemma 6.1

Let $u\in\\{0,1\\}^{d}$ be a bit string, and let $O_{u}$ be a weak phase-
kickback oracle, that is

$O_{u}\ket{x}=e^{2i\eta u_{x}}\ket{x}.$ (46)

Then recovering more than $3/4$ of the bits of $u$ with high probability
requires at least $\Omega(d/\eta)$ calls to $O_{u}$, its inverse or controlled
versions of these.

Proof: See [20] ∎

We will use calls to controlled versions of $O_{u}$ (denoted $c-O_{u}$) to
implement the PAC state generation oracle $Q_{u}$. We fix $\eta\in[0,\pi/2]$
such that $\sin(\eta)=\sqrt{4\epsilon}$.

###### Lemma 6.2

One can implement $Q_{u}$ using one call to $c-O_{u}$, one to
$c-O_{u}^{\dagger}$ and two qubit-ancillae.

Proof: First, it is convenient to shift the phase to have a $\pm$ symmetry.
Define a constant phase gate as
$P_{\alpha}\ket{x}=e^{i\alpha}\ket{x}.$ (47) Then let
$\widetilde{O}_{u}=P_{\eta}O_{u}^{\dagger},$ (48) so that
$\widetilde{O}_{u}\ket{x}=e^{i\eta\hat{u}_{x}}\ket{x},$ (49) where
$\hat{u}_{x}=(-1)^{u_{x}}.$ (50) We start by generating a uniform
superposition of indices with the two-qubit ancillae in the $\ket{+}$ state:
$\frac{1}{2\sqrt{d}}\sum_{x\in
Y}\ket{x}[\ket{00}+\ket{01}+\ket{10}+\ket{11}].$ (51) We next apply 4
controlled gates - either $c-P_{\eta}$, $c-P_{-\eta}$ $c-\widetilde{O}_{u}$
and $c-\widetilde{O}_{u}^{\dagger}$, such that each term in the superposition
in equation (51) picks up a different phase:
$\mapsto\frac{1}{2\sqrt{d}}\sum_{x\in
Y}\ket{x}\left[e^{i\eta}\ket{00}+e^{-i\eta}\ket{01}+e^{i\eta\hat{u}_{x}}\ket{10}+e^{-i\eta\hat{u}_{x}}\ket{11}\right].$
(52) Note that this requires two calls to singly controlled versions of the
oracle - we can implement a double-controlled version by using a CCNOT
(Toffoli) gate followed by a controlled oracle. Next, we apply a Hadamard gate
to the second qubit register $\mapsto\frac{1}{\sqrt{2d}}\sum_{x\in
Y}\ket{x}\left[\ket{0}(\cos(\eta)\ket{0}+i\sin(\eta)\ket{1})+\ket{1}(\cos(\eta\hat{u}_{x})\ket{0}+i\sin(\eta\hat{u}_{x})\ket{1})\right].$
(53) We then apply $S^{\dagger}$ to the second qubit register (to remove the
factors of $i$). We also use the even/odd ness of cos/sin to regroup the
terms: $\mapsto\frac{1}{\sqrt{2d}}\sum_{x\in
Y}\ket{x}\left[\cos(\eta)(\ket{0}+\ket{1})\ket{0}+\sin(\eta)(\ket{0}+\hat{u}_{x}\ket{1})\ket{1}\right].$
(54) We then apply a Hadamard gate to the first qubit register:
$\mapsto\cos(\eta)\left(\frac{1}{\sqrt{d}}\sum_{x\in
Y}\ket{x}\right)\ket{00}+\sin(\eta)\left(\frac{1}{\sqrt{d}}\sum_{x\in
Y}\ket{x\;u_{x}}\right)\ket{1}$ (55) Conditional on the final qubit being in
the state $\ket{0}$, we apply a unitary to the first register that maps the
uniform superposition over $Y$ into the state $\ket{x_{0}}$:
$\mapsto\cos(\eta)\ket{x_{0}\;0\;0}+\sin(\eta)\left(\frac{1}{\sqrt{d}}\sum_{x\in
Y}\ket{x\;u_{x}}\right)\ket{1}$ (56) Finally, conditional on the first
register not being in the state $\ket{x_{0}}$, we apply an $X$ gate to the
second qubit register,followed by an $H$ gate on the second qubit register:
$\mapsto\left[\cos(\eta)\ket{x_{0}\;0}+\sin(\eta)\left(\frac{1}{\sqrt{d}}\sum_{x\in
Y}\ket{x\;u_{x}}\right)\right]\ket{+}$ (57) But by the definition of $\eta$,
we see that this is exactly equal to the action of the PAC oracle:
$(Q_{u}\ket{\text{IN}})\ket{+}$ (58) ∎

We thus deduce our bound

###### Theorem 6.3

$T_{O}=\Omega\left(\frac{d}{\sqrt{\epsilon}}\right)$

Proof: We can replace every call to $Q_{u}$ (or its inverse) in our PAC
algorithm with the unitary process described in Lemma 6.2, which requires a
constant number of calls to (a controlled) $O_{u}$ (or its inverse). If the
PAC algorithm outputs a correct hypothesis, then by construction of our
distribution, it must agree on at least $3/4$ of the bits of $u$. Thus, the
algorithm replaced with calls to $O_{u}$ (and its inverse) satisfies the
conditions of Lemma 6.1, and thus it must use at least $\Omega(d/\eta)$ calls
to $O_{u}$. Hence, we reach a lower bound of
$T_{O}=\Omega\left(\frac{d}{\arcsin{\sqrt{4\epsilon}}}\right)=\Omega\left(\frac{d}{\sqrt{\epsilon}}\right).$
(59) ∎

Note that our lower bound matches our upper bound (equation (5)), up to
polylogarithmic factors.

##  7 Application to learning $k-$juntas

A $k$-junta is a function $f:\\{0,1\\}^{n}\to{0,1}$ that only depends on a
subset of $k$ bits. Letting $\mathcal{X}=\\{0,1\\}^{n}$, we can consider the
concept class $\mathcal{C}=\\{f\in\\{0,1\\}^{\mathcal{X}}:f\text{ is a
}k\text{ junta}\\}$. The exact VC dimension of $\mathcal{C}$ is unknown, but
we can bound it using the inequalities

$2^{d}\leq|\mathcal{C}|\leq|\mathcal{X}|^{d}+1.$ (60)

The first of these comes from noting that if $\mathcal{C}$ shatters a set of
size $\ell$, it must contain at least $2^{\ell}$ elements; the second is
called Sauer’s lemma [28]. We can bound

$|\mathcal{C}|\leq\binom{n}{k}2^{(2^{k})},$ (61)

since there are $\binom{n}{k}$ ways to choose the $k$ bits determining the
junta, and then $2^{(2^{k})}$ choices for the underlying function. We deduce
that

$d\leq\log\left[\binom{n}{k}\right]+2^{k}\leq k\log(en/k)+2^{k}.$ (62)

Thus, our learning algorithm can PAC learn a $k-$junta with

$O\left(\frac{1}{\sqrt{\epsilon}}\left[k\log\left(\frac{n}{k}\right)+2^{k}+\log(\frac{1}{\delta})\right]\log^{9}(1/\epsilon)\right),$
(63)

oracle calls. This has a worse scaling in $n$ than algorihtms presented in
[29, 10], but has a better scaling in $\epsilon$ and works for any underlying
distribution, whereas previous work has focused on the uniform distribution.

## Acknowledgements

The authors thank J. van Apeldoorn, R. de Wolf, S. Arunachalam, J. Cudby, C.
Long and J. Bayliss for helpful discussions related to this work.

Wilfred Salmon was supported by the EPRSC and Hitachi. Sergii Strelchuk
acknowledges support from the Royal Society University Research Fellowship.
Tom Gur is supported by the UKRI Future Leaders Fellowship MR/S031545/1 and an
EPSRC New Horizons Grant EP/X018180/1. Sergii Strelchuk and Tom Gur are
further supported by EPSRC Robust and Reliable Quantum Computing Grant
EP/W032635/1.

## References

  * [1] L.. Valiant  “A Theory of the Learnable”  In _Commun. ACM_ 27.11 New York, NY, USA: Association for Computing Machinery, 1984, pp. 1134–1142  DOI: 10.1145/1968.1972
  * [2] V.. Vapnik and A.. Chervonenkis  “On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities”  In _Theory of Probability & Its Applications_ 16.2, 1971, pp. 264–280  DOI: 10.1137/1116025
  * [3] Anselm Blumer, A. Ehrenfeucht, David Haussler and Manfred K. Warmuth  “Learnability and the Vapnik-Chervonenkis Dimension”  In _J. ACM_ 36.4 New York, NY, USA: Association for Computing Machinery, 1989, pp. 929–965  DOI: 10.1145/76359.76371
  * [4] Steve Hanneke  “The Optimal Sample Complexity of PAC Learning”  In _Journal of Machine Learning Research_ 17.38, 2016, pp. 1–15  URL: http://jmlr.org/papers/v17/15-389.html
  * [5] Nader H Bshouty and Jeffrey C Jackson  “Learning DNF over the uniform distribution using a quantum example oracle”  In _Proceedings of the eighth annual conference on Computational learning theory_ , 1995, pp. 118–127  DOI: 10.1137/S0097539795293123
  * [6] Srinivasan Arunachalam and Ronald Wolf  “Guest Column: A Survey of Quantum Learning Theory”  In _SIGACT News_ 48.2 New York, NY, USA: Association for Computing Machinery, 2017, pp. 41–67  DOI: 10.1145/3106700.3106710
  * [7] Srinivasan Arunachalam, Yihui Quek and John Smolin  “Private learning implies quantum stability”  In _arXiv preprint arXiv:2102.07171_ , 2021
  * [8] Haoyuan Cai, Qi Ye and Dong-Ling Deng  “Sample complexity of learning parametric quantum circuits”  In _Quantum Science and Technology_ 7.2 IOP Publishing, 2022, pp. 025014
  * [9] Ethan Bernstein and Umesh Vazirani  “Quantum Complexity Theory”  In _SIAM Journal on Computing_ 26.5, 1997, pp. 1411–1473  DOI: 10.1137/S0097539796300921
  * [10] Thomas Chen, Shivam Nadimpalli and Henry Yuen  “Testing and Learning Quantum Juntas Nearly Optimally”  In _Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2023, pp. 1163–1185  DOI: 10.1137/1.9781611977554.ch43
  * [11] Srinivasan Arunachalam and Ronald Wolf  “Optimal Quantum Sample Complexity of Learning Algorithms”  In _Journal of Machine Learning Research_ 19.71, 2018, pp. 1–36  URL: http://jmlr.org/papers/v19/18-195.html
  * [12] Niklas Pirnay, Ryan Sweke, Jens Eisert and Jean-Pierre Seifert  “Superpolynomial quantum-classical separation for density modeling”  In _Phys. Rev. A_ 107 American Physical Society, 2023, pp. 042416  DOI: 10.1103/PhysRevA.107.042416
  * [13] Scott Aaronson  “The learnability of quantum states”  In _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ 463.2088 The Royal Society London, 2007, pp. 3089–3114
  * [14] Kai-Min Chung and Han-Hsuan Lin  “Sample efficient algorithms for learning quantum channels in PAC model and the approximate state discrimination problem”  In _arXiv preprint arXiv:1810.10938_ , 2018
  * [15] Andrea Rocchetto  “Stabiliser States Are Efficiently PAC-Learnable”  In _Quantum Info. Comput._ 18.7–8 Paramus, NJ: Rinton Press, Incorporated, 2018, pp. 541–552
  * [16] Arun Padakandla and Abram Magner  “PAC Learning of Quantum Measurement Classes: Sample Complexity Bounds and Universal Consistency”  In _International Conference on Artificial Intelligence and Statistics_ , 2022, pp. 11305–11319  PMLR
  * [17] Hao-Chung Cheng, Min-Hsiu Hsieh and Ping-Cheng Yeh  “The learnability of unknown quantum measurements”  In _arXiv preprint arXiv:1501.00559_ , 2015
  * [18] Chi Zhang  “An improved lower bound on query complexity for quantum PAC learning”  In _Information Processing Letters_ 111.1 Elsevier, 2010, pp. 40–45
  * [19] Robin Kothari and Ryan O’Donnell  “Mean estimation when you have the source code; or, quantum Monte Carlo methods”  In _Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2023, pp. 1186–1215  DOI: 10.1137/1.9781611977554.ch44
  * [20] Joran Apeldoorn, Arjan Cornelissen, András Gilyén and Giacomo Nannicini  “Quantum tomography using state-preparation unitaries”  In _Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2023, pp. 1265–1318  DOI: 10.1137/1.9781611977554.ch47
  * [21] Jeongwan Haah, Robin Kothari, Ryan O’Donnell and Ewin Tang  “Query-optimal estimation of unitary channels in diamond distance”  In _arXiv preprint arXiv:2302.14066_ , 2023
  * [22] Grzegorz Gluch and Ruediger Urbanke  “Exponential Separation between Two Learning Models and Adversarial Robustness”  In _Advances in Neural Information Processing Systems_ 34 Curran Associates, Inc., 2021, pp. 20785–20797  URL: https://proceedings.neurips.cc/paper_files/paper/2021/file/ae06fbdc519bddaa88aa1b24bace4500-Paper.pdf
  * [23] Michel Boyer, Gilles Brassard, Peter Høyer and Alain Tapp  “Tight Bounds on Quantum Searching”  In _Fortschritte der Physik_ 46.4-5, 1998, pp. 493–505  DOI: https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5¡493::AID-PROP493¿3.0.CO;2-P
  * [24] Michael A. Nielsen and Isaac L. Chuang  “Quantum Computation and Quantum Information: 10th Anniversary Edition”  Cambridge University Press, 2010  DOI: 10.1017/CBO9780511976667
  * [25] Lov K. Grover  “A Fast Quantum Mechanical Algorithm for Database Search”  In _Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’96  Philadelphia, Pennsylvania, USA: Association for Computing Machinery, 1996, pp. 212–219  DOI: 10.1145/237814.237866
  * [26] Andres Masegosa, Stephan Lorenzen, Christian Igel and Yevgeny Seldin  “Second Order PAC-Bayesian Bounds for the Weighted Majority Vote”  In _Advances in Neural Information Processing Systems_ 33 Curran Associates, Inc., 2020, pp. 5263–5273  URL: https://proceedings.neurips.cc/paper_files/paper/2020/file/386854131f58a556343e056f03626e00-Paper.pdf
  * [27] Wassily Hoeffding  “Probability Inequalities for Sums of Bounded Random Variables”  In _Journal of the American Statistical Association_ 58.301 Taylor & Francis, 1963, pp. 13–30  DOI: 10.1080/01621459.1963.10500830
  * [28] Richard P Anstee, Lajos Rónyai and Attila Sali  “Shattering news”  In _Graphs and Combinatorics_ 18 Springer, 2002, pp. 59–73  DOI: 10.1007/s003730200003
  * [29] Alp Atici and Rocco A. Servedio  “Quantum Algorithms for Learning and Testing Juntas”  In _Quantum Information Processing_ 6, 2007  DOI: https://doi.org/10.1007/s11128-007-0061-6


# Resonant Spin Excitation in the High Temperature Superconductor
Ba0.6K0.4Fe2As2

A. D. Christianson  Neutron Scattering Science Division, Oak Ridge National
Laboratory, Oak Ridge, TN 37831, USA  E. A. Goremychkin  Materials Science
Division, Argonne National Laboratory, Argonne, IL 60439-4845, USA  ISIS
Pulsed Neutron and Muon Facility, Rutherford Appleton Laboratory, Chilton,
Didcot OX11 0QX, United Kingdom  R. Osborn  Materials Science Division,
Argonne National Laboratory, Argonne, IL 60439-4845, USA<EMAIL_ADDRESS>S.
Rosenkranz  Materials Science Division, Argonne National Laboratory, Argonne,
IL 60439-4845, USA  M. D. Lumsden  Neutron Scattering Science Division, Oak
Ridge National Laboratory, Oak Ridge, TN 37831, USA  C. D. Malliakas
Materials Science Division, Argonne National Laboratory, Argonne, IL
60439-4845, USA  Department of Chemistry, Northwestern University, Evanston,
IL 60208-3113  l. S. Todorov  H. Claus  D. Y. Chung  Materials Science
Division, Argonne National Laboratory, Argonne, IL 60439-4845, USA  M. G.
Kanatzidis  Materials Science Division, Argonne National Laboratory, Argonne,
IL 60439-4845, USA  Department of Chemistry, Northwestern University,
Evanston, IL 60208-3113  R. I. Bewley  T. Guidi  ISIS Pulsed Neutron and Muon
Facility, Rutherford Appleton Laboratory, Chilton, Didcot OX11 0QX, United
Kingdom

###### Abstract

The recent observations of superconductivity at temperatures up to 55K in
compounds containing layers of iron arsenide Kamihara:2008p7994 ;
Takahashi:2008p7382 ; Ren:2008p8174 ; Rotter:2008p8535  have revealed a new
class of high temperature superconductors that show striking similarities to
the more familiar cuprates. In both series of compounds, the onset of
superconductivity is associated with the suppression of magnetic order by
doping holes and/or electrons into the band DeLaCruz:2008p8095  leading to
theories in which magnetic fluctuations are either responsible for or strongly
coupled to the superconducting order parameter Norman:2007p2671 . In the
cuprates, theories of magnetic pairing have been invoked to explain the
observation of a resonant magnetic excitation that scales in energy with the
superconducting energy gap and is suppressed above the superconducting
transition temperature, Tc. Such resonant excitations have been shown by
inelastic neutron scattering to be a universal feature of the cuprate
superconductors Hufner:2008p9494 , and have even been observed in heavy
fermion superconductors with much lower transition temperatures
Sato:2001p11225 ; Stock:2008p6655 ; Stockert:2008p11663 . In this paper, we
show neutron scattering evidence of a resonant excitation in Ba0.6K0.4Fe2As2,
which is a superconductor below 38 K Rotter:2008p8535 , at the momentum
transfer associated with magnetic order in the undoped compound, BaFe2As2, and
at an energy transfer that is consistent with scaling in other strongly
correlated electron superconductors. As in the cuprates, the peak disappears
at Tc providing the first experimental confirmation of a strong coupling of
the magnetic fluctuation spectrum to the superconducting order parameter in
the new iron arsenide superconductors.

Unconventional superconductivity has been the subject of considerable
theoretical and experimental interest since the discovery of superconductivity
in CeCu2Si2 and other heavy fermion compounds Steglich:1979p11524 , an
interest that was only intensified by the discovery of cuprate superconductors
with transition temperatures in excess of 100 K Norman:2007p2671 . Although
significant progress has been made, the origin of unconventional
superconductivity is still not understood. The observation of a magnetic
resonance in the spin excitation spectrum which appears concurrently with the
onset of superconductivity in both the high Tc cuprates
RossatMignod:1991p10509 ; Mook:1993p10706 ; Fong:1999p11512 ; Dai:2000p10619 ;
He:2002p11430  and the heavy fermion superconductors Sato:2001p11225 ;
Stock:2008p6655 ; Stockert:2008p11663  offers the tantalizing possibility of a
unifying theme for unconventional superconductivity that spans a diverse range
of superconducting materials. Recently, a new family of superconductors
containing layers of Fe2As2 has been discovered with Tcs in excess of 50 K
stimulating considerable experimental and theoretical activity
Kamihara:2008p7994 ; Takahashi:2008p7382 ; Ren:2008p8174 . Although there is
mounting evidence that the superconductivity in this new family is also
unconventional Mazin:2008p8170 , there is as yet no consensus concerning the
mechanism giving rise to superconductivity or even the superconducting pairing
symmetry. In this letter, we describe neutron scattering data that confirm for
the first time the existence of a resonant spin excitation below Tc in the
iron arsenide materials at an energy that shows similar scaling to other heavy
fermion and high-Tc superconductors.

Figure 1: The crystal structure of Ba0.6K0.4Fe2As2 (Fe: blue spheres, As:
yellow spheres, Ba/K: red spheres). The unit cell contains two layers of
Fe2As2 tetrahedra separated by planes of barium atoms. The blue arrows show
the ordering of the iron spins observed in the undoped parent compound
BaFe2As2 Huang:2008p8145 . The atomic distance of 2.77 Å that characterizes
both the antiferromagnetic modulation and the newly observed resonant
excitation is shown by the red arrows.  Figure 2: Inelastic neutron scattering
from Ba0.6K0.4Fe2As2 measured using incident neutron energies of 60 meV (a,b)
and 15 meV (c,d), at temperatures of 7 K (a,c) and 50 K (b,d). Above Tc (b,d),
the magnetic response consists of a column of excitations centred at 1.15 Å-1
and a dispersive ferromagnetic excitation. Below Tc, low-energy intensity in
the column is transferred to the resonant excitation at 15 meV. The strong
scattering at low energy transfers in each plot arises from the tail of strong
elastic nuclear scattering, while the scattering increases strongly at higher
Q due to inelastic phonon scattering. The colour scale is in units of
mbarns/sr/meV/mol.

Although the first iron arsenide superconductors were based on doped variants
of RFeAsO, where R is a rare earth element, there has been considerable
interest in a new series of tetragonal compounds based on AFe2As2 (A = Ba, Sr,
Ca), in which superconductivity is induced either by doping the A-site with
potassium or sodium Rotter:2008p8535 ; Sasmal:2008p8092  or by applying
pressure Park:2008p8883 . These contain the same tetrahedrally-coordinated
Fe2As2 planes as the LaFeAsO compounds (Fig. 1), separated by planes of the
doped A-site, which acts as a charge reservoir. So far, the maximum Tc is 38 K
Rotter:2008p8535  seen in Ba0.6K0.4Fe2As2, which is the compound we are
investigating in this letter. The antiferromagnetic structure of the undoped
parent compound, BaFe2As2 is illustrated in Figure 1 Huang:2008p8145 .

Polycrystalline samples of Ba0.6K0.4Fe2As2 were prepared by solid state
synthesis techniques described in the supplemental information. From XRD and
SEM/EDS measurements, the estimated phase purity of the samples is $\sim$90%
and a sharp superconducting transition was observed by magnetic susceptibility
at the previously reported temperature of 38 K Rotter:2008p8535 . The
inelastic neutron scattering experiments were performed on the recently
commissioned time-of-flight MERLIN spectrometer at the ISIS Pulsed Neutron and
Muon Facility Bewley:2006p11347 , using incident energies of 15, 30, 60, and
100 meV. The data were placed on an absolute intensity scale by normalization
to a vanadium standard.

Figure 2 shows colour plots of the measured inelastic neutron scattering
intensity as a function of momentum transfer, $Q$, and energy transfer,
$\omega$, at two incident neutron energies, 15 and 60 meV, below (T = 7 K) and
above (T = 50 K) the superconducting transition temperature. The range of data
is limited by the kinematics of the scattering process at these low scattering
angles so it is necessary to combine data from multiple incident energies in
order to access data over a reasonable range of energy transfers at such low
$Q$s.

The most striking difference between the scattering above and below Tc is seen
at Q$\sim$1.15 Å-1 and an energy transfer of $\sim$14 meV. At 7 K, there is
clearly a peak that is well-defined in both $Q$ and $\omega$ which is not
present at 50 K (Fig. 2a and 2b). Conversely, measurements at lower incident
energy show that above Tc, there is a column of scattering intensity as a
function of energy transfer, centred at $Q=1.15$ Å-1 (Fig. 2d), which is no
longer visible below Tc (Fig. 2c). The $Q$ characterizing these contributions
to the magnetic response corresponds to the periodicity of the
antiferromagnetic order within each plane of iron spins observed in the
undoped parent compound, BaFe2As2 Huang:2008p8145  (see also Fig. 1), so this
scattering is consistent with the persistence of antiferromagnetic
fluctuations in the absence of long-range spin order. Our measurements
indicate that these antiferromagnetic fluctuations condense into a sharp
resonant excitation, localized in both Q and $\omega$, as previously seen in
the cuprate and heavy fermion superconductors.

Figure 3: Inelastic neutron scattering from Ba0.6K0.4Fe2As2 integrated over a
Q-range of 1.0 to 1.3 Å-1 (a) at 7 K measured using incident neutron energies
of 15 meV (yellow circles), 30 meV (blue circles) and 60 meV (green circles),
and (b) at 7 K (green circles) and 50 K (red circles) using an incident
neutron energy of 60 meV. The error bars are derived from the square root of
the raw detector counts. The data show a clear resonant peak at 7 K and the
transfer of spectral weight from this peak to lower energies at 50 K, i.e.,
above the superconducting transition.

Before discussing this resonant excitation in more detail, we should mention
that there is also clear evidence for ferromagnetic fluctuations shown by the
additional band of excitations in Fig. 2c and 2d that disperses in Q and
$\omega$. The (Q,$\omega$)-dependence is consistent with the dispersion of
ferromagnetic spin waves emerging from Q = 0, flattening at the ferromagnetic
Brillouin zone boundary (which is equivalent to the antiferromagnetic zone
centre) at $\omega\sim 6$ meV. The existence of ferromagnetic fluctuations in
the undoped parent compound has been predicted theoretically Mazin:2008p6770 ,
although it was argued that they would be suppressed by doping before the
onset of superconductivity. We have also observed this mode in BaFe2As2 but it
is clear that they are still present in the superconducting phase although
there is some redistribution of intensity on crossing Tc. The strong intensity
of this mode, coupled with the intensity changes at Tc, indicate that it is
intrinsic to the bulk superconducting phase. We will discuss this aspect of
our data further in a future publication.

To elucidate the evolution of the magnetic response, we combine measurements
below Tc at three incident energies using, in each case, a low-energy cutoff
that excludes the tail of strong elastic nuclear scattering. The resulting
data are shown in Fig. 3a where the resonant excitation is seen to peak
sharply at $\omega_{0}\approx 14$ meV. We cannot rule out that there could be
a small phononic contribution to the scattering within this energy window, but
the strong temperature dependence indicates that it is predominantly magnetic.
A comparison of the data above and below Tc measured with an incident energy
of 60 meV shows that the spectral weight of the column of scattering evident
in Fig. 2d has transferred into the resonant peak in the superconducting
phase.

Figure 4: Inelastic neutron scattering from Ba0.6K0.4Fe2As2 as a function of
temperature integrated over a $Q$ range of 1.0 to 1.3 Å-1 and an energy
transfer range of 12.5 to 17.5 meV. The integration range corresponds to the
region of maximum intensity of the resonant excitation observed below Tc (see
Fig. 2). The error bars are derived from the square root of the raw detector
counts. The dashed line is a guide to the eye below Tc and shows the average
value of the integrals above Tc.

We performed a series of shorter measurements in order to determine the
temperature dependence of this resonant excitation. Fig. 4 shows data
integrated over the (Q,$\omega$)-region of maximum intensity in the resonant
excitation. As also observed in the cuprates, the intensity of the resonance
falls to zero at Tc confirming the strong coupling of this excitation to the
superconducting order parameter.

The existence of similar resonant excitations in other strongly correlated
superconductors, such as the high-Tc cuprates and the heavy fermion
superconductors, is commonly taken as evidence of an unconventional symmetry
of the superconducting order parameter Chang:2007p11651 . The dynamic magnetic
susceptibility is predicted to be enhanced at certain values of Q in the
superconducting phase by a coherence factor provided that the energy gap
symmetry has the following form:

$\Delta_{\textbf{k}+\textbf{Q}}=-\Delta_{\textbf{k}}$

where k and $\textbf{k}+\textbf{Q}$ are wavevectors on different parts of the
Fermi surface.

In the cuprates and heavy fermion superconductors, this is realized by
d${}_{x^{2}-y^{2}}$-symmetry, which has nodes in the energy gap within a
single Fermi surface. In these cases, Q spans sections of the same Fermi
surface that are gapped with opposite phase, such as $\textbf{Q}=(\pi,\pi)$ in
the cuprates. However, such a scenario seems to be ruled out by photoemission
results on Ba0.6K0.4Fe2As2 that show no evidence of any anisotropy of the
energy gap Ding:2008p8816 . According to band structure calculation, the Fermi
surfaces of the iron arsenide superconductors are predominantly derived from
the iron d-electrons, and comprise two small hole pockets centred at the
centre of the Brillouin zone and two small electron pockets at the zone
boundary Liu:2008p8202 ; Yang:2008p8157 . ARPES sees isotropic gaps around
each of the measured surfaces apparently ruling out a d-wave gap symmetry
Ding:2008p8816 .

A resolution of this apparent discrepancy has been provided by theoretical
predictions that the gap symmetry is not d-wave, but rather extended s±-wave
Mazin:2008p6770 . Mazin et al have postulated that the gaps in each hole and
electron pocket are isotropic, but that the gaps on the hole and electron
pockets have opposite phase. This means that magnetic fluctuations are
amplified by the coherence factor at values of Q that couple the hole and
electron pockets, as has been confirmed by explicit calculations of the
neutron scattering intensities Maier:2008p9552 . This is precisely where we
have observed the resonant excitation, so our measurements, combined with the
ARPES data, provide strong experimental support for the validity of extended
s±-wave gap models.

In conclusion, we have presented the first experimental evidence in the new
class of iron arsenide superconductors for the existence of a resonant
excitation in the dynamic magnetic susceptibility that disappears above the
superconducting transition temperature. The energy of this resonant excitation
is at $\omega_{0}\sim 14$ meV, or 4.3 Tc, just under the canonical value of 5
Tc seen in the cuprate superconductors Hufner:2008p9494 . However, Stock et al
have argued that it is more appropriate to scale $\omega_{0}/2\Delta_{0}$,
where $\Delta_{0}$ is the maximum value of the gap, and they estimate that
this ratio ranges from 0.62 to 0.74 in a wide range of materials
Stock:2008p6655 . From ARPES data on Ba0.6K0.4Fe2, $\Delta_{0}\sim 12$ meV
Ding:2008p8816 , giving a ratio of $\omega_{0}/2\Delta_{0}\sim 0.58$. It is
remarkable that materials with such a divergent range of Tcs (over two orders
of magnitude) could be unified by such a simple scaling relation.

###### Acknowledgements.

We acknowledge helpful scientific discussions with Christopher Stock. This
work was supported by the Division of Materials Sciences and Engineering
Division and the Scientific User Facilities Division of the Office of Basic
Energy Sciences, U.S. Department of Energy Office of Science, under Contract
Nos. DE-AC02-06CH11357 and DE-AC05-00OR22725. Correspondence and requests for
materials should be addressed to R. O.

## References

  * (1) Kamihara, Y., Watanabe, T., Hirano, M. & Hosono, H.  Iron-based layered superconductor La[O1-xFx]FeAs (x=0.05-0.12) with Tc=26 K.  _J Am Chem Soc_ 130, 3296–3297 (2008).
  * (2) Takahashi, H. _et al._ Superconductivity at 43 K in an iron-based layered compound LaO1-xFxFeAs.  _Nature_ 453, 376–378 (2008).
  * (3) Ren, Z.-A. _et al._ Superconductivity and phase diagram in iron-based arsenic-oxides (RE=rare-earth metal) without fluorine doping.  _Europhys. Lett._ 83, 17002 (2008).
  * (4) Rotter, M., Tegel, M. & Johrendt, D.  Superconductivity at 38 K in the iron arsenide (Ba1-xKx)Fe2As2.  _arXiv_ 0805.4630 (2008).
  * (5) Cruz, C. D. L. _et al._ Magnetic order close to superconductivity in the iron-based layered LaO1-xFxFeAs systems.  _Nature_ 453, 899–902 (2008).
  * (6) Norman, M. R.  High Temperature Superconductivity - Magnetic Mechanisms, vol. 5 p. 2671 of _Handbook of Magnetism and Advanced Magnetic Materials_ (Wiley, New York, 2007).
  * (7) Hüfner, S., Hossain, M. A., Damascelli, A. & Sawatzky, G. A.  Two gaps make a high-temperature superconductor?  _Rep. Prog. Phys._ 71, 062501 (2008).
  * (8) Stock, C., Broholm, C., Hudis, J., Kang, H. J. & Petrovic, C.  Spin Resonance in the d-Wave Superconductor CeCoIn5.  _Phys. Rev. Lett._ 100, 087001 (2008).
  * (9) Stockert, O. _et al._ Magnetism and superconductivity in the heavy-fermion compound CeCu2Si2 studied by neutron scattering.  _Physica B_ 403, 973–976 (2008).
  * (10) Sato, N. K. _et al._ Strong coupling between local moments and superconducting ‘heavy’ electrons in UPd2Al3.  _Nature_ 410, 340–343 (2001).
  * (11) Steglich, F. _et al._ Superconductivity in the Presence of Strong Pauli Paramagnetism: CeCu2Si2.  _Phys. Rev. Lett._ 43, 1892–1896 (1979).
  * (12) Rossat-Mignod, J. _et al._ Neutron scattering study of the YBa2Cu3O6+x system.  _Physica C_ 185, 86–92 (1991).
  * (13) Mook, H. A., Yethiraj, M., Aeppli, G., Mason, T. E. & Armstrong, T.  Polarized neutron determination of the magnetic excitations in YBa2Cu3O7.  _Phys Rev Lett_ 70, 3490–3493 (1993).
  * (14) Fong, H. F. _et al._ Neutron scattering from magnetic excitations in Bi2Sr2CaCu2O8+δ.  _Nature_ 398, 588–591 (1999).
  * (15) Dai, P., Mook, H. A., Aeppli, G., Hayden, S. M. & Doğan, F.  Resonance as a measure of pairing correlations in the high-Tc superconductor YBa2Cu3O6.6.  _Nature_ 406, 965–968 (2000).
  * (16) He, H. _et al._ Magnetic Resonant Mode in the Single-Layer High-Temperature Superconductor Tl2Ba2CuO6+δ.  _Science_ 295, 1045–1047 (2002).
  * (17) Mazin, I. I., Johannes, M. D., Boeri, L., Koepernik, K. & Singh, D. J.  Challenge of unravelling magnetic properties of LaFeAsO.  _arXiv_ 0806.1869 (2008).
  * (18) Huang, Q. _et al._ Magnetic order in BaFe2As2, the parent compound of the FeAs based superconductors in a new structural family.  _arXiv_ 0806.2776 (2008).
  * (19) Sasmal, K. _et al._ Superconductivity up to 37 K in (A1-xSrx)Fe2As2 with A=K and Cs.  _arXiv_ 0806.1301 (2008).
  * (20) Park, T. _et al._ Pressure-induced superconductivity in CaFe2As2.  _J. Phys.-Cond. Matt._ 20, 322204 (2008).
  * (21) Bewley, R. _et al._ MERLIN, a new high count rate spectrometer at ISIS.  _Physica B_ 385-386, 1029–1031 (2006).
  * (22) Mazin, I. I., Singh, D. J., Johannes, M. D. & Du, M. H.  Unconventional sign-reversing superconductivity in LaFeAsO1-xFx.  _arXiv_ 0803.2740 (2008).
  * (23) Chang, J., Eremin, I., Thalmeier, P. & Fulde, P.  Theory of magnetic excitons in the heavy-fermion superconductor UPd2Al3.  _Phys. Rev. B_ 75, 24503 (2007).
  * (24) Ding, H. _et al._ Fermi-surface–dependent nodeless superconducting gaps in Ba0.6K0.4Fe2As2.  _Europhys. Lett._ 83, 47001 (2008).
  * (25) Liu, C. _et al._ The Fermi surface of Ba1-xKxFe2As2 and its evolution with doping.  _arXiv_ 0806.3453 (2008).
  * (26) Yang, L. X. _et al._ Band structure and electronic signature of the spin density waves in bilayer iron-oxypnictide BaFe2As2.  _arXiv_ 0806.2627 (2008).
  * (27) Maier, T. A. & Scalapino, D. J.  Neutron scattering as a probe of the Fe-pnictide superconducting gap.  _arXiv_ 0805.0316 (2008).