# Convex optimization using quantum oracles

Joran van Apeldoorn  QuSoft, CWI, Amsterdam, the Netherlands<EMAIL_ADDRESS>András Gilyén  QuSoft, CWI, Amsterdam, the Netherlands<EMAIL_ADDRESS>Sander
Gribling  QuSoft, CWI, Amsterdam, the Netherlands<EMAIL_ADDRESS>Ronald de
Wolf  QuSoft, CWI and University of Amsterdam, the Netherlands<EMAIL_ADDRESS>
###### Abstract

We study to what extent quantum algorithms can speed up solving convex
optimization problems. Following the classical literature we assume access to
a convex set via various oracles, and we examine the efficiency of reductions
between the different oracles. In particular, we show how a separation oracle
can be implemented using $\widetilde{\mathcal{O}}\left(1\right)$ quantum
queries to a membership oracle, which is an exponential quantum speed-up over
the $\Omega(n)$ membership queries that are needed classically. We show that a
quantum computer can very efficiently compute an approximate subgradient of a
convex Lipschitz function. Combining this with a simplification of recent
classical work of Lee, Sidford, and Vempala gives our efficient separation
oracle. This in turn implies, via a known algorithm, that
$\widetilde{\mathcal{O}}\left(n\right)$ quantum queries to a membership oracle
suffice to implement an optimization oracle (the best known classical upper
bound on the number of membership queries is quadratic). We also prove several
lower bounds: $\Omega(\sqrt{n})$ quantum separation (or membership) queries
are needed for optimization if the algorithm knows an interior point of the
convex set, and $\Omega(n)$ quantum separation queries are needed if it does
not.

##  1 Introduction

Optimization is a fundamental problem in mathematics and computer science,
with many real-world applications. As people try to solve larger and larger
optimization problems, the efficiency of optimization becomes more and more
important, motivating us to find the best possible algorithms. Recent
experimental progress on building quantum computers draws attention to new
approaches to the problem: can we solve optimization problems more efficiently
by exploiting quantum effects such as superposition, interference, and
entanglement? For many discrete optimization problems [Gro96, DH96, Szeg04,
DHHM06, AŠ06] significant speed-ups have been shown, but less is known about
_continuous_ optimization problems.

One of the most successful continuous optimization paradigms is _convex_
optimization, which optimizes a convex function over a convex set that is
given explicitly (by a set of constraints) or implicitly (by an oracle). See
Bubeck [Bub15] for a recent survey. Quantum algorithms for convex optimization
have been considered before. In 2008, Jordan [Jor08] described a faster
quantum algorithm for minimizing quadratic functions. Recently, for an
important class of convex optimization problems (semidefinite optimization)
quantum speed-ups were achieved using algorithms whose runtime scales
polynomially with the desired precision and some geometric parameters [BS17,
vAGGdW17, BKL+19, vAG19]. However, many convex optimization problems can be
solved classically using algorithms whose runtime scales _logarithmically_
with the desired precision and the relevant geometric parameters. We are aware
of only one quantum speed-up which is partially in this regime, namely the
very recent quantum interior point method of Kerenidis and Prakash [KP18]. In
this paper we look at general convex optimization problems, considering
algorithms that have such favorable logarithmic scaling with the precision.

The generic problem in convex optimization is minimizing a convex function
$f:K\rightarrow\mathbb{R}\cup\\{\infty\\}$, where $K\subseteq\mathbb{R}^{n}$
is a convex set. We consider the setting where an interior point
$x_{0}\in\mathrm{int}(K)$ is given and radii $r,R>0$ are known such that
$B(x_{0},r)\subseteq K\subseteq B(x_{0},R)$, where $B(x_{0},r)$ is the
Euclidean ball of radius $r$ centered at $x_{0}$.

It is well-known that if the convex function is bounded on $K$, then we can
equivalently consider the problem of minimizing a _linear_ function over a
different convex set $K^{\prime}\subseteq\mathbb{R}^{n+1}$, namely the
epigraph $K^{\prime}=\\{(x,\mu):x\in K,f(x)\geq\mu\\}$ of $f$. Accessing
$K^{\prime}$ is easy given access to $K$ and $f$, and the parameters involved
will be similar. Conversely, for any linear optimization problem over an
unknown convex set $K$, there is an equivalent optimization problem over a
known convex set (say, the ball), with an unknown bounded convex objective
function $f$ that can be evaluated easily given access to $K$. From now on we
therefore focus on optimizing a known linear function over an unknown convex
set.

We consider the setting where access to the convex set is given only in a
black-box manner, through an oracle. The five basic problems (oracles) in
convex optimization identified by Grötschel, Lovász, and Schrijver [GLS88]
are: membership, separation, optimization, violation, and validity (see
Section 2 for the definitions). They showed that all five basic problems are
polynomial-time equivalent. That is, given an oracle $O$ for one of these
problems, one can implement an oracle for any of the other problems using a
polynomial number of calls to $O$ and polynomially many other elementary
operations. Subsequent work made these polynomial-time reductions more
efficient, reducing the degree of the polynomials. Recently Lee et al.
[LSV18], in the classical setting, showed that with
$\widetilde{\mathcal{O}}\left(n^{2}\right)$ calls111Here, and in the rest of
the paper, the notation $\widetilde{\mathcal{O}}\left(\cdot\right)$ is used to
hide polylogarithmic factors in $n,r,R,\varepsilon$. to a membership oracle
(and $\widetilde{\mathcal{O}}\left(n^{3}\right)$ other elementary arithmetic
operations) one can solve an optimization problem. They did so by showing that
$\widetilde{\mathcal{O}}\left(n\right)$ calls to a membership oracle suffice
to do separation, and then composing this with the known fact [LSW15] (see
also [LSV18, Theorem 15]) that $\widetilde{\mathcal{O}}\left(n\right)$ calls
to a separation oracle suffice for optimization.

Our main result (Section 4) shows that on a quantum computer,
$\widetilde{\mathcal{O}}\left(1\right)$ calls to a membership oracle suffice
to implement a separation oracle, and hence (by the known classical reduction
from optimization to separation) $\widetilde{\mathcal{O}}\left(n\right)$ calls
to a membership oracle suffice for optimization.222Although not stated
explicitly in our results, we also use
$\widetilde{\mathcal{O}}\left(n^{3}\right)$ additional operations for
optimization using membership, like [LSV18]. This is because our quantum
algorithm for separation uses only $\widetilde{\mathcal{O}}\left(n\right)$
gates in addition to the $\widetilde{\mathcal{O}}\left(1\right)$ membership
queries, and we use the same reduction from optimization to separation as
[LSV18]. If queries themselves have significant time complexity, then our
algorithm does lead to a speedup in time complexity over the best known
classical algorithm. For example, if each membership query (with the required
precision) takes time $\widetilde{\mathcal{O}}\left(n^{2}\right)$ to
implement, then our quantum algorithm for optimization has time complexity
$\widetilde{\mathcal{O}}\left(n^{3}\right)$, while the classical algorithm
will use time $\widetilde{\mathcal{O}}\left(n^{4}\right)$ because it uses
$\widetilde{\mathcal{O}}\left(n^{2}\right)$ membership queries. Lee et al.
[LSV18] use a geometric idea to reduce separation to finding an approximate
subgradient of a convex Lipschitz function. They then show that
$\widetilde{\mathcal{O}}\left(n\right)$ evaluations of a convex Lipschitz
function suffice to get an approximate subgradient. Our contributions here are
twofold (Section 3 and 4). We use the same geometric idea, but we provide a
simpler way to compute an approximate subgradient of a convex Lipschitz
function (Section 3). We point out that this new algorithm is purely
classical. Besides being simpler, the main advantage of our algorithm is that
it is suitable for a quantum speed-up using known quantum algorithms (Jordan’s
algorithm) for computing approximate (sub)gradients [Jor05, GAW19], which we
show in Section 4. To show our quantum speed-up, we have to extend Jordan’s
quantum algorithm for gradient-computation to the case of convex Lipschitz
functions.

As a second set of results, in Section 5 we provide lower bounds on the number
of membership or separation queries needed to implement several other oracles.
We show that our quantum reduction from separation to membership indeed
improves over the best possible classical reduction: $\Omega(n)$ classical
membership queries are needed to do separation.333We are not aware of an
existing proof of this classical lower bound, but it may well be somewhere in
the vast literature on convex optimization. We only have partial results
regarding the optimality of the reduction from optimization to separation. In
the setting where we are not given an interior point of the set $K$, we can
prove an essentially optimal $\Omega(n)$ lower bound on the number of quantum
queries to a separation oracle needed to do optimization, using the general
adversary bound. This lower bound implies that a quantum computer offers no
query speed-up over a classical computer for the task of finding an interior
point.

However, for the case of quantum algorithms that _do_ know an interior point,
we are only able to prove an $\Omega(\sqrt{n})$ lower bound. In the classical
setting, regardless of whether or not we know an interior point, the reduction
uses $\widetilde{\Theta}(n)$ queries. This raises the interesting question of
whether knowing an interior point can lead to a better quantum algorithm. We
therefore view closing the gap between upper and lower bound as an important
direction for future work.

Finally, we briefly mention (Section 6) how to obtain upper and lower bounds
for some of the other oracle reductions, using a convex polarity argument. As
we show, in the setting where we are given an interior point, the relation
between membership and separation is analogous to the relation between
validity and optimization. In particular, our better quantum algorithm for
separation using membership queries implies that on a quantum computer
$\widetilde{\mathcal{O}}\left(1\right)$ queries to a validity oracle suffice
to implement an optimization oracle. That is, on a quantum computer, finding
the optimal value is equivalent to finding an optimizer. Also, the same
polarity argument shows that algorithms for optimization using separation are
essentially equivalent to algorithms for separation using optimization. In
particular, this turns our lower bound on the number of separation queries
needed to implement an optimization oracle into a lower bound on the reverse
direction.

$\mathrm{MEM}(K)$ $\mathrm{SEP}(K)$ $\mathrm{OPT}(K)$ $\mathrm{VAL}(K)$
Classical:$\widetilde{\Theta}(n)$$\Theta(1)$$\widetilde{\Theta}(n)$$\widetilde{\Theta}(n)$$\Theta(1)$$\widetilde{\Theta}(n)$

$\mathrm{MEM}(K)$ $\mathrm{SEP}(K)$ $\mathrm{OPT}(K)$ $\mathrm{VAL}(K)$
Quantum:$\boldsymbol{\widetilde{\Theta}(1)}$$\Theta(1)$
$\phantom{,}\widetilde{\mathcal{O}}\left(n\right)$
$\phantom{,}\boldsymbol{\Omega(n)^{*}}\kern-28.45274pt$
$\boldsymbol{\Omega(\sqrt{n})}$
$\widetilde{\mathcal{O}}\left(n\right)$$\Theta(1)$$\boldsymbol{\widetilde{\Theta}(1)}$

Figure 1: The top and bottom diagram illustrate the relations between the
basic (weak) oracles for respectively classical and quantum queries, with
boldface entries marking our new results. All upper and lower bounds hold in
the setting where we know an interior point of $K$, except the $*$-marked
$\Omega(n)$ lower bound on the number of separation queries needed for
optimization. Notice the central symmetry of the diagrams, which is a
consequence of polarity.

Figure 1 gives an informal presentation of our results; the upper bounds arise
from oracle reductions, the (change in) accuracy is ignored here for
simplicity. The above-mentioned polarity manifests itself in the central
symmetry of the figure.

#### Related independent work.

In independent simultaneous work, Chakrabarti, Childs, Li, and Wu [CCLW18]
discovered a similar upper bound as ours: combining the recent classical work
of Lee et al. [LSV18] with a quantum algorithm for computing gradients, they
show how to implement an optimization oracle via
$\widetilde{\mathcal{O}}\left(n\right)$ quantum queries to a membership oracle
and to an oracle for the objective function. Their proof stays quite close to
[LSV18] while ours first simplifies some of the technical lemmas of [LSV18],
giving us a slightly simpler presentation and a better error-dependence of the
resulting algorithm. They also prove several lower bounds that are similar to
the ones we prove here.

##  2 Preliminaries

We use $[n]:=\\{1,2,\ldots,n\\}$. For $p\geq 1$, $\varepsilon\geq 0$, and a
set $C\subseteq\mathbb{R}^{n}$ we let

$B_{p}(C,\varepsilon)=\\{x\in\mathbb{R}^{n}:\exists y\in C\text{ such that
}||x-y||_{p}\leq\varepsilon\\}$

be the set of points of distance at most $\varepsilon$ from $C$ in the
$\ell_{p}$-norm. When $C=\\{x\\}$ is a singleton set we abuse notation and
write $B_{p}(x,\varepsilon)$. We overload notation by setting

$B_{p}(C,-\varepsilon)=\\{x\in\mathbb{R}^{n}:B_{p}(x,\varepsilon)\subseteq
C\\}.$

Whenever $p$ is omitted it is assumed that $p=2$.

Recall that a function $f:C\rightarrow\mathbb{R}$ is _Lipschitz_ if there
exists a constant $L>0$ such that

$\left|f(y^{\prime})-f(y)\right|\leq L\left\lVert
y^{\prime}-y\right\rVert_{2}\text{ for all }y,y^{\prime}\in C.$

We write that $f$ is _$L$ -Lipschitz_. The inner product between vectors
$v,w\in\mathbb{R}^{n}$ is $\left\langle v,w\right\rangle=v^{T}w$.

######  Definition 1 (Subgradient).

Let $C\subseteq\mathbb{R}^{n}$ be convex and let $x$ be an element of the
interior of $C$. For a convex function $f:C\rightarrow\mathbb{R}$ we denote by
$\underline{\partial}f(x)$ the set of subgradients of $f$ at $x$, i.e., those
vectors $g$ satisfying

$f(y)\geq f(x)+\left\langle g,y-x\right\rangle\text{ for all }y\in C.$

Note that in the above definition $\underline{\partial}f(x)\neq\emptyset$ due
to convexity.

If $f:C\rightarrow\mathbb{R}$ is $L$-Lipschitz, then for any $x$ in the
interior of $C$ and any $g\in\underline{\partial}f(x)$ we have $\left\lVert
g\right\rVert\leq L$, as follows. Consider a $y\in C$ such that $y-x=\alpha g$
for some $\alpha>0$. Then since $g$ is a subgradient of $f$ at $x$ we have

$\alpha\left\lVert g\right\rVert^{2}=\left\langle g,y-x\right\rangle\leq
f(y)-f(x)\leq L\left\lVert y-x\right\rVert=\alpha L\left\lVert g\right\rVert,$
(1)

and therefore $\left\lVert g\right\rVert\leq L$.

We will assume familiarity with quantum computing [NC00]. In particular, a
standard quantum oracle corresponds to a unitary transformation that acts on
two (finite-dimensional) registers, where the first register contains the
query and the answer is added to the second register. For example, a function
evaluation oracle for $f\colon X\rightarrow Y$ would map $|x,0\rangle$ to
$|x,f(x)\rangle$, where $|x\rangle$ and $|f(x)\rangle$ are basis states
corresponding to binary representations of $x$ and $f(x)$ respectively. Unlike
classical algorithms, quantum computers can apply such an oracle to a
_superposition_ of different $y$’s. They are also allowed to apply the inverse
of a unitary oracle.

The standard quantum oracle described above models problems where there is a
single correct answer to a query. When there are multiple good answers (for
instance, different good approximations to the correct value) and the oracle
is only required to give a correct answer with high probability, then we will
work with the more liberal notion of _relational_ quantum oracles.

