#  Small-world complex network generation on a digital quantum processor

Eric B. Jones<EMAIL_ADDRESS>National Renewable Energy Laboratory,
Golden, CO 80401, USA  Logan E. Hillberry  Department of Physics, University
of Texas, Austin, TX 78712, USA  Matthew T. Jones  Department of Physics,
Colorado School of Mines, Golden, CO 80401, USA  NVIDIA Corporation, Boulder,
CO 80302, USA  Mina Fasihi  Department of Physics, Colorado School of Mines,
Golden, CO 80401, USA  Pedram Roushan  Google Quantum AI, Santa Barbara, CA
93101, USA  Zhang Jiang  Google Quantum AI, Santa Barbara, CA 93101, USA  Alan
Ho  Google Quantum AI, Santa Barbara, CA 93101, USA  Charles Neill  Google
Quantum AI, Santa Barbara, CA 93101, USA  Eric Ostby  Google Quantum AI, Santa
Barbara, CA 93101, USA  Peter Graf  National Renewable Energy Laboratory,
Golden, CO 80401, USA  Eliot Kapit<EMAIL_ADDRESS>Quantum Engineering
Program, Colorado School of Mines, Golden, CO 80401, USA  Department of
Physics, Colorado School of Mines, Golden, CO 80401, USA  Lincoln D. Carr
<EMAIL_ADDRESS>Quantum Engineering Program, Colorado School of Mines, Golden,
CO 80401, USA  Department of Physics, Colorado School of Mines, Golden, CO
80401, USA

††preprint: APS/123-QED

Quantum cellular automata (QCA) evolve qubits in a quantum circuit depending
only on the states of their neighborhoods [6, 21] and model how rich physical
complexity can emerge from a simple set of underlying dynamical rules [10].
For instance, Goldilocks QCA depending on trade-off principles exhibit non-
equilibrating coherent dynamics and generate complex mutual information
networks [25], much like the brain [12]. The inability of classical computers
to simulate large quantum systems is a hindrance to understanding the physics
of quantum cellular automata, but quantum computers offer an ideal simulation
platform [31, 22]. Here we demonstrate the first experimental realization of
QCA on a digital quantum processor, simulating a one-dimensional Goldilocks
rule on chains of up to 23 superconducting qubits. Employing low-overhead
calibration and error mitigation techniques, we calculate population dynamics
and complex network measures indicating the formation of small-world mutual
information networks. Unlike random states [7], these networks decohere at
fixed circuit depth independent of system size; the largest of which
corresponds to 1,056 two-qubit gates. Such computations may open the door to
the employment of QCA in applications like the simulation of strongly-
correlated matter [11, 19, 33] or beyond-classical computational
demonstrations.

One of the most profound observations regarding the natural world is that,
despite the simple set of physical laws that underpin it, the universe
displays a plethora of complex, emergent phenomena, encountered in fields as
diverse as biology, sociology, and physics [4, 5, 26]. Examples of classical
systems where complexity arises as a result of many interacting degrees of
freedom are ecosystems, the human brain, and power grids [34]. Certain
classical cellular automata (CA) show how complexity can arise from simple
rules without the controlling hand of a designer [1]. CA possess the ability
to generate oscillatory, self-replicating structures and in some instances are
themselves Turing complete [37, 38, 28, 14, 15].

It is known however, that the laws constituting our best model of the universe
are quantum mechanical rather than classical [18]. Therefore, in order to
simulate the emergence of complexity more fundamentally, one ought to
investigate computational models that are predicated upon quantum mechanics.
Goldilocks quantum cellular automata (QCA) [25], are a class of computational
models that exhibit emergent complexity despite being constructed from
repeated blocks of simple local unitary operators [21]. They involve trade-
offs in the local neighborhood such as are known to be sources of complexity
in classical systems and essential to self-organized criticality [13]. Some
Goldilocks QCA have been shown to generate mutual information networks that
exhibit signatures of complexity, such as large network clustering, short
average path length, and broad node-strength distribution, typically only
observed in classical, small-world networks like social or biological networks
[25]. In addition, QCA have been proposed for other applications such as
lattice discretization in the simulation of strongly-correlated matter,
quantum field, and gravitational theories [33, 11, 19]. However, the
categorical limitation on the ability of classical computers to simulate the
time evolution of large quantum systems is a bottleneck for the discovery and
exploration of QCA more generally, hampering the theoretical illumination of
the class of systems as a whole [31].

Figure 1:  One-dimensional quantum cellular automata circuits. a, Schematic
for embedding one-dimensional chains into a subset of a two-dimensional
Sycamore-class quantum processor. Grey crosses represent transmon qubits and
blue rectangles represent couplers. Purple, green, yellow, and red paths are
hypothetical example embeddings. b, Generic structure of a one-dimensional
quantum cellular automata (QCA) circuit where time flows to the right. An
initialization step is applied to a chain of $L$ qubits, typically to place
them into a classical product state with some number of bit flips
($|1\rangle$s). A number of unitary QCA update cycles, $t$, are applied to all
$L$ qubits before measurement is performed. c, The specific structure of a
Goldilocks QCA for one QCA cycle (red box), wherein the initial state is
$|0\ldots 010\ldots 0\rangle$, the local update unitary is a controlled-
controlled-Hadamard gate, and measurement is performed in the computational
basis. d, After moment alignment, spin-echo insertion, and compilation down to
hardware-native gates a single QCA cycle (red box) results in $4\times(L-1)$
number of $\sqrt{\text{iSWAP}}^{\dagger}$ gates and $8\times L$ number of
individually-parameterized
$\text{PhXZ}(a,x,z)\equiv\text{Z}^{z}\text{Z}^{a}\text{X}^{x}\text{Z}^{-a}$
gates. The number of single and two-qubit layers per QCA cycle does not change
as a function of system size, only total gate volume does.

The last few years have seen the creation of sizeable digital quantum
processors that are already demonstrating their value as tools of scientific
discovery [39, 7, 8, 9, 32, 30, 27]. Due to their universality, such
processors are ideal platforms on which to elucidate the physics and
complexity characteristics of QCA. Herein, we simulate a particular one-
dimensional QCA on a Sycamore-class superconducting processor depicted
schematically in Figs. 1a-d. Through the calculation of population dynamics
and a complex-network characterization of the two-body mutual information
matrix we establish that such QCA form small-world mutual information networks
and thereby exhibit emergent physical complexity. Moreover, we take the first
step towards enabling the widespread use of near-term quantum processors as
QCA simulators and offer a template for how to experimentally investigate QCA
generally.

Quantum cellular automata A one-dimensional (1D) quantum elementary cellular
automaton may be defined as a chain of $L$ quantum bits (qubits) whose states
are updated according to repeated blocks of neighborhood-local unitary
operations along a discrete time axis. When every qubit’s state has been
updated, a QCA cycle, $t$, is completed. After selecting 1D chains of high-
quality qubits from the available hardware graph (Fig. 1a; see also
Supplementary Information), the structure (Fig. 1b) of a 1D QCA experiment is
comprised of an initialization step, followed by the application of some
number of QCA cycle unitaries out to cycle
$t\in\\{0,1,\ldots,t_{\text{max}}\\}$, and the measurement of appropriate
observables.

Figure 2:  Population dynamics and post-selection. a, The left panel shows a
noise-free, numerically-emulated Goldilocks QCA out to 30 cycles and
initialized with a single $|1\rangle$ in the middle of the 21-qubit chain.
Coherent local population, $\langle n_{i}\rangle$, dynamics that resist
equilibration can be observed in the form of the two blue diamond shapes. The
middle panel shows raw population dynamics for the same QCA circuit averaged
over four 21-qubit chains embedded into the 53-qubit Weber processor. The
right panel shows the same experimental data but with post-selection applied
based on domain wall conservation. b, Time-stamped population vignettes show
the same dynamics quantitatively for emulated (blue- lines for visual
clarity), raw (red), and post-selected (green) data. Error bars represent one
standard deviation from the mean over four different chains.

The particular QCA that we simulate is the totalistic, three-site Goldilocks
rule $T_{6}$ with a uniform Hadamard activation unitary applied to each qubit
and boundary conditions equivalent to fixed $|0\rangle$s (see Supplementary
Information) [25]. We note that the QCA notation $T_{6}$ should not be
confused with decoherence times, which we will denote $\tilde{T}_{1}$ and
$\tilde{T}_{2}$ where applicable. Fig. 1c shows how rule $T_{6}$ is compiled
down to quantum gates. A single, central bit flip initialization is followed
by one QCA cycle, and finally, measurement in the computational $z$-basis. The
local update, represented by two non-Clifford CH gates (green box), does
nothing if there are zero or two adjacent $|1\rangle$s and applies the
Hadamard activator to the central qubit if there is exactly one adjacent
$|1\rangle$: this is the trade-off rule that gives rise to the Goldilocks
nomenclature.

Population dynamics and error mitigation The quantum processor on which we run
our QCA simulations is a 53-qubit superconducting processor, Weber, which
follows the design of the Sycamore architecture outlined in Ref. [7] (see also
Supplementary Information). Typical performance characteristics for Weber are:
single-qubit gate error $e_{1}\approx 0.1\%$, two-qubit gate error
$e_{2}\approx 1.4\%$, $|0\rangle$-state readout error $e_{r0}\approx 2\%$,
$|1\rangle$-state readout error $e_{r1}\approx 7\%$, and population relaxation
time $\tilde{T}_{1}\approx 15\mu s$ [2]. Fig. 1d shows the decomposition of a
single QCA cycle (red box) to the native $\sqrt{\text{iSWAP}}^{\dagger}$ two-
qubit and
$\text{PhXZ}(a,x,z)\equiv\text{Z}^{z}\text{Z}^{a}\text{X}^{x}\text{Z}^{-a}$
family of single-qubit gates. Strictly speaking, the native two-qubit gate is
better modelled by $\sqrt{\text{iSWAP}}^{\dagger}\times\text{CPHASE}(\varphi)$
where the parasitic cphase is $\varphi\approx\pi/23$ [8]. We apply a suite of
low-overhead circuit optimization, calibration, and error mitigation
techniques to optimize circuit performance including moment alignment, spin-
echo insertion, Floquet calibration [8, 30], parasitic cphase compensation,
and most importantly, post-selection (see Supplementary Information).

Figure 3:  QCA mutual information network clustering. Clustering coefficient
as a function of QCA cycle for three intermediate system sizes simulated on
Weber, $L=15,17,\text{and}\>19$. Blue curves (lines for visual clarity) are
calculated from numerical emulation, while red (green) data points are from
Weber data without (with) post-selection. Error bars are one standard
deviation in $\mathcal{C}$ over four different chains. Dashed (dotted) black
lines are the clustering of the incoherent uniform random state with (without)
post-selection.

At each QCA cycle depth we measure the output of the circuit in the $z$-basis
$N_{c}=100,000$ times, resulting in a set of $L$-bit strings $\\{|z\rangle\\}$
and associated probabilities $\\{P_{z}\approx N_{z}/N_{c}\\}$, where $N_{z}$
is the number of times bit string $|z\rangle$ is observed. The local
population on each site is calculated via $\langle
n_{i}\rangle=(1-\sum_{z}P_{z}(-1)^{z_{i}})/2$ and averaged over four 1D qubit
chains. The left panel of Fig. 2a shows the numerical emulation of such a
procedure initialized with a single, central bit flip on 21 qubits, out to 30
QCA cycles. The two large-scale blue diamonds indicate coherent dynamics. When
repeated on the Weber processor, a combination of photon loss, gate error, and
state preparation and measurement (SPAM) error leads to nearly total
population decoherence by $t\approx 10$ (Fig. 2a, center panel). We therefore
post-select experimental data and discard any measurements whose eigenvalues
of the Ising-like operator $\mathcal{O}=\sum_{i=0}^{L}Z_{i}Z_{i+1}$ differ
from the corresponding eigenvalue of the initial state. That is, $\mathcal{O}$
is a dynamical invariant of the $T_{6}$ rule that keeps track of the number of
domain walls in the system. The right panel of Fig. 2a shows that post-
selection results in coherent population dynamics that persist beyond
$t\approx 10$, although different observables can degrade with noise on
slightly different timescales (see Fig. 3). The cycle-stamped population
vignettes shown in Fig. 2b support these observations more quantitatively,
with error bars representing one standard deviation on the four different
chains. After $t\approx 15$, error bars on the post-selected data become more
significant and while some qualitative features of the emulated population
dynamics appear to persist, such as larger population towards the center of
the chain, it is unclear from Fig. 2 alone as to what the underlying nature of
these qualitative similarities is. Moreover, our complex-network analysis of
the behavior of rule $T_{6}$ relies on the calculation of two-body observables
beyond the one-body observables depicted in Fig. 2. As such, we turn to a
calculation of Shannon mutual information both to more deeply understand the
long-time population dynamics of our QCA and to establish their complex-
network behavior.

