#  Quantum Speed Limits for Implementation of Unitary Transformations

Abolfazl Farmanian1 Vahid Karimipour1

( 1Deptartment of Physics, Sharif University of Technology, Tehran, Iran
)

###### Abstract

Quantum speed limits are the bounds that define how quickly one quantum state
can transform into another. Instead of focusing on the transformation between
pairs of states, we provide bounds on the speed limit of quantum evolution by
unitary operators in arbitrary dimensions. These do not depend on the initial
and final state but depend only on the trace of the unitary operator that is
to be implemented and the gross characteristics (average and variance) of the
energy spectrum of the Hamiltonian which generates this unitary evolution. The
bounds that we find can be thought of as the generalization of the Mandelstam-
Tamm (MT) and the Margolus-Levitin (ML) bound for state transformations to
implementations of unitary operators. We will discuss the application of these
bounds in several classes of transformations that are of interest in quantum
information processing.

##  1 Introduction

Can the universe impose a speed limit, not on the movement of objects, but on
the speed of information processing itself? In the recent literature on
quantum mechanics and quantum information, this problem is known as the
quantum speed limit or QSL for short. It can be viewed from several different
perspecstives. The first one which is mainly conceptual, understands it as a
more precise formulation of the Heisenberg Energy-Time uncertainty relation[1]
which has been known since the early days of quantum mechanics. However, with
the upsurge of quantum technology, this problem has gained renewed attention
as a practical matter of great interest. Given an amount of energy and a pair
of states, what is the shortest time for transforming one element of the pair
to the other? This point of view is important for speed of quantum computation
[2]. The same question can be asked in a different form: Given an amount of
time, what is the least amount of energy that we need for the evolution of a
given state to another one[3]. This point of view emphasizes the equally
important problem of energy consumption in quantum computation. Regardless of
these points of view, the first attempt for formulating the quantum speed
limit goes back to Mandlestam and Tamm [4] and then to Margolus and Levitin
[5], the combined result of whom can be formulated as follows: Given an
initial state $|\psi_{0}\rangle$, and final state $|\psi_{\tau}\rangle$, such
that $\langle\psi_{0}|\psi_{\tau}\rangle=0$, the time needed for the above
evolution is subject to the following bound [6]:

$T\geq T_{QSL}=Max\Big{\\{}\frac{\hbar\pi}{2\Delta
E},\frac{\hbar\pi}{2E}\Big{\\}},$ (1)

where $H$ is the Hamiltonian which performs this evolution,
$E=\langle\psi_{0}|H|\psi_{0}\rangle-E_{0}$, is the average energy about the
ground state energy $E_{0}$, and $\Delta
E=\langle\psi_{0}|H^{2}|\psi_{0}\rangle-\langle\psi_{0}|H|\psi_{0}\rangle^{2}$
is the variance of energy in the initial state. This relation was then
generalized to the case where the initial and final states are no longer
orthogonal [7, 8, 9]. Since then, various aspects of quantum speed limit have
been extensively studied. These works include QLS bound for mixed states and
nonunitary evolutions[10, 11, 12, 13, 14, 15], relation between entanglement
and QLS [16, 17, 18], speed limits for the evolution of observables in the
Heisenberg picture [19], the study of speed limit for a bounded energy
spectrum[20], and other interesting aspects of quantum speed limit [21, 22,
23, 24, 25, 26, 27, 28, 29]. For a review on this subject see [30, 31].

In this regard we particularly mention the works [32] and [33], where quantum
speed limits are investigated for unitary evolutions and [34] where the
quantum speed limit for a change of basis between Mutually Unbiased Bases
(MUB’s) is studied. In [32], starting from the Fubini-Study distance between
states, a time-energy bound is derived, known as the Anandan-Aharonov
relation. Using this distance, the author proceeds to define a distance
between unitary operators and derive a time-energy bound for unitary evolution
in the form

$T\geq\frac{\sqrt{N}\arccos(\frac{1}{N}|\tr(U)|)}{\sqrt{\tr(H^{2})}}=\frac{\arccos(\frac{1}{N}|\tr(U)|)}{\sqrt{\frac{\sum_{k=1}^{N}E_{k}^{2}}{N}}}.$
(2)

The problem with this interesting bound is that an arbitrary shift in all the
energy levels of the Hamiltonian, while leading to the same unitary evolution,
yields a completely different time-energy bound as is evident from (2).

Starting again from time-energy bounds for evolution of states, the authors of
[33], try to remove the dependence on the energy of the initial and final
states in (1) and replace it with the energy spectrum of the Hamiltonian. To
this end they invoke Popoviciu inequality $\Delta E\leq(E_{max}-E_{min})/2$
[35] (where $E_{max}$ is the highest energy level and $E_{min}$ is the energy
of ground state) and arrive at

$\tau\geq\tau_{QSL}=\frac{2\hbar\theta}{E_{max}-E_{min}}.$ (3)

The new bound now depends on the width of the spectrum of the Hamiltonian
evolving the state. However, the bound still depends on $\theta$, the angle
between the initial and final states. To remedy this, the authors of [33]
define $\theta$ for qubits to be the maximum arc angle on bloch sphere that
the specified unitary can transform a state. In this way they are able to find
time-energy bounds for unitaries acting on $n$ qubits, i.e. for $2^{n}-$
dimensional unitaries, not for general ones. Moreover, their definition for
calculating this angle $\theta$ for an $n-$ qubit unitary does not lead to a
straightforward calculation.

Finally in [34], the authors take a different route and instead of
transformation between two single states, consider transformation between two
special sets of states, namely those sets which are mutually unbiased with
respect to each other. In other words, they consider transformations between
Mutually Unbiased Bases or MUB’s for short. That is, they ask what is the
quantum speed limit if we want to convert a complete basis $\\{|k\rangle,\
k=1\cdots d\\}$ to another one $\\{|e_{k}\rangle,k=1\cdots d\\}$ which is a
Mutually Unbiased Basis (MUB) with respect to the original one. They proceed
to find quantum speed limits for change of basis for qubit and qutrit bases
and conjecture general bounds for general dimensions. ̵Besides the
restriction to certain classes of unitary transformations, a problem with this
approach is that they ignore change of relative phases in evolution between
MUB bases, i.e. they allow that an arbitrary state
$|\psi\rangle=\alpha|0\rangle+b|1\rangle$ be converted to
$|\psi^{\prime}\rangle=\alpha|+\rangle+e^{i\phi}b|-\rangle$. This is inherent
in their approach which considers unitaries of the form
$U=\sum_{k}e^{i\phi_{k}}|e_{k}\rangle\langle k|$, where the phases $e^{i\phi}$
are to meant to be eliminated by another unitary of the form
$V=\sum_{k}e^{-i\phi_{k}}|e_{k}\rangle\langle e_{k}|$. Therefore, if we have
fixed a reference frame for phases, then the energy-time constraint for the
diagonal unitary operator $V$ should also be taken into account. Needless to
say, one can redefine the basis states to remove the phases, however this will
become problematic if we consider consecutive unitary gates acting in a
circuit.

In this article, we follow a different approach, namely we derive quantum
speed limits for unitary evolution from the very beginning, without resorting
to speed limits for transformation of pairs of states. In contrast with [32],
our bound is invariant under a shift of energy levels and in contrast with
[34], we consider transformation of a basis $B=\\{|i\rangle,\
i=0,1,\cdots,N-1\\}$ to another arbitrary one
$B^{\prime}=\\{|e_{i}\rangle,i=0,1,\cdots,N-1\\}$, be it MUB or not with
respect to the original one, without producing any extra relative phase.

