# An explicit vector algorithm for high-girth MaxCut

Jessica K. Thompson<EMAIL_ADDRESS>Sandia National Laboratories, Albuquerque,
NM, USA  Joint Center for Quantum Information and Computer Science, University
of Maryland, College Park, MD  Ojas Parekh<EMAIL_ADDRESS>Sandia National
Laboratories, Albuquerque, NM, USA  ID Kunal Marwaha<EMAIL_ADDRESS>Berkeley Center for Quantum Information and Computation, University of
California, Berkeley, CA

###### Abstract

We give an approximation algorithm for MaxCut and provide guarantees on the
average fraction of edges cut on $d$-regular graphs of girth $\geq 2k$. For
every $d\geq 3$ and $k\geq 4$, our approximation guarantees are better than
those of all other classical and quantum algorithms known to the authors. Our
algorithm constructs an explicit vector solution to the standard semidefinite
relaxation of MaxCut and applies hyperplane rounding. It may be viewed as a
simplification of the previously best known technique, which approximates
Gaussian wave processes on the infinite $d$-regular tree.

##  1 Introduction

Finding the maximum cut in a graph is a canonical NP-hard discrete
optimization problem, and one of the simplest constraint satisfaction
problems. However, to date, MaxCut does not have optimal, efficient
approximation algorithms on most families of graphs. Approximation algorithms
are typically measured by one of two metrics: the _performance_ (or cut
fraction), which is proportional to the cut size; or the _approximation ratio_
, which is the ratio of cut size and optimal cut size (or cut fraction and
optimal cut fraction).

Arguably the most famous strategy to approximate MaxCut is to solve its
semidefinite programming (SDP) relaxation and round the solution to get a cut
(Goemans and Williamson, 1995). Under the Unique Games Conjecture (UGC), this
algorithm has the optimal _worst-case_ approximation ratio $\alpha>0.878$
(Khot, 2002; Khot et al., 2007; O’Donnell and Wu, 2008). In other words, the
cut given is of size at least $\alpha$ times the optimal cut size on _every
graph_. However, many graphs, such as large random graphs, have an optimal cut
fraction less than $1/(2\alpha)$ (Dembo et al., 2017). In such cases, as an
$\alpha$-approximation, Goemans-Williamson only guarantees a cut fraction less
than $1/2$. In contrast, randomly assigning vertices to one of two partitions
has an expected cut fraction of $1/2$. This is why considering the _cut
fraction_ of an algorithm is relevant: for example, one can show that Goemans-
Williamson has cut fraction $1/2$, just as random assignment.

Even if UGC is true, we do not have approximation algorithms on _regular_
graphs that have an optimal worst-case approximation ratio (Halperin et al.,
2004). Regular graphs also admit straightforward bounds on cut fraction. Many
approximation algorithms (including ours) bound the maximum cut size as a
function of basic graph parameters, including the graph degree and number of
edges (Erdös, 1967; Shearer, 1992). One example is a local threshold algorithm
by Hirvonen et al. (2017), which first randomly assigns vertices to one of two
partitions; then, switches the label of each vertex if the number of cut edges
adjacent to it does not meet a threshold. Although the algorithm is simple,
analyzing it is not straightforward; the optimal threshold is not known _a
priori_ , so it must be numerically tuned for each degree value $d$ to
maximize performance.

Quantum algorithms, especially the Quantum Approximate Optimization Algorithm
(QAOA), may be competitive with classical algorithms on many optimization
problems (Farhi et al., 2014, 2015). The QAOA includes a parameter $p$
corresponding to its _depth_ ; its performance under optimal parameter
settings, as well as its complexity, monotonically increases with $p$.
Although hardware limitations of quantum computers prevent the use of the QAOA
at high depth (Harrigan et al., 2021), the QAOA may be competitive even at
lower depths. For example, when the QAOA was proposed, the depth-1 version had
the best known cut fraction guarantee on triangle-free regular graphs (Wang et
al., 2018; Ryan-Anderson, 2018). However, Hastings (2019) numerically showed
that the local threshold algorithm (Hirvonen et al., 2017) outperforms the
depth-1 QAOA. At higher $p$ and progressively higher girth, both algorithms
perform better; however, a practitioner has to tune $O(p)$ parameters to
perform optimally, and few provable performance bounds are known (Farhi et
al., 2014; Marwaha, 2021).

Another style of approximation algorithm uses invariant Gaussian processes
(Csóka et al., 2015; Csóka, 2016; Lyons, 2017; de Boor, 2019; Barak and
Marwaha, 2021). These algorithms are not local, but they generally perform
better than the threshold and quantum algorithms described previously. First,
one constructs an invariant Gaussian process satisfying an eigenvector
equation on an infinite $d$-regular tree (more precisely, a Bethe lattice).
This _Gaussian wave_ process can then be approximated by a factor of an i.i.d.
process assuming an eigenvalue condition is met. One can use this to derive an
independent set (Csóka et al., 2015) or a cut (Csóka, 2016; Lyons, 2017). As
$d$ and the girth go to infinity, these algorithms approach a cut fraction of
$1/2+2/(\pi\sqrt{d})$. However, the analysis is quite technical; it involves
approximating eigenvectors of the adjacency matrix of the infinite $d$-regular
tree. In contrast, our approach only requires the eigenvectors of the
adjacency matrix of a finite path, which are well understood and explicitly
known in certain cases. In addition, the algorithms of Csóka et al. (2015) and
Lyons (2017) were designed to prove existential results, and there is no claim
of computational efficiency. The algorithm in Barak and Marwaha (2021) has a
simpler form, but its analysis is complicated at finite degree; it is only
exactly bounded in the large-degree limit. The algorithm of de Boor (2019) is
the closest in spirit to ours; however, ours offers better performance.

#### Our contributions.

We design an algorithm that retains desirable features of the above approaches
but is simple to implement and analyze. As with Lyons (2017), our algorithm’s
performance bound is a function of the degree $d$ and girth $\geq 2k$, and we
do not require either to be large. In addition to a simplified approach, for
$d\geq 3$ and $k\geq 4$, our approximation guarantees are better than those of
all algorithms we are aware of.

We employ hyperplane rounding on a feasible SDP solution; however, instead of
solving the SDP, we construct an explicit vector solution. The vectors
collectively depend on $k$ parameters, and we optimize the SDP objective
subject to these parameters. This optimization problem is considerably simpler
than solving the SDP and amounts to finding a minimum eigenvector of the
adjacency matrix of a weighted path on $k$ vertices. Moreover, we give a
closed-form approximate solution which also outperforms all previous
algorithms.

Our approach is inspired by the work of Carlson et al. (2020), who construct
and round explicit vector solutions to find large cuts in graphs with few
triangles and in $K_{r}$-free graphs. Furthermore, it turns out that our
algorithm may be viewed as an simplification of the Gaussian wave process, as
discussed in Section 3. Its performance, as a function of $d$ when $k$ goes to
infinity, matches that of other algorithms based on invariant Gaussian
processes.

We motivate our discussion with a comparison to the Goemans-Williamson
algorithm and then explicitly define our algorithm and establish a lower bound
on its performance. We then connect our algorithm to the Gaussian wave
process, and prove that our bound is higher than several other performance
guarantees.

###  1.1 A motivating example

Given a graph $G=(V,E)$, where $n=|V|$ and $m=|E|$, one can describe the
unweighted111Our results readily generalize to the nonnegatively weighted
case, replacing $m$ with the sum of all edge weights. MaxCut problem by the
following binary quadratic program:

$\displaystyle\text{max}\ \frac{1}{2}\ \sum_{(i,j)\in E}(1-z_{i}\cdot z_{j})\
\text{such that }z_{i}\in\\{-1,1\\},\ \forall i\in V$

This can be relaxed to the following semidefinite program (SDP), where $S^{n}$
is the unit sphere in $n$-dimensional space:

$\displaystyle\text{max}\ \frac{1}{2}\sum_{(i,j)\in
E}(1-\mathbf{v}_{i}\cdot\mathbf{v}_{j})\ \text{such that }\mathbf{v}_{i}\in
S^{n},\ \forall i\in V$

Goemans and Williamson (1995) show that given any feasible solution to the SDP
(i.e., any set of unit vectors, $\\{\mathbf{v}_{i}\\}_{i=1}^{n}$ where
$\mathbf{v}_{i}\in S^{n}$) and a random standard Gaussian vector
$\mathbf{r}\in S^{n}$, the cut given by $A=\\{i\
|\mathbf{v}_{i}\cdot\mathbf{r}>0\\}$ and $\bar{A}=V/A$ has a lower bound on
its expected cut size (denoted by $E[W]$):

$\displaystyle E[W]$ $\displaystyle=\frac{1}{\pi}\sum_{(i,j)\in
E}\arccos(\mathbf{v}_{i}\cdot\mathbf{v}_{j})\geq\alpha\cdot\frac{1}{2}\sum_{(i,j)\in
E}(1-\mathbf{v}_{i}\cdot\mathbf{v}_{j})$

This scheme is known as _hyperplane rounding_ : the partition of vertex $i$ is
set by the sign of $\mathbf{r}\cdot\mathbf{v}_{i}$.

Since the optimal solution to the relaxed program has a value at least the
optimal cut size, this algorithm guarantees a cut with approximation ratio
$\alpha$. The cut fraction is not as easy to bound because it depends on the
values of the inner products $\mathbf{v}_{i}\cdot\mathbf{v}_{j}$.

It turns out that the SDP relaxation can be used to give provably large cuts
when the graph is locally tree-like. We use the Goemans-Willamson rounding
scheme; however, instead of actually solving the SDP, we explicitly construct
a vector solution where $\mathbf{v}_{i}\cdot\mathbf{v}_{j}$ is same for all
edges and then round to obtain a cut. Consider the following example from
Carlson et al. (2020), which is the inspiration for this paper. On a
$d$-regular, triangle-free graph, define for every $i,j\in V$:

$v_{ij}=\begin{cases}\frac{1}{\sqrt{2}}&i=j\\\ \frac{-1}{\sqrt{2d}}&(i,j)\in
E\\\ 0&\text{otherwise}\end{cases}$

Let $\mathbf{v}_{i}=[v_{i1},...,v_{in}]^{T}$. Since $\mathbf{v}_{i}\in S^{n}$,
the set $\\{\mathbf{v}_{i}\\}_{i=1}^{n}$ is a feasible solution to the above
semidefinite program. Note that $\mathbf{v}_{i}\cdot\mathbf{v}_{j}$ is the
same for all edges $(i,j)\in E$. Applying the Goemans-Williamson hyperplane
rounding scheme gives a cut with expected size

$\displaystyle E[W]$ $\displaystyle=\frac{1}{\pi}\sum_{(i,j)\in
E}\arccos(\mathbf{v}_{i}\cdot\mathbf{v}_{j})=\frac{m}{\pi}\arccos(\frac{-1}{\sqrt{d}}).$

This algorithm outperforms depth-1 QAOA at every value of $d$ (Wang et al.,
2018). Although it is not as good as the threshold algorithm from Hirvonen et
al. (2017), we can generalize the vector assignment shown above for graphs
with progressively higher girth. On each of these graphs, the explicit vector
solution has a performance guarantee above that of Lyons (2017), the depth-1
and depth-2 QAOA, and the threshold algorithm and its depth-2 extension in
Marwaha (2021).