Figure 4:  Small-world mutual information network behavior. a, Coherence
window, cycle-and-chain-averaged clustering, $\mathcal{C}$, as a function of
system size, $L$. b, Coherence window, cycle-and-chain-averaged path length,
$\ell$, as a function of system size, $L$. c, Normalized node strength
distribution, $P[g_{i}/(L-1)]$, amalgamated over all system sizes. d-g,
Heatmap and force-directed [23] complex network visualization of mutual
information network for $L=23$ at $t=9$ (blue: emulated; red: raw data from
Weber; green: post-selected; black: post-selected incoherent uniform
randomness). Where present, error bars represent one standard deviation from
the mean averaged over four different chains and cycles within the coherence
window.

Mutual information network analysis Following the complex-network approach in
neuroscience wherein functional connectivity of the brain is characterized
between spatially non-adjacent regions [12], we calculate the classical,
Shannon mutual information between all pairs of qubits in each 1D Goldilocks
QCA chain

$I_{ij}\equiv\sum_{z_{i}=0}^{1}\sum_{z_{j}=0}^{1}p(z_{i},z_{j})\log_{2}\frac{p(z_{i},z_{j})}{p(z_{i})p(z_{j})}$
(1)

and regard it as an adjacency matrix of correlations that defines the QCA
network at each cycle. We choose to use classical, rather than a measure of
quantum, mutual information because its calculation only requires measurements
in the computational $z$-basis, which we have shown are amenable to post-
selection. Moreover, we show in Supplementary Information that the Shannon
(classical) mutual information acts as a reliable proxy for von Neumann
(quantum) mutual information for the $T_{6}$ QCA.

Complex networks are ones that are neither purely regular, such as a lattice
or complete graph, nor entirely random [3]. The classic demonstration that a
network has complex, small-world character involves showing persistently large
clustering and simultaneously short path length [36], with a power-law node
strength distribution resulting in highly-connected nodes. By analogy with
transportation networks, these features describe networks that are easily
traversed both locally (clustering) and globally (path length), and exhibit
hubs (broad node strength distribution).

Through decoherence, the state of a quantum processor approaches an incoherent
uniformly random state with all amplitudes equal to $2^{-L/2}$ and for which
$I_{ij}=0$ for all $L\geq 2$. Hence, the incoherent uniformly random state is
neither locally nor globally traversable and is thus not a typical random
network. Upon post-selection, the decohered state is no longer uniform and the
corresponding mutual information network is both non-zero and non-random,
although to a much lesser extent than the states generated by Goldilocks QCA.
The complexity of networks generated by Goldilocks QCA is established by
computing network measures for emulated, raw processor, and post-selected
processor states and then comparing each of these to post-selected incoherent
uniform random states.

Clustering measures local network transitivity and is defined as the ratio of
the weighted number of closed triangles in the network to the weighted total
number of length-2 paths in the network (i.e., the number of potentially
closed triangles, see Supplementary Information)). The first relevant
signature of network complexity is intermediate to large clustering values
that do not decay with system size, in contrast to random networks. The
emulated clustering (blue curves) of the QCA exhibits this signature and
actually increases slightly as a function of system size, $L$ (see Fig. 3).
While we plot three of the larger system sizes we simulated here,
$L=15,17,\text{and}\>19$, this proves true for all other system sizes
simulated as well. Next, we note that without post-selection, the clustering
$\mathcal{C}$ calculated from raw data from Weber (red points) rises briefly
but then quickly decays toward zero, the incoherent uniformly random limit
(black dotted curve), at $t\approx 12$ for all three system sizes. In
contrast, the green curves in Fig. 3 show that with post-selection the
experimental clustering tracks the emulated clustering closely until $t\approx
6$ and remains larger than post-selected uniform randomness (black dashed
curve) until $t\approx 12$, independent of system size. There is therefore a
window between $t\approx 4$ to $12$ over which we can analyze the formation of
a non-random complex network in the QCA for all system sizes simulated. We
provide a more detailed description of our cycle windowing process in
Supplementary Information.

Fig. 4a shows the coherence window, cycle-and-chain-averaged emulated (blue),
raw (red), and post-selected (green) clustering coefficient for $L=5$ to $23$
qubits. After the finite-size effects encountered for $L\leq 11$, it is clear
that while the raw clustering trends towards zero– that of a incoherent
uniformly random state network– both the emulated and post-selected clustering
stabilize towards $\mathcal{C}\approx 0.3$ and appear to trend towards larger
values as a function of system size, indicating substantial network
transitivity beyond post-selected randomness (black dashed curve). Fig. 4b
shows the coherence window, cycle-and-chain-averaged weighted shortest path
length, $\ell$, as a function of system size, which gauges global network
traversability (see Supplementary Information). The raw data path length (red)
in Fig. 4b is large and increases as a function of system size. The post-
selected (green) path length tracks the emulated (blue) path length closely,
trends downward, and is always one to two orders of magnitude smaller than the
raw path length. Interestingly, post-selected path length tracks the path
length of post-selected randomness (black dashed line) nearly as well as it
does emulated path length. Taken together however, Figs. 4a-b signal the
existence of small-world mutual information networks generated in the
coherence window of the Goldilocks QCA beyond what can be obtained by post-
selecting incoherent uniform randomness. The end of the coherence window
($t=12$) for the largest system size simulated ($L=23$) corresponds to
$1,056\>\sqrt{\text{iSWAP}}^{\dagger}$ gates.

Fig. 4c further indicates the formation of small-world mutual information
networks, showing that the size-normalized emulated (blue) and post-selected
(green) node strength distributions (see Supplementary Information),
$P[g_{i}/(L-1)]$, are relatively flat between $1\times 10^{-2}$ to $2\times
10^{-1}$ compared with those of the post-selected random node strengths (black
dashes), which peak between $\sim 2.5\times 10^{-2}$ to $1.5\times 10^{-1}$,
and raw (red) node strengths, which are heavily biased towards much smaller
values, indicating a deficit in network connectivity. Finally, Figs. 4d-g
visually depict how the mutual information for $L=23$ at $t=9$ differs for the
raw QCA data, which approaches the network structure of incoherent uniform
randomness, and the emulated and post-selected QCA networks, which both
display lattice girder-like small-world structure that resemble one another
more closely than they do post-selected randomness.

Towards beyond-classical QCA In addition to their intrinsic scientific value
as quantum models for emergent complexity, QCA also present intriguing
prospects for establishing new inroads to the beyond-classical era. In the
instance of Goldilocks rule $T_{6}$, identification of a dynamical invariant
makes simulation less fragile to noise than a fully chaotic random quantum
circuit (RQC). Meanwhile, the system’s dynamics still occupy a significant
fraction of Hilbert space (see Supplementary Information), which scales as
$\sim 1.08^{L}$. For context, the long-time, cycle-averaged bond entropy of
rule $T_{6}$ was shown to scale between a 1D area and volume law [25].
Although simulation of Goldilocks rules has shown the failure of direct
matrix-product-state approaches [35], given this intermediate scaling it is an
open problem as to whether efficient classical simulatability may be achieved
using a modified tensor network approach [25, 20]. Moreover, efficient
simulatability of area law-scaling states in two-dimensions (2D) or higher
using tensor network approaches, while promising, is even less assured than in
1D. Hence, 2D QCA that exhibit area-law scaling (or worse) may be good
candidates for beyond-classical demonstrations.

Here we have demonstrated that existing quantum processors can efficiently
simulate 1D QCA with high fidelity at large gate volume. While reliant on the
availability of high-fidelity hardware, the main circuit design principles
that enable this goal consist of identification of particular QCA rules that:
i) generate significant complexity signatures, ii) efficiently compile to low-
depth sequences of hardware-native gates, and iii) are amenable to post-
selection through identification of one or more dynamical invariants. We
therefore expect these design principles to aid in discovering QCA that
support beyond-classical demonstrations or are otherwise useful in quantum
computational domain applications. In particular, employing such design
principles for QCAs that model correlated quantum matter could be a promising
route toward beyond-classical simulation of novel physical systems in the near
term.

Methods Please see Supplementary Information.

Data availability The data supporting this work will be made available upon
reasonable request to the corresponding authors.

Code availability The code supporting this work will be made available upon
reasonable request to the corresponding authors.

Acknowledgements We thank the Google Quantum AI team. This work was supported
in part by the NSF under grant PHY-1653820 (EK); and DGE-2125899, CCF-1839232,
PHY-1806372, and OAC-1740130 (MF, MTJ, LDC). This work was authored in part by
the National Renewable Energy Laboratory (NREL), operated by Alliance for
Sustainable Energy, LLC, for the U.S. Department of Energy (DOE) under
Contract No. DE-AC36-08GO28308. This work was supported in part by the
Laboratory Directed Research and Development (LDRD) Program at NREL. The views
expressed in the article do not necessarily represent the views of the DOE or
the U.S. Government. The U.S. Government retains, and the publisher, by
accepting the article for publication, acknowledges that the U.S. Government
retains, a nonexclusive, paid-up, irrevocable, worldwide license to publish or
reproduce the published form of this work, or allow others to do so, for U.S.
Government purposes.

Author contributions Conceptualization (EK, LDC). Data curation (EBJ, LEH,
MTJ, MF, ZJ, AH). Formal Analysis (EBJ, LEH, MTJ, MF, PR, ZJ, AH, CN, EO, EK,
LDC). Funding acquisition (PG, EK, LDC). Investigation (EBJ, LEH, MTJ, MF, PR,
ZJ, AH, CN, EO, EK, LDC). Methodology (EBJ, LEH, MTJ, MF, PR, ZJ, AH, CN, EO,
EK, LDC). Project administration (PR, AH, EO, EK, LDC). Resources (PR, ZJ, AH,
CN, EO). Software (EBJ, LEH, MTJ, ZJ, AH). Supervision (PG, EK, LDC).
Validation (all authors). Visualization (EBJ, LEH, PR, ZJ, AH, CN, EK, LDC).
Writing – original draft (EBJ). Writing – review & editing (all authors).

Competing interests The authors declare no competing interests.

Materials & Correspondence Materials requests to E.B. Jones. Correspondence to
E.B. Jones, E. Kapit, or L.D. Carr.

