author-pays 978-1-4503-4391-6/16/07 2933575.2934538

Joël Ouaknine ††thanks: Supported by the EPSRC.††thanks: Supported by the ERC
grant AVS-ISS (648701). University of Oxford<EMAIL_ADDRESS>Amaury Pouly †
University of Oxford<EMAIL_ADDRESS>João Sousa-Pinto ⋆††thanks:
Supported by the ERC grant ALGAME (321171). University of Oxford
<EMAIL_ADDRESS>James Worrell ⋆ University of Oxford<EMAIL_ADDRESS>
# Solvability of Matrix-Exponential Equations

(2016)

###### Abstract

We consider a continuous analogue of Babai et al. [1996]’s and Cai et al.
[2000]’s problem of solving multiplicative matrix equations. Given $k+1$
square matrices $A_{1},\ldots,A_{k},C$, all of the same dimension, whose
entries are real algebraic, we examine the problem of deciding whether there
exist non-negative reals $t_{1},\ldots,t_{k}$ such that

$\displaystyle\prod\limits_{i=1}^{k}\exp(A_{i}t_{i})=C.$

We show that this problem is undecidable in general, but decidable under the
assumption that the matrices $A_{1},\ldots,A_{k}$ commute. Our results have
applications to reachability problems for linear hybrid automata.

Our decidability proof relies on a number of theorems from algebraic and
transcendental number theory, most notably those of Baker, Kronecker,
Lindemann, and Masser, as well as some useful geometric and linear-algebraic
results, including the Minkowski-Weyl theorem and a new (to the best of our
knowledge) result about the uniqueness of strictly upper triangular matrix
logarithms of upper unitriangular matrices. On the other hand, our
undecidability result is shown by reduction from Hilbert’s Tenth Problem.

###### keywords:

exponential matrices, matrix reachability, matrix logarithms, commuting
matrices, hybrid automata

###### category:

Theory of Computation Models of Computation Timed and hybrid models

###### category:

Mathematics of computing Mathematical Analysis Ordinary differential equations

###### category:

Mathematics of computing Mathematical Analysis Number-theoretic computations

††conference: LICS ’16 July 05-08, 2016, New York, NY, USA

##  1 Introduction

Reachability problems are a fundamental staple of theoretical computer science
and verification, one of the best-known examples being the Halting Problem for
Turing machines. In this paper, our motivation originates from systems that
evolve continuously subject to linear differential equations; such objects
arise in the analysis of a range of models, including linear hybrid automata,
continuous-time Markov chains, linear dynamical systems and cyber-physical
systems as they are used in the physical sciences and engineering—see, e.g.,
Alur [2015].

More precisely, consider a system consisting of a finite number of discrete
locations (or control states), having the property that the continuous
variables of interest evolve in each location according to some linear
differential equation of the form $\dot{\boldsymbol{x}}=A\boldsymbol{x}$; here
$\boldsymbol{x}$ is a vector of continuous variables, and $A$ is a square
‘rate’ matrix of appropriate dimension. As is well-known, in each location the
closed form solution $\boldsymbol{x}(t)$ to the differential equation admits a
matrix-exponential representation of the form
$\boldsymbol{x}(t)=\exp(At)\boldsymbol{x}(0)$. Thus if a system evolves
through a series of $k$ locations, each with rate matrix $A_{i}$, and spending
time $t_{i}\geq 0$ in each location, the overall effect on the initial
continuous configuration is given by the matrix

$\displaystyle\prod\limits_{i=1}^{k}\exp(A_{i}t_{i})\,,$

viewed as a linear transformation on $\boldsymbol{x}(0)$.111In this motivating
example, we are assuming that there are no discrete resets of the continuous
variables when transitioning between locations.

A particularly interesting situation arises when the matrices $A_{i}$ commute;
in such cases, one can show that the order in which the locations are visited
(or indeed whether they are visited only once or several times) is immaterial,
the only relevant data being the total time spent in each location. Natural
questions then arise as to what kinds of linear transformations can thus be
achieved by such systems.

###  1.1 Related Work

Consider the following problems, which can be seen as discrete analogues of
the question we deal with in this paper.

######  Definition 1 (Matrix Semigroup Membership Problem)

Given $k+1$ square matrices $A_{1},\ldots,A_{k},C$, all of the same dimension,
whose entries are algebraic, does the matrix $C$ belong to the multiplicative
semigroup generated by $A_{1},\ldots,A_{k}$?

######  Definition 2 (Solvability of Multiplicative Matrix Equations)

Given $k+1$ square matrices $A_{1},\ldots,A_{k},C$, all of the same dimension,
whose entries are algebraic, does the equation

$\displaystyle\prod\limits_{i=1}^{k}A_{i}^{n_{i}}=C$

admit any solution $n_{1},\ldots,n_{k}\in\mathbb{N}$?

In general, both problems have been shown to be undecidable, in Paterson
[1970] and Bell et al. [2008], by reductions from Post’s Correspondence
Problem and Hilbert’s Tenth Problem, respectively.

When the matrices $A_{1},\ldots,A_{k}$ commute, these problems are identical,
and known to be decidable, as shown in Babai et al. [1996], generalising the
solution of the matrix powering problem, shown to be decidable in Kannan and
Lipton [1986], and the case with two commuting matrices, shown to be decidable
in Cai et al. [2000].

See Halava [1997] for a relevant survey, and Choffrut and Karhumäki [2005] for
some interesting related problems.

The following continuous analogue of Kannan and Lipton [1986]’s Orbit Problem
was shown to be decidable in Hainry [2008]:

######  Definition 3 (Continuous Orbit Problem)

Given an $n\times n$ matrix $A$ with algebraic entries and two $n$-dimensional
vectors $\boldsymbol{x},\boldsymbol{y}$ with algebraic coordinates, does there
exist a non-negative real $t$ such that
$\exp(At)\boldsymbol{x}=\boldsymbol{y}$?

The paper Chen et al. [2015] simplifies the argument of Hainry [2008] and
shows polynomial-time decidability. Moreover, a continuous version of the
Skolem-Pisot problem was dealt with in Bell et al. [2010], where a
decidability result is presented for some instances of the problem.

As mentioned earlier, an important motivation for our work comes from the
analysis of hybrid automata. In addition to Alur [2015], excellent background
references on the topic are Henzinger et al. [1995]; Henzinger [1996].

###  1.2 Decision Problems

We start by defining three decision problems that will be the main object of
study in this paper: the _Matrix-Exponential Problem_ , the _Linear-
Exponential Problem_ , and the _Algebraic-Logarithmic Integer Programming_
problem.

###### Definition 4

An instance of the Matrix-Exponential Problem (MEP) consists of square
matrices $A_{1},\ldots,A_{k}$ and $C$, all of the same dimension, whose
entries are real algebraic numbers. The problem asks to determine whether
there exist real numbers $t_{1},\ldots,t_{k}\geq 0$ such that

$\displaystyle\prod\limits_{i=1}^{k}\exp(A_{i}t_{i})=C\,.$ (1)

We will also consider a generalised version of this problem, called the
_Generalised MEP_ , in which the matrices $A_{1},\ldots,A_{k}$ and $C$ are
allowed to have complex algebraic entries and in which the input to the
problem also mentions a polyhedron $\mathcal{P}\subseteq\mathbb{R}^{2k}$ that
is specified by linear inequalities with real algebraic coefficients. In the
generalised problem we seek $t_{1},\ldots,t_{k}\in\mathbb{C}$ that satisfy (1)
and such that the vector
$(\mathrm{Re}(t_{1}),\ldots,\mathrm{Re}(t_{k}),\mathrm{Im}(t_{1}),\ldots,\mathrm{Im}(t_{k}))$
lies in $\mathcal{P}$.

In the case of commuting matrices, the Generalised Matrix-Exponential Problem
can be analysed block-wise, which leads us to the following problem:

###### Definition 5

An instance of the Linear-Exponential Problem (LEP) consists of a system of
equations

$\displaystyle\exp\left(\sum_{i\in
I}\lambda_{i}^{(j)}t_{i}\right)=c_{j}\exp(d_{j})\quad(j\in J),$ (2)

where $I$ and $J$ are finite index sets, the $\lambda_{i}^{(j)}$, $c_{j}$ and
$d_{j}$ are complex algebraic constants, and the $t_{i}$ are complex
variables, together with a polyhedron $\mathcal{P}\subseteq\mathbb{R}^{2k}$
that is specified by a system of linear inequalities with algebraic
coefficients. The problem asks to determine whether there exist
$t_{1},\ldots,t_{k}\in\mathbb{C}$ that satisfy the system (2) and such that
$(\mathrm{Re}(t_{1}),\ldots,\mathrm{Re}(t_{k}),\mathrm{Im}(t_{1}),\ldots,\mathrm{Im}(t_{k}))$
lies in $\mathcal{P}$.

To establish decidability of the Linear-Exponential Problem, we reduce it to
the following _Algebraic-Logarithmic Integer Programming_ problem. Here a
_linear form in logarithms of algebraic numbers_ is a number of the form
$\beta_{0}+\beta_{1}\log(\alpha_{1})+\cdots+\beta_{m}\log(\alpha_{m})$, where
$\beta_{0},\alpha_{1},\beta_{1},\ldots,\alpha_{m},\beta_{m}$ are algebraic
numbers and $\log$ denotes a fixed branch of the complex logarithm function.

###### Definition 6

An instance of the Algebraic-Logarithmic Integer Programming Problem (ALIP)
consists of a finite system of equations of the form

$\displaystyle A\boldsymbol{x}\leq\frac{1}{\pi}\boldsymbol{b}$

where $A$ is an $m\times n$ matrix with real algebraic entries and where the
coordinates of $\boldsymbol{b}$ are real linear forms in logarithms of
algebraic numbers. The problem asks to determine whether such a system admits
a solution $\boldsymbol{x}\in\mathbb{Z}^{n}$.

###  1.3 Paper Outline

After introducing the main mathematical techniques that are used in the paper,
we present a reduction from the Generalised Matrix Exponential Problem with
commuting matrices to the Linear-Exponential Problem, as well as a reduction
from the Linear-Exponential Problem to the Algebraic-Logarithmic Integer
Programming Problem, before finally showing that the Algebraic-Logarithmic
Integer Programming Problem is decidable. By way of hardness, we will prove
that the Matrix-Exponential Problem is undecidable (in the non-commutative
case), by reduction from Hilbert’s Tenth Problem.

##  2 Mathematical Background

###  2.1 Number Theory and Diophantine Approximation

A number $\alpha\in\mathbb{C}$ is said to be _algebraic_ if there exists a
non-zero polynomial $p\in\mathbb{Q}[x]$ for which $p(\alpha)=0$. A complex
number that is not algebraic is said to be _transcendental_. The monic
polynomial $p\in\mathbb{Q}[x]$ of smallest degree for which $p(\alpha)=0$ is
said to be the minimal polynomial of $\alpha$. The set of algebraic numbers,
denoted by $\overline{\mathbb{Q}}$, forms a field. Note that the complex
conjugate of an algebraic number is also algebraic, with the same minimal
polynomial. It is possible to represent and manipulate algebraic numbers
effectively, by storing their minimal polynomial and a sufficiently precise
numerical approximation. An excellent course (and reference) in computational
algebraic number theory can be found in Cohen [1993]. Efficient algorithms for
approximating algebraic numbers were presented in Pan [1996].

Given a vector $\boldsymbol{\lambda}\in\overline{\mathbb{Q}}^{m}$, its _group
of multiplicative relations_ is defined as

$\displaystyle
L(\boldsymbol{\lambda})=\\{\boldsymbol{v}\in\mathbb{Z}^{m}:\boldsymbol{\lambda}^{\boldsymbol{v}}=1\\}.$

Moreover, letting $\log$ represent a fixed branch of the complex logarithm
function, note that $\log(\alpha_{1}),\ldots,\log(\alpha_{m})$ are linearly
independent over $\mathbb{Q}$ if and only if

$\displaystyle L(\alpha_{1},\ldots,\alpha_{m})=\\{\boldsymbol{0}\\}.$

Being a subgroup of the free finitely generated abelian group
$\mathbb{Z}^{m}$, the group $L(\boldsymbol{\lambda})$ is also free and admits
a finite basis.

The following theorem, due to David Masser, allows us to effectively determine
$L(\boldsymbol{\lambda})$, and in particular decide whether it is equal to
$\\{\boldsymbol{0}\\}$. This result can be found in Masser [1988].

######  Theorem 1 (Masser)

The free abelian group $L(\boldsymbol{\lambda})$ has a basis
$\boldsymbol{v}_{1},\ldots,\boldsymbol{v}_{l}\in\mathbb{Z}^{m}$ for which

$\displaystyle\max\limits_{1\leq i\leq l,1\leq j\leq m}\lvert
v_{i,j}\rvert\leq(D\log H)^{O(m^{2})}$

where $H$ and $D$ bound respectively the heights and degrees of all the
$\lambda_{i}$.

Together with the following result, due to Alan Baker, Masser’s theorem allows
us to eliminate all algebraic relations in the description of linear forms in
logarithms of algebraic numbers. In particular, it also yields a method for
comparing linear forms in logarithms of algebraic numbers: test whether their
difference is zero and, if not, approximate it numerically to sufficient
precision, so as to infer its sign. Note that the set of linear forms in
logarithms of algebraic numbers is closed under addition and under
multiplication by algebraic numbers, as well as under complex conjugation. See
Baker [1975] and Baker and Wüstholz [1993].

######  Theorem 2 (Baker)

Let $\alpha_{1},\ldots,\alpha_{m}\in\overline{\mathbb{Q}}\setminus\\{0\\}$. If

$\displaystyle\log(\alpha_{1}),\ldots,\log(\alpha_{m})$

are linearly independent over $\mathbb{Q}$, then

$\displaystyle 1,\log(\alpha_{1}),\ldots,\log(\alpha_{m})$

are linearly independent over $\overline{\mathbb{Q}}$.

The theorem below was proved by Ferdinand von Lindemann in 1882, and later
generalised by Karl Weierstrass in what is now known as the Lindemann-
Weierstrass theorem. As a historical note, this result was behind the first
proof of transcendence of $\pi$, which immediately follows from it.

######  Theorem 3 (Lindemann)

If $\alpha\in\overline{\mathbb{Q}}\setminus\\{0\\}$, then $e^{\alpha}$ is
transcendental.

We will also need the following result, due to Leopold Kronecker, on
simultaneous Diophantine approximation, which generalises Dirichlet’s
Approximation Theorem. We denote the _group of additive relations_ of
$\boldsymbol{v}$ by

$\displaystyle
A(\boldsymbol{v})=\\{\boldsymbol{z}\in\mathbb{Z}^{d}:\boldsymbol{z}\cdot\boldsymbol{v}\in\mathbb{Z}\\}.$

Throughout this paper, $\operatorname{dist}$ refers to the $l_{1}$ distance.