##  2 Vector assignments to the semidefinite program

Consider a $d$-regular graph, $G=(V,E)$, where $n=|V|$ and $m=|E|$, with graph
girth at least $2k$. For each vertex, we define a vector $\mathbf{v}_{i}$ for
all $i\in V$, where $\mathbf{v}_{i}=[v_{i1},...,v_{in}]^{T}$, and

$v_{ij}=\begin{cases}\alpha_{0}&i=j\\\ \alpha_{\ell}&dist(i,j)=\ell<k\\\
0&\text{otherwise}.\end{cases}$

Here, $dist(i,j)$ is the length of the shortest path between $i$ and $j$. The
algorithm is then to round the vectors $\mathbf{v}_{i}$ using the Goemans-
Williamson rounding scheme. We choose $\alpha_{\ell}$ to optimize the cut
fraction. Notice that $\mathbf{v}_{i}\cdot\mathbf{v}_{j}$ is the same for all
$(i,j)\in E$. Minimizing this value, where the vectors are restricted to being
unit length, becomes the following optimization problem:

$\displaystyle\min
2\alpha_{0}\alpha_{1}+2(d-1)\alpha_{1}\alpha_{2}+\cdots+2(d-1)^{k-2}\alpha_{k-2}\alpha_{k-1}$
$\displaystyle\text{such that
}\alpha_{0}^{2}+d\alpha_{1}^{2}+d(d-1)\alpha_{2}^{2}+\cdots+d(d-1)^{k-2}\alpha_{k-1}^{2}=1$

By scaling the $\alpha_{\ell}$’s, the problem becomes a minimization of a
quadratic function over $S^{k}$:

$\displaystyle\min_{\|\boldsymbol{\beta}\|_{2}=1}\frac{2}{\sqrt{d}}\beta_{0}\beta_{1}+\frac{2\sqrt{d-1}}{d}\beta_{1}\beta_{2}+\cdots+\frac{2\sqrt{d-1}}{d}\beta_{k-2}\beta_{k-1}=\min_{\|\boldsymbol{\beta}\|_{2}=1}\boldsymbol{\beta}^{T}A_{k}\boldsymbol{\beta}$
$\displaystyle\boldsymbol{\beta}=[\beta_{0},...,\beta_{k-1}]^{T}$
$\displaystyle\beta_{\ell}=\begin{cases}\alpha_{0}&\ell=0\\\
\alpha_{\ell}\sqrt{d(d-1)^{\ell-1}}&\ell>0\end{cases}$

The minimum $\mathbf{v}_{i}\cdot\mathbf{v}_{j}$ is then the minimum eigenvalue
of the following $k\times k$ matrix:

$A_{k}=\begin{bmatrix}0&a&0&0&0&\cdots\\\ a&0&b&0&0&\cdots\\\
0&b&0&b&0&\cdots\\\ &&\ddots&\ddots&\ddots&\\\ 0&0&\cdots&b&0&b\\\
0&0&\cdots&0&b&0\end{bmatrix}\quad a=\frac{1}{\sqrt{d}}\quad
b=\frac{\sqrt{d-1}}{d}$

The optimal $\beta_{\ell}$ are the entries of the corresponding eigenvector.
The $\alpha_{\ell}$ are then set from the $\beta_{\ell}$.

We now state our main result:

######  Theorem 1.

Given a finite $d$-regular graph $G=(V,E)$ where $m=|E|$ with girth at least
$2k$, there is an edge cut of $G$ with size

$E[W]\geq\frac{m}{\pi}\arccos(\sigma_{d,k}),$

such that

$\sigma_{d,k}\leq\frac{-2\sqrt{d-1}}{d}\Big{(}\cos\frac{\pi}{k+1}+\big{(}\sqrt{\frac{d}{d-1}}-1\big{)}\frac{2}{k+1}\sin\frac{\pi}{k+1}\sin\frac{2\pi}{k+1}\Big{)}<\frac{-2\sqrt{d-1}}{d}\cos\frac{\pi}{k+1}\text{.}$

###### Proof.

Choose parameters where $\boldsymbol{\beta}=\mathbf{w}$, such that

$\displaystyle
w_{\ell}=\sqrt{\frac{2}{k+1}}\sin\frac{(\ell+1)k\pi}{k+1}\quad\mathbf{w}^{T}=[w_{0},...,w_{k-1}].$

Let’s calculate the inner product $\mathbf{w}^{T}A_{k}\mathbf{w}$ in this
case. Consider the following $k\times k$ matrix:

$B_{k}=\begin{bmatrix}0&b&0&0&0&\cdots\\\ b&0&b&0&0&\cdots\\\
0&b&0&b&0&\cdots\\\ &&\ddots&\ddots&\ddots&\\\ 0&0&\cdots&b&0&b\\\
0&0&\cdots&0&b&0\end{bmatrix}$

Since $B_{k}$ is a hollow tridiagonal Toeplitz matrix, its eigenvectors and
eigenvalues are fully known (Noschese et al., 2013). Here, $\mathbf{w}$ is the
eigenvector associated with the minimum eigenvalue of $B_{k}$:

$\displaystyle\mathbf{w}^{T}B_{k}\mathbf{w}=\lambda_{\min}(B_{k})=2b\cos\frac{k\pi}{k+1}$

Because of this, the following inequality holds:

$\displaystyle\lambda_{\min}(A_{k})\leq\mathbf{w}^{T}A_{k}\mathbf{w}=2(a-b)w_{0}w_{1}+\mathbf{w}^{T}B_{k}\mathbf{w}=2(a-b)w_{0}w_{1}+2b\cos\frac{k\pi}{k+1}$

Since $\arccos$ is decreasing, the cut fraction is lower bounded:

$\displaystyle E[W]=\frac{1}{\pi}\sum_{(i,j)\in
E}\arccos(\mathbf{v}_{i}\cdot\mathbf{v}_{j})$
$\displaystyle=\frac{m}{\pi}\arccos(\lambda_{\min}(A_{k}))\geq\frac{m}{\pi}\arccos(\mathbf{w}^{T}A_{k}\mathbf{w})$

Algebraic manipulation of the expression for $\mathbf{w}^{T}A_{k}\mathbf{w}$
finishes the proof.222Note that because $w_{0}w_{1}\leq 0$ and $a\geq b$,
$\mathbf{w}^{T}A_{k}\mathbf{w}\leq\mathbf{w}^{T}B_{k}\mathbf{w}=\lambda_{min}(B_{k})$.
∎

Assigning $\boldsymbol{\beta}$ as the minimum eigenvector of $B_{k}$ does not
require any additional calculation, because a closed-form expression for the
eigenvector is known for all $k$. However, this algorithm has highest
performance when assigning $\beta_{\ell}$ from the minimum eigenvector of
$A_{k}$. At large $d$ or $k$, the difference between $A_{k}$ and $B_{k}$ tends
to zero.

When $d\geq 3$ and $k\geq 4$, this is the best known cut fraction for
$d$-regular graphs of girth $\geq 2k$. See Section 4 for a comparison of this
bound with other algorithms’ performance guarantees.

##  3 Relationship to the Gaussian wave process

Consider a vector assignment given by our algorithm,
$\\{\mathbf{v}_{i}\\}_{i=1}^{n}$, and let
$V=[\mathbf{v}_{1}...\mathbf{v}_{n}]$. Hyperplane rounding can now be thought
of as sampling from a $n$-variable Gaussian distribution
$\mathbf{x}\sim\mathcal{N}(0^{n},\Sigma)$ (where $\Sigma=V^{T}V$), and taking
the sign of each variable. Any multivariate Gaussian distribution can be
expressed as linear combinations of i.i.d. Gaussians. In other words and when
applied to our setting, $\mathbf{x}=V\mathbf{z}$, where $\mathbf{z}$ encodes
$n$ i.i.d Gaussian random variables. This yields

$\mathbf{x}_{i}=\sum_{j\in
V}\alpha_{d(i,j)}\mathbf{z}_{j}=\sum_{\ell=0}^{k-1}\sum_{j:d(i,j)=\ell}\alpha_{\ell}\mathbf{z}_{j}.$

Thus, our algorithm may be viewed as a linear factor of an i.i.d process,
presented in Csóka et al. (2015) to approximate the Gaussian wave and used in
Lyons (2017):

$\mathbf{x}_{i}=\sum_{j\in
V}\alpha_{d(i,j)}\mathbf{z}_{j}=\sum_{\ell=0}^{\infty}\sum_{j:d(i,j)=\ell}\alpha_{\ell}\mathbf{z}_{j}$

The first equation may be recovered by setting $\alpha_{\ell}=0$ for all
$\ell\geq k$.

Csóka et al. (2015) construct a linear factor of an i.i.d. process on the
infinite $d$-regular tree to approximate the Gaussian wave process. They
observe that in this setting, one may assume that only a finite number of the
$\alpha_{\ell}$ are nonzero; however, their results are on graphs of
sufficiently high girth, and they do not explicitly consider girth as a
parameter.

The approach of Chapter 4.1 in de Boor (2019) is similar to ours. The main
difference is that de Boor uses one free parameter $c$ to determine
$\\{\alpha_{\ell}\\}_{l=0}^{k-1}$ rather than obtaining the optimal values as
we do. In fact, de Boor’s optimal choice of $c$ exactly reproduces the block
FIID in Theorem 4.2 of Lyons (2017), with the same bound on cut fraction.333de
Boor makes a mathematical mistake; on page 20, his $\zeta^{2}$ should equal
$1+c^{2}dL$. Our approach is guaranteed to perform as well any other approach
based on a linear factor of an i.i.d. process using only
$\\{\alpha_{\ell}\\}_{\ell=0}^{k-1}$.

##  4 Comparison of performance guarantees

The expected cut size given by our algorithm is larger than the guarantee
given by Theorem 4.2 of Lyons (2017). We state this formally:

######  Theorem 2.

Given a finite $d$-regular graph $G=(V,E)$ with girth at least $2k$, the
explicit vector solution has a higher performance guarantee than that of the
algorithm in Lyons (2017) for every $k\geq 3$ and $d\geq 3$.

###### Proof.

First consider this form of the expected cut fraction:

$E[W]=\frac{m}{\pi}\arccos(-2b\cdot\xi)$

We compare $\xi$ for the explicit vector solution and the algorithm in Lyons
(2017). Call $\xi$ the _relative expectation_. The explicit vector solution
has relative expectation

$\displaystyle\xi_{EV}$
$\displaystyle\geq\frac{\lambda_{\min}(B_{k})}{-2b}=\cos\frac{\pi}{k+1}\geq
1-0.5(\frac{\pi}{k+1})^{2}.$

The algorithm in Lyons (2017) has relative expectation

$\displaystyle\xi_{L}=(1+\frac{d-1}{d(k-1)})^{-1}=\frac{k-1}{k-1/d}.$

The condition $\xi_{EV}>\xi_{L}$ holds when

