[1,2]Pedro H. G. Lugão These authors contributed equally to this work.

These authors contributed equally to this work.

[1]National Laboratory of Scientific Computing - LNCC, Av. Getúlio Vargas,
Petrópolis, 25651-075, RJ, Brazil

2]Universidade Federal de Juiz de Fora - UFJF, Rua José Lourenço Kelmer, Juiz
de Fora, 36036-900, MG, Brazil

# Quantum search by continuous-time quantum walk on $t$-designs

0000-0002-2316-445X<EMAIL_ADDRESS>Renato Portugal
0000-0003-0894-4279<EMAIL_ADDRESS>*  [

###### Abstract

This work examines the time complexity of quantum search algorithms on
combinatorial $t$-designs with multiple marked elements using the continuous-
time quantum walk. Through a detailed exploration of $t$-designs and their
incidence matrices, we identify a subset of bipartite graphs that are
conducive to success compared to random-walk-based search algorithms. These
graphs have adjacency matrices with eigenvalues and eigenvectors that can be
determined algebraically and are also suitable for analysis in the multiple-
marked vertex scenario. We show that the continuous-time quantum walk on
certain symmetric $t$-designs achieves an optimal running time of
$O(\sqrt{n})$, where $n$ is the number of points and blocks, even when
accounting for an arbitrary number of marked elements. Upon examining two
primary configurations of marked elements distributions, we observe that the
success probability is consistently $o(1)$, but it approaches 1 asymptotically
in certain scenarios.

###### keywords:

Quantum walks, Quantum search, $t$-designs, Bipartite graphs

##  1 Introduction

Continuous-time quantum walk, a quantum analog of the continuous-time Markov
chain, is a dynamic paradigm that is crucial to quantum computation and
information processing [1]. They are powerful computational procedures that
encompass the non-classical properties of quantum systems, enabling them to
explore superposition and entanglement with a straightforward formalism.
Continuous-time quantum walk and the alternative versions in discrete-time are
invaluable tools in constructing quantum search algorithms, where they can
perform searches over graphs faster than their classical counterparts [2].
This speedup underlies their advantage in finding solutions to various
optimization problems [3]. Furthermore, quantum walks offer a robust mechanism
for simulating complex quantum physical systems, enabling the understanding
and prediction of the behavior of quantum particles in various environments
[4].

The fundamental concept behind a quantum walk-based search algorithm involves
initializing a quantum walker at a state that is easily prepared, and then
allowing it to evolve according to a standard quantum walk operator, which is
modified by an oracle that identifies the locations of the marked vertices.
When the quantum walk operator is aptly designed, the quantum walker will not
only reach the marked vertex eventually but also display a significant
probability of being found at one of the marked vertices. Indeed, the
efficiency of a quantum walk-based search algorithm is determined by both the
runtime and the success probability [5].

Given the current progress in quantum computing, it becomes compelling to
explore quantum search algorithms on classes of graphs, as opposed to
individual graphs, and to determine the time complexity of these algorithms
relative to the number of vertices. Historically, the class of complete graphs
was the first to undergo analysis. In this context, quantum-walk-based search
mirrors the function of Grover’s algorithm [6]. Quantum search by continuous-
time quantum walk on certain specific graph classes is analyzed in [2, 7, 8].
The fascinating interplay between quantum computation and combinatorial graph
theory persistently unveils geometrical structures that hold potential for
devising new quantum algorithms.

One structure in combinatorial mathematics is the block design [9, 10]. It
refers to an incidence structure comprising a set of points and a selection of
subset families, termed blocks. The points within these blocks are chosen to
meet specific frequency conditions. This meticulous selection ensures that the
entire collection of blocks exhibits a sense of symmetry, often termed
“balance”. In the absence of additional context, the term “block design” is
typically interpreted as a balanced incomplete block design or, equivalently,
a 2-design. Historically, this specific type has been extensively researched
due to its pivotal role in experimental design, coding theory, cryptography,
and software testing [11]. Such applications may also be influential in the
quantum realm, making it intriguing to examine the relationship between
$2$-designs and quantum algorithms from a theoretical standpoint. A more
generalized version of this concept is the $t$-design, which is the structure
of our interest.

While our primary focus in this paper lies on combinatorial $t$-designs, it’s
worth noting the intriguing extension of these designs into the realm of
quantum mechanics, known as quantum $t$-designs [12]. In the context of
quantum information theory, a set of quantum states forms a quantum $t$-design
if the average of certain quantum operations, specifically those expressible
as polynomials of degree $t$ or less in the entries of a density matrix, over
this set mirrors that of the entire space of quantum states (according to the
Haar measure). Essentially, quantum $t$-designs offer a compact and
representative subset of quantum states, capturing the statistical properties
of random quantum states up to the $t$-th moment. These designs have found
applications in quantum algorithms [13] and quantum error correction [14].

Turning our attention back to the concept of combinatorial $t$-designs, the
incidence matrix of a $t$-design enumerates the repetitions of each point
within every block. As the incidence matrix constitutes a bipartite graph
[15], a continuous-time quantum walk on a $t$-design is synonymous with a walk
on its corresponding bipartite graph. Apart from the complete bipartite graph,
there are limited results in existing literature that establish the time
complexity of search algorithms on bipartite graphs. To our best
understanding, none of these address scenarios involving multiple marked cases
in the continuous-time model. Indeed, quantum-walk-based search algorithms
have a rich history in the single-marked case, beginning with the foundational
paper by Shenvi et al. [16] and Childs&Goldstone [2] on searching for a single
marked vertex on hypercubes and other graphs. However, the focus has recently
shifted to the multiple-marked case [17, 18, 19, 20, 21].

The primary goal of this work is to determine the time complexity of quantum
search algorithms on $t$-designs with multiple marked elements (points or
blocks) using the continuous-time quantum walk. Such effort helps in
discerning the time complexity of quantum search on bipartite graphs, a
notably challenging problem. Our focus lies in pinpointing specific subsets of
bipartite graphs that are most conducive to producing successful results.
Ideally, these graphs would have adjacency matrices with determinable
eigenvalues and eigenvectors in algebraic terms, underlining their suitability
for evaluating the time complexity in the multiple-marked vertex context. We
use $t$-designs to identify such a significant subset of bipartite graphs. Our
findings indicate that the optimal running time of a continuous-time quantum
walk on certain symmetric $t$-designs is $O(\sqrt{n})$, where $n$ stands for
the number of points and blocks, even when accounting for an arbitrary number
of marked elements. We assess two configurations: in the first, all marked
elements are situated in one part of the bipartite graph, meaning that all of
them are points or all of them are blocks; in the second, the marked elements
are evenly distributed between the two parts. The probability of success
remains consistently $o(1)$ across both setups, but it approaches 1 in
particular scenarios.

This paper is organized as follows. In Section 2, we derive the spectral
decomposition of symmetric $t$-designs. In Section 3, we first determine the
time complexity of a quantum search using a continuous-time quantum walk on
symmetric $t$-designs, beginning with the single-marked case. We then address
the two-marked case, and subsequently, build up to the multiple-marked
scenario. We conclude our discussion in Section 4, where we present our final
thoughts and conclusions.

##  2 Spectral decomposition of symmetric t-designs

Let $X$ be a finite set of $v$ elements called points. Let $k$ and $\lambda$
be positive integers. The definition of a $t$-design, which includes the
balanced incomplete block design (2-design) is as follows.

######  Definition 1 ($t$-design).

Given a set $X$ of $v<\infty$ elements (called points) and any positive
integer $t$, assuming that $t\leq k\leq v$, a $t$-$(v,k,\lambda)$-design is a
class of $k$-subsets of $X$, called blocks, such that every point $x$ in $X$
appears in exactly $r$ blocks, and every $t$-subset appears in exactly
$\lambda$ blocks.

Let us define

$\lambda_{i}=\lambda{\binom{v-i}{t-i}}{\binom{k-i}{t-i}}^{-1}$

for $i=0,1,\ldots,t$. Note that $\lambda_{t}=\lambda$ and $\lambda_{i}$
represents the number of blocks that contain any $i$-set of points.

The number of blocks $b$ in a $t$-design is given by

$b=\lambda_{0}=\lambda{v\choose t}{k\choose t}^{-1}.$

Number $r$ is given by

$r=\lambda_{1}=\lambda{v-1\choose t-1}{k-1\choose t-1}^{-1}.$

Any $t$-$(v,k,\lambda)$-design is also an $s$-$(v,k,\lambda)$-design for any
$s$ satisfying $1\leq s\leq t$ [9]. It should be observed that the $\lambda$
value changes as described above and is dependent on $s$. It follows that
every $t$-design with $t\geq 2$ is also a 2-design. Besides, the number of
blocks $\lambda_{i}$ that contain any $i$-subset of $X$ in a $t$-design is
independent of the choice of the subset for $i=1,\ldots,t$. The term block
design by itself usually means a 2-design. Given numbers $t$, $v$, $k$, and
$\lambda$, it is no easy task to find examples of $t$-$(v,k,\lambda)$-designs.

Let $\mathcal{D}$ be a $t$-design with parameters $(v,b,r,k,\lambda_{t})$ and
$G$ its incidence graph. By definition, $G$ is a $(r,k)$-biregular bipartite
graph [15]. The adjacency matrix of $G$ is

$A=\begin{pmatrix}0&N\\\ N^{T}&0\end{pmatrix},$ (1)

where $N$ is a $v\times b$ incidence matrix.

######  Theorem 1.

Let $\mathcal{D}$ be a symmetric $t$-design (i.e., $v=b$ and $r=k$). Then, the
eigenvalues of the adjacency matrix of $\mathcal{D}$ are $\\{\pm
k,\pm\sqrt{r-\lambda_{2}}\\}$ and the spectral idempotents are

$\displaystyle E_{-k}$ $\displaystyle=\frac{1}{2v}\begin{pmatrix}J&-J\\\
-J&J\end{pmatrix},$ (2) $\displaystyle E_{k}$
$\displaystyle=\frac{1}{2v}\begin{pmatrix}J&J\\\ J&J\end{pmatrix},$ (3)
$\displaystyle E_{-\sqrt{r-\lambda_{2}}}$
$\displaystyle=\frac{1}{2}\begin{pmatrix}\mathrm{I}-\frac{1}{v}J&-M\\\
-M^{T}&\mathrm{I}-\frac{1}{v}J\end{pmatrix},$ (4) $\displaystyle
E_{\sqrt{r-\lambda_{2}}}$
$\displaystyle=\frac{1}{2}\begin{pmatrix}\mathrm{I}-\frac{1}{v}J&M\\\
M^{T}&\mathrm{I}-\frac{1}{v}J\end{pmatrix},$ (5)

where $M=\frac{1}{v\sqrt{r-\lambda_{2}}}\left(-kJ+vN\right)$ and $J$ is a
matrix of ones.

###### Proof.

To proof this theorem, it suffices to show that
{$E_{k},E_{-k},E_{\sqrt{r-\lambda_{2}}},E_{-\sqrt{r-\lambda_{2}}}$} is a set
of orthogonal projectors obeying the completeness relation
$\sum_{i}E_{i}=\mathrm{I}$ and that the spectral decomposition of $A$ is

$A=kE_{k}+(-k)E_{-k}+\sqrt{r-\lambda_{2}}E_{\sqrt{r-\lambda_{2}}}+(-\sqrt{r-\lambda_{2}})E_{-\sqrt{r-\lambda_{2}}}.$
(6)

The following equations are valid identities:

  1. 1.

$J^{2}=vJ$

  2. 2.

$(I-J/v)^{2}=(I-J/v)$

  3. 3.

$JN=NJ=N^{T}J=JN^{T}=kJ$

  4. 4.

$JM=MJ=M^{T}J=JM^{T}=0$

  5. 5.

$N^{T}N=NN^{T}=(r-\lambda_{2})(I-J/v)+k^{2}J/v$

  6. 6.

$MM^{T}=M^{T}M=I-J/v$

  7. 7.

$J(I-J/v)=0$

Using Identities (1)-(6), we show that $E_{\pm k}^{2}=E_{\pm k}$ and
$E_{\pm\sqrt{r-\lambda_{2}}}^{2}=E_{\pm\sqrt{r-\lambda_{2}}}$. Using
additionally Identity (7), we show that these projectors are pairwise
orthogonal. Summing the matrices we can see that $\sum_{i}E_{i}=\mathrm{I}$.
Finally using the definition of $M$ we check that Equation (6) is valid, which
concludes the demonstration. ∎

##  3 Quantum search

Quantum search by continuous-time quantum walk on a graph with adjacency
matrix $A$ is driven by a Hamiltonian $H$, whose expression is

$H=-\gamma A-\sum_{w\in W}\ket{w}\bra{w},$

where $\gamma$ is a positive parameter and $W$ represents the set of marked
vertices [2]. The evolution operator is given by

$U(t)=\text{e}^{-\text{i}Ht},$

and the state of the walk at time $t$ is $\ket{\psi(t)}=U(t)\ket{\psi(0)}$,
where $\ket{\psi(0)}$ denotes the initial state. The probability of finding
the walker on vertex $w$ at time $t$ is $p_{w}(t)=\left|\langle
w|\psi(t)\rangle\right|^{2}$. For our initial state, we assume an unbiased
uniform superposition. Our goals include (1) determining the optimal running
time $t_{\text{opt}}$ of the search algorithm as a function of the parameters
of the $t$-design, and (2) determining its success probability, which is
$\sum_{w\in W}p_{w}(t_{\text{opt}})$.

Now, let’s assess the time complexity of a quantum search using a continuous-
time quantum walk on symmetric $t$-designs. We will begin our analysis with
$t$-designs that contain a single marked vertex. Specifically, $W=\\{0\\}$,
where 0 stands for the label of a point or a block.

###  3.1 Single marked vertex

Assuming that the $t$-design is symmetric and contains only one marked vertex,
labeled 0, we next consider $\\{\phi_{l}\\}_{l=0}^{3}$ as the list of
eigenvalues of the $t$-design, ordered from highest to lowest.

Using the method outlined in [22, 23, 24, 19], we have to calculate the sums

$\displaystyle S_{1}$
$\displaystyle=\sum_{l=1}^{3}\frac{\|E_{\phi_{l}}\ket{0}\|^{2}}{\phi_{0}-\phi_{l}},$
$\displaystyle S_{2}$
$\displaystyle=\sum_{l=1}^{3}\frac{\|E_{\phi_{l}}\ket{0}\|^{2}}{(\phi_{0}-\phi_{l})^{2}},$

which are equal to

$S_{1}=\frac{v-1}{v}\frac{k}{k^{2}-r+\lambda_{2}}+\frac{1}{4vk}$

and

$S_{2}=\frac{v-1}{v}\frac{(k^{2}+r-\lambda_{2})}{(k^{2}-r+\lambda_{2})^{2}}+\frac{1}{8vk^{2}}.$

Now, take into consideration that the evolution operator is $\text{e}^{-iHt}$,
where $H=-\gamma A-\ket{0}\bra{0}$, the optimal value for $\gamma$ along with
its corresponding optimal hitting time are provided by

$\displaystyle\gamma$ $\displaystyle=S_{1},$ $\displaystyle t_{\text{opt}}$
$\displaystyle=\frac{\pi}{2\epsilon},$

where $\epsilon=\frac{S_{1}\|E_{k}\ket{0}\|}{\sqrt{S_{2}}}$. Using that
$\lambda_{2}=r(k-1)/(v-1)$ and $k=r$, we obtain

$t_{\text{opt}}=\frac{\pi\sqrt{k+1}}{\sqrt{2k}}\sqrt{v}+O\left(\frac{1}{\sqrt{v}}\right).$

Given that the number of vertices, ${n}$, equals $v+b=2v$, it follows that the
optimal time $t_{\text{opt}}$ is on the order of $\sqrt{{n}}$. To complete the
time complexity analysis, we must calculate the success probability, which is

$p_{\text{succ}}=\frac{S_{1}^{2}}{2vS_{2}\|E_{k}\ket{0}\|^{2}}=\frac{k}{k+1}+O\left(\frac{1}{v}\right).$

It’s interesting to note that, if the bipartite graph is complete, then $k=v$.
As a result, the success probability becomes $p_{\text{succ}}=1+O(1/v)$ and
the optimal running time is
$t_{\text{opt}}=\pi\sqrt{v}/\sqrt{2}+O(1/\sqrt{v})$. These are the expected
results for a complete bipartite graph as shown in [25].

While Theorem 1 doesn’t apply to complete graphs due to an indeterminacy in
$M$ when $k=v$ (since it implies $\lambda_{2}=r$), it is indeed a compelling
result that the final asymptotic behavior aligns with the theory as $k$
approaches $v$. As we increase the number of marked vertices, we may or may
not observe this same correspondence.

###  3.2 Multiple marked vertices

Adhering to the methodology presented in [19] for multiple marked vertices,
where $W$ is the set of marked vertices, our interest remains focused on only
two eigenvalues of the Hamiltonian, which are given by

$\lambda^{\pm}=-\gamma\phi_{0}\pm\epsilon.$ (7)

The extension of the one-marked case to the multiple-marked case for the
computation of these two eigenvalues implies that we must solve the equation

$\det(\Lambda_{\lambda})=0,$ (8)

where $\Lambda_{\lambda}$ is a $|W|\times|W|$ matrix defined as

$(\Lambda_{\lambda})_{ww^{\prime}}=\delta_{ww^{\prime}}+\sum_{l=0}^{3}\frac{\bra{w}E_{\phi_{l}}\ket{w^{\prime}}}{\lambda+\gamma\phi_{l}}.$
(9)

By combining Equations (9) and (7), we derive an expression for
$\Lambda_{\lambda(\epsilon)}$, denoted as $\Lambda_{\epsilon}$, accurate up to
the second order in $\epsilon$, which is

$(\Lambda_{\epsilon})_{ww^{\prime}}=\pm\frac{\bra{w}E_{k}\ket{w^{\prime}}}{\epsilon}+\delta_{ww^{\prime}}-\frac{S^{(1)}_{ww^{\prime}}}{\gamma}\mp\frac{\epsilon
S^{(2)}_{ww^{\prime}}}{\gamma^{2}},$ (10)

where

$S^{(1)}_{ww^{\prime}}=\sum_{l=1}^{3}\frac{\bra{w}E_{\phi_{l}}\ket{w^{\prime}}}{k-\phi_{l}}$
(11)

and

$S^{(2)}_{ww^{\prime}}=\sum_{l=1}^{3}\frac{\bra{w}E_{\phi_{l}}\ket{w^{\prime}}}{(k-\phi_{l})^{2}}.$
(12)

Despite this modification, Equation (8) remains challenging to compute for a
general case. Therefore, we confine our analysis to certain specific cases
where the determinant can be more readily managed.

#### Two-marked vertices

We now proceed to analyze the two-marked case to aid in the computation of the
more challenging multiple-marked case. Since we only have two marked vertices,
$\Lambda_{\lambda}$ is a $2\times 2$ matrix. Although the determinant is
straightforward to compute, it’s important to note that
$(\Lambda_{\lambda})_{ww^{\prime}}$ with $w\neq w^{\prime}$ can have different
expressions depending on the location and relation between the marked
vertices, as determined by the values of $S^{(1)}_{ww^{\prime}}$ and
$S^{(2)}_{ww^{\prime}}$. Thus, even with just two marked vertices, we must
consider three different cases to exhaust all possibilities using that the
bipartite graph has two parts $V$ and $V^{\prime}$.

#### Case 1: $w$ and $w^{\prime}$ adjacent

In the scenario that $w\in V$ and $w^{\prime}\in V^{\prime}$ belong to
different parts but they are adjacent, we have

$\displaystyle S^{(1)}_{ww^{\prime}}$
$\displaystyle=\frac{(-k+v)k}{v\sqrt{r-\lambda_{2}}(k^{2}-r+\lambda_{2})}-\frac{1}{4vk},$
$\displaystyle S^{(2)}_{ww^{\prime}}$
$\displaystyle=\frac{(-k+v)(k^{2}+r-\lambda_{2})}{v\sqrt{r-\lambda_{2}}(k^{2}-r+\lambda_{2})^{2}}-\frac{1}{8vk^{2}}.$

Given that $\Lambda_{\lambda}$ is a symmetric matrix, we find that

$\det(\Lambda_{\lambda})=\big{(}(\Lambda_{\lambda})_{ww}+(\Lambda_{\lambda})_{ww^{\prime}}\big{)}\big{(}(\Lambda_{\lambda})_{ww}-(\Lambda_{\lambda})_{ww^{\prime}}\big{)}.$

Term $(\Lambda_{\lambda})_{ww}+(\Lambda_{\lambda})_{ww^{\prime}}$ is the
eigenvalue of $\Lambda_{\lambda}$ associated with the uniform eigenvector. The
correct values for $\lambda^{\pm}$ are obtained equating this term to zero. We
select $\epsilon$ such that

$\displaystyle 0$
$\displaystyle=\epsilon\Big{(}(\Lambda_{\epsilon})_{ww}+(\Lambda_{\epsilon})_{ww^{\prime}}\Big{)}$
$\displaystyle=a(\gamma)+b(\gamma)\epsilon+c(\gamma)\epsilon^{2}+O(\epsilon^{3}),$

with $\gamma$ chosen in a manner such that $b(\gamma)=0$, leading us to two
symmetrical roots. This approach yields

$\gamma=\frac{k\left(k-v+(1-v)\sqrt{k-\lambda_{2}}\right)}{v\sqrt{k-\lambda_{2}}\,(k-\lambda_{2}-k^{2})}$
(13)

and

$\epsilon^{\pm}=\pm\frac{\sqrt{k+\sqrt{k}}}{\sqrt{k+1}}\frac{1}{\sqrt{v}}+O\left(\frac{1}{v}\right).$
(14)

By applying the formulas for the two-marked case as outlined in [19], we
obtain

$t_{\text{opt}}=\frac{\pi\sqrt{k+1}}{2\sqrt{k+\sqrt{k}}}\sqrt{v}+O\left(\frac{1}{v}\right)$

and

$p_{\text{succ}}=\frac{4\sqrt{k}(\sqrt{k}+1)^{3}(k+1)}{(4\sqrt{k}+k+2k\sqrt{k}+1)^{2}}+O\left(\frac{1}{\sqrt{v}}\right).$

#### Case 2: $w$ and $w^{\prime}$ are non-adjacent and belong to different
parts

In this scenario, we have

$\displaystyle S^{(1)}_{ww^{\prime}}$
$\displaystyle=\frac{-k^{2}}{v\sqrt{r-\lambda_{2}}(k^{2}-r+\lambda_{2})}-\frac{1}{4vk},$
$\displaystyle S^{(2)}_{ww^{\prime}}$
$\displaystyle=\frac{-k(k^{2}+r-\lambda_{2})}{v\sqrt{r-\lambda_{2}}(k^{2}-r+\lambda_{2})^{2}}-\frac{1}{8vk^{2}}.$

This minor difference in the scenario results in a different $\gamma$ value

$\gamma=\frac{k\left(k+(1-v)\sqrt{k-\lambda_{2}}\right)}{v\sqrt{k-\lambda_{2}}\,(k-\lambda_{2}-k^{2})}$
(15)

and in a simpler $\epsilon$

$\epsilon^{\pm}=\pm\frac{\sqrt{k}}{\sqrt{k+1}}\frac{1}{\sqrt{v}}+O\left(\frac{1}{v}\right).$
(16)

With those new expressions, we have

$t_{\text{opt}}=\displaystyle\frac{\pi\sqrt{k+1}}{2\sqrt{k}}\sqrt{v}+O\left(\frac{1}{\sqrt{v}}\right)$

and

$p_{\text{succ}}=\frac{k}{k+1}-O\left(\frac{1}{\sqrt{v}}\right).$

#### Case 3: $w$ and $w^{\prime}$ are in the same part

This is the simplest scenario ($\\{w,w^{\prime}\\}\in V$ or
$\\{w,w^{\prime}\\}\in V^{\prime}$) , since the sums are

$\displaystyle S^{(1)}_{ww^{\prime}}$
$\displaystyle=-\frac{k}{v(k^{2}-r+\lambda_{2})}+\frac{1}{4vk},$
$\displaystyle S^{(2)}_{ww^{\prime}}$
$\displaystyle=-\frac{k^{2}+r-\lambda_{2}}{v(k^{2}-r+\lambda_{2})^{2}}+\frac{1}{8vk^{2}}.$

Then, we obtain

$\gamma=\displaystyle\frac{2k^{2}v-3k^{2}+\lambda_{2}-r}{2kv\left(k^{2}+\lambda_{2}-r\right)}$
(17)

and

$\epsilon^{\pm}=\pm\frac{\sqrt{k}}{\sqrt{k+1}}\frac{1}{\sqrt{v}}+O\left(\frac{1}{v}\right),$
(18)

which is the same first-order expression of Case 2. The expression for the
optimal running time and success probability are

$t_{\text{opt}}=\displaystyle\frac{\pi\sqrt{k+1}}{2\sqrt{k}}\sqrt{v}+O\left(\frac{1}{\sqrt{v}}\right)$

and

$p_{\text{succ}}=\frac{k}{k+1}-O\left(\frac{1}{\sqrt{v}}\right),$

which are the same first-order expressions of Case 2.

#### All marked vertices are in the same part

To generalize this analysis, we restrict our attention to the case where there
are $m$ marked vertices in one of the parts of the bipartite graph. This is
the only situation where all vertices are related in the same way (as
described in the previous subsection), allowing us to fully compute the
determinant of the $\Lambda_{\lambda}$ matrix.

The key concept here is that $(\Lambda_{\lambda})_{ww^{\prime}}$ is the same
for every pair $(w,w^{\prime})$ in the same part ($V$ or $V^{\prime}$). This
fact can be verified by noting that the sums considered in the previous
section only depend on the relation between the two vertices, not their
position. Consequently, because every pair shares the same relation, we obtain
an $m\times m$ $\Lambda_{\lambda}$ matrix in the following form

$\begin{pmatrix}a&b&\ldots&b\\\ b&a&\ldots&b\\\ \vdots&\vdots&\ddots&\vdots\\\
b&b&\ldots&a\end{pmatrix},$

whose determinant is $(a-b)^{m-1}(a+(m-1)b)$. This can be easily checked
noting that $(1,1,...,1)$ is a $(a+(m-1)b)$-eigenvector and that
$\dim(\ker(\Lambda_{\lambda}-I(a-b)))=m-1$, giving us an $(a-b)$-eigenspace of
dimension $m-1$.

Let’s recall that $a=(\Lambda_{\lambda})_{ww}$ and
$b=(\Lambda_{\lambda})_{ww^{\prime}}$, with $w\neq w^{\prime}$. Our goal is to
find a root for the determinant, so we can either take $\lambda$ as a root of
$(a-b)$ or a root of $(a+(m-1)b)$. Our calculations show that the $\lambda$
which serves as the root of $(a-b)$ does not follow the format of Equation (7)
(as it can be readily resolved by canceling some terms). Therefore, we limit
our search to the $\lambda$ described by Equation (7) that serves as the root
of $(a+(m-1)b)$. More specifically, we deal with

$\epsilon((\Lambda_{\epsilon})_{ww}+(m-1)(\Lambda_{\epsilon})_{ww^{\prime}}))=A(\gamma)\epsilon^{2}+B(\gamma)\epsilon+C(\gamma)+O(\epsilon^{3}).$