######  Definition 2 (Relational quantum oracle).

Let $\mathcal{F}\colon X\rightarrow\mathcal{P}(Y)$ be a function, such that
for each $x\in X$ the subset $\mathcal{F}(x)\subseteq Y$ is the set of valid
answers to an $x$ query. A relational quantum oracle for $\mathcal{F}$ which
answers queries with success probability $\geq 1-\rho$, is a unitary that for
all $x\in X$ maps

$U\colon|x,0,0\rangle\mapsto\sum_{y\in Y}\alpha_{x,y}|x,y,\psi_{x,y}\rangle,$

where $|\psi_{x,y}\rangle$ denotes some normalized quantum state and
$\sum_{y\in\mathcal{F}(x)}|\alpha_{x,y}|^{2}\geq 1-\rho$. Thus measuring the
second register of $U|x,0,0\rangle$ gives a valid answer to the $x$ query with
probability at least $1-\rho$.

This definition is very natural for cases where the oracle is implemented by a
quantum algorithm that produces a valid answer with probability $\geq 1-\rho$.
In order to achieve our quantum speed-ups we will always assume access to the
inverse $U^{\dagger}$ of the relational oracle as well, which is justified if
$U$ comes from an efficiently implementable quantum algorithm.

###  2.1 Oracles for convex sets

The five basic oracles for a convex set $K$ that we consider are as follows
(in contrast with the original [GLS88], we allow some error probability $\rho$
in these oracles as in [LSV18]). Throughout we will assume that real vectors
are represented with $\mathrm{polylog}(nR/(r\varepsilon))$ bits of precision
per coordinate. In particular, we assume that the input / output of the
following oracles is represented this way.444Note that for weak oracles, where
$\varepsilon>0$, this is essentially without loss of generality, since the
rounding errors can be incorporated into the error parameter of the oracle.

######  Definition 3 (Membership oracle $\mathrm{MEM}_{\varepsilon,\rho}(K)$).

Queried with a vector $y\in\mathbb{R}^{n}$, the oracle, with success
probability $\geq 1-\rho$, correctly asserts one of the following

  * •

$y\in B(K,\varepsilon)$, or

  * •

$y\not\in B(K,-\varepsilon)$.

######  Definition 4 (Separation oracle $\mathrm{SEP}_{\varepsilon,\rho}(K)$).

Queried with a vector $y\in\mathbb{R}^{n}$, the oracle, with success
probability at least $\geq 1-\rho$, correctly asserts one of the following

  * •

$y\in B(K,\varepsilon)$, or

  * •

$y\not\in B(K,-\varepsilon)$,

and in the second case it returns a unit vector $g\in\mathbb{R}^{n}$ such that
$\langle g,x\rangle\leq\langle g,y\rangle+\varepsilon$ for all $x\in
B(K,-\varepsilon)$.

######  Definition 5 (Optimization oracle
$\mathrm{OPT}_{\varepsilon,\rho}(K)$).

Queried with a unit vector $c\in\mathbb{R}^{n}$, the oracle, with probability
$\geq 1-\rho$, does one of the following:

  * •

it returns a vector $y\in\mathbb{R}^{n}$ such that $y\in B(K,\varepsilon)$ and
$\left\langle c,x\right\rangle\leq\left\langle c,y\right\rangle+\varepsilon$
for all $x\in B(K,-\varepsilon)$,

  * •

or it correctly asserts that $B(K,-\varepsilon)$ is empty.

Note that the above optimization oracle corresponds to _maximizing_ a linear
function over a convex set; we could equally well state it for minimization.

######  Definition 6 (Violation oracle $\mathrm{VIOL}_{\varepsilon,\rho}(K)$).

Queried with a unit vector $c\in\mathbb{R}^{n}$ and a real number $\gamma$,
the oracle, with probability $\geq 1-\rho$, does one of the following:

  * •

it asserts that $\left\langle c,x\right\rangle\leq\gamma+\varepsilon$ for all
$x\in B(K,-\varepsilon)$,

  * •

or it finds a vector $y\in B(K,\varepsilon)$ such that $\left\langle
c,y\right\rangle\geq\gamma-\varepsilon$.

######  Definition 7 (Validity oracle $\mathrm{VAL}_{\varepsilon,\rho}(K)$).

Queried with a unit vector $c\in\mathbb{R}^{n}$ and a real number $\gamma$,
the oracle, with probability $\geq 1-\rho$, does one of the following:

  * •

it asserts that $\left\langle c,x\right\rangle\leq\gamma+\varepsilon$ for all
$x\in B(K,-\varepsilon)$,

  * •

or it asserts that $\left\langle c,y\right\rangle\geq\gamma-\varepsilon$ for
some $y\in B(K,\varepsilon)$.

If in the above definitions both $\varepsilon$ and $\rho$ are equal to $0$,
then we call the oracle _strong_. If either is non-zero then we sometimes call
it _weak_.

The above describes the classical oracles, and the quantum oracles are defined
analogously, i.e., they are relational quantum oracles (see Definition 2),
that use a binary representation for the input / output vectors.

When we discuss membership queries, we will always assume that we are given a
small ball which lies inside the convex set. It is easy to see that without
such a small ball one cannot obtain an optimization oracle using only
$\mathrm{poly}(n)$ classical queries to a membership oracle (see, e.g.,
[GLS88, Sec. 4.1] or the example below). As the following example shows, the
same holds for quantum queries. We will use a reduction from a version of the
well-studied _search_ problem:

_Given $z\in\\{0,1\\}^{N}$ such that $|z|=1$, find $b\in[N]$ such that
$z_{b}=1$._

It is not hard to see that if the access to $z$ is given via classical queries
$i\mapsto z_{i}$, then $\Omega(N)$ queries are needed. It is well known
[BBBV97] that if we allow quantum queries, i.e., applications of the unitary
$|i\rangle|b\rangle\mapsto|i\rangle|z_{i}\oplus b\rangle$, then
$\Omega(\sqrt{N})$ queries are needed. Now let $N=2^{n}$ and consider an input
$z\in\\{0,1\\}^{N}$ to the search problem. Let $b\in\\{0,1\\}^{n}$ be the
index such that $z_{b}=1$. Consider maximizing the linear function $\langle
e,z\rangle$ (where $e$ is the all-1 vector) over the set
$K_{z}=\prod_{i=1}^{n}[b_{i}-1/2,b_{i}]$. Clearly the optimal solution to this
convex optimization problem, even with a small constant additive error in the
answer, gives the solution to the search problem. However, a membership query
is essentially equivalent to querying a bit of $z$ and therefore
$\Omega(\sqrt{N})=\Omega(2^{n/2})$ quantum queries to the membership oracle
are needed for optimization.

##  3 Computing approximate subgradients of convex Lipschitz functions

Here we show how to compute an approximate subgradient (at $0$) of a convex
Lipschitz function. That is, given a convex set $C$ such that
$0\in\mathrm{int}(C)$ and a convex function $f:C\rightarrow\mathbb{R}$, we
show how to compute a vector $\tilde{g}\in\mathbb{R}^{n}$ such that $f(y)\geq
f(0)+\langle\tilde{g},y\rangle-a\left\lVert y\right\rVert-b$ for some real
numbers $a,b>0$ that will be defined later (see Lemma 12 and Lemma 18). The
idea of the classical algorithm given in the next section is to pick a point
$z\in B_{\infty}(0,r_{1})$ uniformly at random and use the finite difference
$\nabla^{(r_{2})}f(z)$ (defined below) as an approximate subgradient of $f$ at
$0$; the radii $r_{1}$ and $r_{2}$ need to be chosen small to make the
approximation good. This results in a slightly simplified version of the
algorithm of Lee et al. [LSV18]. In Section 3.2 we show how to improve on this
classical algorithm on a quantum computer.

###  3.1 Classical approach

In the discussion that follows we will use the following approximation of the
gradient.

######  Definition 8 (Finite-difference gradient approximation).

For a function $f:C\rightarrow\mathbb{R}$, a real $r>0$, and a point
$x\in\mathbb{R}^{n}$ such that $B_{1}(x,r)\subseteq C$, and $i\in[n]$, we
define

$\nabla_{i}^{(r)}f(x):=\frac{f(x+re_{i})-f(x-re_{i})}{2r},$

where $e_{i}\in\\{0,1\\}^{n}$ is the vector that has a 1 only in its $i$th
coordinate. Similarly we define

$\nabla^{(r)}f(x):=\left(\nabla_{1}^{(r)}f(x),\nabla_{2}^{(r)}f(x),\ldots,\nabla_{n}^{(r)}f(x)\right).$

We will also consider a similar approximation of the Laplacian (the trace of
the Hessian) of a function.

######  Definition 9 (Finite-difference Laplace approximation).

For a function $f:C\rightarrow\mathbb{R}$, a real $r>0$, and a point
$x\in\mathbb{R}^{n}$ such that $B_{1}(x,r)\subseteq C$, and $i\in[n]$, we
define

$\Delta_{i}^{\\!\\!(r)}f(x):=\frac{f(x+re_{i})-2f(x)+f(x-re_{i})}{r^{2}}.$

Similarly

$\Delta^{\\!\\!(r)}f(x):=\sum_{i=1}^{n}\Delta_{i}^{\\!\\!(r)}f(x).$

Note that for a convex function we have $\Delta_{i}^{\\!\\!(r)}f(x)\geq 0$ for
all $x$ such that $B_{1}(x,r)\subseteq C$.

The next two lemmas will be needed in the proof of the main result of this
section, Lemma 12. In Lemma 10 we give an upper bound on the deviation
$\left\lVert g-\nabla^{(r_{2})}f(z)\right\rVert_{1}$ of a finite difference
gradient approximation $\nabla^{(r_{2})}f(z)$ from an actual subgradient $g$
at the point $z$, in terms of the finite difference Laplace approximation
$\Delta^{\\!\\!(r_{2})}f(z)$. Then, in Lemma 11 we show that in expectation
(over the points of a small ball around $x$), the finite difference Laplace
approximation is small. Together with Markov’s inequality this gives us good
control over the quality of a finite difference gradient approximation.

######  Lemma 10.

If $r_{2}>0$, $z\in\mathbb{R}^{n}$, and
$f:B_{1}(z,r_{2})\rightarrow\mathbb{R}$ is convex, then

$\sup_{g\in\underline{\partial}f(z)}\left\lVert
g-\nabla^{(r_{2})}f(z)\right\rVert_{1}\leq\frac{r_{2}\Delta^{\\!\\!(r_{2})}f(z)}{2}.$

###### Proof.

Fix a $g\in\underline{\partial}f(z)$. For every $i\in[n]$, we have
$f(z+r_{2}e_{i})\geq f(z)+\langle g,r_{2}e_{i}\rangle=f(z)+r_{2}g_{i}$, and,
similarly, $f(z-r_{2}e_{i})\geq f(z)-r_{2}g_{i}$. Rearranging gives

$\underbrace{\frac{f(z)-f(z-r_{2}e_{i})}{r_{2}}}_{:=A}\leq
g_{i}\leq\underbrace{\frac{f(z+r_{2}e_{i})-f(z)}{r_{2}}}_{:=B}.$

Note that $|g_{i}-\frac{A+B}{2}|\leq\frac{B-A}{2}$ for any three real numbers
$A\leq g_{i}\leq B$. Moreover, $\frac{A+B}{2}=\nabla_{i}^{(r_{2})}f(z)$ and
$B-A=r_{2}\Delta_{i}^{\\!\\!(r_{2})}f(z)$, thus
$\left|g_{i}-\nabla_{i}^{(r_{2})}f(z)\right|\leq\frac{r_{2}\Delta_{i}^{\\!\\!(r_{2})}f(z)}{2}$.
Now we can finish the proof by summing this inequality over all $i\in[n]$. ∎

######  Lemma 11.

If $0<r_{2}\leq r_{1}$, and $f:B_{\infty}(x,r_{1}+r_{2})\rightarrow\mathbb{R}$
is convex and $L$-Lipschitz, then

$\underset{z\in
B_{\infty}(x,r_{1})}{\mathbb{E}}\Delta^{\\!\\!(r_{2})}f(z)\leq\frac{nL}{r_{1}}.$

###### Proof.

Below we show that $\underset{z\in
B_{\infty}(x,r_{1})}{\mathbb{E}}\Delta_{i}^{\\!\\!(r_{2})}f(z)\leq\frac{L}{r_{1}}$
for all $i\in[n]$, summing over $i$ then proves the lemma.

Let $h_{i}(z):=f(z-r_{2}e_{i})-f(z)$; we have that

$\displaystyle\underset{z\in
B_{\infty}(x,r_{1})}{\mathbb{E}}\Delta_{i}^{\\!\\!(r_{2})}f(z)$
$\displaystyle=\frac{1}{(2r_{1})^{n}}\int_{z\in
B_{\infty}(x,r_{1})}\frac{f(z+r_{2}e_{i})-2f(z)+f(z-r_{2}e_{i})}{r^{2}_{2}}\,dz$
$\displaystyle=\frac{1}{(2r_{1})^{n}}\int_{\begin{subarray}{c}z_{j}\in[x_{j}-r_{1},x_{j}+r_{1}],\\\
j\in[n],j\neq
i\end{subarray}}\int_{z_{i}\in[x_{i}-r_{1},x_{i}+r_{1}]}\frac{f(z-r_{2}e_{i})-2f(z)+f(z+r_{2}e_{i})}{r^{2}_{2}}\,dz$
$\displaystyle=\frac{1}{(2r_{1})^{n}}\int_{\begin{subarray}{c}z_{j}\in[x_{j}-r_{1},x_{j}+r_{1}],\\\
j\in[n],j\neq
i\end{subarray}}\Big{(}\int_{z_{i}\in[x_{i}-r_{1},x_{i}+r_{1}]}\frac{h_{i}(z)}{r^{2}_{2}}\,dz$
$\displaystyle\qquad\qquad\qquad\qquad\quad\qquad-\int_{z_{i}\in[x_{i}-r_{1},x_{i}+r_{1}]}\frac{h_{i}(z+r_{2}e_{i})}{r^{2}_{2}}\,dz\Big{)}$
$\displaystyle=\frac{1}{(2r_{1})^{n}}\int_{\begin{subarray}{c}z_{j}\in[x_{j}-r_{1},x_{j}+r_{1}],\\\
j\in[n],j\neq
i\end{subarray}}\Big{(}\int_{z_{i}\in[x_{i}-r_{1},x_{i}+r_{1}]}\frac{h_{i}(z)}{r^{2}_{2}}\,dz$
$\displaystyle\qquad\qquad\qquad\qquad\quad\qquad-\int_{z_{i}\in[x_{i}-r_{1}+r_{2},x_{i}+r_{1}+r_{2}]}\frac{h_{i}(z)}{r^{2}_{2}}\,dz\Big{)}$
$\displaystyle=\frac{1}{(2r_{1})^{n}}\int_{\begin{subarray}{c}z_{j}\in[x_{j}-r_{1},x_{j}+r_{1}],\\\
j\in[n],j\neq
i\end{subarray}}\Big{(}\int_{z_{i}\in[x_{i}-r_{1},x_{i}-r_{1}+r_{2}]}\frac{h_{i}(z)}{r^{2}_{2}}\,dz$
$\displaystyle\qquad\qquad\qquad\qquad\quad\qquad-\int_{z_{i}\in[x_{i}+r_{1},x_{i}+r_{1}+r_{2}]}\frac{h_{i}(z)}{r^{2}_{2}}\,dz\Big{)}$
$\displaystyle\leq\frac{1}{(2r_{1})^{n}}\int_{\begin{subarray}{c}z_{j}\in[x_{j}-r_{1},x_{j}+r_{1}],\\\
j\in[n],j\neq i\end{subarray}}2L\,dz$ $\displaystyle=\frac{L}{r_{1}}.$