Remark: One may argue that given a unitary operator $U=e^{-iHT}$, one can
first calculate the eigenvalues $\lambda_{k}$ of $U$ and then proceed to
extract the energies via the relation $\lambda_{k}(U)=e^{-iE_{k}T}$ from which
a time-energy bound can be established [36]. There are however two major
problems with this approach. The first obvious one is that finding the
logarithm of a unitary, specially in high dimensions is a highly nontrivial
problem. The second more important one is that, from the relation
$\lambda_{k}(U)=e^{-iE_{k}T}$, each energy level or more precisely each
$E_{k}T$ is obtained only modulo an arbitrary multiple of $2\pi$ (i.e.
$E_{k}T$ and $E_{k}T+2\pi n_{k}$ where $n_{k}$ is an integer lead to the same
eigenvalue of $\lambda_{k}(U)$). Of course one can restrict all the $E_{k}T$’s
to lie in the interval $(-\pi,\pi)$ for obtaining the minimum average energy.
However, even then, an ambiguity in the correct time-energy relations remains.
This is due to the fact that from the spectrum of $U$ arranged on the unit
circle in the complex plane, in the form $\lambda_{k}(U)=e^{-iE_{k}T}$, each
of the energies $E_{k}$ can be shifted to be the ground state. This obviously
affects the average energy above the ground state according to the definition
(4).

The time-energy bound that we propose circumvents these two problems. It only
needs a knowledge of $tr(U)$, is free from the phase ambiguity of taking the
logarithm of $U$ and depends solely on $tr(U)$. This bound in fact generalizes
in a simple way the Mandelstamm-Taam and Margolous-Levitin bounds to
implementation of unitaries and can be useful in design of quantum circuits
and other quantum information processing tasks.

The structure of this paper is as follows: in section 2, we state our main
result in the form a proposition. This proposition is then proved in section
3. In section 4 we calculate the bounds for several classes of unitaries which
are important for quantum computation algorithms. Finally in section 5, we
discuss the tightness of these bounds for qubit and qutrit cases. we conclude
the paper with a discussion.

Notations: Throughout the paper we take $\hbar=1$ and consider a system which
is represented in a finite dimensional Hilbert space of dimension $N$ with
discrete energy eigenvalues are ordered as $\\{E_{0}\leq\cdots\leq
E_{i}\leq\cdots E_{N-1}\\}$. Thus some of the energy eigenvalues may be
degenerate. Therefore $E_{0}=E_{min}$ is the minimum energy eigenvalue and
$E_{N-1}=E_{max}$ is the maximum one . The average energy above the ground
state is denoted by

$E:=\frac{\sum_{k}E_{k}}{N}-E_{0}$ (4)

and its variance by

$(\Delta E)^{2}=\frac{1}{N}\sum_{k=0}^{N-1}(E_{k}-\overline{E})^{2}.$ (5)

The width of the spectrum is also denoted by $\delta E$:

$\delta E:=E_{max}-E_{min}.$ (6)

##  2 Main results

Our main result is the following proposition which we state below and prove in
the next section.

Proposition: To affect an $N-$ dimensional unitary gate $U=e^{-iHT}$, the
following quantum speed limit holds:

$T\geq
Max\left(\frac{\pi}{2E}\Big{(}1-\frac{|tr(U)|}{N}\sqrt{1+\frac{4}{\pi^{2}}}\Big{)}\
,\ \frac{1}{\Delta E}\sqrt{1-\frac{|tr(U)|^{2}}{N^{2}}}\right)$ (7)

2

This bound is the analogue of combined Mandlestam-Tamm(MT) and the Margolus-
Levitin (ML) bound [4, 5].

Note that this bound depends only on $|tr(U)|$. This reflects the equivalence
of the gates $U$ and $e^{i\phi}U$, the latter being equivalent to a shift of
all energies. The bound is also the same for the gates $U$ and
$VUV^{\dagger}$, where $V$ is a unitary which changes the bases of the Hilbert
space, in which $U$ is expressed as a matrix.

Corollary: From the main proposition also follows a bound which depends on the
width of the spectrum and is written as

$T\geq Max\left(\frac{\pi}{\delta
E}\Big{(}1-\frac{|tr(U)|}{N}\sqrt{1+\frac{4}{\pi^{2}}}\Big{)}\ ,\
\frac{2}{\delta E}{\sqrt{1-\frac{|tr(U)|^{2}}{N^{2}}}}\ \ \right),$ (8)

where $\delta E=E_{max}-E_{min}$ is the width of the spectrum.

##  3  Proof of the proposition

Let $U$ be the Unitary and $H$ be the Hamiltonian with energy levels in the
set

$\\{E_{0}\leq\cdots E_{i}\cdots\leq E_{N-1},\ \ i=0,1,\cdots N-1\\},$

which is responsible for transformation of the basis
$B_{0}=\\{|0\rangle,|1\rangle,\cdots,|N-1\rangle\\}$ to a basis
$B_{1}=\\{|e_{i}\rangle,i=0,1,\cdots N-1\\}$. The unitary operator
corresponding to this evolution is given by $U=e^{-iHT}$.

Consider the well-known identity

$x\geq\frac{\pi}{2}(1-\cos x)-\sin x,\ \ \ \ \ \ \forall\ x\geq 0.$ (9)

Let $x=(E_{k}-E_{0})T$ in (9) and sum over $k$ to find :

$\sum_{i}(E_{k}-E_{0})T\geq\frac{N\pi}{2}-\frac{\pi}{2}\sum_{k}\cos(E_{k}-E_{0})T-\sum_{k}\sin(E_{k}-E_{0})T$
(10)

With a little rearrangement, equation (10) can be rewritten as

$\sum_{i}(E_{k}-E_{0})T\geq N\frac{\pi}{2}-(\sum_{k}\cos
E_{k}T)(\frac{\pi}{2}\cos E_{0}T-\sin E_{0}T)-(\sum_{k}\sin
E_{k}T)(\frac{\pi}{2}\sin E_{0}T+\cos E_{0}T).$ (11)

Noting that

$tr(U)=\sum_{k}e^{-iE_{k}T}=\sum_{k}\cos E_{k}T-i\sum_{k}\sin
E_{k}T:=|tr(U)|(\cos\theta-i\sin\theta)$ (12)

for some angle $\theta$, and equivalently that

$\sum_{k}\cos E_{k}T:=|tr(U)|\cos\theta,\hskip 28.45274pt\sum_{k}\sin
E_{k}T:=|tr(U)|\sin\theta.$ (13)

In view of (13) we find

$N(\overline{E}-E_{min})T\geq
N\frac{\pi}{2}-|tr(U)|\big{(}\frac{\pi}{2}\cos(\theta-E_{0}T)-\sin(\theta-
E_{0}T)\big{)}.$ (14)

Since the last trigonometic expression is always less than
$\sqrt{1+\frac{\pi^{2}}{4}}$, this leads to

$N(\overline{E}-E_{min})T\geq
N\frac{\pi}{2}-|tr(U)|\big{(}\sqrt{1+\frac{\pi^{2}}{4}}\big{)}.$ (15)

or in view of the definition $E=\overline{E}-E_{min}$, as

$ET\geq\frac{\pi}{2}-\frac{|tr(U)|}{N}\big{(}\frac{\pi}{2}\cos(\theta-
E_{0}T)-\sin(\theta-E_{0}T)\big{)}.$ (16)

and hence we find

$T\geq\frac{\pi}{2E}\Big{(}1-\frac{|tr(U)|\sqrt{1+\frac{4}{\pi^{2}}}}{N}\Big{)}.$
(17)