$\displaystyle 1-0.5(\frac{\pi}{k+1})^{2}$ $\displaystyle>\frac{k-1}{k-1/d}$
$\displaystyle\Leftrightarrow$ $\displaystyle k-1/d$
$\displaystyle>\frac{k-1}{1-0.5(\frac{\pi}{k+1})^{2}}$
$\displaystyle\Leftrightarrow$ $\displaystyle d$
$\displaystyle>\Big{(}k-(\frac{k-1}{1-0.5(\frac{\pi}{k+1})^{2}})\Big{)}^{-1}.$

The righthand expression decreases with $k$, so if the condition holds at
$k_{*}$, it holds at all $k\geq k_{*}$.

Consider $k\in\\{3,4,5\\}$. The condition holds when

$\displaystyle d$ $\displaystyle>9.26$ $\displaystyle(k=3)$ $\displaystyle d$
$\displaystyle>3.82$ $\displaystyle(k=4)$ $\displaystyle d$
$\displaystyle>2.75$ $\displaystyle(k=5).$

All that remains to show is that the relative expectation is higher for
($k=3$, $3\leq d\leq 9$) and ($k=4$, $d=3$). A numerical calculation verifies
this; see Table 1. This completes the proof. ∎

The explicit vector solution also outperforms the QAOA and threshold
algorithm, at depth-1 and depth-2, for all $k\geq 3$ and $d\geq 3$. Our
solution has performance increasing with $k$, and the other algorithms have
performance increasing with depth, so we compare the $k=3$ solution to the
depth-2 algorithms. Consider the cut fraction $1/2+c_{d}/\sqrt{d}$, where
$c_{d}$ is the _normalized value_. At large $d$, our algorithm has normalized
value $c_{\infty}=\sqrt{2}/\pi>0.45$, higher than that of the QAOA
($c_{\infty}\approx 0.41$) and the threshold algorithm ($c_{\infty}\approx
0.42)$. The normalized value decreases with $d$ for $d\geq 3$; for example,
$c_{8}\approx 0.454$. Compare this with Figure 2 and Table 1 of Marwaha
(2021); the explicit vector solution outperforms the QAOA and threshold
algorithm at all $d\geq 3$.

The modified threshold algorithm of $d\in\\{3,4,5\\}$ was found with a
computer search over a large class of algorithms (Marwaha, 2021). This
outperforms our solution at $k=3$ but not at $k=4$.

k | d | Explicit vector | Lyons bound
---|---|---|---
3 | 3 | 0.78656 | 0.75000
4 | 0.76180 | 0.72727
5 | 0.74883 | 0.71428
6 | 0.74085 | 0.70588
7 | 0.73543 | 0.70000
8 | 0.73151 | 0.69565
9 | 0.72855 | 0.69230
4 | 3 | 0.85927 | 0.81818
Table 1: Comparison of relative expectation of our solution and the lower
bound of a previous Gaussian wave algorithm. The calculation uses the bound
$\mathbf{w}^{T}A_{k}\mathbf{w}$ given in the proof of Theorem 1, where
$\mathbf{w}$ is the minimum eigenvector of $B_{k}$. All values are truncated.

##  5 Conclusions

We provide a procedure to find a large cut on a high-girth graph. For a given
girth $g\geq 8$, this algorithm provides a cut fraction guarantee higher than
that of all other classical and quantum algorithms to date. It gives a simple,
explicit solution to the semidefinite program. Moreover, the process of using
hyperplane rounding on this solution can be thought of as a simplification of
the Gaussian wave process previously used.

Although our analysis requires $k$ upper bounded by the girth, in practice one
can use $k$ equal to the diameter of the graph. Numerically, this change
improves the cut fraction, but a new analysis is needed to prove it.

One can also use the explicit vector technique in other optimization problems.
For example, it can be directly applied to the independent set algorithm in
Csóka et al. (2015). Though this does not improve the performance, further
work (for example a tighter bound) could lead to an improvement.

There is recent interest in the development of local improvement algorithms
which start with an existing approximation (as opposed to random
initialization). For example, Egger et al. (2021) implement “warm-start” QAOA,
initializing the quantum computer with a solution produced by the Goemans-
Williamson algorithm. This technique could also be applied here. Using the
output of our algorithm, one could apply a local threshold procedure to
improve the cut. Although previous results are numerical, analytic bounds may
be possible here because of our solution’s simple form.

No current algorithm provably achieves the optimal cut fraction on locally
tree-like graphs (Dembo et al., 2017). It is suspected that one may exist
using approximate message-passing (Alaoui et al., 2020; Montanari, 2021); but
for now, this is an open question. This means that better algorithms than the
one we propose may exist, including better quantum algorithms.

## Acknowledgements

KM thanks Boaz Barak for personal guidance. OP and JT are affiliated with
Sandia National Laboratories, which is a multimission laboratory managed and
operated by National Technology and Engineering Solutions of Sandia, LLC., a
wholly owned subsidiary of Honeywell International, Inc., for the U.S.
Department of Energy’s National Nuclear Security Administration under contract
DE-NA-0003525. OP and JT were supported by the U.S. Department of Energy,
Office of Science, Office of Advanced Scientific Computing Research,
Accelerated Research in Quantum Computing and Quantum Algorithms Teams
programs.

## References

  * Alaoui et al. (2020) A. E. Alaoui, A. Montanari, and M. Sellke.  Optimization of mean-field spin glasses, 2020.  2001.00904.
  * Barak and Marwaha (2021) B. Barak and K. Marwaha.  Classical algorithms and quantum limitations for maximum cut on high-girth graphs, 2021.  2106.05900.
  * Carlson et al. (2020) C. Carlson, A. Kolla, R. Li, N. Mani, B. Sudakov, and L. Trevisan.  Lower bounds for max-cut via semidefinite programming.  In Y. Kohayakawa and F. K. Miyazawa, editors, _LATIN 2020: Theoretical Informatics_ , pages 479–490, Cham, 2020. Springer International Publishing.  ISBN 978-3-030-61792-9.  1810.10044.
  * Csóka et al. (2015) E. Csóka, B. Gerencsér, V. Harangi, and B. Virág.  Invariant gaussian processes and independent sets on regular graphs of large girth.  _Random Structures & Algorithms_, 47(2):284–303, 2015.  1305.3977.
  * Csóka (2016) E. Csóka.  Independent sets and cuts in large-girth regular graphs, 2016.  1602.02747.
  * de Boor (2019) C. de Boor.  In search of degree-4 sum-of-squares lower bounds for maxcut.  Technical Report CMU-CS-19-118, Carnegie Mellon University, 2019.  URL http://reports-archive.adm.cs.cmu.edu/anon/2019/CMU-CS-19-118.pdf.
  * Dembo et al. (2017) A. Dembo, A. Montanari, and S. Sen.  Extremal cuts of sparse random graphs.  _The Annals of Probability_ , 45(2):1190–1217, 2017.  1503.03923.
  * Egger et al. (2021) D. J. Egger, J. Mareček, and S. Woerner.  Warm-starting quantum optimization.  _Quantum_ , 5:479, Jun 2021.  ISSN 2521-327X.  doi: 10.22331/q-2021-06-17-479.  2009.10095.
  * Erdös (1967) P. Erdös.  On even subgraphs of graphs.  _Mat. Lapok_ , 18(3, 4):283–288, 1967.  URL http://real-j.mtak.hu/id/eprint/9365.
  * Farhi et al. (2014) E. Farhi, J. Goldstone, and S. Gutmann.  A quantum approximate optimization algorithm.  _arXiv preprint_ , 2014.  1411.4028.
  * Farhi et al. (2015) E. Farhi, J. Goldstone, and S. Gutmann.  A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem, 2015.  1412.6062.
  * Goemans and Williamson (1995) M. X. Goemans and D. P. Williamson.  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  _Journal of the ACM (JACM)_ , 42(6):1115–1145, 1995.  URL http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf.
  * Halperin et al. (2004) E. Halperin, D. Livnat, and U. Zwick.  Max cut in cubic graphs.  _Journal of Algorithms_ , 53(2):169–185, 2004\.  ISSN 0196-6774.  doi: https://doi.org/10.1016/j.jalgor.2004.06.001.  URL https://www.sciencedirect.com/science/article/pii/S0196677404000902.
  * Harrigan et al. (2021) M. P. Harrigan, K. J. Sung, M. Neeley, et al.  Quantum approximate optimization of non-planar graph problems on a planar superconducting processor.  _Nature Physics_ , 17(3):332–336, Mar 2021.  ISSN 1745-2481.  doi: 10.1038/s41567-020-01105-y.  2004.04197.
  * Hastings (2019) M. B. Hastings.  Classical and quantum bounded depth approximation algorithms, 2019.  1905.07047.
  * Hirvonen et al. (2017) J. Hirvonen, J. Rybicki, S. Schmid, and J. Suomela.  Large cuts with local algorithms on triangle-free graphs.  _The Electronic Journal of Combinatorics_ , pages P4–21, 2017.  1402.2543.  Preliminary version on arXiv, 2014.
  * Khot (2002) S. Khot.  On the power of unique 2-prover 1-round games.  In _Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing_ , STOC ’02, page 767–775, New York, NY, USA, 2002. Association for Computing Machinery.  ISBN 1581134959.  doi: 10.1145/509907.510017.  URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.5651&rep=rep1&type=pdf.
  * Khot et al. (2007) S. Khot, G. Kindler, E. Mossel, and R. O’Donnell.  Optimal inapproximability results for MAX-CUT and other 2-variable csps?  _SIAM J. Comput._ , 37(1):319–357, 2007.  doi: 10.1137/S0097539705447372.  URL https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf.  Preliminary version in FOCS 2004.
  * Lyons (2017) R. Lyons.  Factors of iid on trees.  _Combinatorics, Probability and Computing_ , 26(2):285–300, 2017.  1401.4197.
  * Marwaha (2021) K. Marwaha.  Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs.  _Quantum_ , 5:437, Apr. 2021.  ISSN 2521-327X.  doi: 10.22331/q-2021-04-20-437.  2101.05513.
  * Montanari (2021) A. Montanari.  Optimization of the sherrington–kirkpatrick hamiltonian.  _SIAM Journal on Computing_ , 0(0):FOCS19–1, 2021\.  1812.10897.  Preliminary version in FOCS ’19.
  * Noschese et al. (2013) S. Noschese, L. Pasquini, and L. Reichel.  Tridiagonal toeplitz matrices: properties and novel applications.  _Numerical linear algebra with applications_ , 20(2):302–326, 2013.  URL http://www.math.kent.edu/~reichel/publications/toep3.pdf.
  * O’Donnell and Wu (2008) R. O’Donnell and Y. Wu.  An optimal sdp algorithm for max-cut, and equally optimal long code tests.  In _Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing_ , STOC ’08, page 335–344, New York, NY, USA, 2008. Association for Computing Machinery.  ISBN 9781605580470.  doi: 10.1145/1374376.1374425.  URL https://doi.org/10.1145/1374376.1374425.
  * Ryan-Anderson (2018) C. Ryan-Anderson.  Quantum algorithms, architecture, and error correction, 2018.  1812.04735.
  * Shearer (1992) J. B. Shearer.  A note on bipartite subgraphs of triangle-free graphs.  _Random Structures & Algorithms_, 3(2):223–226, 1992.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240030211.
  * Wang et al. (2018) Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel.  Quantum approximate optimization algorithm for maxcut: A fermionic view.  _Phys. Rev. A_ , 97:022304, Feb 2018.  doi: 10.1103/PhysRevA.97.022304.  1706.02998.