### References

  * Adamatzky [2010] A. Adamatzky.  _Game of life cellular automata_ , volume 1.  Springer, 2010.
  * AI [2021] G. Q. AI.  Quantum computer data sheet.  https://quantumai.google/hardware/datasheet/weber.pdf, May 2021\.
  * Albert and Barabási [2002] R. Albert and A.-L. Barabási.  Statistical mechanics of complex networks.  _Reviews of modern physics_ , 74(1):47, 2002.
  * Anderson [1972] P. W. Anderson.  More is different.  _Science_ , 177(4047):393–396, 1972.
  * Anderson [2018] P. W. Anderson.  _Basic notions of condensed matter physics_.  CRC Press, 2018.
  * Arrighi [2019] P. Arrighi.  An overview of quantum cellular automata.  _Natural Computing_ , 18(4):885–899, 2019.
  * Arute et al. [2019] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al.  Quantum supremacy using a programmable superconducting processor.  _Nature_ , 574(7779):505–510, 2019.
  * Arute et al. [2020a] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, A. Bengtsson, S. Boixo, M. Broughton, B. B. Buckley, et al.  Observation of separated dynamics of charge and spin in the fermi-hubbard model.  _arXiv preprint arXiv:2010.07965_ , 2020a.
  * Arute et al. [2020b] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, S. Boixo, M. Broughton, B. B. Buckley, D. A. Buell, et al.  Hartree-fock on a superconducting qubit quantum computer.  _Science_ , 369(6507):1084–1089, 2020b.
  * Bleh et al. [2012] D. Bleh, T. Calarco, and S. Montangero.  Quantum game of life.  _EPL (Europhysics Letters)_ , 97(2):20012, 2012\.
  * Brun and Mlodinow [2020] T. A. Brun and L. Mlodinow.  Quantum cellular automata and quantum field theory in two spatial dimensions.  _Physical Review A_ , 102(6):062222, 2020.
  * Bullmore and Sporns [2009] E. Bullmore and O. Sporns.  Complex brain networks: graph theoretical analysis of structural and functional systems.  _Nature reviews neuroscience_ , 10(3):186–198, 2009.
  * Carlson and Doyle [2002] J. M. Carlson and J. Doyle.  Complexity and robustness.  _Proceedings of the national academy of sciences_ , 99(suppl 1):2538–2545, 2002.
  * Chopard and Droz [1998] B. Chopard and M. Droz.  _Cellular automata_ , volume 1.  Springer, 1998.
  * Cook et al. [2004] M. Cook et al.  Universality in elementary cellular automata.  _Complex systems_ , 15(1):1–40, 2004.
  * Cotler and Wilczek [2020] J. Cotler and F. Wilczek.  Quantum overlapping tomography.  _Physical review letters_ , 124(10):100401, 2020\.
  * Developers [2021] C. Developers.  Cirq, Aug. 2021.  URL https://doi.org/10.5281/zenodo.5182845.  See full list of authors on Github: https://github .com/quantumlib/Cirq/graphs/contributors.
  * Donoghue et al. [2014] J. F. Donoghue, E. Golowich, and B. R. Holstein.  _Dynamics of the standard model_ , volume 35.  Cambridge university press, 2014.
  * Duranthon and Di Molfetta [2021] O. Duranthon and G. Di Molfetta.  Coarse-grained quantum cellular automata.  _Physical Review A_ , 103(3):032224, 2021.
  * Eisert et al. [2010] J. Eisert, M. Cramer, and M. B. Plenio.  Colloquium: Area laws for the entanglement entropy.  _Reviews of modern physics_ , 82(1):277, 2010\.
  * Farrelly [2020] T. Farrelly.  A review of quantum cellular automata.  _Quantum_ , 4:368, 2020.
  * Feynman [2018] R. P. Feynman.  Simulating physics with computers.  In _Feynman and computation_ , pages 133–153. CRC Press, 2018.
  * Fruchterman and Reingold [1991] T. M. Fruchterman and E. M. Reingold.  Graph drawing by force-directed placement.  _Software: Practice and experience_ , 21(11):1129–1164, 1991.
  * Gamel [2016] O. Gamel.  Entangled bloch spheres: Bloch matrix and two-qubit state space.  _Physical Review A_ , 93(6):062320, 2016.
  * Hillberry et al. [2021] L. E. Hillberry, M. T. Jones, D. L. Vargas, P. Rall, N. Y. Halpern, N. Bao, S. Notarnicola, S. Montangero, and L. D. Carr.  Entangled quantum cellular automata, physical complexity, and goldilocks rules.  _Quantum Science and Technology_ , 6(4):045017, 2021.  URL http://iopscience.iop.org/article/10.1088/2058-9565/ac1c41.
  * Jensen [1998] H. J. Jensen.  _Self-organized criticality: emergent complex behavior in physical and biological systems_ , volume 10.  Cambridge university press, 1998.
  * Jurcevic et al. [2021] P. Jurcevic, A. Javadi-Abhari, L. S. Bishop, I. Lauer, D. F. Bogorin, M. Brink, L. Capelluto, O. Günlük, T. Itoko, N. Kanazawa, et al.  Demonstration of quantum volume 64 on a superconducting quantum computing system.  _Quantum Science and Technology_ , 6(2):025020, 2021.
  * Lindgren and Nordahl [1988] K. Lindgren and M. G. Nordahl.  Complexity measures and cellular automata.  _Complex Systems_ , 2(4):409–440, 1988.
  * Muldoon et al. [2016] S. F. Muldoon, E. W. Bridgeford, and D. S. Bassett.  Small-world propensity and weighted brain networks.  _Scientific reports_ , 6(1):1–13, 2016.
  * Neill et al. [2021] C. Neill, T. McCourt, X. Mi, Z. Jiang, M. Niu, W. Mruczkiewicz, I. Aleiner, F. Arute, K. Arya, J. Atalaya, et al.  Accurately computing the electronic properties of a quantum ring.  _Nature_ , 594(7864):508–512, 2021.
  * Nielsen and Chuang [2002] M. A. Nielsen and I. Chuang.  Quantum computation and quantum information, 2002.
  * Pino et al. [2021] J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. Allman, C. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, et al.  Demonstration of the trapped-ion quantum ccd computer architecture.  _Nature_ , 592(7853):209–213, 2021.
  * Shah and Gorard [2019] R. Shah and J. Gorard.  Quantum cellular automata, black hole thermodynamics, and the laws of quantum complexity.  _arXiv preprint arXiv:1910.00578_ , 2019.
  * Turcotte and Rundle [2002] D. L. Turcotte and J. B. Rundle.  Self-organized complexity in the physical, biological, and social sciences, 2002.
  * Vargas [2016] D. L. Vargas.  Quantum complexity: Quantum mutual information, complex networks, and emergent phenomena in quantum cellular automata.  Master’s thesis, Colorado School of Mines. Arthur Lakes Library, 2016\.
  * Watts and Strogatz [1998] D. J. Watts and S. H. Strogatz.  Collective dynamics of âsmall-worldânetworks.  _nature_ , 393(6684):440–442, 1998.
  * Wolfram [1983] S. Wolfram.  Statistical mechanics of cellular automata.  _Reviews of modern physics_ , 55(3):601, 1983\.
  * Wolfram [1985] S. Wolfram.  Cryptography with cellular automata.  In _Conference on the Theory and Application of Cryptographic Techniques_ , pages 429–432. Springer, 1985.
  * Wright et al. [2019] K. Wright, K. Beck, S. Debnath, J. Amini, Y. Nam, N. Grzesiak, J.-S. Chen, N. Pisenti, M. Chmielewski, C. Collins, et al.  Benchmarking an 11-qubit quantum computer.  _Nature communications_ , 10(1):1–6, 2019.

##  Part I Supplementary Information

###### Contents

  1. I Supplementary Information
    1. I Quantum Cellular Automata in 1D
    2. II Quantum Hardware Specifications and Qubit Picking
      1. II.1 Weber Processor
      2. II.2 Rainbow Processor
    3. III Circuit Compilation, Calibration, and Optimization
    4. IV Post-Selection
    5. V Mutual Information Measures
    6. VI Complex Network Measures
      1. VI.1 Clustering Coefficient
      2. VI.2 Average Shortest Path Length
      3. VI.3 Node-Strength Distribution
    7. VII Establishing the Coherence Window
    8. VIII Effect of Higher Product State Filling

###  I Quantum Cellular Automata in 1D

A one-dimensional quantum cellular automaton is defined as a chain of $L$
identical qubits whose states are updated according to homogeneous blocks of
neighborhood-local unitary operators [6, 21]. Each local unitary takes as an
input the state of the target qubit’s neighbors and outputs a particular
operator, either the identity or the activation operator, to be applied to the
target qubit, conditioned on the neighborhood’s state. When such an update
unitary has been applied to all $L$ qubits, a QCA cycle is complete. In the
specific construction with nearest-neighbor connectivity, corresponding to
three-site (closed) neighborhoods (denoted $T_{R}$), a specific qubit’s open
neighborhood (its two neighbors) can be in a superposition of any $2^{2}$
states. The target qubit’s state can either be activated or not depending upon
these $4$ configurations. As such there are $2^{2^{2}}=16$ possible transition
functions on a three-site closed neighborhood. We label each of these
transition functions, or rules, as $R\in\\{0,1,\ldots,15\\}$. To specify a
three-site rule, we write $T_{R}$. The rule which activates for only a
balanced neighborhood of 0-1 or 1-0, $T_{6}$, is called the Goldilocks rule
and is the main focus of our study on the quantum processor.

For efficient circuit parallelization purposes, we update all even qubits in
parallel followed by all odd qubits. In this ordering, the general form for
the $L$-qubit unitary operator that evolves the system from cycle $t$ to cycle
$t+1$ is [25]

$\begin{split}U(T_{R};t,t+&1)=\prod_{o=1,3,\ldots}^{L}U_{o}(T_{R})\prod_{e=2,4,\ldots}^{L-1}U_{e}(T_{R}),\\\
U_{e(o)}(T_{R})=&\sum_{m,n=0}^{1}P_{e(o)-1}^{(m)}\otimes
V^{c_{mn}}_{e(o)}\otimes P_{e(o)+1}^{(n)}\end{split}$ (2)

where $i=e(o)$ indexes each even (odd) qubit in the 1D chain,
$P_{j}^{(m)}=|m\rangle\langle m|$ is a single-qubit projection operator, and
$V_{i}$ is the chosen activation unitary applied to qubit $i$ (which is
typically taken to be the same operator for all $i$). In order to convert from
a rule number to a unitary operator, one first performs a binary expansion of
the rule number where the expansion coefficients are themselves labelled by
2-bit strings, $R=\sum_{m,n=0}^{1}c_{mn}2^{m+n}$. The coefficients $c_{mn}$
describe which neighborhood configurations activation occurs on. For
Goldilocks rule $T_{6}$ considered in the main text, we have that $6=1\times
2^{1}+1\times 2^{2}$ so that $c_{00}=c_{11}=0$ while $c_{01}=c_{10}=1$.
Therefore, the local $T_{6}$ cycle unitary reads

$U_{i}(T_{6})=|00\rangle 1\langle 00|+|01\rangle V\langle 01|+|10\rangle
V\langle 10|+|11\rangle 1\langle 11|,$ (3)

which applies the activation unitary $V$ to qubit $i$ if its surrounding
qubits are in the configurations $|01\rangle$ or $|10\rangle$ and does nothing
otherwise. We refer to $T_{6}$ as a totalistic rule because activation obeys a
left-right symmetry and only depends on the total number of adjacent
$|1\rangle$s. Another important totalistic rule is $T_{1}$, also called the
PXP model in many-body quantum literature when run in continuous time [25];
here we consider discrete time, i.e., a quantum circuit, in line with the main
concept of cellular automata. Note that that for 1D, three-site neighborhoods
there are only $2^{3}=8$ totalistic rules. Restricting a QCA search space to
require totalistic updates is a useful tool for discovering emergent
complexity. Finally, we note that $V=X$, the bit-flip operator, corresponds to
a reversible classical cellular automaton. In the main text we choose $V=H$,
the Hadamard operator. It has been shown that the particular form of the
activation unitary affects the complexity outcomes of $T_{6}$ relatively
little so long as $V$ is able to move classical states off the poles of the
Bloch sphere, which $H$ does [25].

###  II Quantum Hardware Specifications and Qubit Picking

####  II.1 Weber Processor

