11institutetext:  CNRS, Université Grenoble Alpes, Institut Néel, 38042
Grenoble, France
Department of Physics, School of Advanced Engineering, University of Petroleum
and Energy Studies (UPES), Dehradun, Uttarakhand 248007, India
Earth and Planets Laboratory, Carnegie Institution for Science, 5241 Broad
Branch Road, NW, Washington, DC 20015, USA
Univ. Bordeaux, CNRS, Bordeaux INP, ICMCB, UMR 5026, F-33600 Pessac, France
Normandie Université, ENSICAEN, UNICAEN, CNRS, CRISMAT, 14000 Caen, France

# Lattice dynamics in the FeSi-based family of superconductors

S. Layek (equal contribution) 1122 M. F. Hansen (equal contribution) 1133
J.-B. Vaney 44 P. Toulemonde 11 S. Tencé 22 P. Boullay 55 A. Cano 11 M.-A.
Méasson 111122334455

###### Abstract

The lattice dynamics of the superconducting materials LaFeSiH and LaFeSiO1-δ
as well as their intermetallic precursor LaFeSi are investigated by polarized
Raman spectroscopy and first-principles calculations, together with X-ray and
advanced electron diffraction techniques for their structural analysis. We
find that the Fe-dominated Raman-active modes reflect the chemical
peculiarities of these silicides compared to their pnictide counterparts, with
enhanced structural couplings between the FeSi layer and the spacer that can
be related to the ionic vs covalent character of the latter. In addition, we
find signatures of enhanced electron-phonon coupling for some of the Raman-
active modes. Beyond that, our study reveals intriguing Fe-based Raman
features as well as structural subtleties in LaFeSiH suggesting that this
superconductor may formally be non-centrosymmetric.

##  1 Introduction

Iron-based superconductors provide a distinct realization of unconventional
superconductivity [1, 2] which, in some cases, can be supplemented with
intriguing topological features [3, 4]. These properties motivate a constant
interest in new materials of this class. At present, there are only four
successful compounds in which iron is combined with non-toxic crystallogen
elements: the germanide YFe2Ge2 with superconducting Tc $\sim$ 0.1 K [5, 6, 7]
and the silicides LaFeSiH [8, 9, 10], LaFeSiF [11], and LaFeSiO with Tc = 10 K
[12]. In the case of the silicides, some of their structure-property
relationships challenge previous precepts such as the quasi-universal
correlation between anion height and $T_{c}$ thus calling for further
investigations [12].

In this paper, we address the dynamical structural properties of the FeSi-
based superconductors together with that of their LaFeSi precursor by means of
polarized Raman spectroscopy combined with density-functional-theory (DFT)
calculations and advanced diffraction techniques. The measured phonon
frequencies as well as the observed selection rules are found to be in good
agreement with the calculations. In LaFeSiH, however, we observe a Raman Fe-
based feature displaying an intriguing double-peak shape. Driven by this
observation, we revisit the crystal structure of this system by means of
electron and X-ray diffraction. Furthermore, we elucidate the structural
coupling between the FeSi layer and the La$X$ spacer in these systems from the
trends of the phonon energies, which we discuss also in relation to the ionic
vs covalent character of the spacer as a function of its precise composition
($X=$ empty site, H, or O). In addition, the relative strength of the
electron-phonon interaction is discussed from the Fano shape observed for some
of the Raman-active modes.

##  2 Methods

Single crystals of the intermetallic LaFeSi were extracted from the bulk of an
arc-melted sample with nominal composition La35Fe35Si30. LaFeSiH single
crystals were then obtained by hydrogenation of these crystals at 250°C under
a gas flow of H2 for 4h. Both the LaFeSi precursor and the LaFeSiH
superconductor crystallize in the tetragonal ZrCuSiAs-type structure as
confirmed from single-crystal X-ray diffraction. The samples have sub-
millimeter size and a plate-like shape with the larger faces perpendicular to
the crystallographic c-axis. The LaFeSiO samples, however, are from the same
batch as Ref. [12], which displays an oxygen-site occupancy of $\sim$ 0.9 and
a Tc of 10 K. Specifically, they were obtained by heating powders of LaFeSi at
320 °C in 20%/80% O2/Ar flow for 72 h. Microscopic crystals were then selected
and the shiny faces were assumed to be parallel to the (001) plane as is the
case for the other compounds. From these crystals we obtained well-defined
polarized Raman spectra. However, the perfect orientation of the $a$-axis is
lost in this case and hence the selection rules are almost fully (but not
completely) obeyed.

The Raman spectra of small single crystals were measured under a microscope
attached to a WITec (Model: alpha 300R) confocal Raman spectrometer. A 532 nm
laser line was used for the excitation. The laser power was kept below 1 mW in
order to avoid local overheating and/or damaging the crystals. Macro-Raman as
a function of temperature was performed on a triple-stage spectrometer and in
a cryo-free cryostat down to 9 K. Different polarizations of the light and
orientations of the samples were investigated to access the symmetries of the
excitations.

Precession electron diffraction tomography (PEDT) was performed with a JEOL
F200 cold-FEG transmission electron microscope operated at 200 kV, equipped
with a NANOMEGAS DigiStar precession module and a GATAN RIO16 camera. Samples
for PEDT investigations were prepared by smoothly crushing powder. PEDT data
was processed using the programs PETS 2.0 [13] and Jana2020 [14] (Cf. Suppl.
Mat.).

The DFT calculations were performed with the Quantum ESPRESSO package [15]
using the norm-conserving pseudopotentials from the PseudoDojo library [16].
We used the Perdew-Burke-Ernzerhof form of the generalized gradient
approximation [17]. The calculations were converged with a Monkhorst-Pack mesh
of 13$\times$13$\times$7 $k$-points and a 125 Ry cutoff for the wave functions
with a 0.01 Ry smearing. We used the experimental lattice parameters reported
in ref. [18, 8, 12] and optimized the internal coordinates of the La and Si
atoms.

##  3 Preliminaries

We first recall the nature of the $\Gamma$-point phonons expected in our
systems and their Raman selection rules. The systems under consideration
represent the FeSi-based counterparts of previous 111 and 1111 Fe-based
superconductors with $P4/nmm$ crystal structure ($D_{4h}$ point group) [19].
The contribution of the different atoms to the different $\Gamma$-point
phonons is summarized in Table 1. In the case of the LaFeSi precursor, we then
have two A1g, one B1g and three Eg Raman-active modes. In LaFeSiH and LaFeSiO,
there is an additional B1g Raman-active mode as well as another Eg mode.

In our experiments, the c-axis of the samples is parallel to Poynting vector
of the light. The Eg modes, which are strongly affected by magnetism in
BaFe2As2 [21], are not visible for this configuration. As a result, we then
probe a total of 2A1g \+ B1g and 2A1g \+ 2B1g Raman-active modes in LaFeSi and
LaFeSiH/O, respectively, with selection rules as summarized in Table 2.

These modes are associated with out-of-plane displacements of the atoms. In
the following, we denote these modes as $A_{1g}^{\rm La/Si}$ and $B_{1g}^{\rm
Fe/H/O}$ according to the main contribution to these displacements. However,
these modes generally have a mixed character with dominant and subdominant
displacements of different atoms (Fe-$X$ and Si-La).

Table 1: Atoms and $\Gamma$-point phonons to which they contribute in LaFeSi and LaFeSiH/O. The Raman-active modes are indicated in bold. Atom (Wyckoff position) |  ${\Gamma}$-point modes
---|---
La ($2c$) |  A1g+A2u+Eg+Eu
Fe ($2b$) |  B1g+A2u+Eg+Eu
Si ($2c$) |  A1g+A2u+Eg+Eu
H/O ($2a$) |  B1g+A2u+Eg+Eu
Table 2: Raman selection rules for the $D_{4h}$ point group in Porto’s notation. $a^{\prime}$ stands for the (110) axis.  Polarization geometry |  | Raman-active phonons
---|---|---
$c(aa)\bar{{c}}$ |  | A1g+B1g
$c(a^{\prime}a^{\prime})\bar{{c}}$ |  | A1g+B2g
$c(ba)\bar{{c}}$ |  | A2g+B2g
$c(b^{\prime}a^{\prime})\bar{{c}}$ |  | A2g+B1g

[width=]4-Panel.eps

Figure 1:  Polarized Raman spectra of LaFeSi, LaFeSiH and LaFeSiO single
crystals measured at room temperature. The configuration of the polarization
is indicated in Porto’s notation, with the selected Raman modes in bold. Black
and red curves represent data from different samples. The insets show optical
images of the samples. For LaFeSiO, star and losange symbols indicate a signal
from the optical fiber in the setup and ‘leakage’ from A1g modes,
respectively, while circles indicate an additional high-energy feature,
probably related to a multi-phonon process.

##  4 LaFeSi precursor

The Figure 1a) shows the polarized Raman spectra obtained on single crystals
of the LaFeSi precursor at room temperature. The symmetry of the Raman-active
phonons behind the observed peaks are deduced by changing the polarization
geometry according to Table 2. We clearly identify the three modes
$A_{1g}^{\rm La}$, $A_{1g}^{\rm Si}$, and $B_{1g}^{\rm Fe}$. This
identification is additionally supported by the DFT calculations (see Table
3), which also provide the main atomic character of these modes.

##  5 Superconducting LaFeSiH

The polarized Raman spectra obtained from single crystals of LaFeSiH are shown
in Figure 1b). In addition to the three modes $A_{1g}^{\rm La}$, $A_{1g}^{\rm
Si}$, and $B_{1g}^{\rm Fe}$, we observe the mode corresponding to $B_{1g}^{\rm
H}$. The frequencies of these modes are in reasonable agreement with the
calculations (see Table 3), which again provide the main atomic character of
these modes.

Table 3: Frequencies of the different $\Gamma$-point phonons of the
investigated silicides together with their symmetries. In the case of the
Raman-active modes observed in our experimental setup (i.e. $A_{1g}$ and
$B_{1g}$), the main atomic displacements are indicated with the superscripts.

LaFeSi | LaFeSiH | LaFeSiO
---|---|---
Frequency (cm-1) |  | Mode | Frequency (cm-1) |  | Mode | Frequency (cm-1) |  | Mode
Experimental | Calculated |  | symmetry | Experimental | Calculated |  | symmetry | Exp. | Cal. |  | symmetry
| 96 |  | $E_{g}$ |  | 98 |  | $E_{g}$ |  | 79 |  | $E_{u}$
112.6 | 123 |  | $A_{1g}^{\rm La}$ |  | 115 |  | $E_{u}$ |  | 106 |  | $A_{2u}$
| 148 |  | $E_{u}$ | 146.4 | 120 |  | $A_{1g}^{\rm La}$ |  | 123 |  | $E_{g}$
| 152 |  | $A_{2u}$ |  | 122 |  | $A_{2u}$ | 164.4 | 156 |  | $B_{1g}^{\rm Fe}$
| 209 |  | $E_{g}$ |  | 178 |  | $E_{g}$ |  | 179 |  | $E_{g}$
205.6 | 218 |  | $B_{1g}^{\rm Fe}$ | 222.8, 228.5 | 228 |  | $B_{1g}^{\rm Fe}$ | 186 | 186 |  | $A_{1g}^{\rm La}$
250.0 | 313 |  | $A_{1g}^{\rm Si}$ | 279 | 289 |  | $A_{1g}^{\rm Si}$ | – | 272 |  | $B_{1g}^{\rm O}$
| 322 |  | $A_{2u}$ |  | 315 |  | $A_{2u}$ |  | 282 |  | $A_{2u}$
| 364 |  | $E_{u}$ |  | 403 |  | $E_{u}$ |  | 295 |  | $E_{u}$
| 372 |  | $E_{g}$ |  | 407 |  | $E_{g}$ | 260 | 297 |  | $A_{1g}^{\rm Si}$
|  |  |  | 809.2 | 792 |  | $B_{1g}^{\rm H}$ |  | 389 |  | $A_{2u}$
|  |  |  |  | 809 |  | $E_{u}$ |  | 414 |  | $E_{g}$
|  |  |  |  | 822 |  | $A_{2u}$ |  | 414 |  | $E_{u}$
|  |  |  |  | 847 |  | $E_{g}$ |  | 433 |  | $E_{g}$