# Early Dark Energy beyond slow-roll: implications for cosmic tensions

Ravi kumar Sharma  Indian Institute of Astrophysics, Bengaluru, Karnataka
560034, India  Subinoy Das  Indian Institute of Astrophysics, Bengaluru,
Karnataka 560034, India  Vivian Poulin  Laboratoire Univers and Particules de
Montpellier(LUPM), CNRS, Université de Montpellier (UMR-5299)

###### Abstract

In this work, we explore the possibility that Early Dark Energy (EDE) is
dynamical in nature and study its effect on cosmological observables. We
introduce a parameterization of the equation of state allowing for an equation
of state $w$ differing considerably from cosmological constant (cc, $w={-1}$)
and vary both the initial $w_{i}$ as well final $w_{f}$ equation of state of
the EDE fluid. This idea is motivated by the fact that in many models of EDE,
the scalar field may have some kinetic energy when it starts to behave like
EDE before the CMB decoupling. We find that the present data have a mild
preference for non-cc early dark energy $(w_{i}=-0.78)$ using
Planck+BAO+Pantheon+S$H_{0}$ES data sets, leading to $\Delta\chi^{2}_{\rm
min}$ improvement of -2.5 at the expense of one more parameter. However,
$w_{i}$ is only weakly constrained, with $w_{i}<-0.56$ at $1\sigma$. We argue
that allowing for $w_{i}\neq-1$ can play a role in decreasing the $\sigma_{8}$
parameter. Yet, in practice the decrease is only $\sim 0.4\sigma$ and
$\sigma_{8}$ is still larger than weak lensing measurements. We conclude that
while promising, a dynamical EDE cannot resolve both $H_{0}$ and $\sigma_{8}$
tensions simultaneously.

##  I Introduction

The cosmological model with a cosmological constant and cold dark matter
dubbed ‘$\Lambda$CDM’ has been the most successful candidate to describe our
universe. It is consistent with almost all cosmological observations, but
recently a few discrepancies between the model predictions and direct
measurements of a few observables have arisen. Measurement of the expansion
rate of the Universe is one of the most discussed mismatches over the last
decade. The latest measurements of the Cosmic Microwave Background (CMB) by
the Planck satellite when analyzed under the $\Lambda$CDM model predict a
value of the Hubble parameter $H_{0}=67.36\pm 0.54\rm{km/s/Mpc}$ [6]. Beyond
Planck, data that are calibrated using pre-recombination information, like
Baryon Acoustic Oscillations(BAO)[2] and Big Bang nucleosynthesis(BBN)[14] is
consistent with the lower value of Hubble parameter inferred from CMB. On the
other hand, the Supernovae H0 for the equation of state (S$H_{0}$ES) team has
measured the value of the Hubble parameter $H_{0}=73.04\pm 1.04\rm{km/s/Mpc}$
by building a distance ladder to supernovae of type 1a (SN1a) [41, 40, 42].
Other local/direct measurements are consistent with a higher value of the
Hubble parameter, although not at the same tension level as S$H_{0}$ES (see
Ref. [5] for a review). With the increasing precision of experiments, and more
and more data available, this tension has gained more significance and drawn
more attention from the cosmology community [45, 16, 17].

There also exists a comparatively milder tension in the measurement of local
growth parameterized by $S_{8}=\sigma_{8}\sqrt{\frac{\Omega_{M}}{0.3}}$, where
$\Omega_{M}$ is the total matter density today and $\sigma_{8}$ is root mean
square of matter fluctuations at the scale of 8 Mpc$/h$. The Planck 2018 CMB
measurements using $\Lambda$CDM model infers the value of
$S_{=}0.832\pm{0.013}$. On the other hand, observations of galaxies through
weak lensing by CFHTLenS collaboration have indicated that the $\Lambda$CDM
model predicts a $S_{8}$ value that is larger than the direct measurement at
the $2\sigma$ level [20, 35]. This tension has gained more significance with
various data sets such as the KiDS/Viking data [22, 27] and DES data [1, 3].
Recently, the combination of KiDS/Viking and SDSS data has established
$3\sigma$ tension with $S_{8}=0.766^{+0.02}_{-0.014}$ [21], although the
combination of KiDS and DES indicates a slightly lower significance of the
tension [4].

No studies have found obvious errors and systemic in data that could explain
the $H_{0}$ tension, such that the possibility of new physics has gained a lot
of attention. It is becoming evident from recent works [30, 45] that the pre-
recombination era is the most likely epoch to contain hidden new physics which
may solve the Hubble tension by reducing the CMB sound horizon. Early dark
energy, originally introduced in Refs. [29, 39, 33], invokes a scalar field
frozen until matter-radiation equality, that suddenly becomes dynamical and
dilutes faster than radiation. Although EDE can bring down the $H_{0}$ tension
significantly, it suffers from a few major challenges (see Refs. [28, 38] for
discussion). First, generic to models that resolve the Hubble tension by
changing the pre-recombination era, the EDE cosmology has a small-scale power
increase in the matter power spectra, that tends to slightly worsen the
$S_{8}$ tension [23, 49]. Second, the EDE model suffers a problem of
coincidence, whereby the EDE must become dynamical at a special time, namely
matter-radiation equality, that raises questions of fine-tuning in the model
(see e.g. Refs. [19, 37, 34] for studies in this context). At the same time,
at late time the existence of the present dark energy is still a mystery and
faces a similar challenge of fine-tuning. Dynamical dark energy is one of the
most well-studied candidates as an alternative to cosmological constant to
explain the fine-tuning problem.

There already have been a few physical models where early dark energy appears
to be naturally present at matter radiation equality [19, 13, 34]. In some
physical models, one can in fact have a dynamical evolution for early dark
energy even prior to its fast dilution. For example in Ref. [19], authors
discuss a model where a neutrino-like particle is in interaction with a scalar
field. Depending on the shape of the potential of this scalar field, the
equation of state of EDE can change, and it is shown that for a $\phi^{2}$
potential, the initial equation of state is $w_{i}=-\frac{1}{3}$.

In this paper, motivated by this idea, we explore whether a dynamical EDE
model may be preferred over a purely frozen (i.e., cosmological constant-like)
behavior. If EDE also happens to be dynamical, one might get a hint that
perhaps ‘Nature’ has the same mechanism of turning on dark energy at different
epochs of the universe - may it be inflation or EDE or present DE.
Interestingly, we indeed find that up-to-date cosmological data sets may
indeed prefer an equation of state $w_{i}\neq-1$. The plan of the paper is as
follows: In section II we present our phenomenological modeling of the EDE
component at the background and perturbations level. We discuss the impact of
the initial equation of state (before the fluid dilutes) on observable in
section III. In section IV.1, we present our main analysis setup and
methodology, while our results are discussed in section V. We finally conclude
in section VI.

##  II Background and Perturbation equations

We consider a homogeneous isotropic and flat universe described by the
Friedmann-Lemaitre-Robertson-Walker (FLRW) metric and filled with the usual
species that compose the $\Lambda$CDM model (photons, baryons, neutrinos, cold
dark matter, and dark energy). To implement EDE, we consider an extra
component in the form of a generalized fluid description, which requires us to
specify its equation of state $w$, sound speed $c_{s}^{2}$, and eventually,
its anisotropic stress which we take to be zero as valid for a scalar field
(see Ref. [44] for a discussion about the role of anisotropic stress with
EDE). The equation of state is parameterized as follows:

$w_{\rm
EDE}(a)={\frac{{w_{f}}-{w_{i}}}{\left[{1+{\left(\frac{a_{c}}{a}\right)}^{3\times(w_{f}-w_{i})}}\right]}}-w_{i}$
(1)

where $w_{i}$ and $w_{f}$ are the initial and final equations of states
parameters respectively and $a_{c}$ is the scale factor at the time of
transition, while $p$ is the parameter controlling the width of the
transition. The background energy density of the early dark energy component
evolves as follows

$\rho_{\rm EDE}(a)=\rho_{\rm EDE}(1)\times\exp\left(3\int_{1}^{a}(1+w_{\rm
EDE}(a))da\right)\,.$ (2)

To describe perturbations in the fluid, we make use of the generalized dark
matter formalism [24]. The perturbation equations (Euler and Continuity) in
the synchronous gauge are given by:

$\displaystyle\frac{d}{d\eta}\left(\frac{\delta_{\rm EDE}}{1+w_{\rm
EDE}}\right)$ $\displaystyle=$ $\displaystyle-\left(\theta_{\rm
EDE}+h^{\prime}\right)$
$\displaystyle-3\textit{H}(c_{s}^{2}-c_{a}^{2})\left(\frac{\delta_{\rm
EDE}}{1+w_{\rm EDE}}+3\textit{H}\frac{\theta_{\rm EDE}}{k^{2}}\right)\,,$

$\frac{d}{d\eta}\left(\theta_{\rm
EDE}\right)=-\textit{H}\left(1-3c_{s}^{2}\right)\theta_{\rm
EDE}+c_{s}^{2}k^{2}\frac{\delta_{\rm EDE}}{1+w_{\rm EDE}}\,.$ (3)

Here $\delta_{\rm EDE}$ is the density perturbation and $\theta_{\rm EDE}$ is
the velocity divergence of the EDE fluid. The sound speed of the EDE fluid
relates the density and pressure perturbations as $c_{s}^{2}=\frac{\delta
P}{\delta\rho}$, $k$ is the comoving wave-number, H the conformal Hubble
parameter, $c_{a}^{2}$ is the adiabatic sound speed defined as

$c_{a}^{2}=\frac{\rho^{\prime}_{\rm EDE}}{P^{\prime}_{\rm EDE}}=w_{\rm
EDE}-\frac{1}{3}\frac{dw_{\rm EDE}/d\ln a}{1+w_{\rm EDE}}\,.$ (4)

Using equation 1, we find that

$c_{a}^{2}=\begin{cases}w_{i}&a\ll a_{c}\,,\\\ w_{f}&a\gg a_{c}\,.\end{cases}$

The sound speed $c_{s}^{2}$ is set as follows

$c_{s}^{2}=\begin{cases}1&a<a_{c}\,,\\\ w_{f}&a>=a_{c}\,,\end{cases}$

but we find that the results are not strongly sensitive to the way in which we
parameterize $c_{s}^{2}$, when we impose $c_{s}^{2}=w_{f}$ in the decaying
phase.

To find the initial conditions, we assume that the system starts in the
radiation-dominated era so $\textit{H}=\frac{1}{\eta}$. If the energy density
of early dark energy at early times is negligible, the solution for the metric
perturbation $h$ will not change and is given by $h=\frac{(k\eta)^{2}}{2}$.
For super–Hubble mode $k\eta\ll 1$, equations II and 3 reduced to

