[1]Fachbereich Physik and Dahlem Center for Complex Quantum Systems, Freie
Universität Berlin, Arnimallee 14, 14195 Berlin, Germany

# Graph test of controllability in qubit arrays: A systematic way to determine
the minimum number of external controls

Fernando Gago-Encinas  Monika Leibscher  Christiane P. Koch

###### Abstract

The ability to implement any desired quantum logic gate on a quantum
processing unit is equivalent to evolution-operator controllability of the
qubits. Conversely, controllability analysis can be used to minimize the
resources, i.e., the number of external controls and qubit-qubit couplings,
required for universal quantum computing. Standard controllability analysis,
consisting in the construction of the dynamical Lie algebra, is, however,
impractical already for a comparatively small number of qubits. Here, we show
how to leverage an alternative approach, based on a graph representation of
the Hamiltonian, to determine controllability of arrays of coupled qubits. We
provide a complete computational framework and exemplify it for arrays of five
qubits, inspired by the ibmq_quito architecture. We find that the number of
controls can be reduced from five to one for complex qubit-qubit couplings and
to two for standard qubit-qubit couplings.

##  1 Introduction

Universal quantum computing requires evolution-operator controllability on the
quantum processing units in order to perform every possible quantum logic
gate. One way to achieve this, pursued for example in most superconducting
qubit architectures, is to couple each qubit to at least one other qubit and
drive all qubits locally. This approach becomes impractical for larger qubit
arrays due to increasing requirements on physical space for control lines and
on calibration time for control pulses. One may wonder whether a number of
local drives smaller than the number of qubits would already be sufficient. If
so, this would suggest the possibility of more resource-efficient
architectures than currently in use.

Here, we show that controllability analysis provides a systematic approach to
determine the minimum number of local controls for which any desired quantum
logic gate can be implemented. We find that indeed the number of local
controls can be smaller than the number of qubits. The minimum number of local
controls, for a given size of the qubit array, depends on the type of qubit-
qubit couplings. To facilitate analysis of medium-sized qubit arrays, we
leverage a graph theory-based approach to controllability analysis and
investigate five-qubit arrays starting from the ibmq_quito architecture.

Controllability analysis answers the question, in a yes-no fashion, which
states can be reached by time evolution from a set of initial states [1, 2].
The standard approach consists in determining the rank of the dynamical Lie
algebra of the system and comparing it to the dimension of the algebra that
generates the unitary group of all time evolutions [3]. This approach has been
extensively used to prove controllability for finite-dimensional systems with
sufficiently small Hilbert space dimension [4, 5, 6] and can also be employed
in subspaces of infinite-dimensional systems, when combined with Galerkin-type
approximations [7, 8, 9, 10]. The focus of these studies has been on single
quantum systems. For multi-partite systems, where the Hilbert space dimension
scales exponentially in the number of subsystems, evaluating the Lie rank
condition quickly becomes challenging. It has thus mainly been used to
identify controllable subspaces in systems which as a whole are not
controllable [11, 12, 13, 14]. Positive controllability results for qubit
arrays, as needed for universal quantum computing, require an alternative
approach.

The exponential scaling of Hilbert space dimension with the number of qubits
is evidently inherent to gate-based quantum computing and represents a
fundamental obstacle to controllability analysis that cannot be overcome with
classical computers. But even for qubit arrays which are classically
simulable, use of the Lie rank condition is hampered by numerical
instabilities which are common when constructing orthogonal bases in large
operator spaces. This latter obstacle can be avoided by resorting to graph
theory-based methods for controllability analysis [15, 9, 16] which have
successfully been applied to quantum walks [17], quantum networks [18], and
quantum rotors [10, 19]. The latter are characterized by a highly degenerate
spectrum which results in multiple resonant transitions, i.e., transitions
with the same resonance frequency that are driven by the same external
control. Controllability can then not simply be read off from the connectivity
of the graph. This problem is also present for arrays of locally driven
coupled qubits but the different spectral structure requires different
graphical methods to prove controllability, as we will discuss below.

The manuscript is organized as follows. The basic concepts of controllability
analysis are briefly reviewed in section 2. The methodology we suggest to use
for controllability analysis of coupled qubit arrays is presented in section 3
with subsection 3.1 explaining how to deal with resonant transitions,
subsection 3.2 presenting the actual graph test in the form of a flow chart
and three algorithms and subsection 3.3 illustrating the use of the algorithms
on simple two-qubit examples. Our results on five-qubit arrays inspired by the
ibmq_quito architecture are presented in section 4, and section 5 concludes.

##  2 Controllability analysis

We study quantum systems that couple linearly to controls, such that their
Hamiltonian can be expressed as

$\hat{H}(t)=\hat{H}(t;u_{1},...u_{m})=\hat{H}_{0}+\sum_{j=1}^{m}u_{j}(t)\hat{H}_{j}\,,$
(1)

where the controls $u_{j}(t)$ are real-valued functions and $\hat{H}_{j}$ are
the control operators. A state that evolves under Equation 1, is given by
$\ket{\psi(t)}=\hat{U}(t;u_{1},...u_{m})\ket{\psi(0)}$. We consider coherent
evolutions because it is the relevant foundation for gate-based quantum
information.

For qubit arrays, the drift $\hat{H}_{0}$ is split into
$\hat{H}_{0}=\sum_{l=1}^{N_{Q}}\hat{H}_{0,l}+\hat{H}_{c}$, representing the
independent local Hamiltonians $\hat{H}_{0,l}$ of the $N_{Q}$ free qubits and
the time-independent couplings $\hat{H}_{c}$ between them. Typically, local
controls $\hat{H}_{j}$ act on single qubits, for example in the form of laser
pulses in ion arrays [20] or varying microwave fields for certain
superconducting qubits [21]. Regardless of the physical implementation of the
qubits, we would like to answer the question whether a system with a set of
controls is capable of performing any unitary operation.

The answer can be found by analysing the controllability; in particular, the
evolution-operator controllability of the system [3]. It is defined as
follows:

###### Definition 1

A system with controls as defined in Equation 1 and Hilbert space dimension
$n$ is evolution-operator controllable iff for every unitary evolution
$\hat{U}_{target}\in U(n)$ there exist a final time $T\geq 0$, a phase angle
$\theta\in[0,2\pi)$ and a set of controls $\\{u_{j}\\}_{j=1}^{m}$ such that
$\ket{\psi(T)}=e^{i\theta}\hat{U}_{target}\ket{\psi(0)}=\hat{U}(t;u_{1},...u_{m})\ket{\psi(0)}$
for any initial state $\ket{\psi(0)}$ in the system’s Hilbert space.

Note that $e^{i\theta}$ is a global phase that does not depend on the choice
of the initial state. In other words, a system is evolution-operator
controllable if and only if we can always choose controls and a final time to
carry out any unitary operation, up to a global phase. For simplicity, we
refer to this property as ’controllable’.

A widely used method for studying the controllability of a quantum system is
to analyze the dynamical Lie algebra [3, 17, 22]. It is generated by the drift
and the $m$ control operators of the system,
$\mathcal{L}:=Lie(i\hat{H}_{0},i\hat{H}_{1},...,i\hat{H}_{m})$, i.e., it
contains the skew-Hermitian operators
$i\hat{H}_{0},i\hat{H}_{1},...,i\hat{H}_{m}$, and their (nested) commutators.
A system with Hilbert space dimension $n$ is controllable if the dimension of
the dynamical Lie algebra is $n^{2}$ or $n^{2}-1$. In other words, it is
controllable if the dimension of the Lie algebra matches either that of
$\mathfrak{su}(n)$ (which generates the special unitary group $SU(n)$) or
$\mathfrak{u}(n)$ (which generates the unitary group $U(n)$). This is
sometimes referred to as the Lie algebra rank condition [3]. The main
difference between generating $U(n)$ or $SU(n)$ is that the former allows the
system to perform any unitary evolution including all global phases.
Conversely, the latter encompasses all unitary evolutions up to a non-
controllable global phase.

Alternatively to constructing the dynamical Lie algebra, a graph test can be
used to analyze controllability [16, 10, 23]. The graph encodes the
information of the Hamiltonian.

###### Definition 2

Given a quantum system evolving under Equation 1, we can construct an
undirected graph according to the rules:

  1. 1.

For every eigenstate $\ket{e_{k}}$ of $\hat{H}_{0}$, add a vertex to the graph
with a corresponding label.

  2. 2.

For every control $\hat{H}_{j}$ and every nonzero element
$\bra{e_{i}}\hat{H}_{j}\ket{e_{k}}$, add an edge between the vertices labelled
$\ket{e_{i}}$ and $\ket{e_{k}}$. Additionally, add a label to every edge
stating which control drives that transition.

We call this the graph of a quantum system111Note that given two vertices
there can be more than one edge between the two of them (belonging to
different controls). Technically, this makes the graph of a system a
multigraph..

Since the nodes of the graph are labelled by the eigenstates $\ket{e_{k}}$, we
use these labels also to name the edges that represent the transitions
generated by the controls. The edge joining the vertices $\ket{e_{a}}$ and
$\ket{e_{b}}$ is denoted by $(a,b)$. For Hermitian controls, the transitions
will necessarily happen in both directions, implying an undirected graph. This
means, in particular, that both $(a,b)$ and $(b,a)$ refer to the same edge.

An important aspect of the graph are the energy gaps related to the graph
edges $\Delta E_{a,b}:=\left|E_{\ket{e_{a}}}-E_{\ket{e_{b}}}\right|$. If two
transitions have the same energy gap $\Delta E_{a,b}$, they are called
’resonant’. Resonant transitions may pose a challenge to controllability
since, depending on the local controls, it may be impossible to address them
independently.

###### Definition 3

Let $\mathcal{G}$ be the graph of a system. If two edges $(a,b),(c,d)\in
E(\mathcal{G})$ belong to the same control $\hat{H}_{j}$ and have degenerate
energy gaps $\Delta E_{a,b}=\Delta E_{c,d}$, then the two transitions
represented by the edges are coupled to one another. Alternatively, if an edge
$(a,b)\in E(\mathcal{G})$ is not coupled to any other transition belonging to
its own control $\hat{H}_{j}$, the transition is said to be decoupled.

This leads to the following theorem whose proof can be found in Ref. [7]:

###### Theorem 1

Let $\mathcal{S}$ be a quantum system following Equation 1 and let
$\mathcal{G}$ be its associated graph. The system $\mathcal{S}$ is
controllable if there exists a connected subgraph of $\mathcal{G}$ that
contains all vertices of $\mathcal{G}$ and only decoupled transitions.

An undirected graph is said to be connected if for every two vertices there
exists a chain of adjacent edges that creates a path between the two selected
vertices. A subgraph of a graph $\mathcal{G}$ is a graph defined by a subset
of the vertices $V(\mathcal{G})$ and a subset of the edges $E(\mathcal{G})$
that only link vertices in the subset. This means that a subgraph is a graph
that we obtain by removing any number of the edges and vertices from the
original graph.

The main benefit of the graph test in Theorem 1 is that it allows us to avoid
calculating the full dynamical Lie algebra. The graph of a quantum system with
Hilbert space dimension $n$ has $n$ vertices. To have a connected subgraph we
need to find $n-1$ decoupled transitions such that they create a single
connected component. This works quite efficiently if there are no resonant
transitions in the system.

In the following, we expand this graph test such that it also works with
resonant transitions. To this end, we adapt graphical methods for
controllability analysis in degenerate systems [19] to systems with degenerate
energy gaps driven by multiple controls. Since resonant transitions are very
common in qubit arrays due to the multi-partite structure of the system, this
modification opens the route to efficient analysis of controllability of qubit
arrays.

##  3 Graph test of controllability for coupled subsystems

In this section we outline the algorithm for a graph test for coupled
subsystems with resonant transitions. In subsection 3.1 we present methods to
determine the graphical commutators already used in rotor systems [10] and we
introduce the concept of subalgebras to treat resonant transitions driven by
multiple controls. We show in subsection 3.2 that the graphical commutators
can be calculated in a systematic way, avoiding the construction of the entire
dynamical Lie algebra of a system. We illustrate the use of these methods in
subsection 3.3 with simple two-qubit examples.

###  3.1 Resonant transitions and graphical commutators

We first present two concepts to decouple resonant transitions without
calculating the complete Lie algebra of the system. To this end, we introduce
the generalized skew-Hermitian Pauli matrices

