degree. Indeed, a sufficient condition for $l$-clique denseness is when all
vertices have degree at least $\gamma n$, for $\gamma>\frac{l-2}{2(l-1)}$
[81]. Hence, a class of graphs for which the LGZ algorithm could exhibit
quantum advantage will be when the degree of every vertex is at least $n-k$
for constant $k$, in which case the complement of the graph will have maximum
degree $k$, and so the Laplacian (6.4) will be $k$-local. Hamiltonian
simulation of local Fermionic operators is likely to be a less resource
intensive task on near-to-medium-term devices than simulation of general
sparse operators. For example, one can take an efficient Fermion-to-qubit
mapping (e.g. the Bravyi-Kitaev transform [17]) to obtain a $\log$-local qubit
operator $\hat{d}$ corresponding to the coboundary operator $d$. Hamiltonian
simulation of the $\log$-local qubit operator
$\hat{B}=(\hat{d}+\hat{d}^{\dagger})$, or of the Laplacian itself, can then be
implemented via Trotterization using no extra ancilla qubits. If we have
information about the underlying structure of the graph $G$, it is possible
that this simulation could be made even more efficient [82]. Moreover, since
we are interested only in the low-energy subspace of these operators, it is
possible that some recent results (e.g., [83]) regarding Hamiltonian
simulation within low-energy subspaces could be exploited to make the
simulation even more efficient. We leave these questions open as further work.

###  6.3 A VQE approach to TDA

The quantum algorithm described in the previous section suffers from a couple
of drawbacks. First, it is only efficient when the graph is clique dense,
which will likely restrict the family of graphs to which it can be applied.
Second, it computes only _normalized_ Betti numbers, and it is not entirely
clear that these quantities have any immediate practical application. In
particular, being able to estimate normalized $l$th Betti numbers up to
inverse-polynomial additive error only allows one to distinguish complexes
with very many $l$-dimensional holes from those with very few $l$-dimensional
holes, which again might limit the family of graphs to which this algorithm
can usefully be applied. In this section we propose an alternative quantum
approach to TDA via variational quantum algorithms that suffers from neither
of the above concerns, and argue that this is well motivated given the strong
connections between (co)homology and ground states of physical systems
outlined in this paper, and in particular the direct connection to the
aforementioned fermion hard-core model.

As discussed, task of performing topological data analysis amount to finding
ground states of the fermion hard-core model. Hence, if we expect variational
quantum algorithms to be useful for finding ground states of many-body systems
like the Fermi-Hubbard model, then it is reasonable to expect that they could
be useful for finding ground states of the fermion hard-core model, and
therefore also be useful for topological data analysis. In the short sections
that follow, we briefly describe the variational quantum eigensolver before
considering its applicability to finding ground states of the fermion hard-
core model and hence topological data analysis.

From a complexity-theoretic perspective, the $\QMA_{1}$-hardness, and
containment in $\QMA$, of the cohomology problem suggests that variational
approaches such as the variational quantum eigensolver (VQE) [84, 85] might be
promising candidates for tackling the problem, just as they are conjectured to
be for finding ground states of physical systems – a problem that is
$\QMA$-complete in general. In particular, solving the $k$-local cohomology
problem for the independence complex would have direct applications in
topological data analysis. In this context, the task would be to decide
whether or not a graph has a hole at some dimension $l$ (i.e. non-zero $l$th
Betti number), or even to find an example of such a hole (i.e. by finding an
$l$-cycle that is not an $l$-boundary). This solves a much harder problem than
estimating normalized Betti numbers, does not rely on any assumption regarding
the clique-density of the input graph, and might even find application in
persistent homology, where one must track holes across multiple complexes
[76]. In fact, the problem of deciding whether or not a particular Betti
number of a clique complex is non-zero was recently shown to be $\NP$-hard
[58], but is not known to be _in_ $\NP$ except for the special case of chordal
graphs. With an appropriate promise on the input (that the $l$th Laplacian has
a spectral gap above 0 when the $l$th cohomology is trivial), this problem is
in $\QMA$ as we showed in Section 4. If the problem remains $\NP$-hard under
this promise, then the complexity of the problem lies somewhere between $\NP$
and $\QMA$. Without this promise, the relaxed problem of estimating the
smallest eigenvalue of the $l$th Laplacian up to inverse-polynomial additive
error is in $\QMA$ as we showed in Section 3.2. In terms of topological data
analysis, we suspect that this latter problem is akin to finding “almost
holes” in the graph, analogous to finding small cuts of a graph by analyzing
the low-lying spectrum of the ordinary graph Laplacian, and will probably
still be useful for topological data analysis.

#### The variational quantum eigensolver (VQE).

Roughly, the VQE framework gives rise to algorithms that follow the following
structure. To find low-energy states of some Hamiltonian $H$, we first choose
a circuit ansatz: a parameterised quantum circuit $U(\bm{\theta})$ depending
on a collection of parameters $\bm{\theta}$; and some initial easy-to-prepare
state $\ket{\psi}$. Then we repeat the following until convergence, or some
other stopping criterion is met:

  1. 1.

Apply the circuit to the initial state to obtain
$U(\bm{\theta})\ket{\psi}=\ket{\psi(\bm{\theta})}$.

  2. 2.

Estimate the energy
$E(\bm{\theta})=\langle\psi(\bm{\theta})|H|\psi(\bm{\theta})\rangle$.

  3. 3.

Update the parameters $\bm{\theta}$ using some (classical) optimisation
method, in an attempt to minimise the energy $E(\bm{\theta})$.

Often these hybrid algorithms can be realised using far fewer resources than
full quantum algorithms, depending on how hard it is to implement the
variational quantum circuit and to measure the energy of a state constructed
by that circuit. Since we are concerned with finding states with a fixed
fermion number, it is possible that a circuit ansatz such as the number-
preserving ansatz from [86], which is a generalisation of the Hamiltonian
variational ansatz [87], could perform well. Inspired by adiabatic evolution,
this family of ansatze are similar to applying parameterised rotations by
terms in the Hamiltonian $H$, and are expected to perform well if one already
knows something about the structure of the true ground state (e.g. knowing the
ground state of an “easier” version of the Hamiltonian from which one could
adiabatically evolve to the full Hamiltonian). To implement a single “layer”
of the ansatz, and also to measure the energy at the end of the circuit, it is
often natural to group the terms of the Hamiltonian into sets of mutually
commuting operators. If one can decompose the Hamiltonian into a small number
of such sets, it can lead to shallower ansatz circuits and fewer measurements
required to estimate the energy. When dealing with very structured
Hamiltonians, often the number of terms in the decomposition can be very
small. For instance, for the Fermi-Hubbard Hamiltonian there is a natural
decomposition into only $5$ sets of commuting terms, leading to very shallow
circuit ansatze and a relatively small number of energy measurements [86, 88].

#### VQE for the fermion hard-core model.

There are two approaches we could take to design a variational quantum
algorithm for the fermion hard-core model: i) find low-energy states of the
Dirac operator $B=(d+d^{\dagger})$, or ii) find low-energy states of the
Laplacian/Hamiltonian $\Delta$. Note that option i) is only available to us
due to the supersymmetry of the underlying system.

When designing VQE algorithms for a particular model, there are a number of
considerations that must be taken into account. As mentioned above, two of
these are the complexities of the circuit ansatz and of the energy
measurements, which often rely on the number of sets of commuting operators
into which one can decompose the relevant operators. In Appendix C, we
consider a worst-case analysis of the number of sets into which we can
decompose the Dirac operator and Laplacian associated to the fermion hard-core
model for an arbitrary input graph $G=(V,E)$ with maximum degree $d$. We find
that the use of the Dirac operator rather than the Laplacian can lead to
saving a factor of $d$ in the size of the decomposition, which could lead to
lower-depth circuit ansatze and more efficient energy measurements. This
observation might prove useful in other applications, since it suggests that
the supersymmetry of a system might sometimes allow for slightly more
efficient variational algorithms for finding ground states.

For a VQE algorithm to be successful, it is often very useful to have some
prior knowledge about the ground states of the system. For instance, the
Hamiltonian variational ansatz for VQE was designed for systems for which we
know the ground state of an easier version of the Hamiltonian, which the
variational circuit can, in a sense, adiabatically evolve into the ground
state of the full Hamiltonian. In Section 6.1 we described what is already
known about ground states of the fermion hard-core model, but do not yet see
an obvious way in which this knowledge might aid the design of a VQE
algorithm. One promising approach could come from the introduction of the
“staggered” fermion hard-core model used in [89, 90].

In summary, we suggest that variational quantum algorithms could very well be
a promising approach for topological data analysis (or to the cohomology
problem more generally) on near-to-medium term devices, and that this
application is theoretically well-motivated in light of our results showing
$\QMA_{1}$-hardness and containment in $\QMA$ of the cohomology problem – a
result that generally suggests intractability of the problem even for
heuristic classical algorithms. Even if the near-term VQE-type algorithms fail
to be useful for this problem, it is likely that phase-estimation-based
algorithms would be successful, as they are predicted to be for many-body
problems in the future [91]. Moreover, the fact that $l$-dimensional holes of
clique complexes are in one-to-one correspondence with supersymmetric ground
states of the fermion hard-core model means that we might be able to leverage
existing knowledge about the properties of the hard-core model, and many-body
systems in general, to design efficient and useful quantum algorithms for the
problem of topological data analysis. Aside from TDA, it would likely be
interesting anyway to use quantum algorithms to find ground states of the
fermion hard-core model on simple lattices (e.g. the triangular lattice). In
our discussion above we also briefly considered the possibility of leveraging
supersymmetry in order to design slightly more efficient variational quantum
algorithms, which is something that could be of broader interest.

Finally, we note that there are a plethora of computational tools for
computing ground states of quantum many-body systems, including quantum Monte
Carlo and tensor networks [92], which might yield efficient _classical_
algorithms for topological data analysis. One immediate observation however,
in both cases, is that often these techniques are designed for systems on very
structured graphs (e.g. 2D lattices), and hence they might struggle to perform
well on more arbitrary input graphs. Understanding exactly when these
classical and quantum techniques might perform well is an interesting
question.

##  7 Discussion and Outlook

We have argued that the intersection of many-body physics, complexity theory,
and supersymmetry is a natural arena to study the complexity of problems in
homological algebra, in particular the (co)homology problem. Indeed, this
perspective reveals that the problems of deciding whether a (co)homology group
is nontrivial and of estimating its rank are intrinsically quantum mechanical
and serve as natural hard problems for various quantum complexity classes.
Precisely, we defined $k$-local Cohomology and showed that its complexity lies
between $\QMA_{1}$ and $\QMA$. Similarly, the complexity of an additive
approximation to (quasi) Betti numbers lies between $\mathsf{DQC1}$ and
$\BQP$.

These complexity results may come as a surprise at first, as the computational
problems we discuss are defined purely in the context of (co)homology and are
not manifestly quantum mechanical. As we have observed, however, these can be
seen as quantum mechanical when viewed as problems in supersymmetric quantum
mechanics, and relate to properties of the ground states of supersymmetric
Hamiltonians. Indeed, the complexity of $k$-local Cohomology ultimately
follows from the fact that the $k$-local Hamiltonian problem for
supersymmetric systems remains $\QMA$-complete, as shown in Section 3.

A set of interesting questions arises when considering simpler instances of
supersymmetric Hamiltonians. An obvious question, for instance, is whether
$\QMA$-hardness of the local Hamiltonian problem for systems with ${\cal N}=2$
SUSY is maintained for $2\leq k\leq 3$. One may also consider systems with
higher degrees of supersymmetry, ${\cal N}>2$, and study whether there is a
complexity transition at a certain value of ${\cal N}$ for each $k$. It is
often the case, at least in the context of supersymmetric QFTs, that beyond a
value of ${\cal N}$ the systems become so constrained that the entire class of
Hamiltonians is specified by a small set of parameters.323232An example is the
case of 4d QFTs with sixteen (Poincaré) supercharges, which are specified by a
choice of gauge group and one complex coupling constant. These and other
maximally supersymmetric systems are also often integrable. Although
integrability does not imply tractability in a computational sense (see, e.g.,
[93] for a counterexample) it would be interesting to consider the
computational hardness of these systems.  We note, however, that although
systems with extended supersymmetry can be easily constructed in continuum
quantum mechanics and quantum field theory, much less is known about spin
systems with extended supersymmetry (see however the ${\cal N}=4$ systems of
[94]). We also stress that although the Hamiltonian for which we have proven
hardness is local, in the sense that it is given by a sum of terms acting at
most on a constant number of sites, it is in general geometrically non-local.
It would be interesting to study whether the SUSY local Hamiltonian problem
remains hard for systems constrained by geometric locality or other physical
considerations. All this applies also to the problem of Betti number
estimation. Finally, it would be interesting to study the complexity of these
problems in the case of the fermion hard-core model of [16], especially in
relation to topological data analysis as discussed in Section 6. In
particular, if the local Hamiltonian problem remains $\QMA$-hard for this
model, as it is known to be for similar models like Fermi-Hubbard [29], then
this may imply $\QMA_{1}$-hardness of the cohomology problem for the
independence complex, and likely also $\mathsf{DQC1}$-hardness for QBNE of
clique complexes. The latter would imply that the LGZ algorithm cannot be
dequantized unless $\mathsf{DQC1}\subseteq\BPP$.

More generally, we note that our hardness constructions give a general
approach for mapping hard problems in Hamiltonian complexity into hard
problems in algebraic homology. This suggests that the approach could be
exploited to elucidate the complexity of problems beyond those considered in
this paper. In fact, this suggests defining new problems in computational
topology altogether, which are natural from a quantum Hamiltonian complexity
perspective. For instance, one may consider the standard $\QCMA$-complete
problem of deciding whether a local Hamiltonian has an “efficiently
describable” ground state, the $\QMA(2)$-complete problem of deciding if there
is a ground state with a particular tensor-product structure, or finding the
ground energy of stoquastic Hamiltonians. It would be interesting to determine
whether these additional constraints correspond to any natural constraints or
promises on the corresponding problems in homological algebra.