######  Theorem 4 (Kronecker)

Let $\boldsymbol{\alpha}_{1},\ldots,\boldsymbol{\alpha_{k}}\in\mathbb{R}^{d}$
and $\boldsymbol{\beta}\in\mathbb{R}^{d}$. The following are equivalent:

  1. 1.

For any $\varepsilon>0$, there exists $\boldsymbol{n}\in\mathbb{N}^{k}$ such
that

$\displaystyle\operatorname{dist}(\boldsymbol{\beta}+\sum\limits_{i=1}^{k}n_{i}\boldsymbol{\alpha}_{i},\mathbb{Z}^{d})\leq\varepsilon.$

  2. 2.

It holds that

$\displaystyle\bigcap\limits_{i=1}^{k}A(\boldsymbol{\alpha}_{i})\subseteq
A(\boldsymbol{\beta}).$

Many of these results, or slight variations thereof, can be found in Hardy and
Wright [1938] and Cassels [1965].

###  2.2 Lattices

Consider a non-zero matrix $K\in\overline{\mathbb{Q}}^{r\times d}$ and vector
$\boldsymbol{k}\in\overline{\mathbb{Q}}^{r}$. The following proposition shows
how to compute a representation of the affine lattice
$\\{\boldsymbol{x}\in\mathbb{Z}^{d}:K\boldsymbol{x}=\boldsymbol{k}\\}$.
Further information about lattices can be found in Micciancio and Goldwasser
[2002] and Cohen [1993].

###### Proposition 1

There exist $\boldsymbol{x}_{0}\in\mathbb{Z}^{d}$ and $M\in\mathbb{Z}^{d\times
s}$, where $s<r$, such that

$\displaystyle\\{\boldsymbol{x}\in\mathbb{Z}^{d}:K\boldsymbol{x}=\boldsymbol{k}\\}=\boldsymbol{x}_{0}+\\{M\boldsymbol{y}:\boldsymbol{y}\in\mathbb{Z}^{s}\\}\,.$

######  Proof 2.5.

Let $\theta$ denote a primitive element of the number field generated by the
entries of $K$ and $\boldsymbol{k}$. Let the degree of this extension, which
equals the degree of $\theta$, be $D$. Then for
$\boldsymbol{x}\in\mathbb{Z}^{d}$ one can write

$\displaystyle K\boldsymbol{x}=\boldsymbol{k}$
$\displaystyle\Leftrightarrow\left(\sum\limits_{i=0}^{D-1}N_{i}\theta^{i}\right)\boldsymbol{x}=\sum\limits_{i=0}^{D-1}\boldsymbol{k}_{i}\theta^{i}$
$\displaystyle\Leftrightarrow N_{i}\boldsymbol{x}=\boldsymbol{k}_{i},\forall
i\in\\{0,\ldots,D-1\\},$

for some integer matrices $N_{0},\ldots,N_{D-1}\in\mathbb{Z}^{r\times d}$ and
integer vectors
$\boldsymbol{k}_{0},\ldots,\boldsymbol{k}_{D-1}\in\mathbb{Z}^{r}$. The
solution of each of these equations is clearly an affine lattice, and
therefore so is their intersection.

###  2.3 Matrix exponentials

Given a matrix $A\in\mathbb{C}^{n\times n}$, its exponential is defined as

$\displaystyle\exp(A)=\sum\limits_{i=0}^{\infty}\frac{A^{i}}{i!}.$

The series above always converges, and so the exponential of a matrix is
always well defined. The standard way of computing $\exp(A)$ is by finding
$P\in\mathit{GL}_{n}(\mathbb{C})$ such that $J=P^{-1}AP$ is in Jordan
Canonical Form, and by using the fact that $\exp(A)=P\exp(J)P^{-1}$, where
$\exp(J)$ is easy to compute. When $A\in\overline{\mathbb{Q}}^{n\times n}$,
$P$ can be taken to be in $GL_{n}(\overline{\mathbb{Q}})$; note that

$\displaystyle\mbox{if }J$
$\displaystyle=\begin{pmatrix}\lambda&&1&&0&&\cdots&&0\\\
0&&\lambda&&1&&\cdots&&0\\\ \vdots&&\vdots&&\ddots&&\ddots&&\vdots\\\
0&&0&&\cdots&&\lambda&&1\\\ 0&&0&&\cdots&&0&&\lambda\end{pmatrix}\mbox{ then
}$ $\displaystyle\exp(Jt)$ $\displaystyle=\exp(\lambda
t)\begin{pmatrix}1&&t&&\frac{t^{2}}{2}&&\cdots&&\frac{t^{k-1}}{(k-1)!}\\\
0&&1&&t&&\cdots&&\frac{t^{k-2}}{(k-2)!}\\\
\vdots&&\vdots&&\ddots&&\ddots&&\vdots\\\ 0&&0&&\cdots&&1&&t\\\
0&&0&&\cdots&&0&&1\end{pmatrix}.$

Then $\exp(J)$ can be obtained by setting $t=1$, in particular
$\exp(J)_{ij}=\frac{\exp(\lambda)}{(j-i)!}$ if $j\geq i$ and $0$ otherwise.

When $A$ and $B$ commute, so must $\exp(A)$ and $\exp(B)$. Moreover, when $A$
and $B$ have algebraic entries, the converse also holds, as shown in Wermuth
[1989]. Also, when $A$ and $B$ commute, it holds that
$\exp(A)\exp(B)=\exp(A+B)$.

###  2.4 Matrix logarithms

The matrix $B$ is said to be a logarithm of the matrix $A$ if $\exp(B)=A$. It
is well known that a logarithm of a matrix $A$ exists if and only if $A$ is
invertible. However, matrix logarithms need not be unique. In fact, there
exist matrices admitting uncountably many logarithms. See, for example, Culver
[1966] and Helton [1968].

A matrix is said to be unitriangular if it is triangular and all its diagonal
entries equal $1$. Crucially, the following uniqueness result holds:

######  Theorem 2.6.

Given an upper unitriangular matrix $M\in\mathbb{C}^{n\times n}$, there exists
a unique strictly upper triangular matrix $L$ such that $\exp(L)=M$. Moreover,
the entries of $L$ lie in the number field $\mathbb{Q}(M_{i,j}:1\leq i,j\leq
n)$.

######  Proof 2.7.

Firstly, we show that, for any strictly upper triangular matrix $T$ and for
any $1<m<n$ and $i<j$, the term $(T^{m})_{i,j}$ is polynomial on the elements
of the set $\\{T_{r,s}:s-r<j-i\\}$. This can be seen by induction on $m$, as
each $T^{m}$ is strictly upper triangular, and so

$\displaystyle(T^{m})_{i,j}=\sum\limits_{l=1}^{n}(T^{m-1})_{i,l}T_{l,j}=\sum\limits_{l=i+1}^{j-1}(T^{m-1})_{i,l}T_{l,j}.$

Finally, we show, by induction on $j-i$, that each $L_{i,j}$ is polynomial on
the elements of the set

$\displaystyle\\{M_{i,j}\\}\cup\\{M_{r,s}:s-r<j-i\\}.$

If $j-i\leq 0$, then $L_{i,j}=0$, so the claim holds. When $j-i>0$, as $L$ is
nilpotent,

$\displaystyle M_{i,j}$
$\displaystyle=\exp(L)_{i,j}=L_{i,j}+\sum\limits_{m=2}^{n-1}\frac{1}{m!}(L^{m})_{i,j}$
$\displaystyle\Rightarrow L_{i,j}$
$\displaystyle=M_{i,j}-\sum\limits_{m=2}^{n-1}\frac{1}{m!}(L^{m})_{i,j}.$

The result now follows from the induction hypothesis and from our previous
claim, as this argument can be used to both construct such a matrix $L$ and to
prove that it is uniquely determined.

###  2.5 Properties of commuting matrices

We will now present a useful decomposition of $\mathbb{C}^{n}$ induced by the
commuting matrices $A_{1},\ldots,A_{k}\in\mathbb{C}^{n\times n}$. Let
$\sigma(A_{i})$ denote the spectrum of the matrix $A_{i}$. In what follows,
let

$\displaystyle\boldsymbol{\lambda}=(\lambda_{1},\ldots,\lambda_{k})\in\sigma(A_{1})\times\cdots\times\sigma(A_{k}).$

We remind the reader that $\ker(A_{i}-\lambda_{i})^{n}$ corresponds to the
generalised eigenspace of $\lambda_{i}$ of $A_{i}$. Moreover, we define the
following subspaces:

$\displaystyle\mathcal{V}_{\boldsymbol{\lambda}}=\bigcap\limits_{i=1}^{k}\ker(A_{i}-\lambda_{i}I)^{n}.$

Also, let
$\Sigma=\\{\boldsymbol{\lambda}\in\sigma(A_{1})\times\cdots\times\sigma(A_{k}):\mathcal{V}_{\boldsymbol{\lambda}}\neq\\{\boldsymbol{0}\\}\\}$.

######  Theorem 2.8.

For all $\boldsymbol{\lambda}=(\lambda_{1},\ldots,\lambda_{k})\in\Sigma$ and
for all $i\in\\{1,\ldots,k\\}$, the following properties hold:

  1. 1.

$\mathcal{V}_{\boldsymbol{\lambda}}$ is invariant under $A_{i}$.

  2. 2.

$\sigma(A_{i}\restriction_{\mathcal{V}_{\boldsymbol{\lambda}}})=\\{\lambda_{i}\\}$.

  3. 3.

$\mathbb{C}^{n}=\bigoplus\limits_{\boldsymbol{\lambda}\in\Sigma}\mathcal{V}_{\boldsymbol{\lambda}}.$

######  Proof 2.9.

We show, by induction on $k$, that the subspaces
$\mathcal{V}_{\boldsymbol{\lambda}}$ satisfy the properties above.

When $k=1$, the result follows from the existence of Jordan Canonical Forms.
When $k>1$, suppose that $\sigma(A_{k})=\\{\mu_{1},\ldots,\mu_{m}\\}$, and let
$\mathcal{U}_{j}=\ker(A_{k}-\mu_{j}I)^{n}$, for $j\in\\{1,\ldots,m\\}$. Again,
it follows from the existence of Jordan Canonical Forms that

$\displaystyle\mathbb{C}^{n}=\bigoplus\limits_{j=1}^{m}\mathcal{U}_{m}.$

In what follows, $i\in\\{1,\ldots,k-1\\}$ and $j\in\\{1,\ldots,m\\}$. Now, as
$A_{k}$ and $A_{i}$ commute, so do $(A_{k}-\mu_{j}I)$ and $A_{i}$. Therefore,
for all $\boldsymbol{v}\in\mathcal{U}_{j}$,
$(A_{k}-\mu_{j}I)^{n}A_{i}\boldsymbol{v}=A_{i}(A-\mu_{j}I)^{n}\boldsymbol{v}=\boldsymbol{0}$,
so $A_{i}\boldsymbol{v}\in\mathcal{U}_{j}$, that is, $\mathcal{U}_{j}$ is
invariant under $A_{i}$. The result follows from applying the induction
hypothesis to the commuting operators $A_{i}\restriction_{\mathcal{U}_{j}}$.

We will also make use of the following well-known result on simultaneous
triangularisation of commuting matrices. See, for example, Newman [1967].

######  Theorem 2.10.

Given $k$ commuting matrices
$A_{1},\ldots,A_{k}\in\overline{\mathbb{Q}}^{n\times n}$, there exists a
matrix $P\in\mathit{GL}_{n}(\overline{\mathbb{Q}})$ such that $P^{-1}A_{i}P$
is upper triangular for all $i\in\\{1,\ldots,k\\}$.

###  2.6 Convex Polyhedra and Semi-Algebraic Sets

A convex polyhedron is a subset of $\mathbb{R}^{n}$ of the form
$\mathcal{P}=\\{\boldsymbol{x}\in\mathbb{R}^{n}:A\boldsymbol{x}\leq\boldsymbol{b}\\}$,
where $A$ is a $d\times n$ matrix and $\boldsymbol{b}\in\mathbb{R}^{d}$. When
all the entries of $A$ and coordinates of $\boldsymbol{b}$ are algebraic
numbers, the convex polyhedron $\mathcal{P}$ is said to have an algebraic
description.

A set $S\subseteq\mathbb{R}^{n}$ is said to be semi-algebraic if it is a
Boolean combination of sets of the form
$\\{\boldsymbol{x}\in\mathbb{R}^{n}:p(\boldsymbol{x})\geq 0\\}$, where $p$ is
a polynomial with integer coefficients. Equivalently, the semi-algebraic sets
are those definable by the quantifier-free first-order formulas over the
structure $(\mathbb{R},<,+,\cdot,0,1)$.

It was shown by Alfred Tarski in Tarski [1951] that the first-order theory of
reals admits quantifier elimination. Therefore, the semi-algebraic sets are
precisely the first-order definable sets.

######  Theorem 2.11 (Tarski).

The first-order theory of reals is decidable.

See Renegar [1992] and Basu et al. [2006] for more efficient decision
procedures for the first-order theory of reals.

######  Definition 2.12 (Hilbert’s Tenth Problem).

Given a polynomial $p\in\mathbb{Z}[x_{1},\ldots,x_{k}]$, decide whether
$p(\boldsymbol{x})=0$ admits a solution $\boldsymbol{x}\in\mathbb{N}^{k}$.
Equivalently, given a semi-algebraic set $S\subseteq\mathbb{R}^{k}$, decide
whether it intersects $\mathbb{Z}^{k}$.

The following celebrated theorem, due to Yuri Matiyasevich, will be used in
our undecidability proof; see Matiyasevich [1993] for a self-contained proof.

######  Theorem 2.13 (Matiyasevich).

Hilbert’s Tenth Problem is undecidable.

On the other hand, our proof of decidability of ALIP makes use of some
techniques present in the proof of the following result, shown in Khachiyan
and Porkolab [1997]:

######  Theorem 2.14 (Khachiyan and Porkolab).

It is decidable whether a given _convex_ semi-algebraic set
$S\subseteq\mathbb{R}^{k}$ intersects $\mathbb{Z}^{k}$.

###  2.7 Fourier-Motzkin Elimination

Fourier-Motzkin elimination is a simple method for solving systems of
inequalities. Historically, it was the first algorithm used in solving linear
programming, before more efficient procedures such as the simplex algorithm
were discovered. The procedure consists in isolating one variable at a time
and matching all its lower and upper bounds. Note that this method preserves
the set of solutions on the remaining variables, so a solution of the reduced
system can always be extended to a solution of the original one.

######  Theorem 2.15.

By using Fourier-Motzkin elimination, it is decidable whether a given convex
polyhedron $\mathcal{P}=\\{\boldsymbol{x}\in\mathbb{R}^{n}:\pi
A\boldsymbol{x}<\boldsymbol{b}\\}$, where the entries of $A$ are all real
algebraic numbers and those of $\boldsymbol{b}$ are real linear forms in
logarithms of algebraic numbers, is empty. Moreover, if $\mathcal{P}$ is non-
empty one can effectively find a rational vector
$\boldsymbol{q}\in\mathcal{P}$.