Figure 5:  Weber parallel $|1\rangle$-state readout error rates. Each qubit is
represented by a square and is indexed by a row and column number. Heatmap
values represent the probability of finding a qubit in the $|0\rangle$ state
after it was prepared in the $|1\rangle$ state when all qubits are read out in
parallel.  Figure 6:  Weber idle $\tilde{T}_{1}$ decoherence times ($\mu$s).
Each qubit is represented by a square and is indexed by a row and column
number. Heatmap values represent the idle $\tilde{T}_{1}$ decoherence time in
$\mu$s.  Figure 7:  Weber parallel $\sqrt{\text{iSWAP}}^{\dagger}$ Pauli error
rates. Each qubit is indexed by a row and column number, and hexagons
represent couplers. Heatmap values represent the cross-entropy benchmarking
Pauli error per cycle when executed in parallel (see [7]).

The Weber quantum processing unit is a 53-qubit superconducting processor that
follows the design of the Sycamore-class architecture in Ref. [7]. As
discussed in the main text, typical performance characteristics for Weber are:
single-qubit gate error $e_{1}\approx 0.1\%$, two-qubit gate error
$e_{2}\approx 1.4\%$, $|0\rangle$-state readout error $e_{r0}\approx 2\%$,
$|1\rangle$-state readout error $e_{r1}\approx 7\%$, and population relaxation
time $\tilde{T}_{1}\approx 15\mu s$ [2]. Of these, the three performance
characteristics that are potentially the most deleterious to calculating
accurate observables are $e_{r1}$, $e_{2}$, and $\tilde{T}_{1}$ (relative to
total circuit execution time). Selecting high-quality chains of qubits
therefore involves simultaneously optimizing for these three characteristics,
which change slightly between processor calibrations.

For the particular calibration displayed, Fig. 5 shows that while the parallel
readout $e_{r1}$ on Weber is relatively homogeneous across the chip, it is
slightly lower on the right-hand side. Meanwhile, the idle $\tilde{T}_{1}$
decoherence times shown in Fig. 6 are somewhat longer on the right-hand side
of the processor as well and relatively uniform within its top right quadrant.
Finally, $e_{2}$ rates for the $\sqrt{\text{iSWAP}}^{\dagger}$ gate when
executed in parallel on Weber and characterized by cross-entropy benchmarking
(XEB) are lower both in the processor’s top-right quadrant and in a small
region left of center. Taken together, these observations indicate that the
top-right quadrant of Weber is an ideal region within which to choose 1D qubit
embeddings. For instance, a particular five qubit embedding that exploits this
quadrant has qubit indices (1, 6) $\rightarrow$ (2, 6) $\rightarrow$ (2, 7)
$\rightarrow$ (3, 7) $\rightarrow$ (4, 7). Of course, as chains become longer,
that is, as $L$ becomes larger, the available real-estate for picking the
highest-quality qubits becomes constrained.

####  II.2 Rainbow Processor

Figure 8:  Rainbow parallel $|1\rangle$-state readout error rates. Same data
as Fig. 5, but for the 23-qubit Rainbow quantum processor.  Figure 9:  Rainbow
idle $\tilde{T}_{1}$ decoherence times. Same data as Fig. 6, but for the
23-qubit Rainbow quantum processor.  Figure 10:  Rainbow parallel
$\sqrt{\text{iSWAP}}^{\dagger}$ Pauli error rates. Same data as Fig. 7, but
for the 23-qubit Rainbow quantum processor.

The Rainbow quantum processing unit is a 23-qubit superconducting processor
with typical performance characteristics similar to Weber. While the results
in the main text were generated on the Weber processor, we used Rainbow in
order to assess the effect of varying initial conditions in the product state.
These varying initial conditions were assessed in a 17-qubit chain, the
largest 1D chain embeddable on Rainbow. This size of the chain is large enough
to not be susceptible to the finite-size effects encountered in smaller
chains. At the same time it is not so large that low retained count fractions
cause problems with measurement statistics and thus create large error bars.
Figs. 8, 9, and 10 show the three most relevant performance characteristics
for choosing high-quality chains, parallel $e_{r1}$, $\tilde{T}_{1}$, and
parallel $e_{2}$, respectively. However, the ability to avoid noisy qubits on
Rainbow was severely constrained by the large size of the chain relative to
the size of the processor. For reference, we used the embedding (5, 0)
$\rightarrow$ (5, 1) $\rightarrow$ (4, 1) $\rightarrow$ (4, 2) $\rightarrow$
(4, 3) $\rightarrow$ (5, 3) $\rightarrow$ (5, 2) $\rightarrow$ (6, 2)
$\rightarrow$ (7, 2) $\rightarrow$ (7, 3) $\rightarrow$ (6, 3) $\rightarrow$
(6, 4) $\rightarrow$ (6, 5) $\rightarrow$ (7, 5) $\rightarrow$ (7, 4)
$\rightarrow$ (8, 4) $\rightarrow$ (8, 5).

###  III Circuit Compilation, Calibration, and Optimization

In order to simulate the $T_{6}$ QCA with high-fidelity, we compile,
calibrate, and optimize circuits in the following manner. The Cirq open source
framework was used for the workflow [17].

  1. 1.

Each $CH(q_{i},q_{j})$ gate between control qubit $q_{i}$ and target qubit
$q_{j}$ in the local $T_{6}$ update unitary is compiled into

$CH(q_{i},q_{j})=Y^{1/4}(q_{j})CZ(q_{i},q_{j})Y^{-1/4}(q_{j}),$ (4)

where up to a global phase $Y^{t}=R_{Y}(\pi t)$.

  2. 2.

Each $CZ$ gate is further decomposed into two bare
$\sqrt{\text{iSWAP}}^{\dagger}$ gates and single-qubit rotations. A
controlled-phase gate between control qubit $q_{i}$ and target qubit $q_{j}$
can be decomposed as

$\displaystyle\begin{split}\mathrm{CPHASE}(\phi)_{ij}&=e^{i(2\varphi-\phi)/4}\\\
\times&R_{Z_{i}}(\pi-\phi/2)\otimes R_{Z_{j}}(-\phi/2)\\\
\times&R_{X_{i}}(-\xi_{i})\otimes R_{X_{j}}(-\xi_{j})\\\
\times&K(\theta)_{ij}\mathrm{CPHASE}(\varphi)_{ij}\\\
\times&R_{Z_{i}}(\pi+\varphi/2)\otimes R_{Z_{j}}(\varphi/2)\\\
\times&R_{X_{i}}(-2\alpha)\otimes 1_{j}\\\
\times&K(\theta)_{ij}\mathrm{CPHASE}(\varphi)_{ij}\\\
\times&R_{Z_{i}}(\phi/2)\otimes R_{Z_{j}}(\phi/2)\\\
\times&R_{X_{i}}(\xi_{i})\otimes R_{X_{j}}(\xi_{j}),\end{split}$ (5)

which is equivalent to the decomposition presented in Ref. [8]. Here,
$K(\theta)$ is a continuously-parameterized fractional-iSWAP gate such that
$\sqrt{\text{iSWAP}}^{\dagger}=K(\pi/4)$. In this step, we take $\varphi=0$
and account for the parasitic $\varphi\approx\pi/23$ using Floquet calibration
in a later step. The other decomposition parameters are given by

$\sin(\alpha)=\sqrt{\frac{\sin^{2}(\phi/4)-\sin^{2}(\varphi/2)}{\sin^{2}(\theta)-\sin^{2}(\varphi/2)}},$
(6)
$\displaystyle\begin{split}\xi_{i}&=\tan^{-1}\Bigg{(}\frac{\tan(\alpha)\cos(\theta)}{\cos(\varphi/2)}\Bigg{)}\\\
&+\frac{\pi}{2}\Big{(}1-\text{sgn}\Big{(}\cos(\varphi/2)\Big{)}\Big{)},\end{split}$
(7)

and

$\displaystyle\begin{split}\xi_{j}&=\tan^{-1}\Bigg{(}\frac{\tan(\alpha)\sin(\theta)}{\sin(\varphi/2)}\Bigg{)}\\\
&+\frac{\pi}{2}\Big{(}1-\text{sgn}\Big{(}\sin(\varphi/2)\Big{)}\Big{)}.\end{split}$
(8)

To decompose the $CZ$ gate, we simply set $\phi=\pi$.

  3. 3.

Strings of consecutive single-qubit gates are merged together into
$\text{PhXZ}(a,x,z)\equiv Z^{z}Z^{a}X^{x}Z^{-a}$ gates using the cirq.google
optimized_for_sycamore utility. This compresses into alternating moments of
parallel single-qubit gates followed by parallel two-qubit gates.

  4. 4.

Spin echo insertion: Wherever a qubit is idle for more than one single-qubit
gate layer, pairs of Pauli operators are inserted to decrease idle qubit
crosstalk. For instance, $XX=1$.

  5. 5.

Floquet characterization: Our targeted native two-qubit gate on Weber is the
$\sqrt{\text{iSWAP}}^{\dagger}=K(\pi/4)$ gate. However, due to calibration
drift and cross-talk errors, the effective gate implemented has the form (see
Supplementary Information of Refs. [8, 30])

$\begin{split}\quad\quad&K(\theta,\zeta,\chi,\gamma,\varphi)=\\\
&\begin{bmatrix}1&0&0&0\\\
0&e^{-i\gamma-i\zeta}\cos(\theta)&-ie^{-i\gamma+i\chi}\sin(\theta)&0\\\
0&-ie^{-i\chi-i\gamma}\sin(\theta)&e^{-i\gamma+i\zeta}\cos(\theta)&0\\\
0&0&0&e^{-2i\gamma-i\varphi}\end{bmatrix}.\end{split}$ (9)

In the absence of calibration drift and cross-talk errors, $\theta=\pi/4$ and
$\zeta=\chi=\gamma=\varphi=0$, and one recovers the target gate as
$\sqrt{\text{iSWAP}}^{\dagger}=K(\pi/4,0,0,0,0)$. When such drift and errors
are present, the goal of Floquet characterization is to determine the values
of $\theta,\zeta,\chi,\gamma,$ and $\varphi$ with a view towards subsequently
correcting for some or all of them. This is done by repeating circuit moments
with two-qubit gates many times with interleaved, parameterized z-rotations as
probes, in order to amplify the calibration drift and control errors embodied
in $\theta,\zeta,\chi,\gamma,$ and $\varphi$. All five angles except for
$\chi$ are able to be characterized, since $\chi$ corresponds to a complex
hopping phase and requires closed loops in order to characterize. For more
details, see Refs. [8, 30].

  6. 6.

After Floquet characterization, the first angle we correct for is the
parasitic cphase angle, $\varphi$. We do this by reconstructing our circuits
and re-decomposing our $CZ$ gates using Eq. 5 where now instead of $\varphi=0$
we use the value determined by Floquet characterization on each moment, which
is typically in the vicinity of $\varphi\approx\pi/23$.

  7. 7.

Next, we re-merge single-qubit gates according to the procedure in Step 3.

  8. 8.

Re-insert spin echoes according to the logic of Step 4.

  9. 9.

Floquet calibration: In addition to $\varphi$, the angles $\gamma$ and $\zeta$
can be corrected for by inserting z-rotations on either side of an imperfect
two-qubit gate. The relationship between the general excitation-number-
conserving gate and our target gate (with parasitic cphase) is

$\begin{split}\quad\quad&K(\theta,0,0,0,\varphi)=\\\
&R_{Z}(-\beta,\beta)R_{Z}(\gamma,\gamma)K(\theta,\zeta,\chi,\gamma,\varphi)R_{Z}(-\alpha,\alpha),\end{split}$
(10)