On the more practical side, as we discussed in Section 6, viewing the problem
of topological data analysis as the problem of finding the ground states of a
(supersymmetric) Hamiltonian suggests new approaches to this problem. In
particular, this opens the door to using modern techniques from quantum
chemistry for topological data analysis and cohomology problems more
generally, as long as these can be formulated in terms of a fermionic
coboundary operator acting on Fock space. Before the arrival of fault-tolerant
quantum computers, it may also be interesting to consider the application of
classical techniques (e.g. traditional tools for studying condensed-matter
systems, or even machine learning techniques [95]) for studying ground states
of many-body systems to topological data analysis or other (co)homological
problems.

## Acknowledgements

We are grateful to Ronald de Wolf and Kareljan Schoutens for helpful
discussions and feedback on an earlier version of this paper, and Vedran
Dunjko, Casper Gyurik, Ido Niesen, and Ian Marshall for useful discussions. CC
was supported by QuantERA project QuantAlgo 680-91-034. PMC is supported by
the European Union’s Horizon 2020 Research Council grant 724659 Massive-Cosmo
ERC–2016–COG and the STFC grant ST/T000791/1.

##  Appendix A Complexity Classes

In this section, we define the complexity classes $\QMA$, $\QMA_{1}$, and
$\mathsf{DQC1}$, which play a central role in our work.

We begin by defining the quantum complexity class $\QMA$. Loosely speaking,
this is the class of problems whose solution can be verified in polynomial
time by a quantum computer, a quantum analog of the class $\NP$. More
formally, the quantum complexity class $\QMA[c,s]$ is defined as follows:

######  Definition 2 ($\QMA{[c,s]}$).

A promise problem $A=(A_{\text{yes}},A_{\text{no}})$ is in $\QMA[c,s]$ if
there exists a polynomial-time quantum circuit (the “verifier”) $V_{x}$ for
any $n$-bit input string $x$ such that

  * •

If $x\in A_{\text{yes}}$, there exists a $\poly(n)$-qubit witness state
$\ket{w}$ such that $\Pr[V_{x}(\ket{w})=1]\geq c$,

  * •

If $x\in A_{\text{no}}$, then for any $\poly(n)$-qubit witness state
$\ket{w}$, $\Pr[V_{x}(\ket{w})=1]\leq s$.

That is, for a yes-instance, there must exist a quantum witness that causes
the verifier to accept with probability $\geq c$. Otherwise, the verifier must
reject all witnesses with probability $\geq 1-s$.

The parameters $c$ and $s$ are known as the completeness and soundness
parameters, respectively. The class $\QMA[2/3,1/3]$ is simply denoted by
$\QMA$ and is viewed as the quantum analogue of the class $\mathsf{NP}$. The
choice of $2/3$ and $1/3$ is arbitrary; in fact we have that
$\QMA=\QMA[1-1/\exp(n),1/\exp(n)]=\QMA[c,c-1/\poly(n)]$. A class that will be
relevant for us is the “perfect completeness” variant of $\QMA$,
$\QMA[1,1-1/\poly(n)]=\QMA_{1}$. Whether $\QMA_{1}=\QMA$ is a longstanding
open question in quantum complexity theory.

#### A comment on perfect completeness.

The notion of a perfect completeness complexity class introduces some nuances.
In particular, the notion of a “universal gate set” becomes tricky, and one
must fix a gate set in advance and require that any quantum circuits (i.e. the
verifier circuit in the case of $\QMA_{1}$) be constructed from this gate set.
It is not known whether the definition of $\QMA_{1}$ can be made independent
of the choice of gate set. To illustrate this point, consider a problem
contained in $\QMA_{1}$ with respect to some choice of universal gate set
$\mathcal{G}$, meaning that the verifier circuit, constructed out of gates
from $\mathcal{G}$, accepts any valid witness with probability 1. Now consider
moving to another universal gate set $\mathcal{G}^{\prime}$: of course the
verifier circuit can still be constructed out of gates from
$\mathcal{G}^{\prime}$, but only _approximately_ , even though the
approximation can be exponentially close to the target circuit. For perfect
completeness, however, this is not enough: we require that the circuit built
using $\mathcal{G}^{\prime}$ also accepts valid witnesses with certainty, and
not with “merely” a probability exponentially close to 1. Hence, the problem
would be considered to be in $\QMA_{1}$ with respect to $\mathcal{G}$, but
_not_ in $\QMA_{1}$ with respect to $\mathcal{G}^{\prime}$. In [60], Gosset
and Nagaj use a standard universal gate set
$\mathcal{G}=\\{\hat{H},T,CNOT\\}$, and for our purposes we choose this gate
set also for our definition of $\QMA_{1}$. For a detailed discussion of this
point, we refer the reader to [60].

Next we define the one-clean-qubit model, and its associated complexity class
$\mathsf{DQC1}$. Here, we are given access to a _fixed_ input

$\rho=\ket{0}\\!\bra{0}\otimes\frac{I_{n}}{2^{n}}$ (A.1)

consisting of a single qubit in a pure state $\ket{0}$, and $n$ qubits in a
maximally mixed state. We are allowed to apply a polynomial (in $n$) sized
circuit, without intermediate measurements, to this state, and then we can
measure the clean qubit. We are allowed to perform this procedure a polynomial
number of times, and the probability of obtaining a $0$ on the output is
considered the output of the model. The associated complexity class is called
$\mathsf{DQC1}$ and is defined as follows.

######  Definition 3 ($\mathsf{DQC1}$).

A language $L=(L_{\text{yes}}L_{\text{no}})$ is in $\mathsf{DQC1}$ if, for
every $r$-bit input $x\in L$, there exists a quantum circuit $U_{x}$ acting on
$n=\poly(r)$ qubits and consisting of $O(\poly(n))$ quantum gates, such that

  * •

If $x\in L_{\text{yes}}$,

$p_{\text{yes}}={\rm
Tr}\,\left[\left(U_{x}\left(\ket{0}\\!\bra{0}\otimes\frac{I}{2^{n-1}}\right)U_{x}^{\dagger}\right)\ket{1}\\!\bra{1}\otimes
I\right]\geq a$

  * •

If $x\in L_{\text{no}}$,

$p_{\text{yes}}={\rm
Tr}\,\left[\left(U_{x}\left(\ket{0}\\!\bra{0}\otimes\frac{I}{2^{n-1}}\right)U_{x}^{\dagger}\right)\ket{1}\\!\bra{1}\otimes
I\right]\leq b$

for $a-b\geq 1/O(\poly(n))$.

The promise gap between $a$ and $b$ means that, to solve any problem in
$\mathsf{DQC1}$, it is enough to estimate the “average acceptance probability”
of $U_{x}$, $p_{\text{yes}}$, up to inverse-polynomial additive error.

##  Appendix B $\mathsf{DQC1}$ Algorithm for Estimating Quasi Betti Numbers

Here we provide a proof of Corollary 1.

###### Proof.

Observe that the condition
$\frac{\dim(V^{l})}{2^{n}}=\Omega\left(\frac{1}{\poly(n)}\right)$ immediately
implies that $V^{l}$ is efficiently sample-able, and so the set of instances
satisfying this constraint is a subset of those in $\BQP$: if the space makes
up a polynomially large fraction of the entire $n$-qubit Hilbert space, one
can use rejection sampling to sample uniformly from $V^{l}$ by repeatedly
generating random $n$-bit strings until finding one that is contained in the
set $S^{l}$ of strings that give the computational basis states that span
$V^{l}$. Each string has at least a $1/\poly(n)$ probability of being in
$S^{l}$, and hence this rejection sampling takes polynomial time (and succeeds
with probability arbitrarily close to 1). We will show that in the case that
membership in $V^{l}$ can be tested using only logarithmically many ancilla
(qu)bits, this rejection sampling step can effectively be performed inside
$\mathsf{DQC1}$.

First, we note that if the co-boundary operator $d$ is $\log$-local, then the
(Hermitian) operator $A=(d+d^{\dagger})^{2}$ that we use for Hamiltonian
simulation will also be $\log$-local. Hamiltonian simulation of $\log$-local
Hamiltonians can be performed in polynomial time in $\mathsf{DQC1}$ using the
vanilla simulation technique of Trotterization ([96], Section 3.4). Hence, as
pointed out in [45], each step of the algorithm from Theorem 7 can be
performed in $\mathsf{DQC1}$, since the Hamiltonian simulation step requires
no clean ancilla qubits, and the phase estimation routine requires at most
$O(\log n)$ of them. The same error analysis applies in this case as in the
proof of Theorem 7, and so for the rest of the proof we will assume that each
part of the quantum algorithm works perfectly, and instead focus on the
problem of doing rejection sampling within the one-clean-qubit model. We will
refer to the circuit that performs steps 1 and 2 of the algorithm sketched in
the proof of Theorem 7 (i.e. phase estimation on (an approximation of)
$e^{iA}$) as $C$, and assume that it works perfectly – i.e. for an eigenstate
$\ket{\psi}$ of $A$, it outputs the corresponding eigenvalue $\lambda$
perfectly and with certainty.

In $\mathsf{DQC1}$, we have at our disposal $O(\log n)$ clean qubits (i.e. in
the state $\ket{0}$), and a maximally mixed register of $n$ qubits in the
state

$\rho=\frac{1}{2^{n}}\sum_{x\in\\{0,1\\}^{n}}\ket{x}\\!\bra{x}.$

The algorithm of Theorem 7 requires a maximally mixed state over the space
$V^{l}$, and so we need a way to emulate that input within $\mathsf{DQC1}$
given access to only the full maximally mixed state $\rho$. Provided there
exists a (classical) circuit to check whether a given bit-string is contained
in $S^{l}$ that uses no more than $O(\log n)$ workspace bits, we can perform
this check within the one clean qubit model itself. This allows us to build
the rejection sampling step into the $\mathsf{DQC1}$ algorithm, in one of two
ways.

If we are allowed to measure 2 qubits at the end of the computation, rather
than the usual single qubit, then we can perform the rejection sampling as a
post-selection step at the end of the computation. Such a model was considered
in, e.g., [97], although this model does not technically give rise to the same
complexity class $\mathsf{DQC1}$. Alternatively, we could estimate the
quantity $\frac{\dim(V^{l})}{2^{n}}$ classically (i.e. in $\BPP$), and
estimate the quantity $\frac{\tilde{\beta_{l}}}{2^{n}}$ using a
$\mathsf{DQC1}$ algorithm, where $\tilde{\beta_{l}}$ is used to denote the
number of eigenvalues of $A_{V^{l}}$ below the given threshold. By dividing
the latter by the former, and ensuring that the estimation accuracies are
chosen appropriately, we can obtain an estimate of
$\frac{\tilde{\beta_{l}}}{\dim(V^{l})}$, which will give us a solution to the
normalized quasi-Betti number estimation problem after errors from the circuit
are taken into account. The class $\mathsf{DQC1}$ is defined333333The accepted
definition of $\mathsf{DQC1}$ is quite hard to pin down. We take it to be the
set of problems solvable in polynomial time given access to a one-clean-qubit
quantum computer (which we can run non-adaptively) plus polynomial-time
probabilistic classical computation, which feels quite natural – after all,
one must have access to _some_ form of classical computation in order to, say,
post-process the results of a polynomial number of measurement outcomes in
order to output a final answer to the decision problem. This is the view taken
also by Brandão in [46] to be the set of problems solvable in polynomial time,
given access to a one-clean-qubit quantum computer plus polynomial time
classical post-processing, and hence this would be a true $\mathsf{DQC1}$
algorithm.

We begin by considering the first approach. As described in the proof of
Theorem 6, if we were to input the state
$\ket{0}\\!\bra{0}_{A}\otimes\rho_{V^{l}}$ to $C$, where the first register
consists of the $O(\log n)$ ancilla qubits used by the circuit, we would
obtain an approximation of a uniformly random eigenvalue of $A_{|V^{l}}$ in
the first register. We can append an extra ancilla qubit and use this as a
flag that we set to $\ket{1}$ when the eigenvalue in the first register is
$\leq b$, and $\ket{0}$ otherwise. Then the probability of measuring a 1 on
this qubit at the end of the computation will be equal to the fraction of
eigenvalues of $A_{|V^{l}}$ that are $\leq b$. However, since $\mathsf{DQC1}$
requires us to input the maximally mixed state $\rho$ over the full $n$-qubit
Hilbert space we will also obtain estimates of eigenvalues of the other parts
of $A$. To remedy this, we can attach another ancilla qubit and use it as a
flag that we set to $\ket{1}$ at the beginning of the computation only when
the state on the maximally mixed register is a computational basis state from
$V^{l}$ (here is where it is important that this checking only requires
$O(\log n)$ many “work” qubits, which we must provide as yet more clean
ancilla qubits). Finally, if we can measure the two flag qubits at the end of
the computation, then by keeping a count of the number of times we see a state
from $V^{l}$, and the number of times we see an eigenvalue $\leq b$, we can
estimate the fraction of eigenvalues smaller than $b$ out of all eigenvalues
of $A_{|V^{l}}$ using a Hoeffding bound.

Now we consider the second approach. We proceed in exactly the same way as
above, except we add a single extra ancilla qubit in which we store the
logical AND of the two flag qubits. We then measure this qubit at the end of
the computation as permitted by the canonical definition of $\mathsf{DQC1}$.
The circuit for this is shown in Figure 5, where we call the unitary for the
entire circuit $V$.