$\displaystyle\hat{G}_{j,k}$ $\displaystyle=e_{j,k}-e_{k,j}\,,$
$\displaystyle\hat{F}_{j,k}$ $\displaystyle=ie_{j,k}+ie_{k,j}\,,$ (2)
$\displaystyle\hat{D}_{j,k}$ $\displaystyle=ie_{j,j}-ie_{k,k}\,,$

where $e_{j,k}$ is the null matrix except for a 1 in the entry $(j,k)$. The
commutators of these matrices with the skew-Hermitian drift are given by [23,
19]

$\displaystyle[i\hat{H}_{0},\hat{G}_{j,k}]$ $\displaystyle=-\Delta
E_{k,j}\hat{F}_{j,k}\,,$ $\displaystyle[i\hat{H}_{0},\hat{F}_{j,k}]$
$\displaystyle=\Delta E_{k,j}\hat{G}_{j,k}\,.$ (3)

Consider a transition $(i,k)$ with transition matrix element

$\langle e_{i}|\hat{H}_{j}|e_{k}\rangle=\alpha-i\beta\,,$ (4)

where $\ket{e_{i}}$, $\ket{e_{k}}$ with $i\neq k$ are eigenstates of the drift
Hamiltonian, $\hat{H}_{0}$, $\alpha,\beta\in\mathbb{R}$ and at least one of
them is nonzero. If $(i,k)$ is a decoupled transition, the Lie algebra of the
system contains the element

$\hat{T}=\alpha\hat{F}_{i,k}+\beta\hat{G}_{i,k}\,,$ (5)

and the generalized skew-Hermitian Pauli matrices
$\hat{G}_{i,k},\hat{F}_{i,k}$ and $\hat{D}_{i,k}$ are also elements of the Lie
algebra $Lie(i\hat{H}_{0},\hat{T})$, i.e.,
$dim[Lie(i\hat{H}_{0},{\hat{T}})]=4$.

If a system contains the two decoupled transitions $\\{(i,k),(i,l)\\}$ with
$\hat{T}_{1}=\alpha_{1}\hat{F}_{i,k}+\beta_{1}\hat{G}_{i,k}$ and
$\hat{T}_{2}=\alpha_{2}\hat{F}_{i,l}+\beta_{2}\hat{G}_{i,l}$, respectively,
and $i\neq l\neq k$, their commutator is of the form
$\hat{T}_{3}:=[\hat{T}_{1},\hat{T}_{2}]=\alpha_{3}\hat{F}_{k,l}+\beta_{3}\hat{G}_{k,l}$.
The graph of the system thus has an additional edge $(k,l)$, as depicted in
Figure 1(a) for $i=0$, $k=1$ and $l=2$. For testing controllability, it is
often sufficient to know that there exists a transition $(k,l)$, without
calculating the coefficients $\alpha_{3},\beta_{3}$. Since the existence of
the transition $(k,l)$ can be deduced from the graph with edges $(i,k)$ and
$(i,l)$, we refer to this operation as graphical commutator and denote it as
$(k,l)=[(i,k),(i,l)]$.

Figure 1: Examples for graphical commutators. The circles represent the
vertices of the graph and the edges (transitions) are depicted by the arrows.
Same-colour arrows represent coupled transitions. In all cases, the commutator
between the transitions depicted by dashed blue and dash-dotted green arrows
result in transitions depicted by solid red arrows. The four panels present
the following cases: (a) Graphical commutator between two uncoupled
transitions $[(0,1),(0,2)]=(1,2)$ (b) Graphical commutator between the coupled
transitions $\\{(0,3),(1,4)\\}$ and the uncoupled transition $(1,2)$ results
in the uncoupled transition $(2,4)$ (c) Graphical commutator between the
coupled transitions $\\{(0,1),(2,3)\\}$ and the uncoupled transition $(1,2)$
results in the coupled transition $\\{(0,2),(1,3)\\}$. (d) The commutator
between the coupled transitions $\\{(0,2),(1,3)\\}$ and $\\{(0,1),(2,3)\\}$
cannot be determined graphically.

Graphical commutators can be used as an efficient tool to decouple resonant
transitions. This is shown in the example depicted in Figure 1(b) Consider
transitions $\hat{T}_{1}=\alpha_{1}\hat{G}_{1,2}+\beta_{1}\hat{F}_{1,2}$
(dash-dotted green arrow in Figure 1(b)) and
$\hat{T}_{2}=\alpha_{2}\hat{F}_{0,3}+\beta_{2}\hat{G}_{0,3}+\gamma_{2}\hat{F}_{1,4}+\delta_{2}\hat{G}_{1,4}$
(dashed blue arrows) with $\hat{T}_{1}$ decoupled (i.e. the transition $(1,2)$
is not coupled to any other one) and $\hat{T}_{2}$ consisting of the pair of
coupled transitions $\\{(0,3),(1,4)\\}$, which are not coupled to any other
transition. The graphical commutator between $\hat{T}_{1}$ and $\hat{T}_{2}$
has then only contributions corresponding to the transition $(2,4)$, depicted
by the red arrow. The graph has thus the additional decoupled transition
$(2,4)$. Furthermore, the graphical commutator between the decoupled
transitions $(1,2)$ and $(2,4)$ is the decoupled transition $(1,4)$. In this
example, the resonant transitions $\\{(0,3),(1,4)\\}$ can thus be decoupled by
taking graphical commutators.

In certain instances, the graphical commutators might not give enough
information to decouple resonant transitions and determine the controllability
of the system. Examples are shown in Figure 1(c) and (d). In Figure 1(c), the
graphical commutator between the coupled transitions $\\{(0,1),(2,3)\\}$
(dashed blue arrows) and the decoupled transition $(1,2)$ (dash-dotted green
arrows) results in the coupled transitions $\\{(0,2),(1,3)\\}$ (red arrows).
This does not allow for decoupling any of the coupled transitions. In Figure
1(d), two pairs of coupled transitions are considered, namely
$\\{(0,1),(2,3)\\}$ (dashed blue arrows) and $\\{(0,2),(1,3)\\}$ (dash-dotted
green arrows). The graphical commutators $[(0,1),(0,2)]$ and $[(1,3),(2,3)]$
both result in the transition $(1,2)$. Without further knowledge of the
coefficients of the corresponding Lie algebra elements, it is not possible to
determine whether the two terms result in a non-zero transition $(1,2)$, or
whether they cancel each other.

In such cases, we make use of an alternative procedure to decouple resonant
transitions, which takes into account that in qubit systems, the same
(coupled) transitions are often driven by different controls. Consider a
system with drift $\hat{H}_{0}$ and two controls that both drive the two
resonant transitions $\\{(1,2),(3,4)\\}$. The Lie algebra of the system thus
contains the terms

$\displaystyle\hat{T}_{4}$
$\displaystyle=\alpha_{4}\hat{F}_{1,2}+\beta_{4}\hat{G}_{1,2}+\gamma_{4}\hat{G}_{3,4}+\delta_{4}\hat{G}_{3,4}\,,$
$\displaystyle\hat{T}_{5}$
$\displaystyle=\alpha_{5}\hat{F}_{1,2}+\beta_{5}\hat{G}_{1,2}+\gamma_{5}\hat{G}_{3,4}+\delta_{5}\hat{G}_{3,4}\,.$
(6)

The two transitions $(1,2)$ and $(3,4)$ are decoupled if
$\hat{T}_{6}:=\alpha_{6}\hat{F}_{1,2}+\beta_{6}\hat{G}_{1,2}$ is an element of
the Lie algebra $Lie(i\hat{H}_{0},\hat{T}_{4},\hat{T}_{5})$ for any real
$\alpha_{6},\beta_{6}$ (at least one of them nonzero). This is true if and
only if
$dim\left[Lie(i\hat{H}_{0},\hat{T}_{4},\hat{T}_{5})\right]=dim\left[Lie(i\hat{H}_{0},\hat{G}_{1,2},\hat{G}_{3,4})\right]=\,7$,
i.e., when the generated sub-algebra has maximum dimension (for a given number
of transitions). Note that we have deliberately chosen transitions
$\\{(1,2),(3,4)\\}$, which have no vertex in common, i.e., they are disjoint.
Restricting ourselves to disjoint transitions, the maximum dimension of the
generated sub-algebra is $3n_{t}+1$, where $n_{t}$ is the number of
transitions that are coupled. In order to determine, if a set of $n_{t}$
transitions driven by $n_{t}$ different controls is decoupled, it is thus
sufficient to calculate the dimension of the sub-algebra with maximal
dimension $3n_{t}+1$. This is typically much smaller than the dimension of the
Lie algebra of the complete system. If the transitions are not disjoint, the
dimension of the relevant subalgebra scales quadratically with the number of
transitions $n_{t}$. This, although feasible for a small number of
transitions, would make the construction of the subalgebras more demanding

In the following we use both methods, i.e., graphical commutators and the
calculation of the dimension of small sub-algebras, in order to decouple
resonant transitions. This allows us to extend the graph test for
controllability to coupled susbystems with resonant transitions.

###  3.2 Algorithms for graph test of controllability for coupled subsystems
with resonant transitions

Our graph test for controllability of a quantum system with resonant
transitions is divided into several steps, depicted in Figure 2. The main
output of the complete algorithm is a variable conveying whether the system is
controllable, not controllable or whether the test remains inconclusive.

Figure 2: Flowchart representing the necessary steps and order in which the
three main subroutines (A1-3) are used. The three possible results for this
test are displayed in the three green round cells.

1

2Input:
$\bullet$ H_op: list including the drift $\hat{H}_{0}$ and all control
operators $\hat{H}_{j}$ in the logical basis.
$\bullet$ $\mathbf{\delta_{H}}$: minimum tolerance for a nonzero transition
coefficient.
$\bullet$ $\mathbf{\delta_{E}}$: minimum tolerance for two energy gaps to be
identical.

3Diagonalize $\hat{H}_{0}$ and represent all control operators $\hat{H}_{j}$
in the eigenbasis of $\hat{H}_{0}$.

4Initialize decoupled-graph, representing every eigenstante $\ket{e_{a}}$ of
$\hat{H}_{0}$ as a vertex in the graph.

5for  _every control $\hat{H}_{j}$ in H_op_ do

6 for  _$0\leq a <b<\text{Hilbert space dimension}$_ do

7 if  _$\left|\bra{e_{a}}\hat{H}_{j}\ket{e_{b}}\right| >\delta_{H}$_ then

8 Add $(a,b)$ to transition-list.

9 end if

10

11 end for

12

13 Sort transition-list by the energy gaps $\Delta E_{a,b}:=|E_{a}-E_{b}|$

14 for  _every $(a,b)$ in transition-list_ do

15 Add all transitions $(c,d)$ resonant to $(a,b)$ (i.e. $\left|\Delta
E_{a,b}-\Delta E_{c,d}\right|<\delta_{E}$) to a new, separate list resonant-
trans-ab (including $(a,b)$).

16 Add coefficients $\bra{e_{c}}\hat{H}_{j}\ket{e_{d}}$ of all resonant
transitions $(c,d)$ into a new list resonant-coef-ab (including $(a,b)$).

17 if  _resonant-trans-ab has more than one element_ then

18 Add resonant-trans-ab as a new entry in the list coupled-transitions.

19 Add resonant-coef-ab as a new entry in the list coupled-coefficients.

20 else

21 Add resonant-trans-ab as a decoupled transition in decoupled-graph.

22 end if

23

24 Remove all resonant transitions $(c,d)$ and $(a,b)$ from transition-list.

25 end for

26

27 end for

28

29Output:
$\bullet$ decoupled-graph: a dictionary containing all vertices of the graph
(eigenstates of $\hat{H}_{0}$) and all decoupled transitions as edges.
$\bullet$ coupled-transitions: a list of lists containing all coupled
transitions stored as dictionaries and sorted by their respective energy gap
$\Delta E_{a,b}$. Resonant transitions from the same control with the same
$\Delta E_{a,b}$ are stored in the same inner list since they are coupled.
$\bullet$ coupled-coefficients: a list of lists of the transition
coefficients, matching the order of coupled-transitions.

Algorithm 1 Compute the initial graph of the system

1 Input:
$\bullet$ decoupled-graph: from algorithm 1.
$\bullet$ graph-components: list containing the sets representing the
connected components of decoupled-graph.
$\bullet$ coupled-transitions: from algorithm 1.

2transition-added = False

3connecting-transitions-found = False

4$i=0$