where $\alpha=(\zeta+\chi)/2$, $\beta=(\zeta-\chi)/2$, and we use the
following shorthand for pairs of two single-qubit z-rotations,
$R_{Z}(z_{i},z_{j})=e^{i(z_{i}+z_{j})/2}R_{Z_{i}}(z_{i})\otimes
R_{Z_{j}}(z_{j})$. Since we cannot characterize $\chi$, we set $\chi=0$. The
resulting simplification in Eq. 10 will correct for $\gamma$ and $\zeta$. As
such, after the insertion of the z-rotations in Eq. 10, each $CZ$ gate in the
original QCA circuit is compiled correctly as in Eq. 5 with the effective two-
qubit native gate $\sim
K(\pi/4,0,0,0,\pi/23)=K(\pi/4)\mathrm{CPHASE}(\pi/23)$. The angles
$\theta\sim\pi/4$ and $\chi\sim 0$ remain uncorrected. The inserted,
corrective z-rotations are merged with the execution of two-qubit gates at the
hardware level and do not need to be re-merged into PhXZ gates.

  10. 10.

Send circuits to the quantum processor, Weber or Rainbow, in temporal batches,
averaging over qubit arrangements.

###  IV Post-Selection

Figure 11:  Fraction of $z$-basis measurements retained after post-selection.

Once measurement statistics are gathered by measuring $N_{c}$ times in the
$z$-basis, post-selection is used to discard measurements, i.e. bit strings,
that result from error and thus reside outside the invariant-protected sector
of Hilbert space. We emphasize that with a higher fidelity, post-selection
would be unnecessary for the establishment of coherence windows; generally
however, in the NISQ era post-selection is an important and useful tool for
quantum computing. The dynamical invariant that defines the protected sector
of Hilbert space is the operator

$\begin{split}\mathcal{O}\equiv\sum_{i=0}^{L}\mathcal{O}_{i},\\\
\mathcal{O}_{i}\equiv Z_{i}Z_{i+1}\end{split}$ (11)

where the sites $i=0$ and $i=L+1$ refer to padding boundary qubits fixed to
the $|0\rangle$ state. We first give a proof that $\mathcal{O}$ is a dynamical
invariant of the $T_{6}$ rule. Consider the commutator between Eq. 2 and Eq.
11

$\begin{split}\Big{[}\mathcal{O},U(T_{R};t,t+1)\Big{]}=\sum_{i=0}^{L}\Big{[}\mathcal{O}_{i},\prod_{o}U_{o}\prod_{e}U_{e}\Big{]}\\\
=\sum_{i=0}^{L}\Big{(}\Big{[}\mathcal{O}_{i},\prod_{o}U_{o}\Big{]}\prod_{e}U_{e}+\prod_{o}U_{o}\Big{[}\mathcal{O}_{i},\prod_{e}U_{e}\Big{]}\Big{)}.\end{split}$
(12)

Using standard commutator identities, the two commutators in the second line
of Eq. 12 can be expressed as

$\begin{split}\Big{[}\mathcal{O}_{i},\prod_{j}U_{j}\Big{]}=\sum_{j}\prod_{l^{\prime}>j}U_{l^{\prime}}\Big{[}\mathcal{O}_{i},U_{j}\Big{]}\prod_{l<j}U_{l}\\\
=\sum_{j}\prod_{l^{\prime}>j}U_{l^{\prime}}\Big{(}Z_{i}\Big{[}Z_{i+1},U_{j}\Big{]}+\Big{[}Z_{i},U_{j}\Big{]}Z_{i+1}\Big{)}\prod_{l<j}U_{l},\end{split}$
(13)

where $j$ can run over either the even or odd index set. Next, note that since
any projection operator commutes with the Pauli $Z$ operator,

$\begin{split}\Big{[}Z_{k},U_{j}\Big{]}=P_{j-1}^{(m)}\Big{[}Z_{j},V^{c_{mn}}_{j}\Big{]}\delta_{k,j}P_{j+1}^{(n)}.\end{split}$
(14)

Substituting Eqs. 14 and 13 into Eq. 12 and noting that
$Z_{k}P_{k}^{(m)}=P_{k}^{(m)}Z_{k}=(-1)^{m}P_{k}^{(m)}$ we find

$\begin{split}\Big{[}\mathcal{O},U(T_{R};t,t+1)\Big{]}=\\\
\sum_{o}\prod_{l^{\prime}>o}U_{l^{\prime}}\sum_{m,n}P_{o-1}^{(m)}\Big{[}Z_{o},V_{o}^{c_{mn}}\Big{]}P_{o+1}^{(n)}\Big{(}(-1)^{m}\\\
+(-1)^{n}\Big{)}\prod_{l<o}U_{l}\prod_{e}U_{e}\\\
+\prod_{o}U_{o}\sum_{e}\prod_{l^{\prime}>e}U_{l^{\prime}}\sum_{m,n}P_{e-1}^{(m)}\Big{[}Z_{e},V_{e}^{c_{mn}}\Big{]}P_{e+1}^{(n)}\Big{(}(-1)^{m}\\\
+(-1)^{n}\Big{)}\prod_{l<e}U_{l}\end{split}$ (15)

We now specify to the rule $T_{6}$. There are four combinations of $m$ and $n$
to consider. In the instance where $m=n=0$ or $m=n=1$, the commutator
$[Z_{j},V_{j}^{c_{m=n}=0}]=0$. Meanwhile, when $m\neq n$,
$(-1)^{m}+(-1)^{n}=0$. Therefore, each term indexed by $(m,n)$ vanishes and

$\Big{[}\mathcal{O},U(T_{6};t,t+1)\Big{]}=0,$ (16)

proving that $\mathcal{O}$ is a dynamical invariant of rule $T_{6}$ for any
unitary $V_{j}$.

In addition, $\mathcal{O}$ has eigenstates diagonal in the $z$-basis. Hence,
any $z$-basis measurement whose eigenvalue under $\mathcal{O}$ is different
than the $\mathcal{O}$-eigenvalue of the QCA’s initialized state must have
resulted from an error in the computation. In order to see this, and that Eq.
11 is related to domain wall conservation, consider the action of
$\mathcal{O}$ on a five-qubit chain, initialized with a single, central bit
flip, and padded by fixed boundary $|0\rangle$s

$\mathcal{O}\,|0\rangle\\!\otimes\\!|00100\rangle\\!\otimes\\!|0\rangle=2\,|0\rangle\\!\otimes\\!|00100\rangle\\!\otimes\\!|0\rangle.$
(17)

Now consider the action of $\mathcal{O}$ on another state with the same number
of domain walls

$\mathcal{O}\,|0\rangle\\!\otimes\\!|01110\rangle\\!\otimes\\!|0\rangle=2\,|0\rangle\\!\otimes\\!|01110\rangle\\!\otimes\\!|0\rangle.$
(18)

If however a bit flip were to occur on the central qubit in the chain, the
action of $\mathcal{O}$ would be

$\mathcal{O}\,|0\rangle\\!\otimes\\!|01010\rangle\\!\otimes\\!|0\rangle=-2\,|0\rangle\\!\otimes\\!|01010\rangle\\!\otimes\\!|0\rangle.$
(19)

Hence, the calculated eigenvalue of $-2$, rather than $+2$, indicates that we
should discard this measurement from our statistics when calculating
observables.

Note that $\mathcal{O}$ does not protect against all longitudinal relaxation
errors. For example, if the state in Eq. 18 relaxes on the qubit just left or
right of center, $\mathcal{O}$ still has eigenvalue $+2$. In addition, if two
photons are lost, say in both the central qubit and in the one just to the
right or left, $\mathcal{O}$ will also have eigenvalue $+2$. In instances such
as these, superposition amplitudes will renormalize in such a way as to
degrade the fidelity of the computation while still keeping the processor’s
state superposition in the protected subspace.

Fig. 11 shows the fraction of initial processor counts, $N_{c}$, that are
retained after applying post-selection to our experimental measurements from
Weber as a function of QCA cycle depth for all system sizes considered,
$L=5,7,9,\ldots,23$. Unsurprisingly, from $t=0$ to $t=14$, each set of data
points with constant $L$ decays exponentially as a function of QCA cycle as
the post-selection procedure has to discard exponentially many measurements in
order to compensate for $\tilde{T}_{1}$ decoherence. At $t=15$, there is an
evident step change in the decay rate of the retained count fractions. The
nominal gate execution times for PhXZ and $\sqrt{\text{iSWAP}}^{\dagger}$ on
Weber are 25 ns and 32 ns, respectively. Since each QCA cycle has eight
alternating layers of each, at $t=15$, the nominal circuit execution time
(excluding readout) is about $6.84\>\mu\text{s}$. While median $\tilde{T}_{1}$
times are about $15\>\mu\text{s}$, low end (10th percentile) $\tilde{T}_{1}$
times are about $11\>\mu\text{s}$ on Weber. Hence, at $6.84\>\mu\text{s}$, the
probability of a 10th percentile qubit erroneously relaxing from the
$|1\rangle$ state is about $47\>\%$, making it difficult for post-selection to
compensate for multi-photon loss processes or delocalizing errors. QCA cycle
$t=15$ is also the point referenced in the main text (e.g., main text Fig. 2b)
where the error bars on population dynamics begin to grow significantly.

In addition, the retained count fraction also decays roughly exponentially at
fixed $t$ as a function of $L$. The number of gate layers, and thus the
circuit execution time, is fixed as a function of system size for fixed QCA
cycle depth with respect to $\tilde{T}_{1}$. Since gate volume however grows
linearly in $L$, it is likely that this decay in the retained count fraction
as a function of system size is a result of accumulating gate error, as is
well-established within the digital error model [7].

Figure 12:  Relative Hilbert space dimension of sectors with constant
$\mathcal{O}=L-m$ for $m\in\\{3,7,11,15\\}$. These sectors correspond to
initial conditions with 1, 2, 3, and 4, $|1\rangle$’s that are well separated
by $|0\rangle$’s, respectively. Normalization is provided by the total Hilbert
space size $2^{L}$. Black lines are exponential fits to the last four data
points.

Since $T_{6}$ conserves $\mathcal{O}$, the system evolves in a Hilbert space
of reduced dimension $\mathcal{H}_{\mathcal{O}}$. In Fig. 12 we plot the
relative dimension $\dim(\mathcal{H}_{\mathcal{O}})/\dim(\mathcal{H}$) for
initial conditions consisting of a few $|1\rangle$’s separated by
$|0\rangle$’s. For the case studied in the main text, a single $|1\rangle$,
the relative Hilbert space dimension decays as $\propto e^{-L/1.63}$. Thus,
since $\dim(\mathcal{H})=2^{L}$, we have $\dim(\mathcal{H}_{L-3})\propto
1.08^{L}$.

###  V Mutual Information Measures

Figure 13:  Comparing Shannon and von Neumann mutual information. Distribution
of a, relative Frobenius distances and b, relative network measure differences
over 10,000 QCA cycles.

Consider a set of $z$-basis measurements
$\\{|z\rangle\>\>\text{s.t.}\in\\{0,1\\}^{\otimes N}\\}$ from an $N$-qubit
(subset of a) quantum processor and associated probabilities, $\\{P_{z}\\}$.
For any two qubits, $q_{i}$ and $q_{j}$, one can construct a $z$-basis joint
and two marginal probability distributions via

$\displaystyle p(z_{i},z_{j})$
$\displaystyle=\sum_{z^{\prime}}P_{z^{\prime}}\delta_{z_{i},z_{i}^{\prime}}\delta_{z_{j},z_{j}^{\prime}}$
(20) $\displaystyle p(z_{i(j)})$
$\displaystyle=\sum_{z_{j(i)}}p(z_{i},z_{j}).$ (21)

For two classical variables (e.g., bits) $z_{i}$ and $z_{j}$ with joint
probability distribution $p(z_{i},z_{j})$ and marginal probability
distributions, $p(z_{i})$ and $p(z_{j})$, the Shannon mutual information is
defined in terms of the Shannon entropy of a distribution, ${\rm H}(p)$, as
(see e.g., Ref. [31])