Then, we can proceed in the same way as before, deriving $\gamma$ such that
$B(\gamma)=0$ and $\epsilon^{\pm}$ from the final quadratic expression

$\displaystyle\gamma$
$\displaystyle=\displaystyle\frac{-3k^{2}m+4k^{2}v+\lambda_{2}m-mr}{4kv\left(k^{2}+\lambda_{2}-r\right)},$
$\displaystyle\epsilon^{\pm}$
$\displaystyle=\pm\frac{\sqrt{k}\sqrt{m}}{\sqrt{2v}\sqrt{k+1}}+O\left(\frac{1}{v}\right).$

The expressions for $t_{\text{opt}}$ and $p_{\text{succ}}$ still derive from
the formulas provided by [19]. As the calculations in the cited paper
primarily focus on the two marked cases, and we have already used its final
formulas in the previous subsection, we will now elaborate on these
expressions in more detail. We start by observing that [19] provides us with
an expression for the probability of locating a marked vertex as a function of
time, following certain assumptions (which we have also considered). The
expression is as follows

$p(t)=4|\braket{\lambda}{\psi(0)}|^{2}\sum_{w\in
W}|\braket{w}{\lambda}|^{2}\sin^{2}\epsilon t+o(1)+o(\epsilon t),$ (19)

which implies that $t_{\text{opt}}=\frac{\pi}{2\epsilon}$, giving us