5while  _( $i$ < length of coupled-transitions) and (transition-added =
False)_ do

6 $i=i+1$

7 element_i = coupled-transitions$[i]$
# element_i is a set of coupled transitions of the form
$\\{(a_{0},a_{1}),(a_{2},a_{3}),...\\}$

8 $j=0$

9 while  _( $j$ < length of element_i) and (transition-added = False)_ do

10

11 $j=j+1$

12 $(b_{0},b_{1})=$ element_i$[j]$

13 if  _$b_{0}$ and $b_{1}$ belong to different components in graph-
components_ then

14

15 connecting-transitions-found = True

16 component_0 = component in graph-components containing $b_{0}$

17 component_1 = component in graph-components containing $b_{1}$

18 $k=0$

19 while  _( $k$ < number of transitions in decoupled-graph) and (transition-
added = False)_ do

20

21 $k=k+1$

22 $(c_{0},c_{1})=k\text{-th}$ transition in decoupled-graph

23 if  _( $\\{c_{0},c_{1}\\}\subset$ component_0) or
($\\{c_{0},c_{1}\\}\subset$ component_1)_ then

24

25 graphical-commutator = [element_i, $(b_{0},b_{1})$]

26 if  _graphical-commutator is a single transition_ then

27

28 transition-added = True

29 Add graphical-commutator to decoupled-graph

30 Merge component_0 and component_1 in graph-components

31 end if

32

33 end if

34

35 end while

36

37 end if

38

39 end while

40

41 end while

42

43Output:
$\bullet$ decoupled-graph: updated after the routine.
$\bullet$ graph-components: updated after the routine.
$\bullet$ transition-added: True if a transition was added during this
subroutine to decoupled-graph; False otherwise.
$\bullet$ connecting-transitions-found: True if at least one transition in
coupled-transitions connects different components; False otherwise.

Algorithm 2 Add a single decoupled transition using graphical commutators

1 Input:
$\bullet$ decoupled-graph: from algorithm 2.
$\bullet$ graph-components: from algorithm 2.
$\bullet$ coupled-transitions: from algorithm 1.
$\bullet$ coupled-coefficients: from algorithm 1.

2for  _every set of resonant transitions
$\\{(a_{0},a_{1}),(a_{2},a_{3}),...\\}$ in coupled-transitions_ do

3 resonant-set = $\\{(a_{0},a_{1}),(a_{2},a_{3}),...\\}$

4 if  _resonant-set contains only disjoint transitions_ then

5 if  _resonant-set connects different components in graph-components_ then

6 if  _resonant-set appears multiple times in coupled-transitions_ then

7 Set $m$ as the number of times resonant-set is generated by different
controls.

8 Set $n_{t}$ as the number of coupled transitions in resonant-set

9 for  _$0\leq j <m$_ do

10

11 Using the coefficients in coupled-coefficients related to the $j$-th
instance of resonant-set, generate an array T-array-j to represent the
transition.
#
$\hat{T}_{j}=\alpha_{a_{0},a_{1}}^{(j)}\hat{F}_{a_{0},a_{1}}+\beta_{a_{0},a_{1}}^{(j)}\hat{G}_{a_{0},a_{1}}+\alpha_{a_{2},a_{3}}^{(j)}\hat{F}_{a_{2},a_{3}}+\beta_{a_{2},a_{3}}^{(j)}\hat{G}_{a_{2},a_{3}}+...$
# T-array-j
$=\left(\alpha_{a_{0},a_{1}}^{(j)},\beta_{a_{0},a_{1}}^{(j)},0,\alpha_{a_{2},a_{3}}^{(j)},\beta_{a_{2},a_{3}}^{(j)},0,...\right)$

12 end for

13 if
_$dim\left(Lie\left\\{i\hat{H}_{0},\textit{T-array-0},...,\textit{T-array-m}\right\\}\right)=3n_{t}+1$_
then

14 Add every transition in resonant-set to decoupled-graph

15 end if

16

17 end if

18

19 end if

20

21 end if

22

23 end for

24

25Output:
$\bullet$ decoupled-graph: updated after the routine.

Algorithm 3 Subroutine to compute subalgebras of repeated resonant transitions

As can be seen in Figure 2, the first stage is creating the initial graph of
the quantum system (A1). The step-by-step definition is found in algorithm 1.
To compute this graph, we diagonalize the drift $\hat{H}_{0}$, taking its
eigenstates as the vertices of the graph. Then, we determine the nonzero
transitions $\bra{e_{a}}\hat{H}_{j}\ket{e_{b}}$ for all $m$ controls and take
these to be the edges $(a,b)$ of the graph. Numerically, we take into account
all transitions that are larger or equal than a certain tolerance,
$\delta_{H}>0$, i.e.,

$\left|\bra{e_{a}}\hat{H}_{j}\ket{e_{b}}\right|\geq\delta_{H}\quad\longrightarrow\quad(a,b)\,.$
(7)

The next step is to determine which transitions are coupled. As defined in
section 2, two or more transitions are coupled if and only if they have the
same energy gap and are generated by the same control. Any transition not
coupled to any other one is by definition a decoupled transition. Note that
two transitions generated by different controls can never be coupled to one
another. To numerically compare the energy gaps, we define a minimal tolerance
$\delta_{E}>0$ such that two transitions driven by the same control, $(a,b)$
and $(c,d)$, are considered coupled if $\left|\Delta E_{a,b}-\Delta
E_{c,d}\right|\leq\delta_{E}$. We sort all the transitions of each control
according to the energy gaps $\Delta E_{a,b}$ and separate them depending on
whether they are coupled or not. If a coupled transition $(a,b)^{(j)}$ is
generated by multiple controls $\hat{H}_{j}$, we also calculate and store the
corresponding transition coefficients
$\bra{e_{a}}\hat{H}_{j}\ket{e_{b}}=\alpha_{a,b}^{(j)}+\beta_{a,b}^{(j)}i$.
Note that here, we have introduced the notation $(a,b)^{(j)}$ to indicate that
the transition $(a,b)$ is driven by the control $\hat{H}_{j}$.

The output of algorithm 1 encompasses the decoupled-graph, the coupled-
transitions and the coupled-coefficients. The first output, decoupled-graph,
is a dictionary that contains all vertices (eigenstates) and all decoupled
edges (decoupled transitions) of the systems graph. These are the elements
that we can use directly to test the controllability of the system using
Theorem 1. In the second output, coupled-transitions, every set of coupled
transitions is stored as a list of tuples $(a,b)$. Coupled transitions cannot
be immediately used for the test in Theorem 1, but are necessary for
generating additional decoupled transitions, by using graphical commutators or
subalgebras of resonant transitions. The last output variable coupled-
coefficients consists of the entries
$\bra{e_{a}}\hat{H}_{j}\ket{e_{b}}=\alpha_{a,b}^{(j)}+\beta_{a,b}^{(j)}i$ for
every coupled transition $(a,b)^{(j)}$ which are required for calculating the
dimension of the subalgebras.

Once the initial graph of the system has been computed, we check if the graph
containing only decoupled transitions (decoupled-graph) is connected. To do
so, we determine the number of connected components in the graph. In terms of
graph theory, a component is a connected subgraph that it is not contained in
any larger connected subgraph. In other words, each of the connected parts
into which we can divide a graph is called a component of the graph.
Therefore, the graph is connected if and only if it has exactly one component.
One of the many possible ways to count the number of components is to use the
depth-first search (DFS) algorithm222The DFS algorithm is a common recursive
algorithm to explore explore systematically all vertices in a graph. It uses
an exhaustive search by traversing down a chain of edges, or by backtracking
when not possible.. If the decoupled-graph is already connected, we can stop
the routine and state that the system is indeed controllable.

If the graph is not connected, then algorithm 2 is called. The aim of this
algorithm is to search for an additional edge of the graph by using graphical
commutators. As explained in section 2, the graphical commutators of a coupled
transition and a decoupled transition may generate a new decoupled transition.
Note that, instead of identifying and adding every possible combination of
commutators between a decoupled transition and a set of coupled transitions,
we are only interested in commutators that result in a decoupled transition
which connects different components of the graph and therefore potentially
creates a connected graph. That is, in algorithm 2 we compute the commutator
of a coupled transition that connects two separate components of decoupled-
graph with a decoupled transition in one of the two components. If the result
of this commutator is a decoupled transition, then this new edge will connect
the two components in decoupled-graph, merging them into a single component.
If a new decoupled transition is added to the decoupled-graph during this
step, the number of connected components is counted again to determine if the
graph is now connected.

If the number of components is still larger than one, i.e. if the decoupled-
graph is not connected after algorithm 2, and no new transition was added
during its last call, then we check if there is any transition in coupled-
transitions that connects different components of decoupled-graph. If this is
not the case, the routine is stopped. If all transitions, coupled and
decoupled, only connect vertices within the same components, then all possible
commutators result in transitions within the same components. The number of
components will stay constant and the graph will never be connected. This
implies that the system is not controllable.

However, if there exists at least one coupled transition connecting different
components, then this argument is no longer valid and the controllability of
the system is not yet decided. For these cases, we use the coupled-
coefficients that are related to the coupled-transitions to obtain a more
conclusive answer.

This step is carried out by algorithm 3. It builds upon the updated decoupled-
graph from algorithm 2 and tries to add new decoupled transitions by computing
the low-dimensional subalgebras of resonant transitions driven by different
controls. First, the algorithm selects the transitions from coupled-
transitions that connect different components. In particular, we are
exclusively interested in sets of disjoint transitions, such that the
dimension of the associated subalgebras remains low. Next, the algorithm finds
out if those transitions have a multiplicity equal to or higher than 2, that
is, if the same sets of coupled transitions
$\left\\{(a_{0},a_{1}),(a_{2},a_{3}),...\right\\}^{(j)}$ are generated
multiple times by different controls $\hat{H}_{j}$. Following the reasoning
presented in subsection 3.1, we try to generate the full associated subalgebra
of the coupled-transitions,
$\left\\{(a_{0},a_{1}),(a_{2},a_{3}),...\right\\}$, by using their respective
coupled-coefficients. If a subalgebra with maximal dimension is generated, we
take all transitions $\left\\{(a_{0},a_{1}),(a_{2},a_{3}),...\right\\}$ as
effectively decoupled. This allows us to add every transition $(a_{k},a_{l})$
as a decoupled edge to decoupled-graph. Note that in algorithm 3, we compute
the Lie subalgebras of the resonant transitions including $i\hat{H}_{0}$,
where we deduce the commutators
$\left[i\hat{H}_{0},\left\\{(0,1),(2,3)\right\\}^{(j)}\right]$ using
subsection 3.1. This makes these calculations simple and encompassed within a
vector space of dimension $3n_{t}$, with $n_{t}$ being the number of
transitions in $\left\\{(a_{0},a_{1}),(a_{2},a_{3}),...\right\\}$.

Finally, we compute the new number of components in decoupled-graph using DFS
once again. If the graph is still not connected, we use algorithm 2 to add as
many graphical commutators as possible to connect the remaining components. If
the graph ends up with one single component, the system is controllable. If
there are more components and there are no transitions in coupled-transitions
that connect any of them, then the system is proven to be not controllable. If
none of these two hold to be true, then the controllability test remains
inconclusive. Indeed, unlike the dynamical Lie algebra method, the test might
yield no definitive answer. If a graph is not connected, we cannot ensure that
the system is not controllable, generally speaking. It might be that the graph
can be connected after computing a large number of commutators or that it will
remain forever not connected. Calculating this quantity of commutators is
tantamount to computing the dynamical Lie algebra and would therefore be
unfeasible for relatively large systems.

###  3.3 Illustrative examples

Here we present two examples constructed to showcase how the algorithms
described in subsection 3.2 work.

Figure 3: (a) Two-qubit system with Hamiltonian (8), where $\omega_{0}=5$ GHz,
$\omega_{1}=5.5$ GHz, $J=150$ MHz. (b) Graph of the system. All transitions
are decoupled, making the system controllable by Theorem 1.

We start by considering the two-qubit system shown in Figure 3(a), described
by the Hamiltonian

$\hat{H}_{2A}(t)=\hat{H}_{0}+u_{1}(t)\hat{H}_{1}$ (8)

with the drift

$\hat{H}_{0}=\sum_{i=0}^{1}-\frac{\omega_{i}}{2}\hat{Z}^{i}+J(\hat{X}^{0}\hat{X}^{1}+\hat{Z}^{0}\hat{Z}^{1})\,,$
(9)