This is the analogue of the Margolus-Levitin bound. To prove the analogue of
the Mandelstam-Tamm bound, we use the identitiy

$x^{2}\geq 2(1-\cos x),\hskip 28.45274pt\forall\ \ x.$ (18)

Setting x = $(E_{k}-E_{l})T$ in (18) and summing over all $k$ and $l$ we have:

$\sum_{k,l}(E_{k}-E_{l})^{2}T^{2}\geq 2\sum_{k,l}(1-\cos((E_{k}-E_{l})T))$
(19)

We note that

$\sum_{k,l=1}^{N}(E_{k}-E_{l})^{2}=2N(\sum_{k}E_{k}^{2})-2(\sum_{k}E_{k})^{2}=2N^{2}\Delta
E^{2}$ (20)

and

$|tr(U)|^{2}=\sum_{k}e^{-iE_{k}T}\sum_{l}e^{iE_{l}T}=\sum_{k,l}e^{-i(E_{k}-E_{l})T}=\sum_{k,l}\cos(E_{k}-E_{l})T,$
(21)

where we have used the odd parity of $\sin(E_{k}-E_{l})T$. Inserting these two
last equalities in (19), we find

$\Delta E^{2}T^{2}\geq(1-\frac{|tr(U)|^{2}}{N^{2}})$ (22)

or

$T\geq\frac{\sqrt{(1-\frac{|tr(U)|^{2}}{N^{2}})}}{\Delta E}$ (23)

Combination of the two inequalities (17) and (23), proves the proposition.

Proof of the corollary:

If we use Popoviciu identity [35], namely, $2\Delta E\leq
E_{max}-E_{min}=\delta E$, we can also obtain a new bound from (23) which is
based on the width of the spectrum, that is

$T\geq\frac{2\sqrt{(1-\frac{|tr(U)|^{2}}{N^{2}})}}{\delta E}.$ (24)

Alternatively, we can prove an analogue of the Dual Margolus-Levitin bound
[20]by taking $x=(E_{max}-E_{k})T$ in (9) and exactly follow the same steps to
arrive at

$N(E_{max}-\overline{E})T\geq
N\frac{\pi}{2}-|tr(U)|\big{(}\sqrt{1+\frac{\pi^{2}}{4}}\big{)}.$ (25)

or

$T\geq\frac{\pi}{2(E_{max}-\overline{E})}\Big{(}1-\frac{|tr(U)|\sqrt{1+\frac{4}{\pi^{2}}}}{N}\Big{)}.$
(26)

Summing (25) with (15), we find

$N(E_{max}-E_{min})T\geq N{\pi}-|tr(U)|\big{(}\sqrt{4+\pi^{2}}\big{)},$ (27)

or

$T\geq\frac{\pi}{\delta
E}\Big{(}1-\frac{|tr(U)|}{N}\sqrt{1+\frac{4}{\pi^{2}}}\Big{)}.$ (28)

Combining the two bounds (28) and (24), proves the corollary (8).

##  4 Examples

We now provide several case scenarios of applying the bounds on the unitary
gates. The examples which are chosen are the ones which have practical
applications in quantum information and computation theory.

###  4.1 Transformation between Mutually Unbiased Bases or MUB’s

Let $U$ be a transformation which maps
$B_{0}=\\{|0\rangle,|1\rangle,\cdots|N-1\rangle\\}$ to a mutually unbiased
bases $B_{1}=\\{|e_{0}\rangle,|e_{1}\rangle,\cdots|e_{N-1}\rangle\\}$, where
$|<k|e_{l}>|^{2}=\frac{1}{N}\ \ \forall\ \ k,\ l$. This implies that:
$|tr(U)|\leq\sqrt{N}$ and hence the bound (7) reads:

$T\geq
Max\left(\frac{\pi}{2E}(1-\frac{1}{\sqrt{N}}\sqrt{1+\frac{4}{\pi^{2}}})\ ,\
\frac{\sqrt{1-\frac{1}{N}}}{\Delta E}\right)$ (29)

In [34], a bound is obtained for transformation between $MUB$’s which can be
expressed as follows:

$T\geq\begin{cases}\frac{2\pi}{9E}&\text{for\ \ N=3}\\\
\frac{\pi(N-1)}{4NE}&\text{for}\ N\geq 4\end{cases}$ (30)

It is seen that for all dimensions $N\geq 4$, our bound is tighter than the
bound (30) obtained in [34]. Specially for very large dimensions the right-
hand side of our bound converges to $\frac{\pi}{2}$ while the one given in
(30) converges to $\frac{\pi}{4}$. Note also that for every $N$-qubit system,
there is an explicit example, namely $U=H^{\otimes N}$ [34] which converts a
basis to a MUB basis in $T=\frac{\pi}{2E}$ This shows that for large $N$, the
bound in (29) becomes tight.

As a special case of transformation between MUB’s, the Fourier Transform is
defined as

$F=\frac{1}{\sqrt{N}}\sum_{k,l=0}^{N-1}\omega^{kl}|k\rangle\langle l|,$

where $\omega=e^{\frac{2\pi i}{N}}$. A closed form for the trace of $F$ is
given in the form of general quadratic Gauss sum [37]. This is given by

$|tr(F)|=|\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega^{k^{2}}|=\begin{cases}\sqrt{2}&{\rm
if}\ N=0\ \ \ \ {\rm mod}4\\\ 1&{\rm if}\ N=1,3\ {\rm mod}4\\\ 0&{\rm if}\
N=2\ \ \ \ {\rm mod}4\\\ \end{cases}.$ (31)

One can insert these values in (7) and (8) and obtain time-energy bounds for
Fourier transform in any dimension.

###  4.2 The permutation operator

As another special case, we can consider a permutation operator $P$, which
permutes the basis states in such a way that a number $m$ of basis states are
kept fixed. In this case, the operator $P$ is real and $Tr(P)=m$ leading to

$T\geq Max\left(\frac{\pi}{2E}(1-\frac{m}{N}\sqrt{1+\frac{4}{\pi^{2}}})\ ,\
\frac{1}{\Delta E}\sqrt{1+\frac{m^{2}}{N^{2}}}\right).$ (32)

In passing we note that the bound given in proposition 6 of [34] applies only
to shift operator $U|n\rangle=|(n+1)\ mod\ N\rangle$ and not to any
permutation. This is evident from the proof of this proposition in [34] which
hinges upon a form of eigenvalues specific to the shift operator and not to
any permutation operator.

###  4.3 The Grover operator

The Grover operator is defined as $G=(2|s\rangle\langle
s|-I_{N})(I_{N}-2|\omega\rangle\langle\omega|)$, where $I_{N}$ is the
$N$-dimensional identity operator, $|\omega\rangle$ is the single state which
is to be found and $|s\rangle=\frac{1}{\sqrt{N}}(\sum_{x=1}^{N}|x\rangle)$. We
find $|tr(G)|=N-4+\frac{4}{N}.$ In this case, we find from (23) a time-energy
bounds for the Grover operator in any dimension

$T\geq\frac{\sqrt{1-(1-\frac{4}{N}+\frac{4}{N^{2}})^{2}}}{\Delta
E}\approx\frac{2\sqrt{2}}{\Delta E\sqrt{N}},$ (33)

where the last expression is given for large $N$.

##  5 An examination of the bounds in low dimensions

To evaluate our bounds and see how tight they are, we examine them in low
dimensions, where explicit calculations of the eigenvalues of the unitary
operator is possible. We directly determine the Energy-Time relation by
explicit calculation and determine how well our bounds are compared with them.
Let us consider the qubit and the qutrit cases separately.