$t_{\text{opt}}=\frac{\pi\sqrt{k+1}}{\sqrt{2k}\sqrt{m}}\sqrt{v}+O\left(\frac{1}{\sqrt{v}}\right).$
(20)

The success probability is

$p_{\text{succ}}=4|\braket{\lambda}{\psi(0)}|^{2}\sum_{w\in
W}|\braket{w}{\lambda}|^{2}.$ (21)

First, we need to find each $|\braket{w}{\lambda}|$, taking note that the
definition of $\Lambda_{\lambda}$ in [19] establishes that the vector with
$|\braket{w}{\lambda}|$ as its coordinates is a 0-eigenvector. Based on our
choice of $\epsilon$, we have $u=(1,1,...,1)$ as a 0-eigenvector. This is a
multiple of the desired vector, and it already demonstrates that
$|\braket{w}{\lambda}|=|\braket{w^{\prime}}{\lambda}|$ for every pair
$(w,w^{\prime})$. We find a correction factor $c$, which is provided in [19]
and it follows that:

$\braket{w}{\lambda}=c=\frac{k}{\sqrt{2}\sqrt{m}\sqrt{k^{2}-\lambda_{2}+r}}+\left(\frac{1}{\sqrt{v}}\right).$

Knowing this term, we can also calculate

