$\displaystyle\overline{T}(1)$ $\displaystyle=O(\log
n^{*}+\mathrm{QW}_{O(n^{*})})$ $\displaystyle\overline{T}(n)$
$\displaystyle\leq c\sqrt{h}(\overline{T}(n/h)+f(n))+f(n)\enspace.$

By taking $h=2c^{6}$, the solution to this recurrence becomes
$\widetilde{O}(n^{2/3})\cdot\mathrm{QW}_{O(n^{*})}+O(\sqrt{n}\log n^{*})$ as
claimed.

For the query complexity, let
$g(n)=O(n^{2/3}\log(n)\cdot\mathrm{QW}_{O(n^{*})}$ be an upper bound on the
query complexity of the create and completion functions from Theorem 37. By
Theorem 27 and Theorem 37, the query complexity $T(n)$ for
$\textsc{BLDS}(\alpha,\mathcal{I})$ satisfies the following recurrence
relation for any $h\geq 2$:

$\displaystyle T(1)$ $\displaystyle=O(1)$ $\displaystyle T(n)$
$\displaystyle=c\sqrt{h}(T(n/h)+g(n))+g(n)\enspace.$

Again taking $h=2c^{6}$, the solution to this recurrence becomes
$O(n^{2/3}\cdot\log(n))$. ∎

###  6.2 Application to LDS

Finally, we can use the algorithm for BLDS as part of a bottom-up algorithm
for LDS.

######  Theorem 39.

There is a quantum algorithm that solves LDS in time
$\widetilde{O}(n^{2/3})\cdot\mathrm{QW}_{O(n)}$ and a quantum algorithm that
solves LDS with $O(n^{2/3}\log(n)\log\log(n))$ queries.

###### Proof.

We use the bottom-up approach. Let the input be $a\in\Sigma^{n}$. We can pad
the input by repeating the last character without changing the length of a
longest distinct substring. Thus we may assume $n$ is a power of 2 without
changing the asymptotic complexity.

Let $P(a,t,k)$ be the length of a longest distinct substring of $a$ contained
in the interval $\\{(k-1)n/2^{t}+1,\ldots,kn/2^{t}\\}$, with the left endpoint
in the left half of this interval and right endpoint in the right half of this
interval. Letting
$i_{1}=(k-1)n/2^{t}+1,i_{2}=(2k-1)n/2^{t+1},j_{1}=(2k-1)n/2^{t+1}+1,j_{2}=kn/2^{t}$
and $\mathcal{I}=(i_{1},i_{2},j_{1},j_{2})$ we see that
$P(a,t,k)=\textsc{BLDS}(a,\mathcal{I})$. Thus by Theorem 38 there is a quantum
algorithm that outputs $P(a,t,k)$ with probability at least $9/10$ in time
$\widetilde{O}(n^{2/3}/2^{2t/3}\cdot\mathrm{QW}_{O(n)})$ and with
$O(n^{2/3}/2^{2t/3}\log(n/2^{t})$ queries. Applying Theorem 9 gives a quantum
algorithm for LDS with running time
$\widetilde{O}(n^{2/3})\cdot\mathrm{QW}_{O(n)}$ and a quantum algorithm with
query complexity $O(n^{2/3}\log(n)\log\log(n))$. ∎

##  7 Klee’s Coverage

Given a set $\cal B$ of $n$ axis-parallel hyperrectangles (boxes) in
$d$-dimensional real space $\mathbb{R}^{d}$, the Klee’s Measure problem asks
to compute the volume of the union of the boxes in $\cal B$. A special case is
the Klee’s Coverage problem where we are also given a base box $\Gamma$, and
the question is to decide whether the union of the boxes in $\cal B$ covers
$\Gamma$. In 2-dimensions the complexity of the Klee’s Measure problem is
$O(n\log n)$ [Kle77], and for any constant $d\geq 3$, Chan [Cha13] has given
an $O(n^{d/2})$ time classical algorithm for it.

######  Problem 40 (Klee’s Coverage).

Given a set $\cal B$ of $n$ axis-parallel boxes and a base box $\Gamma$ in
$\mathbb{R}^{d}$, is $\Gamma\subseteq\cup_{B\in{\cal B}}B$?

We give a quantum algorithm for Klee’s Coverage that achieves an almost
quadratic speedup over the classical divide and conquer algorithm of Chan
[Cha13], when $d\geq 8$. The speedup is less than quadratic for $5\leq n\leq
7$, and there is no quantum speedup for $n\leq 4$.

######  Theorem 41.

For every constant $\varepsilon>0$, the quantum time complexity of the Klee’s
Coverage problem is $O(n^{d/4+\varepsilon}\cdot\mathrm{QW}_{N(n)})$ when
$d\geq 8$, and is $O(n^{2}\cdot\mathrm{QW}_{N(n)})$ for $5\leq d\leq 7$, where
$N(n)=O(n^{d/2+\varepsilon})$.

Informally it is easy to see why the problem can be solved by a divide and
conquer algorithm: if the base box $\Gamma$ is divided into an arbitrary
number of base sub-boxes, then $\Gamma$ is not covered by ${\cal B}$ if and
only if there is a base sub-box which is not covered by ${\cal B}$. However,
such a division should also ensure that for every base sub-box, the number of
boxes in ${\cal B}$ intersecting it also gets appropriately reduced, a highly
non-trivial task. Chan’s classical divide and conquer algorithm achieves
exactly that by using a weighting scheme, and our quantum divide and conquer
algorithm essentially follows the classical algorithm of Chan. Still, we need
a couple of modifications. Besides the quantum procedures in our algorithm, we
will divide an instance into $h$ sub-instances and not into $2$, where $h$ is
a sufficiently large constant to be specified later. We also use padding in
the create step to ensure the uniform size of the subproblems.

###### Proof.

We start with a few preliminary remarks. First observe that the boxes in $\cal
B$ cover $\Gamma$ exactly when they cover $\mathrm{Int}(\Gamma)$, the interior
of $\Gamma$. By an instance of length $n$ we mean an instance $a=(\Gamma,{\cal
B})$ where the number of boxes in $\cal B$ is $n-1$, with the base box
$\Gamma$ bringing the total length of the instance to $n$. As we have
observed, Klee’s Coverage is a natural constructible instance
$(h,m)$-disjunctive problem with a trivial completion function, where $h$ can
be any constant, and given $h$, the value of the best $m$ requires some
reasoning. Therefore the algorithm itself is fully specified by the create
step that produces the $h$ constitutive strings. We suppose that the input
size is $n^{*}$.

In Chan’s description, the create step contains two distinct parts, called
simplification and cut, and we will complete this with a third part, padding.
In fact, the algorithm also contains a preprocessing step which should be
accounted for in the final complexity. In the preprocessing, we sort the input
boxes in each dimension. Since, in the $\mathsf{QRAG}$ model, coordinates can
be compared classically in time $O(\mathrm{QW}_{N(n^{*})})$, this takes time
$O(n^{*}\log n^{*}\cdot\mathrm{QW}_{N(n^{*})})$.

In the simplification step, we transform the problem into an instance without
slabs, that is without boxes in $\cal B$ which cover $\Gamma$ in each
dimension but one. Formally, a $k$-slab is a box whose restriction to $\Gamma$
is of the form $\\{(x_{1},\ldots,x_{d})\in\Gamma:a_{1}\leq x_{k}\leq
a_{2})\\}$, for some real numbers $a_{1}<a_{2}$. After the elimination of a
$k$-slab, the $k$th coordinates of all the base boxes and the other boxes are
changed accordingly, that is all regions between $a_{1}$ and $a_{2}$ are also
eliminated. The elimination of a slab might create new slabs, that is box
which was not a slab before the elimination might become one after. Therefore
the elimination process is done iteratively. We start with the family of boxes
containing all original slabs, we eliminate the elements of the family one by
one, while after each elimination we add the newly created slabs. The process
ends when we have an instance without any slab or we find a slab which fully
covers $\Gamma$. This can be done classically in
$O(n^{2}\cdot\mathrm{QW}_{N(n^{*})})$ time for pre-sorted inputs. In [Cha13]
the simplification is described without dealing with the elimination of the
freshly created slabs during the elimination process of the initial ones, and
it is claimed that this can be done in time $O(n)$. While doing the overall
elimination process in time $O(n^{2}\cdot\mathrm{QW}_{N(n^{*})})$ is easy,
doing it in linear time requires further proof that we don’t attempt here. The
slower elimination process changes the result only for $d<8$.

Without the elimination of the slabs, it is true that every box that doesn’t
fully cover $\Gamma$ has a $(d-1)$-face intersecting $\mathrm{Int}(\Gamma)$,
but slabs don’t have faces of dimension lower than this intersecting
$\mathrm{Int}(\Gamma)$. After the elimination of the slabs, the remaining
boxes have at least one $(d-2)$-face intersecting $\mathrm{Int}(\Gamma)$ which
makes possible a better complexity analysis of the algorithm.

The cut step is done with the help of a weight function that we define for
simplified instances. Let ${\cal F(B)}$ denote the set of $(d-2)$-faces of the
boxes in ${\cal B}$ that intersect $\mathrm{Int}(\Gamma)$. For every
$f\in{\cal F(B)}$ which is orthogonal to the $i$th and $j$th axes, we define
its weight as $w(f)=h^{(i+j)/d}$, and we define the weight of the instance
$a=(\Gamma,{\cal B})$ as $w(a)=\sum_{f\in{\cal F(B)}}w(f).$ The weight of a
$(d-2)$ face is at most $h^{2}$, and the number of $(d-2)$-faces per box is a
constant (depending on $d$). Therefore there exists a constant $\kappa>0$,
also depending on $d$, such that for every instance $a$ of length $n$, we have
$w(a)\leq\kappa n$.

The cut steps cycle over the $d$ dimensions. From instance $a=(\Gamma,{\cal
B})$ we create $h$ subproblems $b^{(k)}=(\Gamma_{k},{\cal B}_{k})$, for
$k\in[h].$ We cut the base box $\Gamma$ into $h$ sub-boxes
$\Gamma_{1},\ldots\Gamma_{h}$ by parallel hyperplanes which are orthogonal to
some axis. For technical simplicity, all the cuts will be described as
orthogonal to the first axis, and at the end of each iteration, the axes names
$(1,2,\ldots,d)$ will be cyclically permuted as $(d,1,\ldots,d-1)$. Let $W$ be
the sum of the weights of the $(d-2)$-faces in ${\cal F(B)}$ orthogonal to the
first axis. The cutting is done by $h-1$ hyperplanes
$x_{1}=v_{1},\ldots,x_{1}=v_{h-1}$ where the values $v_{1},\ldots,v_{h-1}$ are
chosen such that for every $1\leq k\leq h$, the total weight of the $(d-2)$
faces in ${\cal F(B)}$ orthogonal to the first axis and intersecting
$\mathrm{Int}(\Gamma_{k})$ is at most $W/h$. The boxes belonging to $b^{(k)}$
are chosen as ${\cal B}_{k}=\\{B\in{\cal
B}:B\cap\mathrm{Int}(\Gamma_{k})\neq\emptyset\\}.$ The cutting can be done
classically in $O(n\cdot\mathrm{QW}_{N(n^{*})})$ time.

After the cut step, the weight of a $(d-2)$-face parallel with the first axis
expressed in the permuted axes’ names is multiplied by $h^{-2/d}$, while the
weight of a $(d-2)$-face orthogonal to the first axis is multiplied by
$h^{(d-2)/d}$. Since the total weight of $(d-2)$ faces orthogonal to the first
axis inside the interior of each $\Gamma_{k}$ is divided by a factor of $h$,
altogether the total weight of the $(d-2)$-faces inside each sub-box decreases
by a factor of $h^{2/d}$, that is $w(b^{(k)})\leq w(a)/h^{2/d}$, for every
$k\in[h]$.

In order to be able to apply Theorem 23 we have to ensure that the
constitutive strings have all the same length, and we enforce this via
padding. Let us recall that $w(a)\leq\kappa|a|$, for some constant $\kappa>0$,
thus, for every $k\in[h]$, we have

$|b^{(k)}|\leq w(b^{(k)})\leq w(a)/h^{2/d}\leq\kappa|a|/h^{2/d}.$

For every $k\in[h]$, we define the constitutive string $a^{(k)}$ by repeating
some arbitrarily chosen box in ${\cal B}_{k}$ an appropriate number times to
make $|a^{(k)}|$ be equal to $\kappa|a|/h^{2/d}.$ Clearly negative instances
remain negative and positive instances remain positive by this transformation.
We can now apply Theorem 23 with the constant $m=h^{2/d}\cdot\kappa^{-1}$ and
we have an algorithm that solves the problem.

Let $\overline{T}(n^{*},n)$ denote the time complexity of the algorithm,
maximized over all _instances_ of length $n$. Then from Theorem 23 we have
$\overline{T}(n^{*},n)=O(\mathrm{QW}_{N(n^{*})})$, when $n$ is small, and

$\overline{T}(n^{*},n)\leq ch^{1/2}(\log
h+\overline{T}(n^{*},n/(h^{2/d}\cdot\kappa^{-1})))+O(n^{2}\cdot\mathrm{QW}_{N(n^{*})})\enspace,$

when $n$ is large. For $d\geq 8$, the solution of this is

$\overline{T}(n^{*},n)=O(n^{d/4+\varepsilon}\cdot\mathrm{QW}_{N(n^{*})}),$

if the constant $h$ is sufficiently large, for example if
$h>\max\\{c,\kappa\\}^{d^{2}/\varepsilon}$. For $5\leq d\leq 7$, we get
$\overline{T}(n^{*},n)=O(n^{2}\cdot\mathrm{QW}_{N(n^{*})})$. From a similar
recursion for the memory size, it is easy to see that
$N(n)=O(n^{d/2+\epsilon})$ when $d\geq 5$. The result follows when we take
$n=n^{*}$. ∎

##  8 Quantum complexity of some rectangle problems in $\bf{APSP}$

###  8.1 The problems and classical complexity

In this section, we will address the quantum complexity of two related
maximization problems on $n^{2}$ weighted points arranged in the plane in a
grid. They respectively look for a sub-rectangle with maximum sum, and for a
sub-rectangle where the sum of the 4 corner values with alternating signs is
maximum. We will need the following definitions where we think about the
points as contained in a matrix.

Given an $n\times n$ matrix $B$ and four indices $1\leq i\leq j\leq n$ and
$1\leq k\leq\ell\leq n$, we denote by $F_{B}((i,k),(j,\ell))$ the
4-combination $B_{ik}+B_{j\ell}-B_{i\ell}-B_{jk}$ and by
$S_{B}((i,k),(j,\ell))$ the sum

$\sum_{i\leq u\leq j,k\leq v\leq\ell}B_{uv}.$

######  Problem 42 (Maximum Submatrix (MSM)).

Given an $n\times n$ matrix $B$ of integers find a maximum weight submatrix,
that is

$\arg\max_{i\leq j,k\leq\ell}S_{B}((i,k),(j,\ell)).$

######  Problem 43 (Maximum 4-Combination (M4C)).

Given an $n\times n$ matrix $B$ of integers, find a maximum 4-combination,
that is

$\arg\max_{i\leq j,k\leq\ell}F_{B}((i,k),(j,\ell)).$

The MSM (also called Maximum Subarray) problem is a special case of a basic
problem in geometry, where given $N$ points in the plane, one has to find an
axis-parallel rectangle that maximizes the total weight of the points it
contains [DGM96, BCNP14]. The best-known algorithms run in time $O(N^{2})$ for
this general problem. The particular geometry of the $N=n^{2}$ points arranged
in a grid allows faster solutions for the MSM problem and the best algorithms
for it run in time $O(N^{3/2})=O(n^{3})$ [TT98, Tak02]. The M4C problem was
defined in [BDT16], where it was shown that it can be solved in $O(n^{3})$
time. It is also another generalization of the SSST problem.

Before stating our quantum complexity results, we will dwell on the classical
complexity of these problems. In [BDT16] they are analyzed in the context of
fine-grained complexity, and it is proven that in a strong sense, both MSM and
M4C have the same deterministic complexity as the well-known All-pairs
Shortest Paths problem. Fine-grained complexity establishes fine complexity
classes among computational problems by picking some well-studied problem $P$
which can be solved in time $\widetilde{O}(T(n))$, for some polynomial $T(n)$,
but for which no algorithm is known in time $T(n)^{1-\varepsilon}$, for any
$\varepsilon>0$. Then the fine-grained (quantum) complexity class with respect
to $P$ consists of all problems $X$ such that $P$ and $X$ are (quantum)
sub-$T(n)$ equivalent, that is inter-reducible by some appropriate (quantum)
sub-$T(n)$ reductions, ensuring that either, both, or neither of them can be
solved in (quantum) time $T(n)^{1-\varepsilon}$, for some $\varepsilon>0$. The
existence of such reductions also implies that all problems in the class are
solvable in time $\widetilde{O}(T(n))$. We won’t give here the technical
definition of the appropriate reduction.

The class $\bf{APSP}$ of problems that are sub-$n^{3}$ equivalent in the above
sense to APSP is one of the richest in fine-grained complexity theory [WW18,
Wil19]. It contains various path, matrix, and triangle problems, and also MSM
and M4C. We enumerate here some important problems from this class.

######  Problem 44 (All-pairs Shortest Paths).

Given a weighted graph on $n$ vertices, compute the length of a shortest path
between $u$ and $v$, for all vertices $u,v$.

######  Problem 45 (Matrix Product).

Given two $n\times n$ matrices, compute their matrix product over the (min, +)
semiring.

######  Problem 46 (Metricity).

Given an $n\times n$ matrix, decide if it defines a metric.

######  Problem 47 (Maximum Triangle).

Given a weighted graph on $n$ vertices, find a maximum weight triangle, where
the weight of a triangle is the sum of its edges.

######  Theorem 48 ([WW18, BDT16]).

Problems 42, 43, 44, 45, 46, 47 are in $\bf{APSP}$.

###  8.2 Quantum complexity

The study of fine-grained complexity equally makes sense in the quantum case,
and indeed several recent works have studied quantum fine-grained complexity
[ACL+20, BPS21, BLPS22]. These papers often address the quantum complexity of
problems in the same classical equivalence class and [ABL+22] has specifically
considered $\bf{APSP}$. Of course, it is not guaranteed at all that
classically equivalent problems remain equivalent in the quantum model of
computing, and this is exactly what happens with $\bf{APSP}$. While all known
problems in the class receive some quantum speedup, the measure of the speedup
can differ from problem to problem. It turns out that many of the problems in
$\bf{APSP}$ can be solved either in time $\widetilde{O}(n^{5/2})$ or in time
$\widetilde{O}(n^{3/2})$ by simple quantum algorithms, and concretely APSP
falls in the former category. In some cases, the classical fine-grained
reductions also work for establishing the relevant quantum equivalences. This
is illustrated by the following propositions.

######  Proposition 49.

The problems Matrix Product and All-pairs Shortest Paths can be solved in
quantum time $\widetilde{O}(n^{5/2}),$ and they are quantum sub-$n^{5/2}$
equivalent.

###### Proof.

The upper bounds come from quantum minimum finding (4) and the classical
sub-$n^{3}$ reductions of [FM71, Mun71] also establish the quantum
sub-$n^{5/2}$ equivalence. These reductions show that if one of the problems
can be solved in (classical or quantum) time ${O}(n^{2}+T(n))$ then the other
can be solved in time $\widetilde{O}(n^{2}+T(n))$. ∎

######  Proposition 50.

The problems Maximum Triangle and Metricity can be solved in quantum time
$\widetilde{O}(n^{3/2})$, and they are quantum sub-$n^{3/2}$ equivalent.

###### Proof.

The upper bound can be obtained by Grover search (1) over $n^{3}$ elements and
the classical sub-$n^{3}$ reductions of [WW18] establish also the quantum
sub-$n^{3/2}$ equivalence. Their reductions show that one of the problems can
be solved in (classical or quantum) time ${O}(T(n))$ if and only if the other
can be solved in time $\widetilde{O}(T(n))$. ∎

However, for some problems finding the “right” quantum upper bounds or
establishing fine-grained equivalences requires innovative quantum algorithms.
For example [ABL+22] used variable time quantum search and specific data
structures to construct quantum algorithms for $\Delta$-Matching Triangles and
Triangle Collection, two problems from $\bf{APSP}$. In particular, they have
shown that in the $\mathsf{QRAG}$ model the former problem can be solved in
quantum time $\widetilde{O}(n^{3/2+o(1)})$ when $\omega(1)\leq\Delta\leq
n^{o(1)}$, and the latter problem has a quantum algorithm of complexity
$\widetilde{O}(n^{3/2})$.

It turns out that, from the point of view of quantum complexity, the two
rectangle problems of our concern are quite interesting. In their study, we
will suppose that the absolute value of all input integers is polynomially
bounded in the input size. As optimizing logarithmic factors are not relevant
for this discussion, for simplicity, we choose to state our results taking
both $\mathrm{QR}_{n^{2}}$ and $\mathrm{QW}_{O(n^{2})}$ to be $O(\log^{2}n)$
when $N(n)$ is a polynomial in $n$ (Section 2.2.2).

We will show that the quantum time complexity of MSM is $O(n^{2}\log^{2}n)$
and that its quantum query complexity is $\Omega(n^{2}).$ One novelty of this
is that, to our knowledge, this is the first example of a problem from
$\bf{APSP}$ whose quantum time complexity is not of the order of $n^{5/2}$ or
$n^{3/2}$. The second novelty is that our lower bound is established for the
query complexity and therefore it is unconditional. The possibility of proving
a matching query lower bound is a specific feature of the quantum complexity
since the classical time complexity of MSM is believed to be super-linear in
the input size.

The interesting aspect of the ${O}(n^{3/2}\log^{5/2}(n))$ quantum algorithm we
obtain for M4C is that it is based on quantum divide and conquer. More
precisely, we exploit the fact that the one-dimensional analog of this problem
is SSST for which, in Theorem 15, we have designed an
$O(n^{1/2}\log^{5/2}(n))$ time quantum algorithm based on that technique.

######  Theorem 51.

The quantum time complexity of MSM is $O(n^{2}\log^{2}n)$ in the
$\mathsf{QRAG}$ model. Its quantum query complexity is $\Theta(n^{2}).$

###### Proof.

Let $B$ be an $(n,M)$ matrix. We define the $(n+1,M+1)$ matrix $C$ by
$C_{ik}=S_{B}((1,1),(i,k))$, for $1\leq i,k\leq n$, and we set
$C_{i0}=C_{0i}=0$, for all $0\leq i\leq n$. Then we have
$B_{ik}=C_{ik}-C_{i-1k}-C_{ik-1}+C_{i-1k-1}$. Therefore
$C_{ik}=B_{ik}+C_{i-1k}+C_{ik-1}-C_{i-1k-1}$ can be computed by dynamic
programming in time $O(n^{2}\cdot\mathrm{QW}_{O(n^{2})})$, as memory access
and addition both take time $\mathrm{QW}_{O(n^{2})}$ (see Section 2.2.2). We
have then, for $1\leq i<j\leq n$ and $1\leq k<\ell\leq n$,

$S_{B}((i,k),(j,\ell))=F_{C}((i-1,k-1),(j,\ell)).$

Therefore the maximum submatrix, over indices verifying $i<j$ and $k<\ell$,
can be found in time $O(n^{2}(\log
n+\mathrm{QW}_{O(n^{2})}))=O(n^{2}\log^{2}n)$ by quantum maximum search (4).

For the query lower bound we will make a reduction from the Boolean majority
function $\operatorname{\textsc{Maj}}(x_{1},\ldots,x_{m})$ which is by
definition $1$, if $\sum_{i=1}^{m}x_{i}>\lfloor m/2\rfloor$. It is known that
the quantum query complexity of $\operatorname{\textsc{Maj}}$ on $m$ bits is
$\Omega(m)$ [BBC+01]. Suppose we are given $n^{2}$ bits $x_{1},\ldots
x_{n^{2}}$ that we arrange into a matrix $B$. We define a $(2n+1)\times(2n+1)$
matrix $C$ as follows. We put $B$ into the intersection of the first $n$ rows
and first $n$ columns. Into the intersection of the first $n$ rows and last
$n$ columns we put an $n\times n$ matrix $D$ which has $\lfloor
n^{2}/2\rfloor$ 1’s and $\left\lceil n^{2}/2\right\rceil$ 0’s. We put
$C_{j,n+1}=-n-1$ for $1\leq j\leq n$, and we put -1 into the rest of $C$.
Because of the negative barrier put into the column $n+1$ and the negative
elements in the lower half of $C$, its maximum submatrix is either fully
inside $B$ or fully inside $D$. Therefore
$\operatorname{\textsc{Maj}}(x_{1},\ldots,x_{n^{2}})=1$ if and only if the
maximum submatrix in $C$ has value greater than $\lfloor n^{2}/2\rfloor$. ∎

######  Theorem 52.

The quantum time complexity of M4C is ${O}(n^{3/2}\log^{5/2}n)$ in the
$\mathsf{QRAM}$ model.

###### Proof.

Let us be given an $n\times n$ matrix $B$. For every $1\leq i\leq j\leq n$, we
define the array $A^{ij}$ by $A^{ij}=B_{j}-B_{i}$, where $B_{i}$ denotes the
$i$th row of $B$. Then

$B_{ik}+B_{j\ell}-B_{i\ell}-B_{jk}=A^{ij}_{\ell}-A^{ij}_{k},$

and therefore

$\max_{i\leq j,k\leq\ell}F_{B}((i,k),(j,\ell))=\max_{i\leq
j}\max_{k\leq\ell}A^{ij}_{\ell}-A^{ij}_{k}.$

By Theorem 15, we can determine $\max_{k<\ell}A^{ij}_{\ell}-A^{ij}_{k}$, in
time $O(\sqrt{n\log n}\cdot\lambda_{2}(n,\mathrm{QR}_{n^{2}}),$ for fixed
$i\leq j$. Let $m$ be this value, then
$\max_{k\leq\ell}A^{ij}_{\ell}-A^{ij}_{k}=\max\\{m,0\\}$, taking into account
also the case $k=\ell$. Therefore by Corollary 6 we can run quantum maximum
finding on the indices $i\leq j$ for the function
$f(i,j)=\max_{k\leq\ell}A^{ij}_{\ell}-A^{ij}_{k}$ in time O($n^{3/2}(\log
n)^{1/2}\cdot\lambda_{2}(n,\mathrm{QR}_{n^{2}}))=O(n^{3/2}\log^{5/2}n)$. ∎

We observe that the classical fine-grained reduction of [BDT16] from Maximum
Triangle to M4C is also a sub-$n^{3/2}$ reduction. Indeed, they show that if
M4C can be solved in (classical or quantum) time $\widetilde{O}(T(n))$ then
Maximum Triangle can be solved in time $\widetilde{O}(n+T(n))$. Therefore if
we believe that there is no sub-$n^{3/2}$ quantum algorithm for Maximum
Triangle then this also applies for M4C. However, proving an $\Omega(n^{3/2})$
query lower bound for Maximum Triangle could be a hard if not impossible task.
Indeed, while the best-known quantum algorithm for finding a triangle in an
unweighted graph has time complexity $O(n^{3/2}\log n)$, query algorithms of
much lower complexity are known for this problem [MSS07, Bel12, LMS17, Gal14],
and the situation could be similar for Maximum Triangle. We leave it as an
open problem whether proving such a query lower bound for M4C is possible.

######  Open Question 1.

What is the quantum query complexity of M4C?

### Acknowledgments

This research is supported by the National Research Foundation, Singapore, and
A*STAR under its CQT Bridging Grant and its Quantum Engineering Programme
under grant NRF2021-QEP2-02-P05. AB is supported by the Latvian Quantum
Initiative under European Union Recovery and Resilience Facility project no.
2.3.1.1.i.0/1/22/I/CFLA/001 and the QuantERA project QOPT. TL is supported in
part by the ARC DP grant DP200100950. TL thanks CQT for their hospitality
during a visit where part of this work was conducted.

## References

  * [ABI+19] Andris Ambainis, Kaspars Balodis, Janis Iraids, Martins Kokainis, Krisjanis Prusis, and Jevgenijs Vihrovs.  Quantum speedups for exponential-time dynamic programming algorithms.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1783–1793, 2019.
  * [ABL+22] Andris Ambainis, Harry Buhrman, Koen Leijnse, Subhasree Patro, and Florian Speelman.  Matching triangles and triangle collection: Hardness based on a weak quantum conjecture.  arXiv preprint arXiv:2207.11068, 2022.
  * [ACL+20] Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, and Ruizhe Zhang.  On the quantum complexity of closest pair and related problems.  In Proceedings of the 35th Computational Complexity Conference (CCC), pages 16:1–16:43, 2020.
  * [AGJ+15] Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O’Connor, Michele Mosca, and Priyaa Varshinee Srinivasan.  On the robustness of bucket brigade quantum RAM.  In Proceedings of the 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), pages 226–244, 2015.
  * [AGS19] Scott Aaronson, Daniel Grier, and Luke Schaeffer.  A quantum query complexity trichotomy for regular languages.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 942–965. IEEE, 2019.
  * [AHJ+22] Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, and Miklos Santha.  Classical and quantum algorithms for variants of subset-sum via dynamic programming.  In 30th Annual European Symposium on Algorithms (ESA), pages 6:1–6:18, 2022.
  * [AJ22] Shyan Akmal and Ce Jin.  Near-optimal quantum algorithms for string problems.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 2791–2832. SIAM, 2022.
  * [Amb07a] Andris Ambainis.  Quantum walk algorithm for element distinctness.  SIAM Journal on Computing, 37(1):210–239, 2007.
  * [Amb07b] Andris Ambainis.  Quantum walk algorithm for element distinctness.  SIAM Journal on Computing, 37(1):210–239, 2007.
  * [AS04] Scott Aaronson and Yaoyun Shi.  Quantum lower bounds for the collision and the element distinctness problems.  Journal of the ACM (JACM), 51(4):595–605, 2004.
  * [BBC+01] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf.  Quantum lower bounds by polynomials.  J. ACM, 48(4):778–797, 2001.
  * [BBHT98] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp.  Tight bounds on quantum searching.  Fortschritte der Physik: Progress of Physics, 46(4-5):493–505, 1998\.
  * [BCNP14] Jérémy Barbay, Timothy M. Chan, Gonzalo Navarro, and Pablo Pérez-Lantero.  Maximum-weight planar boxes in o(n${}^{\mbox{2}}$) time (and better).  Information Processing Letters, 114(8):437–445, 2014.
  * [BDT16] Arturs Backurs, Nishanth Dikkala, and Christos Tzamos.  Tight hardness results for maximum weight rectangles.  In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 81:1–81:13, 2016.
  * [Bel12] Aleksandrs Belovs.  Span programs for functions with constant-sized 1-certificates: extended abstract.  In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC), pages 77–84, 2012.
  * [BJLM13] Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer.  Quantum algorithms for the subset-sum problem.  In Proceedings of the 5th International workshop on Post-Quantum Cryptography (PQCrypto), pages 16–33, 2013.
  * [BLPS22] Harry Buhrman, Bruno Loff, Subhasree Patro, and Florian Speelman.  Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks.  In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), pages 31:1–31:12, 2022.
  * [BPS21] Harry Buhrman, Subhasree Patro, and Florian Speelman.  A framework of quantum strong exponential-time hypotheses.  In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 19:1–19:19, 2021.
  * [Cha13] Timothy M. Chan.  Klee’s measure problem made easy.  In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 410–419, 2013.
  * [CKK+22] Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, and Daochen Wang.  Quantum divide and conquer.  CoRR, abs/2210.06419, 2022.
  * [CP08] Maxime Crochemore and Ely Porat.  Computing a longest increasing subsequence of length k in time o(n log log k).  In Erol Gelenbe, Samson Abramsky, and Vladimiro Sassone, editors, Visions of Computer Science - BCS International Academic Conference, Imperial College, London, UK, 22-24 September 2008, pages 69–74. British Computer Society, 2008.
  * [CT65] James Cooley and John Tukey.  An algorithm for the machine calculation of complex fourier series.  Mathematics of Computation, 19(90):297–301, 1965.
  * [DGM96] David P. Dobkin, Dimitrios Gunopulos, and Wolfgang Maass.  Computing the maximum bichromatic discrepancy with applications to computer graphics and machine learning.  Journal of Computer and System Sciences, 52(3):453–470, 1996.
  * [DH96] Christoph Dürr and Peter Høyer.  A quantum algorithm for finding the minimum.  arXiv preprint quant-ph/9607014, 1996.
  * [FM71] Michael J. Fischer and Albert R. Meyer.  Boolean matrix multiplication and transitive closure.  In 12th Annual Symposium on Switching and Automata Theory, East Lansing, Michigan, USA, October 13-15, 1971, pages 129–131. IEEE Computer Society, 1971.
  * [FRPU94] Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal.  Computing with noisy information.  SIAM J. Comput., 23(5):1001–1018, 1994.
  * [Gal14] François Le Gall.  Improved quantum algorithm for triangle finding via combinatorial arguments.  In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 216–225, 2014.
  * [Gau76] Carl Friedrich Gauss.  Theoria interpolationis methodo nova tractata.  Carl Friedrich Gauss Werke, Königlichen Gesellschaft der Wissenschaften: Göttingen, 3:265–327, 1876.
  * [GLM08] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.  Architectures for a quantum random access memory.  Physical Review A, 78(5), 2008.
  * [Gro96] Lov K Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the 28th annual ACM symposium on Theory of computing (STOC), pages 212–219, 1996.
  * [GvN47] Herman Goldstone and John von Neumann.  Planning and coding of problems for an electronic computing instrument.  IAS Princeton, 2(2):49—68, 1947.
  * [HJB84] Michael Heideman, Don Johnson, and Sidney Burrus.  Gauss and the history of the fast fourier transform.  IEEE ASSP Magazine, 1(4):14–21, 1984.
  * [HMdW03] Peter Høyer, Michele Mosca, and Ronald de Wolf.  Quantum search on bounded-error inputs.  In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP), pages 291–299, 2003.
  * [Hoa62] Tony Hoare.  Quicksort.  Comput. J., 5(1):10–15, 1962.
  * [Jef22] Stacey Jeffery.  Quantum subroutine composition.  CoRR, abs/2209.14146, 2022.
  * [JP23] Stacey Jeffery and Galina Pass.  Personal communication, 2023.
  * [KL84] Bernhard Korte and László Lovász.  Greedoids - a structural framework for the greedy algorithm.  In WILLIAM R. PULLEYBLANK, editor, Progress in Combinatorial Optimization, pages 221–243. Academic Press, 1984.
  * [Kle77] Victor Klee.  Can the measure of $\bigcup^{n}_{1}[a_{i},b_{i}]$ be computed in less than ${O}(n\log n)$ steps?  American Mathematical Monthly, 84(4):284–285, 1977.
  * [KO62] Anatoly Karatsuba and Yuri Ofman.  Multiplication of many-digital numbers by automatic computers (in russian).  Doklady Akademii Nauk SSSR, 145(2):293–294, 1962.
  * [LMS17] Troy Lee, Frédéric Magniez, and Miklos Santha.  Improved quantum query algorithms for triangle detection and associativity testing.  Algorithmica, 77(2):459–486, 2017.
  * [MSS07] Frédéric Magniez, Miklos Santha, and Mario Szegedy.  Quantum algorithms for the triangle problem.  SIAM Journal on Computing, 37(2):413–424, 2007.
  * [Mun71] J. Ian Munro.  Efficient determination of the transitive closure of a directed graph.  Inf. Process. Lett., 1(2):56–58, 1971.
  * [Str69] Volker Strassen.  Gaussian elimination is not optimal.  Numerische Mathematik, 13(4):354–356, 1969.
  * [Tak02] Tadao Takaoka.  Efficient algorithms for the maximum subarray problem by distance matrix multiplication.  In Electronic Notes in Theoretical Computer Science, pages 191–200, 2002.
  * [TLJ23] Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka.  The power of recursion in graph neural networks for counting substructures.  In International Conference on Artificial Intelligence and Statistics, pages 11023–11042. PMLR, 2023.
  * [TT98] Hisao Tamaki and Takeshi Tokuyama.  Algorithms for the maxium subarray problem based on matrix multiplication.  In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 446–452, 1998.
  * [Wan22] Qisheng Wang.  A note on quantum divide and conquer for minimal string rotation.  CoRR, abs/2210.09149, 2022.
  * [Wil19] Virginia Vassilevska Williams.  On some fine-grained questions in algorithms and complexity.  In Proceedings of the International Congress of Mathematicians (ICM), pages 3447–3487, 2019.
  * [WW18] Virginia Vassilevska Williams and R. Ryan Williams.  Subcubic equivalences between path, matrix, and triangle problems.  J. ACM, 65(5):27:1–27:38, 2018.
  * [WY20] Qisheng Wang and Mingsheng Ying.  Quantum algorithm for lexicographically minimal string rotation.  arXiv preprint arXiv:2012.09376, 2020.