[width=8cm]2-panel_LT_LaFeSiH.eps

Figure 2: Temperature dependence of the polarized Raman spectra on a third
LaFeSiH single crystal, at 300 K, 100 K and 9 K. Spectra are shifted for
clarity. The inset in a) shows that the distance between the maxima of the
two-peak feature at 228 cm-1 is constant with temperature.

In the measured spectra, however, the $B_{1g}^{\rm Fe}$ mode at $\sim$228 cm-1
appears as a double-peak feature. This is surprising because, even if this
mode involves dominant Fe and subdominant H displacements, it should be a
single non-degenerate mode. Accordingly, a symmetry breaking, for example,
cannot produce such splitting. Furthermore, as shown in Fig. 2, no new modes
or new splittings appear as a function of temperature and in none of the four
probed symmetries, which is consistent with the absence of a structural
transition associated with magnetism reported in [20]. The B1g double-peak
feature, however, persists down to 9 K as seen Fig. 2(a) and both the position
of its two maxima and overall width remain quite constant. Note that the Raman
inactive modes are relatively far in frequency from this feature (see Table
3), so that the Raman activation of some of these modes due to a structural
change could hardly explain this observation (unless the change would be quite
substantial).

The double-peak at $\sim 228$ cm-1 is robust, in the sense that it is
systematically observed in all the samples at the same frequency with similar
relative intensities. Thus, even if the light only penetrates $\sim$ 40 nm in
this type of compounds, it should not be a surface artifact. In fact, the
incomplete hydrogenation at the surface as well as a partial oxydation can be
excluded by noting that the frequencies and FWHM of corresponding B1g modes in
the LaFeSi precursor and LaFeSiO (see below) are very different. Thus, we
conclude that such a double-peak feature is LaFeSiH specific and has an
intrinsic character.

However, according to the above, that feature cannot be easily explained
within the $P4/nmm$ structural model of LaFeSiH and hence questions the
accuracy of such a model. Thus, we used PEDT to carefully revisit the
structure of this system. As explained in the Supplemental Material, the
analysis of the PEDT data confirms the atomic positions and the site
occupancies previously derived from X-ray diffraction [8]. However, it also
reveals the presence of additional weak reflections as illustrated in Fig. 3,
that suggests the absence of the $n$-glide plane symmetry. The PEDT refinement
also displays a residual density close to the Si sites, if the $P4/nmm$
structure is assumed. These observations thus confirm that the ideal $P4/nmm$
model does not accurately capture all the structural details of the samples.
To confirm the presence of these extra reflections, inferring that the actual
structure would be non-centrosymmetric, we then performed additional single-
crystal X-ray diffraction measurements.

However, due to their very weak intensity in both PEDT and X-ray diffraction,
we could not determine the crystal structure of these systems more accurately.
At the same time, we note that the extra reflections could also be due to the
presence of stacking faults along $c$. In any case, the actual structure of
these systems seems to be immeasurably close to $P4/nmm$ while the Raman
double-peak feature observed in LaFeSiH is visibly a much stronger effect.
These observations then remain open questions.

[width=.475]PEDT1.eps

Figure 3:  Electron diffraction pattern obtained for LaFeSiH at the $hk0$
plane. The green circle indicates the 310 reflection expected according to the
$P4/nmm$ structure. The reflections encircled in red, however, are
incompatible with $n$-glide plane symmetry. The Fourier-difference map
obtained after the PEDT refinement is superimposed to the ball-and-stick model
of the corresponding $P4/nmm$ structure using VESTA[22]. This map shows
residual densities close to Si sites (isosurface levels with
3$\sigma$[$\Delta$V(r)] are in yellow).

##  6 Superconducting LaFeSiO

The polarized Raman spectra obtained from LaFeSiO are shown in Fig. 1c).
First, in the parallel polarized configuration we clearly observe two A1g
modes, at 187 cm-1 and 260 cm-1. The mode measured at 165 cm-1 is assigned to
the $B_{1g}^{\rm Fe}$ mode. In these measurements, however, the polarization
of light with respect to the $a$ axis is not perfect, so that there is no full
extinction of the B1g modes. Yet, we observe significant changes in the peak
intensities from which the symmetry of the corresponding modes can be deduced.
The relative intensity of the A1g modes, for example, remains constant in
parallel polarization when the polarization angle changes within the $ab$
plane.

The $B_{1g}^{\rm O}$ mode is not immediately identifiable given the present
data. This mode is expected at 272 cm-1 according to our calculations and
should be observable in the same configuration as the $B_{1g}^{\rm Fe}$ mode.
We do observe intensity at 262 cm-1 but it is more likely attributed to a
”leakage” of the $A_{1g}^{\rm Si}$ (marked with a losange in Fig. 1),
similarly to the ”leakage” of the $A_{1g}^{\rm La}$ mode measured at about 182
cm-1. In addition, a broad peak, marked with a circle, is measured at 672
cm-1. It seems to be active in the A1g channel. When considering leakage of Eg
modes, the closest Eg mode is calculated to be at 433 cm-1 and hence excludes
such a possibility. In fact, there is no $\Gamma$-point phonon matching that
frequency. This high-energy feature may thus be related with a scattering
process involving multiple phonons with finite wavevectors.

##  7 Comparative analysis

To gain further insight about the structural properties of the above systems,
we perform a comparative analysis in this section. The most relevant Raman
features are summarized in Fig. 4 (see also Table 3).

First, we discuss the modes associated with the FeSi layer. We note that the
frequency of the $B_{1g}^{\rm Fe}$ mode in LaFeSi and LaFeSiH is comparable to
that of the reference compounds LaFeAsO (201 cm-1) and SmFeAsO (208 cm-1)
reported in [23]. This mode, however, becomes considerably softer in LaFeSiO.
This dynamical peculiarity adds to another, static one: a strikingly reduced
distance between the Si and the Fe plane in this system [12]. Further, we note
that the $B_{1g}^{\rm Fe}$ and $A_{1g}^{\rm As}$ modes are quasi degenerate in
the above arsenides, while the frequencies of the $B_{1g}^{\rm Fe}$ and the
$A_{1g}^{\rm Si}$ modes are quite different in the silicides with the latter
being harder (also compared with the $A_{1g}^{\rm As}$ ones). The non-
degeneracy of these modes suggests that the structural coupling of the FeSi
layer to the spacer is more important in the silicides. The above trends are
confirmed in the calculations.

Next, we discuss the modes associated with the spacer. The $A_{1g}^{\rm La}$
becomes progressively harder from LaFeSi, to LaFeSiH then to LaFeSiO. This can
be related to the insertion of the light element within the spacer and its
electronegativity. The observed trend then suggests that the ionic character
of the spacer increases with increasing electronegativity of the inserted
element, thereby hardening the $A_{1g}^{\rm La}$ mode. At the same time, we
also note that the frequency of this mode in LaFeSiO is higher compared to
that in LaFeAsO. This can be associated with the subdominant contribution of
the Si displacements, which again suggests an enhanced structural coupling
between the FeSi layer and the spacer. Since this is eventually determined by
the corresponding chemical bonds, the electronic structure of these silicides
can be expected to be more three-dimensional in general with low-energy
details near the Fermi level more sensitive to changes in the spacer.

[width=8cm]Comparison.eps

Figure 4: Experimental Raman spectra of (a) LaFeSi, (b) LaFeSiH and (c) LaFeSiO as measured at T = 300 K. The theoretically calculated positions of the phonon modes are marked below the data as ticks and arrows for the non-degenerate and degenerate modes, respectively. The insets show the Raman features associated with the B${}_{1g}^{\rm Fe}$ mode, whose fitting requires two peaks in LaFeSiH. Table 4: Fano parameter $10^{3}\cdot\frac{1}{q^{2}}$ for the two A1g modes mainly associated with La and Si. The corresponding fits are shown in Fig. 3 of the Supplementary Material. The higher $\frac{1}{q^{2}}$, the stronger the Fano effect is. | A${}_{1g}^{\rm La}$ | A${}_{1g}^{\rm Si}$
---|---|---
LaFeSi | 32(3.4) | 11(2.1)
LaFeSiH | 3.5(0.8) | 3.5(0.4)
LaFeSiO | 27(4.4) | 2.1(0.4)

Finally, we note that, in general, the $A_{1g}$ Raman peaks in the silicides
display a Fano shape that is more apparent compared to their arsenide
counterparts [23] (see Table 4). In addition, we observe a significant
broadening of the $A_{1g}^{\rm La}$ mode from 5 cm-1 in the LaFeSi precursor
to $\sim$10.5 cm-1 in LaFeSiH and LaFeSiO.

These differences can be due to enhanced electron-phonon couplings for these
particular $\Gamma$-point modes. In relation to superconductivity, however,
the most relevant couplings involve the Fe-dominated modes and, in any case,
the strength of the overall coupling according to DFT calculations remains too
weak to explain the superconducting $T_{c}$ of LaFeSiH for example [24].

##  8 Conclusion

Our combined analysis of the lattice dynamics of Fe-based superconducting
silicides reveals that, compared with their arsenide counterparts, the
structural coupling between the FeSi layer and the spacer is stronger. This
dynamics is also found to be affected by the change from covalent to more
ionic bonds within the spacer across the LaFeSi$X$ series ($X=$ empty site, H,
and O). Consequently, despite their layered structure, the effective 2D
behavior is different in these systems. Intriguingly, the Raman spectrum of
LaFeSiH displays a double-peak feature that cannot be easily explained
according to the ideal $P4/nmm$ crystal structure of these systems. Besides,
detailed electron and X-ray diffraction suggests that the structure may in
reality be non-centrosymmetric. Thus, it would be interesting to determine the
structure of these systems more accurately and, if the absence of
centrosymmetry is confirmed, to further investigate the superconducting
properties of Fe-based silicides from that perspective.

###### Acknowledgements.

This work was supported by the French Agence Nationale de la Recherche (ANR
IRONMAN, Grant No. ANR-18-CE30-0018-03) and the Labex LANEF du Programme
d’Investissements d’Avenir (grant No. ANR-10-LABX-51-01). We thanks Etienne
Gaudin for fruitful discussion. Contributions: MAM conceived the work and
supervised the project with AC. JBV and ST synthetized the LaFeSi(H) samples
and performed XRD measurements. MH and PT synthetized LaFeSiO. PB performed
and analysized the PEDT measurements. SL and MH performed the Raman
experiments with the support of MAM. AC performed the ab-initio calculations.
MAM, AC and MH discussed the results and wrote the manuscript, with
contributions from all the authors.