The last inequality above follows from multiplying the upper bound $r_{2}L$ on
$|h_{i}|$ with the length $r_{2}$ of the integration intervals. ∎

Note that the above lemma is stated and proved for continuous random
variables, but the same proof holds if we have a uniform hypergrid over the
same hypercube, providing a discrete version of the above result. In the
discrete case, in order to get the same cancellations we need to assume that
both $r_{1}$ and $r_{2}$ are integer multiples of the grid spacing.

We are now ready to prove the main result of this section. Informally, the
next lemma proves that an approximate subgradient of a convex Lipschitz
function $f$ at $0$ can be obtained by an algorithm that outputs
$\nabla^{(r_{2})}\tilde{f}(z)$ for a random $z$ close enough to $0$, where
$\tilde{f}$ is an approximate version of $f$. In other words, this lemma gives
us a classical algorithm to compute an approximate subgradient of $f$ using
$2n$ classical queries to an approximate version of $f$.

######  Lemma 12.

Let $r_{1}>0$, $L>0$, $\rho\in(0,1/3]$, $\delta\in(0,r_{1}\sqrt{n}L/\rho]$,
then $r_{2}:=\sqrt{\frac{\delta r_{1}\rho}{\sqrt{n}L}}\leq r_{1}$. Suppose
$f:C\to\mathbb{R}$ is a convex function that is $L$-Lipschitz on
$B_{\infty}(0,2r_{1})$, and $\tilde{f}:B_{\infty}(0,2r_{1})\to\mathbb{R}$ is
such that $\left\lVert\tilde{f}-f\right\rVert_{\infty}\leq\delta$. Then for a
uniformly random $z\in B_{\infty}(0,r_{1})$, with probability at least
$1-\rho$,

$f(y)\geq
f(0)+\left\langle\nabla^{(r_{2})}\tilde{f}(z),y\right\rangle-\frac{3n^{\frac{3}{4}}}{2}\sqrt{\frac{\delta
L}{\rho r_{1}}}\left\lVert y\right\rVert-2L\sqrt{n}r_{1}\qquad\text{for all
}y\in C.$

###### Proof.

Let $z\in B_{\infty}(0,r_{1})$ and $g\in\underline{\partial}f(z)$. Recall
$\left\lVert g\right\rVert\leq L$ by Equation (1). Then for all $y\in C$

$\displaystyle f(y)$ $\displaystyle\geq f(z)+\langle g,y-z\rangle$
$\displaystyle=f(z)+\langle
g,y-z\rangle+\left(\left\langle\nabla^{(r_{2})}f(z),y\right\rangle-\left\langle\nabla^{(r_{2})}f(z),y\right\rangle\right)+\left(f(0)-f(0)\right)$
$\displaystyle=f(0)+\left\langle\nabla^{(r_{2})}f(z),y\right\rangle+\langle
g-\nabla^{(r_{2})}f(z),y\rangle+(f(z)-f(0))+\langle g,-z\rangle$
$\displaystyle\geq
f(0)+\left\langle\nabla^{(r_{2})}f(z),y\right\rangle-\left\lVert
g-\nabla^{(r_{2})}f(z)\right\rVert_{1}\left\lVert
y\right\rVert_{\infty}-L\left\lVert z\right\rVert-\left\lVert
g\right\rVert\left\lVert z\right\rVert$ $\displaystyle\geq
f(0)+\left\langle\nabla^{(r_{2})}f(z),y\right\rangle-\left\lVert
g-\nabla^{(r_{2})}f(z)\right\rVert_{1}\left\lVert
y\right\rVert_{\infty}-L\sqrt{n}r_{1}-L\sqrt{n}r_{1}$ $\displaystyle\geq
f(0)+\left\langle\nabla^{(r_{2})}\tilde{f}(z),y\right\rangle-\frac{\delta\sqrt{n}}{r_{2}}\left\lVert
y\right\rVert-\left\lVert g-\nabla^{(r_{2})}f(z)\right\rVert_{1}\left\lVert
y\right\rVert_{\infty}-2L\sqrt{n}r_{1}.$

Note that in the last line we switched from $f$ to $\tilde{f}$, using that
$\nabla^{(r_{2})}f(z)$ and $\nabla^{(r_{2})}\tilde{f}(z)$ differ by at most
$\delta/r_{2}$ in each coordinate. Our choice of $r_{2}$ gives
$\frac{\delta\sqrt{n}}{r_{2}}=n^{\frac{3}{4}}\sqrt{\frac{\delta L}{\rho
r_{1}}}$ and by Lemma 10–11 we have

$\underset{z\in B_{\infty}(x,r_{1})}{\mathbb{E}}\left\lVert
g-\nabla^{(r_{2})}f(z)\right\rVert_{1}\leq\frac{nLr_{2}}{2r_{1}}=\frac{n^{\frac{3}{4}}}{2}\sqrt{\frac{\delta
L\rho}{r_{1}}}.$

By Markov’s inequality we get that $\left\lVert
g-\nabla^{(r_{2})}f(z)\right\rVert_{1}\leq\frac{n^{\frac{3}{4}}}{2}\sqrt{\frac{\delta
L}{\rho r_{1}}}$ with probability $\geq 1-\rho$ over the choice of $z$.
Plugging this bound on $\left\lVert g-\nabla^{(r_{2})}f(z)\right\rVert_{1}$
into the above lower bound on $f(y)$ concludes the proof of the lemma. ∎

###  3.2 Quantum improvements

In this section we show how to improve subgradient computation of convex
functions via Jordan’s quantum algorithm for gradient computation [Jor05]. We
use the formulation given by Gilyén et al. [GAW19, Lemma 20], for which we
first introduce the following definition.

######  Definition 13 (Hyper-grid).

For $k\in\mathbb{N}$ we define the following discretization of the interval
$(-1/2,1/2)$:

$G_{k}:=\left\\{\frac{j}{2^{k}}-\frac{1}{2}+2^{-k-1}:j\in\\{0,\ldots,2^{k}-1\\}\right\\}\leavevmode\nobreak\
\subset\leavevmode\nobreak\ (-1/2,1/2).$

Similarly we define the $n$-dimensional hyper-grid $G^{n}_{k}$, which is the
$n$-fold Cartesian product of $G_{k}$ with itself.

Note that an element of $G_{k}^{n}$ can be represented using $n\times k$
(qu)bits. Basically, Jordan’s algorithm just sets up a uniform superposition
over all grid points, applies a “phase query” to $f$, and then a quantum
Fourier transform over each coordinate.

######  Lemma 14.

(Jordan’s quantum gradient computation algorithm [GAW19, Lemma 20])
Let $m\in\mathbb{N}$, $c\in\mathbb{R}$ and $g\in\mathbb{R}^{n}$ such that
$\left\lVert g\right\rVert_{\infty}\leq 1/3$. If $h:G_{m}^{n}\to\mathbb{R}$ is
such that

$\left|h(x)-\left\langle g,x\right\rangle-c\right|\leq\frac{2^{-m}}{42\pi},$
(2)

for 99.9% of the points $x\in G_{m}^{n}$, then using a single query to a phase
oracle $\mathrm{O}\colon|x\rangle\mapsto e^{2\pi i2^{m}h(x)}|x\rangle$
Jordan’s gradient computation algorithm outputs a vector $v\in\mathbb{R}^{n}$
such that:

$\Pr\left[|v_{i}-g_{i}|>\\!2^{2-m}\right]\leq 1/3\quad\text{ for every
}i\in[n].$

We now show that the above algorithm allows us to compute an approximate
subgradient of a function $f$, even if we are only given standard oracle
access to a function $\tilde{f}$ which is sufficiently close to $f$. In
particular, we will assume we are given access to a standard unitary oracle of
a function $\tilde{f}\colon G_{m}^{n}\to\mathbb{R}$ which satisfies
$|\tilde{f}(x)-f(x)|\leq\delta$ for all $x\in G_{m}^{n}$. That is, we assume
we are given access to a unitary $U$ acting as

$U:|x\rangle|0\rangle\mapsto|x\rangle|\tilde{f}(x)\rangle$ (3)

Note that if we can classically efficiently evaluate $\tilde{f}$, then it is
well known that we can construct such a unitary as a small quantum circuit
(see [NC00, Sec. 1.4.1]).

The main idea is that, using one application of $U$, a phase gate
corresponding to the output register, and another application of $U^{\dagger}$
to uncompute the function value, we can implement a phase oracle for
$\tilde{f}$. Moreover, Equation (4) below will also hold for $\tilde{f}$, with
a slightly worse right-hand side, since $f$ is close to $\tilde{f}$. A version
of the following is proven in [GAW19, Theorem 21], for completeness we sketch
a proof.

######  Corollary 15 (Gradient computation using approximate function
evaluation).

Let $\delta,B,r\in\mathbb{R}_{+},c\in\mathbb{R}$, $\rho\in(0,1/3]$. Let
$x_{0},g\in\mathbb{R}^{n}$ with $\left\lVert
g\right\rVert_{\infty}\leq\frac{B}{r}$. Let
$m:=\left\lceil\log_{2}\left(\frac{B}{28\pi\delta}\right)\right\rceil$ and
suppose $f:\left(x_{0}+rG_{m}^{n}\right)\to\mathbb{R}$ is such that

$\left|f(x_{0}+rx)-\left\langle g,rx\right\rangle-c\right|\leq\delta$ (4)

for 99.9% of the points $x\in G_{m}^{n}$, and we have access to a standard
unitary oracle $U$, providing
$\mathcal{O}\left(\log\left(\\!\frac{B}{\delta}\\!\right)\right)$-bit fixed-
point binary approximations $\tilde{f}(z)$ s.t.
$|\tilde{f}(z)-f(z)|\leq\delta$ for all $z\in\left(x_{0}+rG_{m}^{n}\right)$.
Then we can compute a vector $\tilde{g}\in\mathbb{R}^{n}$ such that

$\Pr\left[\,\left\lVert\tilde{g}-g\right\rVert_{\infty}>\\!\frac{8\cdot
42\pi\delta}{r}\right]\leq\rho,$

with $\mathcal{O}\left(\\!\log\\!\big{(}\frac{n}{\rho}\big{)}\\!\right)$
queries to $U$ and $U^{\dagger}$ and gate complexity
$\mathcal{O}\left(\\!n\log\\!\big{(}\frac{n}{\rho}\big{)}\\!\log\\!\big{(}\\!\frac{B}{\delta}\\!\big{)}\\!\log\\!\log\\!\big{(}\frac{n}{\rho}\big{)}\\!\log\\!\log\\!\big{(}\\!\frac{B}{\delta}\\!\big{)}\\!\right)\\!$.

###### Proof.

As described above the corollary, we first implement a phase oracle for
$\tilde{f}$ and then we apply Jordan’s gradient computation algorithm (Lemma
14).

With a single query to $U$ and its inverse we can implement a phase oracle
$\mathrm{O}$ that acts as $\mathrm{O}:|x\rangle\mapsto e^{2\pi
i\frac{M}{3B}\tilde{f}(x_{0}+rx)}|x\rangle$, where
$M:=\frac{3B}{84\pi\delta}$, and555We can assume without loss of generality
that the upper bound $B$ is such that $M$ is a power of two. $m:=\log_{2}(M)$.
Let $h(x):=\frac{\tilde{f}(x_{0}+rx)}{3B}$, then by (4) 99.9% of the points
$x\in G_{m}^{n}$ satisfy
$\big{|}h(x)-\left\langle\frac{r}{3B}g,x\right\rangle-\frac{c}{3B}\big{|}\leq\frac{2\delta}{3B}=\frac{1}{42\pi
M}$. Since $\left\lVert\frac{r}{3B}g\right\rVert_{\infty}\leq\frac{1}{3}$, by
Lemma 14 we can compute a vector $v\in\mathbb{R}^{n}$ which is a
coordinatewise $\frac{4}{M}$-approximator of $\frac{r}{3B}g$: for each
$i\in[n]$ we have
$\left|g_{i}-\frac{3B}{r}v_{i}\right|\leq\frac{12B}{rM}=\frac{8\cdot
42\pi\delta}{r}$ with probability at least $\frac{2}{3}$.

Note that the above success probability is per coordinate of $g$. However,
repeating the whole procedure
$\mathcal{O}\big{(}\\!\log(\frac{n}{\rho})\big{)}$ times and taking the median
of the resulting vectors coordinatewise gives a gradient approximator
$\tilde{g}$ with the desired approximation quality with probability at least
$1-\rho$. For the proof of the gate complexity we refer666The correspondence
with the parametrization of [GAW19, Theorem 21] is
$\varepsilon\leftrightarrow\frac{8\cdot 42\pi\delta}{r}$,
$M\leftrightarrow\frac{B}{r}$. to [GAW19, Theorem 21] where the complexity of
Jordan’s algorithm is analyzed in detail. ∎

#### Remark.

With essentially the same approach, the above corollary of Jordan’s quantum
gradient computation algorithm can also be proven in the setting where our
access to an approximation of $f$ is not given by a standard quantum oracle
but by a _relational_ quantum oracle, see Appendix A for both the definition
of this type of approximation to $f$ and a proof of this corollary.

In terms of applications, we want to point out that if the membership oracle
used in Section 4 comes from a deterministic algorithm, then we get a standard
quantum oracle. Only when the membership oracle itself is relational (for
example, when it is itself computed by a bounded-error quantum algorithm) do
we need the more general setting of Appendix A.

We would like to apply the above corollary to compute gradients of a convex
Lipschitz function. To that end, the function needs to be sufficiently close
to a linear function on a small region. Fortunately convex Lipschitz functions
have this property. The following two lemmas ensure that Equation (4) holds.

######  Lemma 16.

Let $S\subseteq\mathbb{R}^{n}$ be such that $S=-S$, and let $\mathrm{conv}(S)$
denote the convex hull of $S$. If $f:\mathrm{conv}(S)\to\mathbb{R}$ is a
convex function, $f(0)=0$, and $\left|f(s)\right|\leq\delta$ for all $s\in S$,
then

$|f(s^{\prime})|\leq\delta\text{ for all }s^{\prime}\in\mathrm{conv}(S).$

###### Proof.

Since $f$ is convex and $f(s)\leq\delta$ for all $s\in S$ we immediately get
that $f(s^{\prime})\leq\delta$ for all $s^{\prime}\in\mathrm{conv}(S)$.
Because $f(0)=0$ and $S=-S$, due to convexity we get that
$f(s^{\prime})\geq-f(-s^{\prime})\geq-\delta$. ∎

######  Lemma 17.

If $r_{2}>0$, $z\in\mathbb{R}^{n}$ and $f:B_{1}(z,r_{2})\rightarrow\mathbb{R}$
is convex, then

$\sup_{y\in B_{1}(0,r_{2})}\left|f(z+y)-f(z)-\left\langle
y,\nabla^{(r_{2})}f(z)\right\rangle\right|\leq\frac{r_{2}^{2}\Delta^{\\!\\!(r_{2})}f(z)}{2}.$

###### Proof.