###  5.1 The qubit case:

A general unitary operator for qubit systems is of the form :

$U=e^{i\phi}\begin{pmatrix}e^{i\alpha}\cos\theta&e^{i\beta}\sin\theta\\\
-e^{-i\beta}\sin\theta&e^{-i\alpha}\cos\theta\end{pmatrix}.$ (34)

We assume that this unitary operator is affected by a Hamiltonian $H$ which is
constant in time and therefore $U=e^{-iHT}$. To find the energy levels of the
Hamiltonian, we find the eigenvalues of the operator $U$, which turn out to
be:

$\lambda_{\pm}=e^{i\phi}\Big{(}\cos\theta\cos\alpha\pm
i\sqrt{1-\cos^{2}\theta\cos^{2}\alpha}\Big{)}$ (35)

In view of the relation $U=e^{-iHT}$, this gives the following relation:

$(E_{2}-E_{1})T=2\cos^{-1}(|\cos\theta\cos\alpha|)$ (36)

where $E_{1}\leq E_{2}$ are the energies of the Hamiltonian. Since from (34),
$|tr(U)|=2|\cos\theta\cos\alpha|$ and since for a two-level system, we have
$E=\frac{E_{1}+E_{2}}{2}-E_{1}=\frac{E_{2}-E_{1}}{2}$, this can be written as

$T=\frac{\cos^{-1}(\frac{|tr(U)|}{2})}{E}.$ (37)

This relation gives the exact time for enacting the operator $U=e^{-iHT}$ on a
two-level system. Figure (1) compares our bound (7) with the actual time.

Figure 1:  (Color online) The exact time versus $|\tr(U)|$ for enacting a
unitary operator on a qubit system (solid line), compared with the bound (7)
(the dashed line). For qubits, $\Delta E=E=\frac{E_{2}-E_{1}}{2}$ and hence
both bounds in (7) can be expressed as $ET$ versus $|\tr(U)|$.

The energy time relation for transformation between qubit MUB’s: Equation (37)
gives the energy time relation for any qubit unitary operator. Note that this
is an equality, obtained by exact solution of the spectrum of the Hamiltonian.
For a unitary operator which transforms the basis
$B_{0}=\\{|0\rangle,|1\rangle\\}$ to a basis which is MUB with respect to
$B_{0}$, we should set $\theta=\frac{\pi}{4}$. Therefore equation (37) gives
the relation $T=\frac{\cos^{-1}(\frac{|\cos(\alpha)|}{\sqrt{2}})}{E}$ which
takes its minimum value for $\alpha=0$ and $\alpha=\pi$. This corresponds to
the following MUB basis with respect to $B_{1}$:

$B^{*}_{1}=\Big{\\{}|e_{0}\rangle=\frac{1}{\sqrt{2}}\begin{pmatrix}1\\\
e^{i\phi}\end{pmatrix}\ \ ,\ \
|e_{1}\rangle=\frac{1}{\sqrt{2}}\begin{pmatrix}-e^{-i\phi}\\\
1\end{pmatrix}\,\Big{\\}}.$ (38)

What is the meaning of the minimization carried over $\alpha$ or $|tr(U)|$? It
means that among the set of all MUB bases available, the one which can be
reached in the shortest possible time with the given amount of energy
$E_{2}-E_{1}$ is the MUB with $\alpha=0$ or $\alpha=\pi$. Figure (2)
illustrates this point.

Figure 2: The basis $B_{0}=\\{|0\rangle,|1\rangle\\}$ can be transformed to a
basis in the set of all MUB’s (shaded region). With a given energy,
transforming to the basis $B_{1}^{*}=\\{|e_{0}\rangle,|e_{1}\rangle\\}$ as
given in (38) needs the shortest amount of time.

###  5.2 The qutrit case

Unlike the qubit case, the exact determination of an energy-time relation for
general three-dimensional unitaries is not feasible. This is due to the large
number of parameters that such a unitary has which renders exact determination
of its eigenvalues and the corresponding Hamiltonian and hence an exact energy
time relation is intractable or at least not illuminating. We can do this for
a subset of such unitaries, namely, the ones which perform transformations
between MUB bases. This also enables us to compare our results with [34].
Therefore we restrict ourselves to those unitaries which transform the basis
state $B_{0}=\\{|0\rangle,|1\rangle,|2\rangle\\}$ to a basis
$B_{1}=\\{|e_{0}\rangle,|e_{1}\rangle,|e_{2}\rangle\\}$ which is MUB with
respect $B_{0}$. A unitary operator which performs this transformation,
without inducing extra phases is given by
$U=\sum_{i=0}^{2}|e_{i}\rangle\langle i|$. It has been shown that that the
most general unitary operator performing this task falls into one of the
following two classes [34]:

$U_{1}=\frac{1}{\sqrt{3}}\begin{pmatrix}e^{i\phi_{1}}&e^{i(\phi_{1}-\alpha)}&e^{i(\phi_{1}-\beta)}\\\
e^{i\phi_{2}}&\omega^{2}e^{i(\phi_{2}-\alpha)}&\omega e^{i(\phi_{2}-\beta)}\\\
e^{i\phi_{3}}&\omega
e^{i(\phi_{3}-\alpha)}&\omega^{2}e^{i(\phi_{3}-\beta)}\end{pmatrix}$ (39)

and

$U_{2}=\frac{1}{\sqrt{3}}\begin{pmatrix}e^{i\phi_{1}}&e^{i(\phi_{1}-\alpha)}&e^{i(\phi_{1}-\beta)}\\\
e^{i\phi_{2}}&\omega e^{i(\phi_{2}-\alpha)}&\omega^{2}e^{i(\phi_{2}-\beta)}\\\
e^{i\phi_{3}}&\omega^{2}e^{i(\phi_{3}-\alpha)}&\omega
e^{i(\phi_{3}-\beta)}\end{pmatrix}$ (40)

where $\omega=e^{\frac{2\pi i}{3}}$. The set of MUB’s is thus a continuous
five dimensional manifold with local coordinates
$\\{\phi_{1},\phi_{2},\phi_{3},\alpha,\beta\\}$ . Let us denote this manifold
by ${\cal M}$. One can remove the phases $\phi_{1},\phi_{2}$ and $\phi_{3}$ by
first transforming $U\longrightarrow e^{-i\phi_{1}}U$ and then transforming
$U\longrightarrow VUV^{\dagger}$, where
$V=diag(1,e^{i(\phi_{1}-\phi_{2})},e^{i(\phi_{1}-\phi_{3})})$. These two
transformations still retain the property of MUB-ness, i.e. map the manifold
of MUB bases into itself. The first transformation is affected by a shift of
all energy levels of the Hamiltonian $H\longrightarrow H+\frac{\phi_{1}}{T}$
and the second one is affected by a conjugation of the Hamiltonian
$H\longrightarrow VHV^{\dagger}$. Both of these Hamiltonians have the same
energy characteristics $E$ and $\Delta E$ as the original one. The net result
is that if the Hamiltonian $H$ brings the basis $B_{0}$ to a point $B_{1}$ in
the manifold ${\cal M}$, another Hamiltonian with the same energy
characteristics, can also reach another point of ${\cal M}$ at the same time,
i.e. under the same time-energy bound.