$\displaystyle\braket{\psi(0)}{\lambda}$
$\displaystyle=-\frac{1}{\lambda+\gamma\phi_{0}}\sum_{w\in
W}\braket{w}{\lambda}\braket{\psi_{0}}{w}$
$\displaystyle=-\frac{\sqrt{2}}{2}+o(1).$

Substituting all the calculated terms in Equation (21) finally yields

$p_{\text{succ}}=\frac{k}{k+1}+O\left(\frac{1}{\sqrt{v}}\right).$ (22)

#### More general cases

Another potential generalization is the scenario where the subgraph induced by
the marked vertices is regular with parts of equal size. Although calculating
the determinant remains a challenging task in this case, we can leverage the
fact that the sum of all rows is the same. Consequently, we can work with the
eigenvector consisting entirely of ones and find the $\lambda$ value that
results in a zero eigenvalue.

Let $m$ represent the number of marked vertices in each part of the bipartite
graph, and let $d$ denote the number of marked vertices each marked vertex is
connected to. Additionally, let us define $a$ as
$(\Lambda_{\lambda})_{ww^{\prime}}$ when $w$ and $w^{\prime}$ are adjacent,
$b$ as the expression when they are in different parts and non-adjacent, and
$c$ as the expression for vertices in the same part. Then, the sum of each row
in $\Lambda_{\lambda}$ will be equal to

$(\Lambda_{\lambda})_{ww}+da+(m-d)b+(m-1)c.$

It is the eigenvalue associated with vector $(1,1,...,1)$. We wish to reduce
this eigenvalue to zero. We employ the same strategy of multiplying the
expression by $\epsilon$, identifying the $\gamma$ that cancels out the linear
term, and then calculating the values of $\epsilon^{\pm}$. We obtain

$\displaystyle\gamma$ $\displaystyle=\frac{k\left(km-
dv+(m-v)\sqrt{k-\lambda_{2}}\right)}{v\sqrt{k-\lambda_{2}}\,(k-\lambda_{2}-k^{2})},$
$\displaystyle\epsilon^{\pm}$
$\displaystyle=\pm\frac{\sqrt{m(k+d\sqrt{k})}}{\sqrt{k+1}}\frac{1}{\sqrt{v}}+O\left(\frac{1}{v}\right).$

From this, we can directly derive

$t_{\text{opt}}=\displaystyle\frac{\pi\sqrt{k+1}}{2\sqrt{m(k+d\sqrt{k})}}\sqrt{v}+O\left(\frac{1}{v}\right).$
(23)

In the preceding equation, it’s worth noting that we can revert to the
expression for two marked vertices in separate parts ($m=1$) in both the
adjacent ($d=1$) and non-adjacent ($d=0$) cases. The scenario where the two
marked vertices are within the same part constitutes a subcase of the
discussion from the prior subsection.

To calculate the success probability, we follow the method used in the
previous subsection calculating $\braket{\lambda}{w}$ and
$\braket{\psi(0)}{\lambda}$ to obtain

$p_{\text{succ}}=\frac{4\,\sqrt{k}\left(k+1\right)\left(d+\sqrt{k}\right)^{3}}{\left((k+1)(d+2\sqrt{k})+2d\sqrt{k}\right)^{2}}+O\left(\frac{1}{v}\right).$

In every case we analyzed, it’s evident that the primary factor affecting the
success probability is independent of both the number of vertices and the
number of marked vertices. In every instance, when we enhance the degree $k$
of the graph and the number of nodes $v$, the probability approaches 1. It’s
also crucial to highlight that in the final scenario, where the marked
vertices are connected, the success probability rises in proportion to the
degree of connectivity among the marked vertices. Here, $d$ represents the
degree of the induced subgraph.

Given that the success probability is $o(1)$, our main concern becomes
determining the optimal number of steps to infer the time complexity of the
search algorithm. While the optimal time is $O(\sqrt{v})$, Equations (20) and
(23) elucidate how the number of marked vertices $m$ and their connectivity
(expressed by $d$) can reduce the algorithm’s runtime.

A notable point concerning $t_{\text{opt}}$ in Equation (23), particularly in
cases where each part of the bipartite graph features $m$ marked vertices,
emerges as follows: When $k>m$, we have the option to choose a set of marked
vertices inducing a complete bipartite subgraph, where $d=m$. This implies
that each marked vertex connects to the marked vertices in the opposing part.
Under these conditions, $t_{\text{opt}}=O\left(\frac{\sqrt{v}}{m}\right)$,
assuming $m$ stays below a certain fixed $k$. Such behavior is not common in
quantum searches that involve multiple marked vertices.

##  4 Final remarks

In this work, we investigated quantum search algorithms on bipartite graphs
using continuous-time quantum walks, with a particular focus on the
significance of combinatorial $t$-designs. We determined the eigenvalues and
eigenvectors of symmetric $t$-designs. By carefully analyzing these designs
and their incidence matrices, we identified a subset with symmetries that are
particularly useful for determining the time complexity in scenarios with
multiple marked vertices. Our findings highlight the effectiveness of the
continuous-time quantum walk on certain symmetric $t$-designs. We show that
these designs can achieve a running time of $O(\sqrt{n})$, where $n$ is the
number of vertices in the corresponding bipartite graph, regardless of the
number of marked vertices. Additionally, the success probability remains
consistently $o(1)$, but it converges to unity in certain cases. These results
are among the first to study multiple marked elements on complex geometric
structures where the time complexity of spatial search algorithms can be
analytically derived using the continuous-time model.

This work deepens our understanding of the relationship between quantum walks
and combinatorial graph theory, especially within the context of symmetrical
$t$-designs. Additionally, it aids in paving the path for analytically
determining the time complexity of quantum-walk-based search algorithms on
bipartite graphs with multiple marked vertices, a notably challenging task in
the continuous-time scenario. Anticipated future research offers the prospect
of more comprehensive results, potentially broadening the relevance of non-
symmetric $t$-designs in quantum search algorithms.

## Conflict of interest

The authors declare that there is no conflict of interest.

## Data availability

All data generated or analyzed during this study are included in this
published article.

## Acknowledgements

We are indebted to Chris Godsil and Qiuting Chen for their insightful
discussions, which significantly contributed to the formulation of Theorem 1
[26]. The work of P. Lugão was supported by CNPq grant number 140897/2020-8,
and FAPERJ grant number E-26/202.351/2022. The work of R. Portugal was
supported by FAPERJ grant number CNE E-26/200.954/2022, and CNPq grant numbers
308923/2019-7 and 409552/2022-4. The authors have no competing interests to
declare that are relevant to the content of this article.

## References

  * [1] E. Farhi and S. Gutmann.  Quantum computation and decision trees.  Phys. Rev. A, 58:915–928, 1998.
  * [2] A. M. Childs and J. Goldstone.  Spatial search by quantum walk.  Phys. Rev. A, 70:022314, 2004.
  * [3] S. Marsh and J. B. Wang.  Combinatorial optimization via highly efficient quantum walks.  Phys. Rev. Res., 2:023302, 2020.
  * [4] Karuna Kadian, Sunita Garhwal, and Ajay Kumar.  Quantum walk and its application domains: A systematic review.  Computer Science Review, 41:100419, 2021.
  * [5] R. Portugal.  Quantum Walks and Search Algorithms.  Springer, Cham, 2nd edition, 2018.
  * [6] L. K. Grover.  Quantum mechanics helps in searching for a needle in a haystack.  Phys. Rev. Lett., 79(2):325–328, 1997.
  * [7] P. Philipp, L. Tarrataca, and S. Boettcher.  Continuous-time quantum search on balanced trees.  Phys. Rev. A, 93:032305, 2016.
  * [8] Hajime Tanaka, Mohamed Sabri, and Renato Portugal.  Spatial search on johnson graphs by continuous-time quantum walk.  Quantum Information Processing, 21(2):74, 2022.
  * [9] Douglas R. Stinson.  Combinatorial Designs: Constructions and Analysis.  Springer, New York, 2004.
  * [10] Thomas Beth, Dieter Jungnickel, and Hanfried Lenz.  Design Theory, volume 1.  Cambridge University Press, Cambridge, UK, second edition, 1999.
  * [11] O. S. Rothaus.  On “bent” functions.  Journal of Combinatorial Theory, Series A, 20(3):300–305, 1976\.
  * [12] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine.  Exact and approximate unitary 2-designs and their application to fidelity estimation.  Phys. Rev. A, 80:012304, 2009.
  * [13] Andris Ambainis and Joseph Emerson.  Quantum t-designs: t-wise independence in the quantum world.  In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07), pages 129–140, 2007.
  * [14] Joseph Emerson, Robert Alicki, and Karol Życzkowski.  Scalable noise estimation with random unitary operators.  Journal of Optics B: Quantum and Semiclassical Optics, 7(10):S347, 2005.
  * [15] C. Godsil and G. F. Royle.  Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics. volume 207 of Graduate Texts in Mathematics. Springer, New York, 2001\.
  * [16] N. Shenvi, J. Kempe, and K. B. Whaley.  A quantum random walk search algorithm.  Phys. Rev. A, 67(5):052307, 2003.
  * [17] Thomas G. Wong.  Spatial search by continuous-time quantum walk with multiple marked vertices.  Quantum Information Processing, 15(4):1411–1443, 2016.
  * [18] G. A. Bezerra, P. H. G. Lugão, and R. Portugal.  Quantum-walk-based search algorithms with multiple marked vertices.  Phys. Rev. A, 103:062202, 2021.
  * [19] P. H. G. Lugão, R. Portugal, M. Sabri, and H. Tanaka.  Multimarked spatial search by continuous-time quantum walk.  arXiv:2203.14384, 2022.
  * [20] Simon Apers, Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland.  Quadratic speedup for spatial search by continuous-time quantum walk.  Phys. Rev. Lett., 129:160502, 2022.
  * [21] Mathieu Roget, Hachem Kadri, and Giuseppe Di Molfetta.  Optimality conditions for spatial search with multiple marked vertices.  Phys. Rev. Res., 5:033021, 2023.
  * [22] S. Chakraborty, L. Novo, and J. Roland.  Optimality of spatial search via continuous-time quantum walks.  Phys. Rev. A, 102:032214, 2020.
  * [23] A. Chan, C. D. Godsil, C. Tamon, and W. Xie.  Of shadows and gaps in spatial search.  Quantum Inf. Comput., 22(13&14):1110–1131, 2022.
  * [24] C. F. Teixeira da Silva, D. Posner, and R. Portugal.  Walking on vertices and edges by continuous-time quantum walk.  Quantum Information Processing, 22(2):93, Jan 2023.
  * [25] Renato Portugal and Jalil Khatibi Moqadam.  Implementation of continuous-time quantum walks on quantum computers.  ArXiv:2212.08889, 2022.
  * [26] Qiuting Chen.  PhD thesis, University of Waterloo, https://uwspace.uwaterloo.ca/handle/10012/19958.