Let $d(y):=f(z+y)-f(z)-\left\langle y,\nabla^{(r_{2})}f(z)\right\rangle$ be
the difference between $f(z+y)$ and its linear approximator. Let
$S:=\left\\{\pm r_{2}e_{i}:i\in[n]\right\\}$. It is easy to see that $d(0)=0$,
$S=-S$, and $\mathrm{conv}(S)=B_{1}(0,r_{2})$. Also, for all $s\in S$ we have
$\left|d(s)\right|\leq r_{2}^{2}\Delta^{\\!\\!(r_{2})}f(z)/2$:

$\displaystyle d(\pm r_{2}e_{i})$ $\displaystyle=f(z\pm
r_{2}e_{i})-f(z)-\left\langle\pm r_{2}e_{i},\nabla^{(r_{2})}f(z)\right\rangle$
$\displaystyle=f(z\pm r_{2}e_{i})-f(z)\mp r_{2}\nabla_{i}^{(r_{2})}f(z)$
$\displaystyle=f(z\pm
r_{2}e_{i})-f(z)\mp\frac{f(z+r_{2}e_{i})-f(z-r_{2}e_{i})}{2}$
$\displaystyle=\frac{f(z+r_{2}e_{i})-2f(z)+f(z-r_{2}e_{i})}{2}$
$\displaystyle=r_{2}^{2}\Delta_{i}^{\\!\\!(r_{2})}f(z)/2\quad\leq
r_{2}^{2}\Delta^{\\!\\!(r_{2})}f(z)/2.$

Therefore Lemma 16 implies that $\sup_{y\in B_{1}(0,r_{2})}|d(y)|\leq
r_{2}^{2}\Delta^{\\!\\!(r_{2})}f(z)/2$. ∎

We can now state the main result of this section, the quantum analogue of
Lemma 12.

######  Lemma 18.

Let $r_{1}>0$, $L>0$, $\rho\in(0,1/3]$, and suppose
$\delta\in(0,r_{1}nL/\rho]$. Suppose $f:C\to\mathbb{R}$ is a convex function
that is $L$-Lipschitz on $B_{\infty}(0,2r_{1})$, and we have quantum query
access777Using Corollary 29 instead of Corollary 15 shows that a relational
quantum oracle also suffices as input. to $\tilde{f}$, which is a
$\delta$-approximate version of $f$, via a unitary $U$ over a (fine-enough)
hypergrid of $B_{\infty}(0,2r_{1})$. Then we can compute a
$\tilde{g}\in\mathbb{R}^{n}$ using $\mathcal{O}\left(\log(n/\rho)\right)$
queries to $U$ and $U^{\dagger}$, such that with probability $\geq 1-\rho$, we
have

$f(y)\geq f(0)+\left\langle\tilde{g},y\right\rangle-23^{2}\sqrt{\frac{\delta
n^{3}L}{\rho r_{1}}}\left\lVert
y\right\rVert_{1}-2L\sqrt{n}r_{1}\qquad\text{for all }y\in C$

and hence (by Cauchy-Schwarz)

$f(y)\geq
f(0)+\left\langle\tilde{g},y\right\rangle-(23n)^{2}\sqrt{\frac{\delta L}{\rho
r_{1}}}\left\lVert y\right\rVert-2L\sqrt{n}r_{1}\qquad\text{for all }y\in C.$

###### Proof.

Let $r_{2}:=\sqrt{\frac{\delta r_{1}\rho}{nL}}$ and note that $r_{2}\leq
r_{1}$. The quantum algorithm works roughly as follows. It first picks a
uniformly888A discrete quantum computer strictly speaking cannot do this, but
(as noted after Lemma 11) a uniformly random point from a fine-enough
hypergrid suffices. random $z\in B_{\infty}(0,r_{1})$. Then it uses Jordan’s
quantum algorithm to compute an approximate gradient at $z$ by approximately
evaluating $f$ in superposition over a discrete hypergrid of
$B_{\infty}(z,r_{2}/n)$. This then yields an approximate subgradient of $f$ at
$0$.

We now work out this rough idea. Since $B_{\infty}(z,r_{2}/n)\subseteq
B_{1}(z,r_{2})$, Lemma 17 implies

$\sup_{y\in B_{\infty}(0,r_{2}/n)}\left|f(z+y)-f(z)-\left\langle
y,\nabla^{(r_{2})}f(z)\right\rangle\right|\leq\frac{r_{2}^{2}\Delta^{\\!\\!(r_{2})}f(z)}{2}.$
(5)

Also as shown by Lemma 11 and Markov’s inequality we have

$\Delta^{\\!\\!(r_{2})}f(z)\leq\frac{2nL}{\rho r_{1}}$ (6)

with probability $\geq 1-\rho/2$ over the choice of $z$. If $z$ is such that
Equation (6) holds, then we get

$\sup_{y\in B_{\infty}(0,r_{2}/n)}\left|f(z+y)-f(z)-\left\langle
y,\nabla^{(r_{2})}f(z)\right\rangle\right|\leq\frac{nLr_{2}^{2}}{\rho
r_{1}}=\delta.$

Now apply the quantum algorithm of Corollary 15 with $r=2r_{2}/n$, $c=f(z)$,
$g=\nabla^{(r_{2})}f(z)$, and $B=Lr$. This uses
$\mathcal{O}\left(\log(n/\rho)\right)$ queries to $U$ and $U^{\dagger}$, and
with probability $\geq 1-\rho/2$ computes an approximate gradient $\tilde{g}$
such that

$\left\lVert\nabla^{(r_{2})}f(z)-\tilde{g}\right\rVert_{\infty}\leq\frac{8\cdot
42\pi n}{2r_{2}}\cdot\delta=4\cdot 42\cdot\pi\sqrt{\frac{\delta n^{3}L}{\rho
r_{1}}}.$ (7)

Also, if $z$ is such that Equation (6) holds, then by Lemma 10 we get that

$\sup_{g\in\underline{\partial}f(z)}\left\lVert\nabla^{(r_{2})}f(z)-g\right\rVert_{1}\leq\frac{r_{2}\Delta^{\\!\\!(r_{2})}f(z)}{2}\leq\frac{nLr_{2}}{\rho
r_{1}}=\sqrt{\frac{\delta nL}{\rho r_{1}}},$

and therefore by the triangle inequality and Equation (7) we get that

$\displaystyle\sup_{g\in\underline{\partial}f(z)}\left\lVert
g-\tilde{g}\right\rVert_{\infty}$
$\displaystyle\leq\sup_{g\in\underline{\partial}f(z)}\left\lVert
g-\nabla^{(r_{2})}f(z)\right\rVert_{\infty}+\left\lVert\nabla^{(r_{2})}f(z)-\tilde{g}\right\rVert_{\infty}$
$\displaystyle\leq\sup_{g\in\underline{\partial}f(z)}\left\lVert
g-\nabla^{(r_{2})}f(z)\right\rVert_{1}+\left\lVert\nabla^{(r_{2})}f(z)-\tilde{g}\right\rVert_{\infty}$
$\displaystyle\leq\sqrt{\frac{\delta nL}{\rho r_{1}}}+4\cdot
42\cdot\pi\sqrt{\frac{\delta n^{3}L}{\rho
r_{1}}}\quad<23^{2}\sqrt{\frac{\delta n^{3}L}{\rho r_{1}}}.$

Thus with probability at least $1-\rho$, for all $y\in C$ and for all
$g\in\underline{\partial}f(z)$ we have that

$\displaystyle f(y)$ $\displaystyle\geq f(z)+\left\langle g,y-z\right\rangle$
$\displaystyle=f(0)+\left\langle\tilde{g},y\right\rangle+\left\langle
g-\tilde{g},y\right\rangle+(f(z)-f(0))+\langle g,-z\rangle$ $\displaystyle\geq
f(0)+\left\langle\tilde{g},y\right\rangle-|\left\langle
g-\tilde{g},y\right\rangle|-L\left\lVert z\right\rVert-\left\lVert
g\right\rVert\left\lVert z\right\rVert$ $\displaystyle\geq
f(0)+\left\langle\tilde{g},y\right\rangle-\left\lVert
g-\tilde{g}\right\rVert_{\infty}\left\lVert
y\right\rVert_{1}-L\sqrt{n}r_{1}-L\sqrt{n}r_{1}$ (by (1)) $\displaystyle\geq
f(0)+\left\langle\tilde{g},y\right\rangle-23^{2}\sqrt{\frac{\delta
n^{3}L}{\rho r_{1}}}\left\lVert y\right\rVert_{1}-2L\sqrt{n}r_{1}$
$\displaystyle\geq
f(0)+\left\langle\tilde{g},y\right\rangle-(23n)^{2}\sqrt{\frac{\delta L}{\rho
r_{1}}}\left\lVert y\right\rVert-2L\sqrt{n}r_{1}.\qed$

##  4 Algorithms for separation using membership queries

Let $K\subseteq\mathbb{R}^{n}$ be a convex set such that $B(0,r)\subseteq
K\subseteq B(0,R)$. Given a membership oracle999For simplicity we assume
throughout this section that the membership oracle succeeds with certainty
(i.e., its error probability is $0$). This is easy to justify: suppose we have
a classical $T$-query algorithm, which uses $\mathrm{MEM}_{\varepsilon,0}(K)$
queries and succeeds with probability at least $1-\rho$. If we are given
access to a $\mathrm{MEM}_{\varepsilon,\frac{1}{3}}(K)$ oracle instead, then
we can create a $\mathrm{MEM}_{\varepsilon,\frac{\rho}{T}}(K)$ oracle by
$\mathcal{O}\left(\log(T/\rho)\right)$ queries to
$\mathrm{MEM}_{\varepsilon,\frac{1}{3}}(K)$ and taking the majority of the
answers. Then running the original algorithm with
$\mathrm{MEM}_{\varepsilon,\frac{\rho}{T}}(K)$ will fail with probability at
most $2\rho$. Therefore the assumption of a membership oracle with error
probability 0 can be removed at the expense of only a small logarithmic
overhead in the number of queries. A similar argument works for the quantum
case. $\mathrm{MEM}_{\varepsilon,0}(K)$ as in Definition 3, we will construct
a separation oracle $\mathrm{SEP}_{\eta,\rho}(K)$ as in Definition 4. Let $x$
be the point we want to separate from $K$. We first make a membership query to
$x$ itself, receiving answer $x\in B(K,\varepsilon)$ or $x\not\in
B(K,-\varepsilon)$. Suppose $x\not\in B(K,-\varepsilon)$, then we need to find
a hyperplane that approximately separates $x$ from $K$. Due to the rotational
symmetry of the separation problem, for ease of notation we assume that
$x=-\left\lVert x\right\rVert e_{n}$.101010For the query complexity this is
without loss of generality, since we can always apply a rotation to all the
points such that this holds. If we instead consider the computational cost of
our algorithm, then we have to take into account the cost of this rotation and
its inverse. Note, however, that this rotation can always be written as the
product of $n$ rotations on only $2$ coordinates, and hence can be applied in
$\widetilde{\mathcal{O}}\left(n\right)$ additional steps. These rotations can
also be found in $\widetilde{\mathcal{O}}\left(n\right)$ time via a greedy
algorithm: first find a rotation on coordinates $n$ and $n-1$ that leaves
coordinate $n-1$ zero, then similarly for coordinates $n-2$ and $n$, and so
on. We define $h:\mathbb{R}^{n-1}\rightarrow\mathbb{R}\cup\\{\infty\\}$ as

$h(y):=\inf_{(y,y_{n})\in K}y_{n},$

see also Figure 2. Note that $h$ implicitly depends on $x$, since we have
rotated the space such that $x=-\left\lVert x\right\rVert e_{n}$.

Figure 2: Graphical example of the relation between $h(y)$ and the distance
from $(y,0)$ to the border in the $-e_{n}$ direction.

Our $h$ is a bit different from the one used in [LSV18], but we can show that
it has many of the same properties. Since $K$ is a convex set, $h$ is a convex
function over $\mathbb{R}^{n-1}$. As we show below, the function $h$ is also
Lipschitz (Lemma 19) and we can approximately compute its value using binary
search with $\widetilde{\mathcal{O}}\left(1\right)$ classical queries to a
membership oracle (Lemma 20). Furthermore, an approximate subgradient of $h$
at $0$ allows to construct a hyperplane approximately separating $x$ from $K$
(Lemma 21). Combined with the results of Section 3 this leads to the main
results of this section, Theorems 22 and 23, which show how to efficiently
construct a separation oracle using respectively classical and quantum queries
to a membership oracle.

Analogously to [LSV18, Lemma 12] we first show that our $h$ is Lipschitz.

######  Lemma 19.

For every $\delta\in(0,r)$, $h$ is $\frac{R}{r-\delta}$-Lipschitz on
$B(0,\delta)\subseteq\mathbb{R}^{n-1}$, that is, we have

$|h(y^{\prime})-h(y)|\leq\frac{R}{r-\delta}\left\lVert
y^{\prime}-y\right\rVert\quad\text{for all }y,y^{\prime}\in B(0,\delta).$

###### Proof.

Observe that for all $y\in B(0,r)$ we have $-R\leq h(y)\leq 0$, because
$B(0,r)\subseteq K\subseteq B(0,R)$. Let $y,y^{\prime}\in B(0,\delta)$ be
arbitrary but distinct points. Due to symmetry it will suffice to show that
$h(y^{\prime})-h(y)\leq\frac{R}{r-\delta}\left\lVert
y^{\prime}-y\right\rVert$.

We will restrict our attention to the line through $y$ and $y^{\prime}$, i.e.,
the line given by $y+\lambda z$ for $z:=\frac{y^{\prime}-y}{\left\lVert
y^{\prime}-y\right\rVert}$. Define the point

$p:=y+\left(\left\lVert
y^{\prime}-y\right\rVert+\left(r-\delta\right)\right)z=y^{\prime}+\left(r-\delta\right)z$

on this line and note that $p\in B(0,r)$. Since $y^{\prime}$ lies between $y$
and $p$ on the line it is a convex combination of these two points. In
particular, since $\left\lVert p-y^{\prime}\right\rVert=r-\delta$, it is the
convex combination

$y^{\prime}=\frac{\left\lVert y^{\prime}-y\right\rVert}{\left\lVert
y^{\prime}-y\right\rVert+(r-\delta)}p+\frac{r-\delta}{\left\lVert
y^{\prime}-y\right\rVert+(r-\delta)}y.$

Due to convexity we have

$h(y^{\prime})\leq\frac{\left\lVert y^{\prime}-y\right\rVert}{\left\lVert
y^{\prime}-y\right\rVert+(r-\delta)}h(p)+\frac{r-\delta}{\left\lVert
y^{\prime}-y\right\rVert+(r-\delta)}h(y),$

which implies

$h(y^{\prime})-h(y)\leq\frac{\left\lVert y^{\prime}-y\right\rVert}{\left\lVert
y^{\prime}-y\right\rVert+(r-\delta)}\left(h(p)-h(y)\right)\leq\frac{\left\lVert
y^{\prime}-y\right\rVert}{r-\delta}R.\qed$

Now we show how to compute the value of $h$ using membership queries to $K$.

######  Lemma 20.

For all $y\in B\big{(}0,\frac{r}{2}\big{)}\subset\mathbb{R}^{n-1}$ we can
compute a $\delta$-approximation of $h(y)$ with
$\mathcal{O}\left(\log\left(\frac{R}{\delta}\right)\right)$ queries to a
$\mathrm{MEM}_{\varepsilon,0}(K)$ oracle, where
$\varepsilon\leq\frac{r}{3R}\delta$.

###### Proof.