Figure 3: The manifold of MUB bases for qutrits has two disjoint parts. With a
given amount of energy, the basis $B_{0}=\\{|0\rangle,|1\rangle,|2\rangle\\}$
can be transformed in the shortest time to a MUB basis $B_{1}\in{\cal M}_{I}$
or to a MUB basis $B_{2}\in{\cal M}_{II}$. The energy-time bound for the two
sets are different.

In this way, one can restrict the transformations between MUB’s which have
only two free parameters, instead of five. Thus the two classes of unitaries
are the following:

$U_{1}(x,y)=\frac{1}{\sqrt{3}}\begin{pmatrix}1&e^{ix}&e^{iy}\\\
1&\overline{\omega}e^{ix}&\omega e^{iy}\\\ 1&\omega
e^{ix}&\overline{\omega}e^{iy}\end{pmatrix}$ (41)

and

$U_{2}(x,y)=\frac{1}{\sqrt{3}}\begin{pmatrix}1&e^{ix}&e^{iy}\\\ 1&\omega
e^{ix}&\overline{\omega}e^{iy}\\\ 1&\overline{\omega}e^{ix}&\omega
e^{iy}\end{pmatrix}$ (42)

where $x$ and $y$ are real parameters. These two manifolds are disjoint,
figure (3). Consider the class $U_{1}$. We can determine the energy-time
relation for this unitary by numerically evaluating its eigenvalues, leads to
energy times eigenvalues in the form $E_{0}T,E_{1}T$ and $E_{2}T$. Note that,
due to the ambiguity in taking the logarithm of $U$, even after choosing the
energies to be as low as possible, several different time-energy relations
follow. (see the remark in the introduction). We have chosen the order of
energies in such a way to lead to the minimum time-energy relation. Figure (4)
shows the exact energy-time relation for the unitary $U_{1}$ as a function of
$y$ for various values of $x$. Figure (5) shows the same relation for the
unitary $U_{2}$. On the same figures, the bound (17) is also plotted. This
plot is obtained simply by evaluating
$|tr(U_{1})|=|tr(U_{2})|=\frac{1}{\sqrt{3}}|1+{\omega}(e^{ix}+e^{iy})|$ and
using (17). It is evident that the exact calculation (which is obtained after
numerical work) validates the bound (17) which is obtained by a very simple
calculation.

Figure 4: The exact energy-time relation for the unitary $U_{1}$ as a function
of $y$ for various values of $x$(continuous line) versus the time-energy bound
(17) (dashed line).  Figure 5: The exact energy-time relation for the unitary
$U_{2}$ as a function of $y$ for various values of $x$(continuous line) versus
the time-energy bound (17) (dashed line).

##  6 Conclusion and outlook

We have established bounds on the speed limit of quantum evolution by unitary
operators in arbitrary dimensions. These time-energy bounds do not depend on
the initial and final state but depend only on the trace of the unitary
operator which is to be implemented and the gross characteristics of the
energy spectrum of the Hamiltonian which generates this unitary evolution. To
this end, we have shown how one can circumvent the ambiguities encountered in
taking the logarithm of a unitary operator $U=e^{-iHT}$. The bounds that we
find can be thought of as the generalization of the Mandelstam-Tamm (MT)
bound, the Margolus-Levitin (ML) bound and the dual Margolus-Levitin (dual ML)
bounds to the realm of unitary operators. After proving these bounds, we have
studied several classes of transformations, including change of basis between
MUB’s, permutations, Fourier transform, and the Grover operation. We have also
explicitly studied the general transformation for qubits and MUBs
transformation for qutrits. When applicable, we have compared our bounds with
those obtained in previous works.

Acknowledgment: This research was supported in part by Iran National Science
Foundation, under Grant No.4022322. The authors wish to thank Vahid
Jannessary, Shayan Roofeh and Amirhossein Tangestani for their valuable
comments and suggestions.

## References

  * [1] Y. Aharonov and D. Bohm.  Time in the quantum theory and the uncertainty relation for time and energy.  Physical Review, 122:1649–1658, 06 1961.
  * [2] Seth Lloyd.  Ultimate physical limits to computation.  Nature, 406:1047–1054, 08 2000.
  * [3] Jacob D. Bekenstein.  Energy cost of information transfer.  Physical Review Letters, 46:623–626, 03 1981.
  * [4] L I Mandelstam and Ig Tamm.  The uncertainty relation between energy and time in non-relativistic quantum mechanics.  Springer eBooks, pages 115–123, 01 1991.
  * [5] Norman Margolus and Lev B. Levitin.  The maximum speed of dynamical evolution.  Physica D: Nonlinear Phenomena, 120:188–195, 09 1998.
  * [6] Lev B Levitin and Tommaso Toffoli.  Fundamental limit on the rate of quantum dynamics: The unified bound is tight.  Physical review letters, 103, 10 2009.
  * [7] Peter Pfeifer.  How fast can a quantum state change with time?  Physical Review Letters, 70:3365–3368, 05 1993.
  * [8] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.  Quantum limits to dynamical evolution.  Physical Review A, 67, 05 2003.
  * [9] Niklas Hörnedal and Ole Sönnerborn.  Margolus-levitin quantum speed limit for an arbitrary fidelity.  Physical review research, 5, 12 2023.
  * [10] M M Taddei, B M Escher, Luiz Davidovich, and L de.  Quantum speed limit for physical processes.  110, 01 2013.
  * [11] A. del Campo, I. L. Egusquiza, M. B. Plenio, and S. F. Huelga.  Quantum speed limits in open system dynamics.  Physical Review Letters, 110, 01 2013.
  * [12] Sebastian Deffner and Eric Lutz.  Energy–time uncertainty relation for driven quantum systems.  Journal of Physics A, 46:335302–335302, 07 2013.
  * [13] Francesco Campaioli, Felix A. Pollock, Felix C. Binder, and Kavan Modi.  Tightening quantum speed limits for almost all states.  Physical Review Letters, 120, 02 2018.
  * [14] Ken Funo, Naoto Shiraishi, and Keiji Saito.  Speed limit for open quantum systems.  New journal of physics, 21:013006–013006, 01 2019.
  * [15] Dorje C Brody and Bradley Longstaff.  Evolution speed of open quantum dynamics.  Physical review research, 1, 11 2019.
  * [16] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.  The role of entanglement in dynamical evolution.  Europhysics letters, 62:615–621, 06 2003.
  * [17] Josep Batle, Montserrat Casas, Ángel R Plastino, and A Plastino.  Connection between entanglement and the speed of quantum evolution.  Physical review. A, Atomic, molecular, and optical physics/Physical review, A, Atomic, molecular, and optical physics, 72, 09 2005\.
  * [18] Lukasz Rudnicki.  Quantum speed limit and geometric measure of entanglement.  Physical Review A, 104, 09 2021.
  * [19] Brij Mohan and Arun Kumar Pati.  Quantum speed limits for observables.  Physical Review A, 106, 10 2022.
  * [20] Gal Ness, Andrea Alberti, and Yoav Sagi.  Quantum speed limit for states with a bounded energy spectrum.  Physical review letters, 129, 09 2022.
  * [21] Mao Zhang, Huai-Ming Yu, and Jing Liu.  Quantum speed limit for complex dynamics.  npj Quantum Information, 9:1–7, 10 2023.
  * [22] Ashraf Naderzadeh-ostad and Seyed Javad Akhtarshenas.  Optimal quantum speed for mixed states.  Journal of physics. A, Mathematical and theoretical, 01 2024.
  * [23] Jie-Hui Huang, Shan-Shan Dong, Guang-Long Chen, Nan-Run Zhou, Fu-Yao Liu, and Li-Guo Qin.  Path distance of a quantum unitary evolution.  Physical review. A/Physical review, A, 108, 08 2023.
  * [24] Niklas Hörnedal, Nicoletta Carabba, Apollonas S Matsoukas-Roubeas, and Adolfo del Campo.  Ultimate speed limits to the growth of operator complexity.  Communications physics, 5, 08 2022.
  * [25] Van Vu and Keiji Saito.  Topological speed limit.  Physical review letters, 130, 01 2023.
  * [26] Pablo M. Poggi, Steve Campbell, and Sebastian Deffner.  Diverging quantum speed limits: A herald of classicality.  PRX Quantum, 2, 12 2021.
  * [27] Matteo Fadel and Lorenzo Maccone.  Time-energy uncertainty relation for quantum events.  Physical review, 104, 11 2021.
  * [28] Manuel Gessner and Augusto Smerzi.  Statistical speed of quantum states: Generalized quantum fisher information and schatten speed.  Physical review. A/Physical review, A, 97, 02 2018.
  * [29] Diego Paiva Pires, Marco Cianciaruso, Lucas C Céleri, Gerardo Adesso, and Diogo O Soares-Pinto.  Generalized geometric quantum speed limits.  Physical review. X, 6, 06 2016.
  * [30] Michael R. Frey.  Quantum speed limits—primer, perspectives, and potential future directions.  Quantum Information Processing, 15:3919–3950, 07 2016.
  * [31] Sebastian Deffner and Steve Campbell.  Quantum speed limits: from heisenberg’s uncertainty principle to optimal quantum control.  Journal of Physics A: Mathematical and Theoretical, 50:453001, 10 2017.
  * [32] Pablo M. Poggi.  Geometric quantum speed limits and short-time accessibility to unitary operations.  Physical Review A, 99, 04 2019.
  * [33] Maxwell Aifer and Sebastian Deffner.  From quantum speed limits to energy-efficient quantum gates.  New Journal of Physics, 24:055002, 05 2022.
  * [34] Moein Naseri, Chiara Macchiavello, Dagmar Bruß, Pawel Horodecki, and Alexander Streltsov.  Quantum speed limits for change of basis.  New journal of physics, 02 2024.
  * [35] Rajendra Bhatia and Chandler Davis.  A better bound on the variance.  The American mathematical monthly, 107:353–357, 04 2000.
  * [36] Ju-Yeon Gyhm, Dario Rosa, and Dominik Šafránek.  Minimal time required to charge a quantum system.  Physical review. A/Physical review, A, 109, 02 2024.
  * [37] Bruce C Berndt and Ronald J Evans.  The determination of gauss sums.  Bulletin of the American Mathematical Society, 5:107–129, 01 1981\.