######  Proof 2.16.

When using Fourier-Motzkin elimination, isolate each term $\pi x_{i}$, instead
of just isolating the variable $x_{i}$. Note that the coefficients of the
terms $\pi x_{i}$ will always be algebraic, and the loose constants will
always be linear forms in logarithms of algebraic numbers, which are closed
under multiplication by algebraic numbers, and which can be effectively
compared by using Baker’s Theorem.

##  3 Example

Let $\lambda_{1},\lambda_{2}\in\mathbb{R}\cap\bar{\mathbb{Q}}$ such that
$\lambda_{1}>\lambda_{2}$ and consider the following commuting matrices
$A_{1},A_{2}\in(\mathbb{R}\cap\bar{\mathbb{Q}})^{2\times 2}$:

$\displaystyle A_{i}=\begin{pmatrix}\lambda_{i}&&1\\\
0&&\lambda_{i}\end{pmatrix},i\in\\{1,2\\}.$

One can easily see that

$\displaystyle\exp(A_{i}t_{i})$
$\displaystyle=\exp(\lambda_{i}t_{i}I)\exp(t_{i}(A_{i}-\lambda_{i}I))$
$\displaystyle=\exp(\lambda_{i}t_{i})\exp\begin{pmatrix}0&&t_{i}\\\
0&&0\end{pmatrix}$
$\displaystyle=\exp(\lambda_{i}t_{i})\begin{pmatrix}1&&t_{i}\\\
0&&1\end{pmatrix},i\in\\{1,2\\}.$

Let $c_{1},c_{2}\in\mathbb{R}\cap\bar{\mathbb{Q}}$ such that $c_{1},c_{2}>0$,
and let

$\displaystyle C=\begin{pmatrix}c_{1}&&c_{2}\\\ 0&&c_{1}\end{pmatrix}.$

We would like to determine whether there exists a solution
$t_{1},t_{2}\in\mathbb{R}$, $t_{1},t_{2}\geq 0$ to

$\displaystyle\exp(A_{1}t_{1})\exp(A_{2}t_{2})=C$

This amounts to solving the following system of equations:

$\displaystyle\begin{cases}\exp(\lambda_{1}t_{1}+\lambda_{2}t_{2})=c_{1}\\\
(t_{1}+t_{2})\exp(\lambda_{1}t_{1}+\lambda_{2}t_{2})=c_{2}\end{cases}$
$\displaystyle\Leftrightarrow$
$\displaystyle\begin{cases}\exp(t_{1}(\lambda_{1}-\lambda_{2})+\frac{c_{2}}{c_{1}}\lambda_{2})=c_{1}\\\
t_{2}=\frac{c_{2}}{c_{1}}-t_{1}\end{cases}$ $\displaystyle\Leftrightarrow$
$\displaystyle\begin{cases}t_{1}=\frac{\log(c_{1})-\frac{c_{2}}{c_{1}}\lambda_{2}}{\lambda_{1}-\lambda_{2}}\\\
t_{2}=\frac{\frac{c_{2}}{c_{1}}\lambda_{1}-\log(c_{1})}{\lambda_{1}-\lambda_{2}}\end{cases}$

Then $t_{1},t_{2}\geq 0$ holds if and only if

$\displaystyle\lambda_{2}\leq\frac{c_{1}}{c_{2}}\log(c_{1})\leq\lambda_{1}.$

Whether these inequalities hold amounts to comparing linear forms in
logarithms of algebraic numbers.

##  4 Decidability in the Commutative Case

We start this section by reducing the Generalised MEP with commuting matrices
to LEP. The intuition behind it is quite simple: perform a change of basis so
that the matrices $A_{1},\ldots,A_{k}$, as well as $C$, become block-diagonal
matrices, with each block being upper triangular; we can then separate the
problem into several sub-instances, corresponding to the diagonal blocks, and
finally make use of our uniqueness result concerning strictly upper triangular
logarithms of upper unitriangular matrices.

######  Theorem 4.17.

The Generalised MEP with commuting matrices reduces to LEP.

######  Proof 4.18.

Consider an instance of the generalised MEP, as given in Definition 4, with
commuting $n\times n$ matrices $A_{1},\ldots,A_{k}$ and target matrix $C$.

We first show how to define a matrix $P$ such that each matrix $P^{-1}A_{i}P$
is block diagonal, $i=1,\ldots,k$, with each block being moreover upper
triangular.

By Theorem 2.8 we can write $\mathbb{C}^{n}$ as a direct sum of subspaces
$\mathbb{C}^{n}=\oplus_{j=1}^{b}\mathcal{V}_{j}$ such that for every subspace
$\mathcal{V}_{j}$ and matrix $A_{i}$, $\mathcal{V}_{j}$ is an invariant
subspace of $A_{i}$ on which $A_{i}$ has a single eigenvalue
$\lambda_{i}^{(j)}$.

Define a matrix $Q$ by picking an algebraic basis for each $\mathcal{V}_{j}$
and successively taking the vectors of each basis to be the columns of $Q$.
Then, each matrix $Q^{-1}A_{i}Q$ is block-diagonal, where the $j$-th block is
a matrix $B^{(j)}_{i}$ that represents $A_{i}\restriction{\mathcal{V}_{j}}$,
$j=1,\ldots,b$.

Fixing $j\in\\{1,\ldots,b\\}$, note that the matrices
$B_{1}^{(j)},\ldots,B_{k}^{(j)}$ all commute. Thus we may apply Theorem 2.10
to obtain an algebraic matrix $M_{j}$ such that each matrix
$M_{j}^{-1}B^{(j)}_{i}M_{j}$ is upper triangular, $i=1,\ldots,k$. Thus we can
write

$M_{j}^{-1}B^{(j)}_{i}M_{j}=\lambda_{i}^{(j)}I+N_{i}^{(j)}$

for some strictly upper triangular matrix $N_{i}^{(j)}$.

We define $M$ to be the block-diagonal matrix with blocks
$M_{1},\ldots,M_{b}$. Letting $P=QM$, it is then the case that $P^{-1}A_{i}P$
is block-diagonal, with the $j$-th block being
$\lambda_{i}^{(j)}I+N_{i}^{(j)}$ for $j=1,\ldots,b$. Now

$\displaystyle\prod\limits_{i=1}^{k}\exp(A_{i}t_{i})=C\Leftrightarrow\prod\limits_{i=1}^{k}\exp(P^{-1}A_{i}Pt_{i})=P^{-1}CP.$
(3)

If $P^{-1}CP$ is not block-diagonal, with each block being upper triangular
and with the same entries along the diagonal, then Equation (3) has no
solution and the problem instance must be negative. Otherwise, denoting the
blocks $P^{-1}CP$ by $D^{(j)}$ for $j\in\\{1,\ldots,b\\}$, our problem amounts
to simultaneously solving the system of matrix equations

$\displaystyle\prod\limits_{i=1}^{k}\exp\big{(}\big{(}\lambda_{i}^{(j)}I+N_{i}^{(j)}\big{)}t_{i}\big{)}=D^{(j)},\quad
j\in\\{1,\ldots,b\\}$ (4)

with one equation for each block.

For each fixed $j$, the matrices $N_{i}^{(j)}$ inherit commutativity from the
matrices $B^{(j)}_{i}$, so we have

$\displaystyle\prod\limits_{i=1}^{k}\exp((\lambda_{i}^{(j)}I+N_{i}^{(j)})t_{i})$
$\displaystyle=\exp\big{(}\sum_{i=1}^{k}(\lambda_{i}^{(j)}I+N_{i}^{(j)})t_{i}\big{)}$
$\displaystyle=\exp\big{(}\sum_{i=1}^{k}\lambda_{i}^{(j)}t_{i}\big{)}\cdot\exp\big{(}\sum_{i=1}^{k}N_{i}^{(j)}t_{i}\big{)}.$

Hence the system (4) is equivalent to

$\displaystyle\exp\big{(}\sum_{i=1}^{k}\lambda_{i}^{(j)}t_{i}\big{)}\cdot\exp\big{(}\sum_{i=1}^{k}N_{i}^{(j)}t_{i}\big{)}=D^{(j)}$
(5)

for $j=1,\ldots,b$.

By assumption, the diagonal entries of each matrix $D^{(j)}$ are equal to a
unique value, say $c^{(j)}$. Since the diagonal entries of
$\exp\left(\sum_{i=1}^{k}N^{(j)}t_{i}\right)$ are all $1$, the equation system
(5) is equivalent to:

$\displaystyle\exp\big{(}\sum_{i=1}^{k}\lambda_{i}^{(j)}t_{i}\big{)}=c^{(j)}\mbox{
and
}\exp\big{(}\sum_{i=1}^{k}N_{i}^{(j)}t_{i}\big{)}=\frac{1}{c^{(j)}}D^{(j)}$

for $j=1,\ldots,b$.

Applying Theorem 2.6, the above system can equivalently be written

$\displaystyle\exp\big{(}\sum_{i=1}^{k}\lambda_{i}^{(j)}t_{i}\big{)}=c^{(j)}\mbox{
and }\sum_{i=1}^{k}N_{i}^{(j)}t_{i}=S^{(j)}$

for some effectively computable matrix $S^{(j)}$ with algebraic entries,
$j=1,\ldots,b$.

Except for the additional linear equations, this has the form of an instance
of LEP. However we can eliminate the linear equations by performing a linear
change of variables, i.e., by computing the solution of the system in
parametric form. Thus we finally arrive at an instance of LEP.

In the following result, we essentially solve the system of equations 2,
reducing it to the simpler problem that really lies at its heart.

######  Theorem 4.19.

LEP reduces to ALIP.

######  Proof 4.20.

Consider an instance of LEP, comprising a system of equations

$\displaystyle\exp\left(\sum_{\ell=1}^{k}\lambda_{\ell}^{(j)}t_{\ell}\right)=c_{j}\exp(d_{j})\quad
j=1,\ldots,b,$ (6)

and polyhedron $\mathcal{P}\subseteq\mathbb{R}^{2k}$, as described in
Definition 5.

Throughout this proof, let $\log$ denote a fixed logarithm branch that is
defined on all the numbers $c_{j},\exp(d_{j})$ appearing above, and for which
$\log(-1)=i\pi$. Note that if any $c_{j}=0$ for some $j$ then (6) has no
solution. Otherwise, by applying $\log$ to each equation in (6), we get:

$\displaystyle\sum_{\ell=1}^{k}\lambda_{\ell}^{(j)}t_{\ell}=d_{j}+\log(c_{j})+2i\pi
n_{j}\quad j=1,\ldots,b,$ (7)

where $n_{j}\in\mathbb{Z}$.

The system of equations (7) can be written in matrix form as

$\displaystyle
A\boldsymbol{t}\in\boldsymbol{d}+\log(\boldsymbol{c})+2i\pi\mathbb{Z}^{b}\,,$

where $A$ is the $b\times k$ matrix with $A_{j,\ell}=\lambda_{\ell}^{(j)}$ and
$\log$ is applied pointwise to vectors. Now, defining the convex polyhedron
$\mathcal{Q}\subseteq\mathbb{R}^{2b}$ by

$\displaystyle\mathcal{Q}=\\{$
$\displaystyle(\mathrm{Re}(A\boldsymbol{y}),\mathrm{Im}(A\boldsymbol{y})):\boldsymbol{y}\in\mathbb{C}^{k},(\mathrm{Re}(\boldsymbol{y}),\mathrm{Im}(\boldsymbol{y}))\in\mathcal{P}\\}\,,$

it suffices to decide whether the affine lattice
$\boldsymbol{d}+\log(\boldsymbol{c})+2i\pi\mathbb{Z}^{b}$ intersects
$\\{\boldsymbol{x}\in\mathbb{C}^{b}:(\mathrm{Re}(\boldsymbol{x}),\mathrm{Im}(\boldsymbol{x}))\in\mathcal{Q}\\}$.

Define $f:\mathbb{R}^{b}\rightarrow\mathbb{C}^{b}$ by
$f(\boldsymbol{v})=\boldsymbol{d}+\log(\boldsymbol{c})+2i\pi\boldsymbol{v}$,
and define a convex polyhedron $\mathcal{T}\subseteq\mathbb{R}^{b}$ by

$\mathcal{T}=\\{\boldsymbol{v}\in\mathbb{R}^{b}:(\mathrm{Re}(f(\boldsymbol{v})),\mathrm{Im}(f(\boldsymbol{v})))\in\mathcal{Q}\\}\,.$

The problem then amounts to deciding whether the convex polyhedron
$\mathcal{T}$ intersects contains an integer point. Crucially, the description
of the convex polyhedron $\mathcal{T}$ is of the form $\pi
B\boldsymbol{x}\leq\boldsymbol{b}$, for some matrix $B$ and vector
$\boldsymbol{b}$ such that the entries of $B$ are real algebraic and the
components of $\boldsymbol{b}$ are real linear forms in logarithms of
algebraic numbers. But this is the form of an instance of ALIP.

We are left with the task of showing that ALIP is decidable. The argument
essentially consists of reducing to a lower-dimensional instance whenever
possible, and eventually either using the fact that the polyhedron is bounded
to test whether it intersects the integer lattice or using Kronecker’s theorem
to show that, by a density argument, it must intersect the integer lattice.

######  Theorem 4.21.

ALIP is decidable.

######  Proof 4.22.

We are given a convex polyhedron
$\mathcal{P}=\\{\boldsymbol{x}\in\mathbb{R}^{d}:\pi
A\boldsymbol{x}\leq\boldsymbol{b}\\}$, where the coordinates $\boldsymbol{b}$
are linear forms in logarithms of algebraic numbers, and need to decide
whether this polyhedron intersects $\mathbb{Z}^{d}$. Throughout this proof,
$\log$ denotes the logarithm branch picked at the beginning of the proof of
Theorem 4.19. We start by eliminating linear dependencies between the
logarithms appearing therein, using Masser’s Theorem. For example, suppose
that

$\displaystyle
b_{i}=r_{0}+r_{1}\log(s_{1})+\cdots+r_{k}\log(s_{k}),r_{0},r_{1},s_{1},\ldots,r_{k},s_{k}\in\overline{\mathbb{Q}}.$

Due to Baker’s theorem, there exists a non-trivial linear relation with
algebraic coefficients amongs $\log(-1),\log(s_{1}),\ldots,\log(s_{k})$ if and
only if there is one with integer coefficients. But such relations can be
computed, since

$\displaystyle
n_{0}\log(-1)+n_{1}\log(s_{1})+\cdots+n_{k}\log(s_{k})=0\Leftrightarrow$
$\displaystyle(-1)^{n_{0}}s_{1}^{n_{1}}\cdots s_{k}^{n_{k}}=1$