Figure 5: $\mathsf{DQC1}$ circuit for quasi Betti number estimation. The gate
“$\in V^{l}$?” is a gate that checks (using at most $O(\log n)$ ancillas)
whether a (computational basis) state is contained in $V^{l}$ or not, QPE is
quantum phase estimation (for some choice of unitary), and the “$\leq b$?”
gate checks whether the value stored in the phase register is smaller than $b$
or not.

Collecting the clean qubits into a single register $A$, the probability of
measuring a $1$ on the first qubit is

$\Pr[\text{measure }1]={\rm
Tr}\,\left[V\left(\ket{0}\\!\bra{0}_{A}\otimes\frac{I}{2^{n}}\right)V^{\dagger}(\ket{1}\\!\bra{1}\otimes
I)\right].$ (B.1)

Since $(d+d^{\dagger})^{2}$ is block-diagonal with each block acting on a
separate $V^{l}$, every one of its eigenvectors, and therefore those of $A$,
are either entirely supported within some $V^{l}$, or else not supported at
all. By expanding the equation above and taking the maximally mixed state to
be a uniform mixture over eigenvectors of $A$ (plus any extra orthogonal
vectors required to complete a basis for $\mathbb{C}^{2^{n}}$), we can see
that the probability of measuring a 1 at the end of the circuit is just the
probability that some input state $\ket{\psi}$ chosen from the ensemble is
contained in $V^{l}$ and that this state is an eigenstate of $A$ with
eigenvalue $\leq b$. Hence, the probability of measuring 1 at the end of the
computation, taken over all such states $\ket{\psi}$, is

$\displaystyle\Pr_{\ket{\psi}}[\text{measure }1]$ $\displaystyle=$
$\displaystyle\Pr_{\ket{\psi}}[\ket{\psi}\in
V^{l}]\cdot\Pr_{\ket{\psi}}[\langle\psi|A|\psi\rangle\leq b|\ket{x}\in V^{l}]$
(B.2) $\displaystyle=$
$\displaystyle\frac{\dim(V^{l})}{2^{n}}\cdot\frac{\tilde{\beta_{l}}}{\dim(V^{l})}=\frac{\tilde{\beta_{l}}}{2^{n}}.$
(B.3)

By repeating the computation a polynomial number of times, we can obtain an
estimate of this probability up to additive accuracy $1/\poly(n)$. Hence, we
can obtain a quantity

$\frac{\tilde{\beta_{l}}}{2^{n}}\pm\frac{1}{p(n)},$ (B.4)

for $p(n)$ some polynomial in $n$.

Next, we can classically estimate the fraction of all $n$-qubit (computational
basis) states that lie inside $V^{l}$ – i.e. estimate the relative dimension
of the space $V^{l}$. To do this we can sample $n$-bit strings uniformly at
random and check whether they satisfy the description of $V^{l}$ provided as
input. Once again, in polynomial time and by a Hoeffding bound we can obtain
an estimate

$\frac{\dim(V^{l})}{2^{n}}\pm\frac{1}{r(n)}$ (B.5)

for some polynomial $r(n)$. Finally, dividing the quantity in B.4 by the one
in B.5, we obtain an estimate

$\displaystyle\left(\frac{\tilde{\beta_{l}}}{2^{n}}\pm\frac{1}{p(n)}\right)\left(\frac{\dim(V^{l})}{2^{n}}\pm\frac{1}{r(n)}\right)^{-1}$
$\displaystyle=$
$\displaystyle\left(\frac{\tilde{\beta_{l}}}{2^{n}}\pm\frac{1}{p(n)}\right)\frac{2^{n}}{\dim(V^{l})}\left(1\pm\frac{2^{n}}{r(n)\dim(V^{l})}\right)^{-1}$
$\displaystyle=$
$\displaystyle\left(\frac{\tilde{\beta_{l}}}{\dim(V^{l})}\pm\frac{2^{n}}{p(n)\dim(V^{l})}\right)\left(1\pm\frac{2^{n}}{r(n)\dim(V^{l})}\right)^{-1}.$

Using the fact that $\frac{\dim(V^{l})}{2^{n}}\geq 1/q(n)$ for some polynomial
$q(n)$, our estimate satisfies

$\displaystyle\left(\frac{\tilde{\beta_{l}}}{\dim(V^{l})}\pm\frac{q(n)}{p(n)}\right)\left(1\pm\frac{q(n)}{r(n)}\right)^{-1}.$
(B.7)

Choosing $r(n)$ and $p(n)$ sufficiently large so that
$\frac{q(n)}{p(n)}=\epsilon=1/\poly(n)$ and
$\frac{q(n)}{r(n)}=1/\poly(n)=\epsilon^{\prime}$, we have an estimate

$\displaystyle\left(\frac{\tilde{\beta_{l}}}{\dim(V^{l})}\pm\epsilon\right)\left(1\pm\epsilon^{\prime}\right)^{-1}.$
(B.8)

We can then see that

$(1\pm\epsilon^{\prime})^{-1}=1\mp\frac{\epsilon^{\prime}}{1\pm\epsilon^{\prime}}=1\pm\frac{1}{O(\poly(n))},$

and hence the estimate in Equation B.8 satisfies

$\displaystyle\frac{\tilde{\beta_{l}}}{\dim(V^{l})}\pm\frac{1}{O(\poly(n))}$
(B.9)

for some polynomial depending on $\epsilon$ and $\epsilon^{\prime}$.

In the end we obtain an estimate of $\frac{\tilde{\beta_{l}}}{\dim(V^{l})}$ up
to inverse polynomial additive error in polynomial time using a
$\mathsf{DQC1}$ algorithm, proving the statement. ∎

##  Appendix C Decompositions of the Dirac and Laplacian Operators for VQE

As discussed in the main text, when designing VQE algorithms to find ground
states of a Hamiltonian $H$, it is often helpful to decompose the Hamiltonian
into sets of mutually commuting operators, which can lead to shallower circuit
ansatze and fewer energy measurements required to estimate the energy of a
candidate state.

More precisely, if we can write $H=\sum_{j=1}^{m}H_{j}$ where each $H_{j}$ is
a sum of commuting operators, then a single layer of the ansatz is a unitary
of the form

$\prod_{j=1}^{m}e^{it_{j}H_{j}}$ (C.1)

where the individual $t_{j}$ are parameters of the ansatz. This decomposition
can allow for more efficient implementation if the terms in each $H_{j}$ can
be implemented in parallel, and therefore minimising the number $m$ of terms
can lead to shallower ansatz circuits.

Similarly, to measure the energy
$E(\bm{\theta})=\langle\psi(\bm{\theta})|H|\psi(\bm{\theta})\rangle$ at the
end of the circuit, it is again natural to use a decomposition into sets of
commuting terms. I.e. we can obtain an estimate of $E(\bm{\theta})$ by noting
that
$\langle\psi(\bm{\theta})|H|\psi(\bm{\theta})\rangle=\sum_{j=1}^{m}\langle\psi(\bm{\theta})|H_{j}|\psi(\bm{\theta})\rangle=:\sum_{j=1}^{m}E_{j}(\bm{\theta})$.
Since all the observables within a single $H_{j}$ commute, we can measure them
simultaneously. Hence, to obtain an estimate of $E(\bm{\theta})$ it suffices
to obtain estimates of each of the $m$ energies $E_{j}(\bm{\theta})$.
Minimising the number $m$ of terms in the decomposition can again lead to
fewer energy measurements. Alternatively, if the available resources allow for
it, one can use quantum phase estimation to measure the energy.

As we mentioned in Section 6.3, there are two approaches we could take to
design a variational quantum algorithm for TDA using the independence complex:
i) find low-energy states of the Dirac operator $B=(d+d^{\dagger})$, or ii)
find low-energy states of the Laplacian $\Delta$, where option i) is only
available to us due to the supersymmetry of the underlying system. In what
follows we show that in some cases this approach might improve the scaling of
a VQE algorithm.

The first step in either approach is to transform the problem into qubit
space: i.e. transform the operator on fermionic modes into one on qubits. For
simplicity, we focus here on the well-known Jordan-Wigner transform.343434Here
the fermionic creation and annihilation operators are mapped as
$a_{i}^{\dagger}\xmapsto{JW}\sigma^{+}_{i}=\frac{1}{2}(X_{i}-iY_{i})Z_{0}\cdots
Z_{i-1}$,
$a_{i}\xmapsto{JW}\sigma^{-}_{i}=\frac{1}{2}(X_{i}+iY_{i})Z_{0}\cdots
Z_{i-1}$. The string of $Z$’s is often referred to as the Pauli string and
introduces some non-locality (in qubit space) from the otherwise local
fermionic operators. Once we have done this, we can consider what
decompositions into commuting sums of the transformed operators
$B\xmapsto{JW}\hat{B}$ or $\Delta\xmapsto{JW}\hat{\Delta}$ are possible. There
have been a number of recent works on general techniques for splitting the
terms of a local Hamiltonian into commuting sets [98, 99, 100, 101], but we
won’t consider these here and instead focus on using the structure of the
graph more directly.

First we consider the operator $\hat{B}$. Under the Jordan Wigner
transformation, we choose a fixed ordering over fermionic modes, which we will
take to be the same as the ordering over vertices in the graph. Then $\hat{B}$
takes the form

$\hat{B}=\sum_{i=1}^{n}X_{i}\overrightarrow{Z_{i}}\hat{P}_{i}$ (C.2)

where $\overrightarrow{Z_{i}}$ is the Pauli string that takes the form
$\overrightarrow{Z_{i}}=\bigotimes_{j<i}Z_{j}$ and

$\hat{P}_{i}=\prod_{j:(i,j)\in E}\ket{0}\\!\bra{0}_{j}.$ (C.3)

Grouping these into sets of commuting terms might be difficult: any $X_{i}$
will not commute with a term $Z_{i}$ or $\ket{0}\\!\bra{0}_{i}$, and so if a
vertex $i$ appears in the $\overrightarrow{Z_{i^{\prime}}}$ or
$\hat{P}_{i^{\prime}}$ terms of another vertex $i^{\prime}$, we cannot group
together the operators associated with $i$ and $i^{\prime}$. In general the
projectors $\hat{P}_{i}$ will contain at most $d$ terms, whilst the Pauli
strings could contain up to $n$ terms, making such overlaps likely. For more
structured graphs it might be possible with some pre-processing to choose the
Jordan Wigner ordering carefully to maximise the number of commuting terms.
However, this might not always be possible, and in that case the simplest
decomposition is the one written above in Eq. (C.2), where there are at most
$n$ sets of commuting terms of the form
$X_{i}\overrightarrow{Z_{i}}\hat{P}_{i}$.

The second approach considers the full Laplacian $\Delta$, rather than the
operator $B$ considered above. The Jordan-Wigner transformed Laplacian is

$\hat{\Delta}=\sum_{(i,j)\in
E}\hat{P}_{i}\frac{1}{2}(X_{i}X_{j}-iY_{i}Y_{j})Z_{i+1}\cdots
Z_{j-1}\hat{P}_{j}+\sum_{i\in V}\hat{P}_{i}\,$ (C.4)

where now the Pauli strings only act on vertices that lie between $i$ and $j$
under the chosen ordering. Once again, grouping these operators into sets of
commuting terms will often be difficult, except here we have the advantage
that the Pauli strings $Z_{i+1}\cdots Z_{j-1}$ generally involve fewer
vertices, and could be made more local with a good choice of JW-ordering. On
the other hand, each term contains now two $\hat{P}_{i}$ terms, which in the
worst case might act on disjoint vertices, leading to a combined locality of
$2d$. Similarly to the previous case, we see that without any additional
structure on the graph, the simplest decomposition is again the one written in
Eq. (C.4), in which there are $n(d+1)$ terms.

Hence, in a worst-case analysis, the possibility of using the Dirac operator
$B$ over the Laplacian $\Delta$ can reduce the size of the decomposition into
sets of commuting terms. As discussed in the main text, this size is a common
bottleneck for VQE algorithms, often affecting both the scaling of the depth
of the circuit ansatz and the total number of energy measurements that need to
be performed. Using the independence complex as an example, we found that
considering $B$ instead of $\Delta$ led to a factor of $d+1$ improvement in
the size of this decomposition. It is likely that the decomposition could be
made more efficient by, for example, taking into account the underlying
structure and connectivity of the graph, or by using alternative fermion-to-
qubit transformations, but we leave such considerations to further work. More
generally, one might expect that the use of the supercharge of a
supersymmetric system, rather than the Hamiltonian itself, might yield better
scaling VQE algorithms for finding low-energy states.