and a single local control $\hat{H}_{1}=\hat{X}^{1}$ acting on qubit 1. Here,
$\omega_{i}$ are the natural frequencies of the qubits and $J$ is the coupling
strength. For simplicity, we use the notation
$\hat{X}^{j}=\hat{\sigma}_{x}^{j}$ for the Pauli matrices. Algorithm 1 results
in the graph shown in Figure 3(b) with the circular vertices representing the
eigenstates of $\hat{H}_{0}$. The local control $\hat{H}_{1}$ gives rise to
four non-zero transitions, which form the edges of the graph, denoted by the
arrows in Figure 3(b). The different lengths of the arrows indicate that all
four transitions have different energy gaps and are thus decoupled. The actual
controllability test for this example consists simply of algorithm 1 and the
DFS algorithm, which proves that the graph is connected and the system is
controllable. In other words, from every vertex $i=0,...3$, every other vertex
of the graph can be reached by following the edges belonging to decoupled
transition, as seen in Figure 3(b).

Figure 4: (a) Two-qubit system with Hamiltonian (10) where $\omega_{0}=5$GHz,
$\omega_{1}=5.5$ GHz, $J=150$ MHz. Both local controls are necessary for the
system to be controllable. (b) Graph of the system. Theorem 1 is not directly
applicable due to the coupled transitions. A study of the coefficients reveals
that it is possible to decouple all transitions.

A second example is illustrated in Figure 4(a). Here, the Hamiltonian is given
by

$\hat{H}_{2B}(t)=\hat{H}_{0}+\sum_{j=1}^{2}u_{j}(t)\hat{H}_{j}$ (10)

with the drift

$\hat{H}_{0}=\sum_{i=0}^{1}-\frac{\omega_{i}}{2}\hat{Z}^{i}+J\hat{X}^{0}\hat{X}^{1}\,,$
(11)

and two local controls

$\hat{H}_{1}=\hat{X}^{1}\quad\quad\mbox{and}\quad\quad\hat{H}_{2}=\hat{X}^{0}$
(12)

acting on the qubits 1 and 0, respectively. The main difference between
Equation 10 and Equation 8 is the omission of $\hat{Z}^{0}\hat{Z}^{1}$ in the
drift Hamiltonian. This severely impacts the graph, as seen in Figure 4. The
symmetries that had previously been broken by including
$\hat{Z}^{0}\hat{Z}^{1}$ appear in the energy gap degeneracies, $\Delta
E_{0,1}=\Delta E_{2,3}$ and $\Delta E_{0,2}=\Delta E_{1,3}$. There are no
decoupled transitions and the number of components in the initial graph is
equal to four. A second difference is the second local control. The
transitions driven by the controls $\hat{X}^{1}$ (which is the same local
control as in Equation 8) and $\hat{X}^{0}$ consist of two pairs of coupled
transitions $\\{(0,1),(2,3)\\}$ and $\\{(0,2),(1,3)\\}$ shown by purple solid
and dashed blue arrows respectively in Figure 4(b).

| Transition parameters
---|---
| $(0,1)$ | $(2,3)$ | $(0,2)$ | $(1,3)$
$\hat{X}^{0}$ | $0.967$ | $0.967$ | $-0.253$ | $0.253$
$\hat{X}^{1}$ | $-0.281$ | $0.281$ | $-0.960$ | $-0.960$
Table 1: Control coefficients $\bra{e_{a}}\hat{H}_{j}\ket{e_{b}}$ for the
system (10). The coupled transitions are $\\{(0,1),(2,3)\\}$ and
$\\{(0,2),(1,3)\\}$. They appear with double multiplicity, once for each
control.

In this example, graphical commutators do not yield any new transition that we
could add to the graph. In fact, we can only take commutators of pairs of
coupled transitions, analogously to the case depicted in Figure 1(d). Since
there is no definitive answer, graphical commutators are not useful in this
particular instance. However, since there exist coupled transitions which
connect different components of the graph, algorithm 3 can be applied. The
coefficients
$\bra{e_{a}}\hat{H}_{j}\ket{e_{b}}=\alpha_{a,b}^{(j)}+\beta_{a,b}^{(j)}i$ of
the coupled transitions are shown in Table 1. Note that in this example, the
coefficients are real, $\beta_{a,b}^{(j)}=0$. The Lie algebra thus contains
the terms

$\displaystyle\hat{T_{0}}=\alpha_{0,1}^{(0)}{\hat{F}}_{0,1}+\alpha_{2,3}^{(0)}{\hat{F}}_{2,3}\,,$
$\displaystyle\hat{T_{1}}=\alpha_{0,1}^{(1)}{\hat{F}}_{0,1}+\alpha_{2,3}^{(1)}{\hat{F}}_{2,3}\,.$
(13)

It is immediate to see that we can isolate the term $\hat{F}_{2,3}$ by a
linear combination of ${\hat{T}}_{0}$ and ${\hat{T}}_{1}$. This means that all
operators $\hat{F}_{2,3},\hat{G}_{2,3},\hat{D}_{2,3}$ are elements of the
subalgebra. Similarly, the opposite linear combination can isolate the element
$\hat{F}_{0,1}$, adding $\hat{F}_{0,1},\hat{G}_{0,1},\hat{D}_{0,1}$ to the
generated subalgebra. This means that the dimension of
$Lie\left(i\hat{H}_{0},\hat{T}_{0},\hat{T}_{1}\right)=7$ (including the
contribution of $i\hat{H}_{0}$) is maximal and thus the transitions $(0,1)$
and $(2,3)$ can be decoupled. Analogously, $(0,2)$ and $(1,3)$ may be
decoupled as well. This means that all the edges are decoupled in the graph of
Figure 4. By virtue of Theorem 1, this implies controllability of the system.

##  4 Results

In this section, we examine qubit systems which are used for quantum
computing. With the algorithm presented in section 3, we can efficiently prove
if a given qubit array is controllable. We present three different examples
based on the IBM five-qubit array ibmq_quito [24]. We do not use the exact
parameters of this system, but simply its configuration and realistic
parameters (except for the natural frequencies which correspond to the real
data [24]).

The Hamiltonian of an array similar in structure to ibmq_quito can be
expressed as:

$\hat{H}^{\textit{quito}}(t)=-\sum_{j=0}^{4}\frac{\omega_{j}}{2}\hat{Z}^{j}+\hat{H}_{c}^{\textit{quito}}+\sum_{k=1}^{m}u_{k}(t)\hat{H}_{k}\,,$
(14)

where $u_{k}(t)$ represent local controls and the couplings
$\hat{H}_{c}^{\textit{quito}}$ are of the form

$\hat{H}_{c}^{\textit{quito}}=J_{0,1}\hat{H}_{0,1}+J_{1,2}\hat{H}_{1,2}+J_{1,3}\hat{H}_{1,3}+J_{3,4}\hat{H}_{3,4}$
(15)

with each $\hat{H}_{j,k}$ representing an entangling (time-independent)
coupling between the qubits $j$ and $k$. The following three examples are
based on Equation 14 for different types of couplings and local controls. We
will prove that while the original IBM design is indeed controllable there
exist options that require fewer resources for controllability.

The set of parameters, including the natural frequencies $\omega_{j}$ and the
coupling strengths $J_{i,j}$ are found in Table 2. We use these parameters for
all examples presented in this section.

| Coupling strengths (MHz)
---|---
| $J_{0,1}$ | $J_{1,2}$ | $J_{1,3}$ | $J_{3,4}$
| $100$ | $250$ | $170$ | $300$
Qubit frequencies (GHz)
$\omega_{0}$ | $\omega_{1}$ | $\omega_{2}$ | $\omega_{3}$ | $\omega_{4}$
$5.301$ | $5.081$ | $5.322$ | $5.164$ | $5.052$
Table 2: Parameters for the system (14). The qubit frequencies are those of
[24]. The coupling strengths have been chosen to be in the range of hundreds
of MHz, common for this type of qubits.

###  4.1 Example A: five-qubit system similar to IBM’s ibmq_quito

This example mimics the qubit arrangement of ibmq_quito. The static couplings
in Equation 15 are [25]

$\hat{H}_{ij}=J_{i,j}\left(\hat{X}^{i}\hat{X}^{j}+\hat{Y}^{i}\hat{Y}^{j}\right)\,.$
(16)

A local control $\hat{H}_{j}=\hat{X}^{j}$ is added to every qubit. The system
diagram is shown in Figure 5.

Figure 5: Five-qubit system inspired by IBM’s ibmq_quito with Hamiltonian
found in Equation 14. The rectangles present the qubits with natural
frequencies $\omega_{j}$, $j=1-5$, and the lines indicate the couplings
between the qubits. Local controls are to be assumed in every qubit in the
form of $\hat{X}^{j}$.

For a five-qubit system, there is a total of 32 vertices. After running
algorithm 2 for this example with an energy gap tolerance of
$\delta_{E}=0.01$GHz, we obtain an initial graph with only 7 decoupled edges,
resulting in a total of 25 different connected components. Use of algorithm 2
alone is not enough in this case, since the graphical commutators do not yield
any new results. Executing algorithm 3, a total of 192 new edges are added to
the graph. These turn out to be more than sufficient to connect all the
components and achieve a connected graph.

We can thus conclude that the system presented in Figure 5 is controllable and
therefore suitable to perform any unitary operation. In the following examples
we investigate whether the five-qubit array is also controllable if the number
of local controls is reduced.

###  4.2 Example B: five-qubit system with reduced number of controls

Figure 6: Same as Figure 5 with fewer controls, located on qubits 1 and 3
(pink rectangles).

Next, we investigate the controllability of a five-qubit system with a reduced
number of local controls. For the drift Hamiltonian, we consider the same
five-qubit system as before with all parameters as listed in Table 2 but
decrease the number of local controls to two. This is depicted in Figure 6,
which represents one of the ten different scenarios with two local controls
$\hat{H}_{j}=\hat{X}^{j}$.

Running algorithm 1 we obtain identical results to those in subsection 4.1: a
graph with only 7 decoupled transitions and 25 different connected components.
Again, it is crucial to use algorithm 3 to make the graph connected. It may
come as a surprise that the number of new edges that we can add is again 192.
In other words, the number of new decoupled edges has not been reduced by
removing three of the local controls. With the new decoupled edges included,
the system is indeed controllable.

We could attempt to take this study further to single local control. However,
with a single local control $\hat{X}^{j}$, we always obtain an inconclusive
result, no matter on which qubit we apply it. Although this hints to the
possibility of the system not being controllable, the algorithm cannot
conclusively determine it, similarly to the case shown in Figure 4. In that
two-qubit example we can prove using the Lie algebra method that a single
local control $\hat{X}^{j}$ is never sufficient. We therefore conjecture that
the least number of local controls required for the system to be controllable
is two.

Since two local controls is the minimum number to obtain a controllable
system, we now study how the position of the control affects controllability.
We categorize all possible arrangements of two local controls $\hat{X}^{j}$ by
their distance. For example, the local controls for qubits 1 and 3, shown in
Figure 6, have distance equal to 1 since they are direct neighbors connected
by a single coupling. Analogously, we can set local controls separated by two
couplings (e.g. on qubit 2 and 3) that have distance 2, or local controls for
qubits separated by three couplings (e.g qubits 0 and 4) that have distance 3.
The results of the controllability tests for all these possible arrangements
of two local controls are shown in Table 3.

Distance | Controllability |  $\\#$ cases
---|---|---
1 | Controllable | 4
2 | Inconclusive | 4
3 | Controllable | 2
Table 3: Study of controllability for a five-qubit system similar to
ibmq_quito but with only two local controls.

Accordingly, the five-qubit system is controllable with two local controls if
they have either distance one or three, independent of the position of the
controls themselves. On the other hand, if the controls are at distance 2, the
algorithm returns an inconclusive answer. This implies that algorithm 3 cannot
decouple enough transitions for the graph to be connected. In fact, it turns
out that no new transitions could be added at all. This is because the
coefficients $\bra{e_{a}}\hat{H}_{j}\ket{e_{b}}$ of the different transitions
depend on the position of the local control that drives them. By shifting a
local control to a neighboring qubit, it is common to see a change in some of
the coefficients. The transition coefficients of same-type controls for a set
of coupled transitions tend to be linearly independent when the controls are
shifted by an odd number of qubits and dependent in the even case. This allows
us to generate maximal subalgebras only for controls that are at an odd qubit-
distance, turning the coupled transitions into decoupled transitions that can
eventually make the graph connected.