$\tau_{\mathbf{c}_{[n]}}:(\mathbb{F}\bbslash{\mathbb{C}})(\mathbf{c}_{[n]})\to{\mathcal{D}}(\mathbf{c}_{[n]}).$

Effectively, we are taking the beginning of each sub-division of
$\mathbf{d}_{[k_{0}+...+k_{n}]}$, which looks similar to (but is different
from) the projection from the simplicial replacement of a category to the
category itself.

We now prove that the functors $\tau_{\mathbf{c}_{[n]}}$ are homotopy cofinal,
hence induce homotopy equivalences. For the case of a single object,
$\mathbf{c}=c_{0}$, we see that we are simply comparing the category
${\mathcal{D}}(c)$ and its simplicial replacement. And it is well known that
for any category ${\mathcal{X}}$, the initial element functor
$\mathbb{X}\to{\mathcal{X}}$ is homotopy cofinal.

By induction, consider the following diagram with
$\mathbf{c}_{[n-1]}=c_{1}\to...\to c_{n}$ and both vertical functors given by
natural projections. The bottom arrow $\tau_{n-1}$ is homotopy cofinal, both
vertical arrows are opfibrations, and the restriction of $\tau_{n}$ on the
fibres of the left arrow gives, again, the standard functor between a category
and its simplicial replacement. Thus $\tau_{n}$ is homotopy cofinal by Lemma
4.19.

To continue, we also need to study the fibres of the projection

(4.1)
$(\mathbb{F}\bbslash{\mathbb{C}})(\mathbf{c}^{\prime}_{[k]}\to\mathbf{c}_{[n]})\to(\mathbb{F}\bbslash{\mathbb{C}})(\mathbf{c}^{\prime}_{[k]}).$

Fix a morphism $s:\mathbf{c}^{\prime}_{[k]}\to\mathbf{c}_{[n]}$ in
${\mathbb{C}}$ and an object $(\mathbf{d},\mathbf{c}^{\prime}_{[k]},f)$ in
$(\mathbb{F}\bbslash{\mathbb{C}})(\mathbf{c}^{\prime}_{[k]})$. Denote by
$Fibre(s,\mathbf{d},\mathbf{c}^{\prime}_{[k]},f)$ the fibre of the projection
(4.1) over $(\mathbf{d},\mathbf{c}^{\prime}_{[k]},f)$.

An object of $Fibre(s,\mathbf{d},\mathbf{c}^{\prime}_{[k]},f)$ is, by
definition, an object $(\mathbf{d}^{\prime},\mathbf{c}_{[n]},f^{\prime})$ and
a morphism $s^{\prime}:\mathbf{d}\to\mathbf{d}^{\prime}$ such that $s\circ
f=f^{\prime}\circ\mathbb{F}(s^{\prime})$. Since ${\mathbb{C}}$ is discretely
opfibred over $\Delta$, the problem is completely defined by its image in
$\Delta$. The category $Fibre(s,\mathbf{d},\mathbf{c}^{\prime}_{[k]},f)$ does
not, thus, depend on the exact detail of the categories
${\mathcal{D}},{\mathcal{C}}$, so we can replace them with one-object
categories. Effectively, we are given a map $g:[n]\to[k]$ and a surjective map
$h:[m]\twoheadrightarrow[k]$, and we consider triples
$[m^{\prime}],h^{\prime},g^{\prime}$, with
$h^{\prime}:[m^{\prime}]\twoheadrightarrow[n]$ surjective,
$g^{\prime}:[m^{\prime}]\to[m]$ arbitrary, and $h\circ
g^{\prime}=h^{\prime}\circ g$.

Factor $[n]\stackrel{{\scriptstyle g}}{{\to}}[k]$ as a surjection and an
injection, $[n]\stackrel{{\scriptstyle
g_{s}}}{{\to}}[n^{\prime\prime}]\stackrel{{\scriptstyle g_{i}}}{{\to}}[k]$,
and observe that we can take pullbacks of surjections along $g_{i}$, with
results being surjections. We thus see that we are studying the category of
possible diagrams where the whole right (pullback) square and $g_{s}$ are
fixed. The data of $[m^{\prime}]\twoheadrightarrow[n]$ is equivalent to an
object of $\Delta^{n+1}$. Specifying a compatible map
$[m^{\prime}]\to[m^{\prime\prime}]$ then gives us a functor
$L:(\Delta^{n+1})^{\sf op}\to{\rm\bf Set}$: there are no non-trivial morphisms
between two different liftings. Moreover, if we denote by
$g_{s,*}:\Delta^{n+1}\to\Delta^{n^{\prime\prime}+1}$ the post-composition
functor, we see that $L\cong g_{s,*}^{*}S$, where
$S:(\Delta^{n^{\prime\prime}+1})^{\sf op}\to{\rm\bf Set}$ is the functor
represented by $[m^{\prime\prime}]\twoheadrightarrow[n^{\prime\prime}]$.

It will thus suffice to prove the following. Consider any surjection
$g:[n]\twoheadrightarrow[k]$, and the induced functor
$g_{*}:\Delta^{n+1}\to\Delta^{k+1}$. Then we need to show that for any
representable functor $S:(\Delta^{k+1})^{\sf op}\to{\rm\bf Set}$, the
$n+1$-fold simplicial set $(g_{*})^{*}S$ is contractible. By induction on $k$,
it suffices to consider the case $k=0$. Take the diagonal embedding
$\delta:\Delta\to\Delta^{n+1}$. Then $|\delta^{*}(g_{*})^{*}S|$ is equivalent
to $|(g_{*})^{*}S|$, so it suffices to prove that for any $X:\Delta^{\sf
op}\to{\rm\bf Set}$, one has a homotopy equivalence $|i_{n+1}^{*}X|\cong|X|$,
where $i_{n+1}=g_{*}\circ\delta:\Delta\to\Delta$. Explicitly, $i_{n+1}$ acts
exactly as $n+1$-fold edgewise subdivision functor, and $|i_{n+1}^{*}X|$ is
homotopically equivalent (actually homeomorphic) to $|X|$ for any simplicial
set $X$. ∎

###  4.2. Sections over relative comma objects

In the following, it will be useful to axiomatise the relevant properties of
the functor $\mathbf{E}\to{\mathbb{C}}$.

######  Definition 4.20.

Let ${\mathcal{X}}$ be a $\Delta$-indexed category. A _model Segal
bifibration_ over ${\mathcal{X}}$ is a bifibration
$\mathbf{E}\to{\mathcal{X}}$ with the following properties.

  1. (1)

The bifibration $\mathbf{E}\to{\mathcal{X}}$ is a Quillen presheaf: the fibres
$\mathbf{E}(x)$ are model categories, and for each $f:x\to y$, the adjunction
$f_{!}:\mathbf{E}(x)\rightleftarrows\mathbf{E}(y):f^{*}$ is a Quillen pair.

  2. (2)

The following base change condition holds. For a commutative square with
vertical arrows Segal, and horizontal arrows projecting to initial element
preserving maps in $\Delta$, the induced natural transformation
${\mathbb{L}}f_{!}{\mathbb{R}}\alpha^{*}\to{\mathbb{R}}\beta^{*}{\mathbb{L}}g_{!}$
is an isomorphism.

By [1, Theorem 1] we have that the category of sections ${\sf
Sect}({\mathcal{X}},\mathbf{E})$ carries a Reedy model structure.

######  Definition 4.21.

Let $\mathbf{E}\to{\mathcal{X}}$ be a model Segal bifibration, as described
above. A section $X:{\mathcal{X}}\to\mathbf{E}$ is called _Segal_ if for any
Segal map $f:x\to y$ the induced morphism

$X(x)\to{\mathbb{R}}f^{*}X(y)$

is an isomorphism in ${\rm Ho}\,\mathbf{E}(x)$.

We denote by ${\sf Sect}_{\mathscr{S}}({\mathcal{X}},\mathbf{E})$ the
corresponding full subcategory.

######  Lemma 4.22.

Let $X$ be a Segal section of $\mathbf{E}\to{\mathcal{X}}$. Then for each
degeneracy $s:x\twoheadrightarrow y$ of ${\mathcal{X}}$, both induced maps
$X(x)\to{\mathbb{R}}s^{*}X(y)$ and ${\mathbb{L}}s_{!}X(x)\to X(y)$ are
isomorphisms in ${\rm Ho}\,\mathbf{E}(x)$ and ${\rm Ho}\,\mathbf{E}(y)$
respectively.