## References

  * [1] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing 26 (Oct, 1997) 1484–1509. arXiv:quant-ph/9508027.
  * [2] J. Watrous, Quantum Computational Complexity, pp. 7174--7201.  Springer New York, New York, NY, 2009.  quant-ph/0804.3401.
  * [3] A. Drucker and R. de Wolf, Quantum proofs for classical theorems, Theory of Computing (2011). arXiv:0910.3376.
  * [4] A. Y. Kitaev, A. H. Shen, and M. N. Vyalyi, Classical and Quantum Computation.  Graduate Studies in Mathematics, 2002.
  * [5] J. Kempe and O. Regev, $3$-local hamitonian is $\QMA$-complete, Quantum Information & Computation 3 (2003), no. 3 258--264. arXiv:quant-ph/0302079.
  * [6] J. Kempe, A. Kitaev, and O. Regev, The complexity of the local Hamiltonian problem, SIAM Journal on Computing 35 (2006), no. 5 1070--1097. arXiv:quant-ph/0406180.
  * [7] P. M. Crichigno, Supersymmetry and Quantum Computation, arXiv:2011.01239.
  * [8] C. A. Weibel, An Introduction to Homological Algebra.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1994.
  * [9] H. Cartan and S. Eilenberg, Homological Algebra (PMS-19).  Princeton University Press, 2016.
  * [10] T. Kaczynski, K. M. Mischaikow, M. Mrozek, and K. Mischaikow, Computational homology.  Applied mathematical sciences (Springer-Verlag New York Inc.); v. 157\. Springer, New York, 2004.
  * [11] C. A. Weibel, Chapter 28 - History of Homological Algebra, in History of Topology (I. James, ed.), pp. 797--836.  North-Holland, Amsterdam, 1999.
  * [12] H. Nicolai, Supersymmetry and Spin Systems, Journal of Physics A 9 (1976) 1497--1506.
  * [13] E. Witten, Dynamical Breaking of Supersymmetry, Nuclear Physics B 188 (1981) 513.
  * [14] E. Witten, Constraints on Supersymmetry Breaking, Nuclear Physics B 202 (1982) 253.
  * [15] E. Witten, Supersymmetry and Morse theory, J. Differential Geometry 17 (1982), no. 4 661--692.
  * [16] P. Fendley, K. Schoutens, and J. de Boer, Lattice models with $\mathcal{N}=2$ supersymmetry, Physical review letters 90 (2003), no. 12 120402. arXiv:hep-th/0210161.
  * [17] S. B. Bravyi and A. Y. Kitaev, Fermionic quantum computation, Annals of Physics 298 (2002), no. 1 210--226. arXiv:quant-ph/0003137.
  * [18] L. Huijse, K. Schoutens, et al., Supersymmetry, lattice fermions, independence complexes and cohomology theory, Advances in Theoretical and Mathematical Physics 14 (2010), no. 2 643--694. arXiv:0903.0784.
  * [19] L. Wasserman, Topological data analysis, Annual Review of Statistics and Its Application 5 (2018) 501--532. arXiv:1609.08227.
  * [20] S. Lloyd, S. Garnerone, and P. Zanardi, Quantum algorithms for topological and geometric analysis of data, Nature Communications 7 (2016), no. 1 10138. arXiv:1408.3106.
  * [21] B. Foxen, C. Neill, A. Dunsworth, P. Roushan, B. Chiaro, A. Megrant, J. Kelly, Z. Chen, K. Satzinger, and R. Barends, Demonstrating a continuous set of two-qubit gates for near-term quantum algorithms, Physical Review Letters 125 (Sep, 2020). arXiv:2001.08343.
  * [22] H. Saleur and N. P. Warner, Lattice models and n= 2 supersymmetry, in Quantum Field Theory and String Theory, pp. 335--377.  Springer, 1995.  arXiv:hep-th/9311138.
  * [23] P. Fendley, B. Nienhuis, and K. Schoutens, Lattice fermion models with supersymmetry, Journal of Physics A: Mathematical and General 36 (Dec, 2003) 12399–12424. arXiv:cond-mat/0307338.
  * [24] X. Yang and P. Fendley, Non-local spacetime supersymmetry on the lattice, Journal of Physics A Mathematical General 37 (Sept., 2004) 8937--8948, [cond-mat/0404682].
  * [25] P. Fendley and K. Schoutens, Cooper pairs and exclusion statistics from coupled free-fermion chains, J. Stat. Mech. 0702 (2007) P02017, [cond-mat/0612270].
  * [26] J. de Gier, G. Z. Feher, B. Nienhuis, and M. Rusaczonek, Integrable supersymmetric chain without particle conservation, J. Stat. Mech. 1602 (2016), no. 2 023104, [arXiv:1510.02520].
  * [27] W. Fu, D. Gaiotto, J. Maldacena, and S. Sachdev, Supersymmetric sachdev-ye-kitaev models, Physical Review D 95 (Mar, 2017).
  * [28] T. Cubitt and A. Montanaro, Complexity classification of local Hamiltonian problems, SIAM Journal on Computing 45 (2016), no. 2 268--316. arXiv:1311.3161.
  * [29] B. O’Gorman, S. Irani, J. Whitfield, and B. Fefferman, Electronic structure in a fixed basis is qma-complete, arXiv:2103.08215 (2021).
  * [30] O. Goldreich, On promise problems: A survey, in Theoretical computer science, pp. 254--290.  Springer, 2006.
  * [31] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf, Quantum lower bounds by polynomials, Journal of the ACM (JACM) 48 (2001), no. 4 778--797. arXiv:quant-ph/9802049.
  * [32] D. Janzing and P. Wocjan, A simple $\mathsf{PromiseBQP}$-complete matrix problem, Theory of computing 3 (2007), no. 1 61--79.
  * [33] M. Freedman, $\mathsf{P}/\mathsf{NP}$, and the quantum field computer, Proceedings of the National Academy of Sciences of the United States of America 95 1 (1998) 98--101.
  * [34] M. Freedman, A. Kitaev, M. Larsen, and Z. Wang, Topological quantum computation, Bulletin of the American Mathematical Society 40 (2003), no. 1 31--38. arXiv:quant-ph/0101025.
  * [35] J. Preskill, Lecture notes for Physics 219: Quantum computation, Caltech Lecture Notes (1999). Link.
  * [36] V. Lahtinen and J. Pachos, A short introduction to topological quantum computation, SciPost Physics 3 (Sep, 2017). arXiv:1705.04103.
  * [37] A. Kitaev, Fault-tolerant quantum computation by anyons, Annals of Physics 303 (Jan, 2003) 2–30. arXiv:quant-ph/9707021.
  * [38] M. H. Freedman, A. Kitaev, and Z. Wang, Simulation of topological field theories by quantum computers, Communications in Mathematical Physics 227 (Jun, 2002) 587–603. arXiv:quant-ph/0001071.
  * [39] M. H. Freedman, M. Larsen, and Z. Wang, A modular functor which is universal for quantum computation, Communications in Mathematical Physics 227 (2002), no. 3 605--622. arXiv:quant-ph/0001108.
  * [40] D. Aharonov, V. Jones, and Z. Landau, A polynomial quantum algorithm for approximating the jones polynomial, Algorithmica 55 (2009), no. 3 395--421. arXiv:quant-ph/0511096.
  * [41] E. Witten, Quantum Field Theory and the Jones Polynomial, Communications in Mathematical Physics 121 (1989) 351--399.
  * [42] C. Hagendorf, T. B. Fokkema, and L. Huijse, Bethe ansatz solvability and supersymmetry of the M2 model of single fermions and pairs, Journal of Physics A: Mathematical and Theoretical 47 (Nov, 2014) 485201. arXiv:1408.4403.
  * [43] S. Gharibian, Y. Huang, Z. Landau, and S. W. Shin, Quantum Hamiltonian complexity, Theoretical Computer Science 10 (2014), no. 3 159--282. arXiv:1401.3916.
  * [44] B. Brown, S. T. Flammia, and N. Schuch, Computational difficulty of computing the density of states, Physical Review Letters 107 (Jul, 2011). arXiv:1010.3060.
  * [45] C. Gyurik, C. Cade, and V. Dunjko, Towards quantum advantage for topological data analysis, arXiv:2005.02607 (2020).
  * [46] F. G. Brandão, Entanglement theory and the quantum simulation of many-body physics, arXiv:0810.0026 (2008).
  * [47] J. Minář, B. van Voorden, and K. Schoutens, Kink dynamics and quantum simulation of supersymmetric lattice Hamiltonians, 2020.
  * [48] T. Grover, D. Sheng, and A. Vishwanath, Emergent Space-Time Supersymmetry at the Boundary of a Topological Phase, Science 344 (2014), no. 6181 280--283, [arXiv:1301.7449].
  * [49] A. Rahmani, X. Zhu, M. Franz, and I. Affleck, Emergent Supersymmetry from Strongly Interacting Majorana Zero Modes, prl 115 (Oct., 2015) 166401, [arXiv:1504.05192].
  * [50] G. Junker, Supersymmetric Methods in Quantum and Statistical Physics.  Theoretical and Mathematical Physics. Springer-Verlag Berlin Heidelberg, 1996.
  * [51] K. Hori, S. Katz, A. Klemm, R. Pandharipande, R. Thomas, C. Vafa, R. Vakil, and E. Zaslow, Mirror symmetry, vol. 1 of Clay mathematics monographs.  AMS, Providence, USA, 2003.
  * [52] H. Edelsbrunner and J. L. Harer, Computational Topology: An Introduction, vol. 47.  2009\.
  * [53] A. J. Zomorodian, Topology for Computing.  Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2005.
  * [54] W. Fu, D. Gaiotto, J. Maldacena, and S. Sachdev, Supersymmetric Sachdev-Ye-Kitaev models, Phys. Rev. D 95 (2017), no. 2 026009, [arXiv:1610.08917]. [Addendum: Phys.Rev.D 95, 069904 (2017)].
  * [55] Y.-K. Liu, M. Christandl, and F. Verstraete, Quantum computational complexity of the $n$-representability problem: $\QMA$ complete, Physical Review Letters 98 (Mar, 2007). arXiv:quant-ph/0609125.
  * [56] D. W. Berry, A. M. Childs, and R. Kothari, Hamiltonian simulation with nearly optimal dependence on all parameters, in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 792--809, IEEE, 2015.  arXiv:1501.01715.
  * [57] V. Kaibel and M. E. Pfetsch, Some Algorithmic Problems in Polytope Theory, arXiv Mathematics e-prints (Feb., 2002) math/0202204, [math/0202204].
  * [58] M. Adamaszek and J. Stacho, Complexity of simplicial homology and independence complexes of chordal graphs, Computational Geometry 57 (2016) 8 -- 18.
  * [59] S. Bravyi, Efficient algorithm for a quantum analogue of 2-SAT, Contemporary Mathematics 536 (2011) 33--48, [quant-ph/0602108].
  * [60] D. Gosset and D. Nagaj, Quantum 3-sat is $\QMA_{1}$-complete, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (Oct, 2013). arXiv:1302.0290.
  * [61] S. Lloyd, Universal quantum simulators, Science (1996) 1073--1078. arXiv:quant-ph/9703054.
  * [62] S. Aaronson, On perfect completeness for $\QMA$, Quantum Information & Computation 9 (2009), no. 1 81--89. arXiv:0806.0450.
  * [63] P. Scheiblechner, On the complexity of deciding connectedness and computing betti numbers of a complex algebraic variety, Journal of Complexity 23 (2007), no. 3 359--379.
  * [64] N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2 83--96.
  * [65] J. R. Lee, S. O. Gharan, and L. Trevisan, Multiway spectral partitioning and higher-order cheeger inequalities, Journal of the ACM (JACM) 61 (2014), no. 6 1--30. arXiv:1111.1055.
  * [66] R. Peng, H. Sun, and L. Zanetti, Partitioning well-clustered graphs: Spectral clustering works!, in Conference on Learning Theory, pp. 1423--1455, PMLR, 2015.  arXiv:1411.2021.
  * [67] O. Parzanchevski, R. Rosenthal, and R. J. Tessler, Isoperimetric inequalities in simplicial complexes, Combinatorica 36 (2016), no. 2 195--227. arXiv:1207.0638.
  * [68] D. Horak and J. Jost, Spectra of combinatorial laplace operators on simplicial complexes, Advances in Mathematics 244 (2013) 303--336. arXiv:1105.2712.
  * [69] J. Steenbergen, C. Klivans, and S. Mukherjee, A cheeger-type inequality on simplicial complexes, Advances in Applied Mathematics 56 (2014) 56--77. arXiv:1209.5091.
  * [70] A. Gundert and M. Szedlák, Higher dimensional cheeger inequalities, in Proceedings of the thirtieth annual symposium on Computational geometry, pp. 181--188, 2014.  arXiv:1401.2290.
  * [71] S. Palande and B. Wang, Spectral sparsification of simplicial complexes for clustering and label propagation, Journal of Computational Geometry 11 (2020), no. 1 176--211. arXiv:1708.08436.
  * [72] J. T. Seeley, M. J. Richard, and P. J. Love, The Bravyi-Kitaev transformation for quantum computation of electronic structure, The Journal of chemical physics 137 (2012), no. 22 224109. arXiv:1208.5986.
  * [73] S. Aaronson, A. Bouland, G. Kuperberg, and S. Mehraban, The computational complexity of ball permutations, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 317--327, 2017.  arXiv:1610.06646.
  * [74] Y. Cao, J. Romero, J. P. Olson, M. Degroote, P. D. Johnson, M. Kieferová, I. D. Kivlichan, T. Menke, B. Peropadre, N. P. Sawaya, et al., Quantum chemistry in the age of quantum computing, Chemical reviews 119 (2019), no. 19 10856--10915. arXiv:1812.09976.
  * [75] J. R. McClean, N. C. Rubin, J. Lee, M. P. Harrigan, T. E. O’Brien, R. Babbush, W. J. Huggins, and H.-Y. Huang, What the foundations of quantum computer science teach us about chemistry, arXiv:2106.03997 (2021).
  * [76] R. Ghrist, Barcodes: the persistent topology of data, Bulletin of the American Mathematical Society 45 (2008), no. 1 61--75.
  * [77] P. Fendley and K. Schoutens, Exact results for strongly correlated fermions in 2+ 1 dimensions, Physical review letters 95 (2005), no. 4 046403. arXiv:cond-mat/0504595.
  * [78] J. Jonsson, Certain homology cycles of the independence complex of grids, Discrete & Computational Geometry 43 (2010), no. 4 927--950.
  * [79] H. van Eerten, Extensive ground state entropy in supersymmetric lattice models, Journal of mathematical physics 46 (2005), no. 12 123302\. arXiv:cond-mat/0509581.
  * [80] L. Huijse, D. B. Mehta, N. Moran, K. Schoutens, and J. Vala, Supersymmetric lattice fermions on the triangular lattice: Superfrustration and criticality, New Journal of Physics. 14 (2012) 073002, [arXiv:1112.3314].
  * [81] C. Reiher, The clique density theorem, Annals of Mathematics (2016) 683--707. arXiv:1212.2454.
  * [82] A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu, A theory of Trotter error, arXiv:1912.08854 (2019).
  * [83] B. Sahinoglu and R. Somma, Hamiltonian simulation in the low energy subspace, Bulletin of the American Physical Society. arXiv:2006.02660.
  * [84] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’brien, A variational eigenvalue solver on a photonic quantum processor, Nature communications 5 (2014), no. 1 1--7. arXiv:1304.3061.
  * [85] J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik, The theory of variational hybrid quantum-classical algorithms, New Journal of Physics 18 (2016), no. 2 023023. arXiv:1509.04279.
  * [86] C. Cade, L. Mineh, A. Montanaro, and S. Stanisic, Strategies for solving the fermi-hubbard model on near-term quantum computers, Physical Review B 102 (2020), no. 23 235122. arXiv:1912.06007.
  * [87] D. Wecker, M. B. Hastings, and M. Troyer, Progress towards practical quantum variational algorithms, Physical Review A 92 (2015), no. 4 042303. arXiv:1507.08969.
  * [88] Z. Cai, Resource estimation for quantum variational simulations of the hubbard model, Physical Review Applied 14 (2020), no. 1 014059. arXiv:1910.02719.
  * [89] P. Fendley and C. Hagendorf, Exact and simple results for the $XYZ$ and strongly interacting fermion chains, Journal of Physics A: Mathematical and Theoretical 43 (Sep, 2010) 402004. arXiv:1006.0237.
  * [90] L. Huijse, N. Moran, J. Vala, and K. Schoutens, Exact ground states of a staggered supersymmetric model for lattice fermions, Physical Review B 84 (Sep, 2011). arXiv:1103.1368.
  * [91] V. von Burg, G. H. Low, T. Häner, D. S. Steiger, M. Reiher, M. Roetteler, and M. Troyer, Quantum computing enhanced computational catalysis, arXiv:2007.14460 (2020).
  * [92] J. P. LeBlanc, A. E. Antipov, F. Becca, I. W. Bulik, G. K.-L. Chan, C.-M. Chung, Y. Deng, M. Ferrero, T. M. Henderson, C. A. Jiménez-Hoyos, et al., Solutions of the two-dimensional hubbard model: Benchmarks and results from a wide range of numerical algorithms, Physical Review X 5 (2015), no. 4 041041. arXiv:1505.02290.
  * [93] S. Aaronson, A. Bouland, G. Kuperberg, and S. Mehraban, The computational complexity of ball permutations, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 317--327, 2017.  arXiv:1610.06646.
  * [94] R. Santachiara and K. Schoutens, Supersymmetric model of spin-1/2 fermions on a chain, Journal of Physics A Mathematical General 38 (June, 2005) 5425--5439, [cond-mat/0503354].
  * [95] H.-Y. Huang, R. Kueng, G. Torlai, V. V. Albert, and J. Preskill, Provably efficient machine learning for quantum many-body problems, 2021.
  * [96] C. Cade and A. Montanaro, The quantum complexity of computing Schatten $p$-norms, in 13th Conference on the Theory of Quantum Computation, Communication and Cryptography, 2018.  arXiv:1706.09279.
  * [97] T. Morimae, K. Fujii, and J. F. Fitzsimons, Hardness of classically simulating the one-clean-qubit model, Physical review letters 112 (2014), no. 13 130502. arXiv:1312.2496.
  * [98] W. J. Huggins, J. R. McClean, N. C. Rubin, Z. Jiang, N. Wiebe, K. B. Whaley, and R. Babbush, Efficient and noise resilient measurements for quantum chemistry on near-term quantum computers, npj Quantum Information 7 (2021), no. 1 1--9. arXiv:1907.13117.
  * [99] O. Crawford, B. van Straaten, D. Wang, T. Parks, E. Campbell, and S. Brierley, Efficient quantum measurement of Pauli operators in the presence of finite sampling error, Quantum 5 (2021) 385. arXiv:1908.06942.
  * [100] A. F. Izmaylov, T.-C. Yen, and I. G. Ryabinkin, Revising the measurement process in the variational quantum eigensolver: is it possible to reduce the number of separately measured operators?, Chemical science 10 (2019), no. 13 3746--3755. arXiv:1810.11602.
  * [101] P. Gokhale, O. Angiuli, Y. Ding, K. Gui, T. Tomesh, M. Suchara, M. Martonosi, and F. T. Chong, Minimizing state preparations in variational quantum eigensolver by partitioning into commuting families, arXiv:1907.13623 (2019).