###  4.3 Example C: five-qubit system with single local control

Figure 7: Diagram introducing a modified version of IBM’s ibmq_quito with
$\hat{Z}\hat{Z}$ contributions added to every coupling and all local controls
removed except for $\hat{X}^{1}$.

To conclude the list of examples, we demonstrate that the number of local
controls that is required for the system to be controllable also depends on
the type for couplings connecting the qubits. We showcase a system that is
controllable with a minimal number of local controls, i.e., a single local
control. The main difference between this example (shown in Figure 7) and the
previous ones (displayed in Figure 5 and 6) is that the couplings are of the
form

$\hat{H}_{ij}=J_{i,j}\left(\hat{X}^{i}\hat{X}^{j}+\hat{Y}^{i}\hat{Y}^{j}+\hat{Z}^{i}\hat{Z}^{j}\right)\,,$
(17)

i.e., they have an extra term $\hat{Z}^{i}\hat{Z}^{j}$ compared to the
couplings considered in the examples before. These kinds of couplings can be
achieved in systems of superconducting qubits by harnessing both capacitive
and inductive interactions between the qubits. Executing algorithm 1 with
$\delta_{E}=0.1$GHz, we obtain a total of 24 initially decoupled edges and a
total of 14 connected components. This is already more promising than the
examples in subsection 4.1 and subsection 4.2. Furthermore, use of graphical
commutators results in the system being controllable, ending up with 37
decoupled edges that are sufficient to make the graph connected. The
controllability analysis thus shows that with the $\hat{Z}^{i}\hat{Z}^{j}$
addition, the system is controllable with only one local control. In Figure 7,
we have added a local control on qubit 1, but additional tests show that the
same statement is true for any single local control $\hat{X}^{j}$, independent
of its position at qubit 0 to 4. Therefore, this controllable system has a
minimal number of local controls at the cost of using a more complex type of
two-qubit couplings.

The effect of couplings of the form $\hat{Z}^{i}\hat{Z}^{j}$ on the graph of
the system can be understood by considering the simple two-qubit systems shown
in Figure 3 and Figure 4. In Figure 4, couplings of the form
$\hat{X}^{i}\hat{X}^{j}$ result in two pairs of resonant (coupled) transitions
for each local control. Therefore, two local controls are required to decouple
the transitions and ensure controllability. In Figure 3, a single control
$\hat{X}$ is sufficient due to the $\hat{Z}^{0}\hat{Z}^{1}$ term in its
coupling. This term is already diagonal in the eigenbasis of the free qubits,
which means that it does not mix the eigenstates of the free qubits. However,
it shifts their eigenenergies, such that all four vertices of the graph
correspond to different transition frequencies and thus a single local control
corresponds to four decoupled transitions, making the system controllable. A
similar effect happens in the present five-qubit example, where the couplings
have an off-diagonal contribution
$\hat{X}^{i}\hat{X}^{j}+\hat{Y}^{i}\hat{Y}^{j}$ and a diagonal part
$\hat{Z}^{i}\hat{Z}^{j}$. The former mixes the free-qubit eigenstates and in
turn creates more edges in the graph with the inclusion of a local control
like $\hat{X}^{j}$. The latter changes some resonant energy gaps and decouples
the transitions associated to them. The combination of these two effects
achieves controllability with a minimal number of local controls, as seen in
Figure 7. The special role of this coupling has already been observed for spin
systems, where spin chains have been proven to be controllable with a number
of local controls smaller than the number of spins [11].

##  5 Summary and conclusions

We have presented a practical way to test for evolution-operator
controllability in order to numerically verify the ability of a given qubit
array to implement universal quantum computing. The graph theory-based
approach allows for analyzing comparatively large qubit systems for which the
evaluation of the Lie rank condition for controllability would be difficult or
impossible. Indeed, the computationally expensive calculation of nested
commutators of the drift and control Hamiltonians, which is required to
construct the system’s dynamical Lie algebra, is avoided in graphical methods.
On the other hand, in some cases, a graphical controllability test remains
inconclusive. We believe that the disadvantage is small in view of the
positive results that can be obtained for systems not amenable to the Lie rank
condition.

The key challenge in controllability tests for systems of coupled qubits using
graph theory-based methods is due to the tensor product structure of Hilbert
space. This leads to graphs that often consist of sets of coupled (resonant)
transitions. A similar problem was encountered in the controllability analysis
of driven quantum rotors [10] which are highly degenerate systems with
multiple resonant transitions. In that case, the specific spectral structure
allowed for an inductive evaluation of the graphical commutators [19]. Here,
we have made no assumptions on the spectral structure of the system. Instead,
we have found and implemented numerically efficient ways to decouple the
resonant transitions such as to make them exploitable for the graph test. In
particular, our algorithm only determines those graphical commutators which
are relevant because they add to the connectivity of the graph. Moreover, we
have made use of fact that in qubit arrays, coupled transitions are typically
driven by several controls: These coupled transitions become decoupled if the
dimension of the subalgebra that they generate when driven by different
controls is maximal. Since the sub-algebras are very small compared to the
Hilbert space of the complete system, their numerical construction does not
pose a challenge. The remaining limitation to the number of qubits $N_{Q}$,
for which a controllability test can be carried out, is the exponential
scaling of the Hilbert space dimension with $N_{Q}$ because the drift
Hamiltonian (including the qubit-qubit couplings) needs to be diagonalized.
Typically, the drift is sparse in the logical basis. For the graph test
presented here, only a single diagonalization of the (sparse) drift
Hamiltonian is necessary to obtain the initial graph.

We have illustrated the utility of our approach by showing how controllability
analysis can be used to determine the minimum number of local controls
required for universal quantum computing in existing quantum processing units.
To this end, we have chosen the five-qubit array ibmq_quito [24] as specific
example, treating the qubit-qubit couplings as fixed. This is justified since,
whenever a system with time-independent couplings is controllable, the
corresponding system with tunable couplings is controllable as well. The
actual ibmq_quito system contains a local control for each of the five qubits.
Our analysis has shown that by modifying the couplings between the qubits, the
number of local controls necessary for universal quantum computing can be
reduced to a single local control. For standard qubit-qubit couplings the
minimal number of local controls is two. Analyzing the controllability for
different positions of the two local controls reveals that the distance
between the local controls is essential for the system to be controllable: The
two local controls must be separated by an odd number (one or three) of qubit-
qubit couplings in order to provide controllability and allow for universal
quantum computing. These results showcase the utility of our graph test for
improving the design and scalability of qubit arrays.

In future work, it will be interesting to gather a deeper understanding of the
required control distance, as this might allow for generalizing our findings
to larger qubit arrays. Another important open question is the relationship
between the minimal number of local controls and the quantum speed limit for
universal quantum computing. The quantum speed limit [26] refers to the
minimum time in which a quantum process, such as a quantum gate, can be
executed. For a complete universal set of gates, the quantum speed limit can
be obtained using quantum optimal control [27]. Given a quantum system and a
set of controls, the time required for any particular operation will always be
equal or longer than the time required for the same operation in the same
system with more controls added. Conversely, reducing the number of local
controls is likely to increase the time needed to carry out a gate. Thus,
reducing the number of local controls has to be balanced with the requirement
of sufficiently fast logical operations. The minimal sets of local controls
from controllability analysis as suggested here offers a good starting point
to find the best balanced set of controls with quantum optimal control.

## Acknowledgments

We would like to thank David Pohl, Max Werninghaus, Eugenio Pozzoli, Daniel
Basilewitsch, Ugo Boscain, and Mario Sigalotti for the helpful discussions. We
gratefully acknowledge financial support from the European Union’s Horizon
2020 research and innovation programme under the Marie Sklodowska-Curie grant
agreement Nr. 765267 (QuSCo) and the Einstein Research Foundation (Einstein
Research Unit on Near-Term Quantum Devices).

## References

  * [1] Steffen J. Glaser, Ugo Boscain, Tommaso Calarco, Christiane P. Koch, Walter Köckenberger, Ronnie Kosloff, Ilya Kuprov, Burkard Luy, Sophie Schirmer, Thomas Schulte-Herbrüggen, D. Sugny, and Frank K. Wilhelm.  “Training Schrödinger’s cat: quantum optimal control. strategic report on current status, visions and goals for research in europe”.  Eur. Phys. J. D 69, 279 (2015).
  * [2] Christiane P. Koch, Ugo Boscain, Tommaso Calarco, Gunther Dirr, Stefan Filipp, Steffen J. Glaser, Ronnie Kosloff, Simone Montangero, Thomas Schulte-Herbrüggen, Dominique Sugny, and Frank K. Wilhelm.  “Quantum optimal control in quantum technologies. strategic report on current status, visions and goals for research in europe”.  EPJ Quantum Technol. 9, 19 (2022).
  * [3] Domenico d’Alessandro.  “Introduction to quantum control and dynamics”.  Chapman and Hall/CRC. (2008).
  * [4] S. G. Schirmer, H. Fu, and A. I. Solomon.  “Complete controllability of quantum systems”.  Phys. Rev. A 63, 063410 (2001).
  * [5] H Fu, S G Schirmer, and A I Solomon.  “Complete controllability of finite-level quantum systems”.  Journal of Physics A: Mathematical and General 34, 1679 (2001).
  * [6] Claudio Altafini.  “Controllability of quantum mechanical systems by root space decomposition of su(n)”.  Journal of Mathematical Physics 43, 2051–2062 (2002).
  * [7] Thomas Chambrion, Paolo Mason, Mario Sigalotti, and Ugo Boscain.  “Controllability of the discrete-spectrum Schrödinger equation driven by an external field”.  Annales de l’Institut Henri Poincaré C 26, 329–349 (2009).
  * [8] Nabile Boussaïd, Marco Caponigro, and Thomas Chambrion.  “Weakly coupled systems in quantum control”.  IEEE Trans. Automat. Control 58, 2205–2216 (2013).
  * [9] U. Boscain, M. Caponigro, T. Chambrion, and M. Sigalotti.  “A weak spectral condition for the controllability of the bilinear Schrödinger equation with application to the control of a rotating planar molecule”.  Comm. Math. Phys. 311, 423–455 (2012).
  * [10] Monika Leibscher, Eugenio Pozzoli, Cristobal Pérez, Melanie Schnell, Mario Sigalotti, Ugo Boscain, and Christiane P. Koch.  “Full quantum control of enantiomer-selective state transfer in chiral molecules despite degeneracy”.  Communications Physics 5, 1–16 (2022).
  * [11] Xiaoting Wang, Peter Pemberton-Ross, and Sophie G. Schirmer.  “Symmetry and subspace controllability for spin networks with a single-node control”.  IEEE Transactions on Automatic Control 57, 1945–1956 (2012).
  * [12] Xiaoting Wang, Daniel Burgarth, and S. Schirmer.  “Subspace controllability of spin-$\frac{1}{2}$ chains with symmetries”.  Phys. Rev. A 94, 052319 (2016).
  * [13] Jiahui Chen, Yehao Zhou, Ji Bian, Jun Li, and Xinhua Peng.  “Subspace controllability of symmetric spin networks”.  Phys. Rev. A 102, 032602 (2020).
  * [14] Francesca Albertini and Domenico D’Alessandro.  “Subspace controllability of multi-partite spin networks”.  Systems & Control Letters 151, 104913 (2021).
  * [15] Francesca Albertini and Domenico D’Alessandro.  “The Lie algebra structure and controllability of spin systems”.  Linear Algebra and its Applications 350, 213–235 (2002).
  * [16] Ugo Boscain, Marco Caponigro, and Mario Sigalotti.  “Multi-input Schrödinger equation: controllability, tracking, and application to the quantum angular momentum”.  Journal of Differential Equations 256, 3524–3551 (2014).
  * [17] Chris Godsil and Simone Severini.  “Control by quantum dynamics on graphs”.  Physical Review A 81, 052316 (2010).
  * [18] Can Gokler, Seth Lloyd, Peter Shor, and Kevin Thompson.  “Efficiently controllable graphs”.  Phys. Rev. Lett. 118, 260501 (2017).
  * [19] Eugenio Pozzoli, Monika Leibscher, Mario Sigalotti, Ugo Boscain, and Christiane P. Koch.  “Lie algebra for rotational subsystems of a driven asymmetric top”.  J. Phys. A: Math. Theor. 55, 215301 (2022).
  * [20] Caroline Figgatt, Aaron Ostrander, Norbert M Linke, Kevin A Landsman, Daiwei Zhu, Dmitri Maslov, and Christopher Monroe.  “Parallel entangling operations on a universal ion-trap quantum computer”.  Nature 572, 368–372 (2019).
  * [21] Philip Krantz, Morten Kjaergaard, Fei Yan, Terry P Orlando, Simon Gustavsson, and William D Oliver.  “A quantum engineer’s guide to superconducting qubits”.  Applied Physics Reviews 6, 021318 (2019).
  * [22] SG Schirmer, ICH Pullen, and AI Solomon.  “Identification of dynamical Lie algebras for finite-level quantum control systems”.  Journal of Physics A: Mathematical and General 35, 2327 (2002).
  * [23] Ugo Boscain, Eugenio Pozzoli, and Mario Sigalotti.  “Classical and quantum controllability of a rotating symmetric molecule”.  SIAM Journal on Control and Optimization 59, 156–184 (2021).
  * [24] IBM.  “IBM quantum”.  url: quantum-computing.ibm.com/services.
  * [25] Marco Roth, Marc Ganzhorn, Nikolaj Moll, Stefan Filipp, Gian Salis, and Sebastian Schmidt.  “Analysis of a parametrically driven exchange-type gate and a two-photon excitation gate between superconducting qubits”.  Physical Review A 96, 062323 (2017).
  * [26] Sebastian Deffner and Steve Campbell.  “Quantum speed limits: from Heisenberg’s uncertainty principle to optimal quantum control”.  Journal of Physics A: Mathematical and Theoretical 50, 453001 (2017).
  * [27] Michael H. Goerz, Felix Motzoi, K. Birgitta Whaley, and Christiane P. Koch.  “Charting the circuit-QED design landscape using optimal control theory”.  npj Quantum Inf. 3, 37 (2017).