$I_{ij}\equiv{\rm H}[p(z_{i})]+{\rm H}[p(z_{j})]-{\rm H}[p(z_{i},z_{j})]$ (22)

and can be written as

$I_{ij}\equiv\sum_{z_{i}=0}^{1}\sum_{z_{j}=0}^{1}p(z_{i},z_{j})\log_{2}\frac{p(z_{i},z_{j})}{p(z_{i})p(z_{j})}.$
(23)

It measures, as a relative entropy, correlations in the variables $z_{i}$ and
$z_{j}$. That is, $I_{ij}\geq 0$ and $I_{ij}=0$ if and only if
$p(z_{i},z_{j})=p(z_{i})p(z_{j})$.

The quantum mechanical generalization of the classical probability
distributions is the reduced density matrix (RDM). For a Hilbert space
composed of two subspaces, $\mathcal{H}=\mathcal{H}_{A}\otimes\mathcal{H}_{B}$
and a density matrix $\rho\in\mathcal{H}$, the RDM of subspace
$\mathcal{H}_{A}$ is defined as

$\rho_{A}\equiv\text{Tr}_{B}\rho,$ (24)

where the the trace is taken over the degrees of freedom of subsystem
$\mathcal{H}_{B}$. RDMs can also be constructed from few-body quantum
observables. For instance, the single-qubit RDM for qubit $q_{i}$ can be
constructed as

$\rho_{i}=\frac{1}{2}\sum_{\mu=0}^{3}\langle\sigma_{i}^{\mu}\rangle\sigma_{i}^{\mu},$
(25)

where $\sigma_{i}^{0}=1_{i}$, $\sigma_{i}^{1}=X_{i}$, $\sigma_{i}^{2}=Y_{i}$,
and $\sigma_{i}^{3}=Z_{i}$ are elements of the Pauli algebra, and expectation
values are calculated from quantum processor measurements in the appropriate
basis [24]. Similarly, a $k$-qubit RDM can be calculated as

$\rho_{i_{1}\ldots
i_{k}}=\frac{1}{2^{k}}\sum_{\mu_{1},\ldots,\mu_{k}=0}^{3}\langle\sigma_{i_{1}}^{\mu_{1}}\otimes\ldots\otimes\sigma_{i_{k}}^{\mu_{k}}\rangle\sigma_{i_{1}}^{\mu_{1}}\otimes\ldots\otimes\sigma_{i_{k}}^{\mu_{k}}.$
(26)

Expectation values of long Pauli strings can be efficiently calculated via
schema such as quantum overlapping tomography [16]. With an RDM in hand, the
von Neumann entropy is defined as

$S(\rho)\equiv-\text{Tr}\rho\log_{2}\rho$ (27)

and the von Neumann mutual information between two qubits follows similarly

$I_{ij}^{\rm vN}\equiv S(\rho_{i})+S(\rho_{j})-S(\rho_{ij}).$ (28)

Calculation of $I_{ij}^{\rm vN}$ therefore requires measurements of
observables, such as $\langle X_{i}Z_{j}\rangle$, in bases other than the
$z$-basis. However, the dynamical invariant introduced in the main text,
$\mathcal{O}=\sum_{i=0}^{L}Z_{i}Z_{i+1}$, can only be used to post-select for
errors when measurement is performed in the $z$-basis. As such, we choose to
use Shannon mutual information for the calculation of complex network
measures.

As validation for this choice, we numerically emulate $L=19$ qubits
initialized with a single-bit flip and evolving under $T_{6}$ for 10,000
cycles. At each cycle we calculate the relative Frobenius distance $\|I-I^{\rm
vN}\|_{\rm F}/\|I\|_{\rm F}$, where the Frobenius norm of a matrix $M$ with
elements $M_{ij}$ is defined as

$\|M\|_{\rm F}=\sqrt{\sum_{i,j=0}^{L-1}|M_{ij}|^{2}}.$ (29)

Fig. 13a shows the distribution of the relative Frobenius distance between the
Shannon and Von Neumann mutual information across 10,000 cycles. The median
relative distance is $9.7\%$. We also examine relative differences of network
measures (defined in detail in the next section) in Fig. 13b. Clustering is
the most similar between Shannon and von Neumann-based mutual information
(blue histogram, median relative difference $0.7\%$). Path length (gold
histogram) exhibits a median relative difference $-18\%$) while that of node
strength (green histogram) is $8\%$. We conclude that the Shannon mutual
information is a reliable proxy the the von Neumann entropy at the level of,
at worst, a few percent. Moreover, since we use only the Shannon mutual
information in the main text, our conclusions regarding QCA network
complexity, as compared to random networks and post-selected incoherent
uniform random states, stand irrespective of the mutual information definition
employed.

###  VI Complex Network Measures

####  VI.1 Clustering Coefficient

In order to establish the small-world character of the $T_{6}$ QCA’s mutual
information network, we focus on three canonical complex network measures:
clustering, path length, and node strength distribution. Intuitively, one can
view the mutual information matrix $I_{ij}$, as an adjacency matrix in analogy
with that of a transportation network. For example, the economic activities of
two cities are likely to be more tightly intertwined if high-speed rail (large
adjacency weight) connects them rather than a rutted dirt track (low adjacency
weight). Similarly, the dynamics of two qubits will be more strongly
correlated if they share more mutual information.

Continuing with this analogy, the clustering coefficient gauges how locally
traversable a network is. Suppose Alice is attempting to reach City C from
City A, but there only exist rail lines from City A to City B and from City B
to City C, but no lines exist, or perhaps just a dirt track exists, between
City A and City C. Locally, this is an inefficient network to traverse since
Alice either has to travel through City B else has to take the dirt track to
get between Cities A and C. A highly traversable network at the local scale
also implies high network transitivity; that is, if Cities A and B are well-
connected and Cities B and C are well-connected, then so should be cities A
and C. The global clustering coefficient assesses this local transitivity in a
manner that averages over the entire network. At a particular cycle depth,
$t$, it is defined as

$\mathcal{C}\equiv\frac{\text{Tr}[I^{3}]}{\sum_{i\neq j=1}^{L}[I^{2}]_{ij}}.$
(30)

The numerator of Eq. 30 counts the weighted number of closed triangles (node
triplets) in the network, while the denominator is the weighted number of
length-2 paths in the network, that is, the weighted number of potentially
closed triangles. In the main text, we show that the Goldilocks rule $T_{6}$
exhibits sizeable clustering, much larger than the post-selected uniform
random state. The clustering grows with system size within the Weber processor
coherence window, indicating experimental formation of a series of locally
traversable networks.

####  VI.2 Average Shortest Path Length

A network’s average shortest path length measures the extent to which it is
globally traversable. In the transportation network analogy, a network of
cities (e.g., Atlanta, Nashville, Indianapolis, Detroit, Pittsburgh,
Baltimore, Raleigh, and Charlotte) laid out in a one-dimensional ring topology
but only connected to their nearest neighbors (Atlanta and Indianapolis for
Nashville) and next-nearest neighbors (Charlotte and Detroit for Nashville)
via high-speed rail lines would have very high local traversability, i.e.,
transitivity. However, it would take a relatively long time to traverse
between antipodes of the ring (e.g., Nashville to Baltimore) and thus those
cities’ economic activities might be less correlated. From the standpoint of
network weights, a large mutual information between two nodes should
contribute to shortening path length, such as a rail line that could carry
more passengers might, while small mutual information should increase the path
length by virtue of its low traversability, like the dirt track. We therefore
define the network-averaged weighted path length for a particular cycle depth
as

$\displaystyle\ell\equiv\frac{1}{L(L-1)}$ $\displaystyle\sum_{i\neq
j=1}^{L}d_{ij},$ (31) $\displaystyle d_{ij}=\min_{p_{ij}\in\mathcal{P}_{ij}}$
$\displaystyle\sum_{\langle k,l\rangle\in p_{ij}}1/I_{kl},$

where $d_{ij}$ is the minimum distance between nodes (i.e., qubits) $q_{i}$
and $q_{j}$, the sum in the first line runs over all pairs of qubits, and
$L(L-1)$ is the number of pairs in the network. The sum in the second line
runs over all edges ($\langle k,l\rangle$) in a particular path ($p_{ij}$)
between nodes $q_{i}$ and $q_{j}$ and the minimum is taken over all possible
paths ($\mathcal{P}_{ij}=\\{p_{ij}\\}$) between the two nodes. As discussed,
we use $1/I_{kl}$ as weights in the summand under the intuition that edges
with large mutual information are traversed easily while small mutual
information values should be detrimental to short path length, consistent with
[29].

####  VI.3 Node-Strength Distribution

The last complex network measure we consider is the node-strength
distribution. In the transportation network analogy, an efficiently
traversable network will have many nodes like Grand Central Station (termed
hubs) that have many, strong connections to other nodes as well as some nodes
that have few or weak connections, like Golden, Colorado, whose servicing
light rail line terminates three miles short of the center of town.
Mathematically, this translates into a broad, flat node-strength distribution.
We calculate a size-invariant (un-normalized) node-strength distribution,

$P[g_{i}/(L-1)]=\text{hist}\Bigg{[}\frac{1}{L-1}\sum_{j}I_{ij}\Bigg{]}$ (32)

Practically, Eq. 32 is evaluated by aggregating all size-scaled values of
$g_{i}/(L-1)=\sum_{j}I_{ij}/(L-1)$ across all system sizes,
$L\in\\{5,7,\ldots,23\\}$ into a set which is then histogrammed. The resulting
distribution is increasingly biased towards low node strength as the network
approaches randomness. Small-world networks have broad, flat distributions,
while distributions that are more sharply-peaked around smaller ranges of
values indicate increasing non-random regularity in the network.

###  VII Establishing the Coherence Window

Figure 14:  Establishing the coherence window. Clustering coefficient
calculated from the post-selected data generated from the Weber processor
(green data points), as a function of QCA cycle and for all system sizes
simulated (one in each panel), $L\in\\{5,7,\ldots,23\\}$. Error bars: one
standard deviation from the mean on four different qubit chains. Horizontal
dashed lines: clustering coefficient for post-selected incoherent uniform
randomness, based on the QCA initial condition of a single $|1\rangle$
initialized in a chain of $L$ qubits. Vertical dashed lines: beginning and end
of the coherence window in each subplot.

As discussed in the main text, our Goldilocks QCA circuits, when aided by
post-selection, generate mutual information complex network observables that
exhibit structure in excess of post-selected incoherent uniform randomness.
Fig. 14 shows the clustering coefficient calculated from the post-selected
data generated from the Weber processor (green data points), as a function of
QCA cycle and for all system sizes simulated, $L\in\\{5,7,\ldots,23\\}$. Over
the first few cycles, the clustering coefficient climbs from zero until it
crosses the horizontal dashed line in each panel, which is the value of the
clustering coefficient for the incoherent uniform random state subject to the
same post-selection procedure as the QCA data from Weber. The left-most
vertical dashed line demarcates this point, which is the QCA cycle at which
the post-selected experimental clustering becomes larger than post-selected
randomness. In all cases, the post-selected experimental clustering continues
to climb for a few cycles until decoherence mechanisms begin to degrade the
data in excess of what post-selection can mitigate for, typically at $t\approx
8$. After a few more cycles, the post-selected experimental clustering drops
to the clustering value of post-selected incoherent uniform randomness and
remains there for the rest of the simulation. The right-most vertical dashed
line demarcates this point, which occurs at $t\approx 12$ roughly independent
of system size. For each system size, the region between the two vertical
dashed lines is where the post-selected experimental clustering is in excess
of post-selected incoherent uniform randomness and is therefore the coherence
window over which we calculate the cycle-averaged complex network observables.
We remark that after the end of the coherence window, $t\approx 12$, for
$L=21$ and $L=23$ the post-selected experimental clustering fails to return to
the value associated with post-selected incoherent uniform randomness. We do
not regard this as an extension of the coherence window. Rather, inspection of
Fig. 11 shows that after $t\approx 12$, the 21-qubit chains are retaining
fewer than roughly 100 of the 100,000 initial measurements while the 23-qubit
chains are retaining fewer than about 10 of the initial 100,000 measurements.
As such, error bars become significant and calculation of observables after
$t\approx 12$ in each case becomes unreliable.