## References

  * [1] Hosono H. Kuroki K. Physica C: Superconductivity and its Applications5142015399.
  * [2] Alloul H. Cano A. Comptes Rendus Physique1720161.
  * [3] Zhang P., Yaji K., Hashimoto T., Ota Y., Kondo T., Okazaki K., Wang Z., Wen J., Gu G. D., Ding H. Shin S. Science3602018182.
  * [4] Zhang P., Wang Z., Wu X., Yaji K., Ishida Y., Kohama Y., Dai G., Sun Y., Bareille C., Kuroda K., Kondo T., Okazaki K., Kindo K., Wang X., Jin C., Hu J., Thomale R., Sumida K., Wu S., Miyamoto K., Okuda T., Ding H., Gu G. D., Tamegai T., Kawakami T., Sato M. Shin S. Nature Physics15201941.
  * [5] Zou Y., Feng Z., Logg P. W., Chen J., Lampronti G. Grosche F. M. physica status solidi (RRL) - Rapid Research Letters82014928.
  * [6] Kim H., Ran S., Mun E., Hodovanets H., Tanatar M., Prozorov R., Bud’ko S. Canfield P. Philosophical Magazine952015804.
  * [7] Chen J., Semeniuk K., Feng Z., Reiss P., Brown P., Zou Y., Logg P. W., Lampronti G. I. Grosche F. M. Physical Review Letters1162016127001.
  * [8] Bernardini F., Garbarino G., Sulpice A., Núñez-Regueiro M., Gaudin E., Chevalier B., Méasson M.-A., Cano A. Tencé S. Physical Review B972018.
  * [9] Bhattacharyya A., Rodière P., Vaney J.-B., Biswas P. K., Hillier A. D., Bosin A., Bernardini F., Tencé S., Adroja D. T. Cano A. Physical Review B1012020224502.
  * [10] Hansen M., Vaney J.-B., De Rango P., Salaün M., Tencé S., Nassif V. Toulemonde P. Journal of Alloys and Compounds9452023169281.
  * [11] Vaney J.-B., Vignolle B., Demourgues A., Gaudin E., Durand E., Labrugère C., Bernardini F., Cano A. Tencé S. Nature Communications1320221462.
  * [12] Hansen M. F., Vaney J.-B., Lepoittevin C., Bernardini F., Gaudin E., Nassif V., Méasson M.-A., Sulpice A., Mayaffre H., Julien M.-H., Tencé S., Cano A. Toulemonde P. npj Quantum Materials7202286.
  * [13] Palatinus L., Brázda P., Jelínek M., Hrdá J., Steciuk G. Klementová M. Acta Crystallographica Section B Structural Science, Crystal Engineering and Materials752019512.
  * [14] Petříček V., Dušek M. Palatinus L. Zeitschrift für Kristallographie - Crystalline Materials2292014345.
  * [15] Giannozzi P., Baroni S., Bonini N., Calandra M., Car R., Cavazzoni C., Ceresoli D., Chiarotti G. L., Cococcioni M., Dabo I., Dal Corso A., de Gironcoli S., Fabris S., Fratesi G., Gebauer R., Gerstmann U., Gougoussis C., Kokalj A., Lazzeri M., Martin-Samos L., Marzari N., Mauri F., Mazzarello R., Paolini S., Pasquarello A., Paulatto L., Sbraccia C., Scandolo S., Sclauzero G., Seitsonen A. P., Smogunov A., Umari P. Wentzcovitch R. M. Journal of Physics: Condensed Matter212009395502.
  * [16] van Setten M., Giantomassi M., Bousquet E., Verstraete M., Hamann D., Gonze X. Rignanese G.-M. Computer Physics Communications226201839.
  * [17] Perdew J. P., Burke K. Ernzerhof M. Physical Review Letters7719963865.
  * [18] Welter R., Venturini G. Malaman B. Journal of Alloys and Compounds189199249.
  * [19] Ivantchev S., Kroumova E., Madariaga G., Pérez-Mato J. M. Aroyo M. I. Journal of Applied Crystallography3320001190.
  * [20] Hansen M. F., Layek S., Vaney J. B., Chaix L., Suchomel M. R., Mikolasek M., Garbarino G., Chumakov A., Rüffer R., Nassif V., Hansen T., Elkaim E., Pelletier T., Mayaffre H., Bernardini F., Sulpice A., Núñez-Regueiro M., Rodière P., Cano A., Tencé S., Toulemonde P., Julien M. H. d’Astuto M. Magnetic and structural properties of the iron silicide superconductor lafesih (2023).
  * [21] Chauvière L., Gallais Y., Cazayous M., Sacuto A., Méasson M. A., Colson D. Forget A. Physical Review B802009.
  * [22] Momma K. Izumi F. Journal of Applied Crystallography4420111272.
  * [23] Hadjiev V. G., Iliev M. N., Sasmal K., Sun Y.-Y. Chu C. W. Physical Review B772008220505.
  * [24] Hung L. Yildirim T. Phys. Rev. B972018224501.


A}^{\circ}\rangle=\sum_{e\in\overline{E}}{{\langle}\rightarrow,e|}w_{\cal
A}\rangle\sqrt{\frac{2}{{\sf r}^{e}}}{{\lvert}\hat{w}_{\cal
A}^{e}\rangle}+\Pi_{E\setminus\overline{E}}{\lvert}w_{\cal A}\rangle$

is a negative witness for $G^{\circ}$.

###### Proof.