# Truncated tube domains with multi-sheeted envelope

Suprokash Hazra Department of Mathematics
Mid Sweden University
SE-851 70 Sundsvall
Sweden<EMAIL_ADDRESS><EMAIL_ADDRESS>and  Egmont Porten

###### Abstract.

The present article is concerned with a group of problems raised by J. Noguchi
and M. Jarnicki/P. Pflug, namely whether the envelopes of holomorphy of
truncated tube domains are always schlicht, i.e. subdomains of
$\mathbb{C}^{n}$, and how to characterise schlichtness if this is not the
case. By way of a counter-example homeomorphic to the $4$-ball, we answer the
first question in the negative. Moreover, it is possible that the envelopes
has arbitrarily many sheets. The article is concluded by sufficient conditions
for schlichtness in complex dimension two.

###### Key words and phrases:

Envelopes of holomorphy, truncated tube domains, special phenomena in complex
dimension two.

###### 2020 Mathematics Subject Classification:

Primary 32D10, 32D26, 32Q02 ; Secondary 32V25, 32E20.

##  1\. Introduction

A domain $D\subset\mathbb{C}^{n}$ is said to be a _tube domain_ if there are
domains $X$, $Y\subset\mathbb{R}^{n}$ such that $D=X+iY$. In case that one of
the domains $X$, $Y$ equals $\mathbb{R}^{n}$, $D$ is a _Bochner tube domain_.
Otherwise $D$ is often called _truncated_ tube domain. A classical theorem of
Bochner [1] shows the envelope of holomorphy of $X+i\mathbb{R}^{n}$ to be the
tube $\mbox{conv}(X)+i\mathbb{R}^{n}$ over the convex hull $\mbox{conv}(X)$,
meaning in particular that the envelope is schlicht.

Truncated tube domains are much less understood. While the geometry of
pseudoconvex tube domains is still simple (see [8] and [7] for an alternative
approach), the investigation of the envelope becomes subtle in the
nonpseudoconvex case. Recently, questions about multi-sheetedness of these
envelopes were raised by J. Noguchi [7] and by M. Jarnicki and P. Pflug [3].
More precisely, it is asked in [3, Rem.4] whether these envelopes are always
schlicht, and in [7, Problem 4.4] whether simply connected or contractible
tube domain have schlicht envelope. In the present article, we will present
counter-examples answering both of the questions in the negative, namely tube
domains homeomorphic to the $4$-ball whose envelopes have arbitrarily many
sheets.

Let us review some terminology and results on envelopes, see [2] for
exhaustive information. It is classical that every domain
$D\subset\mathbb{C}^{n}$ admits a Riemann domain
$\pi:\textsf{E}(D)\rightarrow\mathbb{C}^{n}$ (unique up to isomorphisms of
Riemann domains over $\mathbb{C}^{n}$) with the following properties:

  * (i)ii

There is an embedding $\alpha:D\hookrightarrow\textsf{E}(D)$ with
$\pi\circ\alpha=\mbox{id}_{D}$.

  * (ii)i

For every $f\in\mathcal{O}(D)$, the lift $f\circ(\pi|_{\alpha(D)})$ extends
holomorphically to $\textsf{E}(D)$,

  * (iii)

$\textsf{E}(D)$ is Stein.

This domain is called the _envelope of holomorphy of $D$_, see [2] for
exhaustive information. We say that $\textsf{E}(D)$ is _$k$ -sheeted over
$z\in\mathbb{C}^{n}$_ if $\\#\pi^{-1}(z)=k$. For $U^{\rm
open}\subset\mathbb{C}^{n}$, a sheet lying _uniformly over $U$_ is an open set
$V\subset\textsf{E}(D)$ such that $\pi|_{V}$ is a homeomorphism onto $U$. The
latter notion is mainly interested for an infinite number of sheets. If
$\textsf{E}(D)$ is $k$-sheeted over $z\in\mathbb{C}^{n}$ with $k<\infty$, then
there are $k$ sheets lying uniformly over any sufficiently small neighbourhood
of $z$.

The following is our main result.

######  Theorem 1.1.

For every integer $k\geq 2$ there is a domain $X_{k}\Subset\mathbb{R}^{2}$
with $\mathcal{C}^{\infty}$-smooth boundary and a radius $r_{k}>0$ such that
the envelope of holomorphy of $D_{k}=X_{k}+iB_{r_{k}}$ has at least $k$ sheets
over some point in $\mathbb{C}^{2}$. Furthermore, there are a domain
$X_{\infty}\Subset\mathbb{R}^{2}$ and $r_{\infty}>0$ such that
$\textsf{E}(X_{\infty}+iB_{r_{\infty}})$ has infinitely many sheets lying
uniformly over a neighbourhood of a circle embedded in $\mathbb{C}^{2}$. The
domains $X_{k}$ and $X_{\infty}$ can be constructed diffeomorphic to the open
$4$-ball.

Throughout, $B_{r}(y_{0})$ denotes the round ball
$\\{y\in\mathbb{R}^{n}:|y-y_{0}|<r\\}$ in $\mathbb{R}^{n}$, in constrast to
balls in $\mathbb{C}^{n}$, denoted by ${\mathbb{B}}_{r}(z_{0})$. If $y_{0}=0$,
we abreviate $B_{r}=B_{r}(0)$. Note however that the exact shape of the
domains in $y$-direction is not very important. Moreover, it is easy to derive
corresponding examples of tube domains in $\mathbb{C}^{n}$, $n\geq 3$. More
interesting is the difference concerning boundary regularity for $X_{k}$,
$k<\infty$, and $X_{\infty}$. The authors do not know whether the envelope is
always finitely sheeted if both $X$ and $Y$ are bounded and have smooth
boundary. This may be viewed as a minor variant of the long-standing open
problem raised by B. Stensønes (Problem 3.3.1, [12]) whether envelopes of
bounded domains with smooth boundary are finitely sheeted.

On the other side, one may still look for sufficient conditions ensuring
schlichtness. In recent work, M. Jarnicki and P. Pflug [3] explicitly
determined the envelopes of the model domains

$D_{n,r_{1},r_{2},r_{3}}=\\{x\subset\mathbb{R}^{n}:r_{1}<|x|<r_{2}\\}+iB_{r_{3}}\subset\mathbb{C}^{n},$
(1.1)

where $n\geq 2,0\leq r_{1}<r_{2},\ 0<r_{3}$, to be schlicht and equal to

$\textsf{E}(D_{n,r_{1},r_{2},r_{3}})=\\{|x|<r_{2},|y|<r_{3},|y|^{2}<|x|^{2}-(r_{1}^{2}-r_{3}^{2})\\}.$
(1.2)

Motivated by their question about generalizations, we present a general
schlichtness theorem for $n=2$.

######  Theorem 1.2.

Let $X\subset\mathbb{R}^{2}$ be a convex domain with finitely many holes with
strictly convex $\mathcal{C}^{2}$-boundary, and let $Y\Subset\mathbb{R}^{2}$
be a convex domain. Then the envelope of holomorphy of $D=X+iY$ is schlicht.

Strict convexity in the above statement is meant in the sense of nonzero
curvature, see Section 4 for details. Note that the domains
$D_{2,r_{1},r_{2},r_{3}}$ satisfy the assumptions with
$X=\\{r_{1}<|x|<r_{2}\\}$. In the general situation, one cannot expect to
obtain a description of $\textsf{E}(D)$ as explicit as in (1.2). Actually,
Lemma 4.1 shows that this is essentially as hard as describing polynomial
hulls. However, Theorem 1.2 permits to derive some qualitative consequences.
Our proof essentially relies on phenomena special to complex dimension two,
and the corresponding question in higher dimension remains open.

The article is organised as follows. In Section 2, we construct the counter-
examples mentioned in the main result. The idea will be to produce a helix
with many turns in the envelope of holomorphy and lying over a circle in
$\mathbb{C}^{2}$. The question whether this helix can arranged to be maximal
in the sense of universal coverings, is discussed and answered in Section 3.
Moreover, the relation of our construction to limit cycles of laminations will
become apparent. Section 4 finally contains the proof of Theorem 1.2 and the
discussion of some structural consequences.

Acknowledgements: The authors would like to thank Professor Peter Pflug for
drawing their attention to his recent article and for a lot of valuable
remarks helping to ameliorate the quality of the article. They would also like
to thank Professor Junjiro Noguchi for his interest in their work.

##  2\. Proof of the main result

The present section is dedicated to the proof of Theorem 1.1, organised in
four major steps.

Step 1: Geometric preparations. For a complex line
$L=\\{az_{1}+bz_{2}=0\\}\subset\mathbb{C}^{2}$, $(a,b)\not=(0,0)$, the
logarithm $f_{L}=\log(az_{1}+bz_{2})$ can be viewed as a univalent holomorphic
function on the universal covering $\pi_{\rm
univ}:Z\rightarrow\mathbb{C}^{2}\backslash L$ of $\mathbb{C}^{2}\backslash L$.
Of course, $Z$ equals essentially $Z_{\log}\times\mathbb{C}$ where $Z_{\log}$
is the Riemann surface of the logarithm in one complex variable. More
precisely, if another complex line $L^{\prime}$ meets $L$ transversally at the
origin, it is clear that $\pi_{\rm univ}^{-1}(L^{\prime})$ is the universal
covering of $L^{\prime}\backslash\\{0\\}$ (and is equivalent to $Z_{\log}$).