# Determining hyperbolicity of compact orientable 3-manifolds with torus
boundary

Robert C. Haraway, III Research partially supported by NSF grant DMS-1006553.

###### Abstract

Thurston’s hyperbolization theorem for Haken manifolds and normal surface
theory yield an algorithm to determine whether or not a compact orientable
3-manifold with nonempty boundary consisting of tori admits a complete finite-
volume hyperbolic metric on its interior.

A conjecture of Gabai, Meyerhoff, and Milley reduces to a computation using
this algorithm.

##  1 Introduction

The work of Jørgensen, Thurston, and Gromov in the late ‘70s showed that the
set of volumes of orientable hyperbolic 3-manifolds has order type
$\omega^{\omega}$. Cao and Meyerhoff in 2001 showed that the first limit point
is the volume of the figure eight knot complement. Agol in 2010 showed that
the first limit point of limit points is the volume of the Whitehead link
complement. Most significantly for this paper, Gabai, Meyerhoff, and Milley in
2009 showed that the smallest, closed, orientable hyperbolic 3-manifold is the
Weeks-Matveev-Fomenko manifold.

The proof of the last result required distinguishing hyperbolic 3-manifolds
from non-hyperbolic 3-manifolds in a large list of 3-manifolds; this was
carried out in [10]. The method of proof was to see whether SnapPea’s
_canonize_ procedure succeeded or not; identify the successes as census
manifolds; and then examine the fundamental groups of the 66 remaining
manifolds by hand. This method made the analysis of non-hyperbolic Mom-4
manifolds, of which there are 762 combinatorial types, prohibitively time-
consuming.

The algorithm presented here determines whether or not a compact 3-manifold
admits a complete finite-volume hyperbolic metric, i.e. is _hyperbolic_ ,
assuming the manifold in question has nonempty boundary consisting of tori.

The Mom-4s have such boundaries. The current implementation of this algorithm
using Regina (see [3]) classifies them, yielding the following result.

m125 | m129 | m202 | m203 | m292 | m295 | m328
---|---|---|---|---|---|---
m329 | m357 | m359 | m366 | m367 | m388 | m391
m412 | s441 | s443 | s503 | s506 | s549 | s568
s569 | s576 | s577 | s578 | s579 | s596 | s602
s621 | s622 | s638 | s647 | s661 | s774 | s776
s780 | s782 | s785 | s831 | s843 | s859 | s864
s880 | s883 | s887 | s895 | s898 | s906 | s910
s913 | s914 | s930 | s937 | s940 | s941 | s948
s959 | t10281 | t10700 | t11166 | t11710 | t12039 | t12044
t12046 | t12047 | t12048 | t12049 | t12052 | t12053 | t12054
t12055 | t12057 | t12060 | t12064 | t12065 | t12066 | t12067
t12143 | t12244 | t12412 | t12477 | t12479 | t12485 | t12487
t12492 | t12493 | t12496 | t12795 | t12840 | t12841 | t12842
v2124 | v2208 | v2531 | v2533 | v2644 | v2648 | v2652
v2731 | v2732 | v2788 | v2892 | v2942 | v2943 | v2945
v3039 | v3108 | v3127 | v3140 | v3211 | v3222 | v3223
v3224 | v3225 | v3227 | v3292 | v3294 | v3376 | v3379
v3380 | v3383 | v3384 | v3385 | v3393 | v3396 | v3426
v3429 | v3450 | v3456 | v3468 | v3497 | v3501 | v3506
v3507 | v3518 | v3527 | v3544 | v3546 |  |
Table 1: Names of hyperbolic Mom-4s.

######  Theorem 1.

Table 1 constitutes the complete list of hyperbolic Mom-4s.

###### Proof.

Put the Python modules unhyp and mom in one directory also containing the data
from [4], which here is called mm4.txt. Then from a bash prompt, run

    python mom.py mm4.txt > hyp4s

One finds that hyp4s has 138 lines, each of which is a distinct name of a
cusped manifold on a census, either the original SnapPea census or
Thistlethwaite’s more recent census of manifolds with eight tetrahedra.
Therefore, Conjecture 5.3 from [4] is correct. ∎

Of course, now we should discuss what is in these modules.

######  Remark 2.

The author would like to thank Tao Li for helpful discussions about normal
surface theory and Seifert fiberings, and especially thank Dave Futer for
pointing out an error in a previous version of the paper.

##  2 Background

Conventions. All manifolds herein are assumed to be compact and piecewise-
linear. All maps between these are assumed to be piecewise-linear and proper
(that is, such that the preimage of compacta are again compacta). In
particular, all homeomorphisms are piecewise-linear with piecewise-linear
inverses. (End Conventions.)

Thurston’s hyperbolicity theorem for Haken manifolds merits a succinct
formulation. Shoving some complications from the original theorem into
definitions and restricting attention to manifolds with nonempty torus
boundary yields

######  Theorem 3.

Let $M$ be a compact orientable 3-manifold with nonempty boundary consisting
of tori.

$M$ is hyperbolic with finite volume if and only if $M$ has no faults.

The above uses the following definitions.

######  Definition 4.

A manifold is _hyperbolic_ when its interior admits a complete hyperbolic
metric—a complete Riemannian metric of constant negative curvature.

######  Definition 5.

Let $s$ be an embedding of a manifold into a connected manifold $M$. By abuse
of notation, also let $s$ denote the image of $s$ in $M$. Suppose $s$ has
codimension 1. Pick a metric on $M$ compatible with its p.l. structure, and
let $M^{\prime}$ be the path-metric completion of $M\smallsetminus s$.

When $M^{\prime}$ is disconnected, $s$ _separates_ $M$.

When $M^{\prime}$ has two connected components $N,N^{\prime}$, $s$ _cuts off
$N$ from $M$_, or, if $M$ is understood from context, _$s$ cuts off $N$_.

If $N$ is homeomorphic to some common 3-manifold $X$, $s$ _cuts off an $X$_;
if, in addition, $N^{\prime}$ is not homeomorphic to $X$, $s$ cuts off _one_
$X$.

######  Definition 6.

A properly embedded surface $s$ in an orientable 3-manifold $M$ is a _fault_
when $\chi(s)\geq 0$ and it satisfies one of the following:

  * •

$s$ is nonorientable.

  * •

$s$ is a sphere which does not cut off a 3-ball.

  * •

$s$ is a disc which does not off one 3-ball.

  * •

$s$ is a torus which does not cut off a $T^{2}\times I$, and does not cut off
a $\partial$-compressible manifold.

  * •

$s$ is an annulus which does not cut off a 3-ball, and does not cut off one
solid torus.

###### Sketch of Thm. 3’s proof..

This is a corollary of common knowledge surrounding Thurston’s hyperbolization
theorem for Haken manifolds. Specifically, it’s commonly known that an
irreducible, $\partial$-incompressible, geometrically atoroidal 3-manifold
with nonempty boundary consisting of tori is either hyperbolic or Seifert-
fibered, where “hyperbolic” means “admits a complete hyperbolic metric.” All
Seifert-fibered spaces with at least two boundary components admit essential
tori, which are faults. A Seifert-fibered space with one boundary component
may admit no essential tori. In this case, the base orbifold $\Sigma$ is a
disc with at most two cone points. Let $\alpha$ be a properly embedded arc
which separates $\Sigma$ into discs with at most one cone point each; then the
vertical fiber over $\alpha$ is an annulus fault. Hence all Seifert-fibered
spaces with nonempty boundary admit faults.

Consequently, a compact orientable 3-manifold with nonempty boundary
consisting of tori which admits no faults is irreducible,
$\partial$-incompressible, Haken, and geometrically atoroidal, and it admits
no annulus faults. So it must be hyperbolic.

In fact, Thurston proved something more, namely that unless this manifold is
$T^{2}\times I$, then its metric has finite volume. Now, $T^{2}\times I$
admits faults—non-separating annuli, in fact. Since we assumed the manifold
had no faults, its metric must have finite volume.

Conversely, hyperbolic 3-manifolds of finite volume admit no orientable
faults—they have no essential spheres, no compressing discs, no incompressible
tori which aren’t $\partial$-parallel, and no annuli which are both
incompressible and $\partial$-incompressible. Finally, orientable hyperbolic
3-manifolds of finite volume don’t admit any faults at all, since they admit
no properly embedded nonorientable surfaces of nonnegative Euler
characteristic. ∎

Having finished this first reformulation, we note the following theorems from
normal surface theory.

######  Theorem 7.

Let $T$ ideally triangulate a compact orientable 3-manifold $M$. Then $M$ has
a closed fault precisely when $T$ has a fundamental normal fault.

######  Theorem 8.

Let $T$ finitely triangulate an irreducible, $\partial$-incompressible,
geometrically atoroidal 3-manifold $M$ with nonempty boundary consisting of
tori.

  1. 1.

$M$ has a fault if and only if $T$ has a vertex Q-normal annulus fault.

  2. 2.

If $M$ has at least two boundary components, then $M$ has a fault if and only
if $T$ has a non-separating vertex Q-normal annulus fault.

The last section contains proofs of these statements.

The reader need know little about the definition of the adjectives, except the
following: for any ideal triangulation, its fundamental normal surfaces are a
finite computable set, and likewise the vertex Q-normal surfaces of a finite
triangulation form a finite computable set.

In particular, one may put all the fundamental normals or vertex Q-normals
into a finite list and iterate a test over this list—say a test for faults—and
guarantee termination for this iteration.

Theorems 3, 7, and 8 together yield the following useful results amenable to
computer implementation.

######  Corollary 9.

Let $M$ be a compact orientable 3-manifold with nonempty boundary consisting
of tori.

Let $T,T^{\prime}$ triangulate $M$ ideally and finitely, respectively.

$M$ is hyperbolic precisely when $T$ has no fundamental normal closed fault,
$T^{\prime}$ has no disc fault, and $T^{\prime}$ has no vertex Q-normal
annulus fault.

######  Corollary 10.

The last condition in Corollary 9 can be relaxed to having no non-separating
vertex Q-normal annulus fault in case $|\partial M|\geq 2$.

Therefore, assuming $T$ is an ideal triangulation of a compact orientable
3-manifold $M$ with nonempty boundary consisting of tori,

    l := list of fundamental normal surfaces in T
    for surf in l:
      if surf is fault:
        return False
    T’ := truncation of T to finite triangulation
    if T’ has a compressing disc:
      return False
    l’ := list of vertex Q-normal surfaces in T’
    for annulus in l’:
      if M has at least two boundary tori:
        if annulus is non-separating:
          return False
      else:
        if annulus is fault:
          return False
    else:
      return True

describes an algorithm determining whether or not $M$ is hyperbolic.