Let $y\in B(0,\frac{r}{2})$, then $(y,h(y))$ is a boundary point of $K$ by the
definition of $h$. Note that $h(y)\in[-R,-r/2]$. Our goal is to perform binary
search over this interval to find a good approximation of $h(y)$. If we had
access to a perfect membership oracle, then this would be straightforward.
However, since our membership oracle can give back a wrong answer when queried
with a point that is $\varepsilon$-close to the boundary of $K$, a more
careful analysis is needed.

Suppose $y_{n}\leq-\frac{r}{2}$ is our current guess for $h(y)$. We first show
that

  1. (_a_)

if $(y,y_{n})\in B(K,\varepsilon)$, then $y_{n}\geq h(y)-\delta$, and

  2. (_b_)

if $(y,y_{n})\not\in B(K,-\varepsilon)$, then $y_{n}\leq
h(y)+\frac{2}{3}\delta$.

For the proof of (_a_) consider a $g\in\underline{\partial}h(y)$. Since $g$ is
a subgradient we have that $h(z)\geq h(y)+\left\langle g,z-y\right\rangle$ for
all $z\in\mathbb{R}^{n-1}$. Hence, for all $z\in\mathbb{R}^{n-1}$ and $z_{n}$
such that $(z,z_{n})\in K$ we have

$\left\langle\begin{pmatrix}-g\\\ 1\end{pmatrix},\begin{pmatrix}y\\\
h(y)\end{pmatrix}\right\rangle\leq\left\langle\begin{pmatrix}-g\\\
1\end{pmatrix},\begin{pmatrix}z\\\
h(z)\end{pmatrix}\right\rangle\leq\left\langle\begin{pmatrix}-g\\\
1\end{pmatrix},\begin{pmatrix}z\\\ z_{n}\end{pmatrix}\right\rangle$

where the first inequality is a rewriting of the subgradient inequality and
the second inequality uses that $z_{n}\geq h(z)$ since $(z,z_{n})\in K$. Since
$(y,y_{n})\in B(K,\varepsilon)$ it follows from the above inequality that

$\left\langle\begin{pmatrix}-g\\\ 1\end{pmatrix},\begin{pmatrix}y\\\
y_{n}\end{pmatrix}\right\rangle\geq\left\langle\begin{pmatrix}-g\\\
1\end{pmatrix},\begin{pmatrix}y\\\
h(y)\end{pmatrix}\right\rangle-\varepsilon\left\lVert\begin{pmatrix}-g\\\
1\end{pmatrix}\right\rVert\geq\left\langle\begin{pmatrix}-g\\\
1\end{pmatrix},\begin{pmatrix}y\\\
h(y)\end{pmatrix}\right\rangle-\varepsilon(\left\lVert g\right\rVert+1).$

Lemma 19 together with the argument of Equation (1) implies that $\left\lVert
g\right\rVert\leq\frac{2R}{r}$. Since

$\varepsilon(\left\lVert
g\right\rVert+1)\leq\varepsilon\left(\frac{2R}{r}+1\right)\leq\varepsilon\frac{3R}{r}\leq\delta,$

we obtain the inequality of (_a_).

For (_b_), consider the convex set $C$ which is the convex hull of
$B((y,0),r/2)$ and $(y,h(y))$. Note that $B(C,-\varepsilon)$ is the convex
hull of $B((y,0),r/2-\varepsilon)$ and
$\big{(}y,h(y)\left(1-\frac{2\varepsilon}{r}\right)\big{)}$. Since $C\subseteq
K$, we have $B(C,-\varepsilon)\subseteq B(K,-\varepsilon)$. Therefore
$(y,y_{n})\not\in B(K,-\varepsilon)$ implies $(y,y_{n})\notin
B(C,-\varepsilon)$, and

$y_{n}\leq
h(y)\left(1-\frac{2\varepsilon}{r}\right)=h(y)-\varepsilon\frac{2h(y)}{r}\leq
h(y)+\varepsilon\frac{2R}{r}\leq h(y)+\frac{2}{3}\delta.$

Now we can analyze the binary search algorithm. By making
$\mathcal{O}\left(\log\left(\frac{R}{\delta}\right)\right)$
$\mathrm{MEM}_{\varepsilon,0}(K)$ queries to points of the form $(y,z)$, we
can find a value $y_{n}\in[-R,-\frac{r}{2}]$ such that $(y,y_{n})\in
B(K,\varepsilon)$ but $(y,y_{n}-\frac{\delta}{3})\not\in B(K,-\varepsilon)$.
By (_a_)-(_b_) we get that $|h(y)-y_{n}|\leq\delta$. ∎

The following lemma shows how to convert an approximate subgradient of $h$ to
a hyperplane that approximately separates $x$ from $K$.

######  Lemma 21.

Suppose $-\left\lVert x\right\rVert e_{n}=x\notin B(K,-\varepsilon)$, and
$\tilde{g}\in\mathbb{R}^{n-1}$ is an approximate subgradient of $h$ at $0$,
meaning that for some $a,b\in\mathbb{R}$ and for all $y\in\mathbb{R}^{n-1}$

$h(y)\geq h(0)+\langle\tilde{g},y\rangle-a\left\lVert y\right\rVert-b,$

then $s:=\frac{(-\tilde{g},1)}{\left\lVert(-\tilde{g},1)\right\rVert}$
satisfies $\left\langle s,z\right\rangle\geq\left\langle
s,x\right\rangle-\frac{aR+b}{\left\lVert(-\tilde{g},1)\right\rVert}-\frac{2R}{r}\frac{\varepsilon}{\left\lVert(-\tilde{g},1)\right\rVert}$
for all $z\in K$.

###### Proof.

Let us introduce the notation $z=(y,z_{n})$ and
$s^{\prime}:=(-\tilde{g},1)=\left\lVert(-\tilde{g},1)\right\rVert s$, then

$\displaystyle\left\langle s^{\prime},z\right\rangle$
$\displaystyle=z_{n}-\left\langle\tilde{g},y\right\rangle$ $\displaystyle\geq
h(y)-\left\langle\tilde{g},y\right\rangle$ $\displaystyle\geq
h(0)-a\left\lVert y\right\rVert-b$ $\displaystyle\geq-\left\lVert
x\right\rVert-\frac{2R}{r}\varepsilon-aR-b$ $\displaystyle=\left\langle
s^{\prime},x\right\rangle-aR-b-\frac{2R}{r}\varepsilon,$

where the last inequality used claim (_b_) from the proof of Lemma 20 with the
point $(0,-\left\lVert x\right\rVert)$ and $\delta=\frac{3R}{r}\varepsilon$. ∎

We now construct a separation oracle using $\widetilde{\mathcal{O}}(n)$
classical queries to a membership oracle. In particular, to construct an
$\eta$-precise separation oracle, we require an $\varepsilon$-precise
membership oracle with

$\varepsilon=\frac{\eta}{676}n^{-2}\left(\frac{r}{R}\right)^{\\!3}\left(\frac{\eta}{R}\right)^{\\!2}\rho$

The analogous result in [LSV18, Theorem 14] uses the stronger
assumption111111It seems that Lee et al. [LSV18, Algorithm 1] did not take
into account the change in precision analogous to our Lemma 20, therefore one
would probably need to worsen their exponent of $\frac{r}{R}$ from 6 to 7.

$\varepsilon\approx\frac{\eta}{8\cdot
10^{6}}n^{-\frac{7}{2}}\left(\frac{r}{R}\right)^{\\!\\!6}\left(\frac{\eta}{R}\right)^{\\!\\!2}\rho^{3}.$

Compared to this, our result scales better in terms of $n,\frac{r}{R}$ and
$\rho$.

######  Theorem 22.

Let $K$ be a convex set satisfying $B(0,r)\subseteq K\subseteq B(0,R)$. For
any $\eta\in(0,R]$ and $\rho\in(0,1/3]$, we can implement the oracle
$\mathrm{SEP}_{\eta,\rho}(K)$ using
$\mathcal{O}\left(n\log\left(\frac{n}{\rho}\frac{R}{\eta}\frac{R}{r}\right)\right)$
classical queries to a $\mathrm{MEM}_{\varepsilon,0}(K)$ oracle, where
$\varepsilon\leq\eta(26n)^{-2}\left(\frac{r}{R}\right)^{\\!3}\left(\frac{\eta}{R}\right)^{\\!2}\rho$.

###### Proof.

Let $x\not\in B(K,-\varepsilon)$ be the point we want to separate from $K$.
Let $\delta:=\eta\frac{n^{-2}}{9\cdot
24}\left(\frac{r}{R}\cdot\frac{\eta}{R}\right)^{\\!2}\rho$,then
$\varepsilon\leq\frac{r}{3R}\delta$. By Lemma 19 we know that $h$ is
$\frac{2R}{r}$-Lipschitz on $B(0,r/2)$. By Lemma 20 we can evaluate $h$ to
within error $\delta$ using
$\mathcal{O}\left(\log\left(\frac{R}{\delta}\right)\right)$ queries to a
$\mathrm{MEM}_{\varepsilon,0}(K)$ oracle. Let us choose
$r_{1}:=\frac{r}{12\sqrt{n}}\frac{\eta}{R}$, then
$r_{1}\sqrt{n}\leq\frac{r}{4}$, therefore $B_{\infty}(0,2r_{1})\subseteq
B(0,r/2)$. Also note that
$\delta\leq\frac{\eta}{6\rho}=\frac{2r_{1}\sqrt{n}R}{\rho r}$. Hence by Lemma
12, using $\mathcal{O}\left(n\log\left(\frac{R}{\delta}\right)\right)$ queries
to a $\mathrm{MEM}_{\varepsilon,0}(K)$ oracle, we can compute an approximate
subgradient $\tilde{g}$ such that with probability at least $1-\rho$ we have

$h(y)\geq
h(0)+\langle\tilde{g},y\rangle-\frac{3n^{\frac{3}{4}}}{2}\sqrt{\frac{\delta
2R}{\rho r_{1}r}}\left\lVert
y\right\rVert-\frac{4R}{r}\sqrt{n}r_{1}\qquad\text{for all
}y\in\mathbb{R}^{n-1}.$

Substituting the value of $r_{1}$ and $\delta$ we get $h(y)\geq
h(0)+\langle\tilde{g},y\rangle-\frac{\eta}{2R}\left\lVert
y\right\rVert-\frac{\eta}{3}$, which by Lemma 21 gives an $s$ such that
$\left\langle s,z\right\rangle\geq\left\langle
s,x\right\rangle-\frac{5}{6}\eta-\frac{2R}{r}\varepsilon\geq\left\langle
s,x\right\rangle-\eta$ for all $z\in K$ ∎

Finally, we give a proof of our main result: we construct a separation oracle
using $\widetilde{\mathcal{O}}(1)$ quantum queries to a membership oracle.

######  Theorem 23.

Let $K$ be a convex set satisfying $B(0,r)\subseteq K\subseteq B(0,R)$. For
any $\eta\in(0,R]$ and $\rho\in(0,1/3]$, we can implement the oracle
$\mathrm{SEP}_{\eta,\rho}(K)$ using
$\mathcal{O}\left(\log\big{(}\frac{n}{\rho}\big{)}\log\left(\frac{n}{\rho}\frac{R}{\eta}\frac{R}{r}\right)\right)$
quantum queries to a $\mathrm{MEM}_{\varepsilon,0}(K)$ oracle (and its
inverse), where
$\varepsilon\leq\eta(58n)^{-\frac{9}{2}}\left(\frac{r}{R}\right)^{\\!3}\left(\frac{\eta}{R}\right)^{\\!2}\rho$.

###### Proof.

Let $x\not\in B(K,-\varepsilon)$ be the point that we want to separate from
$K$. Let us define $\delta:=\eta\frac{23^{-4}}{4\cdot
24}n^{\\!-\frac{9}{2}}\left(\frac{r}{R}\cdot\frac{\eta}{R}\right)^{\\!2}\rho$,
then $\varepsilon\leq\frac{r}{3R}\delta$. By Lemma 19 we know that $h$ is
$\frac{2R}{r}$-Lipschitz on $B(0,r/2)$. By Lemma 20 we can evaluate $h$ to
within error $\delta$ using
$\mathcal{O}\left(\log\left(\frac{R}{\delta}\right)\right)$ queries to a
$\mathrm{MEM}_{\varepsilon,0}(K)$ oracle. Let us choose
$r_{1}:=\frac{r}{12\sqrt{n}}\frac{\eta}{R}$, then
$r_{1}\sqrt{n}\leq\frac{r}{4}$, therefore $B_{\infty}(0,2r_{1})\subseteq
B(0,r/2)$. Also note that $\delta\leq\frac{\eta}{6\rho}=\frac{2r_{1}nR}{\rho
r}$. Hence by Lemma 18, using
$\mathcal{O}\left(\log\\!\big{(}\frac{n}{\rho}\big{)}\\!\log\left(\frac{R}{\delta}\right)\\!\right)$
queries to a $\mathrm{MEM}_{\varepsilon,0}(K)$ oracle, we can compute an
approximate subgradient $\tilde{g}$ such that with probability at least
$1-\rho$ we have

$h(y)\geq h(0)+\langle\tilde{g},y\rangle-(23n)^{2}\sqrt{\frac{2\delta R}{\rho
r_{1}r}}\left\lVert y\right\rVert-\frac{4R}{r}\sqrt{n}r_{1}\qquad\text{for all
}y\in\mathbb{R}^{n-1}.$

Substituting the value of $r_{1}$ and $\delta$ we get $h(y)\geq
h(0)+\langle\tilde{g},y\rangle-\frac{\eta}{2R}\left\lVert
y\right\rVert-\frac{\eta}{3}$, which by Lemma 21 gives an $s$ such that
$\left\langle s,z\right\rangle\geq\left\langle
s,x\right\rangle-\frac{5}{6}\eta-\frac{2R}{r}\varepsilon\geq\left\langle
s,x\right\rangle-\eta$ for all $z\in K$. ∎

##  5 Lower bounds

For a convex set $K$ satisfying $B(0,r)\subseteq K\subseteq B(0,R)$, we have
shown in Theorem 23 that one can implement a $\mathrm{SEP}(K)$ oracle with
$\widetilde{\mathcal{O}}\left(1\right)$ quantum queries to a $\mathrm{MEM}(K)$
oracle if the membership oracle is sufficiently precise. In this section we
first show that this is exponentially better than what can be achieved using
classical access to a membership oracle. We also investigate how many queries
to a membership/separation oracle are needed in order to implement an
optimization oracle. Our results are as follows.

  * •

We show that $\Omega(n)$ classical queries to a membership oracle are needed
to implement a weak separation oracle.

  * •

We show that $\Omega(n)$ classical (resp. $\Omega(\sqrt{n})$ quantum) queries
to a separation oracle are needed to implement a weak optimization oracle;
even when we _know an interior point_ in the set.

  * •

We show an $\Omega(n)$ lower bound on the number of classical and/or quantum
queries to a separation oracle needed to optimize over the set when we _do not
know an interior point_.

In this section we will always assume that the input oracle is a strong oracle
but the output oracle is allowed to be a weak oracle with error $\varepsilon$.
Furthermore, we will make sure that $R$, $1/r$, and $1/\varepsilon$ are all
upper bounded by a polynomial in $n$. This guarantees that the lower bound is
based on the dimension of the problem, not the required precision.

###  5.1 Classical lower bound on the number of MEM queries needed for SEP

Here we show that a separation query can provide $\Omega(n)$ bits of
information about the underlying convex set $K$; since a classical membership
query returns a 0 or a 1 and hence can give at most 1 bit of
information,121212This is not true for _quantum_ membership queries! this
theorem immediately implies a lower bound of $\Omega(n)$ on the number of
classical membership queries needed to implement one separation query.