Recall that the set $\mathcal{T}$ of all real planes $\Pi$ intersecting $L$
transversally at $0$ is a topological open $4$-ball. To see this, we pick one
such plane $\Pi_{0}$ and select real linear coordinates
$s_{1},s_{2},t_{1},t_{2}$ such that $L=\\{s_{1}=s_{2}=0\\}$,
$\Pi_{0}=\\{t_{1}=t_{2}=0\\}$. Then the planes $\Pi\in{\mathcal{T}}$ are
represented as graphs

$\left(\begin{array}[]{c}t_{1}\\\
t_{2}\end{array}\right)=A(\Pi)\left(\begin{array}[]{c}s_{1}\\\
s_{2}\end{array}\right),$

establishing a 1-1 correspondence between $\Pi\in{\mathcal{T}}$ and the real
$2\times 2$ matrices $A(\Pi)$.

An easy homotopy argument shows that we can replace $L^{\prime}$ above by any
$\Pi\in{\mathcal{T}}$. In particular, $Z$ is still connected with infinitely
many sheets over $\Pi\backslash\\{0\\}$. If $\gamma$ is a loop surrounding $0$
once within $\Pi$, following $\gamma$ one turn takes us to a new sheet and
changes thus the value of $\log(az_{1}+bz_{2})$ by $\pm 2\pi i$.

We summarise what we need in the sequel.

######  Lemma 2.1.

Let $L\subset\mathbb{C}^{2}$ be a complex line and $\Pi\subset\mathbb{C}^{2}$
a real $2$-plane which intersect transversally at the origin. Let
$\iota:{\mathbb{T}}=\\{\zeta\in\mathbb{C}:|\zeta|=1\\}\hookrightarrow\Pi\backslash\\{0\\}$
be a continuous embedding that surrounds $0$ in $\Pi$ precisely once,
$D\subset\mathbb{C}^{2}$ a simply connected domain containing
$\iota({\mathbb{T}}\backslash\\{1\\})$ but not $\iota(\\{1\\})$, and $F_{L}$ a
continuous branch of $f_{L}$ on $D$. Then the two one-sided limits
$\lim_{\theta\downarrow 0}F_{L}(e^{i\theta})$ and $\lim_{\theta\uparrow
2\pi}F_{L}(e^{i\theta})$ exist and differ by $\pm 2\pi i$.

In more invariant terms, a general loop in $\mathbb{C}^{2}\backslash L$ lifts
as a loop to $Z$ if and only if it is not linked with $L$, but we will not
need this.

######  Remark 2.2.

a) The constructions in this and the next section rely on the initial choice
of a pair $(L,\Pi)$ of a complex line $L$ and a real $2$-dimensional subspace
$\Pi$ transverse to $L$. These pairs are the points of a $6$-dimensional
manifold $\mathcal{P}$. We claim that $GL_{2}(\mathbb{C})$ acts transitively
on $\mathcal{P}$, meaning that all initial choices are equivalent. Given
$(L,\Pi)$, $j=1,2$, it is easy to reduce to the case that
$\Pi_{1}=\Pi_{2}=\mathbb{R}^{2}_{x}$ and
$L_{j}={\mathbb{C}\left(\\!\\!\begin{array}[]{c}1\\\
a_{j}+ib_{j}\end{array}\\!\\!\right)}$, $b_{j}\not=0$. We conclude by
observing that (i) the matrices in $GL_{2}(\mathbb{R})$ fix
$\mathbb{R}^{2}_{x}$ and (ii) $L_{1}$ can always be mapped to $L_{2}$ by a
real invertible matrices of the form $\left(\\!\\!\begin{array}[]{cc}1&0\\\
c&d\end{array}\\!\\!\right)$.

b) The larger manifold $\mathcal{Q}$ of all pairs $(\Pi_{1},\Pi_{2})$ where
the $\Pi_{j}$ are transverse real $2$-dimensional subspaces of
$\mathbb{C}^{2}$ is $8$-dimensional. By dimensional reasons
($GL_{2}(\mathbb{C})$ has real dimension $8$, but real multiples act the same
way), the action of $GL_{2}(\mathbb{C})$ is not transitive. Alternatively, one
may also observe that pairs of the form $(\Pi,i\Pi)$ form a $4$-dimensional
orbit or use [11], where it is shown that $\Pi_{1}\cup\Pi_{2}$ is sometimes
locally polynomially convex and sometimes not.

Step 2: A first option for $D_{2}$. In the above setting we can take
$\Pi=\mathbb{R}^{2}_{x}$ and fix a complex transverse line $L$ accordingly
(for example $L=\\{z_{1}=iz_{2}\\}$). Set
$A=\\{(x_{1},x_{2})\in\mathbb{R}^{2}:1<|x|<2\\}$, and define

$R=\max\\{r>0:L\cap(A+iB_{r})=\emptyset\\}.$ (2.1)

To show that $R$ is well defined, we easily verify that
$\\{r>0:L\cap(A+iB_{r})\not=\emptyset\\}$ is a nonempty interval that is
either of the form $(0,r_{0}]$ or $(0,\infty)$. The last option is impossible,
since any real plane through the origin different from the $i\mathbb{R}^{2}$
must meet $A+iB_{r}$, provided $r$ is large enough.

Working in $\mathbb{R}^{2}$, we observe that the circle $\\{|x-(3/2,-2)|=2\\}$
intersects the closure of $A$ in two connected arcs. Denoting the component
passing through $p=(3/2,0)$ by $\gamma_{0}$, we set $X=A\backslash\gamma_{0}$.

Pick $r\in(0,R]$. We claim that $\textsf{E}(X\times iB_{r})$ is at least
$2$-sheeted over the points below the hypersurface $H_{0}=\gamma_{0}+iB_{r}$
and close to $(3/2,0)$. To prove this, we observe that $H_{0}$ is strictly
pseudoconvex. By the Levi extension theorem, holomorphic functions locally
defined on the upper side $\\{|x-(3/2,-2)|>2\\}$ extend across $H_{0}$ to a
uniform neighbourhood of $(3/2,0)$. We can choose a branch $f$ of $f_{L}$ on
the simply connected domain $X+iB_{r}$. Our initial remarks on $f_{L}$ imply
that the extension of $f$ through $H_{0}$ differs by $\pm 2\pi i$ from $f$ on
the side $|x-(3/2,-2)|<2$, and the claim follows. What we have shown so far is
already enough to answer Noguchi’s question in the negative.

To finish the construction of $D_{2}$, we have to smoothen the boundary $X$.
This can for example be done by cutting out from $X$ the component of

$\\{2-\eta\leq|x-(3/2,-2)|\leq 2\\}\cap X,\mbox{ where }0<\eta\ll 1,$

containing $\gamma_{0}$ and rounding off the four corners. Note that the
choice of $\eta$ sensitively depends on $r$, as will become clear from the
discussion of the Levi extension theorem before the proof of Lemma 2.3.

Step 3: Construction of $D_{\infty}$. To produce envelopes with infinitely
many sheets, we will replace the previous annulus-type domain by a spiral-
shaped subdomain of $\\{|x|>1\\}$ with the circle $S=\\{|x|=1\\}$ in its limit
set. The mapping

$\varphi:[1/2,1]\times\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}^{2},(s,\theta)\mapsto(1+se^{-\theta})(\cos\theta,\sin\theta)$

is an embedding of the semi-infinite strip $[1/2,1]\times\mathbb{R}_{\geq 0}$
into $\\{|x|>1\\}$ (use that $e^{-2\pi}<1/2$). The domain
$X_{\infty}=\varphi((1/2,1)\times\mathbb{R}_{>0})$ is squeezed between the
straight segment with endpoints $(3/2,0)$ and $(2,0)$ and the two spirals

$\Gamma_{1/2}=\varphi(\\{1/2\\}\times\mathbb{R}_{\geq 0})\ \mbox{ and }\
\Gamma_{1}=\varphi(\\{1\\}\times\mathbb{R}_{\geq 0}).$

$\Gamma_{1}$
---
$\Gamma_{\frac{1}{2}}$
---
($\frac{3}{2}$,0)
---
(2,0)
---
$S$
---
$X_{\infty}$
---
$O$
---
$S_{\tau}$
---
$X_{2}$
---
$X_{1}$
---
$\tau$
---
$Q_{\tau,2}$
---
$\gamma_{\tau,3}$
---
$A_{\rho}$
---
$\tau+\frac{\pi}{2}$
---
$\tau-\frac{\pi}{2}$
---

Figure 2.1. Intersection of $D_{\infty}$ with $\mathbb{R}^{2}$

Note that $S$ also belongs to $\overline{X}_{\infty}$, meaning in particular
that the set theoretic boundary $\partial X_{\infty}$ is not smooth along $S$,
see Figure 2.1.

######  Lemma 2.3.

Set $D_{r}=X_{\infty}+iB_{r}$ with $r\in(0,R)$. Then there is $\rho>0$ such
that $\textsf{E}(D_{r})$ contains a Riemann subdomain which has infinitely
many sheets over every point of the thickened annulus
$A_{\rho}=\\{1-\rho<|x|<1\\}+iB_{\rho}$.

Before entering the proof of Lemma 2.3, some comments are in order.

(1) Let us identify the universal covering of $A_{\rho}$ with

$\\{1-\rho<s<1\\}\times\mathbb{R}_{\theta}\times B_{\rho}$

via the map $(s,\theta,y)\mapsto(s\cos\theta,s\sin\theta,y)$. Then the proof
below will show that the Riemann subdomain in the lemma can actually be chosen
as the lifting of a domain of the form

$\\{1-\rho<s<1\\}\times\\{\theta>C\\}\times B_{\rho},$ (2.2)

with $C>0$ sufficiently large.

(2) Recall the Levi extension theorem: Let $H$ be a connected closed real
hypersurface of a domain $G\subset\mathbb{C}^{2}$ such that $G\backslash H$
has two connected components $G^{\pm}$. In addition, assume that the Levi form
of $H$ is nondegenerate in every point and that $G^{+}$ is the pseudoconcave
side of $H$. For $z_{0}\in H$, there is an $\eta>0$ with the following
properties: For every open set $V$ containing $H$, all functions holomorphic
on $V^{+}=V\cap G^{+}$ extend holomorphically to
$V^{+}\cup\big{(}B_{\eta}(z_{0})\cap\overline{G^{-}}\,\big{)}$.

We need two additional stability properties of Levi extension: (i) Since it
mainly depends on Levi curvature, it is stable under $\mathcal{C}^{2}$-small
deformations of $H$. More concretely, the $\eta$ above can be chosen uniformly
for $H$ and all sufficiently $\mathcal{C}^{2}$-close deformations fixing
$z_{0}$. (ii) The constant $\eta$ does not depend on the size of $G^{+}$. If
$G$ is replaced by a smaller domain $G_{1}$ with analogous properties, we
still obtain holomorphic extension to
$G_{1}^{+}\cup\big{(}B_{\eta}(z_{0})\cap\overline{G^{-}}\,\big{)}$. These
properties can be shown by the method of analytic discs, see [5].

Proof of Lemma 2.3: The spiral $\Gamma_{1/2}$ accumulates smoothly to $S$.
More precisely, for any interval
$(\theta_{1},\theta_{2})\subset\mathbb{R}_{>0}$ which is _short_ in the sense
that $\theta_{2}-\theta_{1}<2\pi$, the parametrisations

$\varphi_{j}(\theta)=\varphi(1/2,\theta+2\pi j),\
\theta_{1}<\theta<\theta_{2},\ j=0,1,\ldots,$

tend to $(\cos\theta,\sin\theta)$ on $(\theta_{1},\theta_{2})$ with all their
derivatives for $j\rightarrow\infty$.

Fix now $r<R$ like indicated in the assumptions. For $\tau\in[\pi/2,5\pi/2)$,
we look at the short interval $I_{\tau}=(\tau-\pi/2,\tau+\pi/2)$, the
corresponding halfcircle $S_{\tau}\subset S$ centered at
$z_{\tau}=(\cos\tau,\sin\tau)$, and the strictly pseudoconvex hypersurface
$H_{\tau}=S_{\tau}+iB_{r}$. For $j=0,1,2,\ldots$, we define the translated
intervals

$I_{\tau,j}=(\tau+\pi(2j-1/2),\tau+\pi(2j+1/2))$

and the curved rectangles

$Q_{\tau,j}=\varphi((1/2,1)\times I_{\tau,j}))+iB_{r}.$

The corresponding tubes $Q_{\tau,j}+iB_{r}$ have a pseudoconcave boundary part

$H_{\tau,j}=\varphi(\\{1/2\\}\times I_{\tau,j}))+iB_{r},$

which converges in $\mathcal{C}^{2}$-sense toward $H_{\tau}$ for
$j\rightarrow\infty$.

Set $z_{\tau,j}=\varphi(1/2,\tau+2\pi j)$. For $\eta>0$ not to large
($\eta<1/4$ will do), the disc $B_{3\eta/2}(z_{\tau,j})$ is disconnected by
the arc $\gamma_{\tau,j}=\varphi(\\{1/2\\}\times I_{\tau,j})$ into two
connected components $B^{\pm}_{3\eta/2}(z_{\tau,j})$. We choose signs such
that $B^{-}_{3\eta/2}(z_{\tau,j})$ lies on the pseudoconvex side of
$H_{\tau,j}$. We now define the enlarged domain

$Q_{\tau,j}(\eta)=Q_{\tau,j}\cup\Big{(}\big{(}\gamma_{\tau,j}\cap
B_{3\eta/2}(z_{\tau,j})\big{)}+iB_{\eta}\Big{)}\cup\Big{(}B^{-}_{3\eta/2}(z_{\tau,j})+iB_{\eta}\Big{)}.$