and since the group of multiplicative relations $L(-1,s_{1},\ldots,s_{k})$ can
be effectively computed. Whenever it contains a non-zero vector, we use it to
eliminate an unnecessary $\log(s_{i})$ term, although never eliminating
$\log(-1)$. When this process is over, we can see whether each term
$b_{i}/\pi$ is algebraic or transcendental: it is algebraic if
$b_{i}=\alpha\log(-1),\alpha\in\overline{\mathbb{Q}}$, and transcendental
otherwise.

Now, when $\boldsymbol{x}\in\mathbb{Z}^{d}$, $A\boldsymbol{x}$ is a vector
with algebraic coefficients, so whenever $b_{i}/\pi$ is transcendental we may
alter $\mathcal{P}$ by replacing $\leq$ by $<$ in the $i$-th inequality,
preserving its intersection with $\mathbb{Z}^{d}$. On the other hand, whenever
$b_{i}/\pi$ is algebraic, we split our problem into two: in the first one,
$\mathcal{P}$ is altered to force equality on the $i$-th constraint (that is,
replacing $\leq$ by $=$), and in the second we force strict inequality (that
is, replacing $\leq$ by $<$). We do this for all $i$, so that no $\leq$ is
left in any problem instance, leaving us with finitely many polyhedra, each
defined by equations of the form

$\displaystyle K\boldsymbol{x}$ $\displaystyle=\boldsymbol{k}\quad$
$\displaystyle(\boldsymbol{k}\in\overline{\mathbb{Q}}^{d_{1}})$ $\displaystyle
M\boldsymbol{x}$ $\displaystyle<\boldsymbol{m}\quad$
$\displaystyle(\boldsymbol{m}\in\overline{\mathbb{Q}}^{d_{2}})$ $\displaystyle
F\boldsymbol{x}$ $\displaystyle<\boldsymbol{f}\quad$
$\displaystyle(\boldsymbol{f}\in\mathbb{R}\setminus\overline{\mathbb{Q}}^{d_{3}})$

where $K,M,F$ are matrices with algebraic entries. Before proceeding, we
eliminate all such empty polyhedra; note that emptiness can be decided via
Fourier-Motzkin elimination, as shown in Theorem 2.15.

The idea of the next step is to reduce the dimension of all the problem
instances at hand until we are left with a number of new instances with full-
dimensional open convex polyhedra, of the same form as the original one, apart
from the fact that all inequalities in their definitions will be strict. To do
that, we use the equations $K\boldsymbol{x}=\boldsymbol{k}$ to eliminate
variables: note that, whenever there is an integer solution,

$\displaystyle
K\boldsymbol{x}=\boldsymbol{k},\boldsymbol{x}\in\mathbb{Z}^{d}\Leftrightarrow\boldsymbol{x}=\boldsymbol{x}_{0}+M\boldsymbol{z},$

where $M$ is a matrix with integer entries, $\boldsymbol{x}_{0}$ is an integer
vector and $\boldsymbol{z}$ ranges over integer vectors over a smaller
dimension space, wherein we also define the polyhedron

$\displaystyle\mathcal{Q}=\\{\boldsymbol{y}:\boldsymbol{x}_{0}+M\boldsymbol{y}\in\mathcal{P}\\}.$

Having now eliminated all equality constraints, we are left with a finite set
of polyhedra of the form $\mathcal{P}=\\{\boldsymbol{x}\in\mathbb{R}^{d}:\pi
A\boldsymbol{x}<\boldsymbol{b}\\}$ that are either empty or full-dimensional
and open, and wish to decide whether they intersect the integer lattice of the
corresponding space (different instances may lie in spaces of different
dimensions, of course). Note that, when $\mathcal{P}$ is non-empty, we can use
Fourier-Motzkin elimination to find a vector $\boldsymbol{q}\in\mathbb{Q}^{d}$
in its interior, and $\varepsilon>0$ such that the $l_{1}$ closed ball of
radius $\varepsilon$ and centre $\boldsymbol{q}$, which we call $\mathcal{B}$,
is contained in $\mathcal{P}$.

The next step is to consider the Minkowski-Weyl decomposition of
$\mathcal{P}$, namely $\mathcal{P}=\mathcal{H}+\mathcal{C}$, where
$\mathcal{H}$ is the convex hull of finitely many points of $\mathcal{P}$
(which we need not compute) and
$\mathcal{C}=\\{\boldsymbol{x}\in\mathbb{R}^{d}:A\boldsymbol{x}\leq\boldsymbol{0}\\}$
is a cone with an algebraic description. Note that $\mathcal{P}$ is bounded if
and only if $\mathcal{C}=\\{\boldsymbol{0}\\}$, in which case the problem at
hand is simple: consider the polyhedron $\mathcal{Q}$ with an algebraic
description obtained by rounding up each coordinate of $\boldsymbol{b}/\pi$,
which has the same conic part as $\mathcal{P}$ and which contains
$\mathcal{P}$, and therefore is bounded; finally, compute a bound on
$\mathcal{Q}$ (such a bound can be defined in the first-order theory of
reals), which is also a bound on $\mathcal{P}$, and test the integer points
within that bound for membership in $\mathcal{P}$. Otherwise,

$\displaystyle\mathcal{C}=\\{\lambda_{1}\boldsymbol{c}_{1}+\cdots+\lambda_{k}\boldsymbol{c}_{k}:\lambda_{1},\ldots,\lambda_{k}\geq
0\\},$

where
$\boldsymbol{c}_{1},\ldots,\boldsymbol{c}_{k}\in\overline{\mathbb{Q}}^{d}$ are
the extremal rays of $\mathcal{C}$. Note that
$\boldsymbol{q}+\mathcal{C}\subseteq\mathcal{P}$ and that
$\mathcal{B}+\mathcal{C}\subseteq\mathcal{P}$.

Now we consider a variation of an argument which appears in Khachiyan and
Porkolab [1997]. Consider the computable set

$\displaystyle\mathcal{L}=\mathcal{C}^{\perp}\cap\mathbb{Z}^{d}=\bigcap\limits_{i=1}^{k}A(\boldsymbol{c}_{i}),$

where $A(\boldsymbol{v})$ denotes the group of additive relations of
$\boldsymbol{v}$.

If $\mathcal{L}=\\{\boldsymbol{0}\\}$ then due to Kronecker’s theorem on
simultaneous Diophantine approximation it must be the case that there exists a
vector $(n_{1},\ldots,n_{k})\in\mathbb{N}^{k}$ such that

$\displaystyle\operatorname{dist}\left(\boldsymbol{q}+\sum\limits_{i=1}^{k}n_{i}\boldsymbol{c}_{i},\mathbb{Z}^{d}\right)\leq\varepsilon,$

and we know that $\mathcal{P}\cap\mathbb{Z}^{d}\neq\emptyset$ from the fact
that the $l_{1}$ closed ball $\mathcal{B}$ of radius $\varepsilon$ and centre
$\boldsymbol{q}$ is contained in $\mathcal{P}$.

On the other hand, if $\mathcal{L}\neq\\{\boldsymbol{0}\\}$, let
$\boldsymbol{z}\in\mathcal{L}\setminus\\{\boldsymbol{0}\\}$. Since
$\mathcal{H}$ is a bounded subset of $\mathbb{R}^{n}$, the set

$\\{\boldsymbol{z}^{T}\boldsymbol{x}:\boldsymbol{x}\in\mathcal{P}\\}=\\{\boldsymbol{z}^{T}\boldsymbol{x}:\boldsymbol{x}\in\mathcal{H}\\}$

is a bounded subset of $\mathbb{R}$. Therefore there exist $a,b\in\mathbb{Z}$
such that

$\displaystyle\forall\boldsymbol{x}\in\mathcal{P},a\leq\boldsymbol{z}^{T}\boldsymbol{x}\leq
b,$

so we can reduce our problem to $b-a+1$ smaller-dimensional instances by
finding the integer points of
$\\{\boldsymbol{x}\in\mathcal{P}:\boldsymbol{z}^{T}\boldsymbol{x}=i\\}$, for
$i\in\\{a,\ldots,b\\}$. Note that we have seen earlier in the proof how to
reduce the dimension of the ambient space when the polyhedron $\mathcal{P}$ is
contained in an affine hyperplane.

##  5 Undecidability of the Non-Commutative Case

In this section we show that the Matrix-Exponential Problem is undecidable in
the case of non-commuting matrices. We show undecidability for the most
fundamental variant of the problem, as given in Definition 4, in which the
matrices have real entries and the variables $t_{i}$ range over the non-
negative reals. Recall that this problem is decidable in the commutative case
by the results of the previous section.

###  5.1 Matrix-Exponential Problem with Constraints

The proof of undecidability in the non-commutative case is by reduction from
Hilbert’s Tenth Problem. The reduction proceeds via several intermediate
problems. These problems are obtained by augmenting MEP with various classes
of arithmetic constraints on the real variables that appear in the statement
of the problem.

######  Definition 5.23.

We consider the following three classes of arithmetic constraints over real
variables $t_{1},t_{2},\ldots$:

  * •

$\mathcal{E}_{\pi\mathbb{Z}}$ comprises constraints of the form
$t_{i}\in\alpha+\beta\pi\mathbb{Z}$, where $\alpha$ and $\beta\neq 0$ are
real-valued constants such that $\cos(2\alpha\beta^{-1})$, $\beta$ are both
algebraic numbers.

  * •

$\mathcal{E}_{+}$ comprises linear equations of the form
$\alpha_{1}t_{1}+\ldots+\alpha_{n}t_{n}=\alpha_{0}$, for
$\alpha_{0},\ldots,\alpha_{n}$ real algebraic constants.

  * •

$\mathcal{E}_{\times}$ comprises equations of the form $t_{\ell}=t_{i}t_{j}$.

A class of constraints
$\mathcal{E}\subseteq\mathcal{E}_{\pi\mathbb{Z}}\cup\mathcal{E}_{+}\cup\mathcal{E}_{\times}$
induces a generalisation of the MEP problem as follows:

######  Definition 5.24 (MEP with Constraints).

Given a class of constraints
$\mathcal{E}\subseteq\mathcal{E}_{\pi\mathbb{Z}}\cup\mathcal{E}_{+}\cup\mathcal{E}_{\times}$,
the problem MEP$(\mathcal{E})$ is as follows. An instance consists of real
algebraic matrices $A_{1},\ldots,A_{k},C$ and a finite set of constraints
$E\subseteq\mathcal{E}$ on real variables $t_{1},\ldots,t_{k}$. The question
is whether there exist non-negative real values for $t_{1},\ldots,t_{k}$ such
that $\prod_{i=1}^{k}e^{A_{i}t_{i}}=C$ and the constraints $E$ are all
satisfied.

Note that in the above definition of MEP$(\mathcal{E})$ the set of constraints
$E$ only mentions real variables $t_{1},\ldots,t_{k}$ appearing in the matrix
equation $\prod_{i=1}^{k}e^{A_{i}t_{i}}=C$. However, without loss of
generality, we can allow constraints to mention fresh variables $t_{i}$, for
$i>k$, since we can always define a corresponding matrix $A_{i}=0$ for such
variables for then $e^{A_{i}t_{i}}=I$ has no effect on the matrix product. In
other words, we effectively have constraints in $\mathcal{E}$ with
existentially quantified variables. In particular, we have the following
useful observations:

  * •

We can express inequality constraints of the form $t_{i}\neq\alpha$ in
$\mathcal{E}_{+}\cup\mathcal{E}_{\times}$ by using fresh variables
$t_{j},t_{\ell}$. Indeed $t_{i}\neq\alpha$ is satisfied whenever there exist
values of $t_{j}$ and $t_{\ell}$ such that $t_{i}=t_{j}+\alpha$ and
$t_{j}t_{\ell}=1$.

  * •

By using fresh variables, $\mathcal{E}_{+}\cup\mathcal{E}_{\times}$ can
express polynomial constraints of the form $P(t_{1},\ldots,t_{n})=t$ for $P$ a
polynomial with integer coefficients.

We illustrate the above two observations in an example.

######  Example 5.25.

Consider the problem, given matrices $A_{1},A_{2}$ and $C$, to decide whether
there exist $t_{1},t_{2}\geq 0$ such that

$e^{A_{1}t_{1}}e^{A_{2}t_{2}}=C\,\mbox{ and }\,t_{1}^{2}-1=t_{2},t_{2}\neq
0\,.$

This is equivalent to the following instance of
MEP$(\mathcal{E}_{+}\cup\mathcal{E}_{\times})$: decide whether there exist
$t_{1},\ldots,t_{5}\geq 0$ such that

$\prod_{i=1}^{5}e^{A_{i}t_{i}}=C\,\mbox{ and
}\,t_{1}t_{1}=t_{3},t_{3}-1=t_{2},t_{2}t_{4}=t_{5},t_{5}=1$

where $A_{1},A_{2}$ and $C$ are as above and $A_{3}=A_{4}=A_{5}=0$.

We will make heavy use of the following proposition to combine several
instances of the constrained MEP into a single instance by combining matrices
block-wise.

######  Proposition 5.26.

Given real algebraic matrices $A_{1},\ldots,A_{k},C$ and
$A_{1}^{\prime},\ldots,A_{k}^{\prime},C^{\prime}$, there exist real algebraic
matrices $A_{1}^{\prime\prime},\ldots,A_{k}^{\prime\prime}$,
$C^{\prime\prime}$ such that for all $t_{1},\ldots,t_{k}$:

$\prod_{i=1}^{k}e^{A_{i}^{\prime\prime}t_{i}}=C^{\prime\prime}\qquad\Leftrightarrow\qquad\prod_{i=1}^{k}e^{A_{i}t_{i}}=C\wedge\prod_{i=1}^{k}e^{A_{i}^{\prime}t_{i}}=C^{\prime}.$

######  Proof 5.27.

Define for any $i\in\\{1,\ldots,k\\}$:

$A_{i}^{\prime\prime}=\begin{bmatrix}A_{i}&0\\\
0&A_{i}^{\prime}\end{bmatrix},\qquad C^{\prime\prime}=\begin{bmatrix}C&0\\\
0&C^{\prime}\end{bmatrix}.$

The result follows because the matrix exponential can be computed block-wise
(as is clear from its power series definition):

$\prod_{i=1}^{k}e^{A_{i}^{\prime\prime}t_{i}}=\prod_{i=1}^{k}\begin{bmatrix}e^{A_{i}t_{i}}&0\\\
0&e^{A_{i}^{\prime}t_{i}}\end{bmatrix}=\begin{bmatrix}\prod_{i=1}^{k}e^{A_{i}t_{i}}&0\\\
0&\prod_{i=1}^{k}e^{A_{i}^{\prime}t_{i}}\end{bmatrix}.$

We remark that in the statement of Proposition 5.26 the two matrix equations
that are combined are over the same set of variables. However, we can clearly
combine any two matrix equations for which the common variables appear in the
same order in the respective products.