###  VIII Effect of Higher Product State Filling

Figure 15:  Effect of higher product state filling. Clustering coefficient as
a function of QCA cycle for three different numbers of isolated $|1\rangle$s
in the initial product state, 3, 4, and 5, for $L=17$ on the Rainbow processor
(blue curves: numerical emulation; red points: Rainbow data without post-
selection; green points: with post-selection). Error bars are one standard
deviation in $\mathcal{C}$ over four different qubit chains. Black dashed
lines represent the clustering of the incoherent uniform random state, subject
to post-selection on the appropriate eigenvalues of $\mathcal{O}$
corresponding to the three different initial conditions: 10 ($L-7$), 6
($L-11$), and 2 ($L-15$).

Throughout the main text, we have focused on a particular initial condition
for our Goldilocks QCA circuits, namely $|0\ldots 010\ldots 0\rangle$, a
single central bit flip in a chain of $L$ qubits. This was done so as to be
able to perform finite size scaling analyses of complex network measures in a
sensible and well-controlled manner, as well as the close analogy to a
standard initial condition for elementary classical cellular automata.
Moreover, it was previously shown that the ability of Goldilocks QCA to
generate physical complexity is largely insensitive to initial conditions
[25]. However, it is an important question as to whether our experimental
protocol, including post-selection, for effectively generating coherent small-
world mutual information networks generalizes beyond the particular instance
of the single bit-flip initialization.

Fig. 15 shows the effect of increasing the number of isolated bit flips in the
initial state on clustering dynamics of a 17-qubit chain simulated on Google’s
23-qubit Rainbow processor. In particular, the left panel corresponds to the
initial condition $|00000100000100000\rangle$, the middle panel corresponds to
the initial condition $|00010000100001000\rangle$ and the right panel
corresponds to the initial condition $|00100010001000100\rangle$, i.e.,
equally spaced $|1\rangle$’s. We observe the following. First, the long-time
average clustering values of the emulated data fall as the number of initial
bit flips increase. Second, the raw clustering follows the expected behavior
in all the panels, rising briefly before decaying down to incoherent uniform
randomness at around $t\approx 12$. Third and most importantly however, we
note that increasing the number of initial bit flips degrades the ability of
our post-selection to correct for errors. While two initial bit flips (left
panel) results in post-selected experimental clustering that follows the
emulated curve relatively closely until $t\approx 4$ when it begins to
degrade, three bit flips (middle panel) results in agreement out to only
$t\approx 2$, and four initial bit flips (right panel) sees immediate
disagreement between emulation and post-selected experiment after $t\approx
1$. In fact, for four initial bit flips, there is no QCA cycle for which post-
selected experimental clustering is meaningfully improved over raw
experimental clustering during the coherence window. This indicates that while
our experimental protocol, including post-selection, is most appropriately
applied at very low initial bit flip filling, it struggles to produce emergent
complexity in the face of noise at higher filling fractions. This is likely
because at higher initial isolated bit-flip filling, there are more error
processes that cause amplitude renormalization but still keep the state vector
in the protected sector of Hilbert space. That is, there are more locations in
a higher-filling bit string where an erroneous bit flip will nonetheless
result in domain wall conservation.


# Sufficient conditions for the unique solution of a class of new Sylvester-
like absolute value equation††thanks: This research was supported by National
Natural Science Foundation of China (No. 11961082).

Shi-Liang Wu, Cui-Xia Li
†School of Mathematics, Yunnan Normal University,
Kunming, 650500, PR China  wushiliang1999<EMAIL_ADDRESS>
###### Abstract

In this paper, a class of new Sylvester-like absolute value equation (AVE)
$AXB-|CXD|=E$ with $A,C\in\mathbb{R}^{m\times n}$, $B,D\in\mathbb{R}^{p\times
q}$ and $E\in\mathbb{R}^{m\times q}$ is considered, which is quite distinct
from the published work by Hashemi [Applied Mathematics Letters, 112 (2021)
106818]. Some sufficient conditions for the unique solution of the Sylvester-
like AVE are obtained.

Keywords: New Sylvester-like absolute value equation; unique solution;
sufficient condition

AMS classification: 90C05, 90C30, 65F10

##  1 Introduction

As is known, the standard absolute value equation (AVE)

$Ax+|x|=f$ (1.1)

and its general version

$Ax+C|x|=f$ (1.2)

are very strong tools in the field of optimization, including the
complementarity problem, linear programming and convex quadratic programming,
where $A$ and $C$ may be rectangular matrices of the same order. Based on
this, the AVE (1.1)/(1.2) has caused wide public concern over the recent
years.

The AVE (1.2) was first introduced in [1] by Rohn. Therewith, its main
research contents consist of two aspects: one is to multifarious numerical
methods for obtaining its numerical solution, see [2, 3, 4, 5, 6, 7, 8, 9, 10,
11], and the other is theoretical analysis, including the existence of
solvability, bounds for the solutions, various equivalent reformulations, and
so on, see [12, 13, 14, 15, 16, 17, 18].

Recently, in [19], Hashemi generalized the concept of absolute value equation
and considered the following Sylvester-like absolute value equation (AVE)

$AXB+C|X|D=F,$ (1.3)

where $A,C\in\mathbb{R}^{m\times n}$, $B,D\in\mathbb{R}^{p\times q}$,
$F\in\mathbb{R}^{m\times q}$ are given. For the Sylvester-like AVE (1.3),
Hashemi in [19] established some sufficient conditions for its unique
solution. Further, in [20], Wang and Li considered the Sylvester-like AVE
(1.3) with square coefficient matrices. Some new sufficient conditions were
gained in [20], which are different from the results in [19].

Further, in [21], Wu found a type of new generalized absolute value equation
(NGAVE), which is below

$Ax-|Bx|=d,$ (1.4)

with $A,B\in\mathbb{R}^{n\times n}$ and $d\in\mathbb{R}^{n}$. Likewise, Wu in
[21] established some necessary and sufficient conditions for the unique
solution of the NGAVE (1.4). Clearly, the NGAVE (1.4) is quite different from
the AVE (1.2).

Inspired by the work in [21], together with the Sylvester-like AVE (1.3), in
this paper, we consider a type of new Sylvester-like absolute value equation
(AVE) below

$AXB-|CXD|=F,$ (1.5)

where $A,C\in\mathbb{R}^{m\times n}$, $B,D\in\mathbb{R}^{p\times q}$,
$F\in\mathbb{R}^{m\times q}$ are given. Here, the new Sylvester-like AVE (1.5)
not only is the generalization form of the GAVE (1.4), but also is from other
fields, such as interval matrix equations [22, 23, 24, 25, 26, 27], robust
control [28], and so on. Similar to the Sylvester-like AVE (1.3), the theory
and practice of the new Sylvester-like AVE (1.5) is still interested and
challenged because of the nonlinear and nondifferentiable term $|CXD|$ in
(1.5). This is our motivation for this paper. At present, to our knowledge,
for the unique solution of the new Sylvester-like AVE (1.5), the necessary and
sufficient condition is _vacant_. Based on this, the goal of the present paper
is to fill in this vacant, gain some sufficient conditions for the unique
solution of the new Sylvester-like AVE (1.5). What’s more, some useful
necessary and sufficient conditions for the unique solution of the new
Sylvester-like AVE (1.5) are obtained with square coefficient matrices.

##  2 Main result

In this section, we will present some conditions for the unique solution of
the new Sylvester-like AVE (1.5). To achieve this goal, by using the Kronecker
product and the vec operator, the new Sylvester-like AVE (1.5) can be
expressed as the NGAVE below

$Sx-|Tx|=f$ (2.1)

with $S=B^{T}\otimes A$, $T=D^{T}\otimes C$, $x=vec(X)$ and $f=vec(F)$, where
‘$\otimes$’, ‘$vec$’ stand for the Kronecker product and the vec operator,
respectively.

To discuss the sufficient condition for the unique solution of the new
Sylvester-like AVE (1.5), Lemmas 2.1, 2.2, 2.3 and 2.4 are required.

######  Lemma 2.1.

_[21]_ Let matrix $A$ in $(\ref{eq:4})$ be nonsingular. If

$\rho((I-2D)BA^{-1})<1$ (2.2)

for any diagonal matrix $D=\mbox{diag}(d_{i})$ with $d_{i}\in[0,1]$, then the
NGAVE $(\ref{eq:4})$ for any $d\in\mathbb{R}^{n}$ has a unique solution.

######  Lemma 2.2.

_[21]_ The NGAVE $(\ref{eq:4})$ for any $d\in\mathbb{R}^{n}$ has a unique
solution if and only if matrix $A+(I-2D)B$ is nonsingular for any diagonal
matrix $D=\mbox{diag}(d_{i})$ with $d_{i}\in[0,1]$.

######  Lemma 2.3.

_[29]_ Let $A,B\in\mathbb{R}^{n\times n}$. Then

$\sigma_{i}(A+B)\geq\sigma_{i}(A)-\sigma_{1}(B),i=1,2\ldots,n,$

where $\sigma_{1}\geq\ldots\geq\sigma_{n}(\geq 0)$ are the singular values of
matrix.

Based on Lemmas 2.2 and 2.3, Lemma 2.4 can be obtained.

######  Lemma 2.4.

If

$\sigma_{1}(B)<\sigma_{n}(A)$ (2.3)

where $\sigma_{1}$ and $\sigma_{n}$ denote the largest and smallest singular
value, respectively, then the NGAVE $(\ref{eq:4})$ for any
$d\in\mathbb{R}^{n}$ has a unique solution.

Proof. Based on Lemma 2.3, the NGAVE $(\ref{eq:4})$ has a unique solution for
any $d\in\mathbb{R}^{n}$ when the matrix $A+(I-2D)B$ is nonsingular for any
diagonal matrix $D=\mbox{diag}(d_{i})$ with $0\leq d_{i}\leq 1$. So, let
$\sigma_{n}(A+(I-2D)B)$ stand for the minimal singular value of the matrix
$A+(I-2D)B$. Based on Lemma 2.3, we have

$\sigma_{n}(A+(I-2D)B)\geq\sigma_{n}(A)-2\sigma_{1}((I-2D)B).$

Since
$\sigma_{1}((I-2D)B)\leq\sigma_{1}((I-2D))\sigma_{1}(B)\leq\sigma_{1}(B)$, the
result in Lemma 2.4 holds under the condition (2.3). $\hfill{}\Box$

Based on the above lemmas, we can present some conditions for the unique
solution of the new Sylvester-like AVE $(\ref{eq:5})$ for any $F$. First, by
using Lemma 2.1 indirectly, we can obtain the following result, see Theorem
2.1.

######  Theorem 2.1.

Let $A,B$ be square nonsingular matrix in $(\ref{eq:5})$. If

$\rho((I-2\Lambda)((B^{-1}D)^{T}\otimes CA^{-1}))<1$ (2.4)

for any diagonal matrix $\Lambda=\mbox{diag}(\lambda_{i})$ with
$\lambda_{i}\in[0,1]$, then the new Sylvester-like AVE $(\ref{eq:5})$ has a
unique solution for any $F$.

Proof. Since

$S^{-1}=(B^{T}\otimes A)^{-1}=B^{-T}\otimes A^{-1},$

we have

$TS^{-1}=(D^{T}\otimes C)(B^{-T}\otimes A^{-1})=D^{T}B^{-T}\otimes
CA^{-1}=(B^{-1}D)^{T}\otimes CA^{-1}.$