$\frac{d}{d\eta}\left(\frac{\delta_{\rm EDE}}{1+w_{\rm
EDE}}\right)=\frac{k^{2}\eta}{2}-3\frac{1}{\eta}(c_{s}^{2}-c_{a}^{2})\left(\frac{\delta_{\rm
EDE}}{1+w_{\rm EDE}}+3\frac{1}{\eta}\frac{\theta_{\rm EDE}}{k^{2}}\right)$

$\frac{d}{d\eta}\left(\theta_{\rm
EDE}\right)=-\frac{1}{\eta}\left(1-3c_{s}^{2}\right)\theta_{\rm
EDE}+c_{s}^{2}k^{2}\frac{\delta_{\rm EDE}}{1+w_{\rm EDE}}\,.$

These can be solved in power of $(k\eta)^{2}$, and we get the initial
condition

$\displaystyle\frac{\delta_{\rm EDE}}{1+w_{\rm EDE}}$ $\displaystyle=$
$\displaystyle-\frac{(4-3c_{s}^{2})/2}{8+6c_{s}^{2}-12c_{a}^{2}}(k\eta)^{2},$
(5) $\displaystyle\theta_{\rm EDE}$ $\displaystyle=$
$\displaystyle-\frac{c_{s}^{2}/2}{8+6c_{s}^{2}-12c_{a}^{2}}k(k\eta)^{3}\,.$
(6)

These equations and the initial conditions have been implemented in a modified
version of the Boltzmann code CLASS [31, 10].

Figure 1: (a) Effect of varying $w_{i}$ on the equation of state. (b) Effect
of varying $w_{i}$ on the slope.  Figure 2: Effect of varying $w_{i}$ on the
evolution of EDE density fraction.

##  III Effect of changing the initial equation of state $w_{i}$

###  III.1 Impact on the background and perturbation dynamics

To investigate the effect of changing on background and perturbations
quantities, we vary $w_{i}$ for a set of values as $w_{i}=-1,-0.8,-0.6,-0.4$.
The effect of varying $w_{i}$ on $w_{\rm EDE}(a)$ and $\frac{dw_{\rm
EDE}(a)}{da}$ is illustrated on Fig. 1.

Impact of $w_{i}$ on EDE background evolution: Firstly let us investigate the
effect on the evolution of the EDE background energy density. This is shown in
figure 2. One can clearly notice that when we increase $w_{i}$, the energy
density spreads over time. The transition is smoother, the EDE component stays
longer and the EDE component starts influencing the expansion rate from
earlier redshift. That results in a smaller value of sound horizon and a large
value of the Hubble parameter today.

Figure 3: Effect of varying $w_{i}$ on the evolution of EDE perturbations for
three modes $k=0.01,0.06,0.3$Mpc-1.  Figure 4: Effect of varying $w_{i}$ on
the evolution of weyl potential. We show the difference with respect to the
$\Lambda$CDM model with identical cosmological parameters.

We now turn to describe the effect of $w_{i}$ on perturbations of early dark
energy as well as how it affects the matter component.

Impact of $w_{i}$ on EDE density perturbations:
In figure 3 we plot the effect of varying $w_{i}$ on EDE density fluctuations,
for $k=0.01,0.06,0.3$Mpc-1, i.e. modes that enter the horizon after, around
and before $a_{c}$ respectively. We also show horizon crossing for each mode
defined as $k\tau(a_{k})\equiv 2\pi$ and the value of $a_{c}$ as red and green
dotted vertical line respectively. The equation which governs EDE
perturbations can be obtained by reducing Eqs. II and 3 to a second-order
differential equation,

$\displaystyle\frac{d^{2}}{d\eta^{2}}\left(\frac{\delta_{\rm EDE}}{1+w_{\rm
EDE}}\right)$ $\displaystyle+$ $\displaystyle k^{2}c_{s}^{2}\frac{\delta_{\rm
EDE}}{1+w_{\rm EDE}}$ $\displaystyle+$
$\displaystyle(1-3c_{a}^{2})\frac{a^{\prime}}{a}\frac{d}{d\eta}\left(\frac{\delta_{\rm
EDE}}{1+w_{\rm EDE}}\right)=0\,.$

This equation is that of a damped simple harmonic oscillator. The solution
will be oscillatory either decreasing in amplitude or increasing in amplitude
depending on the damping terms sign. The frequency of oscillations depends on
’$k^{2}c_{s}^{2}$’, and The term $1-3c_{a}^{2}$ can be either negative or
positive, acting either as a driving force of a friction term (assuming
$w_{i}<-\frac{1}{3}$):

$1-3*c_{a}^{2}=\begin{cases}1-3*w_{i}>0&a\ll a_{c}\\\ 1-3*w_{f}<0&a\gg
a_{c}\,.\end{cases}$

The effect of $w_{i}$ on the growth of the EDE density fluctuations for
different $k$ modes can be understood as follows:

  * •

For modes which enter the horizon well before $a_{c}$, i.e. for $a_{k}\ll
a_{c}$: Before horizon crossing, the growth of $\delta_{\rm EDE}$ is given by
the initial condition [Eq. (5)], which shows that it grows like $(k\tau)^{2}$
and proportionally to $1+w_{\rm EDE}$. Consequently, models with larger
$w_{i}$ grow faster, as is particularly visible for the mode with
$k=0.3$Mpc-1, which crosses the horizon earlier. In the region
$a_{k}<a<a_{c}$, the equation of state is $w_{i}<0$. The solution of
$\delta_{\rm EDE}$ is oscillatory but decreasing in amplitude (see equation
III.1). At the time of $a_{c}$, high $w_{i}$ models have a higher amplitude.
Finally, in the region $a>a_{c}$, the solution remains oscillatory, but the
damping factor switches sign, acting as a driving force and leading to
oscillations whose amplitude is larger for modes that had a larger amplitude
at $a_{c}$, i.e., modes with larger $w_{i}$.

  * •

For modes which enter the horizon well after $a_{c}$, i.e. that verifies
$a_{k}\gg a_{c}$ : In that case, all modes have a similar evolution since they
are frozen (i.e. $(k\tau)^{2}\ll 1$) when the fields become dynamical. Around
horizon crossing, all modes grow proportional to $1+w_{\rm ede}$ as given by
[Eq. (5)] while after horizon crossing they oscillate with increasing
amplitude as larger modes do.

  * •

For modes which enter the horizon around $a_{c}$, i.e. $a_{k}\sim a_{c}$:
Before and around horizon crossing, the growth of $\delta_{\rm EDE}$ is still
given by the initial condition [Eq. (5)], and modes oscillate with increasing
amplitude after horizon crossing. However, $w_{\rm EDE}$ evolves in time as
the modes enter the horizon, and can even become positive around $a_{k}$. This
gives a non-trivial time-evolution to the damping term, such that modes with
larger amplitude at $a_{k}$ now have a smaller amplitude of oscillations at
$a>a_{k}$. For instance, the model with $w_{i}=-0.4$, shows a much lower
amplitude of oscillations than the model with $w_{i}=-0.99$ at this scale,
while it shows a much larger oscillation amplitude at larger $k$. We stress
that this is a specific consequence of our choice of parameterization of
$w_{\rm EDE}(a)$, rather than the effect of $w_{i}$ per se.

Impact on the Weyl potential Evolution:
To understand the impact of $w_{i}$ on the CMB power spectra, it is
instructive to plot the combination of $-(\Psi+\Phi)$ known as Weyl potential
and determined as [38]

$\Phi=-\frac{3}{4k^{2}}\left(\frac{a^{\prime}}{a}\right)^{2}\left(2\delta+\sum_{i}[1+w_{i}]\left[\frac{6(a^{\prime}/a)\theta_{i}}{k^{2}}+3\sigma_{i}\right]\right)\,.$
(8)

We show in Fig. 4 the effect of $w_{i}$ on the evolution of the Weyl potential
for different $k$ modes (identical to the previous figure), normalized to the
standard $\Lambda$CDM case. The impact on the Weyl potential can be explained
through a combination of background and perturbation effects which have been
discussed above.

Figure 5: Effect of varying $w_{i}$ on CMB TT power spectra (left panel) and
matter power spectra (right panel).

  * •

At $a\gg a_{c}$ the Weyl potential is suppressed due to the presence of EDE,
which contributes to the Hubble rate but does not cluster. For modes that are
within the horizon before $a_{c}$, the larger $w_{i}$, the longer the EDE
phase lasts, and the more the Weyl potential is suppressed. For modes entering
the horizon much later, the suppression is identical since the modes are
mostly sensitive to EDE after $a_{c}$, when all models are identical.

  * •

At $a\approx a_{c}$, there are visible residual oscillations (decaying in
amplitude) that are due to EDE perturbations. The frequency of oscillations is
larger for larger $k$ modes, as the EDE oscillations have a frequency set by
$(kc_{s})^{2}$. For modes that are within the horizon before $a_{c}$
($k=0.3$Mpc-1), the larger $w_{i}$, the larger the amplitude of $\delta_{\rm
EDE}$ and therefore the larger the contribution to the Weyl potential around
$a_{c}$. For the mode entering the horizon around $a_{c}$ ($k=0.06$Mpc-1) one
can note again the non-trivial behavior, where the model with smaller $w_{i}$
shows a larger first oscillation. This is due to the fact that $w$ has evolved
in time, affecting the damping term, as discussed previously. For the modes
that enter the horizon very late ($k=0.001$Mpc-1), the EDE perturbations are
essentially zero, and the weyl potential is suppressed around $a_{c}$ due to
the presence of a non-clustering EDE, with minute differences due to slightly-
different time evolution in $w_{\rm EDE}$.

###  III.2 Impact of $w_{i}$ on the CMB and matter power spectra

In figure 5 left panel, we plot residuals of the CMB temperature anisotropy
power spectra (TT) when varying $w_{i}$ and keeping other parameters fixed,
taking $\Lambda$CDM as reference. The main effect of EDE is described in
detail in Ref. [38]. Here we focus on describing the impact of varying
$w_{i}$. The main visible impact of $w_{i}$ on the CMB TT power spectra comes
through the following contributions

  * •

Diffusion damping: When we increase $w_{i}$, the effect of EDE on the
background expansion is increased. Because we keep $\theta_{s}$ fixed, and the
impacts of EDE on the sound horizon and on the damping scales are different,
the adjustment of the angular diameter distance $D_{A}$ by the increase in
$H_{0}$ cannot simultaneously keep the angular diffusion damping scale
$\theta_{d}=\frac{r_{d}}{D_{A}}$ unaffected. As a result, $\theta_{d}$
increases, leading to a suppression of CMB TT power spectra at high $\ell$
that is larger for larger $w_{i}$.

  * •

Sachs-wolfs contribution: As a result of the changes to the Weyl potential due
to increasing $w_{i}$ (and the longer lasting EDE phase), the Sachs wolf
contribution is significantly affected around $\ell\sim 500$. The larger
$w_{i}$, the larger the contribution in the Sachs wolf effect at intermediate
$\ell$’s, boosting the first acoustic peak amplitudes.