###### Proof.

Similar to Lemma 2.12. ∎

For a functor $F:{\mathcal{Y}}\to{\mathcal{X}}$, we would like to study what
happens when we lift Segal sections from ${\mathcal{X}}$ to
$F\bbslash{\mathcal{X}}$ via the natural projection $p_{\mathcal{X}}$. In
general, the latter is an opfibration over face maps, which implies the
following.

######  Proposition 4.23.

Let $\mathbf{E}\to{\mathcal{X}}$ be a model bifibration over a
$\Delta$-indexed category ${\mathcal{X}}$, and
$p:{\mathcal{O}}\to{\mathcal{X}}$ be a right-compatible Reedy functor. Then
there is an induced Quillen adjunction

$p_{!}:{\sf Sect}({\mathcal{O}},p^{*}\mathbf{E})\rightleftarrows{\sf
Sect}({\mathcal{X}},\mathbf{E}):p^{*}$

where the right adjoint is the pullback functor.

Furthermore, if $p$ is a left resolution, then the pushforward
${\mathbb{L}}p_{!}$ admits a simplified expression

${\mathbb{L}}p_{!}X(x)\cong{\mathbb{L}}\operatorname{\varinjlim}_{{\mathcal{O}}(x)}X|_{{\mathcal{O}}(x)},$

suitably functorial in $x$.

###### Proof.

By definition, the functor $p$ identifies the matching objects computed for
$o$ in ${\mathcal{O}}$ with those of its image $p(o)$. This permits to verify
that $p^{*}$ preserves Reedy fibrations and trivial Reedy fibrations. Its left
adjoint, $p_{!}$, is not hard to compute. Given $x\in{\mathcal{X}}$ and a
section $Y:{\mathcal{O}}\to\mathbf{E}$, denote by $p/x$ the usual comma
category fibre consisting of pairs $(o,p(o)\to x)$; we then have

$p_{!}Y(x)\cong\operatorname{\varinjlim}_{p/x}Res_{x}Y|_{p/x}$

with $Res_{x}:Sect(p/x,\mathbf{E})\to\mathbf{E}(x)^{p/x}$ being the
restriction functor induced by the opfibration structure on $\mathbf{E}$. The
category $p/x$ is Reedy with the same latching objects as in ${\mathcal{O}}$,
and the functor $Res_{x}$, as can be checked, preserves (trivial) Reedy
cofibrations. This implies the same expression for the derived functor,

$\mathbb{L}p_{!}Y(x)\cong\mathbb{L}\operatorname{\varinjlim}_{p/x}\mathbb{L}Res_{x}Y|_{p/x}.$

It remains to see that the inclusion functor $i:{\mathcal{O}}(x)\to p/x$ is
homotopy cofinal in the case of a left resolution. For this, we consider the
categories $z\backslash i$, where $z=(o,p(o)\to x)$ is an object of the comma
category $p/x$. One can see that the category $z\backslash i$ is the category
of commutative squares where the upper left object and the bottom arrow are
fixed. It is the same category as the fibre over $o$ of the projection
${\mathcal{O}}(p(o)\to x)\to{\mathcal{O}}(p(o))$, and it is contractible.
Which in turn implies that we can restrict the homotopy colimits from $p/x$ to
${\mathcal{O}}(x)$. ∎

######  Corollary 4.24.

In the situation of Proposition 4.23, if the functor
$p:{\mathcal{O}}\to{\mathcal{X}}$ is a left resolution, then the pullback
functor $p^{*}$ factors through the full subcategory ${\sf
Sect}_{loc}({\mathcal{O}},p^{*}\mathbf{E})$ consisting of those sections
$Y:{\mathcal{O}}\to p^{*}\mathbf{E}$ which send fibrewise maps in
${\mathcal{O}}$ to weak equivalences in the fibres of $\mathbf{E}$. Moreover
$p^{*}:{\sf Sect}({\mathcal{X}},\mathbf{E})\to{\sf
Sect}_{loc}({\mathcal{O}},p^{*}\mathbf{E})$ is a weak equivalence of relative
categories.

###### Proof.

For $Y=p^{*}X$, we see that

${\mathbb{L}}p_{!}Y(x)\cong{\mathbb{L}}\operatorname{\varinjlim}_{{\mathcal{O}}(x)}X(x)\cong
X(x)$

since the category ${\mathcal{O}}(x)$ is contractible. Conversely, given $Y$
which is homotopically constant on the fibres, we have that for any
$o\in{\mathcal{O}}(x)$, which exists since ${\mathcal{O}}(x)$ is nonempty, the
natural map $Y(o)\to{\mathbb{L}}\operatorname{\varinjlim}_{{\mathcal{O}}(x)}Y$
is an isomorphism in ${\rm Ho}\,\mathbf{E}(x)$ [10]. However,
${\mathbb{L}}\operatorname{\varinjlim}_{{\mathcal{O}}(x)}Y\cong(p_{!}Y)(x)\cong(p^{*}p_{!}Y)(o)$.
∎

Returning to the case of the relative comma category $F\bbslash{\mathcal{X}}$
for $F:{\mathcal{Y}}\to{\mathcal{X}}$, we note that, besides
$p_{\mathcal{X}}$, there is another projection functor
$p_{\mathcal{Y}}:F\bbslash{\mathcal{X}}\to{\mathcal{Y}}$, which is also fairly
special.

######  Lemma 4.25.

The functor $p_{\mathcal{Y}}$ is a discrete opfibration admitting a fully
faithful right adjoint $i_{\mathcal{Y}}:{\mathcal{Y}}\to
F\bbslash{\mathcal{X}}$ such that $F=p_{\mathcal{X}}i_{\mathcal{Y}}$. The
functor $p_{\mathcal{Y}}$ is also a right-compatible Reedy functor.

###### Proof.

The right adjoint is easy to see, and is given by sending $y\in{\mathcal{Y}}$
to
$i_{\mathcal{Y}}y=(y,F(y)\stackrel{{\scriptstyle=}}{{\twoheadleftarrow}}F(y))$,
its fully-faithfulness is then obvious. Its opfibration property is also
apparent, as the diagram can be completed to

(4.2) $\begin{diagram}$

using the face-degeneracy factorisation system inherited from $\Delta$. As in
Corollary 4.15, the lift (4.2) allows us to conclude that $p_{\mathcal{Y}}$ is
right-compatible. ∎

######  Proposition 4.26.

Let $\mathbf{E}\to{\mathcal{X}}$ be a model Segal bifibration over a
$\Delta$-indexed category ${\mathcal{X}}$, and
$F:{\mathcal{Y}}\to{\mathcal{X}}$ be a $\Delta$-indexed functor. Then the
functor $p_{\mathcal{Y}}:F\bbslash{\mathcal{X}}\to{\mathcal{Y}}$ induces a
Quillen adjunction

$i_{\mathcal{Y}}^{*}=p_{{\mathcal{Y}},!}:{\sf
Sect}(F\bbslash{\mathcal{X}},p^{*}_{\mathcal{Y}}F^{*}\mathbf{E})\rightleftarrows{\sf
Sect}({\mathcal{Y}},F^{*}\mathbf{E}):p_{\mathcal{Y}}^{*}$

where $i_{\mathcal{Y}}$ is the functor from Lemma 4.25. The functor
$p_{\mathcal{Y}}^{*}$ is a weak equivalence between the relative category
${\sf Sect}({\mathcal{Y}},F^{*}\mathbf{E})$ and the full subcategory of ${\sf
Sect}(F\bbslash{\mathcal{X}},p^{*}_{\mathcal{Y}}F^{*}\mathbf{E})$ consisting
of those $Y$ such that for each $p_{\mathcal{Y}}$-fibrewise map $f$ in
$F\bbslash{\mathcal{X}}$, the induced map $Y(f)$ is a weak equivalence.

###### Proof.

The adjunction $i^{*}_{\mathcal{Y}}\dashv p_{\mathcal{Y}}^{*}$ is easy to
verify, and the right-compatibility of $p_{\mathcal{Y}}$ makes its pullback
right Quillen. We now study the essential image of $p_{\mathcal{Y}}$. Note
that for each $y$, the fibre $y\bbslash{\mathcal{X}}$ of the opfibration
$p_{\mathcal{Y}}$ contains a final object $i_{\mathcal{Y}}y$, and is in
particular contractible. In a way similar to Corollary 4.24, we can now see
that the essential image of $\mathbb{R}p_{\mathcal{Y}}^{*}$ consists of
sections homotopically constant on fibres. ∎

###  4.3. Comparing the Segal sections

######  Definition 4.27.

A map $s:o\to o^{\prime}$ of $F\bbslash{\mathcal{X}}$ is _Segal_ if both its
projections $p_{\mathcal{X}}s$ and $p_{\mathcal{Y}}s$ are Segal maps in
${\mathcal{X}}$ and ${\mathcal{Y}}$ respectively.

######  Lemma 4.28.

Let

(4.3) $\begin{diagram}$

be a diagram in $\Delta$.

  1. (1)

If the map $\alpha$ is a left (respectively, right) interval inclusion, then
we can factor (4.3) as  with $\gamma\zeta=\beta$, $\gamma$ being a left
(respectively, right) interval inclusion, and $\zeta$ a surjection.

  2. (2)

If the map $\beta$ is a left (respectively, right) interval inclusion, then we
can factor (4.3) as  with $\alpha=\epsilon\mu$, and $\epsilon$ being a left
(respectively, right) interval inclusion, and the left square a pull-back.

###### Proof.

The second factorisation is evident. For the first, consider all the elements
contained in the image
$[k]\stackrel{{\scriptstyle\alpha}}{{\longrightarrow}}[l]\longrightarrow[n]$,
they will form an ordered subset included as a left (respectively, right)
interval. The map $\zeta$ is then forced to be a surjection. ∎