# Deep Learning and Mathematical Intuition:
A Review of (Davies et al. 2021)

Ernest Davis
Dept. of Computer Science
New York University
New York, NY 10012
<EMAIL_ADDRESS>
###### Abstract

A recent paper by Davies et al (2021) describes how deep learning (DL)
technology was used to find plausible hypotheses that have led to two original
mathematical results: one in knot theory, one in representation theory. I
argue here that the significance and novelty of this application of DL
technology to mathematics is significantly overstated in the paper under
review and has been wildly overstated in some of the accounts in the popular
science press. In the knot theory result, the role of DL was small, and a
conventional statistical analysis would probably have sufficed. In the
representation theory result, the role of DL is much larger; however, it is
not very different in kind from what has been done in experimental mathematics
for decades. Moreover, it is not clear whether the distinctive features of DL
that make it useful here will apply across a wide range of mathematical
problems. Finally, I argue that the DL here “guides human intuition” is
unhelpful and misleading; what the DL does primarily does is to mark many
possible conjectures as false and a few others as possibly worthy of study.

Certainly the representation theory result represents an original and
interesting application of DL to mathematical research, but its larger
significance is uncertain.

##  1 Introduction

A recent paper by Davies et al. (2021), published in Nature, discusses two
newly proved theorems — one in knot theory, one in representation theory111For
AI readers: “representation theory” here is a subfield of abstract algebra. It
has essentially no connection to either the knowledge representation used in
symbolic AI, or the representations studied in machine learning. — where the
authors were to some extent guided by computational experiments carried out
using deep learning.222The proofs of the theorems are published separately, in
(Davies, Lackenby, Juhasz, and Tomasev, 2021) and (Blundell et al., 2021), and
are included in the supplemental material.

The paper has gathered a great deal of attention in the popular scientific
press, in uncritical articles with overheated headlines, such as “DeepMind AI
collaborates with humans on two mathematical breakthroughs” in NewScientist
(Sparkes, 2021); “Maths researchers hail breakthrough in applications of
artificial intelligence” in phys.org, (U. Sydney, 2021); “Researchers create
AI that can create brand new math theorems” in iflscience.com (Spalding,
2021). An article in ScienceAlert (Neild, 2021) claims “AI is discovering
patterns in pure mathematics that have never been seen before …We can add
suggesting and proving mathematical theorems to the long list of what
artificial intelligence is capable of.” An article in LiveScience (Pappas,
2021) describes the results as “the first-ever important advances in pure
mathematics generated by artificial intelligence.”

On careful examination, however, this excitement is excessive and the articles
are misleading. The AI in these two mathematical research project neither
suggested nor proved any theorems. The use of AI in these projects is not very
different in kind from what has been done in experimental mathematics (Borwein
and Bailey, 2008) for decades. In the case of the knot theory result, though
not the representation theory result, the insight provided by deep learning
could have been achieved through more traditional statistical analysis. The
claim that the AI was used to “guide human intuition” is misleading and
unhelpful; a more accurate claim is that the experimentation indicated that
some specific conjectures might be true and therefore deserve study while
others almost certainly were not, and therefore should be abandoned.

Before going further, let me make two disclaimers. The first has to do with my
own limitations. The work here draws on three different fields, and I am not
an expert in any of them. I have some knowledge of machine learning generally
and deep learning specifically, but I am not an expert. I know very little
about knot theory and almost nothing at all about representation theory. So it
is certainly possible that my account below has some misstatements or
misjudgments. If you find a mistake, please do let me know.

Second, let me clearly set out the limits of what I am claiming here. I am not
at all arguing against the value of computational experiments in mathematical
research or against the development of AI tools for mathematics; there is a
lot of excellent, exciting work going on in both directions. I am not arguing
against the significance of these new mathematical results as mathematics; I
am in no position to judge that. I am not arguing that the Nature paper
misrepresents how the AI tools were used or how helpful the mathematicians
involved found them; I am working from the assumption that that is all
accurately set forth.

What I want to do in this review is to lay out clearly the role of AI in these
projects and to discuss the implications of that role. Since many lay readers
and even many people involved in machine learning technology have little idea
of research in pure mathematics, and since many mathematicians do not follow
machine learning closely, claims such as the ones I have quoted above can
easily be accepted uncritically, leading to miscommunication and
misunderstanding.

Ordinarily, when someone praises a tool that they have been using — a gardener
praises a particular hedge trimmer, a mathematician says that they constantly
use Brouwer’s fixed point theorem — there is no reason to be at all skeptical.
In this case, however, there is a perverse incentive to focus the role of the
DL in this research, not just for the ML specialists from Deep Mind, but even
for the mathematicians. The remarkable fame that these works have achieved —
the prestigious article in Nature, the excitement in all kinds of science
venues across the internet — has nothing to do with their merits as pure
mathematics, and everything to do with the fact that AI was involved. Everyone
involved, therefore, has an interest in highlighting and even exaggerating the
extent and impact of that involvement.

##  2 The knot theory result