Next, in figure 5 right panel, we show the effect of increasing $w_{i}$ on the
total matter power spectra. When we increase, $w_{i}$ the matter power at
smaller scales is suppressed compared to $w_{i}=-1$ case, due to the longer
period of EDE (that suppresses the Weyl potential). As a result, we get a
lower $\sigma_{8}$ for larger $w_{i}$, showing that letting $w_{i}$ free to
vary may help in alleviating the tension with weak lensing surveys. The
increase of power at larger scales is due to the fact that
$\omega_{\Lambda}=1-\Omega_{\rm m}$ is smaller in models with larger $w_{i}$,
as a by product of the larger $h$ value that has increased $\Omega_{\rm
m}=\omega_{\rm m}h^{2}$ at fix $\omega_{\rm m}$.

##  IV Details of the analysis

###  IV.1 Data sets

We use a combination of CMB and BAO data sets along with S$H_{0}$ES and KIDS
priors. The details of our data sets are as follows:

  * •

Planck 2018 measurements of the low-$\ell$ CMB TT, EE, and high-$\ell$ TT, TE,
EE power spectra, together with the gravitational lensing potential
reconstruction [7].

  * •

The BAO measurements from 6dFGS at $z=0.106$ [9], SDSS DR7 at $z=0.15$ [43],
BOSS DR12 at $z=0.38,0.51$ and $0.61$ [8], and the joint constraints from
eBOSS DR14 Ly-$\alpha$ auto-correlation at $z=2.34$ [15] and cross-correlation
at $z=2.35$ [11].

  * •

The measurements of the growth function $f\sigma_{8}(z)$ (FS) from the CMASS
and LOWZ galaxy samples of BOSS DR12 at $z=0.38$, $0.51$, and $0.61$ [8].

  * •

The Pantheon SNIa catalogue, spanning redshifts $0.01<z<2.3$ [47]. We
anticipate that the new Pantheon+ [12] would not significantly affect our
conclusions.

  * •

The S$H_{0}$ES result, modeled with a Gaussian likelihood centered on
$H_{0}=73.2\pm 1.3$ km/s/Mpc [40]; however, choosing a different value that
combines various direct measurements, or the updated value from [42] would not
significantly affect our conclusions.

  * •

The KIDS1000+BOSS+2dfLenS weak lensing data, compressed as a split-normal
likelihood on the parameter $S_{8}=0.766^{+0.02}_{-0.014}$ [21]. We note that
there are additional measurements from DES [3] and the combination o KiDS and
DES [4] that show lower tension with Planck under $\Lambda$CDM, but we choose
this value as a representative example. Choosing a different prior would not
drastically change our conclusions.

###  IV.2 Methodology

Our baseline cosmology consists of the following combination of the six
$\Lambda$CDM parameters $\\{\omega_{b},\omega_{\rm
cdm},100\times\theta_{s},n_{s},{\rm ln}(10^{10}A_{s}),\tau_{\rm reio}\\}$,
plus four EDE parameters as discussed in Sec II, namely $w_{i}$, $w_{f}$,
$z_{\rm c}$, $f_{\rm EDE}$. We run MCMC analyses of the EDE model against
various combinations of the CMB, BAO, and supernovae data sets (details of
which are given in Sec IV.1) with the Metropolis-Hasting algorithm as
implemented in the MontePython-v3 [48] code interfaced with our modified
version of CLASS. All reported $\chi^{2}_{\rm min}$ are obtained with the
python package iMinuit 111https://iminuit.readthedocs.io/ [25]. We make use of
a Choleski decomposition to better handle a large number of nuisance
parameters [32] and consider chains to be converged with the Gelman-Rubin
convergence criterion $R-1<0.05$ [18].

We perform analyses of three different variations of the EDE model: i) a two-
parameter fluid model of EDE varying only ($f_{\rm EDE}$,$\rm z_{c}$) while
fixing the equation of state parameters as ($w_{i}=-1$,$w_{f}=1$), that we dub
2pEDE; ii) a three-parameter ($w_{f}$,$f_{\rm EDE}$,$z_{c}$) model dubbed
3pEDE; iii) a four-parameter ($w_{i}$,$w_{f}$,$f_{\rm EDE}$,$z_{c}$) dubbed
4pEDE. For each model, we perform three sets of runs, starting from the
baseline Planck+BAO+Pantheon, then adding the S$H_{0}$ES prior, and finally
the $S_{8}$ prior. We also perform the same sets of runs with $\Lambda$CDM for
comparison purposes. We set large flat prior for all $\Lambda$CDM parameters.
Prior ranges for Early dark energy parameters are imposed as follows:

Parameter name | prior range
---|---
$w_{i}$ | [-1,0]
$w_{f}$ | [0,1]
$f_{\rm EDE}$ | [0,0.3]
$\log_{10}(z_{c})$ | [2,5]

Note that we let $w_{i}$ be greater than $-1/3$, such that EDE does not
formally refer to a DE like component in some part of the parameter space.
Nevertheless, there is nothing that becomes mathematically ill defined in the
equations. We explore the $w_{i}>0$ part of the parameter space in App. A.

##  V Results

###  V.1 Results including the S$H_{0}$ES prior

Parameters $\downarrow$ | $\Lambda CDM$ | 2 param EDE | 3 param EDE | 4 param EDE
---|---|---|---|---
$100~{}\theta_{s}$ | $1.042066(1.04198)_{-0.00028}^{+0.00029}$ | $1.04158(1.04159)_{-0.00035}^{+0.00034}$ | $1.04160(1.04156)_{-0.00038}^{+0.00033}$ | $1.04124(1.04094)_{-0.00053}^{+0.0006}$
$100~{}\omega_{b}$ | $2.253(2.249)_{-0.014}^{+0.013}$ | $2.284(2.283)_{-0.023}^{+0.022}$ | $2.283(2.278)_{-0.025}^{+0.022}$ | $2.285(2.271)_{-0.024}^{+0.023}$
$\omega_{\rm cdm}$ | $0.1184(0.1183)_{-0.00088}^{+0.00089}$ | $0.1258(0.1247)_{-0.0031}^{+0.0035}$ | $0.1274(0.1267)_{-0.0032}^{+0.0034}$ | $0.128(0.1326)_{-0.0041}^{+0.0044}$
$\log{10^{10}A_{s}}$ | $3.054(3.056)_{-0.016}^{+0.015}$ | $3.063(3.067)_{-0.015}^{+0.015}$ | $3.065(3.072)_{-0.017}^{+0.015}$ | $3.063(3.066)_{-0.016}^{+0.015}$
$n_{s}$ | $0.9697(0.9701)_{-0.0037}^{+0.0037}$ | $0.9803(0.9819)_{-0.0062}^{+0.0062}$ | $0.9841(0.9849)_{-0.0068}^{+0.0066}$ | $0.983(0.9922)_{-0.007}^{+0.0078}$
$\tau_{\rm reio}$ | $0.0602(0.0617)_{-0.0082}^{+0.0073}$ | $0.0569(0.0600)_{-0.0076}^{+0.007}$ | $0.0573(0.0616)_{-0.0078}^{+0.0073}$ | $0.0578(0.0554)_{-0.0081}^{+0.0071}$
$f_{\rm EDE}$ | $-$ | $0.112(0.105)_{-0.036}^{+0.047}$ | $0.118(0.121)_{-0.034}^{+0.044}$ | $0.112(0.160)_{-0.04}^{+0.054}$
${\log_{10}(z_{c})}$ | $-$ | $3.53(3.51)_{-0.12}^{+0.09}$ | $3.67(3.61)_{-0.15}^{+0.091}$ | $3.82(3.81)_{-0.23}^{+0.15}$
$w_{i}$ | $-$ | $-$ | $-$ | $-0.651(-0.783)_{-0.35}^{+0.086}$
$w_{f}$ | $-$ | $-$ | $0.74(0.79)_{-0.13}^{+0.12}$ | $0.61(0.60)_{-0.13}^{+0.1}$
$\sigma_{8}$ | $0.8097(0.8108)_{-0.0064}^{+0.006}$ | $0.831(0.8305)_{-0.011}^{+0.011}$ | $0.834(0.836)_{-0.011}^{+0.011}$ | $0.830(0.841)_{-0.011}^{+0.012}$
$H_{0}$ [km/s/Mpc] | $68.18(68.12)_{-0.41}^{+0.39}$ | $70.03(70.09)_{-0.85}^{+0.91}$ | $70.46(70.52)_{-0.91}^{+0.9}$ | $70.68(71.59)_{-1.1}^{+1.2}$
$\chi^{2}_{\rm min}$ | 3826.58 | 3816.46 | 3814.53 | 3812.16
$\Delta\chi^{2}_{\rm min}$ | 0 | -10.12 | -12.05 | -14.5

Table 1: The mean (best-fit) $\pm 1\sigma$ error of the cosmological
parameters reconstructed from the lensing-marginalized Planck+BAO+SN1a data
with H0 prior  Figure 6: Posterior distributions in the $\Lambda$CDM and EDE
models reconstructed from Planck+BAO+Pantheon+$H_{0}$.

We start by comparing the ability of the different models to resolve the
Hubble tension and therefore focus on the Planck+BAO+Pantheon+S$H_{0}$ES
analyses. The reconstructed mean and best-fit values of parameters are given
in table 1. We provide $\chi^{2}_{\rm min}$ for $\Lambda$CDM vs 2pEDE vs 3pEDE
vs 4pEDE model in App. B in table 4 (without S$H_{0}$ES) and table 5 (with
S$H_{0}$ES). We plot the 1D and 2D posterior distribution of the EDE
parameters as well as $H_{0}$ and $S_{8}$ in figure 6 for $\Lambda$CDM
compared to the three different EDE models.

From the results, it is evident that the value of the Hubble parameter is
higher in the case of the 4pEDE model ($H_{0}=70.68_{-1.1}^{+1.2}$) compared
to the 3pEDE model ($H_{0}=70.46_{-0.91}^{+0.9}$) and 2pEDE model
($H_{0}=70.03_{-0.85}^{+0.91}$). In fact, the overall $\chi^{2}_{\rm min}$ is
also improved by 2.4 in the 4pEDE model compared to the 3pEDE model, which is
a slightly larger improvement in $\chi^{2}$ than when going from 2pEDE to
3pEDE. However, the value of $w_{i}$ is only weakly constrained, with only an
upper limit at $1\sigma$ of $w_{i}<-0.565$, but compatible with $0$ at
$2\sigma$. In App. A, we find that the only hard limit on $w_{i}$ is
$w_{i}<1/3$, from the requirement that EDE does not dominate the energy
density at early times.

Most importantly, while the value of $H_{0}$ is slightly larger, the value of
$\sigma_{8}$ has slightly decreased, by $\sim 0.4\sigma$. This indicates that
$w_{i}$ may indeed play a role in the $S_{8}$ tension, and we now turn to
include $S_{8}$ measurements in the analysis.