Of course, this algorithm depends upon

  * •

enumerating fundamental normal surfaces of ideal triangulations;

  * •

truncating ideal triangulations into finite triangulations;

  * •

the predicate “has a compressing disc”;

  * •

enumerating vertex Q-normal surfaces of finite triangulations;

  * •

the predicate “is non-separating annulus”; and

  * •

the predicate “is fault.”

All but the last two are already described in the existing literature and
implemented conveniently in Regina.

The relevant tests and algorithms for detecting non-separating annuli are in
Regina already—calculating Euler characteristic, cutting along a surface, and
determining whether or not a manifold is connected.

The relevant tests for faultiness (all but the last of which are in Regina)
are

  * •

“is a 3-ball”

  * •

“is $\partial$-compressible”

  * •

“is a solid torus”, and

  * •

“is $T^{2}\times I$”.

We can notice first that admitting a non-separating annulus is a necessary
condition for being $T^{2}\times I$. We note that a further necessary
condition for being $T^{2}\times I$ is that splitting along any such annulus
is a solid torus. Now, if a 3-manifold $M$ split along a non-separating
annulus is a solid torus, then $M$ is a Seifert fibering with base orbifold an
annulus or Möbius band with at most a single cone point, i.e. $M=M(0,2;r)$ or
$M=M(-0,1;r)$ for some $r\in\mathbb{Q}$. In the latter case, $M$ has only one
boundary component, so it cannot possibly be $T^{2}\times I$. Thus we may
restrict our attention to the case $M=M(0,2;r)$. Recall the following results
about Seifert fiberings:

######  Proposition 11 ([6], 2.1).

Every orientable Seifert fibering is isomorphic to one of the models $M(\pm
g,b;s_{1},\ldots,s_{k}).$ Any two Seifert fiberings with the same $\pm g$ and
$b$ are isomorphic when their multisets of slopes are equal modulo 1 after
removing integers, assuming $b>0$.

######  Theorem 12 ([6], 2.3).

Orientable manifolds admitting Seifert fiberings have unique such fiberings up
to isomorphism, except for $M(0,1;s)$ for all $s\in\mathbb{Q}$ (the solid
torus), $M(0,1;1/2,1/2)=M(-1,1;)$ (not the solid torus), and three others
without boundary.

######  Proposition 13.

Among manifolds of the form $M(\pm 0,2;r)$, only $T^{2}\times I$ has all Dehn
fillings being solid tori.

###### Proof.

Plainly $T^{2}\times I$ has this property.

Suppose $M(0,2;r)$ is not $T^{2}\times I$. Then by Proposition 11 and Theorem
12, $r\notin\mathbb{Z}$. We wish to show that $M(0,2;r)$ admits some Dehn
filling which is not a solid torus. Let $s,s^{\prime}$ be two slopes differing
mod 1. Then $M(0,1;r,s)$ and $M(0,1;r,s^{\prime})$ are Dehn fillings of
$M(0,2;r)$. They are not homeomorphic, by Theorem 12 and the fact that
$r\notin\mathbb{Z}$. So one of them is not a solid torus. ∎

It is quite easy to compute slopes differing mod 1 after simplifying the
cusps’ induced triangulations.

######  Proposition 14.

In a triangulation of the torus $T^{2}$ by one vertex, three edges, and two
faces, for any nontrivial element $g$ of $H_{1}(T^{2})$, the edges represent
homology classes not all equivalent mod $g$.

###### Proof.

Suppose $v,w,x\in H_{1}(T^{2})$ and $v+w=x$. Let $\equiv$ denote equivalence
in $H_{1}(T^{2})\mod g$. Then

$\displaystyle v\equiv x$ $\displaystyle\Rightarrow$ $\displaystyle v+w\equiv
x+w$ $\displaystyle=$ $\displaystyle\qquad\\{v+w=x\\}$ $\displaystyle x\equiv
x+w$ $\displaystyle=$ $\displaystyle 0\equiv w;$

assuming $v\equiv w$ then implies $v$ and $x$ also are $0\mod g$. Therefore
they are all multiples of $g$. But $H_{1}(T^{2})$ is not cyclic. So $v,w,x$
cannot generate $H_{1}(T^{2})$.

Now, one may pick homology classes $v,w,x$ representing the three edges such
that $v+w=x$. These generate $H_{1}(T^{2})$. Therefore, by the above argument,
they cannot satisfy $v\equiv w\equiv x\mod g$ for any element $g$. ∎

######  Corollary 15.

The following pseudocode describes an algorithm determining whether or not a
compact, orientable, 3-manifold $M$ with nonempty boundary consisting of tori
is $T^{2}\times I$:

    if number of boundary components of M is not 2:
      return False
    if M splits along no annulus into a solid torus:
      return False
    let D be M’s triangulation
    let T be a boundary component of M
    let tr(T,D) be the triangulation on T induced from D
    change D so tr(T,D) has 2 faces, 3 edges, and 1 vertex
    if M filled along one of the 3 edges’ slopes is not a solid torus:
      return False
    else:
      return True

###### Proof.

Suppose $M$ is $T^{2}\times I$. Then the first if-statement doesn’t activate;
nor does the second, for $M$ splits along an annulus into a solid torus. Also,
$M$ filled along any edge’s slope whatever is a solid torus, so the second if-
statement doesn’t activate. So the algorithm returns True.

Suppose instead that $M$ is not $T^{2}\times I$. If the first if-statement
activates, the algorithm correctly returns False. If $M$ splits along no non-
separating annulus into a solid torus, then the algorithm correctly returns
False. Otherwise, $M$ does so split. At this point in the algorithm, we may
assume (since the first if-statement didn’t activate) that $M$ has exactly two
boundary components. Therefore $M=M(0,2;r)$ for some
$r\in\mathbb{Q}\setminus\mathbb{Z}$. The algorithm then establishes that $M$’s
triangulation induces a minimal triangulation on the boundary component $T$.
By Proposition 14, the edges represent at least two different slopes modulo 1.
Therefore, by Proposition 11 and Theorem 12, the Dehn fillings of $M$ along
these slopes are not all homeomorphic. In particular, one of them is not a
solid torus. Therefore, the if-statement activates, and the algorithm
correctly returns False. ∎

It remains to describe

  * •

splitting along a non-separating annulus into a solid torus,

  * •

changing a triangulation to induce a minimal triangulation on a cusp, and

  * •

filling along a slope in a simplified cusp.

######  Proposition 16.

The following pseudocode describes an algorithm implementing the first item:

    for every vertex Q-normal surface s in M:
      if s is a non-separating annulus:
        if M splits along s into a solid torus:
          return True
    return False

###### Proof.

Suppose $M$ doesn’t split along a non-separating annulus into a solid torus.
Then not both of the if-statements can activate, so the for loop ends without
returning, and so the algorithm correctly returns False.

On the other hand, if $M$ does split along a non-separating annulus into a
solid torus, then $M$ is of the form $M(0,2;r)$. By Lemma 25, every finite
triangulation of such a manifold admits a non-separating Q-vertex annulus.
Hence the if-statements eventually activate, and the algorithm correctly
returns True. ∎

Now for the next item, simplifying cusps. One may find a nice algorithm in
SnapPea for doing this, a special, simpler case of which is presented
here.111SnapPea’s approach to cusp filling is reminiscent of Jaco and
Rubinstein’s _layered-triangulations_ , developed in [7]. We use the following
terminology.

######  Definition 17.

First, suppose $M$ is finitely triangulated. Let $T$, $T^{\prime}$ be boundary
triangles adjacent along an edge $e$. Orient $e$ so that $T$ lies to its left
and $T^{\prime}$ to its right. Let $\Delta$ be a fresh tetrahedron, and let
$\tau$, $\tau^{\prime}$ be boundary triangles of $\Delta$ adjacent along an
edge $\eta$. Orient $\eta$ so that $\tau$ lies to its left and $\tau^{\prime}$
to its right. Without changing $M$’s topology we may glue $\Delta$ to $T$ by
gluing $\eta$ to $e$, $\tau$ to $T^{\prime}$ and $\tau^{\prime}$ to $T$. This
is called a _two-two_ move.

In the above definition, the edge $\eta^{\prime}$ opposite $\eta$ in $\Delta$
becomes a boundary edge of the new finite triangulation.

######  Definition 18.

We say $e$ is _embedded_ when its vertices are distinct. We say $e$ is
_coembedded_ when $\eta^{\prime}$ as defined above is embedded. Equivalently,
$e$ is coembedded when the vertices in $T,T^{\prime}$ opposite $e$ are
distinct.

Given a boundary edge $e$ between two boundary triangles $T$ and $T^{\prime}$,
one may glue $T$ to $T^{\prime}$ and $e$ to itself via a valid, orientation-
reversing map from $T$ to $T^{\prime}$. This identification we call “folding
along $e$”. (Weeks, in the SnapPea source code, calls this a “close-the-book”
move.) This gluing will change the topology of $M$ when the vertices opposite
$e$ in $T$ and $T^{\prime}$ are the same vertex. Conversely, when these
vertices are distinct, the folding preserves the topology. In other words,
folding along $e$ preserves topology if and only if $e$ is coembedded.

Notice that folding along a coembedded edge decreases the number of boundary
triangles, and performing a two-two move on an embedded edge produces a
coembedded edge and preserves the number of boundary triangles. Therefore, the
following while-loops terminate, using number of boundary triangles as a
variant function:

    while there’s an embedded boundary edge e:
      do a two-two move on e
      while there’s a coembedded boundary edge f:
        fold along f

The obvious postcondition of the outer while loop is that there is no embedded
boundary edge. Since the boundary is still triangulated, this is equivalent to
each boundary component having only one vertex on it. Since each boundary
component is a torus, $V-E+F=0$. Now, $V=1$, and since the cellulation is a
triangulation, $3*F=2*E$.

$\displaystyle 1-E+F$ $\displaystyle=0$ $\displaystyle 2-2*E+2*F$
$\displaystyle=0$ $\displaystyle 2-3*F+2*F$ $\displaystyle=0$ $\displaystyle
2-F$ $\displaystyle=0$ $\displaystyle 2$ $\displaystyle=F,$

and there are only two triangles and three edges.

The routine in SnapPea is more complicated because, rather than filling in a
cusp any old way, SnapPea wants to make sure the filling compresses some given
slope in the cusp.

In conclusion,

######  Proposition 19.

The following pseudocode changes a finite triangulation $D$ with boundary
consisting of tori so that $D$ induces a minimal triangulation on every
boundary component:

    while D has an embedded boundary edge e:
      do a two-two move on e
      while D has a coembedded boundary edge f:
        fold along f

###### Proof.

See above discussion. ∎

Finally,

######  Proposition 20.

Assuming a triangulation $D$ has a torus boundary component $T$ and induces a
minimal triangulation thereon, the following pseudocode determines whether
folding along one of the edges in $T$ yields a solid torus:

    for each edge e in T:
      let N be D folded along e
      if N is a solid torus:
        return True
    return False

###### Proof.

Omitted. ∎

This concludes the present sketch of an algorithm to determine hyperbolicity
of a compact, orientable 3-manifold with nonempty boundary consisting of tori.
Both literate and raw implementations of this algorithm as a Regina-Python
module unhyp reside at [5]. Also available at [5] is a Regina Python module
mom for interpreting Milley’s data as manifolds in Regina.

##  3 Normal Surface Corollaries

###### Proof of Thm. 7.

This is just breaking down the definition of closed fault and using the
following classical theorems of normal surface theory. The following are such
theorems from [9], with implications trivially spruced up to equivalences. We
also abbreviate “fundamental normal” to “fundamental.”

######  Theorem 21 ([9], 4.1.12).

Let $M$ be an orientable ideally triangulated 3-manifold.

  * •

$M$ has a projective plane if and only if $M$ contains a fundamental
projective plane.

  * •

$M$ has an essential222Here, “essential” means “does not bound a 3-ball”; see
[9], Remark 3.3.3. sphere if and only if $M$ contains either a fundamental
sphere or a fundamental projective plane.

So $M$ has a closed fault of $\chi>0$ when it has a fundamental closed such
fault.

Now for closed faults of $\chi=0$. The next theorem is more complicated than
we need.

######  Theorem 22 ([9], Lemma 6.4.7).

Let $(M,\Gamma)$ be an orientable irreducible triangulated 3-manifold.
$(M,\Gamma)$ contains an essential torus if and only if $(M,\Gamma)$ contains
either a fundamental essential torus or a normal essential torus which double
covers a fundamental Klein bottle.