######  Lemma 4.29.

Given a surjection $[n]\twoheadrightarrow[m]$ and a left (right) interval
inclusion $\alpha:[k]\to[l]$, there exists a completion to a square with
horizontal arrows being left (right) interval inclusions. Same with $\alpha$
replaced by $\beta:[m]\to[n]$

###### Proof.

Clear. ∎

For a functor $F:{\mathcal{Y}}\to{\mathcal{X}}$ and a model Segal bifibration
$\mathbf{E}\to{\mathcal{X}}$, there are two bifibrations over the relative
comma category which one can obtain using pullback operations:
$p_{\mathcal{X}}^{*}\mathbf{E}\to F\bbslash{\mathcal{X}}$ and
$p_{\mathcal{Y}}^{*}F^{*}\mathbf{E}\to F\bbslash{\mathcal{X}}$. The
bifibration structure induces a Quillen adjunction

$S:{\sf
Sect}(F\bbslash{\mathcal{X}},p^{*}_{\mathcal{X}}\mathbf{E})\rightleftarrows{\sf
Sect}(F\bbslash{\mathcal{X}},p_{\mathcal{Y}}^{*}F^{*}\mathbf{E}):T.$

Over an object $(y,F(y)\stackrel{{\scriptstyle f}}{{\twoheadleftarrow}}x)$,
the functor $S$ amounts to post-composing with
$f_{!}:\mathbf{E}(x)\to\mathbf{E}(F(y))$, and the functor $T$ – with its right
adjoint $f^{*}$.

######  Proposition 4.30.

The Quillen adjunction $S\dashv T$ induces an adjoint equivalence

${\mathbb{L}}S:{\rm Ho}\,{\sf
Sect}_{Seg}(F\bbslash{\mathcal{X}},p^{*}_{\mathcal{X}}\mathbf{E})\rightleftarrows{\rm
Ho}\,{\sf
Sect}_{Seg}(F\bbslash{\mathcal{X}},p_{\mathcal{Y}}^{*}F^{*}\mathbf{E}):{\mathbb{R}}T$

where ${\rm Ho}\,{\sf
Sect}_{Seg}(F\bbslash{\mathcal{X}},p^{*}_{\mathcal{X}}\mathbf{E})$ denotes the
full subcategory of sections $Y:F\bbslash{\mathcal{X}}\to
p^{*}_{\mathcal{X}}\mathbf{E}$ for which the map
$Y(o)\to{\mathbb{R}}t^{*}Y(o^{\prime})$ induced from a Segal map $t:o\to
o^{\prime}$ is an isomorphism (similarly for
$p_{\mathcal{Y}}^{*}F^{*}\mathbf{E}$).

###### Proof.

The restriction to Segal sections is possible due to base change property of
the bifibration in question (Definition 4.20), as the adjoints are essentially
defined using the transition functors. We shall analyse both the unit and the
counit of the adjunction restricted to Segal sections.

Take a Segal section $Y:F\bbslash{\mathcal{X}}\to
p^{*}_{\mathcal{X}}\mathbf{E}$. Over $o=(y,F(y)\stackrel{{\scriptstyle
f}}{{\twoheadleftarrow}}x)$, the map $Y(o)\to{\mathbb{R}}T{\mathbb{L}}SY(o)$
is isomorphic to $Y(o)\to{\mathbb{R}}f^{*}{\mathbb{L}}f_{!}Y(o)$. Denote by
$x_{0}$ and $y_{0}$ the first vertices of $x$ and $y$; the evident map
$o=(y,F(y)\stackrel{{\scriptstyle
f}}{{\twoheadleftarrow}}x)\to(y_{0},F(y_{0})=x_{0})=o_{0}$ is then Segal. If
we denote then, using the Segal condition, we see that the map

$Y(o)\to{\mathbb{R}}f^{*}{\mathbb{L}}f_{!}Y(o)$

is isomorphic to

${\mathbb{R}}\pi_{x}^{*}Y(o_{0})\to{\mathbb{R}}f^{*}{\mathbb{L}}f_{!}{\mathbb{R}}\pi_{x}^{*}Y(o_{0}).$

Finally, using the base change from Definition 4.20, we see that the latter
map is isomorphic to

${\mathbb{R}}\pi_{x}^{*}Y(o_{0})\to{\mathbb{R}}f_{0}^{*}{\mathbb{R}}\pi_{y}^{*}Y(o_{0}),$

which is merely a differently written identity map.

The counit of the adjunction is treated similarly. ∎

######  Proposition 4.31 (Resolutions for $\Delta$-indexed categories).

Let $\mathbf{E}\to{\mathcal{X}}$ be a model Segal bifibration over a
$\Delta$-indexed category ${\mathcal{X}}$, and
$F:{\mathcal{Y}}\to{\mathcal{X}}$ be a $\Delta$-indexed functor. If $F$ is a
resolution, then

$F^{*}:{\sf Sect}_{Seg}({\mathcal{X}},\mathbf{E})\to{\sf
Sect}_{Seg}({\mathcal{Y}},F^{*}\mathbf{E})$

factors through those Segal sections $X:{\mathcal{Y}}\to F^{*}\mathbf{E}$ such
that ${\mathbb{R}}p_{\mathcal{Y}}^{*}X$ is homotopically constant on the
fibres of $p_{\mathcal{X}}:F\bbslash{\mathcal{X}}\to{\mathcal{X}}$, and is a
weak equivalence onto the subcategory of such $X$.

###### Proof.

Corollary 4.24 and Proposition 4.26 can be enhanced using Lemmas 4.28 and
4.29. For the projection
$p_{\mathcal{X}}:F\bbslash{\mathcal{X}}\to{\mathcal{X}}$, we get the following
result: the homotopical essential image of

$p_{\mathcal{X}}^{*}:{\sf Sect}_{Seg}({\mathcal{X}},\mathbf{E})\to{\sf
Sect}(F\bbslash{\mathcal{X}},p^{*}_{\mathcal{X}}\mathbf{E})$

consists of those sections $Y$ for which

  1. (1)

the map $Y(o)\to{\mathbb{R}}t^{*}Y(o^{\prime})$ induced from a Segal map
$t:o\to o^{\prime}$ of $F\bbslash{\mathcal{X}}$ is an isomorphism,

  2. (2)

the usual condition applies, that is, homotopical constancy on the fibres of
$p_{\mathcal{X}}$.

The necessary observation is that ${\mathbb{L}}p_{{\mathcal{X}},!}Y$ is Segal,
as one can verify by lifting Segal maps from ${\mathcal{X}}$ to
$F\bbslash{\mathcal{X}}$ using Lemma 4.29.

For the projection $p_{\mathcal{Y}}$, we get, formally, that the homotopical
essential image of

$p_{\mathcal{Y}}^{*}:{\sf Sect}_{Seg}({\mathcal{Y}},F^{*}\mathbf{E})\to{\sf
Sect}(F\bbslash{\mathcal{X}},p^{*}_{\mathcal{Y}}F^{*}\mathbf{E})$

consists of those sections $Z$ for which

  1. (1)

the map $Z(o)\to{\mathbb{R}}t^{*}Z(o^{\prime})$ induced from a Segal map
$t:o\to o^{\prime}$ of $F\bbslash{\mathcal{X}}$ is an isomorphism,

  2. (2)

the usual condition applies, that is, homotopical constancy on the fibres of
$p_{\mathcal{Y}}$.

Now we need to pass between two different bifibrations. Proposition 4.30
implies that no information is lost by applying $T$ and $S$ to the sections of
interest.

Let $Y:F\bbslash{\mathcal{X}}\to p_{\mathcal{X}}^{*}\mathbf{E}$ be a Segal
section constant on the fibres of $p_{\mathcal{X}}$. We then see that
${\mathbb{L}}S(Y)$ is a Segal section which is automatically constant on the
fibres of $p_{\mathcal{Y}}$: these fibres are $y\bbslash{\mathcal{X}}$, with
only possible maps being induced from degeneracies in ${\mathcal{X}}$, and any
derived section coming from ${\mathcal{X}}$ is constant along degeneracies
(Lemma 4.22). Thus ${\mathbb{L}}S(Y)$ is contained in the essential image of
$p^{*}_{\mathcal{Y}}$.

For the converse, we see that in order for $Z:F\bbslash{\mathcal{X}}\to
p_{\mathcal{Y}}^{*}F^{*}\mathbf{E}$ to belong to the essential image of
$p^{*}_{\mathcal{X}}$, we need exactly that ${\mathbb{R}}T(Z)$ is
homotopically constant on the fibres of $p_{\mathcal{X}}$. Both precedent
observations and the fact that ${\mathbb{R}}T{\mathbb{R}}p_{\mathcal{Y}}^{*}X$
is homotopically constant on the fibres of $p_{\mathcal{X}}$ iff
${\mathbb{R}}p_{\mathcal{Y}}^{*}X$ is such imply the theorem. ∎

The first corollary is a result which is, perhaps surprisingly, not obvious.

######  Corollary 4.32.

Let $F:{\mathcal{D}}\to{\mathcal{C}}$ be an equivalence of categories and
${\mathcal{E}}\to{\mathcal{C}}$ a model opfibration. Then the induced pullback
functor $\mathbb{F}^{*}:{\sf DSect}({\mathcal{C}},{\mathcal{E}})\to{\sf
DSect}({\mathcal{D}},{\mathcal{E}})$ is an equivalence of relative categories.

###### Proof.

Denote by ${\mathcal{I}}$ the category whose objects are triples
$(d,c,F(d)\cong c)$. Both natural projections
$\pi_{\mathcal{C}}:{\mathcal{I}}\to{\mathcal{C}}$ and
$\pi_{\mathcal{D}}:{\mathcal{I}}\to{\mathcal{D}}$ are equivalences (hence
resolutions) and isofibrations; $\pi_{\mathcal{D}}$ admits a canonical inverse
equivalence $i_{\mathcal{D}}$ such that $\pi_{\mathcal{C}}\circ
i_{\mathcal{D}}=F$. The functor $\pi_{\mathcal{C}}$ also admits a section
$i_{\mathcal{C}}$ that corresponds to choosing an equivalence inverse to $F$.
Denote by $\pi_{\mathbb{C}},\pi_{\mathbb{D}},i_{\mathbb{C}},i_{\mathbb{D}}$
the corresponding simplicial replacement functors.