Parameters $\downarrow$ | $\Lambda CDM$ | 3 param EDE | 4 param EDE
---|---|---|---
$100~{}\theta_{s}$ | $1.04210(1.04214)_{-0.00028}^{+0.00028}$ | $1.04185(1.04178)_{-0.00042}^{+0.00034}$ | $1.04143(1.04163)_{-0.00051}^{+0.00072}$
$100~{}\omega_{b}$ | $2.258(2.268)_{-0.013}^{+0.013}$ | $2.277(2.271)_{-0.023}^{+0.02}$ | $2.281(2.271)_{-0.024}^{+0.021}$
$\omega_{\rm cdm}$ | $0.1177(0.1179)_{-0.00081}^{+0.00085}$ | $0.1227(0.1225)_{-0.0035}^{+0.0029}$ | $0.1238(0.1228)_{-0.0044}^{+0.0034}$
$\log{10^{10}A_{s}}$ | $3.048(3.037)_{-0.015}^{+0.014}$ | $3.053(3.050)_{-0.015}^{+0.015}$ | $3.053(3.044)_{-0.015}^{+0.015}$
$n_{s}$ | $0.9708(0.9712)_{-0.0037}^{+0.0036}$ | $0.9797(0.9814)_{-0.0074}^{+0.0072}$ | $0.9795(0.9802)_{-0.0074}^{+0.0071}$
$\tau_{\rm reio}$ | $0.0580(0.0520)_{-0.0078}^{+0.007}$ | $0.0562(0.0544)_{-0.0074}^{+0.0072}$ | $0.0569(0.0526)_{-0.0077}^{+0.0071}$
$f_{\rm EDE}$ | $-$ | $0.069(0.068)_{-0.048}^{+0.036}$ | $0.075(0.054)_{-0.048}^{+0.041}$
${\log_{10}(z_{c})}$ | $-$ | $3.79(3.72)_{-0.32}^{+0.14}$ | $3.89(4.02)_{-0.33}^{+0.22}$
$w_{i}$ | $-$ | $-$ | unconstrained (-0.34)
$w_{f}$ | $-$ | unconstrained$(0.65)$ | $0.58(0.45)_{-0.16}^{+0.1}$
$\sigma_{8}$ | $0.8051(0.8015)_{-0.006}^{+0.0057}$ | $0.817(0.817)_{-0.011}^{+0.01}$ | $0.8161(0.8109)_{-0.0096}^{+0.0095}$
$H_{0}$ [km/s/Mpc] | $68.48(68.50)_{-0.38}^{+0.38}$ | $69.94(69.92)_{-1}^{+0.92}$ | $70.25(69.93)_{-1.2}^{+1.1}$
$\chi^{2}_{\rm min}$ | 3832.41 | 3823.99 | 3823.79
$\Delta\chi^{2}_{\rm min}$ | 0 | -8.42 | -8.62
Table 2: The mean (best-fit) $\pm 1\sigma$ error of the cosmological
parameters reconstructed from Planck+BAO+SN1a data with $H_{0}+S_{8}$ priors.

###  V.2 Results including the $S_{8}$ prior

The mean and best-fit values of various parameters are reported in table 2 and
we plot the same parameters as before in Figure 7. All $\chi^{2}_{\rm min}$
numbers are provided in table 6.

The main impact of adding the $S_{8}$ prior is to reduce the preference for
non-zero EDE and decrease the value of $H_{0}$ while pulling $\sigma_{8}$
down. The $\Delta\chi^{2}$ with respect to $\Lambda$CDM is also significantly
decreased compared to the case without $S_{8}$ prior. In addition, the 4pEDE
model fit is only marginally better than the 3p EDE model, and $w_{i}$ is now
unconstrained. We conclude that, even though the addition of $w_{i}$ does
slightly decrease the $S_{8}$ parameter, it cannot help in resolving both
$H_{0}$ and $S_{8}$ tension simultaneously in the EDE model.

Figure 7: Same as Fig. 6, now also include the $S_{8}$ prior.

##  VI Conclusions

We have explored the cosmological implications of early dark energy beyond
slow roll (e.g. non-cc equation of state), by changing the initial equation of
state $w_{i}$, usually set to $-1$. Our main findings are as follows:

  * •

When one increases $w_{i}$ at fix $f_{\rm EDE}$ and $z_{c}$, EDE contributes
for a longer time to the expansion rate prior to recombination, resulting in a
smaller sound horizon of the CMB and hence a larger $H_{0}$.

  * •

The background effect leads to a suppression of the Weyl potential, due to the
larger contribution of non-clustering EDE to the total energy density. This
results in a comparatively lower power at small scales and hence a smaller
$\sigma_{8}$. We also find that there are additional perturbative effects due
to $w_{i}$ for modes that enter the horizon before or around $z_{c}$, although
the effects on observable are small compared to the main background effect.

  * •

We have confronted three variants of the EDE model to the combination of
Planck18+BAO+Pantheon+S$H_{0}$ES: a two-parameter EDE model with $w_{i}$ and
$w_{f}$ fixed, a three-parameter EDE model with $w_{f}$ freed, and the four-
parameter EDE model with both $w_{i}$ and $w_{f}$ free. We have found that the
overall $\chi^{2}_{\rm min}$ is improved by -2.4 at the expense of one more
parameter $w_{i}$ compared to the 3-parameters model, and by -4.4 compared to
the 2-parameters one. However, $w_{i}$ is not detected in this analysis, and
we only derive a weak upper limit at $1\sigma$, $w_{i}<-0.565$.

  * •

Interestingly, the model with $w_{i}$ free has a slightly larger $H_{0}$, and
a value of $S_{8}$ decreased by $\sim 0.4\sigma$. However, the inclusion of
$S_{8}$ data reduces the preference for non-zero EDE, with a degradation in
the $\chi^{2}_{\rm min}$.

Although the results derived in this work indicate that a non-cc EDE cannot
resolve both $H_{0}$ and $S_{8}$ tensions simultaneously, we hope that it will
trigger further work towards mitigating the increase of small-scale power that
is induced in the EDE cosmology. In fact, this is a requirement not only of
EDE, but generally of the fact that a larger $H_{0}$ (as measured by
S$H_{0}$ES) and a well-constrained $\Omega_{m}$ (as measured by Pantheon and
BAO data) must imply a larger $\omega_{m}\equiv\Omega_{m}h^{2}$, and therefore
earlier matter domination and larger $\sigma_{8}$. Models of EDE in that sense
already manage to compensate for the effect of the larger $H_{0}$ and the
larger $\omega_{m}$ to adjust CMB data but do not sufficiently reduce the
growth of structures. It therefore remains to explore how one may further
build upon these results, within an EDE cosmology [36] or others [26, 46], to
finally resolve cosmic tensions simultaneously.

## Acknowledgements

We acknowledge HPC NOVA, IIA Bangalore where numerical simulations were
performed. VP is supported by funding from the European Research Council (ERC)
under the European Union’s HORIZON-ERC-2022 (Grant agreement No. 101076865).

## References

  * Abbott et al. [2018a] Abbott, T., et al. 2018a, Phys. Rev. D, 98, 043526, doi: 10.1103/PhysRevD.98.043526
  * Abbott et al. [2018b] Abbott, T. M. C., et al. 2018b, Mon. Not. Roy. Astron. Soc., 480, 3879, doi: 10.1093/mnras/sty1939
  * Abbott et al. [2022] —. 2022, Phys. Rev. D, 105, 023520, doi: 10.1103/PhysRevD.105.023520
  * Abbott et al. [2023] —. 2023.  https://arxiv.org/abs/2305.17173
  * Abdalla et al. [2022] Abdalla, E., et al. 2022, JHEAp, 34, 49, doi: 10.1016/j.jheap.2022.04.002
  * Aghanim et al. [2018a] Aghanim, N., et al. 2018a.  https://arxiv.org/abs/1807.06209
  * Aghanim et al. [2018b] —. 2018b.  https://arxiv.org/abs/1807.06209
  * Alam et al. [2017] Alam, S., et al. 2017, Mon. Not. Roy. Astron. Soc., 470, 2617, doi: 10.1093/mnras/stx721
  * Beutler et al. [2011] Beutler, F., Blake, C., Colless, M., et al. 2011, Mon. Not. Roy. Astron. Soc., 416, 3017, doi: 10.1111/j.1365-2966.2011.19250.x
  * Blas et al. [2011] Blas, D., Lesgourgues, J., & Tram, T. 2011, JCAP, 07, 034, doi: 10.1088/1475-7516/2011/07/034
  * Blomqvist et al. [2019] Blomqvist, M., et al. 2019, Astron. Astrophys., 629, A86, doi: 10.1051/0004-6361/201935641
  * Brout et al. [2022] Brout, D., et al. 2022, Astrophys. J., 938, 110, doi: 10.3847/1538-4357/ac8e04
  * Carrillo González et al. [2023] Carrillo González, M., Liang, Q., Sakstein, J., & Trodden, M. 2023.  https://arxiv.org/abs/2302.09091
  * Cooke et al. [2016] Cooke, R. J., Pettini, M., Nollett, K. M., & Jorgenson, R. 2016, Astrophys. J., 830, 148, doi: 10.3847/0004-637X/830/2/148
  * de Sainte Agathe et al. [2019] de Sainte Agathe, V., et al. 2019, Astron. Astrophys., 629, A85, doi: 10.1051/0004-6361/201935638
  * Di Valentino et al. [2021a] Di Valentino, E., et al. 2021a, Astropart. Phys., 131, 102605, doi: 10.1016/j.astropartphys.2021.102605
  * Di Valentino et al. [2021b] Di Valentino, E., Mena, O., Pan, S., et al. 2021b, Class. Quant. Grav., 38, 153001, doi: 10.1088/1361-6382/ac086d
  * Gelman & Rubin [1992] Gelman, A., & Rubin, D. B. 1992, Statist. Sci., 7, 457, doi: 10.1214/ss/1177011136
  * Gogoi et al. [2021] Gogoi, A., Sharma, R. K., Chanda, P., & Das, S. 2021, Astrophys. J., 915, 132, doi: 10.3847/1538-4357/abfe5b
  * Heymans et al. [2013] Heymans, C., et al. 2013, Mon. Not. Roy. Astron. Soc., 432, 2433, doi: 10.1093/mnras/stt601
  * Heymans et al. [2021] —. 2021, Astron. Astrophys., 646, A140, doi: 10.1051/0004-6361/202039063
  * Hildebrandt et al. [2020] Hildebrandt, H., et al. 2020, Astron. Astrophys., 633, A69, doi: 10.1051/0004-6361/201834878
  * Hill et al. [2020] Hill, J. C., McDonough, E., Toomey, M. W., & Alexander, S. 2020, Phys. Rev. D, 102, 043507, doi: 10.1103/PhysRevD.102.043507
  * Hu [1998] Hu, W. 1998, Astrophys. J., 506, 485, doi: 10.1086/306274
  * James & Roos [1975] James, F., & Roos, M. 1975, Computer Physics Communications, 10, 343, doi: 10.1016/0010-4655(75)90039-9
  * Joseph et al. [2023] Joseph, M., Aloni, D., Schmaltz, M., Sivarajan, E. N., & Weiner, N. 2023, Phys. Rev. D, 108, 023520, doi: 10.1103/PhysRevD.108.023520
  * Joudaki et al. [2020] Joudaki, S., et al. 2020, Astron. Astrophys., 638, L1, doi: 10.1051/0004-6361/201936154
  * Kamionkowski & Riess [2022] Kamionkowski, M., & Riess, A. G. 2022.  https://arxiv.org/abs/2211.04492
  * Karwal & Kamionkowski [2016] Karwal, T., & Kamionkowski, M. 2016, Phys. Rev. D, 94, 103523, doi: 10.1103/PhysRevD.94.103523
  * Knox & Millea [2020] Knox, L., & Millea, M. 2020, Phys. Rev. D, 101, 043533, doi: 10.1103/PhysRevD.101.043533
  * Lesgourgues [2011] Lesgourgues, J. 2011.  https://arxiv.org/abs/1104.2932
  * Lewis et al. [2000] Lewis, A., Challinor, A., & Lasenby, A. 2000, Astrophys. J. , 538, 473, doi: 10.1086/309179
  * Lin et al. [2019] Lin, M.-X., Benevento, G., Hu, W., & Raveri, M. 2019, Phys. Rev. D, 100, 063542, doi: 10.1103/PhysRevD.100.063542
  * Lin et al. [2023] Lin, M.-X., McDonough, E., Hill, J. C., & Hu, W. 2023, Phys. Rev. D, 107, 103523, doi: 10.1103/PhysRevD.107.103523
  * MacCrann et al. [2015] MacCrann, N., Zuntz, J., Bridle, S., Jain, B., & Becker, M. R. 2015, Mon. Not. Roy. Astron. Soc., 451, 2877, doi: 10.1093/mnras/stv1154
  * McDonough et al. [2022] McDonough, E., Lin, M.-X., Hill, J. C., Hu, W., & Zhou, S. 2022, Phys. Rev. D, 106, 043525, doi: 10.1103/PhysRevD.106.043525
  * Niedermann & Sloth [2022] Niedermann, F., & Sloth, M. S. 2022, Phys. Lett. B, 835, 137555, doi: 10.1016/j.physletb.2022.137555
  * Poulin et al. [2023] Poulin, V., Smith, T. L., & Karwal, T. 2023.  https://arxiv.org/abs/2302.09032
  * Poulin et al. [2019] Poulin, V., Smith, T. L., Karwal, T., & Kamionkowski, M. 2019, Phys. Rev. Lett., 122, 221301, doi: 10.1103/PhysRevLett.122.221301
  * Riess et al. [2021] Riess, A. G., Casertano, S., Yuan, W., et al. 2021, Astrophys. J. Lett., 908, L6, doi: 10.3847/2041-8213/abdbaf
  * Riess et al. [2019] Riess, A. G., Casertano, S., Yuan, W., Macri, L. M., & Scolnic, D. 2019, Astrophys. J., 876, 85, doi: 10.3847/1538-4357/ab1422
  * Riess et al. [2022] Riess, A. G., et al. 2022, Astrophys. J. Lett., 934, L7, doi: 10.3847/2041-8213/ac5c5b
  * Ross et al. [2015] Ross, A. J., Samushia, L., Howlett, C., et al. 2015, Mon. Not. Roy. Astron. Soc., 449, 835, doi: 10.1093/mnras/stv154
  * Sabla & Caldwell [2022] Sabla, V. I., & Caldwell, R. R. 2022, Phys. Rev. D, 106, 063526, doi: 10.1103/PhysRevD.106.063526
  * Schöneberg et al. [2021] Schöneberg, N., Franco Abellán, G., Pérez Sánchez, A., et al. 2021.  https://arxiv.org/abs/2107.10291
  * Schöneberg et al. [2023] Schöneberg, N., Franco Abellán, G., Simon, T., et al. 2023.  https://arxiv.org/abs/2306.12469
  * Scolnic et al. [2018] Scolnic, D. M., et al. 2018, Astrophys. J., 859, 101, doi: 10.3847/1538-4357/aab9bb
  * Thejs Brinckmann [2018] Thejs Brinckmann, J. L. 2018.  https://arxiv.org/abs/1804.07261
  * Vagnozzi [2021] Vagnozzi, S. 2021, Phys. Rev. D, 104, 063524, doi: 10.1103/PhysRevD.104.063524