######  Theorem 24.

Let $\varepsilon\leq\frac{1}{48}$. There exist a set of $m=2^{\Omega(n)}$
convex sets $K_{1},\ldots,K_{m}$ and points $y,x_{0}\in\mathbb{R}^{n}$ such
that $B(x_{0},1/3)\subseteq K_{i}\subseteq B(x_{0},2\sqrt{n})$ for all
$i\in[m]$, and such that the result of a classical query to
$\mathrm{SEP}_{\varepsilon,0}(K_{i})$ with the point $y$ correctly identifies
$i$.

###### Proof.

Let $h_{1},\ldots,h_{m}\in\mathbb{R}^{n}$ be a set of $m=2^{\Omega(n)}$
entrywise non-negative unit vectors such that $\left\langle
h_{i},h_{j}\right\rangle\leq 0.51$ for all distinct $i,j\in[m]$.131313We can
show that such a set of vectors exists as follows. Let $n=ck$ for sufficiently
large constant $c$. Choose $m=2^{k}$ (which is $2^{\Omega(n)}$) uniformly
random vectors $v_{1},\ldots,v_{m}$ in $\\{0,1\\}^{n}$. Note that the expected
Hamming weight of one such vector is $n/2$, and the expected inner product
between two vectors is $n/4$ (the inner product just counts for how many of
the $n$ bit-positions both vectors have a 1). By a standard calculation
(Chernoff bound plus a union bound), one can show that with high probability
these $2^{k}$ vectors each have Hamming weight $\geq 0.495n$, and the inner
product between any two of them is $\leq 0.252n$. Fix $2^{k}$ such vectors
with these properties, and define $h_{i}:=v_{i}/\left\lVert
v_{i}\right\rVert$. These are unit vectors with non-negative entries, and
pairwise inner products $\left\langle h_{i},h_{j}\right\rangle=\left\langle
v_{i},v_{j}\right\rangle/(\left\lVert v_{i}\right\rVert\left\lVert
v_{j}\right\rVert)\leq 0.252n/(0.495n)<0.51$.

Now pick an $i\in[m]$ and define $\hat{K}_{i}:=\\{x:\left\langle
h_{i},x\right\rangle\leq 0\\}\cap B(0,\sqrt{n})$ and
$K_{i}:=B(\hat{K}_{i},\varepsilon)$. Then $\hat{K}_{i}=B(K_{i},-\varepsilon)$.
Note that for $x_{0}=-e/3$ we have $B(x_{0},1/3)\subseteq K_{i}\subseteq
B(x_{0},2\sqrt{n})$. We claim that a query to
$\mathrm{SEP}_{\varepsilon,0}(K_{i})$ with the point $y=3\varepsilon
e\in\mathbb{R}^{n}$ will identify $h_{i}$. First note that $y\not\in
B(K_{i},\varepsilon)$, since $\hat{K}_{i}$ does not contain any entrywise
positive vectors and $y$ has distance at least $3\varepsilon$ from all vectors
that have at least one non-positive entry. Hence a separation query with $y$
must return a unit vector $g$ that describes a valid separating hyperplane for
$K_{i}$.

On the other, if $g$ describes a valid separating hyperplane for $K_{j}$, then

$\forall x\in\hat{K}_{j}\colon\left\langle g,x\right\rangle\leq\left\langle
g,y\right\rangle+\varepsilon\leq\left\lVert g\right\rVert\cdot\left\lVert
y\right\rVert+\varepsilon\leq(3\sqrt{n}+1)\varepsilon\leq
4\sqrt{n}\varepsilon.$ (8)

Now consider the specific point $x$ that is the projection of $g$ onto
$h_{j}^{\bot}$ (the hyperplane orthogonal to $h_{j}$) scaled by a factor
$\sqrt{n}$, i.e., $x=\sqrt{n}\left(g-\left\langle g,h_{j}\right\rangle
h_{j}\right)$. Since $\left\langle h_{j},x\right\rangle=0$ and $\left\lVert
x\right\rVert\leq\sqrt{n}$, we have $x\in\hat{K}_{j}$. Choosing this $x$ in
(8) gives the following inequality

$\sqrt{n}(1-\left\langle g,h_{j}\right\rangle^{2})=\left\langle
g,x\right\rangle\leq 4\sqrt{n}\varepsilon.$

Hence (8) implies $|\left\langle
g,h_{j}\right\rangle|\geq\sqrt{1-4\varepsilon}\geq\sqrt{\frac{11}{12}}\geq\frac{19}{20}$.

Since (8) holds for $j=i$, it follows that at least one of the two vectors
$g-h_{i}$ and $g+h_{i}$ has length at most $\sqrt{2(1-|\left\langle
g,h_{i}\right\rangle|^{2})}\leq\sqrt{8\varepsilon}$; assume the former for
simplicity. If (8) would also hold for $j\neq i$, then we would get a
contradiction:

$\frac{19}{20}\leq|\left\langle g,h_{j}\right\rangle|\leq|\left\langle
g-h_{i},h_{j}\right\rangle|+|\left\langle
h_{i},h_{j}\right\rangle|\leq\sqrt{8\varepsilon}+0.51<\frac{19}{20}.$

Hence $g$ uniquely identifies $h_{i}$. ∎

###  5.2 Lower bound on number of SEP queries for OPT (given an interior
point)

We now consider lower bounding the number of quantum queries to a separation
oracle needed to do optimization. In fact, we prove a lower bound on the
number of separation queries needed for validity, which implies the same bound
on optimization. We will use a reduction from a version141414Note that this is
a slightly different version from the one used in Section 2.1. of the well-
studied _search_ problem:

_Given $z\in\\{0,1\\}^{n}$ such that either $|z|=0$ or $|z|=1$, decide which
of the two holds._

It is not hard to see that if the access to $z$ is given via classical
queries, then $\Omega(n)$ queries are needed. It is well known [BBBV97] that
if we allow quantum queries, then $\Omega(\sqrt{n})$ queries are needed (i.e.,
Grover’s quantum search algorithm [Gro96] is optimal). We use this problem to
show that there exist convex sets for which it is hard to construct a weak
validity oracle, given a strong separation oracle. Since a separation oracle
can be used as a membership oracle, this gives the same hardness result for
constructing a weak validity oracle from a strong membership oracle.

######  Theorem 25.

Let $0<\rho\leq 1/3$. Let $\mathcal{A}$ be an algorithm that implements a
$\mathrm{VAL}_{(5n)^{-1},\rho}(K)$ oracle for every convex set $K$ (with
$B(x_{0},r)\subseteq K\subseteq B(x_{0},R)$) using only queries to a
$\mathrm{SEP}_{0,0}(K)$ oracle, and unitaries that are independent of $K$.
Then the following statements are true, even when we restrict to convex sets
$K$ with $r=1/3$ and $R=2\sqrt{n}$:

  * •

if the queries to $\mathrm{SEP}_{0,0}(K)$ are classical, then the algorithm
uses $\Omega(n)$ queries.

  * •

if the queries to $\mathrm{SEP}_{0,0}(K)$ are quantum, then the algorithm uses
$\Omega(\sqrt{n})$ queries.

###### Proof.

Let $z\in\\{0,1\\}^{n}$ have Hamming weight $|z|=0$ or $|z|=1$. We construct a
set $K_{z}$ in such a way that solving the weak validity problem solves the
search problem for $z$, while separation queries for $K_{z}$ can be answered
using a single query to $z$. The known classical and quantum lower bounds on
the search problem then imply the two claims of the theorem, respectively.

Define $K_{z}:=\prod_{i=1}^{n}[-1,z_{i}]$. Observe that if we set
$x_{0}=(-1/2,\dots,-1/2)$, then $B(x_{0},\frac{1}{3})\subseteq K_{z}\subseteq
B(x_{0},2\sqrt{n})$.

We first show how to implement a strong separation oracle using a single query
to $z$. Suppose the input is the point $y$. The strong separation oracle works
as follows:

  1. 1.

If $y\in[-1,0]^{n}$, then return the statement that $y\in B(K_{z},0)=K_{z}$.

  2. 2.

If $y\not\in[-1,1]^{n}$, then return a hyperplane that separates $y$ from
$[-1,1]^{n}$ (and hence from $K_{z}$).

  3. 3.

Otherwise, let $i$ be such that $y_{i}>0$. Query $z_{i}$.

    1. (a)

If $z_{i}=1$ and $i$ is the only index such that $y_{i}>0$, then return that
$y\in B(K_{z},0)=K_{z}$.

    2. (b)

If $z_{i}=1$ and there is a $j\neq i$ such that $y_{j}>0$, return the
separating hyperplane corresponding to $x_{j}\leq y_{j}$.

    3. (c)

If $z_{i}=0$, then return the separating hyperplane $x_{i}\leq y_{i}$.

We show that a validity query over $K_{z}$ with the direction
$c=\frac{1}{\sqrt{n}}\left(1,\ldots,1\right)\in\mathbb{R}^{n}$, value
$\gamma=\frac{1}{2\sqrt{n}}$ and error $\varepsilon=\frac{1}{5n}$ solves the
search problem:

  * •

If $|z|=0$, then for all points $x\in K_{0}$ we have $\langle c,x\rangle\leq
0$. Thus, for all points $x\in B\left(K_{0},\varepsilon\right)$ we have
$\langle c,x\rangle\leq\varepsilon<\gamma-\varepsilon$. Hence the validity
oracle will have to return that $\langle c,x\rangle\leq\gamma+\varepsilon$
holds for all $x\in B\left(K_{0},-\varepsilon\right)$, since the other
possible output is not true.

  * •

If $|z|=1$, then the point $z\in K_{z}$ satisfies $\langle
z,c\rangle=\frac{1}{\sqrt{n}}$ and therefore $x=z-\varepsilon e\in
B\left(K_{z},-\varepsilon\right)$ satisfies $\langle
c,x\rangle=\frac{1}{\sqrt{n}}-\sqrt{n}\varepsilon>\gamma+\varepsilon$. Hence
the validity oracle will have to return that $\langle
c,x\rangle\geq\gamma-\varepsilon$ holds for some $x\in
B\left(K_{z},\varepsilon\right)$, since the other possible output is not true.

∎

###  5.3 Lower bound on number of SEP queries for OPT (without interior point)

We now lower bound the number of quantum queries to a separation oracle needed
to solve the optimization problem, if our algorithm does not already know an
interior point of $K$. In fact we prove a lower bound on finding a point close
to $K$ using separation queries, which implies the lower bound on the number
of separation queries needed for optimization since OPT returns a point close
to the set $K$.

We prove our lower bound by a reduction to the problem of learning $z$ with
_first-difference queries_. Here one needs to find an initially unknown
$n$-bit binary string $z$ via a guessing game. For a given guess
$g\in\\{0,1\\}^{n}$ a query returns the first index in $[n]$ for which the
binary strings $z$ and $g$ differ (or it returns $n+1$ if $z=g$). The goal is
to recover $z$ with as few guesses as possible. First we prove an $\Omega(n)$
quantum query lower bound for this problem.151515Note that this is a
strengthening of the $\Omega(n)$ quantum query lower bound for binary search
on a space of size $2^{n}$ by Ambainis [Amb99], since first-difference queries
are at least as strong as the queries one makes in binary search.

######  Theorem 26 (Quantum lower bound for learning $z$ with first-difference
queries).

Let $z\in\\{0,1\\}^{n}$ be an unknown string accessible by an oracle acting as
$O_{z}|g,b\rangle=|g,b\oplus f(g,z)\rangle$, where $f(g,z)$ is the first index
for which $z$ and $g$ differ, more precisely $f(g,z)=\min\\{i\in[n]:g_{i}\neq
z_{i}\\}$ if $g\neq z$ and $f(g,z)=n+1$ otherwise. Then every quantum
algorithm that outputs $z$ with high probability uses at least $\Omega(n)$
queries to $O_{z}$.

###### Proof.

We will use the general adversary bound [HLŠ07]. For this problem, we call
$\Gamma\in\mathbb{R}^{2^{n}\times 2^{n}}$ an _adversary matrix_ if it is a
non-zero matrix with zero diagonal whose rows and columns are indexed by all
$z\in\\{0,1\\}^{n}$. For $g\in\\{0,1\\}^{n}$ let us define
$\Delta_{g}\in\\{0,1\\}^{2^{n}\times 2^{n}}$ such that the $[z,z^{\prime}]$
entry of $\Delta_{g}$ is $0$ if and only if $f(g,z)=f(g,z^{\prime})$. The
general adversary bound tells us that for any adversary matrix $\Gamma$, the
quantum query complexity of our problem is

$\Omega\left(\frac{\left\lVert\Gamma\right\rVert}{\max_{g\in\\{0,1\\}^{n}}\left\lVert\Gamma\circ\Delta_{g}\right\rVert}\right),$
(9)

where “$\circ$” denotes the Hadamard product and
$\left\lVert\cdot\right\rVert$ the operator norm.

We claim that Equation (9) gives a lower bound of $\Omega(n)$ for the
adversary matrix $\Gamma$ defined as

$\Gamma[z,z^{\prime}]=\begin{cases}2^{f(z,z^{\prime})}&\mbox{if }z\neq
z^{\prime}\\\ 0&\mbox{if }z=z^{\prime}\end{cases}$

It is easy to see that $\Gamma$ is indeed an adversary matrix since it is zero
on the diagonal and non-zero everywhere else. Furthermore, the all-one vector
$e$ is an eigenvector of $\Gamma$ with eigenvalue $n2^{n}$:

$(\Gamma
e)_{z}=\sum_{z^{\prime}\in\\{0,1\\}^{n}}\Gamma[z,z^{\prime}]=\sum_{d=1}^{n}2^{d}\cdot|\\{z^{\prime}\in\\{0,1\\}^{n}\,:\,f(z,z^{\prime})=d\\}|=\sum_{d=1}^{n}2^{d}2^{n-d}=n2^{n}.$

So $\Gamma e=n2^{n}e$ and hence $\left\lVert\Gamma\right\rVert\geq n2^{n}$.

From the definition of $\Delta_{g}$ it follows that

$\displaystyle(\Gamma\circ\Delta_{g})[z,z^{\prime}]$
$\displaystyle=2^{f(z,z^{\prime})}\chi_{[f(g,z)\neq f(g,z^{\prime})]},$

where $\chi_{[f(g,z)\neq f(g,z^{\prime})]}$ stands for the indicator function
of the condition $f(g,z)\neq f(g,z^{\prime})$. Let
$\Gamma_{g}:=\Gamma\circ\Delta_{g}$. We will show an upper bound on
$\left\lVert\Gamma_{g}\right\rVert$. We decompose $\Gamma_{g}$ in an “upper-
triangular” and a “lower-triangular” part:

$\displaystyle\Gamma_{g}^{U}[z,z^{\prime}]$
$\displaystyle:=2^{f(z,z^{\prime})}\chi_{[f(g,z)<f(g,z^{\prime})]}=2^{f(g,z)}\chi_{[f(g,z)<f(g,z^{\prime})]},$
(10) $\displaystyle\Gamma_{g}^{L}[z,z^{\prime}]$
$\displaystyle:=2^{f(z,z^{\prime})}\chi_{[f(g,z^{\prime})<f(g,z)]}=2^{f(g,z^{\prime})}\chi_{[f(g,z^{\prime})<f(g,z)]}.$