My discussion of the mathematical aspects of the two results will be minimal;
only as much as is necessary to explain the role of the AI in achieving them.
For a little more detail, go to (Davies et al., 2021); for a lot more detail,
look up the works cited there.

A knot in mathematical parlance is a closed loop in a three-dimensional space.
There are many different numerical features of a knot that can be defined that
describe different geometric characteristics. These features are categorized
into a number of different categories, corresponding to the kind of math used
to define them. Two of the most important categories are algebraic invariants
and hyperbolic invariants. The goal of the research here was to find a
relation between one particular algebraic invariant, called the signature and
a number of hyperbolic invariants; that would exciting because it would be a
connection between two completely separate approaches to characterizing a
knot.

The research project proceeded along a number of steps:

Step 1: The mathematicians selected about 12 hyperbolic invariants as
promising candidates.333The description in (Davies et al. 2021) is not
entirely clear on this point. The list of invariants given in the section
Methods/Topology/Data-Generation is slightly different from the list in figure
3.

Step 2: They created a data set with 2.7 million examples of knots, labelled
with the signature and these 12 hyperbolic invariants.

Step 3: Using the data set, they trained a neural network (3 hidden layers,
300 units in each, fully connected) with the task of predicting the signature
from the hyperbolic invariants.

Step 4: They observed that the trained NN could predict the signature from the
inputs with an accuracy of 78%. This indicated that, indeed, there is a
relation.

Step 5: Using standard techniques for analyzing neural networks, they
determined that they can reduce the input to three hyperbolic invariants — the
real and imaginary parts of the meridional translation and the longitudinal
translation — without losing much accuracy.

Step 6: Thinking about these particular quantities, the mathematicians decided
that it would be reasonable to combine them into a new, geometrically
meaningful, quantity, the ‘natural slope’. If $\mu$ is the meridional
translation (a complex number, thus a pair of real numbers) and $\lambda$ is
the longitudinal translation, then slope = Re($\lambda/\mu$).

Step 7: They plotted the signature against the slope. It turned out that there
was an approximate linear relation: the signature is approximately half the
slope. Using the slope as the sole predictive feature for the signature gave
an accuracy of 78%; i.e. the slope constituted all the predictive power in the
twelve hyperbolic features combined.

Step 8: They formulated an initial hypothesis:

$|2\sigma(K)-\mbox{slope}(K)|<c_{1}\mbox{vol}(K)+c_{2}$

where $K$ ranges over knots, $\sigma$ is the signature, vol($K$) is the volume
(a fourth hyperbolic parameter), and $c_{1}$ and $c_{2}$ are constants.

Step 9: They realized that there might be counter-examples to the initial
hypothesis over a particular category of knots. They generated a data set with
about 36,000 knots in this category. They indeed found some counter-examples.

Step 10: They formulated a revised hypothesis

$|2\sigma(K)-\mbox{slope}(K)|<c\,\mbox{vol}(K)/\mbox{inj}(K)^{3}$

where inj($K$) is the injectivity radius, a fifth hyperbolic parameter, which
can be a small real number.

Step 11: They were able to prove the revised hypothesis.

Note, first, that machine learning was used only in steps 4 and 5, and its
sole outcome is to determine that three particular hyperbolic parameters are
largely predictive of the signature. Step 7 involved doing a linear
regression. Steps 2 and 9, the creation of two data sets, involved highly
specialized non-AI software, almost certainly more sophisticated
computationally and mathematically than the neural network, quite possibly
more demanding computationally (the computation of some of these parameters
can be very difficult.) The other steps were all carried out by the human
mathematicians.

Second, at the end of the day, all that the deep learning component
accomplished was to isolate a mathematically simple relationship between four
real-valued numerical parameters. If we write the complex meridional
translation $\mu$ in the form $\mu=a+bi$, then the formula for slope becomes
slope = Re($\lambda/a+bi$) = $\lambda a/(a^{2}+b^{2})$. The relation detected
by the neural network therefore has the form $\sigma\approx\lambda
a/2(a^{2}+b^{2})$ — linear in $\lambda$ and a simple function of $a$ and $b$.
Again, the DL did not even extract the form of the relation; all it did was to
report that $\sigma$ could be predicted with 78% accuracy from $\lambda$, $a$,
and $b$.

Broadly speaking, this knot theory problem is not actually the kind of problem
where DL typically outshines other machine-learning or statistical methods.
DL’s strength is in cases like vision or text where each instance (image or
text) has a large numbers of low-level input features, it is hard to reliably
identify high-level features, and the function relating the input features to
the answer is, as far as anyone can tell, immensely complex, with no small
subset of the input features being at all determinative. With only twelve
input features, of which only three are relevant, with a simple mathematical
approximate relation involved, and with three million data points, it is hard
to see why a neural network with 200,000 parameters would be the method of
choice; simple, conventional statistical methods or a support vector machine
would be more suitable.

##  3 The representation theory result

Like the knot theory result, the representation theory result involves
connecting two different views of a mathematical object. The objects involved
in representation theory are much more abstract than those in knot theory, and
I will not make the slightest attempt to explain them; I will merely quote
them. (The account of the math in (Davies et al. 2021) is likewise noticeably
sketchier for the representation theory than the knot theory, for the same
reason.)

Symmetric groups are a very important category of mathematical structure;
generally speaking, they describe the ways that a set of some kind can be
mapped into itself. If you have two elements of a symmetry groups, then the
relation between those can be characterized in two different ways: the
unlabelled Bruhat interval graph and the Kazhdan-Lusztig (KL) polynomial. The
Bruhat interval graph rapidly becomes quite complex, even for fairly simple
elements; the KL polynomial is much simpler. For instance, in the examples
they used, some of the graphs had 9! = 362,880 nodes, whereas the polynomials
were at most of degree four.

A long-standing conjecture, known as the “combinatorial invariance” conjecture
states that the KL polynomial can be computed from the Bruhat interval graph.
One of the obstacles to proving this is that the graphs are so large that it
is hard for researchers to get an intuitive feeling for their structure.

What the project here accomplished was to prove a result that is a major step
toward the full conjecture: There is a way to pre-process the interval graph,
called “a hypercube decomposition along its extremal reflection”, and once you
have done that, then the KL-polynomial can be computed using a simple formula.
The only problem is, there can be many different hypercube decompositions
along extremal reflections, and all that Blundell et al. have proved is that
one of these will work; they haven’t given a method of finding the right one.
They have now formulated the further conjecture that, in fact, any hypercube
decomposition along extremal reflections will work, and their experiments bear
that out, but they have not proved it. If they can prove that, then that will
settle the combinatorial invariance conjecture.

The project involved the following steps:

Step 1: They designed a specialized, comparatively shallow (4 propagation
steps), deep learning system that takes as input an encoding of the interval
graph and produces as output the coefficients of the KL polynomial. The
architecture of the network was designed to be “algorithmically aligned” with
existing knowledge about techniques for computing KL-polynomials from
“labelled Bruhat intervals” i.e. Bruhat intervals with some extra information.

Step 2: They created a training set of 24,000 examples, labelled by the Bruhat
interval graph and the KL polynomial.

Step 3: They trained the network on the training set, attaining accuracies for
the four coefficients ranging from 63% to 98%. This success gave some
encouragement that the Bruhat interval graph does indeed determine the
polynomials.

Step 4: “By experimenting on the way in which we input the Bruhat interval to
the network, it became apparent that some choices of graphs and features were
particularly conducive to accurate predictions. In particular, we found that a
subgraph inspired by prior work may be sufficient to calculate the KL
polynomial, and this was supported by a much more accurate estimated
function.” Accuracies on this subgraph ranged between 95.6% and 99% for the
different coefficients.