##  Appendix A Effect of changing prior on $w_{i}$

Figure 8: Effect of changing prior on $w_{i}$

In the main text, we have examined the possibility of changing the initial
equation of state parameter $w_{i}\in[-1,0]$. Now let us examine the case
beyond Dark Energy, with $w_{i}\in[-0.33,1]$. The rest of the parameters are
varied as in the main body of the paper. Our main results are shown in figure
8, which compare the results of $w_{i}\in[-0.33,1]$ with the regular prior
given in the main text, when Planck+BAO+Pantheon+$H_{0}$+$S_{8}$ data are
used. We also provide in table 3 the parameters reconstructed either when
including only the $H_{0}$ prior or both the $H_{0}$ and $S_{8}$ priors.

First, the posterior of $w_{i}$ has a strict upper bound around 0.3, which
simply comes from the fact that a fluid with larger $w_{i}$ would come to
dominate the expansion rate at early times and spoil the fit to data. Second,
one can see that the posterior of $S_{8}$ exactly matches with $\Lambda$CDM,
while $H_{0}$ is significantly larger. In other words, an “EDE” model with
$w_{i}>-0.33$ can perform as good as regular EDE in resolving the tension
without worsening the $S_{8}$ tension. In terms of $\chi^{2}$ number, the
model of EDE with $w_{i}\in[-1,0]$ performs slightly better (by $-1.2$) when
the $H_{0}$ prior is left out of the analysis. However, the model with
$w_{i}\in[-1/3,0]$ performs better when $S_{8}$ is included, as the EDE
contribution lasts even longer, further reducing the growth of the structure.

Parameters $\downarrow$ |  $H_{0}$ prior |  $H_{0}$+$S_{8}$ prior
---|---|---
$100~{}\theta_{s}$ | $1.04143(1.04036)_{-0.00095}^{+0.0011}$ | $1.04108(1.04026)_{-0.00065}^{+0.0013}$
$100~{}\omega_{b}$ | $2.278(2.285)_{-0.024}^{+0.02}$ | $2.279(2.272)_{-0.023}^{+0.019}$
$\omega_{\rm cdm}$ | $0.126(0.1298)_{-0.0042}^{+0.0042}$ | $0.1233(1.268)_{-0.0051}^{+0.0027}$
$\log{10^{10}A_{s}}$ | $3.059(3.060)_{-0.015}^{+0.015}$ | $3.051(3.062)_{-0.016}^{+0.014}$
$n_{s}$ | $0.979(0.9826)_{-0.0067}^{+0.007}$ | $0.977(0.9810)_{-0.0075}^{+0.0061}$
$\tau_{\rm reio}$ | $0.0590(0.0576)_{-0.0078}^{+0.0073}$ | $0.0577(0.0605)_{-0.0079}^{+0.0069}$
$f_{\rm EDE}$ | $0.081(0.120)_{-0.045}^{+0.041}$ | $0.065(0.094)_{-0.055}^{+0.028}$
${\log_{10}(z_{c})}$ | $4.11(3.96)_{-0.28}^{+0.12}$ | $4.134(4.038)_{-0.5}^{+0.31}$
$w_{i}$ | $<0.33(-0.20)$ | $<0.33(0.0978)$
$w_{f}$ | $0.461(0.483)_{-0.089}^{+0.082}$ | $0.486(0.409)_{-0.15}^{+0.057}$
$\sigma_{8}$ | $0.8195(0.8252)_{-0.0087}^{+0.0085}$ | $0.8109(0.8172)_{-0.0088}^{+0.0074}$
$H_{0}$ [km/s/Mpc] | $70.23(70.97)_{-1.1}^{+1.1}$ | $70.08(70.78)_{-1.3}^{+0.99}$
$\chi^{2}_{\rm min}$ | 3813.32 | 3822.69
$\Delta\chi^{2}_{\rm min}$ | -13.26 | -9.72
Table 3: The mean (best-fit) $\pm 1\sigma$ error of the cosmological
parameters reconstructed from Planck+BAO+SN1a data with H0 and $S_{8}$ when
$w_{i}\in[-0.333,1]$

##  Appendix B Tables of $\chi^{2}$

Experiments/Data |  $\Lambda$CDM | 2-param EDE | 3-param EDE | 4-param EDE
---|---|---|---|---
Planck high$-\ell$ TT,TE,EE | 2347.90 | 2348.99 | 2346.49 | 2346.95
Planck low$-\ell$ EE | 396.60 | 396.03 | 396.65 | 396.63
Planck low$-\ell$ TT | 22.97 | 22.22 | 21.89 | 22.19
Planck lensing | 8.76 | 9.016 | 9.04 | 9.16
Pantheon | 1025.92 | 1025.99 | 1025.81 | 1026.02
BAO FS BOSS DR12 | 6.61 | 7.23 | 6.68 | 7.38
BAO BOSS low$-z$ | 1.19 | 1.10 | 1.30 | 1.06
total | 3809.99 | 3810.59 | 3807.90 | 3809.44

Table 4: Best-fit $\chi^{2}$ per experiment (and total) when no prior was
included.

Experiments/Data |  $\Lambda$CDM | 2-param EDE | 3-param EDE | 4-param EDE | 4-param $w_{i}\in[-0.333,1]$
---|---|---|---|---|---
Planck high$-\ell$ TT,TE,EE | 2348.49 | 2349.17 | 2347.96 | 2349.86 | 2349.51
Planck low$-\ell$ EE | 397.97 | 397.16 | 397.77 | 396.09 | 396.63
Planck low$-\ell$ TT | 22.67 | 21.57 | 21.33 | 20.69 | 21.37
Planck lensing | 8.95 | 8.96 | 9.16 | 9.81 | 9.24
Pantheon | 1025.69 | 1025.64 | 1025.64 | 1025.70 | 1025.68
BAO FS BOSS DR12 | 5.93 | 6.42 | 6.61 | 6.99 | 6.42
BAO BOSS low$-z$ | 1.61 | 1.82 | 1.79 | 1.47 | 1.51
S$H_{0}$ES | 15.23 | 5.68 | 4.23 | 1.52 | 2.92
total | 3826.58 | 3816.46 | 3814.53 | 3812.16 | 3813.32

Table 5: Best-fit $\chi^{2}$ per experiment (and total) when the S$H_{0}$ES
prior is included.

Experiments/Data |  $\Lambda$CDM | 3-param EDE | 4-param EDE | 4-param $w_{i}\in[-0.333,1]$
---|---|---|---|---
Planck high$-\ell$ TT,TE,EE | 2353.87 | 2350.49 | 2351.38 | 2350.96
Planck low$-\ell$ EE | 395.68 | 395.89 | 395.75 | 397.42
Planck low$-\ell$ TT | 22.30 | 21.29 | 21.32 | 21.56
Planck lensing | 10.63 | 10.02 | 10.46 | 9.40
Pantheon | 1025.63 | 1025.62 | 1025.63 | 1025.62
BAO FS BOSS DR12 | 5.87 | 6.29 | 6.10 | 6.14
BAO BOSS low$-z$ | 1.92 | 2.154 | 2.069 | 1.90
S$H_{0}$ES | 13.06 | 6.36 | 6.29 | 3.40
$\rm S_{8}(KIDS1000)$ | 3.41 | 5.84 | 4.74 | 6.25
total | 3832.41 | 3823.99 | 3823.79 | 3822.69

Table 6: Best-fit $\chi^{2}$ per experiment (and total) when
S$H_{0}$ES$+S_{8}$ prior is included.