The core of the reduction is to show that the constraints in
$\mathcal{E}_{\pi\mathbb{Z}},\mathcal{E}_{+}$ and $\mathcal{E}_{\times}$ do
not make the MEP problem harder: one can always encode them using the matrix
product equation.

######  Proposition 5.28.

MEP$(\mathcal{E}_{\pi\mathbb{Z}}\cup\mathcal{E}_{+}\cup\mathcal{E}_{\times})$
reduces to MEP$(\mathcal{E}_{+}\cup\mathcal{E}_{\times})$.

######  Proof 5.29.

Let $A_{1},\ldots,A_{k},C$ be real algebraic matrices and
$E\subseteq\mathcal{E}_{\pi\mathbb{Z}}\cup\mathcal{E}_{+}\cup\mathcal{E}_{\times}$
a finite set of constraints on $t_{1},\ldots,t_{k}$. Since $E$ is finite it
suffices to show how to eliminate from $E$ each constraint in
$\mathcal{E}_{\pi\mathbb{Z}}$.

Let $t_{j}\in\alpha+\beta\pi\mathbb{Z}$ be a constraint in $E$. By definition
of $\mathcal{E}_{\pi\mathbb{Z}}$ we have that
$\cos(2\alpha\beta^{-1}),\sin(2\alpha\beta^{-1})$ and $\beta\neq 0$ are real
algebraic. Now define the following extra matrices:

$A^{\prime}_{j}=\begin{bmatrix}0&2\beta^{-1}\\\
-2\beta^{-1}&0\end{bmatrix},C^{\prime}=\begin{bmatrix}\cos(2\alpha\beta^{-1})&\sin(2\alpha\beta^{-1})\\\
-\sin(2\alpha\beta^{-1})&\cos(2\alpha\beta^{-1})\end{bmatrix}.$

Our assumptions ensure that $A_{j}^{\prime}$ and $C^{\prime}$ are both real
algebraic.

We now have the following chain of equivalences:

$\displaystyle e^{A^{\prime}_{j}t_{j}}=C^{\prime}$
$\displaystyle\Leftrightarrow\begin{bmatrix}\cos(2t_{j}\beta^{-1})&\sin(2t_{j}\beta^{-1})\\\
-\sin(2t_{j}\beta^{-1})&\cos(2t_{j}\beta^{-1})\end{bmatrix}=C^{\prime}$
$\displaystyle\Leftrightarrow\cos(2t_{j}\beta^{-1})=\cos(2\alpha\beta^{-1})$
$\displaystyle\qquad\wedge\sin(2t_{j}\beta^{-1})=\sin(2\alpha\beta^{-1})$
$\displaystyle\Leftrightarrow 2\beta^{-1}t_{j}=2\alpha\beta^{-1}\mod 2\pi$
$\displaystyle\Leftrightarrow t_{j}\in\alpha+\beta\pi\mathbb{Z}.$

Thus the additional matrix equation $e^{A_{j}^{\prime}t_{j}}=C^{\prime}$ is
equivalent to the constraint $t_{j}\in\alpha+\beta\pi\mathbb{Z}$. Applying
Proposition 5.26 we can thus eliminate this constraint.

######  Proposition 5.30.

MEP$(\mathcal{E}_{+}\cup\mathcal{E}_{\times})$ reduces to
MEP$(\mathcal{E}_{+})$.

######  Proof 5.31.

Let $A_{1},\ldots,A_{k},C$ be real algebraic matrices and
$E\subseteq\mathcal{E}_{+}\cup\mathcal{E}_{\times}$ a finite set of
constraints on variables $t_{1},\ldots,t_{k}$. We proceed as above, showing
how to remove from $E$ each constraint from $\mathcal{E}_{\times}$. In so
doing we potentially increase the number of matrices and add new constraints
from $\mathcal{E}_{+}$.

Let $t_{l}=t_{i}t_{j}$ be an equation in $E$. To eliminate this equation the
first step is to introduce fresh variables $x,x^{\prime},y,y^{\prime},z$ and
add the constraints

$t_{i}=x,\,t_{j}=y,\,t_{\ell}=z,$

which are all in $\mathcal{E}_{+}$. We now add a new matrix equation over the
fresh variables $x,x^{\prime},y,y^{\prime},z$ that is equivalent to the
constraint $xy=z$. Since this matrix equation involves a new set of variables
we are free to the set the order of the matrix products, which is crucial to
express the desired constraint.

The key gadget is the following matrix product equation, which holds for any
$x,x^{\prime},y,y^{\prime},z\geqslant 0$:

$\displaystyle\begin{bmatrix}1&0&-z\\\ 0&1&0\\\
0&0&1\end{bmatrix}\begin{bmatrix}1&0&0\\\ 0&1&-y^{\prime}\\\
0&0&1\end{bmatrix}\begin{bmatrix}1&x&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix}$
$\displaystyle\qquad\times\begin{bmatrix}1&0&0\\\ 0&1&y\\\
0&0&1\end{bmatrix}\begin{bmatrix}1&-x^{\prime}&0\\\ 0&1&0\\\
0&0&1\end{bmatrix}=\begin{bmatrix}1&x-x^{\prime}&z-xy\\\ 0&1&y-y^{\prime}\\\
0&0&1\end{bmatrix}.$

Notice that each of the matrices on the left-hand side of the above equation
has a single non-zero off-diagonal entry. Crucially each matrix of this form
can be expressed as an exponential. Indeed we can write the above equation as
a matrix-exponential product

$e^{B_{1}z}e^{B_{2}y^{\prime}}e^{B_{3}x}e^{B_{4}y}e^{B_{5}x^{\prime}}=\begin{bmatrix}1&x-x^{\prime}&z-xy\\\
0&1&y-y^{\prime}\\\ 0&0&1\end{bmatrix}$

for matrices

$\begin{array}[]{r@{}cp{.1cm}r@{}c}B_{1}=&\begin{bmatrix}0&0&-1\\\ 0&0&0\\\
0&0&0\end{bmatrix}&&B_{2}=&\begin{bmatrix}0&0&0\\\ 0&0&-1\\\
0&0&0\end{bmatrix}\\\ B_{3}=&\begin{bmatrix}0&1&0\\\ 0&0&0\\\
0&0&0\end{bmatrix}&&B_{4}=&\begin{bmatrix}0&0&0\\\ 0&0&1\\\
0&0&0\end{bmatrix}\\\ B_{5}=&\begin{bmatrix}0&-1&0\\\ 0&0&0\\\
0&0&0\end{bmatrix}&&\end{array}$

Thus the constraint $xy=z$ can be expressed as

$\displaystyle
e^{B_{1}z}e^{B_{2}y^{\prime}}e^{B_{3}x}e^{B_{4}y}e^{B_{5}z^{\prime}}=I\,.$ (8)

Again, we can apply Proposition 5.26 to combine the equation (8) with the
matrix equation from the original problem instance and thus encode the
constraint $x=yz$.

######  Proposition 5.32.

MEP$(\mathcal{E}_{+})$ reduces to MEP.

######  Proof 5.33.

Let $A_{1},\ldots,A_{k},C$ be real algebraic matrices and
$E\subseteq\mathcal{E}_{+}$ a set of constraints. We proceed as above, showing
how to eliminate each constraint from $E$ that lies in $\mathcal{E}_{+}$,
while preserving the set of solutions of the instance.

Let $\beta+\sum_{i=1}^{k}\alpha_{i}t_{i}=0$ be an equation in $E$. Recall that
$\beta,\alpha_{1},\ldots,\alpha_{k}$ are real algebraic. Define the extra
matrices $A_{1}^{\prime},\ldots,A_{k}^{\prime}$ and $C^{\prime}$ as follows:

$A_{i}^{\prime}=\begin{bmatrix}0&\alpha_{i}\\\ 0&0\end{bmatrix},\qquad
C^{\prime}=\begin{bmatrix}1&-\beta\\\ 0&1\end{bmatrix}.$

Our assumptions ensure that $A_{1}^{\prime},\ldots,A_{k}^{\prime}$ and
$C^{\prime}$ are all real algebraic. Furthermore, the following extra product
equation becomes:

$\displaystyle\prod_{i=1}^{k}e^{A_{i}^{\prime}t_{i}}=C$
$\displaystyle\Leftrightarrow\prod_{i=1}^{k}\begin{bmatrix}1&\alpha_{i}t_{i}\\\
0&1\end{bmatrix}=\begin{bmatrix}1&-\beta\\\ 0&1\end{bmatrix}$
$\displaystyle\Leftrightarrow\sum_{i=1}^{k}\alpha_{i}t_{i}=-\beta\,.$

Combining Propositions 5.28, 5.30, and 5.32 we have:

######  Proposition 5.34.

MEP$(\mathcal{E}_{\pi\mathbb{Z}}\cup\mathcal{E}_{+}\cup\mathcal{E}_{\times})$
reduces to MEP.

###  5.2 Reduction from Hilbert’s Tenth Problem

######  Theorem 5.35.

MEP is undecidable in the non-commutative case.

######  Proof 5.36.

We have seen in the previous section that the problem
MEP$(\mathcal{E}_{\pi\mathbb{Z}}\cup\mathcal{E}_{+}\cup\mathcal{E}_{\times})$
reduces to MEP without constraints. Thus it suffices to reduce Hilbert’s Tenth
Problem to
MEP$(\mathcal{E}_{\pi\mathbb{Z}}\cup\mathcal{E}_{+}\cup\mathcal{E}_{\times})$.
In fact the matrix equation will not play a role in the target of this
reduction, only the additional constraints.

Let $P$ be a polynomial of total degree $d$ in $k$ variables with integer
coefficients. From $P$ we build a homogeneous polynomial $Q$, by adding a new
variable $\lambda$:

$Q(\mathbf{x},\lambda)=\lambda^{d}P\left(\frac{x_{1}}{\lambda},\ldots,\frac{x_{k}}{\lambda}\right).$

Note that $Q$ still has integer coefficients. Furthermore, we have the
relationship

$Q(\mathbf{x},1)=P(\mathbf{x}).$

As we have seen previously, it is easy to encode $Q$ with constraints, in the
sense that we can compute a finite set of constraints
$E_{Q}\subseteq\mathcal{E}_{+}\cup\mathcal{E}_{\times}$ mentioning variables
$t_{0},\ldots,t_{m},\lambda$ such that $E$ is satisfied if and only if
$t_{0}=Q(t_{1},\ldots,t_{k},\lambda)$. Note that $E_{Q}$ may need to mention
variables other than $t_{1},\ldots,t_{k}$ to do that. Another finite set of
equations $E_{\pi\mathbb{Z}}\subseteq\mathcal{E}_{\pi\mathbb{Z}}$ is used to
encode that $t_{1},\ldots,t_{k},\lambda\in\pi\mathbb{Z}$. Finally,
$E_{=}\subseteq\mathcal{E}_{+}\cup\mathcal{E}_{\times}$ is used to encode
$t_{0}=0$ and $1\leqslant\lambda\leqslant 4$. The latter is done by adding the
polynomial equations $\lambda=1+\alpha^{2}$ and $\lambda=4-\beta^{2}$ for some
$\alpha$ and $\beta$. Finally we have the following chain of equivalences:

$\displaystyle\exists t_{0},\ldots,\lambda\geqslant 0\text{ s.t. }E_{Q}\cup
E_{\pi\mathbb{Z}}\cup E_{=}\text{ is satisfied }$
$\displaystyle\qquad\Leftrightarrow\exists t_{1},\ldots,\lambda\geqslant
0\text{ s.t. }0=Q(t_{1},\ldots,t_{k},\lambda)$
$\displaystyle\qquad\qquad\wedge
t_{1},\ldots,t_{k},\lambda\in\pi\mathbb{Z}\wedge 1\leqslant\lambda\leqslant 4$
$\displaystyle\qquad\Leftrightarrow\exists
n_{1},\ldots,n_{k}\in\mathbb{N}\text{ s.t. }0=Q(\pi n_{1},\ldots,\pi
n_{k},\pi)$ $\displaystyle\qquad\Leftrightarrow\exists
n_{1},\ldots,n_{k}\in\mathbb{N}\text{ s.t. }0=\pi^{d}Q(n_{1},\ldots,n_{k},1)$
$\displaystyle\qquad\Leftrightarrow\exists
n_{1},\ldots,n_{k}\in\mathbb{N}\text{ s.t. }0=P(n_{1},\ldots,n_{k}).$

##  6 Conclusion

We have shown that the Matrix-Exponential Problem is undecidable in general,
but decidable when the matrices $A_{1},\ldots,A_{k}$ commute. This is
analogous to what was known for the discrete version of this problem, in which
the matrix exponentials $e^{At}$ are replaced by matrix powers $A^{n}$.

A natural variant of this problem is the following:

######  Definition 6.37 (Matrix-Exponential Semigroup Problem).

Given square matrices $A_{1},\ldots,A_{k}$ and $C$, all of the same dimension
and all with real algebraic entries, is $C$ a member of the matrix semigroup
generated by

$\displaystyle\\{\exp(A_{i}t_{i}):t_{i}\geq 0,i=1,\ldots,k\\}?$

When the matrices $A_{1},\ldots,A_{k}$ all commute, the above problem is
equivalent to the Matrix-Exponential Problem, and therefore decidable. In the
non-commutative case, the following result holds:

######  Theorem 6.38.

The Matrix-Exponential Semigroup Problem is undecidable.

A proof will appear in a future journal version of this paper. This can be
done by reduction from the Matrix-Exponential Problem, using a set of gadgets
to force a desired order in the multiplication of the matrix exponentials.

It would also be interesting to look at possibly decidable restrictions of the
MEP/MESP, for example the case where $k=2$ with a non-commuting pair of
matrices, which was shown to be decidable for the discrete analogue of this
problem in Bell et al. [2008]. Bounding the dimension of the ambient vector
space could also yield decidability, which has been partly accomplished in the
discrete case in Choffrut and Karhumäki [2005]. Finally, upper bounding the
complexity of our decision procedure for the commutative case would also be a
worthwhile task.

The author João Sousa-Pinto would like to thank Andrew Kaan Balin for a
productive discussion during the early stages of this work.