We will use the fact that if a switch is off, we always have
$\Pi_{e}{\lvert}w_{\cal A}\rangle={{\langle}\rightarrow,e|}w_{\cal
A}\rangle({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle)$. This is
true because a switch that is off always has $\Xi_{e}^{\cal
A}=\mathrm{span}\\{{\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle\\}$.
In particular, this means that $\Pi_{\overline{E}}{\lvert}\hat{w}_{\cal
A}\rangle\in\Xi_{\overline{E}}^{-}$, so since ${\lvert}\hat{w}_{\cal
A}\rangle+{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle\in{\cal
B}_{G}$, in particular, it is in ${\cal B}_{G}^{-}$. We have:

$\displaystyle{\lvert}\hat{w}_{\cal
A}\rangle+{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle$
$\displaystyle\in{\cal B}_{G}^{-}$
$\displaystyle\Pi_{E\setminus\overline{E}}{\lvert}\hat{w}_{\cal
A}\rangle+\sum_{e\in\overline{E}}{{\langle}\rightarrow,e|}w_{\cal
A}\rangle({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle)+{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle$
$\displaystyle\in{\cal B}_{G}^{-}$
$\displaystyle\Lambda\left(\Pi_{E\setminus\overline{E}}{\lvert}\hat{w}_{\cal
A}\rangle+\sum_{e\in\overline{E}}{{\langle}\rightarrow,e|}w_{\cal
A}\rangle({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle)+{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle\right)$
$\displaystyle\in{\cal B}_{G^{\circ}}$
$\displaystyle\Pi_{E\setminus\overline{E}}{\lvert}\hat{w}_{\cal
A}\rangle+\sum_{e\in\overline{E}}{{\langle}\rightarrow,e|}w_{\cal
A}\rangle\sqrt{2}{\lvert}\bar{b}_{1}^{e}\rangle+{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle$
$\displaystyle\in{\cal B}_{G^{\circ}}$ $\displaystyle{\lvert}\hat{w}_{\cal
A}^{\circ}\rangle+\sum_{e\in\overline{E}}{{\langle}\rightarrow,e|}w_{\cal
A}\rangle\sqrt{\frac{2}{{\sf r}^{e}}}\left(\sqrt{{\sf
r}^{e}}{\lvert}\bar{b}_{1}^{e}\rangle-{\lvert}\hat{w}_{\cal
A}^{e}\rangle\right)+{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle$
$\displaystyle\in{\cal B}_{G^{\circ}}.$

We complete the proof by noting that for all $e\in\overline{E}$, $\sqrt{{\sf
r}^{e}}{\lvert}\bar{b}_{1}^{e}\rangle-{\lvert}\hat{w}_{\cal
A}^{e}\rangle\in{\cal B}_{G^{\circ}}$. To see this, we note:

${\lvert}\hat{w}_{\cal
A}^{e}\rangle+{\lvert}\leftarrow,s\rangle-{\lvert}\rightarrow,t\rangle\in{\cal
B}_{G^{e}}^{-}\cap\mathrm{span}\\{{\lvert}b_{0}^{e}\rangle\\}^{\bot},$

which follows from the fact that ${\lvert}\hat{w}_{\cal A}^{e}\rangle$ is a
cropped negative witness, and so it is orthogonal to
${\lvert}\leftarrow,s^{e}\rangle$ and ${\lvert}\rightarrow,t^{e}\rangle$, and
in particular,
${\lvert}b_{0}^{e}\rangle=\frac{1}{\sqrt{2}}({\lvert}\leftarrow,s^{e}\rangle+{\lvert}\rightarrow,t^{e}\rangle)$.
The only other basis vector of ${\cal B}_{G^{e}}^{-}$ that overlaps
${\lvert}\leftarrow,s^{e}\rangle$ and ${\lvert}\rightarrow,t^{e}\rangle$ is
${\lvert}b_{1}^{e}\rangle\propto{\lvert}\leftarrow,s^{e}\rangle-{\lvert}\rightarrow,t^{e}\rangle+\sqrt{{\sf
r}^{e}}{\lvert}\bar{b}_{0}^{e}\rangle$, from which it follows:

${\lvert}\hat{w}_{\cal A}^{e}\rangle-\sqrt{{\sf
r}^{e}}{\lvert}\bar{b}_{0}^{e}\rangle\in{\cal
B}_{G^{e}}^{-}\cap\mathrm{span}\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}^{\bot}\subset{\cal
B}_{G^{\circ}}.\qed$

###  4.2 Boolean Formula Composition

In this section, we give a subspace graph computing $\varphi\circ(f_{e})_{e}$
when $\varphi$ is a symmetric formula, given subspace graphs for each $f_{e}$.
Subspace graphs for $\varphi$ can be obtained simply by composing the
switching networks for OR and AND in Section 3.3.1 and Section 3.3.2 (see
[JK17]). Our composition theorem, Theorem 4.1, generalizes this simple
switching network composition. We will use the following lemma.

######  Lemma 4.9.

Let $G$ be an $st$-composable subspace graph with scaling factor ${\sf r}=2$,
and $\hat{W}_{-}(G)>1$. Then there is an $st$-composable subspace graph
$G^{\prime}$ with scaling factor ${\sf r}=2$, $\dim H_{G^{\prime}}=\dim
H_{G}+O(1)$, $\hat{W}_{-}(G^{\prime})=2$,
$\hat{W}_{+}(G^{\prime})\leq\hat{W}_{+}(G)(\hat{W}_{-}(G)-1)$ and whose bases
can be generated in the same cost as $G$, up to additive constants.

###### Proof.

The proof is similar to that of Corollary 4.2, except that we compose $G$ into
the edge $e_{2}$ of the graph in Lemma 3.15, using weights ${\sf
w}_{2}=(\hat{W}_{-}(G)-1)^{-1}$ and ${\sf w}_{1}=1-{\sf w}_{2}$. ∎

######  Lemma 4.10.

Let $\varphi$ be a symmetric formula (Definition 2.3) on $\\{0,1\\}^{\Sigma}$.
Let $\\{f_{\sigma}\\}_{\sigma\in\Sigma}$ be Boolean functions, and for each
$\sigma\in\Sigma$, let $G_{\sigma}$ be an $st$-composable subspace graph
(Definition 3.8) computing $f_{\sigma}$, with working bases that can be
generated in time at most $T$ with scaling factor ${\sf r}^{\sigma}=2$, and
$\log\dim H_{G_{\sigma}}\leq S$. Suppose that for each $\sigma\in\Sigma$,
${\sf C}_{\sigma}$ is a known upper bound on $\hat{\cal C}(G_{\sigma})$. For
any $\sigma\in\Sigma\setminus\overline{\Sigma}$ (i.e. proper prefixes of the
strings in $\Sigma$), if the children of $\sigma$ in $\varphi$ are labelled by
$[d]$, define

${\sf C}_{\sigma}=\sqrt{\sum_{i\in[d]}{\sf C}_{i}^{2}},$

and suppose a state proportional to $\sum_{i\in[d]}{\sf
C}_{i}{\lvert}i\rangle$ can be generating in cost $O(\log d)$. Then there is
an $st$-composable subspace graph $G^{\circ}$ computing
$\varphi\circ(f_{\sigma})_{\sigma\in\Sigma}$ with $\log\dim
H_{G^{\circ}}=S+O(\log|\Sigma|)$ and

$\hat{\cal C}(G^{\circ})^{2}\leq\left(\sum_{\sigma\in\Sigma}{\sf
C}_{\sigma}^{2}\right).$

Furthermore, the working bases of $G^{\circ}$ can be generated in time
$T+O(\log|\Sigma|)$ with scaling factor ${\sf r}=2$.

We note that requiring the formula to be symmetric is more stringent than
necessary, but it greatly simplifies things, in particular the time complexity
analysis, and covers most cases of interest, including our application. A
similar statement holds for balanced formulas (which, in particular, have
$O(\log|\Sigma|)$ depth), but the complexity of generating the basis then
depends on the complexity of generating more complicated states.

###### Proof of Lemma 4.10.

First note that

${\sf C}^{2}={\sf C}_{\emptyset}^{2}=\sum_{\sigma\in\Sigma}{\sf
C}_{\sigma}^{2}.$

Let $a$ be a constant such that the bases referred to in Lemma 3.15 and Lemma
3.19 can both be generated in complexity at most $a\log d$, and let
$a^{\prime}$ be a constant such that the cost of generating the basis of
$G^{\circ}$ in Theorem 4.1 is $T+T^{\prime}+a^{\prime}$.

Without loss of generality, we can assume that none of the leaves of $\varphi$
is negated, because if it is, we can just push this negation into
$f_{\sigma}$. The proof will be by induction on the depth of $\varphi$.

We define integers $c_{D}$ recursively, as follows. We let $c_{0}=2$. For
$D>0$, if the nodes of $\varphi$ at distance $D$ from the leaves are labelled
by $\vee$, we let $c_{D}=c_{D-1}$, and if they are labelled by $\wedge$, and
have $d_{D}$ children, we let $c_{D}=d_{D}c_{D-1}$.

By Lemma 4.9, we can assume that for each $\sigma\in\Sigma$, $G_{\sigma}$ has
scaling factor ${\sf r}^{\sigma}=2$ and $\hat{W}_{-}(G_{\sigma})=2$. We will
show by induction on the depth $D$ of $\varphi$, the existence of a subspace
graph with $\hat{W}_{-}(G)=c_{D}$, $\hat{W}_{+}(G)\leq{\sf C}^{2}/c_{D}$ and
scaling factor ${\sf r}=2$, $\log\dim H_{G}\leq\log|\Sigma|+2D+S$, and basis
generation cost $T+(a+a^{\prime})\log|\Sigma|$.

##### Base Case:

If $D=0$, then $\varphi\circ(f_{\sigma})_{\sigma\in\Sigma}=f_{\sigma}$ for
some $\sigma$. Then we just take $G^{\circ}=G_{\sigma}$, and the result
follows, using ${\sf C}_{\sigma}^{2}\geq\hat{\cal C}(G_{\sigma})^{2}$ and the
assumptions ${\sf r}_{\sigma}=2$ and $\hat{W}_{-}(G_{\sigma})=2=c_{0}$.

##### OR Case:

First, suppose $\varphi$ has depth $D>0$, with
$\varphi=\bigvee_{i=1}^{d}\varphi_{i}$ for some formulas of depth $D-1$, and
$d=d_{D}$. Let $G=G_{\textsc{or},d}$ be the subspace graph from Lemma 3.15,
which is $st$-composable, because it is a switching network, and let
$G_{\varphi_{1}},\dots,G_{\varphi_{d}}$ be the $st$-composable subspace graphs
whose existence is promised by the induction hypothesis. For all $i\in[d]$, we
will compose the graphs $G_{\varphi_{i}}$ into the switch edge $e_{i}$ of $G$
using Theorem 4.1, to obtain $G^{\circ}$. If $\varphi_{i}(x)=1$ for some $i$,
then $G_{\varphi_{i}}$ must have some cropped positive witness
${\lvert}\hat{w}^{i}\rangle$, and using the cropped positive witness
${\lvert}\hat{w}\rangle$ from Lemma 3.15, by Theorem 4.1, $G^{\circ}$ has a
cropped positive witness

${\lvert}\hat{w}^{\circ}\rangle=\sqrt{\frac{{\sf
r}^{i}}{2}}\frac{1}{\sqrt{{\sf
w}_{i}}}{\lvert}\hat{w}^{i}\rangle=\frac{1}{\sqrt{{\sf
w}_{i}}}{\lvert}\hat{w}^{i}\rangle,$

where ${\sf r}^{i}=2$ is the scaling factor of the basis for
$G_{\varphi_{i}}$. Thus, if we choose

${\sf w}_{i}=\frac{{\sf C}_{i}^{2}}{{\sf C}^{2}},\quad\mbox{so}\quad{\sf
r}=2\sum_{i=1}^{d}{\sf w}_{i}=2\frac{\sum_{i=1}^{d}{\sf C}_{i}^{2}}{{\sf
C}^{2}}=2$

we get

$\hat{W}_{+}(G^{\circ})\leq\frac{1}{{\sf
w}_{i}}\hat{W}_{+}(G_{\varphi_{i}})\leq\frac{{\sf C}^{2}}{{\sf
C}_{i}^{2}}\frac{{\sf C}_{i}^{2}}{c_{D-1}}=\frac{{\sf C}^{2}}{c_{D}}$

by the induction hypothesis, which says that
$\hat{W}_{+}(G_{\varphi_{i}})\leq{\sf C}_{i}^{2}/c_{D-1}$, and
$c_{D}=c_{D-1}$, since the node at height $D$ is labelled $\vee$.

On the other hand, suppose for all $i\in[d]$, $\varphi_{i}(x)=0$ and so there
exists a cropped negative witness ${\lvert}\hat{w}_{\cal A}^{i}\rangle$ for
$G_{\varphi_{i}}$. Then using the cropped negative witness from Lemma 3.15, by
Theorem 4.1, we have a cropped negative witness for $G^{\circ}$:

${\lvert}\hat{w}^{\circ}_{\cal A}\rangle=\sum_{i=1}^{d}\sqrt{\frac{2}{{\sf
r}^{i}}}\sqrt{{\sf w}_{i}}{\lvert}\hat{w}^{i}_{\cal
A}\rangle=\sum_{i=1}^{d}\sqrt{{\sf w}_{i}}{\lvert}\hat{w}^{i}_{\cal
A}\rangle.$

Thus:

$\hat{W}_{-}(G^{\circ})\leq\sum_{i=1}^{d}{{\sf
w}_{i}}\hat{W}_{-}(G_{\varphi_{i}})\leq\sum_{i=1}^{d}\frac{{\sf
C}_{i}^{2}}{{\sf C}^{2}}c_{D-1}=c_{D-1}=c_{D},$

by the induction hypothesis.

The sub-formula $\varphi_{i}$ has leaves $\Sigma_{i}$, and by the fact that
$\varphi$ is symmetric, $|\Sigma_{i}|=|\Sigma|/d$, so by the induction
hypothesis, the cost of generating the bases for any $G_{\varphi}$ is at most:

$T^{\prime}\colonequals T+(a+a^{\prime})\log\left(|\Sigma|/d\right).$

Thus, by Theorem 4.1, since the bases of $G$ can be generated in cost at most
$T^{\prime\prime}=a\log d$, we can generate the bases of $G^{\circ}$ in cost

$T^{\prime\prime}+T^{\prime}+a^{\prime}\leq
T+(a+a^{\prime})\log(|\Sigma|/d)+(a+a^{\prime})\log
d=T+(a+a^{\prime})\log(|\Sigma|),$

as needed. Here we assumed a state proportional to $\sum_{i}\sqrt{{\sf
w}_{i}}{\lvert}i\rangle\propto\sum_{i}{\sf C}_{i}{\lvert}i\rangle$ can be
generated in $O(\log d)$ time. Similarly, by Theorem 4.1, we have

$\dim H_{G^{\circ}}-2d+\leq\dim H_{G}+\sum_{i=1}^{d}\dim
H_{G_{\varphi_{i}}}\leq 2d+4-2d+d2^{\log(|\Sigma|/d)+2(D-1)+S}\leq
4d2^{\log(|\Sigma|/d)+2(D-1)+S}$

by the induction hypothesis and Lemma 3.15. Thus

$\log\dim H_{G^{\circ}}\leq 2+\log|\Sigma|+2(D-1)+S=\log|\Sigma|+2D+S.$

##### AND Case:

Next, suppose $\varphi=\bigwedge_{i=1}^{d}\varphi_{i}$ for some formulas of
depth $D-1$. Let $G=G_{\textsc{and},d}$ be the graph from Lemma 3.19, which is
a switching network, and hence $st$-composable. Let
$G_{\varphi_{1}},\dots,G_{\varphi_{d}}$ be the $st$-composable subspace graphs
whose existence is promised by the induction hypothesis. We will compose the
graphs $G_{\varphi_{i}}$ into the switch edge $e_{i}$ of $G$ to obtain
$G^{\circ}$. If $\varphi_{i}(x)=1$ for all $i$, then there exist cropped
positive witnesses ${\lvert}\hat{w}^{i}\rangle$ for each $G_{\varphi_{i}}$, so
using the cropped positive witness for $G$ from Lemma 3.19, by Theorem 4.1,
$G^{\circ}$ has cropped positive witness

${\lvert}\hat{w}^{\circ}\rangle=\sum_{i=1}^{d}\sqrt{\frac{{\sf
r}^{i}}{2}}\frac{1}{\sqrt{{\sf
w}_{i}}}{\lvert}\hat{w}^{i}\rangle=\sum_{i=1}^{d}\frac{1}{\sqrt{{\sf
w}_{i}}}{\lvert}\hat{w}^{i}\rangle.$

Thus, setting ${\sf w}_{i}=d$, so that

${\sf r}=\frac{2}{\sum_{i=1}^{d}\frac{1}{{\sf w}_{i}}}=2,$

we have:

$\hat{W}_{+}(G^{\circ})\leq\sum_{i=1}^{d}\frac{1}{{\sf
w}_{i}}\hat{W}_{+}(G_{\varphi_{i}})\leq\frac{1}{d}\sum_{i=1}^{d}\frac{{\sf
C}_{i}^{2}}{c_{D-1}}=\frac{\sum_{i=1}^{d}{\sf C}_{i}^{2}}{dc_{D-1}}=\frac{{\sf
C}^{2}}{c_{D}},$

by the induction hypothesis, which says that
$\hat{W}_{+}(G_{\varphi_{i}})\leq{\sf C}_{i}^{2}/c_{D-1}$, and
$c_{D}=dc_{D-1}$ since nodes at height $D$ are labelled $\wedge$.

On the other hand, suppose $\varphi_{i}(x)=0$ for some $i\in[d]$, so there
exists a cropped negative witness ${\lvert}\hat{w}_{\cal A}^{i}\rangle$ for
$G_{\varphi_{i}}$. Then using the cropped negative witness from Lemma 3.19, by
Theorem 4.1, we have a cropped negative witness for $G^{\circ}$:

${\lvert}\hat{w}^{\circ}_{\cal A}\rangle=\sqrt{\frac{2}{{\sf
r}^{i}}}\sqrt{{\sf w}_{i}}{\lvert}\hat{w}^{i}_{\cal A}\rangle=\sqrt{{\sf
w}_{i}}{\lvert}\hat{w}^{i}_{\cal A}\rangle.$

Thus, we have:

$\hat{W}_{-}(G^{\circ})\leq{\sf w}_{i}\hat{W}_{-}(G_{\varphi_{i}})\leq
dc_{D-1}=c_{D},$

by the induction hypothesis.

A similar argument about the basis efficiency and dimension of $H_{G^{\circ}}$
as in the OR case completes the proof. ∎

###  4.3 Quantum Divide & Conquer

In this section, we state our time-efficient quantum divide & conquer results.
The following is a time-efficient version of Strategy 1 in [CKKD+22],
restricted to symmetric formulas.

######  Theorem 4.11.

Fix a function family $f_{\ell,n}:D_{\ell,n}\rightarrow\\{0,1\\}$. Fix unit-
time-computable functions
$\lambda_{1},\lambda_{2}:\mathbb{N}\rightarrow\mathbb{N}$, and a symmetric
formula $\varphi$ on $\\{0,1\\}^{a+1}$. Suppose $\\{{\cal
P}_{\mathrm{aux},\ell,n}\\}_{\ell,n\in\mathbb{N}}$ is a family of quantum
algorithms such that:

  * •

${\cal P}_{\mathrm{aux},\ell,n}$ decides some
$f_{\mathrm{aux},\ell,n}:D_{\ell,n}\rightarrow\\{0,1\\}$ with time and space
complexities $T_{\mathrm{aux}}(\ell,n)$ and $S_{\mathrm{aux}}(\ell,n)$;

  * •

if $\ell\leq\ell_{0}$, $f_{\ell,n}(x)=f_{aux,\ell,n}(x)$;

  * •

if $\ell>\ell_{0}$, $f_{\ell,n}(x)=\varphi\circ(f_{i})_{i\in[a+1]}$ where each
$f_{i}$ for $i\in[a]$ is an instance of
$f_{\lambda_{1}(\ell),\lambda_{2}(n)}$, and $f_{a+1}=f_{\mathrm{aux},\ell,n}$.

Then there is a bounded-error quantum algorithm that compute $f_{\ell,n}$ with
time complexity $\widetilde{O}(T(\ell,n))$, and space complexity
$O(S_{\mathrm{aux}}(\ell,n)+\log T(\ell,n))$, where for all $\ell>\ell_{0}$:

$T(\ell,n)\colonequals\sqrt{aT(\lambda_{1}(\ell),\lambda_{2}(n))^{2}+O(T_{\mathrm{aux}}(\ell,n)^{2})}\leq\sqrt{a}T(\lambda_{1}(\ell),\lambda_{2}(n))+T_{\mathrm{aux}}(\ell,n)$

and for $\ell\leq\ell_{0}$, $T(\ell,n)=O(T_{\mathrm{aux}}(\ell,n))$.

We remark that, while we assume the subroutine ${\cal
P}_{\mathrm{aux},\ell,n}$ has no error, if it has sufficiently small error
inversely proportional to the number of times it is called, the algorithm must
still work, as this cannot be distinguished from having no error. Amplifying a
bounded-error quantum algorithm to have such small error incurs factors
logarithmic in the number of times it is called, so
$O(T_{\mathrm{aux},\ell,n})$ becomes $O(T_{\mathrm{aux},\ell,n}\log
T(\ell,n))$.

###### Proof.

The proof will be by induction. Specifically, we will show that there is an
$st$-composable subspace graph $G_{\ell,n}$ that computes $f_{\ell,n}$ with
$\dim H_{G}\leq 2^{S(\ell,n)}$, $\hat{\cal C}(G_{\ell,n})\leq T({\ell,n})$,
scaling factor ${\sf r}=2$, $\log\dim H_{G_{\ell,n}}=S_{\ell,n}\leq
cD\log(a+1)+cS_{\mathrm{aux}}(\ell,n)+c\log T_{\mathrm{aux}}(\ell,n)$ and
basis generation cost $L_{\ell,n}\colonequals Dc^{\prime}\log(a+1)+c\log
T_{\mathrm{aux}}(\ell,n)$, where $D$ is the depth of recursion, and $c$ and
$c^{\prime}$ are sufficiently large constants.

For the base case, suppose $\ell\leq\ell_{0}$. Then we let $G_{\ell,n}$ be the
subspace graph from Lemma 3.23 derived from the algorithm ${\cal
P}_{\mathrm{aux},\ell,n}$ and using $\alpha_{r}=1$ for all $r$. Then
$G_{\ell,n}$ computes $f_{\mathrm{aux},\ell,n}$, has ${\sf r}=2$, $\dim
H_{G_{\ell,n}}\leq c(S_{\mathrm{aux}}(\ell,n)+\log T_{\mathrm{aux}}(\ell,n))$,
basis generation cost at most $c\log T_{\mathrm{aux}}(\ell,n)$, and
$T(\ell,n)\colonequals\hat{\cal C}(G_{\ell,n})=O(T_{\mathrm{aux}}(\ell,n))$,
if $c$ is sufficiently large.

We will use the shorthand
$\lambda(\ell,n)=(\lambda_{1}(\ell),\lambda_{2}(n))$. For the induction step,
let $G_{\lambda(\ell,n)}$ be the subspace graph whose existence is guaranteed
by the induction hypothesis, that computes $f_{\lambda(\ell,n)}$ with
$\hat{\cal C}(G_{\lambda(\ell,n)})\leq T(\lambda(\ell,n))$. Then we will use
Lemma 4.10, where $G_{1},\dots,G_{a}$ are each copies of
$G_{\lambda(\ell,n)}$, and $G_{a+1}$ is a subspace graph computing
$f_{\mathrm{aux},\ell,n}$ from Lemma 3.23. This gives a subspace graph
computing $f_{\ell,n}$ with complexity

$\hat{\cal C}(G_{\ell,n})^{2}\leq\sum_{i=1}^{a+1}\hat{\cal
C}(G_{i})^{2}=a\hat{\cal C}(G_{\lambda(\ell,n)})^{2}+\hat{\cal
C}(G_{a+1})^{2}\leq aT(\lambda(\ell,n))^{2}+O(T_{\mathrm{aux}}(\ell,n)^{2})$

by the induction hypothesis, and Lemma 3.23. The cost of generating the bases
for each of the graphs $G_{1},\dots,G_{a}$ is at most

$L_{\lambda(\ell,n)}=(D-1)c^{\prime}\log(a+1)+c\log T_{\mathrm{aux}}(\ell,n)$

by the induction hypothesis, and the cost to generate $G_{a+1}$ is at most
$c\log T_{\mathrm{aux}}(\ell,n)$, by Lemma 3.23. Then by Lemma 4.10 the cost
to generate the basis for $G_{\ell,n}$ is at most:

$\displaystyle c^{\prime}\log(a+1)+L_{\lambda(\ell,n)}$ $\displaystyle\leq
c^{\prime}\log(a+1)+(D-1)c^{\prime}\log(a+1)+c\log T_{\mathrm{aux}}(\ell,n)$
$\displaystyle=Dc^{\prime}\log(a+1)+c\log
T_{\mathrm{aux}}(\ell,n)=L_{\ell,n},$

as needed. Finally, we note that for all $i\in[a]$, by the induction
hypothesis

$\displaystyle\log\dim H_{G_{i}}$ $\displaystyle\leq
c(D-1)\log(a+1)+cS_{\mathrm{aux}}(\lambda(\ell,n))+c\log
T_{\mathrm{aux}}(\lambda(\ell,n))$ $\displaystyle\leq
c(D-1)\log(a+1)+cS_{\mathrm{aux}}(\ell,n)+c\log T_{\mathrm{aux}}(\ell,n)$

and by Lemma 3.23,

$\log\dim H_{G_{a+1}}\leq cS_{\mathrm{aux}}(\ell,n)+c\log
T_{\mathrm{aux}}(\ell,n).$

Thus, by Lemma 4.10, if $c$ is a sufficiently large constant,

$\displaystyle\log\dim H_{G_{\ell,n}}$ $\displaystyle\leq
c(D-1)\log(a+1)+cS_{\mathrm{aux}}(\ell,n)+c\log
T_{\mathrm{aux}}(\ell,n)+c\log(a+1)$
$\displaystyle=cD\log(a+1)+cS_{\mathrm{aux}}(\ell,n)+c\log
T_{\mathrm{aux}}(\ell,n)=S_{\ell,n}.$

This completes the induction. To complete the proof of the theorem, we first
apply Corollary 4.2 to get a subspace graph $G_{\ell,n}^{\prime}$ with
$\hat{W}_{+}\leq 1$, and then apply Theorem 3.12, which turns
$G_{\ell,n}^{\prime}$ into a bounded-error quantum algorithm for $f_{\ell,n}$
with time complexity

$O\left(L_{\ell,n}\sqrt{T(\ell,n)}\right),$

and space complexity $O(S_{\ell,n}+\log T(\ell,n))$. We complete the proof by
noting that

$\log T(\ell,n)\geq\log\sqrt{a}^{D}=\frac{D}{2}\log
a\geq\frac{D}{4}\log(a+1),$

so $L_{\ell,n}=O(\log(T(\ell,n)))$, and
$S_{\ell,n}=O(S_{\mathrm{aux}}(\ell,n)+\log T(\ell,n))$. ∎

###  4.4 Switching Networks with Subroutines

The following is similar to Lemma 4.10, except that we generalize to any
switching network, not just those arising from Boolean formulas (series-
parallel switching networks), and we specialize to the case where the composed
subspace graphs are of the form in Section 3.5 (this specialization is not
necessary, but it is not clear what we gain from the more general result).

######  Lemma 4.12.

Let $G$ be any switching network computing a Boolean function $f$, with
working bases that can be generated in time $T_{\mathrm{basis}}$. For each
$e\in E$, let $\\{U_{r}^{e}\\}_{r=1}^{T_{e}}$ be a quantum algorithm computing
a Boolean function $f_{e}$ with bounded error. Let $T_{\max}$ be an upper
bound on $T_{e}$ for all $e$, and $F_{x}$ an $st$-cut-set of $G(x)$ whenever
$f(x)=0$. Then there is a subspace graph $G^{\circ}$ computing
$f\circ(f_{e})_{e\in E}$ with complexities
$\hat{W}_{+}(G^{\circ})=O\left(\max_{x\in f^{-1}(1)}{\cal R}_{s,t}(G(x))\log
T_{\max}\right)$ and $\hat{W}_{-}(G^{\circ})=O\left(\max_{x\in
f^{-1}(0)}\sum_{e\in F_{x}}{\sf w}_{e}T_{e}^{2}\right)$, and its bases can be
generated in time $T_{\mathrm{basis}}+O(\log T_{\max})$.

We remark that sometimes a better negative witness for $G$ can be obtained by
taking a superposition of different $st$-cut-sets. This also gives a better
negative witness for $G^{\circ}$, but its form is more complicated, so we omit
describing this.

###### Proof.

For each $e\in E$, let $G^{e}$ be the subspace graph from Lemma 3.23 derived
from the algorithm $\\{U_{r}^{e}\\}_{r}$, using weights $\alpha_{r}=r+1$. Thus
$G^{e}$ computes $f_{e}$. We will apply Theorem 4.1 to $G$, and the $G^{e}$.

##### Positive Analysis:

A positive input for $f\circ(f_{e})_{e}$ gives rise to a positive input for
$f$ – let ${\lvert}\hat{w}\rangle$ be a positive witness for $G$ under that
input. This only uses edges that are turned on, so for each $e$ that is on
(i.e. $f_{e}=1$), let ${\lvert}\hat{w}^{e}\rangle$ be a cropped positive
witness for $G^{e}$. By Theorem 4.1, there is a cropped positive witness for
$G^{\circ}$:

${\lvert}\hat{w}^{\circ}\rangle\colonequals\sum_{e\in E}\sqrt{\frac{{\sf
r}^{e}}{2}}{{\langle}\leftarrow,e|}\hat{w}\rangle{\lvert}\hat{w}^{e}\rangle,$

since $\overline{E}=E$, where ${\sf r}^{e}=2$ is the scaling factor of
$G^{e}$’s basis. Since $G$ is a switching network, its positive witness is a
unit $st$-flow, in the sense of (4), so
${{\langle}\leftarrow,e|}\hat{w}\rangle=\frac{\theta(e)}{\sqrt{{\sf w}_{e}}}$,
so we have:

${\lvert}\hat{w}^{\circ}\rangle=\sum_{e\in E}\frac{\theta(e)}{\sqrt{{\sf
w}_{e}}}{\lvert}\hat{w}^{e}\rangle,$

and

$\hat{W}_{+}(G^{\circ})\leq\left\|{\lvert}\hat{w}^{\circ}\rangle\right\|^{2}=\sum_{e\in
E}\frac{\theta(e)^{2}}{{\sf
w}_{e}}\left\|{\lvert}\hat{w}^{e}\rangle\right\|^{2}=\sum_{e\in
E}\frac{\theta(e)^{2}}{{\sf w}_{e}}\hat{W}_{+}(G^{e}).$

Because we have set $\alpha_{r}=r+1$, by Lemma 3.23, we have

$\hat{W}_{+}(G^{e})\leq\sum_{r=1}^{T_{e}}\frac{1}{r+1}=O(\log T_{e}),$

so

$\hat{W}_{+}(G^{\circ})\leq\sum_{e\in E}\frac{\theta(e)^{2}}{{\sf w}_{e}}\log
T_{\max}={\cal R}_{s,t}(G(x))\log T_{\max}.$

##### Negative Analysis:

Similarly, for a negative input to $f\circ(f_{e})_{e}$, let $x$ be its
corresponding negative input to $f$, and let ${\lvert}\hat{w}_{\cal A}\rangle$
be a negative witness for $G$ on input $x$. For each $e$ such that $f_{e}=0$,
let ${\lvert}\hat{w}_{\cal A}^{e}\rangle$ be a negative witness for $G^{e}$.
By Theorem 4.1, there is a cropped negative witness for $G^{\circ}$:

${\lvert}\hat{w}_{\cal A}^{\circ}\rangle=\sum_{e\in
E}{{\langle}\leftarrow,e|}\hat{w}_{\cal A}\rangle{\lvert}\hat{w}_{\cal
A}^{e}\rangle.$

Since $G$ is a switching network, we can always choose a negative witness of
the form

${\lvert}\hat{w}_{\cal A}\rangle=\sum_{e\in F_{x}}\sqrt{{\sf
w}_{e}}({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle),$

where $F_{x}$ is an $st$-cut-set of $G(x)$. Then:

$\displaystyle\hat{W}_{-}(G^{\circ})$ $\displaystyle\leq\max_{x\in
f^{-1}(0)}\sum_{e\in F_{x}}{\sf w}_{e}\left\|{\lvert}\hat{w}_{\cal
A}^{e}\rangle\right\|^{2}=\max_{x\in f^{-1}(0)}\sum_{e\in F_{x}}{\sf
w}_{e}\hat{W}_{-}(G^{e})$ $\displaystyle\leq\max_{x\in f^{-1}(0)}\sum_{e\in
F_{x}}{\sf w}_{e}\sum_{r=1}^{T_{e}}(r+1)=O\left(\max_{x\in
f^{-1}(0)}\sum_{e\in F_{x}}{\sf w}_{e}T_{e}^{2}\right).$

##### Basis Generation:

By Theorem 4.1, since the bases of $G^{e}$ can be generated in time $O(\log
T_{e})$, the bases of $G^{\circ}$ can be generated in time
$T_{\text{basis}}+O(\log T_{\max})$, completing the proof. ∎

Then the main theorem of this section follows directly.

######  Theorem 4.13.

Let $G$ be any switching network computing a Boolean function $f$, with
working bases that can be generated in time $T_{\mathrm{basis}}$. For each
$e\in E$, let $\\{U_{r}^{e}\\}_{r=1}^{T_{e}}$ be a quantum algorithm computing
a Boolean function $f_{e}$ with bounded error. Let $T_{\max}$ be an upper
bound on $T_{e}$ for all $e$, and $F_{x}$ an $st$-cut-set of $G(x)$ whenever
$f(x)=0$. Then there is a bounded error quantum algorithm for $f$ with
complexity

$\widetilde{O}\left(T_{\mathrm{basis}}\sqrt{\max_{x\in f^{-1}(1)}{\cal
R}_{s,t}(G(x))\max_{x\in f^{-1}(0)}\sum_{e\in F_{x}}{\sf
w}_{e}T_{e}^{2}}\right).$

###### Proof.

Let $G^{\circ}$ be the subspace graph from Lemma 4.12. By Corollary 4.2, there
is a subspace graph $G^{\prime}$, also computing $f\circ(f_{e})_{e}$, whose
bases can also be generated in time $T_{\text{basis}}+O(\log T_{\max})$, and
such that $\hat{W}_{+}(G^{\prime})\leq 1$ and
$\hat{W}_{-}(G^{\prime})\leq\hat{W}_{+}(G^{\circ})\hat{W}_{-}(G^{\circ})$.
Then we can apply Theorem 3.12 to $G^{\prime}$ to get a bounded error quantum
algorithm for $f\circ(f_{e})_{e}$ with complexity:

$\displaystyle O\left((T_{\text{basis}}+\log
T_{\max})\sqrt{\hat{W}_{+}(G^{\circ})\hat{W}_{-}(G^{\circ})}\right)$
$\displaystyle={}$ $\displaystyle O\left((T_{\text{basis}}+\log
T_{\max})\sqrt{\max_{x\in f^{-1}(1)}{\cal R}_{s,t}(G(x))\max_{x\in
f^{-1}(0)}\sum_{e\in F_{x}}{\sf w}_{e}T_{e}^{2}\log T_{\max}}\right).\qed$

##  5 Application to DSTCON

In this section we consider the directed st-connectivity problem. First, we
specify the graph access model. We will work in the adjacency matrix, where we
assume that for a directed graph $G=(V,E)$ the input is given as an oracle
$\mathcal{O}_{G}$ that can be queried in unit cost, where for any $u,v\in V$

$\mathcal{O}_{G}:{\lvert}u\rangle{\lvert}v\rangle{\lvert}0\rangle\mapsto\begin{cases}{\lvert}u\rangle{\lvert}v\rangle{\lvert}1\rangle&\mbox{if
}(u,v)\in E\\\
{\lvert}u\rangle{\lvert}v\rangle{\lvert}0\rangle&\mbox{otherwise.}\end{cases}$

However, we note that the time complexity $2^{\frac{1}{2}\log^{2}n+O(\log n)}$
in Theorem 5.3 also holds for the edge list model, in which the algorithm can
query the $i$-th out- or in-neighbour of a vertex. That is because given such
access, we can implement a query to $\mathcal{O}_{G}$ in poly$(n)$ time and
$O(\log n)$ space, and poly$(n)$ factors are suppressed in $2^{O(\log n)}$.

######  Problem 5.1 (dstcon).

Given access to a directed graph $G=(V,E)$ via the oracle $\mathcal{O}_{G}$,
and two vertices $s,t\in V$, decide whether there is a directed path from $s$
to $t$ in $G$.

There is a classical recursive algorithm for dstcon that operates in the low-
space regime due to Savitch [Sav70]. We first describe the subroutine
$\textsc{path}_{\ell}({\cal O}_{G},u,v)$ that will be called recursively in
the algorithm. This subroutine decides whether there is a path of length at
most $\ell$ from $u$ to $v$ in $G$. For $\ell\geq 2$, the subroutine searches
over all vertices for some $w$ such that there are paths of length at most
$\ell/2$ from $s$ to $w$ and $w$ to $t$:

Input: Oracle ${\cal O}_{G}$, $u,v\in V$

Output: $1$ if there is a path of length $\leq\ell$ from $u$ to $v$ in $G$; 0
otherwise.

for  _$w\in V$_ do

$b_{w}\colonequals\textsc{path}(\ell/2,u,w)\land\textsc{path}(\ell/2,w,v)$;

end for

return _$\lor_{w\in V}b_{w}$_ ;

Subroutine 1 $\textsc{path}_{\ell}({\cal O}_{G},u,v)$ for $\ell\geq 2$

Next, we describe the base case. When $\ell=1$, the subroutine simply performs
a single query ${\cal O}_{G}(u,v)$ and outputs:

$\textsc{path}_{1}({\cal O}_{G},u,v)=\begin{cases}1&\mbox{if }(u,v)\in E\\\
0&\mbox{otherwise.}\end{cases}$

Then Savitch’s algorithm simply outputs $\textsc{path}_{n}({\cal O}_{G},s,t)$,
where $n=|V|$, to decide if there is a path from $s$ to $t$.

Input: Oracle ${\cal O}_{G}$ for $G=(V,E)$ with $\left|V\right|=n$, $s,t\in V$

Output: $1$ if there is a path from $s$ to $t$ in $G$; 0 otherwise.

return _$\textsc{path}_{n}({\cal O}_{G},s,t)$_ ;

Algorithm 2 Savitch’s algorithm for dstcon

The following result of Savitch is easy to verify.

######  Theorem 5.2.

Algorithm 2 decides dstcon in time $O((2n)^{\log n}=2^{\log^{2}+O(\log n)})$
and space $O(\log^{2}n)$.

Next, we show a quantum speedup for Savitch’s algorithm via application of
Theorem 4.11.

######  Theorem 5.3.

Let $G=(V,E)$ be a directed graph, $\left|V\right|=n$. Then there exists a
recursive quantum algorithm that decides dstcon on $G$ with bounded error in
time $\widetilde{O}((\sqrt{2n})^{\log n})=2^{\frac{1}{2}\log^{2}n+O(\log n)}$
and space $O(\log^{2}n)$.

###### Proof.

To show existence of such a quantum algorithm, we will rephrase algorithm 2 in
terms of the condition of Theorem 4.11 and analyze its complexity. We start
with defining a function corresponding to dstcon.

$f_{\ell,n}:\\{0,1\\}^{n^{2}}\times\\{0,1\\}^{\log n}\times\\{0,1\\}^{\log
n}\to\\{0,1\\}$ $(G,u,v)\mapsto\begin{cases}1&\mbox{if there is a path from
$u$ to $v$ in $G$ of length $\leq\ell$}\\\ 0&\mbox{otherwise,}\end{cases}$

where $G$ encodes a directed graph on $n$ vertices and $u$,$v$ encode two
vertices in $G$.

Next, we define $\lambda_{1}(\ell)=\ell/2$ and $\lambda_{2}(n)=n$. This
specifies the recursion. Finally, we set $\ell_{0}=1$ and define

$f_{aux,1,n}(G,u,v)=\begin{cases}1&\mbox{if }(u,v)\in E\\\
0&\mbox{otherwise.}\end{cases}$

and $f_{aux,\ell,n}=0$ for all $\ell>1$. Then ${\cal P}_{\mathrm{aux},\ell,n}$
is a single edge query when $\ell=1$ and does nothing otherwise. This implies
$T_{\mathrm{aux}}(\ell,n)=O(1)$ and $S_{\mathrm{aux}}(\ell,n)=O(\log n)$ as
this is the space needed to write down a vertex name. We have everything to
write down $f_{\ell,n}$ recursively, as a symmetric formula in $a=2n$
variables:

$f_{\ell,n}(G,u,v)=\lor_{w\in V}(f_{\ell/2,n}(G,u,w)\land
f_{\ell/2,n}(G,w,v))\lor f_{aux,\ell,n}(G,u,v).$

Now we apply Theorem 4.11 to everything described above and conclude that
there is a recursive bounded error quantum algorithm that computes
$f_{\ell,n}$ with time complexity $\widetilde{O}(T(\ell,n))$ and space
complexity $O(S_{\mathrm{aux}}(\ell,n)+\log T(\ell,n))$, such that we have for
all $\ell>1$:

$T(\ell,n)=\sqrt{2n}T(\ell/2,n)+O(1),$

and $T(1,n)=O(1)$. By solving the recursion, we obtain

$T(n,n)=O((\sqrt{2n})^{\log n})=O\left(2^{\frac{1}{2}(\log^{2}n+\log
n)}\right).$

This gives $S(n,n)=O(\log^{2}n)$. Since $f_{n,n}$ precisely describes the
problem dstcon, this concludes the proof. ∎

##  6 Acknowledgements

We thank Simon Apers for useful discussions about this work.

This work is supported by NWO Klein project number OCENW.Klein.061, and ARO
contract no W911NF2010327. This work is funded/co-funded by the European Union
(ERC, ASC-Q, 101040624). Views and opinions expressed are however those of the
author(s) only and do not necessarily reflect those of the European Union or
the European Research Council. Neither the European Union nor the granting
authority can be held responsible for them. SJ is a CIFAR Fellow in the
Quantum Information Science Program.

This publication is part of the project Divide & Quantum (with project number
1389.20.241) of the research programme NWA-ORC which is (partly) financed by
the Dutch Research Council (NWO).

This work is supported by the Dutch National Growth Fund (NGF), as part of the
Quantum Delta NL programme.

## References

  * [ABB+23] Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, and Miklos Santha.  On the quantum time complexity of divide and conquer.  arXiv: 2311.16401, 2023.
  * [AJPW22] Simon Apers, Stacey Jeffery, Galina Pass, and Michael Walter.  Quantum walks for USTCON.  In Proceedings of the 31st Annual European Symposium on Algorithms (ESA), pages 10:1--10:17, 2022.  arXiv: 2212.00094
  * [BCJ+13] Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez.  Time-efficient quantum walks for 3-distinctness.  In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), pages 105--122, 2013.
  * [Bel13] Aleksandrs Belovs.  Quantum walks and electric networks.  arXiv: 1302.3143, 2013.
  * [BJY23] Aleksandrs Belovs, Stacey Jeffery, and Duyal Yolcu.  Taming quantum time complexity.  arXiv: 2311.15873, 2023.
  * [BR12] Aleksandrs Blovs and Ben W. Reichardt.  Span programs and quantum algorithms for st-connectivity and claw detection.  In Proceedings of the 20th Annual European Symposium on Algorithms (ESA), pages 193--204, 2012.
  * [CKKD+22] Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, and Daochen Wang.  Quantum divide and conquer.  arXiv: 2210.06419, 2022.
  * [DHHM06] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla.  Quantum query complexity of some graph problems.  SIAM Journal on Computing, 35(6):1310--1328, 2006.  Earlier version in ICALP’04. arXiv: quant-ph/0401091
  * [IJ19] Tsuyoshi Ito and Stacey Jeffery.  Approximate span programs.  Algorithmica, 79:2158--2195, 2019.
  * [Jef22] Stacey Jeffery.  Quantum subroutine composition.  arXiv: 2209.14146, 2022.
  * [JJKP18] Michael Jarret, Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita.  Quantum algorithms for connectivity and related problems.  In Proceedings of the 26th Annual European Symposium on Algorithms (ESA), pages 49:1--49:13, 2018.
  * [JK17] Stacey Jeffery and Shelby Kimmel.  Quantum algorithms for graph connectivity and formula evaluation.  Quantum, 1(26), 2017.
  * [JZ23] Stacey Jeffery and Sebastian Zur.  Multidimensional quantum walks and application to $k$-distinctness.  In Proceedings of the 55th ACM Symposium on the Theory of Computing (STOC), pages 1125--1130, 2023.  arXiv: 2208.13492
  * [Kit96] Alexei Y. Kitaev.  Quantum measurements and the Abelian stabilizer problem.  ECCC, TR96-003, 1996.  arXiv: quant-ph/9511026
  * [Lee59] C. Y. Lee.  Representation of switching functions by binary decision programs.  Bell Systems Technical Journal, 38(4):985--999, 1959.
  * [MNRS11] Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha.  Search via quantum walk.  SIAM Journal on Computing, 40(1):142--164, 2011.  Earlier version in STOC’07. arXiv: quant-ph/0608026
  * [Pot15] Aaron H. Potechin.  Analyzing monotone space complexity via the switching network model.  PhD thesis, Massachusetts Institute of Technology, 2015.
  * [Rei11] Ben W. Reichardt.  Faster quantum algorithm for evaluating game trees.  In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 546--559, 2011.
  * [RŠ12] Ben W. Reichardt and Robert Špalek.  Span-program-based quantum algorithm for evaluating formulas.  Theory of Computing, 8(13):291--319, 2012.
  * [Sav70] Walter J Savitch.  Relationships between nondeterministic and deterministic tape complexities.  Journal of computer and system sciences, 4(2):177--192, 1970.
  * [Sha38] Claude E. Shannon.  A symbolic analysis of relay and switching networks.  Transactions of the American Institute of Electrical Engineers, 57(12):713--723, 1938.
  * [Sha49] Claude E. Shannon.  The synthesis of two-terminal switching circuits.  Bell System Technical Journal, 28(1):59--98, 1949.
  * [Sze04] Mario Szegedy.  Quantum speed-up of Markov chain based algorithms.  In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), pages 32--41, 2004.  arXiv: quant-ph/0401053

##  Appendix A Recovering the Local Structure

In this appendix, we prove that the following spaces are equal.

${\cal B}_{G^{\circ}}=\bigoplus_{u\in V}\widetilde{\Lambda}({\cal
V}_{u})\oplus\bigoplus_{e\in\overline{E}}\bigoplus_{u\in
V^{e}\setminus\\{s,t\\}}{\cal
V}_{u}^{e}+\bigoplus_{e\in\overline{E}}\bigoplus_{e^{\prime}\in
E^{e}}\Xi_{e^{\prime}}^{e\cal B}$ (22)

$\overline{\cal B}_{G^{\circ}}=\mathrm{span}\underbrace{\Lambda(\Psi_{{\cal
B}_{G}}^{-})\cup\bigcup_{e\in\overline{E}}(\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\})}_{\equalscolon\Psi_{{\cal
B}_{G^{\circ}}}^{-}}\cup\underbrace{\left\\{\frac{1}{\sqrt{2}}({\lvert}\rightarrow,e^{\prime}\rangle+{\lvert}\leftarrow,e^{\prime}\rangle):e^{\prime}\in\overline{E}^{\circ}=\bigcup_{e\in\overline{E}}\overline{E}^{e}\right\\}}_{\mbox{spans
}\Xi_{\overline{E}^{\circ}}^{\circ\cal
B}=\bigoplus_{e\in\overline{E}}\bigoplus_{e^{\prime}\in\overline{E}^{e}}\Xi_{e^{\prime}}^{e\cal
B}}.$ (23)

######  Lemma A.1.

For any $e\in\overline{E}$,

$\mathrm{span}\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}\oplus\Xi_{\overline{E}^{e}}^{e\cal
B}={\cal
B}_{G^{e}}\cap\\{{\lvert}\leftarrow,s^{e}\rangle,{\lvert}\rightarrow,t^{e}\rangle\\}^{\bot}=\bigoplus_{u\in
V^{e}\setminus\\{s,t\\}}{\cal V}_{u}^{e}+\Xi_{\overline{E}^{e}}^{e\cal B}.$

###### Proof.

It is clear that

$\displaystyle\mathrm{span}\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}\oplus\Xi_{\overline{E}^{e}}^{e\cal
B}$ $\displaystyle\subseteq{\cal B}_{G^{e}}=\mathrm{span}\Psi_{{\cal
B}_{G^{e}}}^{-}\oplus\Xi_{\overline{E}^{e}}^{e\cal B}$ $\displaystyle\mbox{and
also }\bigoplus_{u\in V^{e}\setminus\\{s,t\\}}{\cal
V}_{u}^{e}+\Xi_{\overline{E}^{e}}^{e\cal B}$ $\displaystyle\subseteq{\cal
B}_{G^{e}}=\bigoplus_{u\in V^{e}}{\cal
V}_{u}^{e}+\Xi_{\overline{E}^{e}}^{e\cal B}.$

Since we also have everything in $\mathrm{span}\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}$,
$\bigoplus_{u\in V^{e}\setminus\\{s,t\\}}{\cal V}_{u}^{e}$ and
$\Xi_{\overline{E}^{e}}^{e\cal B}$ orthogonal to both
${\lvert}\leftarrow,s^{e}\rangle$ and ${\lvert}\rightarrow,t^{e}\rangle$, we
have:

$\displaystyle\mathrm{span}\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}\oplus\Xi_{\overline{E}^{e}}^{e\cal
B}$ $\displaystyle\subseteq{\cal
B}_{G^{e}}\cap\\{{\lvert}\leftarrow,s^{e}\rangle,{\lvert}\rightarrow,t^{e}\rangle\\}^{\bot}$
$\displaystyle\mbox{and }\bigoplus_{u\in V^{e}\setminus\\{s,t\\}}{\cal
V}_{u}^{e}+\Xi_{\overline{E}^{e}}^{e\cal B}$ $\displaystyle\subseteq{\cal
B}_{G^{e}}\cap\\{{\lvert}\leftarrow,s^{e}\rangle,{\lvert}\rightarrow,t^{e}\rangle\\}^{\bot}.$

For the other direction, suppose ${\lvert}\phi\rangle\in{\cal
B}_{G^{e}}\cap\\{{\lvert}\leftarrow,s^{e}\rangle,{\lvert}\rightarrow,t^{e}\rangle\\}^{\bot}$.
Since it is in ${\cal B}_{G^{e}}$, for some
${\lvert}\phi_{-}\rangle\in\mathrm{span}\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}$
and ${\lvert}\phi_{+}\rangle\in\Xi_{\overline{E}^{e}}^{e\cal B}$, and scalars
$a_{0}$ and $a_{1}$, we can express it as:

$\displaystyle{\lvert}\phi\rangle$
$\displaystyle=a_{0}{\lvert}b_{0}^{e}\rangle+a_{1}{\lvert}b_{1}^{e}\rangle+{\lvert}\phi_{-}\rangle+{\lvert}\phi_{+}\rangle$
$\displaystyle=a_{0}\frac{1}{\sqrt{2}}({\lvert}\leftarrow,s^{e}\rangle+{\lvert}\rightarrow,t^{e}\rangle)+a_{1}\frac{{\lvert}\leftarrow,s^{e}\rangle-{\lvert}\rightarrow,t^{e}\rangle+\sqrt{{\sf
r}^{e}}{\lvert}\bar{b}_{1}\rangle}{\sqrt{2+{\sf
r}^{e}}}+{\lvert}\phi_{-}\rangle+{\lvert}\phi_{+}\rangle.$

Since ${\lvert}\phi_{-}\rangle$, ${\lvert}\phi_{+}\rangle$, and
${\lvert}\bar{b}_{1}\rangle$ are all orthogonal to both
${\lvert}\leftarrow,s^{e}\rangle$ and ${\lvert}\rightarrow,t^{e}\rangle$,
since ${\lvert}\phi\rangle$ is as well, we must have $a_{0}=a_{1}=0$. Thus
${\lvert}\phi\rangle\in\mathrm{span}\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}\oplus\Xi_{\overline{E}^{e}}^{e\cal
B}$.

Similarly, we can express ${\lvert}\phi\rangle$ as

$\displaystyle{\lvert}\phi\rangle$
$\displaystyle=a_{0}^{\prime}({\lvert}\leftarrow,s\rangle+{\lvert}\psi_{\star}(s^{e})\rangle)+a_{1}^{\prime}({\lvert}\rightarrow,t\rangle+{\lvert}\psi_{\star}(t^{e})\rangle)+{\lvert}\phi_{V}\rangle+{\lvert}\phi_{+}^{\prime}\rangle$

for ${\lvert}\phi_{V}\rangle\in\bigoplus_{u\in V^{e}\setminus\\{s,t\\}}{\cal
V}_{u}^{e}$ and
${\lvert}\phi_{+}^{\prime}\rangle\in\Xi_{\overline{E}^{e}}^{e\cal B}$. By the
same reasoning as above, we must have $a_{0}^{\prime}=a_{1}^{\prime}=0$, so
${\lvert}\phi\rangle\in\bigoplus_{u\in V^{e}\setminus\\{s,t\\}}{\cal
V}_{u}^{e}+\Xi_{\overline{E}^{e}}^{e\cal B}$. ∎

######  Lemma A.2.

For any $e\in\overline{E}$,

$\widetilde{\Lambda}({\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle)\in{\cal
B}_{G^{e}}\cap\\{{\lvert}\leftarrow,s^{e}\rangle,{\lvert}\rightarrow,t^{e}\rangle\\}^{\bot}.$

###### Proof.

Since ${\cal V}_{s}^{e}+{\cal V}_{t}^{e}\subset{\cal B}_{G^{e}}$, we have

${\lvert}\leftarrow,s^{e}\rangle+{\lvert}\psi_{\star}(s^{e})\rangle,{\lvert}\rightarrow,t^{e}\rangle+{\lvert}\psi_{\star}(t^{e})\rangle\in{\cal
B}_{G^{e}}.$

Since ${\lvert}\leftarrow,s\rangle+{\lvert}\rightarrow,t\rangle\in{\cal
B}_{G^{e}}$ (because $G^{e}$ is $st$-composable),

$\displaystyle{\sqrt{{\sf
r}^{e}}}\widetilde{\Lambda}({\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle)$
$\displaystyle={\lvert}\psi_{\star}(s^{e})\rangle+{\lvert}\psi_{\star}(t^{e})\rangle$
$\displaystyle={\lvert}\leftarrow,s^{e}\rangle+{\lvert}\psi_{\star}(s^{e})\rangle+{\lvert}\rightarrow,t^{e}\rangle+{\lvert}\psi_{\star}(t^{e})\rangle-({\lvert}\leftarrow,s\rangle+{\lvert}\rightarrow,t\rangle),$

so
$\widetilde{\Lambda}({\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle)\in{\cal
B}_{G^{e}}$. Clearly
$\widetilde{\Lambda}({\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle)$
is also orthogonal to ${\lvert}\leftarrow,s^{e}\rangle$ and
${\lvert}\rightarrow,t^{e}\rangle$, concluding the proof. ∎

######  Lemma A.3.

Let $\widetilde{\Lambda}$ be as in (14), and define

$\widetilde{\cal
B}_{G^{\circ}}=\mathrm{span}\underbrace{\widetilde{\Lambda}(\Psi_{{\cal
B}_{G}}^{-})\cup\bigcup_{e\in\overline{E}}(\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\})}_{\equalscolon\widetilde{\Psi}_{{\cal
B}_{G^{\circ}}}^{-}}\oplus\bigoplus_{e\in\overline{E}}\bigoplus_{e^{\prime}\in\overline{E}^{e}}\Xi_{e^{\prime}}^{e\cal
B}.$

Then $\widetilde{\cal B}_{G^{\circ}}=\overline{\cal B}_{G^{\circ}}$.

###### Proof.

Let ${\lvert}\tilde{b}^{e}\rangle=\frac{1}{\sqrt{{\sf
r}^{e}}}({\lvert}\psi_{\star}(s^{e})\rangle-{\lvert}\psi_{\star}(t^{e})\rangle)$.
Then

${\lvert}\leftarrow,s^{e}\rangle-{\lvert}\rightarrow,t^{e}\rangle+\sqrt{{\sf
r}^{e}}{\lvert}\tilde{b}^{e}\rangle\in{\cal V}_{s}^{e}+{\cal
V}_{t}^{e}\subseteq\mathrm{span}\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle,\dots,{\lvert}b_{\ell}^{e}\rangle\\}\oplus\Xi_{\overline{E}^{e}}^{e\cal
B}.$

Then since the only vector that overlaps
${\lvert}\leftarrow,s^{e}\rangle-{\lvert}\rightarrow,t^{e}\rangle$ is
${\lvert}b_{1}^{e}\rangle=\frac{1}{\sqrt{2+{\sf
r}^{e}}}({\lvert}\leftarrow,s^{e}\rangle-{\lvert}\rightarrow,t^{e}\rangle)+\sqrt{\frac{{\sf
r}^{e}}{2+{\sf r}^{e}}}{\lvert}\bar{b}_{1}^{e}\rangle$, we must have:

${\langle}b_{1}^{e}\rvert({\lvert}\leftarrow,s^{e}\rangle-{\lvert}\rightarrow,t^{e}\rangle+\sqrt{{\sf
r}^{e}}{\lvert}\tilde{b}^{e}\rangle)=\sqrt{2+{\sf r}^{e}},$

from which it follows that
${{\langle}\bar{b}_{1}^{e}|}\tilde{b}^{e}\rangle=1$, and we can write:

${\lvert}\tilde{b}^{e}\rangle={\lvert}\bar{b}_{1}^{e}\rangle+{\lvert}d^{e}\rangle$
(24)

for some ${\lvert}d^{e}\rangle\in{\cal B}_{G^{e}}$ that is orthogonal to both
${\lvert}\leftarrow,s^{e}\rangle-{\lvert}\rightarrow,t^{e}\rangle$ and
${\lvert}\leftarrow,s^{e}\rangle+{\lvert}\rightarrow,t^{e}\rangle$, so by
Lemma A.1, ${\lvert}d^{e}\rangle\in\mathrm{span}\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}\oplus\Xi_{\overline{E}^{e}}^{e\cal
B}$.

Suppose ${\lvert}\tilde{\psi}\rangle\in\widetilde{\cal B}_{G^{\circ}}$, so we
can express it, for some scalars $a_{e}$,
${\lvert}\psi_{E\setminus\overline{E}}\rangle\in\Xi_{E\setminus\overline{E}}$
and ${\lvert}\psi^{\prime}\rangle\in\mathrm{span}\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}\oplus\Xi_{\overline{E}^{e}}^{e\cal
B}$ as:

$\begin{split}{\lvert}\tilde{\psi}\rangle&=\widetilde{\Lambda}\Bigg{(}\underbrace{\sum_{e\in\overline{E}}a_{e}\frac{1}{\sqrt{2}}({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle)+{\lvert}\psi_{E\setminus\overline{E}}\rangle}_{\in\mathrm{span}\Psi_{{\cal
B}_{G}}^{-}}\Bigg{)}+{\lvert}\psi^{\prime}\rangle\\\
&=\sum_{e\in\overline{E}}a_{e}{\lvert}\tilde{b}^{e}\rangle+{\lvert}\psi_{E\setminus\overline{E}}\rangle+{\lvert}\psi^{\prime}\rangle\\\
&=\sum_{e\in\overline{E}}a_{e}{\lvert}\bar{b}_{1}^{e}\rangle+{\lvert}\psi_{E\setminus\overline{E}}\rangle+\sum_{e\in\overline{E}}a_{e}{\lvert}d^{e}\rangle+{\lvert}\psi^{\prime}\rangle\\\
&=\Lambda\Bigg{(}\underbrace{\sum_{e\in\overline{E}}a_{e}\frac{1}{\sqrt{2}}({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle)+{\lvert}\psi_{E\setminus\overline{E}}\rangle}_{\in\mathrm{span}\Psi_{{\cal
B}_{G}}^{-}}\Bigg{)}+\underbrace{\sum_{e\in\overline{E}}a_{e}{\lvert}d^{e}\rangle+{\lvert}\psi^{\prime}\rangle}_{\in\mathrm{span}\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}\oplus\Xi_{\overline{E}^{e}}^{e\cal
B}}\in\overline{\cal B}_{G^{\circ}}.\end{split}$ (25)

Thus, $\widetilde{\cal B}_{G^{\circ}}\subseteq\overline{\cal B}_{G^{\circ}}$.

For the other direction, suppose ${\lvert}\psi\rangle\in\overline{\cal
B}_{G^{\circ}}$. Then similar to above, we can express it as

$\begin{split}{\lvert}\psi\rangle&=\Lambda\Bigg{(}\underbrace{\sum_{e\in\overline{E}}a_{e}\frac{1}{\sqrt{2}}({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle)+{\lvert}\psi_{E\setminus\overline{E}}\rangle}_{\in\mathrm{span}\Psi_{{\cal
B}_{G}}^{-}}\Bigg{)}+{\lvert}\psi^{\prime}\rangle\\\
&=\sum_{e\in\overline{E}}a_{e}{\lvert}\bar{b}_{1}^{e}\rangle+{\lvert}\psi_{E\setminus\overline{E}}\rangle+{\lvert}\psi^{\prime}\rangle\\\
&=\sum_{e\in\overline{E}}a_{e}{\lvert}\tilde{b}_{1}^{e}\rangle+{\lvert}\psi_{E\setminus\overline{E}}\rangle-\sum_{e\in\overline{E}}a_{e}{\lvert}d^{e}\rangle+{\lvert}\psi^{\prime}\rangle\\\
&=\widetilde{\Lambda}\Bigg{(}\underbrace{\sum_{e\in\overline{E}}a_{e}\frac{1}{\sqrt{2}}({\lvert}\rightarrow,e\rangle-{\lvert}\leftarrow,e\rangle)+{\lvert}\psi_{E\setminus\overline{E}}\rangle}_{\in\mathrm{span}\Psi_{{\cal
B}_{G}}^{-}}\Bigg{)}-\underbrace{\sum_{e\in\overline{E}}a_{e}{\lvert}d^{e}\rangle+{\lvert}\psi^{\prime}\rangle}_{\in\mathrm{span}\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}\oplus\Xi_{\overline{E}^{e}}^{e\cal
B}}\in\widetilde{\cal B}_{G^{\circ}}.\end{split}$ (26)

Thus $\overline{\cal B}{G^{\circ}}\subseteq\widetilde{\cal B}_{G^{\circ}}$. ∎

######  Theorem A.4.

Let $\overline{\cal B}_{G^{\circ}}=\mathrm{span}\Psi_{{\cal B}_{G^{\circ}}}$
where $\Psi_{{\cal B}_{G^{\circ}}}$ is as in (19) (see also (23)), and ${\cal
B}_{G^{\circ}}$ as in (17) (see also (22)). Then $\overline{\cal
B}_{G^{\circ}}={\cal B}_{G^{\circ}}$.

###### Proof.

We will show that ${\cal B}_{G^{\circ}}=\widetilde{\cal B}_{G^{\circ}}$, which
is sufficient, by Lemma A.3. We first show that $\widetilde{\cal
B}_{G^{\circ}}\subseteq{\cal B}_{G^{\circ}}$. First, for any
$e\in\overline{E}$, it follows from Lemma A.1 that

$\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}\oplus\Xi_{\overline{E}^{e}}^{e\cal
B}=\bigoplus_{u\in V^{e}\setminus\\{s,t\\}}{\cal
V}_{u}^{e}+\Xi_{\overline{E}^{e}}^{e\cal B}\subseteq{\cal
B}_{G^{\circ}}^{\prime}.$ (27)

Next, for any ${\lvert}\psi\rangle\in\Psi_{{\cal
B}_{G}}^{-}\subseteq\bigoplus_{u\in V}{\cal V}_{u}$, we have

$\widetilde{\Lambda}({\lvert}\psi\rangle)\in\widetilde{\Lambda}\left(\bigoplus_{u\in
V}{\cal V}_{u}\right)=\bigoplus_{u\in V}\widetilde{\Lambda}({\cal
V}_{u})\subseteq{\cal B}_{G^{\circ}}^{\prime}.$ (28)

From (27) and (28), it follows that $\widetilde{\cal
B}_{G^{\circ}}\subseteq{\cal B}_{G^{\circ}}$.

We now show the other direction, ${\cal B}_{G^{\circ}}\subseteq\widetilde{\cal
B}_{G^{\circ}}$. As in (27), for any $e\in\overline{E}$,

$\bigoplus_{u\in V^{e}\setminus\\{s,t\\}}{\cal
V}_{u}^{e}+\Xi_{\overline{E}^{e}}^{e\cal B}=\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}\oplus\Xi_{\overline{E}^{e}}^{e\cal
B}\subseteq\widetilde{\cal B}_{G^{\circ}}.$ (29)