So $\Gamma_{g}=\Gamma_{g}^{U}+\Gamma_{g}^{L}$ and
$\Gamma_{g}^{U}=(\Gamma_{g}^{L})^{T}$. Hence by the triangle inequality we
have

$\left\lVert\Gamma_{g}\right\rVert\leq\left\lVert\Gamma_{g}^{U}\right\rVert+\left\lVert\Gamma_{g}^{L}\right\rVert=2\left\lVert\Gamma_{g}^{U}\right\rVert.$
(11)

It thus suffices to upper bound $\left\lVert\Gamma_{g}^{U}\right\rVert$.
Notice that as (10) shows, $\Gamma_{g}^{U}[z,z^{\prime}]$ only depends on the
values $f(g,z)$, $f(g,z^{\prime})$. Since the range of $f(g,\,\cdot\,)$ is
$[n+1]$, we can think of $\Gamma_{g}^{U}$ as an $(n+1)\times(n+1)$ block-
matrix, where the blocks are determined by the values of $f(g,z)$ and
$f(g,z^{\prime})$, and within a block all matrix elements are the same. Also
observe that for all $k\in[n]$ there are $2^{n-k}$ bitstrings
$y\in\\{0,1\\}^{n}$ such that $f(g,y)=k$, which tells us the sizes of the
blocks are $2^{n-k}\times 2^{n-k}$. Motivated by these observations we define
an orthonormal set of vectors in $\mathbb{R}^{2^{n}}$ by $v_{n+1}:=e_{g}$, and
for all $k\in[n]$

$\displaystyle v_{k}:=\sum_{y:f(g,y)=k}\frac{e_{y}}{\sqrt{2^{n-k}}}.$

Since the row and column spaces of $\Gamma_{g}^{U}$ are spanned by
$\\{v_{k}:k\in[n+1]\\}$, we can reduce $\Gamma_{g}^{U}$ to an
$(n+1)\times(n+1)$-dimensional matrix $G$:

$\Gamma_{g}^{U}=\left(\sum_{k=1}^{n+1}v_{k}v_{k}^{T}\right)\Gamma_{g}^{U}\left(\sum_{\ell=1}^{n+1}v_{\ell}v_{\ell}^{T}\right)=\left(\sum_{k=1}^{n+1}v_{k}e_{k}^{T}\right)\underbrace{\left(\sum_{k=1}^{n+1}e_{k}v_{k}^{T}\right)\Gamma_{g}^{U}\left(\sum_{\ell=1}^{n+1}v_{\ell}e_{\ell}^{T}\right)}_{G:=}\left(\sum_{\ell=1}^{n+1}e_{\ell}v_{\ell}^{T}\right).$

It follows from the above identity, together with the orthonormality of
$\\{v_{1},\ldots,v_{n},v_{n+1}\\}$, that

$\left\lVert\Gamma_{g}^{U}\right\rVert=\left\lVert\left(\sum_{k=1}^{n+1}e_{k}v_{k}^{T}\right)\Gamma_{g}^{U}\left(\sum_{\ell=1}^{n+1}v_{\ell}e_{\ell}^{T}\right)\right\rVert=\left\lVert
G\right\rVert.$ (12)

$G\in\mathbb{R}^{(n+1)\times(n+1)}$ is a strictly upper-triangular matrix,
with the following entries for $k,\ell\in[n]$:

$\displaystyle G[k,\ell]$ $\displaystyle=v_{k}^{T}\Gamma_{g}^{U}v_{\ell}$
$\displaystyle=\left(\sum_{z:f(g,z)=k}\frac{e_{z}^{T}}{\sqrt{2^{n-k}}}\right)\Gamma_{g}^{U}\left(\sum_{z^{\prime}:f(g,z^{\prime})=\ell}\frac{e_{z^{\prime}}}{\sqrt{2^{n-\ell}}}\right)$
$\displaystyle=\frac{2^{\frac{k+\ell}{2}}}{2^{n}}\left(\sum_{z:f(g,z)=k}e_{z}^{T}\right)\Gamma_{g}^{U}\left(\sum_{z^{\prime}:f(g,z^{\prime})=\ell}e_{z^{\prime}}\right)$
$\displaystyle=\frac{2^{\frac{k+\ell}{2}}}{2^{n}}\sum_{z:f(g,z)=k}\sum_{z^{\prime}:f(g,z^{\prime})=\ell}\Gamma_{g}^{U}[z,z^{\prime}]$

By Equation (10) this is further equal to

$\displaystyle G[k,\ell]$
$\displaystyle=\frac{2^{\frac{k+\ell}{2}}}{2^{n}}\sum_{z:f(g,z)=k}\sum_{z^{\prime}:f(g,z^{\prime})=\ell}2^{k}\chi_{[k<\ell]}$
$\displaystyle=\frac{2^{\frac{k+\ell}{2}}}{2^{n}}2^{n-k}2^{n-\ell}2^{k}\chi_{[k<\ell]}$
$\displaystyle=2^{n-\frac{\ell-k}{2}}\chi_{[k<\ell]}.$

Similarly for $\ell=n+1$ we get that
$G[k,\ell]=\sqrt{2}\,2^{n-\frac{\ell-k}{2}}\chi_{[k<\ell]}$ for all
$k\in[n+1]$. For each $d\in[n]$ define $G_{d}\in\mathbb{R}^{(n+1)\times(n+1)}$
such that $G_{d}[k,\ell]=G[k,\ell]\chi_{[d=\ell-k]}$. This $G_{d}$ is only
non-zero on one non-main diagonal (namely the $(k,\ell)$-entries where
$d=\ell-k$), and its non-zero entries are all upper bounded by
$\sqrt{2}\,2^{n}2^{-\frac{d}{2}}$. We have $G=\sum_{d=1}^{n}G_{d}$ and
therefore

$\left\lVert G\right\rVert\leq\sum_{d=1}^{n}\left\lVert
G_{d}\right\rVert\leq\sum_{d=1}^{n}\sqrt{2}\,2^{n}2^{-\frac{d}{2}}=2^{n}\sum_{d=0}^{n-1}(\sqrt{2})^{-d}\leq\frac{2^{n}}{1-1/\sqrt{2}}\leq
2^{n+2}.$ (13)

Inequalities (11)-(13) give that $\left\lVert\Gamma_{g}\right\rVert\leq
2^{n+3}$ and hence (9) yields a lower bound of
$\Omega\left(\frac{n2^{n}}{2^{n+3}}\right)=\Omega(n)$ on the number of quantum
queries to $O_{z}$ needed to learn $z$. ∎

######  Theorem 27.

Finding a point in $B_{\infty}(K,1/7)$ for an unknown convex set $K$ such that
$K\subseteq B_{\infty}(0,2)\subseteq\mathbb{R}^{n}$ requires $\Omega(n)$
quantum queries to a separation oracle $\mathrm{SEP}_{0,0}(K)$, even if we are
promised there exists some unknown $x\in\mathbb{R}^{n}$ such that
$B_{\infty}(x,1/3)\subseteq K$.

###### Proof.

We will prove an $\Omega(n)$ quantum query lower bound for this problem by a
reduction from learning with first-difference queries. Let $z\in\\{0,1\\}^{n}$
be an unknown binary string, and let us define
$K_{z}:=B_{\infty}(z,1/3)\subset\mathbb{R}^{n}$ as a small box around the
corner of the hypercube corresponding to $z$. Then clearly $K_{z}\subset
B_{\infty}(0,2)$, and finding a point close enough to $K_{z}$ is enough to
recover $z$.

We can easily reduce a separation oracle query to a first-difference query to
$z$, as follows. Suppose $y$ is the vector for which we need to answer a SEP
query:

  1. 1.

If $y$ is outside $[-1/3,4/3]^{n}$, then output a hyperplane separating $y$
from $[-1/3,4/3]^{n}$.

  2. 2.

If $y$ is in $[-1/3,4/3]^{n}$, then let $g$ be the nearest corner of the
hypercube.

  3. 3.

Let $i$ be the result of a first-difference query to $z$ with $g$.

    1. (a)

If $i=n+1$, indicating that $z=g$, then we know $K_{z}$ exactly, so we can
find a separating hyperplane or conclude that $y\in K_{z}$.

    2. (b)

If $z\neq g$, then return $e_{i}$ if $g_{i}=1$, and $-e_{i}$ if $g_{i}=0$.

Hence our $\Omega(n)$ quantum lower bound on learning $z$ with first-
difference queries implies an $\Omega(n)$ lower bound on the number of quantum
queries to a separation oracle needed for finding a point close to a convex
set. ∎

Since optimization over a set $K$ gives a point close to the set $K$, this
also implies a lower bound on the number of separation queries needed for
optimization. This theorem is tight up to logarithmic factors, since it is
known that $\widetilde{\mathcal{O}}\left(n\right)$ classical separation
queries suffice for optimization, even without knowing a point in the convex
set [LSW15]. Finally we remark that, due to our improved algorithm for
optimization using validity queries (by combining Section 6 with Theorem 23),
this also gives an $\widetilde{\Omega}(n)$ lower bound on the number of
separation queries needed to implement validity.161616It is easy to modify
Theorem 26 to prove a lower bound on computing the majority function applied
to $z$, which would imply an $\Omega(n)$ lower bound on the number of
separation queries needed to implement a validity oracle, without the log
factors.

##  6 Consequences of convex polarity

Here we justify the central symmetry of Figure 1 using the results of
Grötschel, Lovász, and Schrijver [GLS88, Section 4.4]. We first need to recall
the definition and some basic properties of the polar $K^{*}$ of a set
$K\subseteq\mathbb{R}^{n}$. This is the closed convex set defined as follows:

$K^{*}=\\{y\in\mathbb{R}^{n}:\langle y,x\rangle\leq 1\text{ for all }x\in
K\\}.$

It is straightforward to verify that if $B(0,r)\subseteq K\subseteq B(0,R)$,
then $B(0,1/R)\subseteq K^{*}\subseteq B(0,1/r)$, moreover $(K^{*})^{*}=K$ for
closed convex sets.171717Note that $K^{*}$ is a dual representation of the
convex set $K$. Each point in $K^{*}$ corresponds to a (normalized) valid
inequality for $K$. This duality is not to be confused with Lagrangian
duality. For the remainder of this section we assume that $K$ is a closed
convex set such that $B(0,r)\subseteq K\subseteq B(0,R)$.

We will observe that for the polar $K^{*}$ of a set $K$ the following holds:

$\mathrm{MEM}(K^{*})\leftrightarrow\mathrm{VAL}(K),\qquad\mathrm{SEP}(K^{*})\leftrightarrow\mathrm{VIOL}(K),$
(14)

where $\mathrm{MEM}(K^{*})\leftrightarrow\mathrm{VAL}(K)$ means we can
implement a weak validity oracle for $K$ using a single query to a weak
membership oracle for $K^{*}$, and vice versa. Since $\mathrm{VIOL}(K)$ and
$\mathrm{OPT}(K)$ are equivalent up to reductions that use
$\widetilde{\Theta}(1)$ queries (via binary search), this justifies the
central symmetry of Figure 1, because it shows that algorithms that implement
$\mathrm{VIOL}(K)$ given $\mathrm{VAL}(K)$ are equivalent to algorithms that
implement $\mathrm{SEP}(K^{*})$ given $\mathrm{MEM}(K^{*})$, and similarly
algorithms that implement $\mathrm{SEP}(K)$ given $\mathrm{VIOL}(K)$ are
equivalent to algorithms that implement $\mathrm{VIOL}(K^{*})$ given
$\mathrm{SEP}(K^{*})$.

Grötschel, Lovász, and Schrijver [GLS88, Section 4.4] showed that the weak
membership problem for $K^{*}$ can be solved using a single query to a weak
validity oracle for $K$, and that the weak separation problem for $K^{*}$ can
be solved using a single query to a weak violation oracle for $K$. Using
similar arguments one can show the reverse directions as well, which justifies
(14). Here we only motivate the equivalences between the above-mentioned weak
oracles by showing the equivalence of the strong oracles (i.e., where $\rho$
and $\varepsilon$ are $0$).

#### Strong membership on $K^{*}$ is equivalent to strong validity on $K$.

First, for a given vector $c\in\mathbb{R}^{n}$ and a $\gamma>0$ observe the
following:

$\frac{c}{\gamma}\not\in\mathrm{int}(K^{*})\quad\Longleftrightarrow\quad\exists
y\in K\text{ s.t.\ }\langle c/\gamma,y\rangle\geq
1\quad\Longleftrightarrow\quad\exists y\in K\text{ s.t. }\langle
c,y\rangle\geq\gamma.$

Hence, a strong membership query to $K^{*}$ with a point $c$ can be
implemented by querying a strong validity oracle for $K$ with the vector $c$
and the value $1$. Likewise, a strong validity query to $K$ with a point $c$
and value181818Observe that validity queries with value $\gamma\leq 0$ can be
answered trivially, since $0\in K$. $\gamma>0$ can be implemented using a
strong membership query to $K^{*}$ with $c/\gamma$.

#### Strong separation on $K^{*}$ is equivalent to strong violation on $K$.

To implement a strong separation query on $K^{*}$ for a vector
$y\in\mathbb{R}^{n}$ we do the following. Query the strong violation oracle
for $K$ with $y$ and the value $1$. If the answer is that $\langle
y,x\rangle\leq 1$ for all $x\in K$, then $y\in K^{*}$. If instead we are given
a vector $x\in K$ with $\langle y,x\rangle\geq 1$, then $x$ separates $y$ from
$K^{*}$ (indeed, for all $z\in K^{*}$, we have $\langle z,x\rangle\leq
1\leq\langle y,x\rangle$).

For the reverse direction, to implement a strong violation oracle for $K$ on
the vector $c$ and value18 $\gamma>0$ we do the following. Query the strong
separation oracle for $K^{*}$ with the point $c/\gamma$. If the answer is that
$c/\gamma\in K^{*}$ then $\langle c,x\rangle\leq\gamma$ for all $x\in K$. If
instead we are given a non-zero vector $y\in\mathbb{R}^{n}$ that satisfies
$\langle c/\gamma,y\rangle\geq\langle z,y\rangle$ for all $z\in K^{*}$, then
$\tilde{y}=y/\langle c/\gamma,y\rangle$ will be a valid answer for the strong
violation oracle for $K$. Indeed, we have $\tilde{y}\in K$ because $\langle
z,\tilde{y}\rangle\leq 1$ for all $z\in K^{*}$ and $K=(K^{*})^{*}$, and by
construction $\langle c,\tilde{y}\rangle=\gamma$.

##  7 Discussion and future work

We mention several open problems for future work:

  * •

Our current implementation of an optimization query using
$\widetilde{\mathcal{O}}\left(n\right)$ quantum membership queries is
quadratically better than the best known classical randomized algorithm, which
uses roughly $n^{2}$ membership queries. However, to the best of our knowledge
it is open whether this quadratic classical bound is optimal (a quadratic
classical lower bound is known for _deterministic_ algorithms [Yao75]).

  * •

Can we improve our $\Omega(\sqrt{n})$ lower bound on the number of separation
(or membership) queries needed to implement an optimization oracle when our
algorithm knows a point in $K$? We conjecture that the correct bound is
$\tilde{\Theta}(n)$, in which case knowing a point in $K$ does not confer much
benefit for query complexity.

  * •