## References

  * Alur [2015] R. Alur.  _Principles of Cyber-Physical Systems_.  MIT Press, 2015.
  * Babai et al. [1996] L. Babai, R. Beals, J. Cai, G. Ivanyos, and E. M. Luks.  Multiplicative equations over commuting matrices.  In _Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 28-30 January 1996, Atlanta, Georgia._ , pages 498–507, 1996\.
  * Baker [1975] A. Baker.  _Transcendental Number Theory_.  Camb. Univ. Press, 1975.
  * Baker and Wüstholz [1993] A. Baker and G. Wüstholz.  Logarithmic forms and group varieties.  _Jour. Reine Angew. Math._ , 442, 1993.
  * Basu et al. [2006] S. Basu, R. Pollack, and M.-F. Roy.  _Algorithms in Real Algebraic Geometry_.  Springer, 2nd edition, 2006.
  * Bell et al. [2008] P. Bell, V. Halava, T. Harju, J. Karhumäki, and I. Potapov.  Matrix equations and Hilbert’s Tenth Problem.  _IJAC_ , 18(8):1231–1241, 2008.
  * Bell et al. [2010] P. C. Bell, J. Delvenne, R. M. Jungers, and V. D. Blondel.  The continuous Skolem-Pisot problem.  _Theor. Comput. Sci._ , 411(40-42):3625–3634, 2010.
  * Cai et al. [2000] J.-Y. Cai, R. J. Lipton, and Y. Zalcstein.  The complexity of the A B C problem.  _SIAM J. Comput._ , 29(6), 2000.
  * Cassels [1965] J. W. S. Cassels.  _An introduction to Diophantine approximation_.  Camb. Univ. Pr., 1965.
  * Chen et al. [2015] T. Chen, N. Yu, and T. Han.  Continuous-time orbit problems are decidable in polynomial-time.  _Inf. Process. Lett._ , 115(1):11–14, 2015.
  * Choffrut and Karhumäki [2005] C. Choffrut and J. Karhumäki.  Some decision problems on integer matrices.  _ITA_ , 39(1):125–131, 2005.
  * Cohen [1993] H. Cohen.  _A Course in Computational Algebraic Number Theory_.  Springer-Verlag, 1993.
  * Culver [1966] W. J. Culver.  On the existence and uniqueness of the real logarithm of a matrix.  _Proc. Amer. Math. Soc._ , 17:1146–1151, 1966.
  * Hainry [2008] E. Hainry.  Reachability in linear dynamical systems.  In _Logic and Theory of Algorithms, 4th Conference on Computability in Europe, CiE 2008, Athens, Greece, June 15-20, 2008, Proceedings_ , pages 241–250, 2008.
  * Halava [1997] V. Halava.  _Decidable and undecidable problems in matrix theory_.  1997\.
  * Hardy and Wright [1938] G. H. Hardy and E. M. Wright.  _An Introduction to the Theory of Numbers_.  Oxford University Press, 1938.
  * Helton [1968] B. W. Helton.  Logarithms of matrices.  _Proc. Amer. Math. Soc._ , 19:733–738, 1968.
  * Henzinger [1996] T. A. Henzinger.  The theory of hybrid automata.  In _Proceedings, 11th Annual IEEE Symposium on Logic in Computer Science, New Brunswick, New Jersey, USA, July 27-30, 1996_ , pages 278–292, 1996.
  * Henzinger et al. [1995] T. A. Henzinger, P. W. Kopke, A. Puri, and P. Varaiya.  What’s decidable about hybrid automata?  In _Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA_ , pages 373–382, 1995.
  * Kannan and Lipton [1986] R. Kannan and R. J. Lipton.  Polynomial-time algorithm for the orbit problem.  _J. ACM_ , 33(4):808–821, 1986.
  * Khachiyan and Porkolab [1997] L. Khachiyan and L. Porkolab.  Computing integral points in convex semi-algebraic sets.  In _FOCS_ , pages 162–171, 1997.
  * Masser [1988] D. W. Masser.  Linear relations on algebraic groups.  In _New Advances in Transcendence Theory_. Camb. Univ. Press, 1988\.
  * Matiyasevich [1993] Y. Matiyasevich.  _Hilbert’s 10th Problem_.  MIT Press, 1993.
  * Micciancio and Goldwasser [2002] D. Micciancio and S. Goldwasser.  _Complexity of Lattice Problems: a cryptographic perspective_ , volume 671 of _The Kluwer International Series in Engineering and Computer Science_.  Kluwer Academic Publishers, Boston, Massachusetts, 2002.
  * Newman [1967] M. Newman.  Two classical theorems on commuting matrices.  _Journal of research of the National Bureau of Standards - B. Mathematics and Mathematical Physics_ , 71 B(2, 3), 1967.
  * Pan [1996] V. Pan.  Optimal and nearly optimal algorithms for approximating polynomial zeros.  _Computers & Mathematics with Applications_, 31(12), 1996.
  * Paterson [1970] M. S. Paterson.  Undecidability in 3 by 3 matrices.  _J. of Math. and Physics_ , 1970.
  * Renegar [1992] J. Renegar.  On the computational complexity and geometry of the first-order theory of the reals.  _J. Symb. Comp._ , 1992.
  * Tarski [1951] A. Tarski.  _A Decision Method for Elementary Algebra and Geometry_.  University of California Press, 1951.
  * Wermuth [1989] E. Wermuth.  Two remarks on matrix exponentials.  _Linear Algebra and its Applications_ , 117:127–132, 1989\.


# Robust two-qubit trapped ions gates using spin-dependent squeezing

Yotam Shapira1 Sapir Cohen2 Nitzan Akerman1 Ady Stern2 Roee Ozeri1 1Department
of Physics of Complex Systems
2Department of Condensed Matter Physics
Weizmann Institute of Science, Rehovot 7610001, Israel

###### Abstract

Entangling gates are an essential component of quantum computers. However,
generating high-fidelity gates, in a scalable manner, remains a major
challenge in all quantum information processing platforms. Accordingly,
improving the fidelity and robustness of these gates has been a research focus
in recent years. In trapped ions quantum computers, entangling gates are
performed by driving the normal modes of motion of the ion chain, generating a
spin-dependent force. Even though there has been significant progress in
increasing the robustness and modularity of these gates, they are still
sensitive to noise in the intensity of the driving field. Here we supplement
the conventional spin-dependent displacement with spin-dependent squeezing,
which enables a gate that is robust to deviations in the amplitude of the
driving field. We solve the general Hamiltonian and engineer its spectrum
analytically. We also endow our gate with other, more conventional, robustness
properties, making it resilient to many practical sources of noise and
inaccuracies.

Two qubit entanglement gates are a crucial component of quantum computing, as
they are an essential part of a universal gate set. Moreover, fault-tolerant
quantum computing requires gates with fidelities above the fault-tolerance
threshold [1]. Generating high-fidelity two-qubit gates in a robust and
scalable manner remains an open challenge, and a research focus, in all
current quantum computing platforms [2, 3, 4].

Trapped ions based quantum computers are a leading quantum computation
platform, due to their high controlability, long coherence times and all-to-
all qubit connectivity [5, 6, 7]. Entanglement gates are typically generated
by driving the ions with electromagnetic fields, that creates phonon mediated
qubit-qubit interactions. Such gates have been demonstrated, with outstanding
fidelities [8, 9, 10, 11]. Moreover, in recent years there have been many
theoretical proposals and experimental demonstrations [12, 13, 14, 15, 16, 17,
18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36,
37, 38, 39, 40, 41, 42, 43] aimed at improving the fidelity, rate,
connectability and resilience of such gates. These schemes are largely based
on generating spin-dependent displacement forces on the ions which, depending
on realization, are linear or quadratic in the driving field. These result in
gates which are sensitive to the field amplitude and exhibit a degradation of
fidelity which is linear in field intensity noise. A widely used scheme for
which is the Mølmer-Sørensen (MS) gate [44, 45]. Driving field amplitude
deviations arise naturally in trapped ions systems and may come about due to
intensity noise in the drive source, as well as beam pointing noise and
polarization noise [46, 47].

Here we propose a gate scheme which is resilient to deviations in the driving
field’s amplitude. We combine the conventional spin-dependent displacement
with spin-dependent squeezing, by driving the first and second motional
sidebands of the ion crystal normal modes. We solve the resulting interaction
analytically and formulate constraints on the drive which generate a resilient
gate. Crucially, most constraints can be easily satisfied without any
numerical optimization. We combine other well-known robustness methods,
resulting in a two-qubit entanglement gate which is resilient to many
experimental parameters and is independent of the initial motional state,
within the Lamb-Dicke regime. Our gates may be implemented using conventional
waveform spectral shaping which are straightforward to implement and are
common to trapped ions systems. Our method is compatible to laser driven gates
as well as laser-free entangling gates [11].

Figure 1: Robust gate performance. Left: Fidelity of our robust gate (blue)
and the conventional MS gate (red), in presence of a deviation of the laser’s
Rabi frequency, $\delta\Omega$. Our gate shows a flat response, that scales as
$\delta\Omega^{4}$, yielding a high-fidelity operation even in the presence of
$10\%$ errors. The MS gate exhibits a quadratic response, and a fast
deterioration in fidelity. The inset shows the infidelity, $1-F$, in log
scale. Our method typically provides more than two orders of magnitude of
improvement throughout the $10\%$ error range. Right: Population dynamics of
the initial state $\ket{00}$, for an ideal case (solid) and an erroneous case,
with a $5\%$ Rabi frequency error (dashed). In both cases a high fidelity
operation (green) is generated at the gate time $t=T$, indicated by an equal
population of the $\ket{00}$ (blue) and $\ket{11}$ (purple) states, while the
$\ket{01}$ and $\ket{10}$ populations (orange) vanish, indicating robustness
to Rabi frequency deviations. The smoothness of the evolution around the gate
time is an indication of robustness to gate timing error as well, shown
explicitly in the text.

Figure 1 showcases our main results, with the fidelity (left) of our gate
(blue) and the conventional MS gate (red), in the presence of deviations in
the field’s Rabi frequency, $\delta\Omega$. As seen, our gate shows a robust
response which scales as $\delta\Omega^{4}$, and exhibits a high-fidelity
entangling operation even with $10\%$ Rabi frqeuency errors. This is
contrasted by the quadratic error of an MS gate. The population dynamics of
the initial state $\ket{00}$ are shown (right) for the ideal,
$\delta\Omega=0$, case (solid) and in presence of a deviation, with
$\delta\Omega/\Omega=0.05$ (dashed). While the two scenarios exhibit different
dynamics, at the gate time, $t=T$, they both converge and result in a high-
fidelity Bell state (green).

Utilizing spin-dependent squeezing for entangling gates has been suggested in
other contexts, such as in order to generate gates in the strong-coupling
regime [33], or in order to generate 3-body [48] and $n$-body [49] interaction
terms.

Below we present the Hamiltonian of interest, its solution, the formulation of
constraints, and their resolution using spectral shaping. Finally, we analyze
our gate’s performance and feasibility.

We start with the non-interacting Hamiltonian of two trapped ions, given by,

$H_{0}=\hbar\omega_{0}J_{z}+\hbar\nu a^{\dagger}a,$ (1)

with $\omega_{0}$ the single ion separation frequency of the relevant qubit
levels, $J_{z}=\left(\sigma^{z}_{1}+\sigma^{z}_{2}\right)/2$ the global
Pauli-$z$ operator such that $\sigma^{z}_{n}$ is the $z$-Pauli operator acting
on the $n$’th ion and $\nu$ the frequency of the center-of-mass normal mode of
motion of the ion-chain with its phonon creation operator, $a^{\dagger}$. All
other modes of motion are assumed to be decoupled from the ion’s evolution,
yet this assumption can be relaxed [27]. The Hamiltonian in Eq. (1) can
trivially be used in a larger ion-chain, by assuming only two ions are
illuminated [50, 41] and they equally participate in the coupled normal mode.

Without loss of generality and for concreteness we assume the ion qubit levels
are coupled by a direct optical transition. The ions are driven by a multi-
tone global laser field with a spectral content in the vicinity of the first
and second motional sidebands. This yields the interaction Hamiltonian,

$V_{I}=J_{x}\left[w_{1}\left(t\right)a^{\dagger}+iw_{2}\left(t\right)\left(a^{\dagger}\right)^{2}\right]+H.c,$
(2)

with $w_{n}\left(t\right)=\sum_{m}\rho_{n,m}e^{i\delta_{n,m}t}$. Here
$\rho_{n,m}$ and $\delta_{n,m}$ are amplitudes and frequencies determined
below. Equation (2) is obtained in a frame rotating with respect to $H_{0}$,
and by driving the ion chain with the global time-dependent drive,

$\begin{split}W\left(t\right)=&-\frac{4}{\eta}\sin\left(\omega_{0}t\right)\sum_{m}\rho_{1,m}\cos\left(\left(\nu-\delta_{1,m}\right)t\right)\\\
&-\frac{8}{\eta^{2}}\cos\left(\omega_{0}t\right)\sum_{m}\rho_{2,m}\sin\left(\left(2\nu-\delta_{2,m}\right)t\right),\end{split}$
(3)

with $\eta$ the Lamb-Dicke parameter, quantifying the coupling between qubit
and motional states [51]. The structure of Eq. (3) implies that the $w_{n}$’s
are proportional to $\Omega$, the driving field’s Rabi frequency. The
resulting interaction in Eq. (2) is valid in terms of a rotating wave
approximation (RWA) in $\Omega/\omega_{0}$ and a second order expansion in
$\eta$. Furthermore we make use of a RWA in $\Omega/\nu$ allowing us to omit
off-resonance carrier coupling terms and counter-rotating terms. Below we
incorporate methods that eliminate carrier coupling terms even further [18].
We note that counter-rotating terms still allow for an analytic solution [27],
but are omitted here in favor of a more concise presentation. Note that the
$w_{n}\left(t\right)$’s can be arbitrary complex time-dependent functions.

For the oscillator, the Hamiltonian in Eq. (2) generates both a spin-dependent
displacing term, modulated by $w_{1}$, and a spin-dependent squeezing term,
modulated by $w_{2}$. In the special case of $w_{2}=0$ the interaction $V_{I}$
reduces to the MS Hamiltonian and is exactly solvable. We show below that we
may still solve it for non-vanishing second sideband modulations.

There exists a known solution to general time-dependent quantum harmonic
oscillators [52]. However here the appearance of spin-dependence requires
special care. We move to a frame rotating with respect to a spin-dependent
squeezing by applying a unitary transformation
$S\left(J_{x}r\left(t\right)\right)=\exp\left[\frac{J_{x}r}{2}\left(a^{2}-\left(a^{\dagger}\right)^{2}\right)\right]$,
with the time-dependent parameter $r\left(t\right)$, for which we assume
$r\left(t=0\right)=0$. This transforms $V_{I}$ to
$V_{S}=S^{\dagger}V_{I}S-iS^{\dagger}\partial_{t}S$ (see full expression in
section I of the supplemental material). Choosing $w_{2}\in\mathbb{R}$, i.e.
the spectrum of $w_{2}$ is symmetric around the second sideband, the term in
$V_{S}$ that is proportional to $J_{x}a^{2}$ is,

$V_{S}^{\left(J_{x}a^{2}\right)}=-iJ_{x}a^{2}\left(w_{2}+\frac{1}{2}\partial_{t}r\right).$
(4)

To simplify $V_{S}$ we are interested in eliminating this term. This yields
the trivial differential constraint, $\partial_{t}r=-2w_{2}$, solved by

$r=-2\int_{0}^{t}dt^{\prime}w_{2}\left(t^{\prime}\right),$ (5)

With these choices, we are left with