We can ignore the $\Gamma$ since this is a theorem about closed surfaces.
(Those not satisfied with this assertion may take comfort in the remark on p.
234 of [9] after the definition of “essential.”) That is to say,

######  Corollary 23.

Let $M$ be an orientable irreducible triangulated 3-manifold. $M$ contains an
essential torus when $M$ contains either a fundamental essential torus or a
normal essential torus which double covers a fundamental Klein bottle.

Now $M$ contains a closed fault of $\chi=0$ when either it contains a $T^{2}$
fault or it contains an embedded $K^{2}$. The former case is equivalent to $M$
containing a fundamental $T^{2}$ or an essential double cover of a fundamental
normal $K^{2}$. The latter case is not much more subtle. Just note that Lemma
6.4.7 is proved, in part, by showing that a minimal-edge-degree injective
$K^{2}$ is fundamental. Such a $K^{2}$ exists if and only if $M$ admits an
injective $K^{2}$.

Therefore, $M$ contains a closed fault of $\chi=0$ if and only if it contains
a fundamental such fault. Consequently, $M$ contains a closed fault if and
only if it contains a fundamental closed fault. ∎

Regina takes care of finding disc faults for us already, so it remains to
examine annulus faults. Before the proof proper, let’s explain why we use
Q-normal coordinates and non-separating annuli.

One may certainly derive theorems for annulus faults as above, and indeed
Matveev does. However, to use these theorems on an ideal triangulation to find
annulus faults, one must truncate the ideal triangulation to get a finite
triangulation first. Even after simplifying the result, one gets many more
tetrahedra in the triangulation, and the number of fundamental surfaces
increases greatly.

In the case of a finite triangulation, there is an alternative to usual normal
coordinates, viz. Q-normal or Q-normal coordinates. The space of Q-normal
surfaces is smaller than that of normal surfaces; it excludes obviously
trivial surfaces. So we use that here, because it is faster than fundamental
normal surface enumeration.

Now, one may test whether an annulus is a fault or not. However, if the
annulus does not separate, this entails “isSolidTorus” and “isBall” tests,
which are costly. So it would be great if we could skip them altogether. And,
as we shall show, indeed we can, if $|\partial M|\geq 2$.

###### Proof of Thm. 8.

Let $M$ be a compact orientable 3-manifold with nonempty boundary consisting
of tori.

By Thurston’s hyperbolization theorem, if $M$ is irreducible,
$\partial$-irreducible, and geometrically atoroidal, then it admits a
homogeneous geometry. This is either hyperbolic, Euclidean, spherical,
Seifert-type, or solve. $\partial M$, and hence $M$ itself, has infinite
$\pi_{1}$, so the geometry is not spherical. By theorem 2.11 of [2],
solvegeometric structures either fiber over $S^{1}$ with $T^{2}$ fiber, which
fibers are faults, or are line bundles over bases $T^{2}$, $K^{2}$, an
annulus, a Möbius strip, or a disc (Bonahon calls this disc a _plane_), which
bases are faults. $M$ has no faults, so it doesn’t admit solvegeometry.
Finally (for now), note that if $M$ admits a Euclidean structure, then by
theorem 2.7 of [2], either $M$ is Seifert-fibered, or is an orientable disc
bundle over $S^{1}$, which is a solid torus (which admits a Seifert fibering),
or is a ball. $M$ is not a ball, since it has torus boundary. In conclusion,
then, either $M$ is hyperbolic or it admits a Seifert fibering.

Let $M$ have a Seifert fibering with base orbifold $\Sigma$. Since by
assumption $M$ admits no torus faults (this is what geometric atoroidality
means), it admits in particular no vertical torus faults. Hence there are no
essential loops in $\Sigma$. Therefore $\Sigma$ is a sphere with $c$ cone
points and $b$ boundary components such that $b+c\leq 3$. We say $M$ is
_medium_ Seifert-fibered, or is a medium Seifert fibering.

We have two consequents to prove.

  1. 1.

Without further assumptions on $M$ we are to prove that $M$ admits a vertex
Q-normal annulus fault. It will plainly suffice to prove the following lemma.

######  Lemma 24.

Let $M$ be a medium Seifert fibering with nonempty boundary.

Every finite triangulation of $M$ admits a vertex Q-normal annulus fault.

Then either $M$ is hyperbolic, in which case it admits no annulus faults
whatever, or $M$ is medium Seifert-fibered with nonempty boundary, in which
case the lemma applies, and $T$ admits a Q-vertex annulus fault.

  2. 2.

In case $|\partial M|\geq 2$, it suffices as above to prove a similar lemma,
viz.

######  Lemma 25.

Let $M$ be a medium Seifert fibering with at least two boundary tori.

Every finite triangulation of $M$ admits a non-separating vertex Q-normal
annulus fault.

∎

To prove these lemmata, we should at least recall what _vertex_ and _Q-normal_
all mean. The reader unfamiliar with normal surface theory should now go read
section 1 of [8]. Let $T$ finitely triangulate a compact orientable 3-manifold
$M$. Now, Haken’s normal surface equations are homogeneous and linear, with
some linear inequalities tacked on at the end. Therefore the solution space
can be projectivized, which in [8] is denoted by $\mathcal{P}$ or
$\mathcal{P}_{\mathcal{T}}$ when being explicit about the given triangulation.
Because the equations and inequalities are linear, this solution space is a
convex polytope in $PR^{7\cdot t-1}$, where $t$ is the number of tetrahedra in
$T$, and $R$ is one’s field of choice, here $\mathbb{Q}$. If $S$ is an
embedded normal surface, then it projects to a point on this polytope. The
smallest face of $\mathcal{P}$ containing $S$ is called the _carrier_ of $S$,
written $\mathcal{C}(S)$. The vertices of $\mathcal{P}$ may or may not be
projections of embedded normal surfaces. If a vertex $v$ is such a projection,
then let $s(v)$ be that surface such that for all normal surfaces $\sigma$
projecting to $v$ and integers $k>0$, $k\cdot\sigma=s(v)$ if and only if
$k=1$. Then $s(v)$ is called a _vertex surface_ , and represents an embedded
surface in $M$.

It turns out that many vertex surfaces are topologically interesting, but some
more interesting than others. In particular, boundary-parallel surfaces are
only mildly interesting from our point of view. Therefore, Q-normal
coordinates are more commensurate with our needs. Q-normal coordinates,
moreover, only lie in $PR^{3\cdot t-1}$! In Q-normal coordinates, one only
records the quads occurring in a normal surface, throwing away the triangle
information. In [11] one finds that throwing away these triangle coordinates
forces one to disregard vertex-linking surfaces, which of course we would like
to do. This is the content of

######  Theorem 26 ([11], Thm. 1).

Every normal surface yields an admissible solution to the Q-matching
equations. Conversely, an admissible solution to the Q-matching equations is
yielded by a _unique_ normal surface with no vertex-linking (“trivial”)
components.

That’s enough to begin the proofs.

###### Proof of Lemma 24.

Suppose $M$ is a medium Seifert fibering with nonempty boundary, and suppose
$T$ finitely triangulates $M$.

$M$’s base orbifold has at least one boundary component $S$. Suppose there
were no essential simple arc from $S$ to itself. Then $M$ has a disc with no
cone points for its base orbifold, and $M$ is a solid torus. But solid tori
are $\partial$-compressible, contrary to our assumptions on $M$. Hence there
is an essential simple arc from $S$ to itself.

The vertical fiber $a$ over this arc is an annulus. $a$ is essential, so it
isotopes to a normal annulus. Let $A$ be such an annulus such that the number
of intersections of $A$ with the 1-skeleton of $T$ is minimal among normal
surfaces isotopic to $a$. That is, let $A$ have least weight in its isotopy
class.

Now, every vertex surface in $\mathcal{C}(A)$ is an essential annulus or an
essential torus (Cor. 6.8, [8]). There are no essential tori, by assumption.
Consequently, each vertex surface in $\mathcal{C}(A)$ is an essential annulus.
The proof of Theorem 2 in [11] shows that every two-sided vertex surface in
$\mathcal{C}(A)$ is isotopic to a Q-vertex surface. Thus $T$ admits some
essential Q-vertex annulus. ∎

###### Proof of Lemma 25.

Suppose $M$ is a medium Seifert fibering with at least two boundary tori, and
suppose $T$ is a finite triangulation of $M$.

$M$’s base orbifold now, by assumption, has at least two boundary components.
Up to isotopy, there is a unique essential simple arc running between them.
Let $a$ be a vertical fiber over such an arc, a non-separating annulus. Since
$a$ is non-separating, it is essential. So it isotopes to a normal annulus.
Let $A$ be a least weight such annulus. Again, every vertex surface in
$\mathcal{C}(A)$ is an essential annulus (or an essential torus, of which
we’ve assumed there are none). Furthermore, every such essential annulus is
isotopic to a Q-vertex surface, as above. So we just need a _non-separating_
vertex annulus in $\mathcal{C}(A)$.

If there is a horizontal vertex annulus in $\mathcal{C}(A)$, then that is a
non-separating vertex annulus in $\mathcal{C}(A)$.

Otherwise, $A$ is a sum of some vertical vertex annuli in $\mathcal{C}(A)$.

The geometric sum (see [9], pp. 136–7 or [8], Fig. 2.1, p. 363) on the
boundary just resolves intersections $\times\to\ \asymp$, which preserves
homology mod 2. Therefore, for all normal surfaces $S,S^{\prime}$,
$\partial(S+S^{\prime})\equiv\partial(S)+\partial(S^{\prime})$ in
$H_{1}(\partial M;\mathbb{Z}/2\mathbb{Z})$.

The boundaries of separating annuli in $M$ are 0 in $H_{1}(\partial
M;\mathbb{Z}/2\mathbb{Z})$, but $\partial A$ is not 0 in this homology. So $A$
is not a sum of separating annuli. Consequently one of the summands must be
non-separating, and be a non-separating vertex annulus in $\mathcal{C}(A)$. ∎

##  4 Further Directions

The algorithm presented here is convenient for demonstrating non-
hyperbolicity, but it only works for cusped manifolds. Closed fault-testing is
already implemented, but the absence of closed faults in a closed 3-manifold
only implies that said 3-manifold is either hyperbolic or small Seifert-
fibered. Tao Li and, independently, J. Hyam Rubinstein have given algorithms
for locating a vertical torus in such a space, cutting along which torus
yields a solid torus and a cusped small Seifert fibering, the detection of
which are implemented. So the time is ripe to implement a rudimentary
algorithm for hyperbolicity testing for arbitrary orientable compact
3-manifolds of Euler characteristic 0.

## References

  * [1] Ian Agol, _The minimal volume orientable hyperbolic 2-cusped manifolds,_ Proc. Amer. Math. Soc. 138 (Oct. 2010), no. 10, 3723–32.
  * [2] F. Bonahon, _Geometric structures on 3-manifolds_ , Chapter 3 from _Handbook of Geometric Topology_ , ed. R. J. Daverman and R. B. Sher, Elsevier, New York, 2002.
  * [3] B. A. Burton, R. Budney, W. Pettersson, et al., _Regina : software for 3-manifold topology and normal surface theory_, http://regina.sourceforge.net/ , 1999–2014.
  * [4] David Gabai, Robert Meyerhoff, and Peter Milley, _Mom technology and volumes of hyperbolic 3-manifolds_ , Comment. Math. Helv. 86 (2011), 145–188.
  * [5] https://www2.bc.edu/robert-c-haraway/code.html
  * [6] A. Hatcher, _Notes on 3-manifold topology_ , available at http://www.math.cornell.edu/$\sim$hatcher/3M/3Mdownloads.html
  * [7] W. Jaco and J. H. Rubinstein, _Layered-triangulations of 3-manifolds_ , arXiv:/math/0603601
  * [8] W. Jaco and J. L. Tollefson, _Algorithms for the complete decomposition of a closed 3-manifold_ , Illinois J. of Math., 39 (Fall 1995), no. 3, 358–406.
  * [9] S. Matveev, _Algorithmic topology and classification of 3-manifolds_ , Springer-Verlag, New York, 2003.
  * [10] Peter Milley, _Minimum volume hyperbolic 3-manifolds_ , J. of Topology 2 (2009), 181–192.
  * [11] J. L. Tollefson, _Normal surface Q-theory_ , Pacific J. of Math., 183 (1998), no. 2, 359–374.