Based on Lemma 2.1, clearly, the result in Theorem 2.1 is right.
$\hfill{}\Box$

Clearly, we can use $\rho(((B^{-1}D)^{T}\otimes CA^{-1})(I-2\Lambda))<1$
instead of the condition (2.4) Theorem 2.1.

In fact, the condition (2.4) in Theorem 2.1 is not easy to implement in
practice. Even if the condition (2.4) in Theorem 2.1 can be executed, the
number of arithmetic operations is required to compute the spectral radius of
the huge matrix. For instance, for $A,C\in\mathbb{R}^{m\times m}$ and
$B,D\in\mathbb{R}^{n\times n}$, the number of arithmetic operations is
$\mathcal{O}(n^{3}m^{3})$. Therefore, the sum of the powers here is $3+3=6$,
i.e., the complexity here is sextic. Faced with this situation, we have to get
some conditions that can be detected. By the simple calculation, we have

$\displaystyle(I-2\Lambda)((B^{-1}D)^{T}\otimes CA^{-1})$
$\displaystyle\leq|(I-2\Lambda)((B^{-1}D)^{T}\otimes CA^{-1}|$
$\displaystyle\leq|I-2\Lambda||(B^{-1}D)^{T}\otimes CA^{-1})|$
$\displaystyle\leq|(B^{-1}D)^{T}\otimes CA^{-1})|$
$\displaystyle=|(B^{-1}D)^{T}|\otimes|CA^{-1}|.$

Note that

$\rho(|(B^{-1}D)^{T}|\otimes|CA^{-1}|)=\rho(|(B^{-1}D)^{T}|)\rho(|CA^{-1}|)=\rho(|B^{-1}D|)\rho(|CA^{-1}|).$

So, we have the following result, see Theorem 2.2.

######  Theorem 2.2.

Let $A,B$ be square nonsingular matrix in $(\ref{eq:5})$. If

$\rho(|B^{-1}D|)\rho(|CA^{-1}|)<1,$ (2.5)

then the new Sylvester-like AVE $(\ref{eq:5})$ has a unique solution for any
$F$.

In addition, based on Theorem 5.6.10 in [30], we also have

$\displaystyle\rho((I-2\Lambda)((B^{-1}D)^{T}\otimes CA^{-1}))$
$\displaystyle\leq\sigma_{1}((I-2\Lambda)((B^{-1}D)^{T}\otimes CA^{-1}))$
$\displaystyle\leq\sigma_{1}(I-2\Lambda)\sigma_{1}((B^{-1}D)^{T}\otimes
CA^{-1})$ $\displaystyle\leq\sigma_{1}((B^{-1}D)^{T}\otimes CA^{-1})$
$\displaystyle=\sigma_{1}((B^{-1}D)^{T})\sigma_{1}(CA^{-1})$
$\displaystyle=\sigma_{1}(B^{-1}D)\sigma_{1}(CA^{-1}).$

Based on this, Theorem 2.3 can be obtained.

######  Theorem 2.3.

Let $A,B$ be square nonsingular matrix in $(\ref{eq:5})$. If

$\sigma_{1}(B^{-1}D)\sigma_{1}(CA^{-1})<1,$ (2.6)

then the new Sylvester-like AVE $(\ref{eq:1})$ has a unique solution for any
$F$.

Compared with Theorem 2.1, indeed, the conditions of Theorems 2.2 and 2.3 can
be easy to execute. Here, it is noted that the conditions of Theorems 2.2 and
2.3 only work if $A$ and $B$ are nonsingular. In addition, for a general
square matrix $H$, there is no relations between $\sigma_{1}(H)$ and
$\rho(|H|)$ unless one adds yet more additional requirements. Based on this
fact, Theorem 2.3 sometimes performs better than Theorem 2.2, vice versa.

To obtain the sufficient condition that is more general, based on Lemma 2.4,
Theorem 2.4 can be obtained and its proof is omitted.

######  Theorem 2.4.

If

$\sigma_{1}(C)\sigma_{1}(D)<\sigma_{n}(A)\sigma_{n}(B)$ (2.7)

then the new Sylvester-like AVE $(\ref{eq:1})$ has a unique solution for any
$F$.

Compared with Theorems 2.2 and 2.3, Theorem 2.4 not only is fit for the square
matrix, but also is fit for the rectangular matrix. This implies that the
condition (2.7) in Theorem 2.4 is indeed more general.

It is not difficult to find that all the conditions of Theorems 2.2, 2.3 and
2.4 can be checked. Not only that, the computational complexity of all the
conditions in Theorems 2.2, 2.3 and 2.4 is cubic.

By the way, for $m=n=p=q$ in (1.5), combining Theorems 3.1 and 3.2 in [21]
with Lemma 2.4, we can obtain the following necessary and sufficient
conditions for the unique solution of the new Sylvester-like AVE
$(\ref{eq:5})$, see Theorem 2.5.

######  Theorem 2.5.

Let $S=B^{T}\otimes A$, $T=D^{T}\otimes C$. Then the following statements are
equivalent:

$1.$ the new Sylvester-like AVE $(\ref{eq:1})$ has a unique solution for any
$F\in\mathbb{R}^{n\times n}$;

$2.$ $\\{S+T,S-T\\}$ has the row $\mathcal{W}$-property;

$3.$ $det(F_{1}(S+T)+F_{2}(S-T))\neq 0$ for arbitrary nonnegative diagonal
matrices $F_{1},F_{2}\in\mathbb{R}^{n\times n}$ with
$\mbox{diag}(F_{1}+F_{2})>0$;

$4$. matrix $(S-T)(S+T)^{-1}$ is a $P$-matrix (all its principal minors are
positive), where matrix $S+T$ is invertible;

$5$. matrix $S+(I-2\Lambda)T$ is nonsingular for any diagonal matrix
$\Lambda=\mbox{diag}(\lambda_{i})$ with $\lambda_{i}\in[0,1]$.

Since the order of the matrices $S$ and $T$ in Theorem 2.5 is $n^{2}\times
n^{2}$, the number of arithmetic operations required to check both parts 2, 3,
4 and 5 of Theorem 2.5 is at-least sextic, i.e., $\mathcal{O}(n^{6})$.
Therefore, the computational complexity of all the conditions in Theorem 2.5
is at-least $\mathcal{O}(n^{6})$.

##  3 Conclusions

In this paper, the unique solution of a type of new Sylvester-like absolute
value equation (AVE) $AXB-|CXD|=E$ with $A,C\in\mathbb{R}^{m\times n}$,
$B,D\in\mathbb{R}^{p\times q}$ and $E\in\mathbb{R}^{m\times q}$ has been
discussed. Some useful sufficient conditions for the unique solution of the
new Sylvester-like AVE are obtained. Particularly, all the sufficient
conditions of Theorems 2.2, 2.3 and 2.4 can be checked with a cubic complexity
in the light of the order of the input matrices.

## References

  * [1] J. Rohn, Systems of linear interval equations, Linear Algebra Appl., 126 (1989) 39-78.
  * [2] L. Caccetta, B. Qu, G.-L. Zhou, A globally and quadratically convergent method for absolute value equations, Comput. Optim. Appl., 48 (2011) 45-58.
  * [3] O.L. Mangasarian, A generalized Newton method for absolute value equations, Optim. Lett., 3 (2009) 101-108.
  * [4] J. Rohn, An algorithm for solving the absolute value equations, Electron. J. Linear Algebra., 18 (2009) 589-599.
  * [5] D.K. Salkuyeh, The Picard-HSS iteration method for absolute value equations, Optim. Lett., 8 (2014) 2191-2202.
  * [6] S.-L. Wu, C.-X. Li, A special Shift-splitting iterative method for the absolute value equations, AIMS Math., 5 (2020) 5171-5183.
  * [7] C.-X. Li, S.-L. Wu, Modified SOR-like iteration method for absolute value equations, Math. Probl. Eng., 2020 (2020) 9231639.
  * [8] P. Guo, S.-L. Wu, C.-X. Li, On SOR-like iteration method for solving absolute value equations, Appl. Math. Lett., 97 (2019) 107-113.
  * [9] Y.-Y. Lian, C.-X. Li, S.-L. Wu, Weaker convergent results of the generalized Newton method for the generalized absolute value equations, J. Comput. Appl. Math., 338 (2018) 221-226.
  * [10] C.-X. Li, A preconditioned AOR iterative method for the absolute value equations, Inter. J. Comput. Meth., 14 (2017) 1750016\.
  * [11] C.-X. Li, A modified generalized Newton method for the absolute value equations, J. Optim. Theory Appl., 170 (2016) 1055-1059.
  * [12] J. Rohn, A theorem of the alternatives for the equation $Ax+B|x|=b$, Linear Multilinear A., 52 (2004) 421-426.
  * [13] S.-L. Wu, C.-X. Li, A note on unique solvability of the absolute value equation, Optim. Lett., 14 (2020) 1957-1960.
  * [14] O.L. Mangasarian, R.R. Meyer, Absolute value equations, Linear Algebra Appl., 419 (2006) 359-367.
  * [15] S.-L. Wu, C.-X. Li, The unique solution of the absolute value equations, Appl. Math. Lett., 76 (2018) 195-200.
  * [16] O. Prokopyev, On equivalent reformulations for absolute value equations, Comput. Optim. Appl., 44 (2009) 363-372.
  * [17] M. Hladík, Bounds for the solutions of absolute value equations, Comput. Optim. Appl., 69 (2018) 243-266.
  * [18] S.-L. Wu, S.-Q. Shen, On the unique solution of the generalized absolute value equation, Optim. Lett., 2020, https://doi.org/10.1007/s11590-020-01672-2.
  * [19] B. Hashemi, Sufficient conditions for the solvability of a Sylvester-like absolute value matrix equation, Appl. Math. Lett., 112 (2021) 106818.
  * [20] L.-M. Wang, C.-X. Li, New sufficient conditions for the unique solution of a square Sylvester-like absolute value equation, Appl. Math. Lett., 116 (2021) 106966.
  * [21] S.-L. Wu, The unique solution of a class of the new generalized absolute value equation, Appl. Math. Lett., 116 (2021) 107029.
  * [22] A. Neumaier, Interval Methods for Systems of Equations, Cambridge University Press, Cambridge, 1990.
  * [23] N.P. Seif, S.A. Hussein, A.S. Deif, The interval Sylvester equation, Computing., 52 (1994) 233-244.
  * [24] B. Hashemi, M. Dehghan, Results concerning interval linear systems with multiple right-hand sides and the interval matrix equation $AX=B$, J. Comput. Appl. Math., 235 (2011) 2969-2978.
  * [25] B. Hashemi, M. Dehghan, The interval Lyapunov matrix equation: analytical results and an efficient numerical technique for outer estimation of the united solution set, Math. Comput. Model., 55 (2012) 622-633.
  * [26] M. Dehghani-Madiseh, M. Hladík, Efficient approaches for enclosing the united solution set of the interval generalized Sylvester matrix equations, Appl. Numer. Math., 126 (2018) 18-33.
  * [27] M. Dehghani-Madiseh, M. Dehghan, Generalized solution sets of the interval generalized Sylvester matrix equation $\sum^{p}_{i=1}A_{i}X_{i}+\sum^{q}_{j=1}Y_{j}B_{j}=C$ and some approaches for inner and outer estimations, Comput. Math. Appl., 68 (2014) 1758-1774.
  * [28] V.N. Shashikhin, Robust assignment of poles in large-scale interval systems, Autom. Rem. Contr., 63 (2002) 200-208.
  * [29] F.-Z. Zhang, Matrix Theory: Basic results and techniques (Second edition). Springer, New York, 2011.
  * [30] R.A. Horn, C.R. Johnson, Matrix Analysis. Cambridge University Press, Cambridge, 1986.