The stability properties of Levi extension discussed above yield an
$\eta=\eta(\tau)>0$ such that for $j$ sufficiently large, say $j\geq
J=J(\tau)$, the following holds: Any function holomorphic on $Q_{\tau,j}$
extends to $Q_{\tau,j}(\eta)$. Enlarging $J$ if necessary, we may in addition
assume that the domain $Q_{\tau,j}(\eta)$, $j\geq J$, contains

${\mathbb{B}}^{-}_{\eta}(\cos\tau,\sin\tau)={\mathbb{B}}_{\eta}(\cos\tau,\sin\tau)\cap(B_{1}+i\mathbb{R}^{2}),$

where ${\mathbb{B}}_{\eta}(z)$ denotes the round ball in $\mathbb{C}^{2}$. By
compactness, we can choose $J$ and $\eta$ uniformly for
$\tau\in[\pi/2,5\pi/2]$.

Relabelling the domains $Q_{\tau,j}$ as $Q_{\sigma}$ if $\sigma=\tau+2\pi j$,
we define $Q_{\sigma}$ for any $\sigma\geq\pi/2$. Then we obtain for every
$f\in\mathcal{O}(D_{\infty})$ a $\sigma$-dependent family of germs
$f_{\sigma}\in\mathcal{O}_{\mathbb{C}^{2},(\cos\sigma,\sin\sigma)}$111
$\mathcal{O}_{\mathbb{C}^{2},(z)}$ denotes the stalk of holomorphic germs at
the point $z\in\mathbb{C}^{2}$., $\sigma\geq 2J\pi+\pi/2$, by

  * (i)ii

restricting $f$ to $f|_{Q_{\sigma}}$,

  * (ii)i

extending $f|_{Q_{\sigma}}$ to $Q_{\sigma}(\eta)$, and

  * (iii)

restricting to the germ of the extension at $(\cos\sigma,\sin\sigma)\in
Q_{\sigma}(\eta)$.

This yields a continuously parametrised curve $\sigma\mapsto
p(\sigma)\in\textsf{E}(D_{\infty})$, $\sigma\geq 2\pi J+\pi/2$, over $S$.

Next we specialise to a branch $\tilde{f}_{L}$ of $f_{L}=\log(az_{1}+bz_{2})$
on $D_{\infty}$, which exists since $D_{\infty}$ is simply connected. The
above construction also gives a continuous curve $\sigma\mapsto q(\sigma)\in
Z$ over $S$, $\sigma\geq 2\pi J+\pi/2$, by mapping the germ of the extension
at $(\cos\sigma,\sin\sigma)$ to the corresponding point in the Riemann domain
of $\tilde{f}_{L}$. With every turn, $q(\sigma)$ changes sheet, and therefore
the values of two consecutive extensions at $(\cos\sigma,\sin\sigma)$ differ
by $\pm 2\pi i$. It follows that $p(\sigma)$ also changes sheet with every
turn, and Lemma 2.3 is proved. ∎

Step 4: Construction of $D_{k}$. With $J$ and $\eta$ as chosen in the proof of
Lemma 2.3, we consider the truncated spiral

$X^{\prime}_{k}=\varphi((1/2,1)\times(0,2\pi J+2(k+1)\pi)).$

Using the arguments above we see that $\textsf{E}(X^{\prime}_{k}\times
iB_{r})$ has the required extension properties. Smoothness can be obtained by
rounding off the corners by moving the boundary outside of $X^{\prime}_{k}$,
which results in a slightly larger domain $X_{k}$. The construction of $X_{k}$
and the proof of Theorem 1.1 are complete. ∎

######  Remark 2.4.

(a) Since the family of curved rectangles depends continuously on the central
angle, we obtain a subset of $\textsf{E}(D_{\infty})$ as parametrised in
(2.2). A careful examination of the proof of Lemma 2.3 shows that we can take
$C=2J\pi+\pi/2$, $\rho=\eta/\sqrt{2}$ in (1).

(b) A straightforward modification of the above proof, relying on the
properties of Levi extension, shows that we could have started from an
_arbitrary_ tubular thickening of the central spiral
$\varphi(\\{3/4\\}\times\mathbb{R}_{>0})$. The resulting slight simplification
will be used in the next section.

##  3\. Universally covered circles

Let $D\subset\mathbb{C}^{n}$ be a domain and $\gamma\subset\mathbb{C}^{n}$ an
embedded loop (a curve homeomorphic to the circle) with inclusion
$\iota_{\gamma}:\gamma\hookrightarrow\mathbb{C}^{n}$. A connected component
$\gamma^{\prime}$ of $\pi_{D}^{-1}(\gamma)$ is either (a) a loop or (b) an
arc. In case (a),
$\pi_{D}|_{\gamma^{\prime}}:\gamma^{\prime}\rightarrow\gamma$ is a covering of
$\gamma$ by $\gamma^{\prime}$, whose topology is determined by the number $k$
of sheets over an arbitrary point of $\gamma$ (here $k$ is a positive
integer). Case (b) splits again: (b1)
$\pi_{D}|_{\gamma^{\prime}}:\gamma^{\prime}\rightarrow\gamma$ may be the
universal covering of $\gamma$, i.e. $k=\infty$. (b2) Otherwise,
$\pi_{D}|_{\gamma^{\prime}}$ is not a covering, and the closure of
$\gamma^{\prime}$ in the abstract closure of $\textsf{E}(D)$ contains at least
one point in the abstract boundary.

If the case (b1) is valid, we say also that $\gamma^{\prime}$ _universally
covers $\gamma$_ (and that $\gamma$ is _universally covered by
$\textsf{E}(D)$_). Intuitively, this means that $\textsf{E}(D)$ becomes as
multi-sheeted as possible above $\gamma$. Note that the definition may be
extended to higher-dimensional submanifolds of $\mathbb{C}^{n}$ instead of
$\gamma$.

The goal of this section is to strengthen the construction of $D_{\infty}$ in
the proof of Theorem 1.1.

######  Proposition 3.1.

Assume that $\Pi=\mathbb{R}^{2}$ and $L$ are selected as in the construction
of $X_{2}$ and that $R$ is defined as in (2.1). For every $r\in(0,R)$, there
is a bounded domain $X\subset\mathbb{R}^{2}$ such that the envelope of
holomorphy of $D=X+iB_{r}$ universally covers a circle
$T\subset\mathbb{R}^{2}\backslash X$.

###### Proof.

Since the idea is close to the proof of Theorem 1.1, we will only sketch the
construction. We choose $\Pi=\mathbb{R}^{2}$, $L$ and $R$ as in the
construction of $X_{2}$. Instead of working with a spiral $S_{\epsilon}$
accumulating from outside to $\\{|x|=1\\}$, we start from a spiral contained
in a thin annulus

$A_{\epsilon}=\\{1<|x|<1+\epsilon\\}\subset\mathbb{R}^{2}$

and accumulating at both of its boundary circles ($\epsilon$ will later be
chosen later). Concretely, $S_{\epsilon}$ can be taken as the curve
parametrised by

$\psi_{\epsilon}:\theta\mapsto\left(1+\epsilon\left(\frac{1}{2}+\frac{\arctan{\theta}}{\pi}\right)\right)(\cos\theta,\sin\theta),\
\theta\in\mathbb{R}.$

This spiral accumulates to $T=\\{|x|=1\\}$ for $\theta\rightarrow-\infty$ and
to $\\{|x|=1+\epsilon\\}$ for $\theta\rightarrow\infty$. The domain $X$ (which
also depends on $\epsilon$) is now chosen as a tubular neighbourhood222 i.e. a
domain $X\subset A_{\epsilon}$ containing $S_{\epsilon}$ and admitting a
homeomorphism $S_{\epsilon}\times(-1,1)\rightarrow X$ which restricts to
$(x,0)\mapsto x$ along $S_{\epsilon}\times\\{0\\}$. of $S_{\epsilon}$ in
$A_{\epsilon}$. Its precise shape is not important, but we can arrange that
$X$ is smoothly bounded as a domain in $A_{\epsilon}$ (but not in
$\mathbb{R}^{2}$).

$\\{|x|=1+\epsilon\\}$
---
$\\{|x|=1\\}$
---
$X_{1}$
---
$\theta$
---
$(0,0)$
---
$S_{\epsilon}$
---
$X_{2}$
---
$\theta-\frac{\pi}{2}$
---
$\theta+\frac{\pi}{2}$
---

Figure 3.2. Intersection of $D$ with $\mathbb{R}^{2}$

Fix now $r\in(0,R)$. Similarly as before, we look at segments

$I_{\epsilon}(\theta)=\psi_{\epsilon}(\theta-\pi/2,\theta+\pi/2)\subset
S_{\epsilon},\ \theta\in\mathbb{R},$

which correspond to a change of angle by $\pi$. The key observation is that a
sufficiently small choice of $\epsilon$ guarantees that for _all_
$\theta\in\mathbb{R}$, holomorphic functions defined near
$I_{\epsilon}(\theta)+iB_{r}$ extend to a uniform domain containing the point
$p_{\theta}=(\cos\theta,\sin\theta)$ on the unit circle
$T\subset\mathbb{R}^{2}$. More precisely, we may even arrange that this domain
contains $L_{\epsilon}(\theta)=\big{(}I_{\epsilon}(\theta)\cup
B^{-}_{2\epsilon}(\psi(\theta))\big{)}+iB_{\epsilon}$, where
$B^{-}_{2\epsilon}(\psi(\theta))$ is the connected component of
$B^{-}_{2\epsilon}(\psi(\theta))\backslash I_{\epsilon}(\theta)$ containing
$p_{\theta}$.

We conclude similarly as before. Looking at a univalent branch on $X+iB_{r}$
of the logarithm $f_{L}$ ”around” $L$, we see that every turn along
$S_{\epsilon}$ brings us to a new sheet in the envelope of $D=X+iB_{r}$.
Formally, this can again be expressed by a mapping which associates to every
$\theta\in\mathbb{R}$ the germ at $(\cos\theta,\sin\theta)$ of the holomorphic
extension of the function restricted to a neighbourhood of
$I_{\epsilon}(\theta)+iB_{r}$. Since the sets $L_{\epsilon}(\theta)$ move
continuously with $\theta$, $T$ is universally covered by $\textsf{E}(D)$. ∎

It is crucial for the above construction that the thickness $\epsilon$ of the
annulus decreases with $r$. To explain the reason, let us keep $X$ as in the
proof but replace $D$ by $D^{\prime}=X+iB_{r^{\prime}}$ with $r^{\prime}>0$
arbitrary. If $r^{\prime}$ is small enough, the lines $L_{x}$ through the
points $x\in T$ and parallel to $L$ are disjoint from

$\\{z\in\mathbb{C}^{2}:|x|=1+\epsilon,|y|\leq r^{\prime}\\}.$

Hence for $\theta$ sufficiently large, the hypersurface
$M=I_{\epsilon}(\theta)+iB_{r^{\prime}}$ does not intersect
$L_{(\cos\theta,\sin\theta)}$. This excludes holomorphic extension from $M$ to
a neighbourhood of $(\cos\theta,\sin\theta)$, and the main argument of the
proof breaks down.

##  4\. Schlichtness in dimension $2$

In the above examples, multi-sheetedness was derived from Levi extension
through pseudoconcave parts of the boundary of $D$. Moreover, there were
always pseudoconvex parts of the boundary over which multi-sheetedness was
observed. The goal of the section is to provide some evidence showing that
this interplay is _necessary_ for multi-sheetedness in dimension $2$.

Let $C$ be a smoothly embedded circle in $\mathbb{R}^{2}$. Picking a
parametrisation of $C$ by a smooth, $2\pi$-periodic immersion
$\gamma:\mathbb{R}\rightarrow\mathbb{R}^{2}$ the increment of the angle may be
viewed as a $2\pi$-periodic $1$-form $\alpha(\theta)\,d\theta$. We call $C$
_strictly convex_ if $\alpha(\theta)$ does not vanish (i.e. there are no
inflection points). It is elementary to verify that this notion is well-
defined and that the bounded domain $X_{C,\sf in}$ surrounded by a strictly
convex circle $C$ is convex. By a _convex domain with finitely many strictly
convex holes_ we mean a domain $X\subset\mathbb{R}^{2}$ obtained from a convex
domain $X_{\sf cvx}$ by excision of finitely many disjoint closed discs of the
form $\overline{X}_{C_{j},\sf in}$ where the $C_{j}$ are strictly convex
circles. We will keep these notations in the following arguments.

Proof of Theorem 1.2: The essence of the proof is contained in the treatment
of a special case, which may be viewed as an appropriate deformation of the
model domains (1.1): Assume that $X$ is bounded by two strictly convex circles
$C_{0},C_{1}$, which we number so that $X$ is strictly concave along $C_{1}$,
and set $D=X+iY$, with $Y$ as in the theorem.

For $K\subset\mathbb{C}^{n}$ compact, we recall that

$\widehat{K}=\\{z\in\mathbb{C}^{n}:|p(z)|\leq\max_{K}|p|\mbox{ for each
holomorphic polynomial }p\\}$

denotes its polynomial hull. We obtain the following description of
$\textsf{E}(D)$ in terms of polynomial hulls.

######  Lemma 4.1.

Let $K_{x}$ be the closure of the convex domain bounded by $C_{1}$ and
$K=K_{x}+i\partial Y$. Then $\textsf{E}(D)=D^{\prime}\backslash\widehat{K}$,
where $D^{\prime}=(X\cup K_{x})+iY$. In particular, $\widehat{K}$ does not
disconnect $D^{\prime}$.