$V_{S}=J_{x}a\left[w_{1}^{\ast}\cosh\left(J_{x}r\right)-w_{1}J_{x}\sinh\left(J_{x}r\right)\right]+H.c$
(6)

Since $V_{S}$ in Eq. (6) is linear in the mode operators it is analytically
solvable. Rotating back to the original frame, the resulting unitary evolution
operator due to $V_{I}$ is,

$U_{I}\left(t\right)=S\left(J_{x}r\left(t\right)\right)D\left(J_{x}\alpha\left(t\right)\right)e^{-i\left(J_{x}^{2}\left(\Phi_{2}\left(t\right)+\Phi_{4}\left(t\right)\right)+J_{x}\Phi_{3}\left(t\right)\right)}.$
(7)

On the spin side, the evolution in Eq. (7) is composed a global $J_{x}$
rotation with angle $\Phi_{3}$, and the desired qubit entangling operation,
$J_{x}^{2}$ with phase $\Phi_{2}+\Phi_{4}$ (Expressions for all $\Phi$’s are
given below). On the oscillator side, it is composed of spin-dependent
squeezing, $S$ and spin-dependent displacement, $D$, with
$D(\alpha)=\exp\left((\alpha a^{\dagger}-\alpha^{\ast}a\right)$.

Adopting the useful conventions,
$\left\\{f\right\\}=\int_{0}^{t}dt_{1}f\left(t_{1}\right)$ and
$\left\\{f\left\\{g\right\\}\right\\}=\int\limits_{0}^{t}dt_{1}\int\limits_{0}^{t_{1}}dt_{2}f\left(t_{1}\right)g\left(t_{2}\right)$,
introduced in [33], $\alpha$ and the $\Phi$’s are given by,

$\displaystyle\alpha=$
$\displaystyle\left\\{-i\left(w_{1}\cosh\left(r\right)-J_{x}w_{1}^{\ast}\sinh\left(r\right)\right)\right\\},$
(8) $\displaystyle\Phi_{2}=$
$\displaystyle\text{Im}\left[\left\\{w_{1}^{\ast}\cosh\left(r\right)\left\\{w_{1}\cosh\left(r\right)\right\\}\right\\}\right],$
(9)
$\displaystyle\begin{split}\Phi_{3}=&\text{Im}\left[\left\\{w_{1}\cosh\left(r\right)\left\\{w_{1}\sinh\left(r\right)\right\\}\right\\}\right]\\\
+&\text{Im}\left[\left\\{w_{1}^{\ast}\sinh\left(r\right)\left\\{w_{1}^{\ast}\cosh\left(r\right)\right\\}\right\\}\right],\end{split}$
(10) $\displaystyle\Phi_{4}=$
$\displaystyle\text{Im}\left[\left\\{w_{1}\sinh\left(r\right)\left\\{w_{1}^{\ast}\sinh\left(r\right)\right\\}\right\\}\right],$
(11)

Before analyzing the results in full we note that for a small $w_{2}$, the
leading order contributions to the entangling phase is,
$\Phi_{2}+\Phi_{4}=\text{Im}\left[\left\\{w_{1}^{\ast}\left\\{w_{1}\right\\}\right\\}+4\left\\{w_{1}\left\\{w_{2}\right\\}\left\\{w_{1}^{\ast}\left\\{w_{2}\right\\}\right\\}\right\\}\right]$,
such that $\Phi_{2}$ scales as $\Omega^{2}$ and $\Phi_{4}$ as $\Omega^{4}$.
This dependence is different from that of the MS scheme and its
generalizations, and provides the opportunity to mitigate deviations in
$\Omega$.

The form of Eq. (7) allows us to formulate constraints for the generation of
two-qubit entangling gates, which are robust to deviations in $\Omega$, and to
then choose the proper $w$’s that will satisfy these constraints. We first
require that at the gate time $t=T$ there will be no residual displacement or
squeezing, i.e., that $r(T)=\alpha(T)=0$, and no rotation of $J_{x}$, i.e.,
$\Phi_{3}(T)=0$. Explicitly, this requires,

$\displaystyle\left\\{w_{1}\cosh\left(r\right)\right\\}=0,$ (C1)
$\displaystyle\left\\{w_{1}^{\ast}\sinh\left(r\right)\right\\}=0,$ (C2)
$\displaystyle r\left(t=T\right)=\left\\{w_{2}\right\\}=0,$ (C3)
$\displaystyle\Phi_{3}\left(T\right)=0.$ (C4)

Crucially, (C1) and (C2) are required to render the gate operation independent
of the initial state of the motional mode, i.e. independent of temperature.

Next, without loss of generality we choose the entanglement phase to be
$\varphi=-\pi/2$, a value that rotates the computational basis to fully
entangled states,

$\Phi_{2}\left(T\right)+\Phi_{4}\left(T\right)=\varphi=-\pi/2.$ (12)

Then, robustness to errors in $\Omega$ is provided by,

$\partial_{\Omega}\left(\Phi_{2}\left(T\right)+\Phi_{4}\left(T\right)\right)=0.$
(13)

That is, we assume a small error, $\Omega\rightarrow\Omega+\delta\Omega$, and
eliminate the leading order contribution of this error to the entanglement
phase. This can be generalized to next order terms. In principle similar
constraints are required also for other quantities. However, we show below
that they are unnecessary by construction.

Our compiled list of six constraints does not uniquely define the drives
$w_{1},w_{2}$. We analyze these constraints in terms of frequencies. All the
constraints are expressed as integrals from $t=0$ to $t=T$. For these
integrals to vanish, the integrands must be composed of non-zero multiples of
the gate rate $\xi=2\pi/T$. The choice,

$\displaystyle w_{1}\left(t\right)=$
$\displaystyle\sum_{n}a_{2n+1}e^{i\xi\left(2n+1\right)t},$ (14) $\displaystyle
r\left(t\right)=$ $\displaystyle\sum_{n}s_{2n}\sin\left(2\xi nt\right),$ (15)

in which $w_{1}$ is made of odd harmonics of the gate rate and $r$ of a sine
series of even harmonics, guarantees that products of the form $w_{1}\cosh(r)$
and $w_{1}\sinh(r)$ will not have components at zero frequency, and will
therefore integrate to zero. This choice guarantees, then, compatibility with
the constraints (C1)–(C3). Furthermore the choice to expand $r$ in a sine
series (and not cosine) satisfies (C4) (see details in section II of the
supplemental material). These considerations are independent of $\Omega$ and
are therefore resilient to its possible deviations.

We are left with only two constraints, (12), which sets the entangling phase
and (13), which makes this phase robust to deviation in $\Omega$.
Appropriately, these can be satisfied with only two degrees of freedom. There
are infinitely many solutions to these constraints. The simplest uses only
$a_{3}$ and $s_{2}$ (setting all other $a$’s and $s$’s to zero). This minimal
gate scheme is presented in section III of the supplemental material.

We employ a more elaborate solution, making use of $a_{3}$, $a_{5}$, $a_{7}$,
$s_{2}$ and $s_{4}$, in order to combine this new result with previously
demonstrated robustness properties: mitigation of unwanted off-resonant
carrier and sideband couplings, robustness to deviations in the gate time,
resilience to phonon mode heating and robustness to motional mode errors [14,
18, 23]. These all correspond to constraints which are linear in the $a_{n}$’s
and $s_{n}$’s and are therefore straightforward to implement (see section IV
of the supplemental material for further details). Yielding the drive,

$\displaystyle w_{1}\left(t\right)=$ $\displaystyle\frac{a}{3}\left(3e^{3i\xi
t}-10e^{5i\xi t}+7e^{7i\xi t}\right),$ (16) $\displaystyle r\left(t\right)=$
$\displaystyle s\left(\sin\left(2\xi t\right)-\frac{1}{2}\sin\left(4\xi
t\right)\right).$ (17)

Figure 2: Spectrum and resulting modulation used to generate our robust gate.
Top: Spectrum of the first (blue) and second (green) sidebands. The amplitude
is given in units of $\xi/\eta^{n}$, with $n$ the sideband order. Bottom:
Resulting time-domain modulation of the first (blue) and second (green)
sidebands. Both modulations vanish continuously at $t=0$ and $t=T$ thus
mitigating off-resonance coupling to unwanted transitions.

Thus we still have only two undetermined degrees of freedom, $a$ and $s$, in
order to satisfy , (12) and (13). We progress by Taylor expanding the
hyperbolic functions in these constraints to $6$’th order, yielding polynomial
equations for $a$ and $s$, which are solved analytically. We then optimize
these solutions numerically by directly evaluating (12) and (13) with a
straightforward gradient descent. This yields, $a=0.3608\cdot\xi$ and
$s=0.7820$, which constitutes a $3\%$ correction to the analytical solution
(see further information in section V of the supplemental material).

The Rabi frequency required by our scheme is
$\Omega_{\text{robust}}\approx\left(3/\eta+6/\eta^{2}\right)\xi$. It is more
demanding than the MS Rabi frequency, $\Omega_{\text{MS}}=\frac{\xi}{2\eta}$,
showing that robustness is afforded at the price of additional drive power. In
the case of two ions, with COM mode $\eta=0.144$, a gate time of $50\text{
}\mu\text{s}$ requires total laser power of $1.6\text{ mW}$ in the usual MS
gate and a power of $150\text{ mW}$ for our fully robust gate (see further
details in section VI of the supplemental material). Nevertheless in most
implementations the limit on two-qubit entangling gates is fidelity and not
driving power. More sophisticated solutions, using additional driving tones
can divert field amplitudes from $w_{2}$ to $w_{1}$, which reduces the
required power but increases the drive complexity. We note that the second
sideband drive is significant and cannot be naively treated perturbatively
[33].

The resulting spectrum is presented in Fig. 2 (top) showing the spectral
components modulating the first (blue) and second (green) sidebands. The
amplitude of the spectrum is normalized by the Lamb-Dicke parameter to the
power of the sideband order, i.e. the second sideband modulation is $\eta$
times stronger than the first sideband modulation. The corresponding time-
domain modulation of the sidebands due to our drive is shown in Fig. 2
(bottom). We note that both modulations continuously vanish at the start and
the end of the gate, which acts to reduce off-resonance coupling to unwanted
transitions.

The phase space trajectories generated by our scheme are deduced by the
squeezing, $S\left(J_{x}r\right)$, and displacement,
$D\left(J_{x}\alpha\right)$ operators, in Eq. (7). We note that due to the
appearance of $J_{x}$ in $D$ and $S$, the states $\ket{++}$ and $\ket{--}$
follow different phase space trajectories. This also occurs in the MS gate,
however here we also have $J_{x}$ operators in $\alpha$, hence the
trajectories are not simply reflected about the origin, as in the MS case. We
calculate the phase space trajectories by using the identity,
$S\left(r\right)D\left(\alpha\right)=D\left(\gamma\right)S\left(r\right)$,
with $\gamma=\alpha\cosh\left(r\right)-\alpha^{\ast}\sinh\left(r\right)$, such
that the state is first squeezed by $r$ and then displaced by $\gamma$. We
note that the MS phase-space intuition for spin-dependent displacement gate is
not valid here, i.e. the entangling phase is not proportional to the area
enclosed by the phase space trajectory.

Figure 3:  Motion in phase space Left: Phase space displacement of the
$\ket{++}$ (solid) and $\ket{--}$ (dashed) states. The two trajectories are
related by a reflection around the $x$ axis and time reversal. Right: standard
deviation of position, $\Delta x=\exp\left(r\right)/2$ (solid) and momentum,
$\Delta p=\exp\left(-r\right)/2$ (dashed) for the $\ket{++}$, revealing
several oscillations of squeezing and anti-squeezing in both quadratures.
These are the same for momentum (solid) and position (dashed) in the
$\ket{--}$ state respectively. Since the squeezing parameter $r$ is real then
together with displacement (left) the motion in phase space is completely
defined.

The phase space displacement of $\ket{++}$ is presented in Fig. 3 (left,
solid). The same evolution is shown for $\ket{--}$ (dashed). The trajectories
are reflected around the $x$ axis and time reversed. Indeed, using
$r\left(T-t\right)=r\left(t\right)$ and
$w_{1}\left(T-t\right)=w_{1}^{\ast}\left(t\right)$, this is readily confirmed.
Squeezing by $r$ changes the expectation value error of position and momentum,
$\Delta x$ and $\Delta p$, to $e^{r}/2$ and $e^{-r}/2$ respectively. Indeed,
the figure also shows the standard deviations (right) of $x$ (solid), and $p$
(dashed) for the $\ket{++}$ state, exhibiting non-trivial dynamics. Since $r$
is real the displacement and standard deviations along both axes completely
define the phase-space motion.

The form of the evolution operator in Eq. (7), together with known phase-space
identities [53], allow us to calculate the gate fidelity. Specifically, we
calculate the overlap of the state generated by our gate with the ideal case,
assuming the initial state is $\ket{00}$, at the motional ground state (see
details in section VII of the supplemental material). This is used to
calculate the gate fidelity in presence of Rabi frequency deviations,
$\delta\Omega$ shown in Fig. 1 (left).

Figure 4: Additional robustness properties of our gate (blue) compared to the
MS gate (red). The insets show the same data recast as infidelity in log
scale. Left: Fidelity in presence of gate timing errors, $\delta T/T$. Our
gate shows a fourth order, wide response enabling high-fidelity operation even
in presence of $5\%$ errors. Right: Fidelity in presence of motional mode
frequency errors, $\delta\nu/\xi$. Similarly, our gate exhibits a wide high
fidelity region. As expected, the fidelity is not symmetric around the peak.

Moreover, as previously demonstrated, the form of the drive in Eq. (17)
ensures that our gate is robust to additional errors and noise. Indeed, Fig. 4
shows our gate fidelity in the presence of gate time deviations, $\delta T$
(left), and motional mode frequency errors, $\delta\nu$ (right). For both of
these errors our gate exhibits high fidelity (blue) which scales favorably
compared to the MS gate (red).

In conclusion, we have used spin-dependent squeezing in order to propose a
two-qubit entangling gate for trapped ions qubits, which is resilient to
deviations in the driving field intensity. We have also supplemented our gate
with more conventional, previously demonstrated, robustness properties, making
it also robust to gate timing errors, motional mode heating, secular frequency
drifts, as well as mitigation of coupling to unwanted transitions such as the
carrier transition and off resonance sidebands. We do so by generating
constraints, which can then be satisfied, almost entirely, with spectral
consideration in an analytic fashion. Our new gate can be readily incorporated
in the trapped ion quantum toolbox.

We thank David Schwerdt for helpful discussions. This work was supported by
the Israeli Science Foundation, the Israeli Ministry of Science Technology and
Space, the Minerva Stiftung, the European Union’s Horizon 2020 research and
innovation programme (Grant Agreement LEGOTOP No. 788715), the DFG
(CRC/Transregio 183, EI 519/7-1), ISF Quantum Science and Technology
(2074/19).

## References

  * Aharonov and Ben-Or [2008] D. Aharonov and M. Ben-Or, Fault-tolerant quantum computation with constant error rate, SIAM Journal on Computing 38, 1207 (2008), https://doi.org/10.1137/S0097539799359385 .
  * Bruzewicz  _et al._ [2019] C. D. Bruzewicz, J. Chiaverini, R. McConnell, and J. M. Sage, Trapped-ion quantum computing: Progress and challenges, Applied Physics Reviews 6, 021314 (2019), https://doi.org/10.1063/1.5088164 .
  * Kjaergaard  _et al._ [2020] M. Kjaergaard, M. E. Schwartz, J. Braumüller, P. Krantz, J. I.-J. Wang, S. Gustavsson, and W. D. Oliver, Superconducting qubits: Current state of play, Annual Review of Condensed Matter Physics 11, 369 (2020), https://doi.org/10.1146/annurev-conmatphys-031119-050605 .
  * Alexeev  _et al._ [2021] Y. Alexeev, D. Bacon, K. R. Brown, R. Calderbank, L. D. Carr, F. T. Chong, B. DeMarco, D. Englund, E. Farhi, B. Fefferman, A. V. Gorshkov, A. Houck, J. Kim, S. Kimmel, M. Lange, S. Lloyd, M. D. Lukin, D. Maslov, P. Maunz, C. Monroe, J. Preskill, M. Roetteler, M. J. Savage, and J. Thompson, Quantum computer systems for scientific discovery, PRX Quantum 2, 017001 (2021).
  * Postler  _et al._ [2021] L. Postler, S. Heußen, I. Pogorelov, M. Rispler, T. Feldker, M. Meth, C. D. Marciniak, R. Stricker, M. Ringbauer, R. Blatt, _et al._ , Demonstration of fault-tolerant universal quantum gate operations, arXiv preprint arXiv:2111.12654 (2021).
  * Pino  _et al._ [2021] J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. Allman, C. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, _et al._ , Demonstration of the trapped-ion quantum ccd computer architecture, Nature 592, 209 (2021).
  * Egan  _et al._ [2021] L. Egan, D. M. Debroy, C. Noel, A. Risinger, D. Zhu, D. Biswas, M. Newman, M. Li, K. R. Brown, M. Cetina, _et al._ , Fault-tolerant control of an error-corrected qubit, Nature 598, 281 (2021).
  * Ballance  _et al._ [2016] C. J. Ballance, T. P. Harty, N. M. Linke, M. A. Sepiol, and D. M. Lucas, High-fidelity quantum logic gates using trapped-ion hyperfine qubits, Phys. Rev. Lett. 117, 060504 (2016).
  * Gaebler  _et al._ [2016] J. P. Gaebler, T. R. Tan, Y. Lin, Y. Wan, R. Bowler, A. C. Keith, S. Glancy, K. Coakley, E. Knill, D. Leibfried, and D. J. Wineland, High-fidelity universal gate set for ${{}^{9}\mathrm{Be}}^{+}$ ion qubits, Phys. Rev. Lett. 117, 060505 (2016).
  * Clark  _et al._ [2021] C. R. Clark, H. N. Tinkey, B. C. Sawyer, A. M. Meier, K. A. Burkhardt, C. M. Seck, C. M. Shappert, N. D. Guise, C. E. Volin, S. D. Fallek, H. T. Hayden, W. G. Rellergert, and K. R. Brown, High-fidelity bell-state preparation with ${}^{40}{\mathrm{ca}}^{+}$ optical qubits, Phys. Rev. Lett. 127, 130505 (2021).
  * Srinivas  _et al._ [2021] R. Srinivas, S. C. Burd, H. M. Knaack, R. T. Sutherland, A. Kwiatkowski, S. Glancy, E. Knill, D. J. Wineland, D. Leibfried, A. C. Wilson, D. T. C. Allcock, and D. H. Slichter, High-fidelity laser-free universal control of trapped ion qubits, Nature 597, 209 (2021).
  * Roos [2008] C. F. Roos, Ion trap quantum gates with amplitude-modulated laser beams, New Journal of Physics 10, 013002 (2008).
  * Green and Biercuk [2015] T. J. Green and M. J. Biercuk, Phase-modulated decoupling and error suppression in qubit-oscillator systems, Phys. Rev. Lett. 114, 120502 (2015).
  * Haddadfarshi and Mintert [2016] F. Haddadfarshi and F. Mintert, High fidelity quantum gates of trapped ions in the presence of motional heating, New Journal of Physics 18, 123007 (2016).
  * Manovitz  _et al._ [2017] T. Manovitz, A. Rotem, R. Shaniv, I. Cohen, Y. Shapira, N. Akerman, A. Retzker, and R. Ozeri, Fast dynamical decoupling of the mølmer-sørensen entangling gate, Phys. Rev. Lett. 119, 220505 (2017).
  * Palmero  _et al._ [2017] M. Palmero, S. Martínez-Garaot, D. Leibfried, D. J. Wineland, and J. G. Muga, Fast phase gates with trapped ions, Phys. Rev. A 95, 022328 (2017).
  * Wong-Campos  _et al._ [2017] J. D. Wong-Campos, S. A. Moses, K. G. Johnson, and C. Monroe, Demonstration of two-atom entanglement with ultrafast optical pulses, Phys. Rev. Lett. 119, 230501 (2017).
  * Shapira  _et al._ [2018] Y. Shapira, R. Shaniv, T. Manovitz, N. Akerman, and R. Ozeri, Robust entanglement gates for trapped-ion qubits, Phys. Rev. Lett. 121, 180502 (2018).
  * Zarantonello  _et al._ [2019] G. Zarantonello, H. Hahn, J. Morgner, M. Schulte, A. Bautista-Salvador, R. F. Werner, K. Hammerer, and C. Ospelkaus, Robust and resource-efficient microwave near-field entangling ${}^{9}{\mathrm{be}}^{+}$ gate, Phys. Rev. Lett. 123, 260503 (2019).
  * Leung  _et al._ [2018] P. H. Leung, K. A. Landsman, C. Figgatt, N. M. Linke, C. Monroe, and K. R. Brown, Robust 2-qubit gates in a linear ion crystal using a frequency-modulated driving force, Phys. Rev. Lett. 120, 020501 (2018).
  * Leung and Brown [2018] P. H. Leung and K. R. Brown, Entangling an arbitrary pair of qubits in a long ion crystal, Phys. Rev. A 98, 032318 (2018).
  * Schäfer  _et al._ [2018] V. M. Schäfer, C. J. Ballance, K. Thirumalai, L. J. Stephenson, T. G. Ballance, A. M. Steane, and D. M. Lucas, Fast quantum logic gates with trapped-ion qubits, Nature 555, 75 (2018).
  * Webb  _et al._ [2018] A. E. Webb, S. C. Webster, S. Collingbourne, D. Bretaud, A. M. Lawrence, S. Weidt, F. Mintert, and W. K. Hensinger, Resilient entangling gates for trapped ions, Phys. Rev. Lett. 121, 180501 (2018).
  * Sutherland  _et al._ [2019] R. T. Sutherland, R. Srinivas, S. C. Burd, D. Leibfried, A. C. Wilson, D. J. Wineland, D. T. C. Allcock, D. H. Slichter, and S. B. Libby, Versatile laser-free trapped-ion entangling gates, New Journal of Physics 21, 033033 (2019).
  * Figgatt  _et al._ [2019] C. Figgatt, A. Ostrander, N. M. Linke, K. A. Landsman, D. Zhu, D. Maslov, and C. Monroe, Parallel entangling operations on a universal ion-trap quantum computer, Nature 572, 368 (2019).
  * Lu  _et al._ [2019] Y. Lu, S. Zhang, K. Zhang, W. Chen, Y. Shen, J. Zhang, J.-N. Zhang, and K. Kim, Global entangling gates on arbitrary ion qubits, Nature 572, 363 (2019).
  * Shapira  _et al._ [2020] Y. Shapira, R. Shaniv, T. Manovitz, N. Akerman, L. Peleg, L. Gazit, R. Ozeri, and A. Stern, Theory of robust multiqubit nonadiabatic gates for trapped ions, Phys. Rev. A 101, 032330 (2020).
  * Sutherland  _et al._ [2020] R. T. Sutherland, R. Srinivas, S. C. Burd, H. M. Knaack, A. C. Wilson, D. J. Wineland, D. Leibfried, D. T. C. Allcock, D. H. Slichter, and S. B. Libby, Laser-free trapped-ion entangling gates with simultaneous insensitivity to qubit and motional decoherence, Phys. Rev. A 101, 042334 (2020).
  * Lishman and Mintert [2020] J. Lishman and F. Mintert, Trapped-ion entangling gates robust against qubit frequency errors, Phys. Rev. Research 2, 033117 (2020).
  * Wang  _et al._ [2020a] Y. Wang, J.-L. Wu, J.-X. Han, Y.-Y. Jiang, Y. Xia, and J. Song, Noise-resistant phase gates with amplitude modulation, Phys. Rev. A 102, 032601 (2020a).
  * Milne  _et al._ [2020] A. R. Milne, C. L. Edmunds, C. Hempel, F. Roy, S. Mavadia, and M. J. Biercuk, Phase-modulated entangling gates robust to static and time-varying errors, Phys. Rev. Applied 13, 024022 (2020).
  * Bentley  _et al._ [2020] C. D. B. Bentley, H. Ball, M. J. Biercuk, A. R. R. Carvalho, M. R. Hush, and H. J. Slatyer, Numeric optimization for configurable, parallel, error-robust entangling gates in large ion registers, Advanced Quantum Technologies 3, 2000044 (2020), https://onlinelibrary.wiley.com/doi/pdf/10.1002/qute.202000044 .
  * Sameti  _et al._ [2021] M. Sameti, J. Lishman, and F. Mintert, Strong-coupling quantum logic of trapped ions, Phys. Rev. A 103, 052603 (2021).
  * Duwe  _et al._ [2021] M. Duwe, G. Zarantonello, N. Pulido-Mateo, H. Mendpara, L. Krinner, A. Bautista-Salvador, N. V. Vitanov, K. Hammerer, R. F. Werner, and C. Ospelkaus, Numerical optimization of amplitude-modulated pulses in microwave-driven entanglement generation (2021).
  * Kang  _et al._ [2021] M. Kang, Q. Liang, B. Zhang, S. Huang, Y. Wang, C. Fang, J. Kim, and K. R. Brown, Batch optimization of frequency-modulated pulses for robust two-qubit gates in ion chains, Phys. Rev. Applied 16, 024039 (2021).
  * Blümel  _et al._ [2021] R. Blümel, N. Grzesiak, N. Pisenti, K. Wright, and Y. Nam, Power-optimal, stabilized entangling gate between trapped-ion qubits, npj Quantum Information 7, 147 (2021).
  * Blümel  _et al._ [2021] R. Blümel, N. Grzesiak, N. H. Nguyen, A. M. Green, M. Li, A. Maksymov, N. M. Linke, and Y. Nam, Efficient stabilized two-qubit gates on a trapped-ion quantum computer, Phys. Rev. Lett. 126, 220503 (2021).
  * Dong  _et al._ [2021] L. Dong, I. n. Arrazola, X. Chen, and J. Casanova, Phase-adaptive dynamical decoupling methods for robust spin-spin dynamics in trapped ions, Phys. Rev. Applied 15, 034055 (2021).
  * Valahu  _et al._ [2021] C. H. Valahu, A. M. Lawrence, S. Weidt, and W. K. Hensinger, Robust entanglement by continuous dynamical decoupling of the j-coupling interaction, New Journal of Physics 23, 113012 (2021).
  * Wang  _et al._ [2022] K. Wang, J.-F. Yu, P. Wang, C. Luan, J.-N. Zhang, and K. Kim, Ultra-fast multi-qubit global-entangling gates without individual addressing of trapped ions (2022).
  * Manovitz  _et al._ [2022] T. Manovitz, Y. Shapira, L. Gazit, N. Akerman, and R. Ozeri, Trapped-ion quantum computer with robust entangling gates and quantum coherent feedback, PRX Quantum 3, 010347 (2022).
  * Fang  _et al._ [2022] C. Fang, Y. Wang, S. Huang, K. R. Brown, and J. Kim, Crosstalk suppression in individually addressed two-qubit gates in a trapped-ion quantum computer (2022).
  * Valahu  _et al._ [2022] C. Valahu, I. Apostolatos, S. Weidt, and W. Hensinger, Quantum control methods for robust entanglement of trapped ions (2022).
  * Sørensen and Mølmer [1999] A. Sørensen and K. Mølmer, Quantum computation with ions in thermal motion, Phys. Rev. Lett. 82, 1971 (1999).
  * Sørensen and Mølmer [2000] A. Sørensen and K. Mølmer, Entanglement and quantum computation with ions in thermal motion, Phys. Rev. A 62, 022311 (2000).
  * Brown  _et al._ [2016] K. R. Brown, J. Kim, and C. Monroe, Co-designing a scalable quantum computer with trapped atomic ions, npj Quantum Information 2, 16034 (2016).
  * Mount  _et al._ [2016] E. Mount, D. Gaultney, G. Vrijsen, M. Adams, S.-Y. Baek, K. Hudek, L. Isabella, S. Crain, A. van Rynbach, P. Maunz, and J. Kim, Scalable digital hardware for a trapped ion quantum computer, Quantum Information Processing 15, 5281 (2016).
  * Andrade  _et al._ [2022] B. Andrade, Z. Davoudi, T. Graß, M. Hafezi, G. Pagano, and A. Seif, Engineering an effective three-spin hamiltonian in trapped-ion systems for applications in quantum simulation, Quantum Science and Technology 7, 034001 (2022).
  * Katz  _et al._ [2022] O. Katz, M. Cetina, and M. Christopher, N-body interactions between trapped ion qubits via spin-dependent squeezing, arXiv preprint arXiv:2202.04230 (2022).
  * Wang  _et al._ [2020b] Y. Wang, S. Crain, C. Fang, B. Zhang, S. Huang, Q. Liang, P. H. Leung, K. R. Brown, and J. Kim, High-fidelity two-qubit gates using a microelectromechanical-system-based beam steering system for individual qubit addressing, Phys. Rev. Lett. 125, 150505 (2020b).
  * Wineland  _et al._ [1998] D. J. Wineland, C. Monroe, W. M. Itano, D. Leibfried, B. E. King, and D. M. Meekhof, Experimental issues in coherent quantum-state manipulation of trapped atomic ions, Journal of research of the National Institute of Standards and Technology 103, 259 (1998).
  * Harari  _et al._ [2011] G. Harari, Y. Ben-Aryeh, and A. Mann, Propagator for the general time-dependent harmonic oscillator with application to an ion trap, Phys. Rev. A 84, 062104 (2011).
  * Gerry and Knight [2004] C. Gerry and P. Knight,  _Introductory Quantum Optics_ (Cambridge University Press, 2004).