A map $f$ in ${\mathcal{I}}$ is an isomorphism iff it is true for either
$\pi_{\mathcal{C}}f$ or $\pi_{\mathcal{D}}f$. This together with Proposition
4.31 implies that the pullbacks $\pi_{\mathbb{C}}^{*}:{\sf
DSect}({\mathcal{C}},{\mathcal{E}})\to{\sf
DSect}({\mathcal{I}},\pi_{\mathcal{C}}^{*}{\mathcal{E}})$ and
$\pi_{\mathbb{D}}^{*}:{\sf DSect}({\mathcal{D}},F^{*}{\mathcal{E}})\to{\sf
DSect}({\mathcal{I}},\pi_{\mathcal{D}}^{*}F^{*}{\mathcal{E}})$ are weak
equivalences of relative categories. The same is thus true for
$i_{\mathbb{C}}^{*}$ and $i_{\mathbb{D}}^{*}$.

Denote by $[[n]]$ the category that has two copies of $[n]$ inside of it,
denoted $0\to...\to n$ and $0^{\prime}\to...\to n^{\prime}$, and exactly one
isomorphism $i\cong i^{\prime}$ for each $0\leq i\leq n$, with the obvious
commutativity identities. Any object $(c,d,Fd\cong c)$ of ${\mathcal{I}}$
yields a map $[[0]]\to{\mathcal{C}}$; similarly, it is true that given an
object $\sigma$ of the simplicial replacement ${\mathbb{I}}$, we have an
associated functor $\sigma:[[n]]\to{\mathcal{C}}$ whose first row looks like
$Fd_{i}$ and the second row like $c_{i}$. We can use this notation to define
$\tilde{\mathbf{E}}(\sigma)={\sf Sect}([[n]],\sigma^{*}{\mathcal{E}}^{\top})$
and form the covariant Grothendieck construction to get
$\tilde{\mathbf{E}}\to{\mathbb{I}}$. Evaluating sections at the top or the
bottom row induces functors
$\pi_{\mathbb{D}}^{*}\mathbb{F}^{*}\mathbf{E}\stackrel{{\scriptstyle
q}}{{\leftarrow}}\tilde{\mathbf{E}}\stackrel{{\scriptstyle
p}}{{\rightarrow}}\pi_{\mathbb{C}}^{*}\mathbf{E}$ over ${\mathbb{I}}$ that are
furthermore seen to be equivalences. We can promote
$\tilde{\mathbf{E}}\to{\mathbb{I}}$ to a model Segal bifibration, such that
the equivalences $q$ and $p$ preserve all parts of the (fibrewise) model
structure. It makes sense to speak of Segal sections of
$\tilde{\mathbf{E}}\to{\mathbb{I}}$.

Observe now that we have the following diagram: This diagram commutes up to an
isomorphism: a section $X:{\mathbb{I}}\to\tilde{\mathbf{E}}$ can be evaluated
on those $\sigma:[[n]]\to{\mathcal{C}}$ that look like creating an isomorphism
between the restriction of $X(\sigma)$ to the top and the bottom rows.
Moreover $p_{*},q_{*},i_{\mathbb{C}}^{*},i_{\mathbb{D}}^{*}$ are weak
equivalences; it thus follows that $\mathbb{F}^{*}$ is one as well. ∎

###### Proof of Proposition 4.7..

Given an arbitrary resolution $F:{\mathcal{D}}\to{\mathcal{C}}$, we can factor
it as $F=\tilde{F}G$, where $\tilde{F}$ is an isofibration and a resolution,
and $G$ is an equivalence. Applying Proposition 4.31 for $\tilde{\mathbb{F}}$
and Corollary 4.32 for $G$, we get that ${\sf
DSect}({\mathcal{C}},{\mathcal{E}})\to{\sf
DSect}_{F^{*}Iso_{\mathcal{C}}}({\mathcal{D}},F^{*}{\mathcal{E}})$ is a weak
equivalence of relative categories, with $F^{*}Iso_{\mathcal{C}}$ denoting the
$F$-isomorphisms. Given any subset ${\mathcal{S}}$ of maps of ${\mathcal{C}}$,
if we ever have a map

$(c_{0}\stackrel{{\scriptstyle{\mathcal{S}}}}{{\to}}...\stackrel{{\scriptstyle{\mathcal{S}}}}{{\to}}c_{k}\to
c_{k+1}\to...\to c_{n})\longrightarrow(c_{k}\to c_{k+1}\to...\to c_{n})$

in ${\mathbb{C}}$, then the resolution property of $F$ allows us to find a map
in ${\mathbb{D}}$ that looks like

$(d_{0}\stackrel{{\scriptstyle
F^{*}{\mathcal{S}}}}{{\to}}...\stackrel{{\scriptstyle
F^{*}{\mathcal{S}}}}{{\to}}d_{k}\to d_{k+1}\to...\to
d_{n})\longrightarrow(d_{k}\to d_{k+1}\to...\to d_{n})$

and such that its $\mathbb{F}$-image covers the ${\mathbb{C}}$-map in
question. This observation allows us to see that any
$F^{*}{\mathcal{S}}$-constant derived section $X$ is the
$\mathbb{F}^{*}$-image of a ${\mathcal{S}}$-constant derived section. ∎

## References

  * [1] Edouard Balzin, Reedy Model Structures in Families, preprint https://arxiv.org/abs/1803.00681
  * [2] Eduard Balzin, Grothendieck Fibrations and Homotopical Algebra, PhD thesis
  * [3] Clark Barwick, On (Enriched) Left Bousfield Localization of Model Categories, preprint https://arxiv.org/abs/0708.2067
  * [4] Clark Barwick, On the Dreaded Right Bousfield Localization, preprint https://arxiv.org/abs/0708.3435
  * [5] Clark Barwick, From operator categories to topological operads, preprint http://arxiv.org/abs/1302.5756
  * [6] Clark Barwick, Saul Glasman, Denis Nardin Dualizing cartesian and cocartesian fibrations, Theory and Applications of Categories 33, September 2014, https://arxiv.org/abs/1409.2165
  * [7] Clark Barwick, Daniel Kan, Relative categories: Another model for the homotopy theory of homotopy theories, preprint https://arxiv.org/abs/1011.1691
  * [8] Clark Barwick, Daniel Kan, In the category of relative categories the Rezk equivalences are exactly the DK-equivalences, preprint https://arxiv.org/abs/1012.1541
  * [9] Alexander Beilinson, Vladimir Drinfeld, Chiral Algebras, AMS 2004
  * [10] Denis-Charles Cisinski, Locally constant functors, Mathematical Proceedings of the Cambridge Philosophical Society (2009), 147, 593
  * [11] Denis-Charles Cisinski, Higher Categories and Homotopical Algebra, on-line book, available at http://www.mathematik.uni-regensburg.de/cisinski/CatLR.pdf
  * [12] William G. Dwyer, Philip S. Hirschhorn, Daniel M. Kan, and Jeffrey H. Smith, Homotopy Limit Functors on Model Categories and Homotopical Categories, AMS 2004
  * [13] David Gepner, Rune Haugseng, Thomas Nikolaus Lax colimits and free fibrations in $\infty$-categories, https://arxiv.org/abs/1501.02161
  * [14] Moritz Groth, On the theory of derivators, doctoral dissertation, Bonn 2011, http://www.math.uni-bonn.de/people/grk1150/DISS/dissertation-groth.pdf
  * [15] Alexander Grothendieck, Michèle Raynaud et al., Revêtements étales et groupe fondamental (SGA I), Lecture Notes in Mathematics 224, Springer 1971
  * [16] Vladimir Hinich, Dwyer–Kan localization revisited, Homology, Homotopy and Applications, Volume 18 (2016), Number 1 preprint https://arxiv.org/abs/1404.1852
  * [17] André Hirschowitz, Carlos Simpson, Descente pour les n-champs (Descent for n-stacks), preprint http://arxiv.org/abs/math/9807049
  * [18] Peter T. Johnstone, Sketches of an elephant: A topos theory compendium, Vol. 1-2. Oxford University Press, 2002.
  * [19] Jacob Lurie, Higher Topos Theory, book, Annals of mathematics studies ; no. 170
  * [20] Jacob Lurie, Higher Algebra, on-line book, available at http://www.math.harvard.edu/~lurie/
  * [21] Aaron Mazel-Gee, Goerss–Hopkins obstruction theory via model $\infty$-categories, PhD Thesis, 2016, etale.site
  * [22] Aaron Mazel-Gee, A user’s guide to co/cartesian fibrations, preprint https://arxiv.org/abs/1510.02402
  * [23] Graeme Segal, Categories and Cohomology Theories, Topology Vol. 13 pp. 293-312, Pergamon Press 1974
  * [24] Danny Stevenson, Covariant Model Structures and Simplicial Localization, North-West. Eur. J. Math. Vol. 3 (2017) pp. 141-202, https://arxiv.org/abs/1512.04815
  * [25] Bertrand Toën, Gabriele Vezzosi, Caractères de Chern, traces équivariantes et géométrie algébrique dérivée G. Sel. Math. New Ser. (2015) 21: 449, https://arxiv.org/abs/0903.3292
  * [26] Angelo Vistoli, Notes on Grothendieck topologies, fibered categories and descent theory, http://arxiv.org/abs/math/0412512
  * [27] Jonathan Woolf, The fundamental category of a stratified space, Journal of Homotopy and Related Structures, Vol. 4(2009), No. 1, pp. 359-387 https://arxiv.org/abs/0811.2580