The lemma may be viewed as a variant of a classical result by Stout [10] on
extension from parts of strictly pseudoconvex boundaries. For the reader’s
convenience, we sketch an independent proof along the lines of [6], see also
[4] for a related application in dimension $2$.

Proof of Lemma 4.1: There is a nonnegative smooth function
$\varphi\in\mathcal{C}^{\infty}(\mathbb{C}^{2})$ that vanishes precisely on
$\widehat{K}$ and is strictly plurisubharmonic on the complement. Since
$\widehat{K}\subset K_{x}+i\overline{Y}$, we have $\varphi>0$ on $D$. After an
appropriate deformation of $\varphi$, we can in addition assume that
$\varphi|_{\mathbb{C}^{2}\backslash\widehat{K}}$ is a good Morse function333
i.e. a function whose critical points are isolated nondegenerate quadratic
singularities lying on different level sets.. Next we deform $C_{1}\times
i\mathbb{R}^{2}$ such that $C_{1}+i(\mathbb{R}^{2}\backslash Y)$ is fixed and
$C_{1}\times Y$ is moved into $D$. Since $C_{1}\times Y$ is strictly
pseudoconvex hypersurface, a $\mathcal{C}^{2}$-small deformation of this kind
will yield a strictly pseudoconvex hypersurface $M\subset D$. Moreover, $M\cup
K$ bounds a domain $D_{\sf in}\subset D^{\prime}$, which is slightly larger
than $\mbox{int}(K_{x})+iY$. Then $M$ disconnects $D_{\sf in}$ into
$D^{\prime\prime}$ and an outer domain $D_{\sf out}$. Finally we may arrange
in addition that $\varphi|_{M}$ is a good Morse function.

We use the methods from [6] to extend (restrictions to $D_{\sf out}$ of)
holomorphic functions on $D$ to the open sets

$Q_{h}=D_{\sf out}\cup\\{z\in D_{\sf in}:\varphi(z)>h\\},\ h>0.$

We need the following three elementary properties:

  * (i)

$Q_{h}=D_{\sf out}$ for $h\gg 0$,

  * (ii)

$Q_{h_{1}}\subset Q_{h_{2}}$ if $h_{1}>h_{2}$,

  * (iii)

$\bigcup_{h>0}Q_{h}=D^{\prime}\backslash\widehat{K}$.

The idea is to construct extension by continuously letting decrease
$h\downarrow 0$. Assume that the extension to $Q_{h_{0}}$ is valid for some
$h_{0}>0$. If $h_{0}$ is neither a critical value of $\varphi$ nor of
$\varphi|_{M}$, it is not hard to construct extension to $Q_{h_{1}}$ for some
$h_{1}<h_{0}$ by gluing finitely many local Levi extensions through the
strictly pseudoconvex hypersurface $\\{\varphi=h_{0}\\}$. The general case
requires a careful study of the local geometry at Morse singularities. For the
details, we refer to [6]. Note however that the constructions in [6], where
extension from _non_ pseudoconvex boundaries is considered, have to take
transitional multi-sheetedness into account. As explained in [4], these
monodromy problems are easier to handle in our setting, thanks to the strict
pseudoconvexity of $M$.

After constructing extension to $D^{\prime}\backslash\widehat{K}$, the proof
will be ready as soon as we have shown that $D^{\prime}\backslash\widehat{K}$
is pseudoconvex. This follows from the convexity of $D^{\prime}$ and the known
fact that the polynomial hull $\widehat{K}$ is pseudoconcave at points of the
essential hull $\widehat{K}\backslash K$, see for example [9]. ∎

######  Remark 4.2.

Most of the above proof generalises without change to $n\geq 3$, giving
univalent extension from $D$ to $D^{\prime}\backslash\widehat{K}$. At least
for the general case of extension from parts of strictly pseudoconvex
boundaries, it is however known that this need not give the entire envelope
and that the envelope may even be multi-sheeted. ∎

Let us now consider the general case, where we denote by $C_{1},\ldots,C_{m}$
the components of $\partial X$ along which $X$ is strictly concave. For each
$\mu=1,\ldots,m$, we select a similar curve $C_{\mu,1}$ obtained by smoothly
deforming $C_{\mu}$ slightly into $X$. By Lemma 4.1 applied to the domain
$X_{\mu}$ squeezed between $C_{\mu}$ and $C_{\mu,1}$, we have

$\textsf{E}(X_{\mu}+iY)=X^{\prime}_{\mu}\backslash\widehat{K_{\mu}}.$

Here $K_{\mu}=K_{x,\mu}+i\partial Y$ with $K_{x,\mu}$ being the closure of the
convex domain bounded by $C_{\mu}$, and $X^{\prime}_{\mu}=(X_{\mu}\cup
K_{x,\mu})+iY$. By construction,

$\widehat{D}=D\cup\bigcup_{\mu=1}^{m}\textsf{E}(X_{\mu}+iY)$

embeds into the envelope of $D$. To conclude the proof, it just remains to
show that $\widehat{D}$ is pseudoconvex (this is the only place where we use
the properties of the outer boundary component of $\partial X$) and must
therefore coincide with the envelope of holomorphy of $D$. Pseudoconvexity
follows from the convexity of

$D^{\prime}=(X\cup\bigcup_{\mu=1}^{m}K_{x,\mu})+iY$

and the local pseudoconvexity along the essential hulls
$\widehat{K_{\mu}}\backslash K_{\mu}$, used already in the proof of Lemma 4.1.
The proof of Theorem 1.2 is complete. ∎

While the assumption on the strict convexity of the holes can probably be
weakened, we cannot completely omit an assumption on their shape.

######  Example 4.3.

The following example is a variant of our first option of $D_{2}$ in Section
2. Choose $\Pi=\mathbb{R}_{x}^{2}$ and a complex line
$L=\\{az_{1}+bz_{2}=0\\}$ like there. We construct $X^{\prime}$ by adding to
the annulus $A=\\{(x_{1},x_{2})\in\mathbb{R}^{2}:2<|x|<3\\}$ the bridge
$\\{|x_{1}|<1/2\\}\cap B_{3}$ from which we cut away a sufficiently thin bent
channel as indicated in figure 4.3 (the width of the channel corresponding to
$\eta$ in the construction of $D_{2}$).

$(1,0)$
---
$X^{\prime}$
---
$A=\\{|x_{1}|<\frac{1}{2}\\}$
---
$X_{1}$
---
$(-1,0)$
---
$O(0,0)$
---
$\\{|x|=3\\}$
---
$X_{2}$
---
$(2,0)$
---
$(-2,0)$
---

Figure 4.3. The domain $X^{\prime}$ in $\mathbb{R}^{2}$

We choose $r$ such that the closure of $D^{\prime}=X^{\prime}+iB_{r}$ does not
intersect $L_{-1}$ and $L_{1}$, the parallel translates of $L$ passing through
the points $(\pm 1,0)$ respectively. Now the choice of a branch of

$\sqrt{(a(z_{1}+1)+bz_{2})(a(z_{1}-1)+bz_{2})}$ (4.1)

defines a univalent holomorphic function $f$ on $D^{\prime}$. If the channel
is sufficiently thin, $f$ extends from the above part of the interrupted
bridge to a neighbourhood of the origin. Since a single turn around one of the
branch points of (4.1) changes the value we have exhibited two sheets over
$0$. Rounding off the eight corners of $X^{\prime}$ we obtain an example with
a nonconvex hole and a nonschlicht envelope of holomorphy. ∎

It is instructive to relate Lemma 4.1 to the results in [3].

######  Example 4.4.

a) For $D_{2,r_{1},r_{2},r_{3}}$ like in (1.1), it is enough to find the
polynomial hull of the solid torus $K=\overline{B}_{r_{1}}+i\partial
B_{r_{3}}$. By convexity $\widehat{K}$ is contained in the closure of the
polydisc tube $P=\overline{B}_{r_{1}}+i\overline{B}_{r_{3}}$. The function
$g=e^{z_{1}^{2}+z_{2}^{2}}$ has modulus $|g|=e^{|x|^{2}-|y|^{2}}$. Thus
$\max_{K}|g|=r_{1}^{2}-r_{3}^{2}$ is obtained at the boundary $\partial
B_{r_{1}}+i\partial B_{r_{3}}$ of $K$, and we get

$\widehat{K}\subset L=\\{|x|^{2}-|y|^{2}\leq r_{1}^{2}-r_{3}^{2}\\}\cap P.$

To show that this is an equality we only have to observe that $L$ is foliated
by the complex curves $\\{z_{1}^{2}+z_{2}^{2}=c\\}$, $\mbox{Re}(c)\leq
r_{1}^{2}-r_{3}^{2}$ (pairs of discs if $\mbox{Re}(c)=\mbox{Im}(c)$ and annuli
else), with boundary in $K$. Equality then follows from the maximum modulus
principle. Hence we have rederived (1.2) from Lemma 4.1.

For $n\geq 3$, our arguments concerning polynomial hulls are still valid. Thus
Remark 4.2 yields holomorphic extension to the set in (1.2), and then we
conclude by directly verifying that this set is pseudoconvex as in [3]. Note
however that local pseudoconvexity of the complement of $\widehat{K}$ at
points of the essential hull $\widehat{K}\backslash K$ is not true in general
for $n\geq 3$. The hull is still locally $1$-pseudoconcave, but this implies
less pseudoconvexity for the complement.

b) Looking at the ”breaking point” $r_{1}=r_{3}$ leads us to considering

$\Delta=\\{z=x+iy\in\mathbb{C}^{2}:|y|^{2}<|x|^{2}<1\\}.$

With respect to the standard real euclidean structure of
$\mathbb{C}^{2}=\mathbb{R}^{4}$, it is congruent to the Hartogs triangle
$\\{z=(z_{1},z_{2})\in\mathbb{C}^{2}:|z_{2}|^{2}<|z_{1}|^{2}<1\\}$. However,
its function theoretic properties are very different. For example, since
$\overline{\Delta}$ is polynomially convex, $\Delta$ has no Nebenhülle, in
contrast to the Hartogs triangle. ∎

It is rare that polynomial hulls can be described as explicitly as in the
Example 4.4. Therefore there is not much hope for more explicit information
than in Theorem 1.2. It is however possible to deduce qualitative properties
like

######  Corollary 4.5.

Let $D$, $K_{x}$ and $Y$ be like in Lemma 4.1. Assume moreover that $0\in Y$,
and set $Y_{R}=R\cdot Y$, $K_{R}=K_{x}+\partial Y_{R}$, $D_{R}=D+iY_{R}$. Then
the following properties hold:

  * (a)

For every $R_{0}\geq 0$ there is $R_{1}>0$ such that
$\widehat{K}_{R}\cap\\{|y|\leq R_{0}\\}=\emptyset$ if $R\geq R_{1}$.

  * (b)

$\textsf{E}(D+i\mathbb{R}^{2})=\bigcup_{R>0}\textsf{E}(D_{R})$.

Proof: General arguments imply actually that (b) always holds for a family of
subdomains exhausting $D$ in a suitable sense if its is know that all
envelopes of the subdomains are schlicht. Alternatively, it is easy to see
that (a) and (b) are equivalent, again because of schlichtness of the
envelopes.

To verify (a), consider again the Gaussian functions

$f_{\zeta}(z)=\exp\big{(}(z_{1}-\zeta_{1})^{2}+(z_{2}-\zeta_{2})^{2}\big{)}.$

For $R_{0}$ fixed, a direct verification very similar to what is done in
Example 4.4 shows that $\max_{K_{R}}|f_{\zeta}|<c<1$ holds for all
$\zeta=(\zeta_{1},\zeta_{2})\in K_{x}+i\overline{B}_{R_{0}}$, provided $R$ is
sufficiently large. Since $f_{\zeta}(\zeta)=1$, we obtain (a). ∎

## References

  * [1] S. Bochner: A theorem on analytic continuation of functions in several variables. Ann. of Math. 39 (1938), 14–19.
  * [2] M. Jarnicki, P. Pflug: Extension of holomorphic functions. Second edition. Walter de Gruyter 2020.
  * [3] M. Jarnicki, P. Pflug: The envelope of holomorphy of a classical truncated tube domain. Proc. AMS 150(2022),1374–1377.
  * [4] Lind, A., $\&$ Porten, E. (2016). On thickening of holomorphic hulls and envelopes of holomorphy on Stein spaces. International Journal of Mathematics, 27(06), 1650051.
  * [5] J. Merker, E. Porten: Holomorphic Extension of CR Functions, Envelopes of Holomorphy, and Removable Singularities. International Mathematics Research Surveys IMRS, Volume 2006, Article ID 28925, p.1-286 (2006).
  * [6] J. Merker, E. Porten: The Hartogs extension theorem on (n-1)-complete complex spaces. J. Reine Angew. Math. (Crelle Journal) 637, 23-39 (2009).
  * [7] J. Noguchi: A brief proof of Bochner’s tube theorem and a generalized tube. Preprint 2020 on arxiv.org/pdf/2007.04597.pdf.
  * [8] E. Porten: On generalized tube domains over $\mathbb{C}^{n}$. Complex Variables 50, 1-5 (2005).
  * [9] Z. Słodkowski: Analytic set-valued functions and spectra. Math. Ann. 256 (1981), 363–386.
  * [10] E. L. Stout: Analytic continuation and boundary continuity of functions of several complex variables. Proc. Roy. Soc. Edinburgh Sect. A 89 (1981), 63–74.
  * [11] B. M. Weinstock: On the polynomial convexity of the union of maximally totally real subspaces of $\mathbb{R}^{n}$. Math. Ann. 282 (1988), 131–138
  * [12] Buzzard, G., Fornaess, J. E., Gavosto, E. A., & Krantz, S. G. (1995). The Several Complex Variables Problem List. https://arxiv.org/abs/math/9509202v1.