Step 5: By analyzing of the states of the DL network generated in the
experiments of step 4, they determined that edges in the Bruhat graph
corresponding to “extremal reflections” tended to be particularly important in
the successful experiments. The authors state that they did not at all
anticipate this.

Step 6: They used the information gathered in steps 4 and 5 to formulate a
conjecture that they were able to prove.

Clearly the role of deep learning is much greater here than in the knot theory
work. In particular my comment about the knot theory work, that other kinds of
statistical analysis would have worked as well, does not at all apply here.
The number of input features is enormous, and the relation between the input
feature and the output is complex.

However, a number of points should be observed.

In step 3, the DL provided little more than general encouragement that the
project on the whole was on the right track and that the deep learning system
might be able to detect the relation of the KL polynomial to the In step 4, it
distinguished successful from unsuccessful experiments with different forms of
input. Presumably all these experiments were carefully selected by the
mathematicians as possibly promising avenues of research. It would be
interesting to know how many such experiments were run and how many were
successful; i.e. how much useful pruning did the DL provide here? In step 5,
analysis of the DL identified certain edges as particularly important; here
the DL did, indeed, provide information that the mathematicians had not
anticipated.

Unlike the knot theory project, which used a generic DL architecture, the
neural network was carefully designed to fit deep mathematical knowledge about
the problem. Moreover, the DL worked much better, with something like 1/40th
the error rate, on pre-processed data than on the original data. This cuts
both ways. On the one hand, in the past, critics of DL, including myself, have
often objected that it is difficult to incorporate domain knowledge; this cuts
against that criticism. On the other hand, enthusiasts for DL have often
praised DL as a “plug-and-play” learning methodology that can be thrown at raw
data for whatever problem comes to hand; this cuts against that praise.

Deep mathematical knowledge of the problem was required here at practically
every stage: In designing the DL architecture in step 1, in creating the data
set in step 2, in choosing the experiments in step 4, in interpreting them in
step 5. and of course in proving the theorem in step 6.

In both projects, the DL was entirely in the dark about the larger
mathematical setting of the problem it was solving. In the knot theory
project, it was not given the actual geometric structure of the knots, just
the invariants as a collection of uninterpreted numbers. In the representation
theory project, it was not given the group or the group elements, just the
Bruhat graph and the KL polynomials.

In applications of deep learning of this kind, success may depend critically
on the way in which the training data is generated and the way that the
mathematical structures are encoded, in ways that are quite specific to a
particular task (Charton, 2021). Finding the best way to generate and encode
data involves a mixture of theory, experience, art, and experimentation. The
burden of all this lies on the human expert. Deep learning can be a powerful
tool, but it is not always a robust one.

In view of all this, it seems to me that DL as used here is best viewed as
another analytic tool in the toolbox of experimental mathematics rather than
as a fundamentally new approach to mathematics. How powerful a tool it is and
how broadly applicable remains to be seen. Experimental mathematics in general
can only be applied to certain kinds of mathematical questions, and this
technique is further limited. Davies et al. (2001) themselves express
hesitation on that:

> There are limitations to where this framework will be useful — it requires
> the ability to generate large datasets of the representations of objects and
> for the patterns to be detectable in examples that are calculable. Further,
> in some domains the functions of interest may be difficult to learn in this
> paradigm.

Additionally, there are examples where other analysis tools are more
effective.

So far, we have one quite impressive example of the use of DL in mathematical
research and one that is much less impressive. The history of AI has had its
share of one-offs; remarkable successes that were achieved on one particular
task that seemed promising but could never be matched on a second task.

##  4 “Guiding Intuition”

Finally, “guiding intuition” seems to me an seriously inaccurate description
of the assistance that mathematicians have gained, or can hope to gain, from
this use of DL systems. The word “intuitive” is a useful, though informal, one
in mathematical writing.444Of course, the phrase “intuitively obvious” is
often abused, either to bully students into quiet acceptance or as a euphemism
for “I haven’t thought it through but I’m pretty sure it’s right.” Because it
is a useful word, it is important not to misuse it. In the mathematical
setting, the word “intuitive” means that a concept or a proof can be grounded
in a person’s deep-seated sense of familiar domains such as numerosity, space,
time, or motion, or in some other way “makes sense” or “seems right” in a way
that does not involve explicit calculation or step-by-step reasoning. Math
teachers work hard to try to give their students an intuitive understanding of
concepts and proofs by tying them to the familiar; this can involve diagrams,
videos, examples from everyday life, and similar tools. Mathematicians and
math students work hard to achieve an intuitive understanding by similar
means. Contrary to the dictionary definition, “consisting in immediate
apprehension, without the intervention of any reasoning process”, an intuitive
grasp of a mathematical concept often requires hard mental work to attain.
Often, gaining an intuitive grasp requires working through multiple specific
examples. But no teacher ever tries to guide their students’ intuitions by
telling them, “I have looked at millions of examples, and I can report that
there is a pattern that works X% of the time, mostly on the basis of features
A,B,C” which is what the DL tells the mathematician, and all that the DL tells
the mathematician. The mathematicians in these projects may well have attained
an intuitive understanding of the concepts they have defined, the theorems
they have prove, and the conjectures they have put forward, but they did not
get that from the DL. What the DL did was to give them some advice as to which
features of the problem seemed to be important and which seemed unimportant.
That is not to be sneezed at, but it should not be exaggerated.

### Acknowledgements

Thanks to François Charton for helpful suggestions.

### References

Blundell et al. (2021) “Towards combinatorial invariance for Kazhdan-Lusztig
polynomials.” Arxiv preprint 2111.15161 https://arxiv.org/abs/2111.15161.

Borwein, J. and Bailey, D. (2008). Mathematics by Experiment. CRC Press.

Charton, F. (2021). “Linear algebra with transformers.” ArXiv preprint
2112.01898
https://arxiv.org/abs/2112.01898

Davies et al. (2021). “Advancing mathematics by guiding human intuition with
AI.” Nature, 600: 70-74.
https://www.nature.com/articles/s41586-021-04086-x

Davies, A., Lackenby, M., Juhasz, A. and Tomašev, N. “The signature and cusp
geometry of hyperbolic knots.” Arxiv preprint 2111.15323.
https://arxiv.org/abs/2111.15323

Neild, D. (2021). “AI is discovering patterns in pure mathematics that have
never been seen before.” ScienceAlert, Dec. 4, 2021.
https://www.sciencealert.com/ai-is-discovering-patterns-in-pure-mathematics-
that-have-never-been-seen-before

Pappas, S. (2021). “DeepMind cracks ’knot’ conjecture that bedeviled
mathematicians for decades.” livescience.com
https://www.livescience.com/deepmind-artificial-intelligence-pure-math

Spalding, K. (2021). “Researchers create AI that can create brand new math
theorems” iflscience.com.
https://www.iflscience.com/editors-blog/researchers-create-ai-that-can-invent-
brand-new-math-theorems/

Sparkes, M. (2021) “DeepMind AI collaborates with humans on two mathematical
breakthroughs.” NewScientist, Dec. 1, 2021.
https://www.newscientist.com/article/2299564-deepmind-ai-collaborates-with-
humans-on-two-mathematical-breakthroughs/

University of Sydney (2021). “Maths researchers hail breakthrough in
applications of artificial intelligence.” phys.org, Dec. 1, 2021.
https://phys.org/news/2021-12-maths-hail-breakthrough-applications-
artificial.html