Next, for any $u\in V$ and ${\lvert}\psi\rangle\in{\cal V}_{u}\subseteq{\cal
B}_{G}=\mathrm{span}\Psi_{{\cal B}_{G}}^{-}\oplus\Xi_{\overline{E}}^{\cal B}$,
we can write

${\lvert}\psi\rangle={\lvert}\psi_{-}\rangle+\sum_{e\in\overline{E}}a_{e}({\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle)$

for some ${\lvert}\psi_{-}\rangle\in\mathrm{span}\Psi_{{\cal B}_{G}}^{-}$ and
scalars $a_{e}$. Then:

$\widetilde{\Lambda}({\lvert}\psi\rangle)=\underbrace{\widetilde{\Lambda}{\lvert}\psi_{-}\rangle}_{\in\mathrm{span}\widetilde{\Lambda}(\Psi_{{\cal
B}_{G}}^{-})\subseteq\widetilde{\cal
B}_{G^{\circ}}}+\sum_{e\in\overline{E}}a_{e}\widetilde{\Lambda}({\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle).$
(30)

By Lemma A.2, for each $e$,
$\widetilde{\Lambda}({\lvert}\rightarrow,e\rangle+{\lvert}\leftarrow,e\rangle)\in{\cal
B}_{G^{e}}\cap\\{{\lvert}\leftarrow,s\rangle,{\lvert}\rightarrow,t\rangle\\}^{\bot}$,
which is equal to $\mathrm{span}\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}\oplus\Xi_{\overline{E}}^{e\cal
B}$ by Lemma A.1. Since $\mathrm{span}\Psi_{{\cal
B}_{G^{e}}}^{-}\setminus\\{{\lvert}b_{0}^{e}\rangle,{\lvert}b_{1}^{e}\rangle\\}\oplus\Xi_{\overline{E}}^{e\cal
B}\subseteq\widetilde{\cal B}_{G^{\circ}}$, we have
$\widetilde{\Lambda}{\lvert}\psi\rangle\in\widetilde{\cal B}_{G^{\circ}}$,
from which it follows that

$\widetilde{\Lambda}({\cal V}_{u})\subseteq\widetilde{\cal B}_{G^{\circ}}.$
(31)

Combining (29) and (31) establishes ${\cal
B}_{G^{\circ}}\subseteq\widetilde{\cal B}_{G^{\circ}}$, completing the proof.
∎