Are there interesting convex optimization problems where separation is much
harder than membership for classical computers?191919Moment polytopes are
promising candidates for such examples. Recently an efficient weak membership
oracle was constructed by Bürgisser et al. [BFG+18] for a class of these
polytopes. However, to the best of our knowledge it is unknown how to directly
implement separation oracles for them, so one might get a quantum speed-up for
implementing separation oracles using few queries to their membership oracle.
Such problems would be good candidates for quantum speed-up in optimization in
the real, non-oracle setting of time complexity. It is known that given a
deterministic algorithm for function evaluation, an algorithm with roughly the
same complexity can be constructed to compute the gradient of that function
[GW08]. Hence for strong, deterministic oracles, separation is not much harder
than membership queries. This, however, still leaves weak / randomized /
quantum membership oracles to be considered.

  * •

The algorithms that give an $\widetilde{\mathcal{O}}\left(n\right)$ upper
bound on the number of separation queries for optimization (for example
[LSW15, Theorem 42]) give the best theoretical results for many convex
optimization problems. However, due to the large constants in these algorithms
they are rarely used in a practical setting. A natural question is whether the
algorithms used in practice lend themselves to quantum speed-ups. Very recent
work by Kerenidis and Prakash [KP18] on quantum interior point methods is a
first step in this direction.

#### Acknowledgments.

We thank Shouvanik Chakrabarti, Andrew Childs, Tongyang Li, and Xiaodi Wu for
sending us a preliminary version of their paper [CCLW18], and for useful
comments and coordination between our two papers. AG thanks Márió Szegedy for
insightful discussions. Many thanks to the anonymous referees of QIP’19 and
Quantum for their constructive comments.

JvA and SG are supported by the Netherlands Organization for Scientific
Research (NWO), grant number 617.001.351. AG and RdW are supported by ERC
Consolidator Grant 615307-QPROGRESS. RdW is also partially supported by NWO
through Gravitation-grant Quantum Software Consortium - 024.003.037, and
through QuantERA project QuantAlgo 680-91-034.

## References

  * [Amb99] Andris Ambainis.  A better lower bound for quantum algorithms searching an ordered list.  In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS), pages 352–357, 1999.  arXiv: quant-ph/9902053
  * [vAG19] Joran van Apeldoorn and András Gilyén.  Improvements in quantum SDP-solving with applications.  In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 99:1--99:15, 2019.  arXiv: 1804.05058
  * [vAGGdW17] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf.  Quantum SDP-solvers: Better upper and lower bounds.  In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS), pages 403--414, 2017.  arXiv: 1705.01843
  * [AŠ06] Andris Ambainis and Robert Špalek.  Quantum algorithms for matching and network flows.  In Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS), pages 172--183, 2006.  arXiv: quant-ph/0508205
  * [BBBV97] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani.  Strengths and weaknesses of quantum computing.  SIAM Journal on Computing, 26(5):1510--1523, 1997.  arXiv: quant-ph/9701001
  * [BFG+18] Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson.  Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes.  In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS), pages 883--897, 2018.  arXiv: 1804.04739
  * [BKL+19] Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu.  Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning.  In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 27:1--27:14, 2019.  arXiv: 1710.02581
  * [BS17] Fernando G. S. L. Brandão and Krysta M. Svore.  Quantum speed-ups for solving semidefinite programs.  In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS), pages 415--426, 2017.  arXiv: 1609.05537
  * [Bub15] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  Foundations and Trends in Machine Learning, 8(3--4):231--357, 2015\.  arXiv: 1405.4980
  * [CCLW18] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu.  Quantum algorithms and lower bounds for convex optimization.  arXiv: 1809.01731, 2018.
  * [DH96] Christoph Dürr and Peter Høyer.  A quantum algorithm for finding the minimum.  arXiv: quant-ph/9607014, 1996.
  * [DHHM06] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla.  Quantum query complexity of some graph problems.  SIAM Journal on Computing, 35(6):1310--1328, 2006.  arXiv: quant-ph/0401091
  * [GAW19] András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe.  Optimizing quantum optimization algorithms via faster quantum gradient computation.  In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1425--1444, 2019.  arXiv: 1711.00465
  * [GLS88] Martin Grötschel, László Lovász, and Alexander Schrijver.  Geometric Algorithms and Combinatorial Optimization.  Springer, 1988.
  * [Gro96] Lov K. Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the 28th ACM Symposium on the Theory of Computing (STOC), pages 212--219, 1996.  arXiv: quant-ph/9605043
  * [GW08] Andreas Griewank and Andrea Walther.  Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation.  SIAM, second edition, 2008.
  * [HLŠ07] Peter Høyer, Troy Lee, and Robert Špalek.  Negative weights make adversaries stronger.  In Proceedings of the 39th ACM Symposium on the Theory of Computing (STOC), pages 526--535, 2007.  arXiv: quant-ph/0611054
  * [Jor05] Stephen P. Jordan.  Fast quantum algorithm for numerical gradient estimation.  Physical Review Letters, 95(5):050501, 2005.  arXiv: quant-ph/0405146
  * [Jor08] Stephen P. Jordan.  Quantum Computation Beyond the Circuit Model.  PhD thesis, Massachusetts Institute of Technology, 2008.  arXiv: 0809.2307
  * [KP18] Iordanis Kerenidis and Anupam Prakash.  A quantum interior point method for LPs and SDPs.  arXiv: 1808.09266, 2018.
  * [LSV18] Yin Tat Lee, Aaron Sidford, and Santosh S. Vempala.  Efficient convex optimization with membership oracles.  In Proceedings of the 31st Conference On Learning Theory (COLT), pages 1292--1294, 2018.  arXiv: 1706.07357
  * [LSW15] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong.  A faster cutting plane method and its implications for combinatorial and convex optimization.  In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), pages 1049--1065, 2015.  arXiv: 1508.04874
  * [NC00] Michael A. Nielsen and Isaac L. Chuang.  Quantum computation and quantum information.  Cambridge University Press, 2000.
  * [Szeg04] Márió Szegedy.  Quantum speed-up of Markov chain based algorithms.  In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), pages 32--41, 2004.  arXiv: quant-ph/0401053
  * [Yao75] Andrew Chi-Chih Yao.  On computing the minima of quadratic forms (preliminary report).  In Proceedings of the 7th ACM Symposium on the Theory of Computing (STOC), pages 23--26, 1975.

##  Appendix A Quantum gradient computation using relational oracles

In this appendix we extend the result of Corollary 15 to functions given by a
relational input oracle. As a direct consequence this shows that the algorithm
from Theorem 23 also works when the input is given as a relational membership
oracle instead of a standard oracle.

######  Definition 28 (Unitary $\delta$-approximator).

Let $X$ be a finite set and let $Y$ denote a set of fixed-point $b$-bit
numbers. Let $f\colon X\to Y$ be a function. We say that a relational quantum
oracle $U$ on $X$ is a _$b$ -bit unitary $\delta$-approximator of $f$_ if the
valid answers for each $x\in X$ differ at most $\delta$ from $f(x)$ (i.e.,
$\mathcal{F}(x)=\\{y\in Y\colon|f(x)-y|\leq\delta\\}$), and the success
probability is at least $\frac{2}{3}$.

######  Corollary 29 (Gradient computation using a unitary
$\delta$-approximator).

Let $\delta,B,r,c\in\mathbb{R}$, $\rho\in(0,1/3]$. Let
$x_{0},g\in\mathbb{R}^{n}$ with $\left\lVert
g\right\rVert_{\infty}\leq\frac{B}{r}$. Let
$m:=\left\lceil\log_{2}\left(\frac{B}{28\pi\delta}\right)\right\rceil$ and
suppose $f:\left(x_{0}+rG_{m}^{n}\right)\to\mathbb{R}$ is such that

$\left|f(x_{0}+rx)-\left\langle g,rx\right\rangle-c\right|\leq\delta$

for 99.9% of the points $x\in G_{m}^{n}$, and we have access to $U$, an
$\mathcal{O}\left(\log\left(\\!\frac{B}{\delta}\\!\right)\right)$-bit unitary
$\delta$-approximator of $f$ over the domain $\left(x_{0}+rG_{m}^{n}\right)$.
Then we can compute a vector $\tilde{g}\in\mathbb{R}^{n}$ such that

$\Pr\left[\,\left\lVert\tilde{g}-g\right\rVert_{\infty}>\\!\frac{8\cdot
42\pi\delta}{r}\right]\leq\rho,$

with $\mathcal{O}\left(\\!\log\\!\big{(}\frac{n}{\rho}\big{)}\\!\right)$
queries to $U$ and $U^{\dagger}$ and gate complexity
$\mathcal{O}\left(\\!n\log\\!\big{(}\frac{n}{\rho}\big{)}\\!\log\\!\big{(}\\!\frac{B}{\delta}\\!\big{)}\\!\log\\!\log\\!\big{(}\frac{n}{\rho}\big{)}\\!\log\\!\log\\!\big{(}\\!\frac{B}{\delta}\\!\big{)}\\!\right)\\!$.

###### Proof.

The algorithm is the same as in the less general Corollary 15 presented in
Section 3.2, we just need to analyze it a bit more carefully. The main idea is
still to implement an approximate version of the phase oracle
$\mathrm{O}:|x,0,0\rangle\mapsto e^{2\pi
i\frac{M}{3B}f(x_{0}+rx)}|x,0,0\rangle$, and then use Jordan’s gradient
computation algorithm. We approximate $\mathrm{O}$ by first approximately
computing $f$ using $U$, then applying202020If $y$ is a $b$-bit fixed-point
binary number, then this can be implemented using $b$ single-qubit phase gates
as follows: we can assume without loss of generality that
$y=a_{0}+a\cdot\sum_{j=1}^{b}y_{j}2^{j}$ for some fixed
$a_{0},a\in\mathbb{R}$. Then $e^{2\pi i\frac{M}{3B}y}=e^{2\pi
i\frac{M}{3B}a_{0}}\prod_{j=1}^{b}e^{2\pi i\frac{M}{3B}ay_{j}2^{j}}$. The
global phase is irrelevant, and the other phase factors can be implemented by
using $b$ single-qubit phase gates, each acting as $|y_{j}\rangle\mapsto
e^{2\pi i\frac{M}{3B}ay_{j}2^{j}}|y_{j}\rangle$.  a controlled phase operation
$\mathrm{cP}$ acting as $\mathrm{cP}\colon|y\rangle\mapsto e^{2\pi
i\frac{M}{3B}y}|y\rangle$ (where $M=\frac{3B}{84\pi\delta}$ as in the proof of
Corollary 15), and finally applying $U^{\dagger}$ to approximately uncompute
$f$.

We can assume without loss of generality that our unitary
$\delta$-approximator is such that the probability of
$\left|f(x)-y\right|>\delta$ is at most $\frac{1}{1200}$. If this is not the
case, we can improve the success probability by querying $U$ a few times and
taking the median of the results.

Let us define $\mathcal{F}(x):=\\{y\in
Y\colon\left|f(x)-y\right|\leq\delta\\}$ as in Definition 28. Observe that

$\displaystyle\left\lVert\mathrm{O}|x,0,0\rangle-U^{\dagger}\left(I\otimes\mathrm{cP}\otimes
I\right)U|x,0,0\rangle\right\rVert^{2}$
$\displaystyle=\left\lVert\left(I\otimes(e^{2\pi
i\frac{M}{3B}f(x_{0}+rx)}I-\mathrm{cP})\otimes
I\right)U|x,0,0\rangle\right\rVert^{2}$ $\displaystyle=\left\lVert\sum_{y\in
Y}\left(e^{2\pi i\frac{M}{3B}f(x_{0}+rx)}-e^{2\pi
i\frac{M}{3B}y}\right)\alpha_{x,y}|x,y,\psi_{x,y}\rangle\right\rVert^{2}.$

We bound the above quantity in two parts using the triangle inequality as
follows:

$\displaystyle\\!\left\lVert\sum_{y\in Y\setminus\mathcal{F}(x)}\left(e^{2\pi
i\frac{M}{3B}f(x_{0}+rx)}-e^{2\pi
i\frac{M}{3B}y}\right)\alpha_{x,y}|x,y,\psi_{x,y}\rangle\right\rVert^{2}$
$\displaystyle\\!\\!\\!\leq\\!\\!\\!\sum_{y\in
Y\setminus\mathcal{F}(x)}|2\alpha_{x,y}|^{2}\leq\frac{1}{300};$
$\displaystyle\left\lVert\sum_{y\in\mathcal{F}(x)}\left(e^{2\pi
i\frac{M}{3B}f(x_{0}+rx)}-e^{2\pi
i\frac{M}{3B}y}\right)\alpha_{x,y}|x,y,\psi_{x,y}\rangle\right\rVert^{2}$
$\displaystyle\\!\\!\\!\leq\\!\sum_{y\in\mathcal{F}(x)}\left|2\pi
i\frac{M}{3B}(f(x_{0}+rx)-y)\alpha_{x,y}\right|^{2}$
$\displaystyle\\!\\!\\!\leq\\!\sum_{y\in Y_{x}}\left|2\pi
i\frac{M}{3B}\delta\right|^{2}\left|\alpha_{x,y}\right|^{2}$
$\displaystyle\\!\\!\\!\leq\left|2\pi
i\frac{M}{3B}\delta\right|^{2}=\frac{1}{42^{2}}.$

Thus for all $x\in G_{m}^{n}$ we have that

$\left\lVert\mathrm{O}|x,0,0\rangle-U^{\dagger}\left(I\otimes\mathrm{cP}\otimes
I\right)U|x,0,0\rangle\right\rVert\leq\sqrt{\frac{1}{300}+\frac{1}{42^{2}}}<\frac{1}{16}.$
(15)

We can assume without loss of generality that our approximate phase oracle
does not change the value of the input register. Otherwise we can just copy
$|x\rangle$ to another register, then apply our approximate phase oracle on
the second copy, then (approximately) erase the second copy of $|x\rangle$
using mod $2$ bitwise addition with the first copy. Under this assumption by
(15) we get that

$\left\lVert\mathrm{O}|\psi\rangle-U^{\dagger}\left(I\otimes\mathrm{cP}\otimes
I\right)U|\psi\rangle\right\rVert<\frac{1}{16},\text{ for any quantum state
}|\psi\rangle=\sum_{x\in G_{m}^{n}}\alpha_{x}|x,0,0\rangle.$ (16)

From now on the proof is the same as the proof of Corollary 15. In that proof
we showed that if we use the phase oracle $\mathrm{O}$ in Jordan’s gradient
computation algorithm, then we would get a gradient estimate where each
individual coordinate has the required approximation quality with probability
at least $\frac{2}{3}$. Equation (16) implies that if instead we use our
approximate implementation of the phase oracle, $U^{\dagger}\left(I\otimes
cP\otimes I\right)U$, then the outcome probability distribution changes by at
most $\frac{1}{16}$ in total variation distance. So one run of Jordan’s
algorithm using this approximate phase oracle still outputs a vector
$v\in\mathbb{R}^{n}$ such that

$\Pr\left[\left|g_{i}-\frac{3B}{r}v_{i}\right|>\frac{8\cdot
42\pi\delta}{r}\right]\leq\frac{1}{3}+\frac{1}{16}<\frac{2}{5}\text{ for every
}i\in[n].$

As in the proof of Corollary 15, repeating the whole procedure
$\mathcal{O}\left(\log(\frac{n}{\rho})\right)$ times, and taking the median of
the resulting vectors coordinatewise, gives a gradient approximator
$\tilde{g}$ of the desired quality. The gate complexity analysis follows from
[GAW19, Theorem 21], noting that each controlled phase operation $cP$ can be
implemented using
$\mathcal{O}\left(\log\left(\\!\frac{B}{\delta}\\!\right)\right)$ single-qubit
phase gates. ∎